您当前的位置：首页 > 公文大全 > 信访维稳公文 > 内容

自考数据结构历年考题综合

无忧文档网时间: 2020-12-15 03:18:08 阅读:次

2006.10 1.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( ) A.顺序存储结构 B.链式存储结构 C.索引存储结构 D.散列存储结构 2.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为( ) A.n-i+1 B.n-i C.i D.i-1 3.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( ) A.顺序表 B.用头指针表示的单循环链表 C.用尾指针表示的单循环链表 D.单链表 4.若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为( ) A.4 B.5 C.6 D.7 5．一棵有16结点的完全二叉树，对它按层编号，则对编号为7的结点X，它的双亲结点及右孩子结点的编号分别为（　　　） A．2，14 B．2，15 C．3，14 D．3，15 6．设有一5阶上三角矩阵A［1..5，1..5］，现将其上三角中的元素按列优先顺序存放在一堆数组B［1..15］中。已知B［1］的地址为100，每个元素占用2个存储单元，则A［3，4］的地址为（　　　） A．116 B．118 C．120 D．122 7．一个带权的无向连通图的最小生成树（　　　） A．有一棵或多棵 B．只有一棵 C．一定有多棵 D．可能不存在 8．下列有关图遍历的说法中不正确的是（　　　） A．连通图的深度优先搜索是一个递归过程 B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C．非连通图不能用深度优先搜索法 D．图的遍历要求每一顶点仅被访问一次 9．某算法的空间花费s(n)=2n+n100+nlog2n+n101，则其空间复杂度为（）。

A． O(nlog2n) B. O(n100) C. O(n101) D. O(2n) 10. 单链表中的存储密度一定（）。

A．小于0.5 B. 等于1 C. 大于0.1 D. 小于1 11．在顺序栈中删除一个元素，至少要移动（）元素。

A． 0 B. 1 C. n/2 D. n 12．空串是（）。

A．只包含空格符的串 B. 长度为0的串 C. 只包含一个空格符的串 D. 不含字母的串 13．采用三元组表存储稀疏矩阵，是为了（）。

A．节省存取时间 B. 节省存储空间 C. 提高对矩阵元素的访问速度 D. 提高对矩阵运算的可靠性 14．高度为h的二叉树最多有（）个节点。

A． 2h-1 B. 2h C. 2h-1 D. 2h-1+1 15．N个顶点，e条边的无权有向图的邻接矩阵中非零元素有（）个。

A． n B. n-e C. e D. e+n 16．直接选择排序在最好情况下的时间复杂度是（）。

A． O(n) B. O(nlog2n) C. O(1) D. O(n2) 17．N个结点的m阶B树至少包含（）个关键字。

A．(m-1)*n B. n C. (「m/2」-1)*(n-1)+1 D. n*「m/2」-1) 18．在散列文件中，同一个桶内的所有记录应当具有（）。

A．相同的关键字 B. 相同的散列值 C. 相同的某个属性值 D. 相同的存取频率 19．在最坏的情况下，查找成功时二叉排序树的平均查找长度（　　　） A．小于顺序表的平均查找长度 B．大于顺序表的平均查找长度 C．与顺序表的平均查找长度相同 D．无法与顺序表的平均查找长度比较 20．散列表中由于散列到同一个地址而引起的“堆积”现象，是由（　　　） A．同义词之间发生冲突引起的 B．非同义词之间发生冲突引起的 C．同义词之间或非同义词之间发生冲突引起的 D．散列表“溢出”引起的二、填空题（每空1.5分，计15分） 21．ALV树是一种平衡的二叉排序树，树中任一结点的( ) 22．在VSAM文件的控制区间中，记录的存储方式为( ) 23．单链表的存储密度（）顺序表的存储密度。

24．设SQ是循环队列，存储在数组D[M]中，则SQ入队操作对其队尾指针rear的修改是（）。

25．长度为n的串s1与长度为2n的串s2的比较运算的时间复杂度是（）。

26．广义表(((a,b,c),d,e,f))的长度是（）。

27．N（n>0）个节点的哈夫曼树恰含（）个度为1的节点。

28．深度为n的二叉树最少有（）个结点。

29．N（n>0）个顶点的连通有向图至少有（）条边。

30．对N（n>0）个记录进行冒泡排序，最少要交换（）记录。

三、简答题（每小题5分，计30分） 31．给出下面森林对应的二叉树及二叉树的后续序列。（图1） 32．一棵树有3度节点100个，2度节点200个，该树有叶子节点多少个，该树可以有多少个度为1的节点？ 33．设有广义表A, A=(((a,b),x),((a),(b)),(c,(d,(y))))，写出由A得到y的对广义表A的操作序列。

34．画出用普里姆算法构造下面所示带权无向图的最小生成树的示意图。

35．写出下列用快排序对下列序列进行两次划分的过程及结果。

37 26 51 48 77 69 82 21 17 13 21 39 55 18 36．画出对下面的5阶B树插入关键字37后的结果。

四、理解设计题（每小题5分，计15分） 37．设某带头结头的单链表的结点结构说明如下：
typedef struct nodel { int data; struct nodel*next; }node; 试设计一个算法：void copy(node*head l,　node*head 2)，将以head 1为头指针的单链表复制到一个不带有头结点且以head2为头指针的单链表中。（5分） 38. 阅读下列算法，并回答下列问题：
(1)该算法采用何种策略进行排序? (2)算法中R[n+1]的作用是什么? typedef struct { KeyType key; infoType otherinfo; } nodeType; typedef nodeType SqList［MAXLEN］; void sort(SqList R,int n) { //n小于MAXLEN-1 int k;i; for(k=n-1;k>=1;k--) if(R[k].key>R[k+1].key) { R[n+1]=R[k]; for(i=k+1;R[i].key<R[n+1].key;i++) R[i-1]=R[i]; R[i-1]=R[n+1]; }} 39．下面函数BinInsert的功能是对线性表R的前n个元素实现二分法插入排序。请在空缺处填入适当的语句，使其能够正确工作。

TYPEDEF STRUCT NODE { INT KEY; /* OTHER INFO */ } NODE; TYPEDEF NODE SEQLIST[100]; VOID BININSERT(SEQLIST R,INT N) { INT LOW,UP,MID,I,J; NODE T; FOR(I=0;I<N;I++) { _____(1)________________; LOW=0; __________(2)_____________; WHILE(LOW<UP) { MID=(LOW+UP)/2; IF(R[MID].KEY==T.KEY) {_________(3)__________; BREAK;} IF(T.KEY<R[MID].KEY)________(4)________; ELSE _______(5)_____; } FOR(J=I;J>LOW;J--) R[J]=R[J-1]; _________(6)_____________; } } 五、算法实现题（共10分） 40.假设二叉树T采用如下定义的存储结构：
typedef struct node { DataType data; struct node *lchild,*rchild,*parent; }PBinTree; 其中，结点的lchild域和rchild域已分别填有指向其左、右孩子结点的指针，而parent域中的值为空指针(拟作为指向双亲结点的指针域)。请编写一个递归算法，将该存储结构中各结点的parent域的值修改成指向其双亲结点的指针。 2006 一．单项选择题 1.D 2.B 3.C 4.B 5.D 6.C 7.B 8.D 9.D 10.D 11.A 12.B 13.B 14.A 15.C 16.A 17.C 18.B 19.C 20.B 二.填空题 21.左右子树树高之差的绝对值不大于1 23.小于 24.sq->rear=(sq->rear+1) % m 25.O(n) 26.1 27.0 28. n 29. n 30. 0 三.简答题 31. G F E D C B J I K H A 32、n0=n2+2n3+1 =200+2*100+1 =401 33、Tail(Head(Tail(Head(Tail(Tail(A)))))=(y) 34、 35、18 26 21 13 17 21 【37】82 69 77 48 39 55 51 36、四.阅读理解题 37、一边遍历，一边申请新结点，链接到head2序列中。

38、直接插入排序。

哨兵。避免边界检测，提高程序运行效率。

39、t=R[i]; up=i-1; low=mid+1; up=mid-1; low=mid+1; R[low]=t; 2002 1．某算法的空间花费s(n)=2n+n100+nlog2n+n101，则其空间复杂度为（）。

A． O(nlog2n) B. O(n100) C. O(n101) D. O(2n) 2．单链表中的存储密度一定（）。

A．小于0.5 B. 等于1 C. 大于0.1 D. 小于1 3．在顺序栈中删除一个元素，至少要移动（）元素。

A． 0 B. 1 C. n/2 D. n 4．空串是（）。

A．只包含空格符的串 B. 长度为0的串 C. 只包含一个空格符的串 D. 不含字母的串 5．采用三元组表存储稀疏矩阵，是为了（）。

A．节省存取时间 B. 节省存储空间 C. 提高对矩阵元素的访问速度 D. 提高对矩阵运算的可靠性 6．高度为h的二叉树最多有（）个节点。

A． 2h-1 B. 2h C. 2h-1 D. 2h-1+1 7．N个顶点，e条边的无权有向图的邻接矩阵中非零元素有（）个。

A． n B. n-e C. e D. e+n 8．直接选择排序在最好情况下的时间复杂度是（）。

A． O(n) B. O(nlog2n) C. O(1) D. O(n2) 9．N个结点的m阶B树至少包含（）个关键字。

A．(m-1)*n B. n C. (「m/2」-1)*(n-1)+1 D. n*「m/2」-1) 10．在散列文件中，同一个桶内的所有记录应当具有（）。

A．相同的关键字 B. 相同的散列值 C. 相同的某个属性值 D. 相同的存取频率 11．某算法的时间花费T(n)=0.05n2+100n+10，则该算法的时间复杂度为（）。

12．单链表的存储密度（）顺序表的存储密度。

13．设SQ是循环队列，存储在数组D[M]中，则SQ入队操作对其队尾指针rear的修改是（）。

14．长度为n的串s1与长度为2n的串s2的比较运算的时间复杂度是（）。

15．广义表(((a,b,c),d,e,f))的长度是（）。

16．N（n>0）个节点的哈夫曼树恰含（）个度为1的节点。

17．深度为n的二叉树最少有（）个结点。

18．N（n>0）个顶点的连通有向图至少有（）条边。

19．对N（n>0）个记录进行冒泡排序，最少要交换（）记录。

20．倒排文件的每个倒排表项包含（）和记录地址。

21．给出下面森林对应的二叉树及二叉树的后续序列。（图1） 22．一棵树有3度节点100个，2度节点200个，该树有叶子节点多少个，该树可以有多少个度为1的节点？ 23．设有广义表A, A=(((a,b),x),((a),(b)),(c,(d,(y))))，写出由A得到y的对广义表A的操作序列。

24．设有程序：
int f(int a[],int n,int key) { int i; for (i=0;i<n;i++) if(a[i]==key) return i; return -1; } 若key在a[j](j=0,1,2,…n-1)中的概率为2-(j+1)，key不在a中的概率为2-n，那么查找Key时平均比较Key的次数是多少，该算法的时间复杂度是多少？ 25．画出用普里姆算法构造下面所示带权无向图的最小生成树的示意图。

四、理解题（每题6分，计12分） 26．指出下面函数GV的功能及其返回值的含义。其中，Tab是存储稀疏矩阵A的非零元素的长度为LEN的三元组表。

#INCLUDE <STDIO.H> TYPEDEF STRUCT {INT ROW,COL,VAL;} TRITUPLENODE; INT GV(INT I,INT J,INT LEN,TRITUPLENODE TAB[]) { INT K; FOR(K=0; K<LEN; K++) IF(TAB[K].ROW==I && TAB[K].COL==J) RETURN TAB[K].VAL; RETURN 0; } 27．设P1和P2是两个单链表，他们的元素都递增有序，指出下面函数F的功能。

TYPEDEF INT DATATYPE; TYPEDEF STRUCT NODE {DATATYPE DATA; STRUCT NODE * NEXT;} LISTNODE; TYPEDEF LISTNODE * LINKLIST; LINKLIST F(LINKLIST P1, LINKLIST P2) { LINKLIST H=NULL, P; WHILE(P1&&P2) { IF(P1->DATA<P2->DATA) { P=P1; P1=P1->NEXT; } ELSE { P=P2; P2=P2->NEXT;} P->NEXT=H; H=P; } WHILE(P1) { P=P1; P1=P1->NEXT; P->NEXT=H; H=P;} WHILE(P2) { P=P2; P2=P2->NEXT; P->NEXT=H; H=P;} RETURN H; } 五、填充题（每题18分） 28．下面函数BinInsert的功能是对线性表R的前n个元素实现二分法插入排序。请在空缺处填入适当的语句，使其能够正确工作。

24、平均比较次数=1*2-(0+1)+2*2-(1+1)+……+n*2-((n-1)+1)+n*2-n =2-2-(n-1)-n*2-n 时间复杂度为：O(1) 25、见图。

四、理解题 26、在三元组表Tab中，查找稀疏矩阵中元素A[I,J]的值，并把此值作为函数的返回值。

27、把两个递增有序的单链表合并为一个递减有序的单链表。

五、填充题 t=R[i]; up=i-1 low=mid+1 up=mid-1 low=mid+1 R[low]=t 2002-10 一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。

1.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( ) A.顺序存储结构 B.链式存储结构 C.索引存储结构 D.散列存储结构 2.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为( ) A.n-i+1 B.n-i C.i D.i-1 3.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( ) A.顺序表 B.用头指针表示的单循环链表 C.用尾指针表示的单循环链表 D.单链表 4.若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为( ) A.4 B.5 C.6 D.7 5.为查找某一特定单词在文本中出现的位置，可应用的串运算是( ) A.插入 B.删除 C.串联接 D.子串定位 6.已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到( ) A.P=″SCIENCE″ B.P=″STUDY″ C.S=″SCIENCE″ D.S=″STUDY″ 7.三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A［３］[4][5]的存储地址为( ) A.356 B.358 C.360 D.362 8.如右图所示广义表是一种( ) A.线性表 B.纯表 C.结点共享表 D.递归表 9.下列陈述中正确的是( ) A.二叉树是度为2的有序树 B.二叉树中结点只有一个孩子时无左右之分 C.二叉树中必有度为2的结点 D.二叉树中最多只有两棵子树，并且有左右之分 10.n个顶点的有向完全图中含有向边的数目最多为( ) A.n-1 B.n C.n(n-1)/2 D.n(n-1) 11.已知一个有向图如右所示，则从顶点a出发进行深度优先偏历，不可能得到的DFS序列为( ) A.a d b e f c B.a d c e f b C.a d c b f e D.a d e f c b 12.在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是( ) A.快速排序 B.堆排序 C.归并排序 D.基数排序 13.不可能生成右图所示二叉排序树的关键字序列是( ) A.4 5 3 1 2 B.4 2 5 3 1 C.4 5 2 1 3 D.4 2 3 1 5 14.ALV树是一种平衡的二叉排序树，树中任一结点的( ) A.左、右子树的高度均相同 B.左、右子树高度差的绝对值不超过1 C.左子树的高度均大于右子树的高度 D.左子树的高度均小于右子树的高度 15.在VSAM文件的控制区间中，记录的存储方式为( ) A.无序顺序 B.有序顺序 C.无序链接 D.有序链接二、填空题(本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分) 16.若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为________。

17.在如图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a和b的两个结点，则可用下列两个语句实现该操作，它们依次是________和________。

18.假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为________。

19.串S=″I am a worker″的长度是________。

20.假设一个10阶的下三角矩阵A按列优顺序压缩存储在一维数组C中，则C数组的大小应为________。

21.在n个结点的线索二叉链表中，有________个线索指针。

22.若采用邻接矩阵结构存储具有n个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为________。

23.对关键字序列(52，80，63，44，48，91)进行一趟快速排序之后得到的结果为________。

24.由10000个结点构成的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度的最大值可能达到________。

25.若要找出所有工资低于1500元，职称是副教授，及所有工资低于2000元，职称是教授的记录，则查询条件是________。

三、解答题(本大题共4小题，每小题5分，共20分) 26.已知一个6行5列的稀疏矩阵中非零元的值分别为：-90，41，-76，28，-54，65和-8，它们在矩阵中的列号依次为：1，4，5，1，2，4和5。当以带行表的三元组表作存储结构时，其行表RowTab中的值依次为0，0，2，2，3和5。请写出该稀疏矩阵(注：矩阵元素的行列下标均从1开始)。

27.已知树T的先序遍历序列为ABCDEFGHIJKL，后序遍历序列为CBEFDJIKLHGA。请画出树T。

28.对关键字序列(72，87，61，23，94，16，05，58)进行堆排序，使之按关键字递减次序排列。请写出排序过程中得到的初始堆和前三趟的序列状态。

初始堆：________ 第1趟：________ 第2趟：________ 第3趟：________ 29.在关键字序列(07，12，15，18，27，32，41，92)中用二分查找法查找和给定值92相等的关键字，请写出查找过程中依次和给定值“92”比较的关键字。

四、算法阅读题(本大题共4小题，每小题5分，共20分) 30.以下函数中，h是带头结点的双向循环链表的头指针。

(1)说明程序的功能；
(2)当链表中结点数分别为1和6(不包括头结点)时，请写出程序中while循环体的执行次数。

int f(DListNode *h) { DListNode *p,*q; int j=1; p=h->next; q=h->prior; while(p!=q && p->prior!=q) if(p->data==q->data) { p=p->next; q=q->prior; } else j=0; return j; } 31.设栈S=(1,2,3,4,5,6,7),其中7为栈顶元素。请写出调用algo(&s)后栈S的状态。

void algo(Stack *S) {int i=0; Queue Q; Stack T; InitQueue(&Q);InitStack(&T); while (!StackEmpty(S)) { if((i=!i)!=0)Push(&T,Pop(&S)); else EnQueue(&Q,Pop(&S)); } while(!QueueEmpty(Q)) Push(&S,DeQueue(&Q)); while(!StackEmpty(T)) Push(&S,Pop(&T))；
} 32.已知带权图的邻接矩阵表示和邻接表表示的形式说明分别如下：
#define MaxNum 50//图的最大顶点数 #define INFINITY INT_MAX //INT_MAX为最大整数，表示∞ typedef struct{ char vexs[MaxNum];//字符类型的顶点表 int edges[MaxNum][MaxMum];//权值为整型的邻接矩阵 int n,e;//图中当前的顶点数和边数 }MGraph;//邻接矩阵结构描述 typedef struct node { int adjvex;//邻接点域 int weight;//边的权值 struct node *next;//链指针域 } EdgeNode;//边表结点结构描述 typedef struct { char vertex;//顶点域 EdgeNode * firstedge;//边表头指针 } VertexNode ;//顶点表结点结构描述 typedef struct { VertexNode adjlist[MaxNum];//邻接表 int n,e;//图中当前的顶点数和边数 } ALGraph;//邻接表结构描述下列算法是根据一个带权图的邻接矩阵存储结构G1建立该图的邻接表存储结构G2，请填入合适的内容，使其成为一个完整的算法。

void convertM(MGraph *G1,ALGraph *G2) { int i,j; EdgeNode * p; G2->n=G1->n; G2->e=G1->e; for(i=0;i<G1->n;i++) { G2->adjlist[i].vertex=G1->vexs[i]; G2->adjlist[i].firstedge= (1) ; } for (i=0;i<G1->n;i++) for (j=0;j<G1->n;j++) if(G1->edges[i][j]<INFINITY) { p=(EdgeNode *) malloc(sizeof(EdgeNode)); p->weight= (2) ; p->adjvex=j; p->next=G2->adjlist[i].firstedge; (3) ; }} 33.阅读下列算法，并回答下列问题：
(1)该算法采用何种策略进行排序? (2)算法中R[n+1]的作用是什么? Typedef struct { KeyType key; infoType otherinfo; } nodeType; typedef nodeType SqList［MAXLEN］; void sort(SqList R,int n) { //n小于MAXLEN-1 int k;i; for(k=n-1;k>=1;k--) if(R[k].key>R[k+1].key) { R[n+1]=R[k]; for(i=k+1;R[i].key<R[n+1].key;i++) R[i-1]=R[i]; R[i-1]=R[n+1]; } } 五、算法设计题(本题共10分) 34.假设二叉树T采用如下定义的存储结构：
typedef struct node { DataType data; struct node *lchild,*rchild,*parent; }PBinTree; 其中，结点的lchild域和rchild域已分别填有指向其左、右孩子结点的指针，而parent域中的值为空指针(拟作为指向双亲结点的指针域)。请编写一个递归算法，将该存储结构中各结点的parent域的值修改成指向其双亲结点的指针。 -90 41 -76 28 54 65 -8 一．单项选择题 1.D 2.A 3.A 4.B 5.D 6.A 7.A 8.C 9.D 10.D 11.A 12.B 13.A 14.B 15.D 二.填空题 16. O(nlogn) 17.b->next=p->next; p->next=s; 18.bceda 19.14 20.46　 21.n+1 22.O（n²）　 23. 48,44,82,63,80,91 24. (10000+1)/2 25. 职称=“副教授”and工资<1500 or职称=“教授”and and工资<2000 三.简答题 26. 27.由于树的后序序列就是等价二叉树的中序遍历序列，因此先得到等价二叉树，然后转化为相应的树。

28. 　初始堆：05,23,16,58,94,72,61,87第一趟：16,23,61,58,94,72,87,05 第二趟：23,58,61,87,94,72,16,05 第三趟：58,72,61,87,94,23,16,05 29．18 32 41 92 四.算法阅读题 30.(1). 检查循环链表中头结点两端对应位置处的结点值是否对称相等。

(2). 当结点个数为1时，循环次数为0次。

当结点个数为0时，循环次数为3次。

31. 7 5 3 1 2 4 6 （7为栈顶） 32.(1)NULL (2)G1->edges[i][j] (3)G2->adjlist[i].firstedge=p 33.(1)从右侧进行的直接插入排序 (2)R[n+1]的作用为哨兵五.算法设计题 34.BintreeNode *pre; pre=NULL; void xiugai(BinTree *T) { if(T) { xiugai ((*T) ->lchild); (*T)->parent=pre; pre=(*T); xiugai ((*T) ->rchild); }} 2003.10 1．下列说法正确的是（　　　） A．数据是数据元素的基本单位 B．数据元素是数据项中不可分割的最小标识单位 C．数据可由若干个数据元素构成 D．数据项可由若干个数据元素构成 2．数据结构的基本任务是（　　　） A．逻辑结构和存储结构的设计 B．数据结构的运算实现 C．数据结构的评价与选择 D．数据结构的设计与实现 3．在一个具有n个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的时间复杂性量级为（　　　） A．O（1） B．O（n） C．O（nlog2n） D．O(n2) 4．顺序存储的线性表（a1,a2,…,an）,在任一结点前插入一个新结点时所需移动结点的平均次数为（　　　） A．n B．n/2 C．n+1 D．(n+1)/2 5．下列树U′，经剪枝运算DELETE（U′，x，2）后为（　　　） 6．一棵有16结点的完全二叉树，对它按层编号，则对编号为7的结点X，它的双亲结点及右孩子结点的编号分别为（　　　） A．2，14 B．2，15 C．3，14 D．3，15 7．设有一5阶上三角矩阵A［1..5，1..5］，现将其上三角中的元素按列优先顺序存放在一堆数组B［1..15］中。已知B［1］的地址为100，每个元素占用2个存储单元，则A［3，4］的地址为（　　　） A．116 B．118 C．120 D．122 8．一个带权的无向连通图的最小生成树（　　　） A．有一棵或多棵 B．只有一棵 C．一定有多棵 D．可能不存在 9．下列有关图遍历的说法中不正确的是（　　　） A．连通图的深度优先搜索是一个递归过程 B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C．非连通图不能用深度优先搜索法 D．图的遍历要求每一顶点仅被访问一次 10．在最坏的情况下，查找成功时二叉排序树的平均查找长度（　　　） A．小于顺序表的平均查找长度 B．大于顺序表的平均查找长度 C．与顺序表的平均查找长度相同 D．无法与顺序表的平均查找长度比较 11．闭散列表中由于散列到同一个地址而引起的“堆积”现象，是由（　　　） A．同义词之间发生冲突引起的 B．非同义词之间发生冲突引起的 C．同义词之间或非同义词之间发生冲突引起的 D．散列表“溢出”引起的 12．从外存设备的观点看，存取操作的基本单位是（　　　） A．逻辑记录 B．数据元素 C．文件 D．物理记录 13．对文件进行检索操作时，每次都要从第一个记录开始的文件是（　　　） A．顺序文件 B．索引文件 C．顺序索引文件 D．散列文件 14．一组记录的键值为（46，74，18，53，14，20，40，38，86，65），利用堆排序的方法建立的初始堆为（　　　） A．（14，18，38，46，65，40，20，53，86，74） B．（14，38，18，46，65，20，40， 53，86，74） C．（14，18，20，38，40，46，53，65，74，86） D．（14，86，20，38，40，46，53，65，74，18） 15．对序列（22，86，19，49，12，30，65，35，18）进行一趟排序后得到的结果如下：（18，12，19，22，49，30，65，35，86），则可以认为使用的排序方法是（　　　） A．选择排序 B．冒泡排序 C．快速排序 D．插入排序二、填空题（本大题共13小题，每空2分，共26分）请在每小题的空格中填上正确答案。错填、不填均无分。

16．表示逻辑关系的存储结构可以有四种方式，即顺序存储方式、链式存储方式、_______________和散列存储方式。

prior data ， next 17．设某非空双链表，其结点形式为　若要删除指针q所指向的结点，则需执行下述语句段：q->prior->next＝q->next; _______________。

18．如图所示，设输入元素的顺序是A，B，C，D，通过栈的变换，在输出端可得到各种排列。若输出序列的第一个元素为D，则输出序列为_______________。

19．队列中允许进行删除的一端为________________。

20．设一棵二叉树中度为2的结点数为10，则该树的叶子数为________________。

21．如图所示的二叉树，若按后根遍历，则其输出序列为________________。

22．一个具有n个顶点的有向完全图的弧数为________________。

23．查找表的数据结构有别于线性表、树型结构等，其逻辑结构为________________。

24．长度为L的顺序表，采用设置岗哨方式顺序查找，若查找不成功，其查找长度为________________。

25．在开散列表上查找某元素时，通常分两步进行，首先必须计算该键值的散列地址，然后在地址指针所指________________中查找该结点。

26．文件的检索有顺序存取、________________和按关键字存取三种方式。

27．在待排序的n个记录中任取一个记录，以该记录的键值作为标准，将所有记录分为两组，使得第一组中各记录的键值均小于或等于该键值，第二组中的各记录的键值均大于该键值；
然后将该记录排在两组中间。再对所分成的两组分别使用上述方法，直到所有记录都排在适当位置为止。这种排序方法称为________________。

28．在对一组记录关键字（54，38，96，23，15，72，60，45，83）进行冒泡排序时，整个冒泡排序过程中需进行________________趟才能完成。

三、应用题（本大题共5小题，共30分） 29．设有一顺序队列sq，容量为5，初始状态时sq.front=sq.rear=0，画出做完下列操作后队列及其头尾指针的状态变化情况，若不能入队，请简述其理由后停止。（6分）（1） d,e,b入队（2） d,e出队（3） i,j入队（4） b出队（5） n,o,p入队 30．已知无向图G的邻接矩阵如下，假设对其每行元素访问时必须从右到左，请写出从V0开始的深度优先搜索的序列。（4分） 31．画出下列二叉树的二叉链表表示图。（6分）　　　　　　　　　　　　　　 32．用二分查找法对一个长度为10的有序表进行查找，填写查找每一元素需要的比较次数。（8分）元素下标 1 2 3 4 5 6 7 8 9 10 比较次数 33．已知序列（10，18，4，3，6，12，1，9，15，8），请给出采用二路归并排序法对该序列进行升序排序时的每一趟结果。（6分）四、设计题（本大题共2小题，共14分） 34．设某带头结头的单链表的结点结构说明如下：
typedef struct nodel { int data; struct nodel*next; }node; 试设计一个算法：void copy(node*head l,　node*head 2)，将以head 1为头指针的单链表复制到一个不带有头结点且以head2为头指针的单链表中。（6分） 35．修改冒泡排序法以实现双向冒泡排序。双向冒泡排序指第一次把最大记录放到表尾，第二次把最小记录放到表头，如此反复进行。试编写修改后的算法：void dbubble(int a[],int n)。（8分）一、单项选择题 1.C 2.B 3.B 4.D 5.C6.D 7.A 8.A 9.C 10.C 11.B 12.D 13.A 14.B 15.C 二、填空题 16．索引存储方式 17. q->next->prior=q->prior; 18. D C B A 19. 队首 20. 11 21. D B F H G E C A 22. N（N-1） 24. L+1 25、链表中 26. 随机存取 27、快排序 28、7 三、应用题：
29、图形略，提示对于使用顺序表的队列，一般使用循环结构，否则随着出队入队次数的增多，一定会出现队尾益出顺序表的情况。

30、V0 V2 V4 V3 V1 32、比较次数顺序为：
3、2、3、4、1、3、4、2、3、4 33、第一趟：（10 8）（3 4）（6 12）（1 9）（8 15）第二趟：（3 4 8 10）（1 6 9 12）（8 15）在本趟末尾并入剩余的一组，结果为：
（3 4 8 10）（1 6 8 9 12 15）第三趟：（1 3 4 6 8 9 10 12 15 四、设计题：
34、void copy(node * head1, *head2) { node *p, *q, *r; p=head1->next; if(p==NULL) { printf(“Error”); return;} while(p) { q=(node *)malloc(sizeof(node)); q->data=p->data; q->next=NULL; if(head2==NULL) { head2=q; r2=q;} else { r2->next=q; r2=q;}} } 2004.10 1．在数据结构中，数据的逻辑结构可以分成（　　　） A．内部结构和外部结构 B．线性结构和非线性结构 C．紧凑结构和非紧揍结构 D．动态结构和静态结构 2．在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（　　　） A．数据元素的相邻地址表示 B．数据元素在表中的序号表示 C．指向后继元素的指针表示 D．数据元素的值表示 3．设p指向单链表中的一个结点，s指向待插入的结点，则下述程序段的功能是（　　　）　　　　　s -> next = p -> next; p -> next = s; t = p -> data; p -> data = s -> data; s ->data = t; A．结点*p与结点*s的数据域互换 B．在p所指结点的元素之前插入元素 C．在p所指结点的元素之后插入元素 D．在结点*p之前插入结点*s 4．栈和队列都是（　　　） A．限制存取位置的线性结构 B．顺序存储的线性结构 C．链式存储的线性结构 D．限制存取位置的非线性结构 5．若数组s[0..n-1]为两个栈s1和s2的共用存储空间，且仅当s[0..n-1]全满时，各栈才不能进行进栈操作，则为这两个栈分配空间的最佳方案是：s1和s2的栈顶指针的初值分别为（　　　） A．1和n+1 B．1和n/2 C．－1和n D．－1和n+1 6．执行下列程序段后，串X的值为（　　　） S=〞abcdefgh〞; T=〞xyzw〞; substr (X,S,2,strlen(T)); substr (Y,S, stelen(T),2); strcat (X,Y); A．〞cdefgh〞 B．〞cdxyzw〞 C．〞cdefxy〞 D．〞cdefef〞 7．多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为（　　　） A．数组的元素处在行和列两个关系中 B．数组的元素必须从左到右顺序排列 C．数组的元素之间存在次序关系 D．数组是多维结构，内存是一维结构 8．从广义表LS＝（(p, q), r, s）中分解出原子q的运算是（　　　） A．tail (head (LS)) B．head (tail (head (LS))) C．head (tail (LS)) D．tail (tail (head (LS))) 9．在具有n个叶子结点的严格二叉树中，结点总数为（　　　） A．2n+1 B．2n C．2n-1 D．2n-2 10．若<vi, vj>是有向图的一条边，则称（　　　） A．vi邻接于vj B．vj邻接于vi C．vi和vj相互邻接 D．vi与vj不相邻接 11．在一个带权连通图G中，权值最小的边一定包含在G的（　　　） A．最小生成树中 B．深度优先生成树中 C．广度优先生成树中 D．深度优先生成森林中 12．当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为（　　　） A．左子树的叶子结点 B．左子树的分支结点 C．右子树的叶子结点 D．右子树的分支结点 13．希尔排序的增量序列必须是（　　　） A．递增的 B．随机的 C．递减的 D．非递减的 14．如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为（　　　） A．插入排序 B．归并排序 C．冒泡排序 D．堆排序 15．设置溢出区的文件是（　　　） A．索引非顺序文件 B．ISAM文件 C．VSAM文件 D．顺序文件二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案。错填、不填均无分。

16．下列程序段的时间复杂度为________________。

　　product = 1; 　　for (i = n;i>0; i--) 　　　for (j = i+1; j<n; j++) 　　　　product *=j; 17．已知指针p指向单链表中某个结点，则语句p -> next =p -> next -> next的作用是________________。

18．假设元素只能按a,b,c,d的顺序依次进栈，且得到的出栈序列中的第一个元素为c，则可能得到的出栈序列为________________，不可能得到的出栈序列为________________。

19．若链串结点中的指针占4个字节，每个字符占1个字节，则结点大小为2的链串的存储密度为________________。

20．右图表示的广义表为________________。

21．若一棵满三叉树中含有121个结点，则该树的深度为________________。

22．若以邻接矩阵表示有向图，则邻接矩阵上　第i行中非零元素的个数即为顶点vi的________________。

23．若希望只进行8趟排序便能在4800个元素中找出其中值最小的8个元素，并且要求排序过程中所进行的关键字比较次数尽可能少，则应该选用________________排序方法。

24．在含20个关键字的3阶B树（2－3树）上查找一个关键字，至多需要访问___________次外存。

25．文件上的两类主要操作为________________和________________。

三、解答题（本大题共4小题，每小题5分，共20分） 26．设栈S1的入栈序列为1 2 3 4（每个数字为13个元素），则不可能得到出栈序列3142。但可通过增设栈S2来实现。例如，按下图中的箭头指示，依次经过栈S1和S2，便可得到序列3 1 4 2。

如果用H1和H2分别表示栈S1和S2的进栈操作，用P1和P2分别表示两个栈的出栈操作，则得到3 1 4 2的一个操作步骤为　　H1，H1，H1，P1，H2，P2，P1，H2，P1，H2，P2，H1，P1，H2，P2，P2 　　　请仿照上例写出利用两个栈从1 2 3 4得到4 1 3 2的操作步骤。

27．已知树如右图所示，　（1）写出该树的后序序列；

（2）画出由该树转换得到的二叉树。

28．为关键字（17，33，31，40，48）构造一个长度为7的散列表，设散列函数为h(key)=key%7,用开放定址法解决冲突的探查序列是　hi = (h(key) + i(key%5+1))%7 0≤i≤6 （1）画出构造所得的散列表；

（2）求出在等概率情况下查找成功时的平均查找长度。

29．已知R［1..8］中的元素依次为（12，5，9，20，6，31，24，27），写出按算法MergeSortDC　对R进行自顶向下的二路归并排序过程中，前5次调用函数Merge(R, low, mid, high)时参数 low, mid 和high的值。

void MergeSortDC (int R[], int low, int mid, int high ) { int mid; if (low<high) { mid = (low +high)/2; MergeSortDC (R, low, mid); MergeSortDC (R, mid+1, high); Merge (R, low, mid, high); } } // MergeSortDC 　（1）第一次调用时的参数值；

　（2）第二次调用时的参数值；

（3）第三次调用时的参数值；

（4）第四次调用时的参数值；

（5）第五次调用时的参数值；

四、算法阅读题（本大题共4小题，每小题5分，共20分） 30．下列函数的功能是，对以带头结点的单链表作为存储结构的两个递增有序表（表中不存在值相同的数据元素）进行如下操作：将所有在Lb表中存在而La表中不存在的结点插入到La中，其中La和Lb分别为两个链表的头指针。请在空缺处填入合适内容，使其成为一个完整的算法。

　 void union (LinkList La, LinkList Lb) { //本算法的功能是将所有Lb表中存在而La表中不存在的结点插入到La表中 LinkList pre = La, q; LinkList pa = La -> next; LinkList pb = Lb -> next; free (Lb); while (pa && pd) { if (pa -> data <pb -> data) { pre = pa; pa = pa -> next;} else if (pa -> data > pb ->data) { (1) ; pre = pb; pb = pb -> next; (2) ; } else { q = pb; pb = pb -> next; free (q); } } if (pb) (3) ; } 31．已知串的存储结构为动态存储分配的顺序串。阅读下列算法，并回答问题：
（1）写出执行函数调用 strc (s, r)的返回结果，其中s=〃aba〃, r=〃abababa〃; （2）简述函数strc的功能。

int strc (HString * sub, HString * str) { int i=0, j, k, count =0; while (i < str -> length – sub -> length +1) { j=i; k=0; while (k <sub -> length && str -> ch[j] = =sub -> ch[k] ) { j++; k++; } if (k = = sub -> length) {count ++; i=j-sub -> length +1;} else i++; } return count; } 32．下列函数MDFSForest的功能是，对一个采用邻接矩阵作存储结构的图进行深度优先搜索遍历，输出所得深度优先生成森林中各条边。请在空缺处填入合适内容，使其成为一个完整的算法。

　#define MaxMun 20 //图的最大顶点数　typedef struct { char vexs [MaxNum]; //字符类型的顶点表 int edges [MaxNum][MaxNum]; //邻接矩阵 int n, e; //图的顶点数和边数　}MGraph; //图的邻接矩阵结构描述　typedef enum {FALSE, TRUE} Boolean; 　Boolean visited [MaxNum]; void MDFSTree (MGraph *G, int i); void MDFSForest (MGraph *G) { int i, k; for (i=0; i <G -> n; i++) visited [i] = (1) ; for (k = 0; k<G -> n; k++) 　if (!visited [k]) MDFSTree (G,k); 　} 　void MDFSTree (MGraph *G, int i) { int j; visited [i]=TRUE; for (j=0; j<G -> n; j++) { if ( (2) ) { printf (〃<%c, %c>〃G -> vexs [i], G -> vexs [j]); (3) ; } } 　｝　 33．已知整形数组L［1..8］中的元素依次为（9，8，5，7，6，3，2，1），阅读下列函数，并写出执行函数调用　sort(L, 8)时，对L进行的头两趟（pass分别为0和1）处理结果。

　Void sort (int R[],int n) { 　 int pass = 0, k, exchange, x; 　 do { 　 k=pass%2+1; 　 exchange = 0; 　 while (k<n) 　 { 　　if (R[k]>R[k+1]) 　　{ 　 x = R[k]; R[k] = R[k+1]; R[k+1] = x; 　 exchange =1; } K+=2 } 　pass ++; }while (exchange = = 1|| pass <=1); } 第一趟（pass = 0）: 第二趟（pass = 1）: 五、算法设计题（本大题共10分） 34．已知二叉排序树中结点的关键字为整数，设计递归算法按递增有序性输出树中所有大于或等于给定值x的结点，并以函数的参数返回输出的结点个数。假设以二叉链表为存储结构，其结点结构为：
　　 lchild key rchild 一、单项选择题 1.B 2.C 3.B 4.A 5.C6.D 7.D 8.B 9.C 10.B11.A 12.B 13.C 14.A 15.B 二、填空题 16．O(n2) 17. 删除p所指示的结点后面的结点 18. 可能：c b a d或c d b a、c b d a不可能：c a b d、c d a b、c a d b 19. 33.3% 20. 递归表21. 5 22. 出度23. 堆排序 24、425、检索和更新三、解答题：
26. H1 H1 H1 H1 P1 H2 P2 P1 H2 P1 H2 P1 H2 P2 P2 H1 P2 P1 H2 P2 27、EBJKFGHICDA, 见下图。

28、（1+1+3+2+4）/5=2.1 31 17 48 33 40 注：找17需1次比较，找33需1次比较，找31需3次比较，找40需2次比较，找48需4次比较。

29、(1) R,1,4,8 (2) R,1,2,4 (3) R,5,6,8 (4) R,1,1,2 (5) R,3,3,4 四、算法阅读题：
30、pre->next=pb; pre->next=pa; pre->next=pb; 30、函数的返回结果为：3 返回sub子串在字符串str中出现的次数；

32、 false; G->edges[i][j]!=0 && !visited[j] MDFSTree(G,j); 33、这是一个奇偶排序的算法。

第一趟：8 9 5 7 3 6 1 2第二趟：8 5 9 3 7 1 6 2 五、算法题目：
假设BinNode是如图所示的结点类型，BinTree是指向树根的指针类型；

int tongji(Bintree T, DataType x) { int count1,count2,count; if (T) { count1=tongji(T->lchild,x); if(T->data>=x) { printf(T->data); count=1;} count2=tongji(T->rchild,x); } return count+count1+count2; else return 0; } 也可以写成下面的形式：首先定义全局变量count，并赋初值0。

int count=0; void tongji(Bintree T, DataType x) { if (T) { tongji(T->lchild,x); if(T->data>=x) { printf(T->data); count++;} tongji(T->rchild,x); } } 2004.1B 1．下列数据组织形式中，（　　　）的各个结点可以任意邻接。

A．集合 B．树形结构 C．线性结构 D．图状结构 2．设某二维数组A［1..n，1..n］，则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为（　　　） A．O（log2n） B．O(n) C．O(nlog2n) D．O(n2) 3．在线性表的下列存储结构中，读取元素花费时间最少的是（　　　） A．单链表 B．双链表 C．循环链表 D．顺序表 4．将一个头指针为p的单链表中的元素按与原单链表相反的次序存放，则下列算法段中的空白处应为 q=NULL; while (p!=NULL) { （　　　） } p=q; A．r=q; q=p; p=p -> next; q -> next=r; B．q=p; r=q; p=p -> next; q -> next=r; C．r=q; p=p -> next; q=p; q -> next=r; D．q=p; p=p -> next; r=q; q -> next=r; 5．数组通常具有两种基本运算，即（　　　） A．创建和删除 B．索引和修改 C．读和写 D．排序和查找 6．除根结点外，树上每个结点（　　　） A．可有任意多个孩子、任意多个双亲 B．可有任意多个孩子、一个双亲 C．可有一个孩子、任意多个双亲 D．只有一个孩子、一个双亲 7．具有100个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、右孩子，其余（　　　）个指针域为空。

A．50 B．99 C．100 D．101 8．邻接表是图的一种（　　　） A．顺序存储结构 B．链式存储结构 C．索引存储结构 D．散列存储结构 9．如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是（　　　） A．G肯定不是完全图 B．G一定不是连通图 C．G中一定有回路 D．G有2个连通分量 10．若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过（　　　） A．n/2 B．n C．(n+1)/2 D．n+1 11．若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至（　　　） A．该中间位置 B．该中间位置－1 C．该中间位置＋1 D．该中间位置／2 12．散列文件不能（　　　） A．随机存取 B．索引存取 C．按关键字存取 D．直接存取 13．若检索顺序文件各个记录的概率相同，设文件占用的页块数为n，则按关键字存取时的平均访问外存次数为（　　　） A．n/2 B．n C．n/4 D．log n 14．下列关键码序列中，属于堆的是（　　　） A．（15，30，22，93，52，71） B．（15，71，30，22，93，52） C．（15，52，22，93，30，71） D．（93，30，52，22，15，71） 15．已知10个数据元素为（54，28，16，34，73，62，95，60，26，43），对该数列按从小到大排序，经过一趟冒泡排序后的序列为（　　　） A．16，28，34，54，73，62，60，26，43，95 B．28，16，34，54，62，73，60，26，43，95 C．28，16，34，54，62，60，73，26，43，95 D．16，28，34，54，62，60，73，26，43，95 二、填空题（本大题共13小题，每小题2分，共26分）请在每小题的空格中填上正确答案。错填、不填均无分。

16．下列程序段的时间复杂性量级是_____________。

for (i=1;i<n; i++) for (j=1; j<i; j++) t=t+1; 17．在顺序存储的线性表（a1,a2…，an）中的第i (1≤i≤n)个元素之前插入一个元素，则需向后移动_____________个元素。

18．在栈的顺序实现中，若栈不满，则进栈操作可以用下列算法片断实现：
_____________；

sq -> data[sq -> top]=x；

19．链队列实际上是一个同时带有头指针和尾指针的单链表，尾指针指向该单链表的_____________。

20．设有k个结点，在用哈夫曼算法构造哈夫曼树的过程中，若第i次合并时已找到权最小的结点x和权次小的结点y，用T［x］.wt表示结点x的权值，已知T［x］.wt=m,　T［y］.wt=n，则合并成新的二叉树后给新根结点的权值赋值的语句为_____________。

21．在下列树中，结点H的祖先为_____________。

22．顶点数为n、边数为n(n-1)/2的无向图称为_____________。

23．动态查找表在开散列表上通常采用_____________来解决冲突问题。

24．对于有10个元素的有序表采用二分查找，需要比较3次方可找到其对应的键值，则该元素在有序表中的位置可能是______________。

25．查找表的逻辑结构与线性结构、树型结构等相比，根本区别在于______________。

26．文件的基本运算包括______________和修改两类。

27．在排序方法中，依次将每个记录插入到一个有序的子序列中去，即在第i(i≥1)遍整理时，r1,r2,…,ri-1已经是排好顺序的子序列，取出第i个元素ri，在已排好序的子序列里为ri找到一个合适的位置，并把它插到该位置上。这种排序方法被称为___________。

28．快速排序法在待排序数据_____________的情况下最不利于发挥其长处。

三、应用题（本大题共5小题，共30分） 29．如图所示，输入元素为A，B，C，在栈的输出端得到一个输出序列ABC，求出在栈的输入端所有可能的输入序列。（5分） 30．分别写出下列二叉树的先根、中根、后根遍历序列。（6分）　　　　 31．已知无向图G的邻接表如下，请写出其从顶点V2开始的深度优先搜索的序列。（4分） 32．设闭散列表容量为7（散列地址空间0..6），给定表（30，36，47，52，34），散列函数H（k）=k mod 6，采用线性探测法解决冲突，要求：（7分）（1）构造散列表；

（2）求查找数34需要的比较次数。

33．已知序列（503，87，512，61，908，170，897，275，653，462）请给出采用快速排序法作升序排序时的每一趟的结果。（8分）四、设计题（本大题共2小题，共14分） 34．设某头指针为head的单链表的结点结构说明如下：（6分） typedef struct node1 { int data; struct node1*next }node; 试设计一个算法void change (node*head),将该单链表中的元素按原单链表相反的次序重新存放，即第一个结点变成最后一个结点，第二个结点变为倒数第二个结点，如此等等。

35．编写一个算法　void DisplayQueue ()，产生50个300～600之间的随机整数（调用一次MyRand()可产生一个符合条件的随机整数）。每产生一个数据，若是奇数，则入队列，若是偶数，则从队首取出一个数据。要求：（8分）　（1）队列用链表实现；

　（2）每产生一个数显示一次相应操作后的队列当前状态；

　（3）无需定义函数int MyRand()；

　（4）显示队列可调用函数　void DisOne (QueptrTp lq)，也无需定义；

　（5）设链队列定义为：
　typedef struct linked_queue {int data; struct linked_queue*next; }LqueueTp; typedef struct queueptr { LqueueTp *front, *rear; }QueptrTp; QueptrTp lq; 一、单项选择题 1.D 2.D 3.D 4.A 5.C6.B 7.D 8.B 9.B 10.B11.B 12.A 13.A 14.A 15.B 二、填空题 16．O(n2) 17. n-i+1 18. sq->top++; 19. 最后一个结点 20. T[k+i].wt=m+n; 21. F B A 22. 完全无向图 23. 拉链法 24、1 3 6 9 25、强调对关键字的查找和更新 26、检索 27、直接插入排序 28、有序三、解答题：
29、A in A out B in B out C in C out C in B in A in A out B out C out A in A out C in B in B out C out B in A in A out B out C in C out C in A in A out B in B out C out 30、先序：A B C E D F G H 中序：C E B D G F H A 后序：E C G H F D B A 31、V2 V5 V3 V1 V4 32、 30 36 47 52 34 比较2次。

四、设计题：
34、（略）提示：扫描原表，把原表结点用头插法插入新表即可。

2004.10 1．下列各个式子中，按增长率从小到大的顺序正确排列的是（）。

A. n1/2, n!, 2n, n3/2 B. n3/2, 2n, nlogn, 2100 C. 2n, log(n), nlog(n), n3/2 D. 2100, log(n), 2n, nn 2．若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是（）。

A. s->next=p->next; p->next=s; B. p->next=s; s->next=p->next; C. p->next=s->next; s->next=p; D. s->next=p; p->next=s->next; 3．若要在O(1)的时间复杂度上实现两个循环链表头尾相接，则应对这两个循环链表各设置一个指针，分别指向（）。

A. 各自的头结点 B. 各自的尾结点 C. 各自的第一个元素结点 D. 一个表的头结点，另一个表的尾结点 4．栈的两种存储结构分别为（）。

A. 顺序存储结构和链式存储结构 B. 顺序存储结构和散列存储结构 C. 链式存储结构和索引存储结构 D. 链式存储结构和散列存储结构 5．已知循环队列的存储控件为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为（）。

A. 5 B. 6 C. 16 D. 17 6．已知在如下定义的链串结点中，每个字符占用一个字节，指针占用4个字节，则该结点的存储密度为()。

typedef struct node { char data[8]; struct node * next;} LinkStrNode; A. 1/4 B. 1/2 C. 2/3 D. 3/4 7．应用简单的匹配算法对主串s=“ BDBABDABDAB“与子串t=“ BDA“进行模式匹配，在匹配成功时，进行的字符比较总次数为（）。

A. 7 B. 9 C. 10 D. 12 8．二维数组A[20][10]采用列优先的存储方法，若每个元素占据两个存储单元，且第一个元素的首地址为200，则元素A[8][9]的存储地址为（）。

A. 574 B. 576 C. 578 D. 580 9．对广义表L=((a,b),c,d)进行操作tail(head(L))的结果是（）。

A. （c,d） B. (d) C. b D. (b) 10．已知一颗树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为（）。

A. ABCDEF B. ABCEFD C. ABFCDE D. ABCDFE 11．一个含有n个顶点和e条弧的有向图以邻接矩阵为存储结构，则计算该有向图中某个顶点出度的时间复杂度为（）。

A. O(n) B. O(e) C. O(n+e) D. O(n2) 12．在关键字序列（12,23,34,45,56,67,78,89,91）中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为（）。

A. 4，4，3 B. 4，3，3 C. 3，4，4 D. 3，3，4 13．下列排序算法中，最好与最坏时间复杂度相同的排序方法是（）。

A. 冒泡排序 B. 直接选择排序 C. 堆排序 D. 归并排序 14．已知含有10个结点的二叉排序树是一颗完全二叉树，则该二叉树在等概率情况下查找成功的平均查找长度为（）。

A. 1.0 B. 2.9 C. 3.4 D. 5.5 15．在列各种文件中，不能进行顺序查找的文件是（）。

A. 顺序文件 B. 索引文件 C. 散列文件 D. 多重表文件第二部分非选择题二、填空题（每题2分，计20分） 16．抽象数据类型是指数据逻辑结构及与之相关的（）。

17．已知在结点个数大于1的单循环链表中，指针p指向表中某个结点，则下列程序段执行结束时，指针q指向结点*p的（）结点。

q=p; while (q->next!=p) q=q->next；

18．假设S和X分别表示进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX，则由a*b+c/d得到ab*cd/+的操作序列为（）。

19．在文本编辑程序中查找一个特定单词在文本中出现的位置，可以利用串的（）运算。

20．假设以行优先顺序将一个n阶的5对角矩阵矩阵压缩存储到一维数组Q中，则数组Q的大小至少为（）。

21．在含有100个结点的完全二叉树中，叶子结点的个数为（）。

22．在无向图中，若从顶点a到顶点b存在（），则称a与b之间是连通的。

23．如果排序过程不改变（）之间的相对次序，则称该排序方法是稳定的。

24．索引顺序查找适宜对（）的顺序表进行查找。

25．文件的检索操作可按检索条件不同分为下列四种询问，它们是简单询问，范围询问，函数询问和（）询问。

三、解答题（每题5分，计20分） 26．画出下图所示的二叉树的中序线索链表的存储表示。

27．已知图G=(V,E)，其中：
V={a,b,c,d,e} E={(a,b),(b,d),(c,b),(c,d),(d,e),(e,a),(e,c)} 画出图G;然后画出图G的邻接表。

28．已知自顶向下的二路归并排序的算法如下所示，按此算法对关键字序列(55,28,73,91,37,64,19,82,46)进行排序，列出算法执行过程中前5次调用Merge函数进行归并之后的关键字序列。

void MergeSortDC(Seqlist R, int low, int high) { int mid; if(low<high) {mid=(low+high)/2; MergeSortDC(R,low,mid); MergeSortDC(R,mid+1,high); Merge(R,low,mid,high); } } 29．由于元素的插入先后次序不同，所构成的二叉排序树可能有多种形态，请画出4棵含1，2，3，4，5，6六个元素而且以1为跟，深度为4的二叉排序树。

四、算法阅读题（每题5分，计20分） 30．L为一个带头结点的循环链表。函数f30的功能是删除L中数据域data的值大于c的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。请在空白处填写适当的内容。

LinkList f30(LinkList L,int c) { LinkList Lc,p,pre; pre=L; p=(①); Lc=(LinkList)Malloc(sizeof(ListNode)); Lc->next=Lc; while(P!=L) if(p->data>c) { pre->next=p->next; ( ②); Lc->next=p; p=pre->next; } else { pre=p; ( ③ ); } return Lc; } 31．设栈S=(1,2,3,4,5,6,7)，其中7为栈顶元素。

写出调用f31(&S)后的S; 简述函数f31中第一个循环语句的功能。

void f31(Stack *S) { Queue Q; Stack T; int i=0; InitQueue(&Q); InitStack(&T); while(! StackEmpty(S)) if((i=!i)!=0) Push(&T, Pop(S)); else EnQueue(&Q, Pop(S)); while(! StackEmpty(&T)) Push(S, Pop(&T)); while(! QueueEmpty(&T)) Push(S, DeQueue(&Q)); 32．图的邻接矩阵表示描述如下：
#define MaxNum 20 typedef struct {char vexs[MaxNum]; int edges[MaxNum][MaxNum]; int n,e; } Mgraph; 阅读下列算法，并回答问题：
(1)对于下列图G的邻接矩阵，写出函数调用f32(&G,3)的返回值；

(2)简述函数f32的功能；

(3)写出函数f32的时间复杂度。

int f32(Mgraph *G, int i) { int d=0, j; for (j=0; j<G->n; j++) { if(G->edges[i][j]) d++; if (G->edges[j][i]) d++; } return d; } 33．阅读下列算法并回答问题：
(1)设数组L[1..8]的初值为（4,-3,7,-1,-2,2,5,-8），写出执行函数调用f33(L,8)之后的L[1..8]中的元素之值。

(3)简述函数f33的功能。

void f33(int R[],int n) { int x=R[1]; int low=1; high=n; while(low<high) { while (low<high && R[high]>=0) high--; if(low<high) { R[low++]=R[high]; while (low<high && R[low]<0) low++; R[high--]=R[low]; } } R[low]=x; } 五、算法设计题（每题5分，计20分） 34．假设以二叉链表作为二叉树的存储结构，其结点结构为：
lchild data Rchild 依照如下给定的函数f34的原型，编写求二叉树T中叶子结点所在的最小层次与最大层次的函数。其中参数level为函数执行过程中T当前所指结点的层次，其初值为1；
*lmin与*lmax分别为叶子结点的最小层次和最大层次，它们的初值均为0。

void f34(BinTree T, int level, int *lmin, int *lmax) 一、单项选择题 1.D 2.A 3.B 4.A 5.D 6.C 7.C 8.B 9.D 10.D 11.A 12.B 13.D 14.B 15.C 二、填空题 16．操作 17. 直接前驱节点 18. SXSSXXSSXSSXXX 19. 匹配 20. 5×n-6 21.50 (只有一个度为1的结点，且n0=n2+1) 22. 路径 23. 相同关键字记录 24. 分块有序 24、布尔询问 27． 28．28 37 55 73 91 19 64 82 46 29．四、算法阅读题：
30、L->next; p->next=Lc; p=p->next; 31、（从栈顶到栈底依次为：2 4 6 7 5 3 1） 32、(1) 3 (2)、求出顶点I的出度和入度之和；
（或求与顶点I相邻接边的数目和邻接于顶点I的边的数目之和）。

(3)、O(n) 33、－8 －3 －2 －1 4 2 5 7 五、算法设计题：
34、本题可采用递归算法解决。基本思路为：以递归算法前序遍历二叉树，当遇到叶子结点时，如果最大层号和最小层号尚未有数值，那么当前叶子的层号就是最大层号和最小层号。如果最大层号和最小层号已经赋过数值，那么应按如下思路处理：如果当前叶子的层号小于原有的最小层号，当前叶子的层号就是最小层号；
如果当前叶子的层号大于原有的最大层号，当前叶子的层号就是最大层号。细化后的算法如下：
Void f34(BinTree T, int level, int *lmin, int *lmax) { if (T) { if(T->lchild==NULL && T->rchild==NULL) if(*lmin==0&&*lmax==0) { *lmin=level; *lmax=level; } else { if(level < *lmin) *lmin=level; if(level > *lmax) *lmax=level; } else { f34(T->lchild, level++, lmin, lmax); f34(T->rchild, level++, lmin, lmax); } } 2005.10 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) 　　A. 操作的有限集合　　　B. 映象的有限集合　　C. 类型的有限集合　　　D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) 　　A. n-i+1 　　　　　　　 B. I 　　C. i+1 　　　　　　　　 D. n-I 3. 若不带头结点的单链表的头指针为head，则该链表为空的判定条件是( ) 　　A. head==NULL 　　　　　B. head->next==NULL 　　C. head!=NULL　　　　　 D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) 　　A. 出队　　　　　　　　 B. 入队　　C. 取队头元素　　　　　D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是( ) 　　A. 2，4，3，1，5，6　　 B. 3，2，4，1，6，5 　　C. 4，3，2，1，5，6 　　D. 2，3，5，1，6，4 6. 字符串通常采用的两种存储方式是( ) 　　A. 散列存储和索引存储　B. 索引存储和链式存储　　C. 顺序存储和链式存储　D. 散列存储和顺序存储 7. 设主串长为n，模式串长为m(m≤n)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为( ) 　　A. m 　　　　　　　　　　B. n-m 　　C. n-m+1　　　　　　　　 D. n 8. 二维数组A［12］［18］采用列优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150，则元素A［9］［7］的地址为( ) 　　A. 429　　　　　　　　　 B. 432 　　C. 435 　　　　　　　　　D. 438 9. 对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是( ) 　　A. (e,f) 　　　　　　　　B. ((e,f)) 　　C. (f) 　　　　　　　　　D. ( ) 10. 下列图示的顺序存储结构表示的二叉树是( ) 11. n个顶点的强连通图中至少含有( ) 　A. n-1条有向边　　　　　　B. n条有向边 C. n(n-1)/2条有向边　　　　D. n(n-1)条有向边 12. 对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为　( 　) 　　A. (19，23，56，34，78，67，88，92) 　B. 23，56，78，66，88，92，19，34) 　　C. (19，23，34，56，67，78，88，92)　 D. (19，23，67，56，34，78，92，88) 13. 若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为( ) 　A. 4 　　　　　　　　　　　B. 5 　C. 8 　　　　　　　　　　　D. 9 14. 由同一关键字集合构造的各棵二叉排序树( ) 　　A. 其形态不一定相同，但平均查找长度相同　　B. 其形态不一定相同，平均查找长度也不一定相同　　C. 其形态均相同，但平均查找长度不一定相同　　D. 其形态均相同，平均查找长度也都相同 15. ISAM文件和VSAM文件的区别之一是( ) 　　A. 前者是索引顺序文件，后者是索引非顺序文件　　B. 前者只能进行顺序存取，后者只能进行随机存取　　C. 前者建立静态索引结构，后者建立动态索引结构　　D. 前者的存储介质是磁盘，后者的存储介质不是磁盘二、填空题(本大题共10小题，每空2分，共20分) 16. 数据的逻辑结构在计算机存储器内的表示，称为数据的____________。

17. 删除双向循环链表中*p的前驱结点(存在)应执行的语句是____________。

18. 栈下溢是指在____________时进行出栈操作。

19. 已知substr(s,i,len)函数的功能是返回串s中第i个字符开始长度为len的子串，strlen(s)函数的功能是返回串s的长度。若s=″ABCDEFGHIJK″,t=″ABCD″,执行运算substr(s,strlen(t), strlen(t))后的返回值为____________。

20. 去除广义表LS=(a1,a2,a3,……，an)中第1个元素，由其余元素构成的广义表称为LS的____________。

21. 已知完全二叉树T的第5层只有7个结点，则该树共有____________个叶子结点。

22. 在有向图中，以顶点v为终点的边的数目称为v的____________。

23. 当关键字的取值范围是实数集合时，无法进行箱排序和____________排序。

24. 产生冲突现象的两个关键字称为该散列函数的____________。

25. 假设散列文件中一个桶能存放m个记录，则桶“溢出”的含义是，当需要插入新的记录时，该桶中____________。

三、解答题(本大题共4小题，每小题5分，共20分) 26. 假设以数组seqn［m］存放循环队列的元素，设变量rear和quelen分别指示循环队列中队尾元素的位置和元素的个数。

(1)写出队满的条件表达式；

(2)写出队空的条件表达式；

(3)设m=40,rear=13,quelen=19,求队头元素的位置；

(4)写出一般情况下队头元素位置的表达式。

27. 已知一棵二叉树的中序序列为ABCDEFG，层序序列为BAFEGCD，请画出该二叉树。

28. 画出下图所示有向图的所有强连通分量。

29. 对7个关键字进行快速排序，在最好的情况下仅需进行10次关键字的比较。

(1)假设关键字集合为{1,2,3,4,5,6,7}，试举出能达到上述结果的初始关键字序列；

(2)对所举序列进行快速排序，写出排序过程。

四、算法阅读题(本大题共4小题，每小题5分，共20分) 30. 阅读下列算法，并回答问题：
　(1)设顺序表L=(3,7,11,14,20,51)，写出执行f30(&L,15)之后的L；

　(2)设顺序表L=(4,7,10,14,20,51)，写出执行f30(&L,10)之后的L；

　(3)简述算法的功能。

　void f30(SeqList*L, DataType x) 　{ 　　int i =0, j; 　　while (ilength && x>L->data［i］)i++; 　if(ilength && x==L->data［i］) 　　　{ 　　for(j=i+1;jlength;j++) 　　L->data［j-1］=L->data［j］; 　　L->length--; } 　　 else 　　　　{for(j=L->length;j>i;j--) 　　L->data［j］=L->data［j-1］; 　　L->data［i］=x; 　　L->length++; 　} } 31. 已知图的邻接表表示的形式说明如下：
　　#define MaxNum 50 //图的最大顶点数　　typedef struct node { 　　int adjvex; //邻接点域　　struct node *next; //链指针域　　} EdgeNode; //边表结点结构描述　　typedef struct { 　　char vertex; //顶点域　　EdgeNode *firstedge; //边表头指针　　} VertexNode; //顶点表结点结构描述　　typedef struct { 　　VertexNode adjlist［MaxNum］; //邻接表　　int n, e; //图中当前的顶点数和边数　　} ALGraph; //邻接表结构描述　下列算法输出图G的深度优先生成树(或森林)的边。阅读算法，并在空缺处填入合适的内容，使其成为一个完整的算法。

　　typedef enum {FALSE, TRUE} Boolean; 　　Boolean visited［MaxNum］; 　　void DFSForest(ALGraph *G){ 　　int i; 　　for(i=0;in;i++) 　　visited［i］=___________________(1); 　　for(i=0;in;i++) if (!visited［i］) DFSTree(G,i); 　　} 　　void DFSTree(ALGraph *G, int i) { 　　EdgeNode *p; 　　visited［i］=TRUE; 　　p=G->adjlist［i］. firstedge; 　　while(p!=NULL){ 　　if(!visited［p->adjvex］){ 　　printf(″<%c,%c>″,G->adjlist［i］. vertex, 　　G->adjlist［p->adjvex］. vertex); 　　_______________(2); 　　} 　　_______________(3); 　　} 　　} 32. 阅读下列算法，并回答问题：
　　(1)假设数组L［8］={3,0,5,1,6,4,2,7}，写出执行函数调用f32(L，8)后的L；

　　(2)写出上述函数调用过程中进行元素交换操作的总次数。

　　void f32(int R［］,int n){ 　　int i,t; 　　for (i=0;i<N-1;I++) 　　while (R［i］!=i){ 　　t=R［R［i］］; 　　R［R［i］］=R［i］; 　　R［i］=t; 　　} 　　} 　33. 已知带头结点的单链表中的关键字为整数，为提高查找效率，需将它改建为采用拉链法处理冲突的散列表。设散列表的长度为m，散列函数为Hash(key)=key%m。链表的结点结构为：
请在空缺处填入适当内容，使其成为一个完整算法。

　void f33 (LinkList L, LinkList H［］, int m) 　　{//由带头结点的单链表L生成散列表H，散列表生成之后原链表不再存在　　int i,j; 　LinkList p,q; 　　for (i=0;i<M;I++) 　　H［i］=_____________(1); 　　p=L->next; 　　while(p) 　　{ 　　q=p->next; 　　j=p->key%m; 　　_________________(2); 　　H［j］=p; 　　_________________(3); 　　} 　　free(L); 　　} 五、算法设计题(本大题10分) 　34. 假设以带双亲指针的二叉链表作为二叉树的存储结构，其结点结构的类型说明如下所示。

typedef char DataType; typedef struct node { DataType data; struct node *lchild, *rchild; //左右孩子指针 struct node *parent; //指向双亲的指针 } BinTNode; typedef BinTNode *BinTree; 若px为指向非空二叉树中某个结点的指针，可借助该结构求得px所指结点在二叉树的中序序列中的后继。

(1)就后继的不同情况，简要叙述实现求后继操作的方法；

(2)编写算法求px所指结点的中序序列后继，并在算法语句中加注注释。

一、单项选择题 1.B 2.D 3.A 4.A 5.D 6.C 7.C 8.A 9.B 10.A 11.B 12.D 13.C 14.B 15.C 二、填空题 16．存储结构 17. q=p->prior; q->prior->next=p; p->prior=q->prior; free(q); 18. 栈空 19. “DEFG” 20. 求表尾操作 21. 11 22. 入度 23. 基数 24. 同义词 25、已经有m个同义词记录三、解答题：
26．（1）Q->quelen==m (2) Q->quelen==0 (3) 13-19+40=32 (4) Q->rear-Q->quelen+m) % m 27． 28．3个：a 、 bce、 dfg 29．我们知道，对n个关键自序列进行一趟快速排序，要进行n-1次比较，也就是基准和其他n-1个关键字比较。这里最好的情况，即要求在做partition的时候，每次都正好将序列平分。即7 - 1 + 2 * ( 3 - 1 ) = 10，满足要求2趟快速排序后，算法结束。所以，列举出来的序列，应该是：
(1)、4 1 3 2 6 5 7 或 4 1 3 7 6 5 2或 4 5 3 7 6 1 2或 4 1 3 5 6 2 7 等等。

四、算法阅读题：
30、(1) L=(3,7,11,14,15,20,51) (2) L=(4,7,14,20,51) (3) 在顺序表L中查找数x, 如果找到，则删除x，如果没找到，则在适当的位置插入x，保证插入后，L依然有序。

31、(1) FALSE //初始化为未访问过 (2) DSFTree( G, p->adjvex ); //从相邻结点往下继续深度搜索 (3) p = p->next; //找到下一个未访问的邻结点 32、(1) L = { 0, 1, 2, 3, 4, 5, 6, 7 }; (2)5次 33、(1) NULL ; //初始化 (2) p->next = H[ j ]; //和下面一句完成头插法 (3) p = q; //继续遍历L 五、算法设计题：
(1) a)如果*px 有右孩子，则其右子树的最左点为其中序序列中的后继；

b)如果*px 无右孩子，从*px开始回溯其祖先结点，找到第1个身份为左孩子的结点；

如果找到，则该结点的父结点为*px的中序序列中的后继。如果找不到，则结点*px没有直接后继。

(2) BinTNode * fintNext( BinTNode * px ) { BinTNode *q, *qp; if( px-> rchild ) //*px 有右孩子 { q=px->rchild; while(q->lchild) q=q->lchild; // 寻找其右孩子的最左点 return q; // 返回找到的结点。

} else { q = px; qp=q->parent; while( qp ) //未回溯到根结点 { if( qp->lchild == q ) return qp; //如果q是qp的左孩子，即找到上面所述结点 else { q = qp; qp=q->parent; } // 否则，继续往上回溯 } return NULL; //未找到 } } 2005.10B 1.若要描述数据处理的变化过程，其正确的次序应为( ) A.处理要求、基本运算和运算、算法 B.处理要求、算法、基本运算和运算 C.基本运算和运算、处理要求、算法 D.算法、处理要求、基本运算和运算 2.从运算类型角度考虑，属于引用型的运算是( ) A.插入、删除 B.删除、修改 C.查找、读取 D.查找、删除 3.若在长度为n的顺序表中插入一个结点，则其结点的移动次数( ) A.最少为0，最多为n B.最少为1，最多为n C.最少为0，最多为n+1 D.最少为1，最多为n+1 4.在一个单链表中，若p所指结点是q所指结点的前驱结点，则在结点p、q之间插入结点s的正确操作是( ) A.s->next=q；
p->next=s->next B.p->next=q；
p->next=s C.s->next=p->next；
p->next=s D.s->next=q->next；
p->next=s->next 5.若有一串数字5、6、7、8入栈，则其不可能的输出序列为( ) A.5、6、7、8 B.8、7、6、5 C.8、7、5、6 D.5、6、8、7 6.FORTRAN语言对数组元素的存放方式通常采用( ) A.按行为主的存储结构 B.按列为主的存储结构 C.按行或列为主的存储结构 D.按行和列为主的存储结构 7.树是n个结点的有穷集合，( ) A.树的结点个数可以为0，此时称该树为空树 B.树至少含有一个根结点，不能为空 C.树至少含有一个根结点和一个叶子结点 D.树至少含有一个根结点和两个叶子结点 8.深度为k的二叉树至多有( ) A.2k个叶子 B.2k-1个叶子 C.2k-1个叶子 D.2k-1-1个叶子 9.具有10个顶点的有向完全图应具有( ) A.20条弧 B.50条弧 C.90条弧 D.100条弧 10.从V1出发，对题10图按广度优先搜索遍历，则可能得到的一种顶点序列为( ) A.V1V2V3V5V4V6 B.V1V2V3V5V6V4 C.V1V5V2V3V6V4 D.V1V3V6V4V5V2 11.适用于静态的查找方法为( ) A.二分查找、二叉排序树查找 B.二分查找、索引顺序表查找 C.二叉排序树查找、索引顺序表查找 D.二叉排序树查找、散列法查找 12.采用二分查找法，若当前取得的中间位置MID的元素值小于被查找值，则表明待查元素可能在表的后半部分，下次查找的起始位置通常应( ) A.从MID/2位置开始 B.从MID位置开始 C.从MID-1位置开始 D.从MID+1位置开始 13.磁盘是一种广泛使用的外部存储设备，对磁盘的存取操作( ) A.只能用顺序方式 B.只能用随机方式 C.既能用顺序方式也能用随机方式 D.方式取决于具体的机器 14.当待排序序列中记录数较少或基本有序时，最适合的排序方法为( ) A.直接插入排序法 B.快速排序法 C.堆排序法 D.归并排序法 15.若对序列（26，90，23，53，16，34，69，39，22）进行一趟排序后所得到的结果为（22，16，23，26，53，34，69，39，90），则该排序可能使用的方法是( ) A.插入排序 B.冒泡排序 C.快速排序 D.选择排序二、填空题(本大题共13小题，每小题2分，共26分) 请在每小题的空格中填上正确答案。错填、不填均无分。

16.算法通常可分为程序、伪语言算法和__________三种类型。

17.时间复杂性描述量级中，若某算法达到__________量级，则该算法通常是不可计算的。

18.对顺序表执行删除操作，其删除算法的平均时间复杂性为__________。

19.若head表示循环链表的头指针，t表示尾结点，则头指针head与尾结点t之间的关系可表示为__________。

20.我们通常把队列中允许删除的一端称为__________。

21.二维数组A［5］［6］采用按列为主序的存储方式，每个元素占3个存储单元，若A［0］［0］的存储地址是100，则A［4］［3］的存储地址是__________。

22.树在数据结构中常采用孩子链表表示法、__________三种存储结构表示。

23.若某二叉树中度为1的结点数为4，度为2的结点数为6，则该树叶子结点数为__________。

24.对于n个顶点的生成树，其边的个数为__________ 。

25.对于具有n个元素的数据序列，若采用二分查找法，当n的值较大时其平均查找长度为__________。

26.解决散列所引起冲突的方案中，__________法是介于开散列表与闭散列表之间的一种方法。

27.多关键字文件是指同时对__________两部分都建立索引的文件组织形式。

28.排序通常可分为内部排序和外部排序，其中内部排序是指排序的整个过程中，数据全部存放在计算机的__________中。

三、应用题(本大题共5小题，每小题6分，共30分) 29。对于如下图所示的二叉树，分别写出其先根遍历、中根遍历和后根遍历的结点访问序列。

30、设散列函数为H(Key)=Key % 11，散列表长度为11（散列地址空间为0…10），在给定表（SUN,MON,TUE,WED,THU,FRI,SAT）中，取单词的第一个字母在英语字母表中的序号为键值K，构造一个散列表，并用线性探测法解决有关的地址冲突。请画出这个散列表。

31、请给出下图的邻接矩阵和邻接表表示。

32.已知一组键值序列（32，44，38，65，53，42，29，57），试采用堆排序法对该组序列作升序排序，给出建立的初始堆以及第一次输出堆元素后筛选调整的堆。

33.已知一组键值序列（13，12，16，17，15，14，11），试采用二路归并排序法对该组序列作升序排序，并给出每一趟的排序结果。

四、设计题(本大题共2小题，每小题7分，共14分) 34.若循环单链表长度大于1，p为指向链表中某结点的指针，试编写一算法删除p结点的前驱结点。

35.若二叉树用二叉链表表示，试编写一算法计算一棵二叉树的叶子总数（可采用递归算法描述）。

一、单项选择题 1.B 2.C 3.A 4.C 5.C 6.B 7.A 8.C 9.C 10.B 11.A 12.D 13.C 14.A 15.C 二、填空题 16．非形式算法语言 17. 指数 18. O(n) 19. t->next=head 20.队首（队头）结点 21.157 22. 双亲表示法孩子兄弟链表法 23. 7 24. n-1 25. Log2n 26、公共溢出区法 27 主关键字与次关键字 28、内存三、应用题：
29．先根遍历：ABDEFC 中根遍历：BFEDAC 后根遍历：FEDBCA 30． 0 1 2 3 4 5 6 7 8 9 10 SAT WED MON FRI SUN TUE THU 31．邻接矩阵和邻接表如下：
32．（考试中建议画成完全二叉树形式）初始建堆后的顺序：
65 57 42 44 53 38 29 32 进行一次输出后再调整：57 53 42 44 32 38 29 65 33、归并排序：
13 12 16 17 15 14 11 12 13 16 17 14 15 11 12 13 16 17 11 14 15 11 12 13 14 15 16 17 四、算法设计题：
34、本题基本思路为：先找到结点p的直接前驱的直接前驱结点，标记为q，并把p的直接前驱结点标记为s；
然后通过修改指针将s从链表中删除。最后释放结点s。

void f34(LinkList L, ListNode *p) {ListNode *q, *s; q=p; while(q->next->next !=p) q=q->next; // 查找结点p的前驱的前驱；

s=q->next; // 把p的直接前驱标记为s; q->next=s->next; free(s); // 释放结点s所占用的空间。

} 35、本题的基本思路是：首先定义公共变量count，并赋予初值0，然后递归遍历二叉树，每次遇到度为0的结点（即叶子结点）时，计数器Count的值加1。算法如下：
int count=0; void f35(BinTree T) { if (T) { if(T->lchild==NULL && T->rchild==NULL) count++; else { f35(T->lchild); f35(T->rchild); } } } QG2003.1 1.下面程序段的时间复杂度是( ) for(i=0;i<n;i++) for(j=1;j<m;j++) A[i][j]=0；

A.O(n) B.O(m+n+1) C.O(m+n) D.O(m*n) 2.在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是( ) A.p=p->next; B.p->next=p->next->next; C.p->next=p; D.p=p->next->next; 3.在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next= head,则( ) A.p指向头结点 B.p指向尾结点 C.*p的直接后继是头结点 D.*P的直接后继是尾结点 4.判定“带头结点的链队列为空”的条件是( ) A.Q.front==NULL B.Q.rear==NULL C.Q.front==Q.rear D.Q.front!=Q.rear 5.设有两个串T和P，求P在T中首次出现的位置的串运算称作( ) A.联接 B.求子串 C.字符定位 D.子串定位 6.广义表A=(a,(b),(),(c,d,e))的长度为( ) A.4 B.5 C.6 D.7 7.一棵含18个结点的二叉树的高度至少为( ) A.3 B.4 C.5 D.6 8.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为( ) A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA 9.无向图中一个顶点的度是指图中( ) A.通过该顶点的简单路径数 B.与该顶点相邻接的顶点数 C.通过该顶点的回路数 D.与该顶点连通的顶点数 10.已知一个图如下所示，从顶点a出发进行广度优先遍历可能得到的序列为( ) A.a c e f b d B.a c b d f e C.a c b d e f D.a c d b f e 11.在下列排序方法中，平均时间性能为O(nlogn)且空间性能最好的是( ) A.快速排序 B.堆排序 C.归并排序 D.基数排序 12.已知一组关键字为{25,48,36,72,79,82,23,40,16,35}，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是( ) A.{25,36,48,72,23,40,79,82,16,35} B.{25,36,48,72,16,23,40,79,82,35} C.{25,36,48,72,16,23,35,40,79,82} D.{16,23,25,35,36,40,48,72,79,82} 13.设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为( ) A.21 B.23 C.41 D.62 14.索引非顺序文件的特点是( ) A.主文件无序，索引表有序 B.主文件有序，索引表无序 C.主文件有序，索引表有序 D.主文件无序，索引表无序 15.倒排文件的主要优点是( ) A.便于进行插入和删除运算 B.便于进行文件的恢复 C.便于进行多关键字查询 D.节省存储空间二、填空题(本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分) 16.抽象数据类型的特点是将____________和____________封装在一起，从而现实信息隐藏。

17.从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需____________一个位置。

18.在队列中，允许进行插入操作的一端称为____________，允许进行删除操作的一端称为____________。

19.如图两个栈共享一个向量空间，top1和top分别为指向两个栈顶元素的指针，则“栈满”的判定条件是____________。

20.设S1=“good“,S2=“ “,S3=“book“，则S1，S2和S3依次联接后的结果是____________。

21.假设三维数组A[10][9][8]按行优先顺序存储，若每个元素占3个存储单元，且首地址为100，则元素A[9][8][7]的存储地址是____________。

22.已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为____________。

23.能够成功完全拓扑排序的图一定是一个____________。

24.如果在排序前，关键字序列已接近正序或逆序，则在堆排序和快速排序两者之中，选用____________较为适当。

25.假设哈希表的表长为m，哈希函数为H(key)，若用线性探查法解决冲突，则探查地址序列的形式表达为____________。

三、解答题(本大题共4小题，每小题5分，共20分) 26.假设通信电文使用的字符集为{a,b,c,d,e,f}，名字符在电文中出现的频度分别为：34，5，12，23，8，18，试为这6个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树(要求树中左孩子结点的权值小于右孩子结点的权值)，然后分别写出每个字符对应的编码。

27.已知一个图如下所示，其顶点按a、b、c、d、e、f顺序存放在邻接表的顶点表中，请画出该图的邻接表，使得按此邻接表进行深度优先遍历时得到的顶点序列为acbefd，进行广度优先遍历时得到的顶点序列为acbdfe。

28.已知两个4×5的稀疏矩阵的三元组表分别如下：
0 1 4 16 0 1 1 32 1 2 2 18 1 2 2 －22 2 3 4 －25 2 2 5 69 3 4 2 28 3 3 4 25 4 4 2 51 请画出这两个稀疏矩阵之和的三元组表。

29.从空树起，依次插入关键字40，8，90，15，62，95，12，23，56，32，构造一棵二叉排序树。

(1)画出该二叉排序树 (2)画出删去该树中元素值为90的结点之后的二叉排序树。

四、算法阅读题(本大题共4小题，每小题5分，共20分) 30.如图所示，利用同一循环向量空间实现两个队列，其类型Queue2定义如下：
typedef struct { DataType data[MaxSize]; int front[2],length[2]; } Queue2; 对于i=0或1,front[i]和length[i]分别为第i个队列的头指针和长度域。请在空缺处填入合适的内容，实现第i个循环队列的入队操作。

int EnQueue(Queue2*Q,int i,DataType x) {//若第i个队列不满，则元素x入队列，并返回1，否则返回0 if(i<0||i>1)return 0; if( (1) ) return 0; Q->data[ (2) ]=x; Q->length[ (3) ]++; return 1; } (1) (2) (3) 31.某二叉树的线索链表存储结构如图(b)所示，其中p为指向根结点的指针，图(a)为结点结构。阅读下列算法，并回答问题：
(1)写出执行函数调用f(p)的输出结果；

(2)简述函数f的功能。

void f(BinThrTree t) { while(t) { printf(t->data); if(t->lchild) t=t->lchild; else t=t->rchild; } } (1) (2) 32.下列函数FindCycle(G,i)的功能是，对一个采用邻接表作存储结构的有向图G，利用深度优先搜索策略寻找一条经过顶点vi的简单回路。数组cycle_path用于保存搜索过程中形成的回路，cycle_path[k]=j(j≥0)表示在回路中顶点vk的下一个顶点是vj。请在空缺处填入合适的内容，使其成为一个完整的算法。

vertex firstedge 已知邻接表的顶点表结点结构为：　　　　　　　　　　　　　　　　 adjvex next 边表结点EdgeNode结构为：　　　　　　　　　　　　　　　　　　　　　　 int cycle_path[MaxNum]; int FindCycle(ALGraph*G,int i) {//若回路存在，则返回1，否则返回0 int j; for(j=0;j<G->n;j++)cycle_path[j]=-1; return DFSPath(G,i,i); } int DFSPath(ALGraph*G,int j,int i) { EdgeNode *p; int cycled=0; for(p=G->adjlist[j].firstedge;p&&!cycled;p=p->next) { cycle_path[j]=p->adjvex; if( (1 ) )cycled=1;//已找到回路 else if(cycle_path[p->adjvex]==-1)cycled= (2) ; } return (3) } (1) (2) (3) 33.阅读下列函数algo,并回答问题。

(1)假设整型数组A[1..8]中的元素依次为(3，8，9，1，7，4，2，6)。执行函数调用algo(A,8)时，外层while的循环体执行多少次?函数的返回值是多少? (2)简述函数algo(L,n)的功能。

int algo(int L[],intn) { int i=0,j,s=1,t=n; while (i!=(n+1)/2) { int x=L[s]；

i=s;j=t; while(i<j) { while(i<j && L[j]>=x)j--; L[i]=L[j]; while(i<j && L[i]<=x)i++; L[j]=L[i]; } L[i]=x; if(i<(n+1)/2)s=i+1; else t=i-1; } if(i==0)return 0; else return L[i]; } 五、算法设计题(本大题共10分) 34.假设以带头结点的单循环链表作非递减有序线性表的存储结构。请设计一个时间复杂度为O(n)的算法，删除表中所有数值相同的多余元素，并释放结点空间。例如：
(7，10，10，21，30，42，42，42，51，70) 经算法操作后变为 (7，10，21，30，42，51，70) 一．单项选择题 1.D 2.B 3.D 4.A 5.D 6.A 7.C 8.D 9.B 10.C 11.B 12.A 13.B 14.A 15.C 二.填空题 16. 数据类型，数据运算　17. 向前移动 18. 队尾，队首 19.top1==top2-1 20. ”good book” 21.(9×(9×8)+8×8+7)×3+100=2257 22.(n-1)/k(k-1)+1 　23.有向无环图 24.堆排序　　　　 25.（H（key）+i）%m 三.简答题 26、编码如下：
a: 0 f: 10 c: 110 b: 1110 e: 1111 27、 0 A 2 1 3 1 B 5 2 C 5 4 3 D 2 4 E 5 5 F 3 28、 1 1 32 1 4 16 2 2 －4 2 5 69 3 4 0 4 2 79 29. 四.算法阅读题 30. (1) Q->length[0]+Q->length[1]= =Maxsize (2) Q->front[i]+ Q->length[i]+1 (3) i 31.(1) 利用前序线索化的后继指针实现线索二叉树的前序遍历。

(2) 题目的输出为：A B D F C E G H 32.(1)p->adjvex= =i (2)DFSpath(G,p->adjvex,i) (3)cycled; 33.(1) 函数的返回值为：4，得到的序列是：2 1 3 4 6 7 8 9 外层循环执行了5次。

(2)函数的功能是把无序序列划分为以首关键字为界的两个序列。左边序列的关键字都比3小，右边序列的关键字都比3大。

五.算法设计题 34、思路：遍历链表，同时记录前后两个结点；
如果后一个结点的值和前一个结点的值相同，则删除后一个结点。

2006.1 1．根据数据元素的关键字直接计算出该元素存储地址的存储方法是（　　　） A．顺序存储方法 B．链式存储方法 C．索引存储方法 D．散列存储方法 2．下述程序段中语句①的频度是（　　　） s=0; for(i=1;i<m;i++) for(j=0;j<=i;j++) ① s+=j; A． (m+1)(m-1)/2 B． m(m-1)/2 C． (m+2)(m-1)/2 D． m(m+1)/2 3．求单链表中当前结点的后继和前驱的时间复杂度分别是（　　　） A．O（n）和O（1） B．O（1）和O（1） C．O（1）和O（n） D．O(n)和O（n） 4．非空的单循环链表的头指针为head,尾指针为rear，则下列条件成立的是（　　　） A．rear->next= =head B．rear->next->next= =head C．head->next= =rear D．head->next->next= =rear 5．若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正确配对的算法，通常选用的辅助结构是（　　　） A．栈 B．线性表 C．队列 D．二叉排序树 6．已知主串s=″ADBADABBAAB″，模式串t=″ADAB″，则应用朴素的串匹配算法进行模式匹配过程中，无效位移的次数是（　　　） A．2 B．3 C．4 D．5 7．串s=″Data Structure″中长度为3的子串的数目是（　　　） A．9 B．11 C．12 D．14 8．假设以行优先顺序存储三维数组R[6][9][6]，其中元素R[0][0][0]的地址为2100，且每个元素占4个存储单元，则存储地址为2836的元素是（　　　） A．R[3][3][3] B．R[3][3][4] C．R[4][3][5] D．R[4][3][4] 9．除第一层外，满二叉树中每一层结点个数是上一层结点个数的（　　　） A．1/2倍 B．1倍 C．2倍 D．3倍 10．对于含n个顶点和e条边的图，采用邻接矩阵表示的空间复杂度为（　　　） A．O（n） B．O(e) C．O(n+e) D．O(n2) 11．如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（　　　） A．深度优先搜索算法 B．广度优先搜索算法 C．求最小生成树的prim算法 D．拓扑排序算法 12．快速排序在最坏情况下的时间复杂度是（　　　） A．O(n2log2n) B．O(n2) C．O(nlog2n) D．O(log2n) 13．能进行二分查找的线性表,必须以（　　　） A．顺序方式存储,且元素按关键字有序 B．链式方式存储,且元素按关键字有序 C．顺序方式存储,且元素按关键字分块有序 D．链式方式存储,且元素按关键字分块有序 14．为使平均查找长度达到最小,当由关键字集合{05,11,21,25,37,40,41,62,84}构建二叉排序树时,第一个插入的关键字应为（　　　） A．05 B．37 C．41 D．62 15．ISAM文件的周期性整理是为了空出（　　　） A．磁道索引 B．柱面索引 C．柱面基本区 D．柱面溢出区二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案。错填、不填均无分。

16．数据类型按其值能否分解,通常可分为_________两种类型。

17．队列的修改是按_________的原则进行的。

18．两个串相等的充分必要条件是两个串的长度相等且_________。

19．数组采用顺序存储方式表示是因为通常不对数组进行_________操作。

20．用广义表的取表头head和取表尾tail的运算，从广义表LS=(b,c,(f),((d)))中分解出原子c的操作为_________。

21．结点数为20的二叉树可能达期的最大高度为_________。

22．带权连通图的生成树的权是该生成树上_________。

23．所谓“就地排序”，是指排序算法辅助空间的复杂度为_________的排序方法。

24．5阶B树的根结点至少含有_________个关键字。

25．索引文件中的索引表指示记录的关键字与_________之间一一对应的关系。

三、解答题（本大题共4小题，每小题5分，共20分） 26．假设以有序对<p,c>表示从双亲结点到孩子结点的一条边，若已知树中边的集合为{<a,b>,<a,d>,<a,c>,<c,e>,<c,f>,<c,g>,<c,h>,<e,i>,<e,j>,<g,k>},请回答下列问题：
（1）哪个结点是根结点？（2）哪些结点是叶子结点？（3）哪些结点是k的祖先？（4）哪些结点是j的兄弟？（5）树的深度是多少？ 27．已知有向图G的深度优先生成森林和广度优先生成森林如下。请写出该图的深度优先遍历序列和广度优先遍历序列。

28．当将两个长度均为n的有序表A=（a1，a2，…，an）与B=（b1，b2，…，bn）(ai≠bj, 1≤i,j≤n)归并为一个有序表C=（c1, c2,…,c2n）时，所需进行的元素比较次数最少可达n,最多可达2n-1。

（1）假设有序表C=（2，4，5，6，7，9），试举出两组A与B的例子，使它们在归并过程中进行的元素比较次数分别达到最少和最多；

（2）写出一般情况下，使归并所需进行的元素比较次数分别达到最少和最多时，A与B中的元素应满足的条件。

29．对下列关键字序列（33，25，48，59，36，72，46，07，65，20）构造表长为19的散列表。假设散列函数为h(key)=key%13,用开放地址法解决冲突，探查序列为d=h(key),d+12,d-12，d+2 2,d-2 2,d+32，d-32，…，等等。

（1）画出该散列表；

（2）计算该散列表的装填因子α；

（3）求出等概率情况下查找成功的平均查找长度ASL。

四、算法阅读题（本大题共4小题，每小题5分，共20分） 30．已知head为带头结点的单循环链表的头指针，链表中的数据元素依次为（a1，a2,a3,a4,…,an）,A为指向空的顺序表的指针。阅读以下程序段，并回答问题：
（1）写出执行下列程序段后的顺序表A中的数据元素；

（2）简要叙述该程序段的功能。

if(head->next!=head) { p=head->next; A->length=0; while(p->next!=head) { p=p->next; A->data[A->length ++]=p->data; if(p->next!=head)p=p->next; } } 31．已知链串的存储结构描述如下：
#define NodeSize 4 typedef struct Node { char data [NodeSize]; struct Node * next; } * LinkStr; 阅读下列算法，并回答问题：
（1）t1和t2的串值分别为″Chinese″和″China″时，写出f31(t1,t2)的返回值；

（2）t1和t2的串值分别为″Japan″和″Japanese″时，写出f31(t1,t2)的返回值；

（3）t1和t2的串值都为″string″时，写出f31(t1,t2)的返回值；

（4）简述函数f31的功能。

inf f31(LinkStr t1,LinkStr t2) {//串值以′′为结束符 int i; while (1){ for (i=0;i<NodeSize;i++){ if (t1->data[i]= =′′&&t2->data[i]= =′′return 0; if(t1->data[i]= =′′))return –1; if(t2->data[i]= =′′)}return 1; if(t1->data[i]>t2->data[i]return 1; if(t1->data[i]<t2->data[i]return –1; } t1=t1->next; t2=t2->next; } } 32．设二叉树采用二叉链表存储结构，结点的数据域data为字符类型。阅读下列算法，并回答问题：
（1）对于如图所示的二叉树，写出执行函数f32的输出结果；

（2）简述函数f32的功能。

void f32(BinTree T) { Stack s; //定义栈s BinTree p,q; if (T= =NULL) return; InitStack(&s); p=T; do { while (p){ Push(&s,p); if (p->lchild)p=p->lchild;else p=p->rchild;} while (!Stack Empty(s)&&q=StackTop(s)&&q->rchild= =p){ p=Pop(&s); printf(″%c″,p->data); } if(!StackEmpty(s)){ q=StackTop(s);p=q->rchild; } } while (! Stack Empty(S)); } 33．已知有向图的邻接表表示的形式说明如下：
#define Max Num 50 //图的最大顶点数 typedef struct node { int adjvex; //邻接点域 struct node * next; //链指针域 }EdgeNode; //边表结点结构描述 typedef struct { char vertex; //顶点域 EdgeNode *firstedge; //边表头指针 }VertexNode; //顶点表结点结构描述 typedef struct{ Vertex Node adjlist [MaxNum]; //邻接表 int n,e; //图中当前的顶点数和边数 }ALGraph; //邻接表结构描述下列函数f33是从有向图G中删除所有以vi为弧头的有向边。请在空缺处填入合适的内容,使其成为一个完整的算法。

void f33 (ALGraph * G, int i) { int j; EdgeNode * p, *q; for (j=0;j<G->n;j= + +){ p=G->adjlist [j].firstedge; while( (1) { q=p; p=p->next; } if(p!=NULL) { if (p !=G->adjlist[j].firstedge) q->next=p->next; else( (2) ; free(p); G->e=( (3) ; } } } 五、算法设计题（本大题10分） 34．在带头结点的循环链表L中，结点的数据元素为整型，且按值递增有序存放。给定两个整数a和b，且a<b，编写算法删除链表L中元素值大于a且小于b的所有结点。

一、单项选择题 1.D 2.C 3.C 4.A 5.A 6.B 7.C 8.B 9.C 10.D 11.B 12.B 13.A 14.B 15.D 二、填空题 16．简单类型和复杂类型 17. 先进先出 18. 对应字符一一相等 19. 增加或减少数组元素个数的 20. head(tail(LS)) 21.20 22. 所有路径长度之和 23. O(1) 24. 1个 25、记录三、解答题：
26．（1）a (2) b d h i j f k (3) c a (4) i (5) 4 27．a c f e b d g a c e f b d g 28．(1) 使比较次数最少：
A={2 4 5} B={6 7 9} 使比较次数最多：A={2 5 7} B={ 4 6 9} (2) 使比较次数最少时，应该满足：an<b1或者bn<a1; 数据在两个有序序列中均匀分布，合并时需要交替式地从两个序列中取数据。

29．（略）四、算法阅读题：
30、 a2 a4 a6 a8 a10 … 把链表中所在位置为偶数的结点的数据存储到一个顺序表中。

31、1 －1 0 比较两个字符串的大小；

32、D B F G E C A 后序遍历二叉树 33、程序功能是删除结点vi的入边。填空如下：
p && p->data !=i G->adjlist[j].firstedge=p->next; G->e--; 五、算法设计题：
34、本题的解决方法有两种：（1）扫描整个单循环链表，如果发现结点值在a和b之间，则删除该结点。即把满足条件的结点逐个删除；
(2)扫描链表，标记出满足条件的一段子链表，然后把这段子链表删除。两种方法的时间复杂度相同，因为在方法2中也需要逐个释放被删除的结点。这里我们使用方法（1）具体算法如下：
void f34(LinkList L, int a, int b) {ListNode *p, *q; p=L; while(p->next !=L) // 扫描整个链表 { q=p->next; // q指向p的直接后继 if(q->data>=a && q->data<=b) // 如果q的值满足条件（在a和b之间） { p->next= q->next; // 修改指针，删除结点q；

free(q); // 释放q的值 } p=p->next；

// 检查下一个结点；

} }