结点数据结构试题

部分题目或答案有问题，现将已经发现的公布如下， 同学在作这些模拟题的时候应着重做题方法的理解，遇到问题以教材或课件为准，不确定的地方可找同学商量或问我

（1）试卷1第一套填空题第1题，试卷1第2套选择题第3题关于循环队列队头指针和队尾指针的约定与教材不一致， 以教材或课件为准，实际上front指向的是队头元素， rear指向当前尚未被占用的第一个队列空间， 队慢或队空的判定条件及入队/出队等操作具体可参考课件或教材

（2）试卷1第一套应用题第5题，不声明邻接点顺序时默认编号最小的邻接点为第一邻接点，该图的深度优先遍历序列为123465,答案错。此外，当给定邻接表时则邻接点顺序按照邻接表中的前后顺序确定，如试卷1第二套填空题第8题

（3）试卷1第五套应用题第4题，两种方法处理冲突的方法下所求ASL值相等都为7/6

（4）试卷1第五套填空题第8题答案给出的是小顶堆需满足的条件，大顶堆满足 ki>=k2i&&ki>=k2i+1

（5）试卷1第一套填空题第9题模式匹配的BF算法以书中答案为准，两者区别在于，教材中存储字符串的数组的0号单元不存放有效字符，而试卷答案认为0号单元也放数组

（6）试卷1第二套填空题第7题给定初始序列建堆未声明建大顶堆还是小顶堆，答案中给出的是小顶堆，大顶堆也要会建

（7）试卷1第二套应用题第1题第4趟直接插入排序的结果应为(22， 40， 45， 48， 80， 78)；答案中给出的实际为第三趟，关键在于首元素自身有序不算一趟

（8）试卷1第二套填空题第2题入栈操作以教材为准，教材中top是指向的栈顶(第一个空位置)的指针，与该套试卷中栈顶结构不一样， 以教材为准

（9）试卷1第三套填空题第12题答案中给出的不是拓扑序列，正确的是1423

（10）试卷1中多处遇到空指针NULL时写的是0而非NULL，实际两者皆可

（11）试卷1第4套填空题第2题双向链表的删除答案错，应为p—>l l ink->rl ink=p->rl ink;p->rl ink->l l ink=p->l l ink;此外，注意课堂中讲的指针名和操作方法

（12）第4套填空题第6题答案错，设哈夫曼树中共有99个结点，则该树中有____50_____个叶子结点；若采用二叉链表作为存储结构，则该树中有__100___个空指针域。

（13）第5套选择第8题答案应为A:设连通图G中的边集E={(a， b)， (a， e)， (a， c)， (b， e)， (e，d)， (d， f)， (f， c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为

(A) abedfc

(14)第5套应用题第3题题目未指明查找方法，没法作

（15）第6套选择第5题应选B，实际是任意结点至多只有一个孩子：设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是(B)高度等于其结点数

（16）第7套填空1题问题本身错，设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为____s->left_____=p； s->right=p->right；___p->right_______=s； s->right->left=s； （设结点中的两个指针域分别为left和right） 。

（17）第8套填空题第8题答案错

（18）第7套选择第3题题目错，应以60为基准关键字，答案为C．设一组初始记录关键字序列为(60，

80， 55， 40， 42， 85)，则以第一个关键字60为基准而得到的一趟快速排序结果是（ ） 。 (C)42，

40， 55， 60， 80， 85

（17）第6套填空9题．快速排序算法的空间复杂度平均情况下为_O(logn)_，最坏的情况下为_O(n)_。

(18)第9套填空第3题，题目说循环队列有m个元素实际指循环队列总长为m，此外，该题关于队头和队尾指针的约定不同于教材

（19）第9套填空第4题答案错， 9个元素冒泡排序，第一趟比较次数为8，最多8趟

1

1．组成数据的基本单位是（ ）。

(A)数据项 (B)数据类型 (C)数据元素 (D)数据变量

2．设数据结构A=(D， R) ，其中D={1， 2， 3， 4}， R={r}， r={<1， 2>， <2， 3>， <3， 4>， <4， 1>}，则数据结构A是（ ）。

(A)线性结构 (B)树型结构 (C) 图型结构 (D)集合

3．数组的逻辑结构不同于下列（ ）的逻辑结构。

(A)线性表 (B)栈 (C) 队列 (D)树

4．二叉树中第i (i≥1)层上的结点数最多有（ ）个。

(A) 2i (B) 2i (C) 2i-1 (D) 2i-1

5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（ ）。

(A) p->next=p->next->next (B) p=p->next

(C) p=p->next->next (D) p->next=p

6．设栈S和队列Q的初始状态为空，元素E1、 E2、 E3、 E4、 E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、 E4、 E3、 E6、 E5和E1，则栈S的容量至少应该是（ ）。(A) 6 (B) 4 (C) 3 (D) 2

7．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（ ）。

(A) 100 (B) 40 (C) 55 (D) 80

8．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（ ）。

(A) 3 (B) 4 (C) 5 (D) 1

9．根据二叉树的定义可知二叉树共有（ ）种不同的形态。

(A) 4 (B) 5 (C) 6 (D) 7

10.设有以下四种排序方法，则（ ）的空间复杂度最大。

(A) 冒泡排序 (B)快速排序 (C)堆排序 (D)希尔排序

1. 设顺序循环队列Q[0： m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F=____________; 。

2. 设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为___________，在链式存储结构上实现顺序查找的平均时间复杂度为___________。

3. 设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有________个指针域， __________个空指针域。

4. 设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点B的操作序列为______________________________________。

5. 设无向图G中有n个顶点和e条边，则其对应的邻接表中有_________个表头结点和_________个表结点。

6. 设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有______关系。

7. 设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为__________。

8. 设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编号为8的双亲结点的编号是___________，编号为8的左孩子结点的编号是_____________。

9. 下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。int index(char s[ ],char t[ ])

{i=j=0;

2

while(i<strlen(s)&&j<strlen(t)) if(s[i]==t[j]){i=i+l;j=j+l;}else{i=_______;j=______;}if(j==strlen(t))return(i-strlen(t));else return(-1);

}

10.设一个连通图G中有n个顶点e条边，则其最小生成树上有________条边。

1．设完全二叉树的顺序存储结构中存储数据ABCDE，要求给出该二叉树的链式存储结构并给出该二叉树的前序、 中序和后序遍历序列。

2．设给定一个权值集合W=(3， 5， 7， 9， 11) ，要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL。

1. 设计判断单链表中结点是否关于中心对称算法。

2. 设计在链式存储结构上建立一棵二叉树的算法。

3. 设计判断一棵二叉树是否是二叉排序树的算法。

3

1.C 2.C 3.D 4.C 5.A

6.C 7.C 8.B 9.B 10.B

1. (F+1) % m

2. O(n) ， O(n)

3. 2n， n+1

4. s->next=p->next; s->next=s

5. n, 2e

6. m=2e

7. CBA

8. 4， 16

9. i-j+1， 0

10. n-1

1. 链式存储结构略，前序ABDEC， 中序DBEAC，后序DEBCA。

2. 哈夫曼树略， WPL=78

3. (18,5, 16, 19,21,23) ， (5， 16， 21， 19， 18， 23)h0

h568h627

5. 深度： 125364，广度： 123456，最小生成树T的边集为E={(1， 4)， (1， 3)， (3， 5)， (5， 6)， (5,6)}

1. 设计判断单链表中结点是否关于中心对称算法。typedef struct {int s[100]; int top;} sqstack;int lklistsymmetry(lklist*head)

{sqstack stack; stack.top=-1; lklist*p;for(p=head;p!=0;p=p->next) {stack.top++; stack.s[stack.top]=p->data;}for(p=head;p!=0;p=p->next) if(p->data==stack.s[stack.top]) stack.top=stack.top-1;else return(0);return(1);

}

2. 设计在链式存储结构上建立一棵二叉树的算法。typedef char datatype;typedef struct node {datatype data; struct node*lchild,*rchild;}bitree;void createbitree(bitree*&bt)

4

{char ch; scanf("%c",&ch);if(ch=='#') {bt=0;return;}bt=(bitree*)malloc(sizeof(bitree));bt->data=ch;createbitree(bt->lchild);createbitree(bt->rchild);

}

3. 设计判断一棵二叉树是否是二叉排序树的算法。int minnum=-32768,flag=1;typedef struct node{int key; struct node*lchild,*rchild;}bitree;void inorder(bitree*bt)

{if(bt!=0)

{inorder(bt->lchi l d); i f(minnum>bt->key)fl ag=0;minnum=bt->key; inorder(bt->rchild);}}

5

1．下面关于线性表的叙述错误的是（ ）。

(A)线性表采用顺序存储必须占用一片连续的存储空间

(B)线性表采用链式存储不必占用一片连续的存储空间

(C)线性表采用链式存储便于插入和删除操作的实现

(D)线性表采用顺序存储便于插入和删除操作的实现

2．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ ）个空指针域。

(A) 2m-1 (B) 2m (C) 2m+1 (D) 4m

3．设顺序循环队列Q[0： M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ ）。

(A) R-F (B) F-R (C) (R-F+M)％M (D) (F-R+M)％M

4．设某棵二叉树的中序遍历序列为AB CD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（ ）。

(A) BADC (B) BCDA (C) CDAB (D) CBDA

5．设某完全无向图中有n个顶点，则该完全无向图中有（ ）条边。

(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1

6．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（ ）。

(A) 9 (B) 10 (C) 11 (D) 12

7．设某有向图中有n个顶点，则该有向图对应的邻接表中有（ ）个表头结点。

(A) n-1 (B) n (C) n+1 (D) 2n-1

8．设一组初始记录关键字序列(5， 2， 6， 3， 8) ， 以第一个记录关键字5为基准进行一趟快速排序的结果为（ ）。

(A) 2， 3， 5， 8， 6 (B) 3， 2， 5， 8， 6

(C) 3， 2， 5， 6， 8 (D) 2， 3， 6， 5， 8

1. 为了能有效地应用 HASH查找技术， 必须解决的两个问题是____________________和

_。

2. 下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。typedef struct {int s[100]; int top;} sqstack;void push(sqstack&stack,int x)

{if(stack.top==m-1)printf(“overflow”);else {____________________;_________________;}

}

3. 中序遍历二叉排序树所得到的序列是___________序列（填有序或无序）。

4. 快速排序的最坏时间复杂度为___________，平均时间复杂度为__________。

5. 设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1 ，则该二叉树中度数为2的结点数为_________；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有_______个空指针域。

6. 设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d，则e=_______。

7. 设一组初始记录关键字序列为(55， 63， 44， 38， 75， 80， 31， 56) ，则利用筛选法建立的初始堆为___________________________。

6

8. 设某无向图G的邻接表为；

广度优先遍历序列为____________。

1． 设一组初始记录关键字序列为(45， 80， 48， 40， 22， 78) ，则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。

2． 设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为l l i nk和r l i nk）。

3． 设一组有序的记录关键字序列为(13， 18， 24， 35， 47， 50， 62， 83， 90) ，查找方法用二分查找，

叉排序树并给出构造过程。

1． 设有一组初始记录关键字序列（K1 ， K2， „， Kn），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki ，右半部分的每个关键字均大于等于Ki。

2． 设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、 B和C用链式存储结构表示。

7

1.D 2.B 3.C 4.A 5.A 6.C 7.B 8.C

1. 构造一个好的HASH函数，确定解决冲突的方法

2. stack. top++， stack. s[stack.top]=x

3. 有序

4. O(n2) ， O(nlog2n)

5. N0-1， 2 N0+N1

6. d/2

7. (31， 38， 54， 56， 75， 80， 55， 63)

8. (1， 3， 4， 2) ， (1， 3， 2， 4)

1. (22， 40， 45， 48， 80， 78) ， (40， 45， 48， 80， 22， 78)

2. q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;

3. 2,ASL=91*1+2*2+3*4+4*2)=25/9

4. 树的链式存储结构略，二叉树略

5. E={(1， 3)， (1， 2)， (3， 5)， (5， 6)， (6， 4)}

6. 略

1. 设有一组初始记录关键字序列（K1 ， K2，„， Kn），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki ，右半部分的每个关键字均大于等于Ki。void quickpass(int r[], int s, int t)

{int i=s,j=t,x=r[s];whi l e(i<j){while(i<j&&r[j]>x)j=j-1; if(i<j) {r[i]=r[j];i=i+1;}whi l e(i<j&&r[i]<x) i=i+1; i f(i<j) {r[j]=r[i];j=j-1;}

}r[i]=x;

}

2. 设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、 B和C用链式存储结构表示。typedef struct node {int data; struct node*next;}lklist;void intersection(lklist*ha,lklist*hb,lklist*&hc)

{lklist*p,*q,*t;for(p=ha,hc=0;p!=0;p=p->next)

{ for(q=hb;q!=0;q=q->next) i f(q->data==p->data)break;if(q!=0){ t=(lklist*)malloc(sizeof(lklist)); t->data=p->data;t->next=hc;hc=t;}

}

}

8

1．设某数据结构的二元组形式表示为A=(D， R)， D={01， 02， 03， 04， 05， 06， 07， 08， 09}， R={r}，r={<01 ， 02>， <01， 03>， <01， 04>， <02， 05>， <02， 06>， <03， 07>， <03， 08>， <03， 09>}，则数据结构A是（ ）。

(A)线性结构 (B)树型结构 (C)物理结构 (D) 图型结构

2．下面程序的时间复杂为（ ）for （i=1， s=0； i<=n； i++） {t=1； for(j=1； j<=i； j++) t=t*j； s=s+t； }

(A) O(n) (B) O(n2) (C) O(n3) (D) O(n4)

3．设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（ ）。(A) q=p->next； p->data=q->data； p->next=q->next； free(q) ；

(B) q=p->next； q->data=p->data； p->next=q->next； free(q) ；

(C) q=p->next； p->next=q->next； free(q) ；

(D) q=p->next； p->data=q->data； free(q) ；

4．设有n个待排序的记录关键字，则在堆排序中需要（ ）个辅助记录单元。

(A) 1 (B) n (C) nlog2n (D) n2

5．设一组初始关键字记录关键字为(20， 15， 14， 18， 21， 36， 40， 10) ，则以20为基准记录的一趟快速排序结束后的结果为( ) 。

(A) 10， 15， 14， 18， 20， 36， 40， 21

(B) 10， 15， 14， 18， 20， 40， 36， 21

(C) 10， 15， 14， 20， 18， 40， 36， 2l

(D) 15， 10， 14， 18， 20， 36， 40， 21

6．设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（ ）。

(A) O(1) (B) O(log2n) (C) (D) O(n2)

7．设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（ ）。(A) n， e (B) e， n (C) 2n， e (D) n， 2e

8.设某强连通图中有n个顶点，则该强连通图中至少有（ ）条边。

(A) n(n-1) (B) n+1 (C) n (D) n(n+1)

9．设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（ ）方法可以达到此目的。

(A)快速排序 (B)堆排序 (C)归并排序 (D)插入排序

10.下列四种排序中（ ）的空间复杂度最大。

(A)插入排序 (B) 冒泡排序 (C)堆排序 (D)归并排序

1. 数据的物理结构主要包括_____________和______________两种情况。

2. 设一棵完全二叉树中有500个结点，则该二叉树的深度为__________；若用二叉链表作为该完全二叉树的存储结构，则共有___________个空指针域。

3. 设输入序列为1、 2、 3，则经过栈的作用后可以得到___________种不同的输出序列。

4. 设有向图G用邻接矩阵A[n] [n]作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i

的________，第i列上所有元素之和等于顶点i的________。

5. 设哈夫曼树中共有n个结点，则该哈夫曼树中有________个度数为1的结点。

6. 设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d，则e和d的关系为_________。

7. __________遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、 中序或后序）。

9