武汉大学数据结构考试试题(附答案)(2)

一、选择题1. B 2. B 3. C 4. B 5．C 6．B 9．C 10．A 11．B 12. C 13. B 14. C 15. C 16. A 17. C 18. A 19. C

二、填空题1.复杂度 2． 物理结构 ， 逻辑结构 ，算法 , 原来的 3． q-next; 4.

4,3 5. 前驱 ， 后续 6． 线性结构 , 顺序结构 7. 5 8. 5 , 31 , 19 。 9. [38 46 56 79][40 84] 。10. (84,79,56,38,40,46) 。 三、问答题 1.答：共有14种可能的出栈序列为：ABCD, ABDC, ACBD, ACDB, BACD, ADCB, BADC, BCAD,BCDA,BDCA,CBAD,CBDA,CDBA,DCBA 2. 答： 显然能达到最大深度的是单支树其深度为n；深度最小的是完全k叉树。

3. 答： 用堆排序最好，因为堆排序不需要等整个排序结束就可挑出前10个最大元素，而快速排序和基数排序都需等待整个排序结束才能知道前10个最大元素。

1. 下面程序段的执行次数为（ A ）

for(i=0;i＜n-1;i++)

for(j=n;j＞i;j--)

state;

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

2. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ B ）A. 110 B .108 C. 100 D. 120

3. 一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（ C ）A. edcba B .decba C. dceab D. abcde

4. 循环队列用数组A[0,m－1]存放其元素值，已知其头尾指针分别是front和rear,则当前队列中的元素个数是（ D ）

A. (rear-front+m)%m B .read-front+1C. read-front-1 D. read-front

5．不带头结点的单链表head为空的判定条件是（ A ）A. head=NULL B .head-next=NULLC. head-next=head D. head!=NULL 6． 在一个单链表中，若p所指的结点不是最后结点，在p之后插入s所指结点，则执行（ B）A. s-next=p;p-next=s; B .s-next=p-next;p-next=s; C. s-next=p-next;p=s; D. p-next=s;s-next=p;

7. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较多少个结点（ D ）A. n B .n2 C. (n-1)2 D. (n+1)28．从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行( D )A. x=HS;HS=HS-next;B .x=HS-data;C. HS=HS-next;x=HS-data;D. x=HS-data;HS=HS-next; 9．串是一种特殊的线性表，其特殊性体现在( B )

A. 可以顺序存储 B .数据元素是一个字符C. 可以链接存储 D. 数据元素可以是多个字符11．二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的起始地址与M按列

存储时下列哪一元素的起始地址相同( B ) A. M[2][4] B .M[3][4] C. M[3][5] D. M[4][4]

12. 数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为( C )A. SA+144 B .SA+180 C. SA+222 D. SA+225

13. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为：( B )A. 2h B .2h-1 C. 2h+1 D. h+1

14. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是( D )A. acbed B .decab C. deabc D. cedba

15. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把 由树转化得到的二叉树叫做这棵树对应的二叉树。下列结论哪个正确( A )A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同

B .树的后根遍历序列与其对应的二叉树的后序遍历序列相同C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同

D. 以上都不对 16. 具有6个顶点的无向图至少应有多少条边才能确保是一个连通图( A )A. 5 B .6 C. 7 D. 8

17. 顺序查找法适合于存储结构为( B )的线性表 A. 散列存储 B .顺序存储或链接存储C. 压缩存储 D. 索引存储

18.采用顺序查找方法查找长度为n的线性表每个元素的平均查找长度为( C )A. n B .n2 C. (n+1)2 D. (n-1)2

19. 有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为( B )

A. 3512 B .3712 C. 3912 D. 4312

20.有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值82为的结点时，几次比较后查找成功（ C ）

二、填空题（每空1分，共20分）

1.在线性表的顺序存储中，元素之间的逻辑关系是通过物理存储位置，决定的；在线性表的链接存储中，元素之间的逻辑关系是通过链域的指针值决定的。2．对于一个具有N个结点的单链表，在已知的结点P后插入一个新结点的时间复杂度为O(1),在给定值为X的结点后插入一个新结点的时间复杂度为 O(N)。 3.有一空桟，现有输入序列1,2,3,4,5,经push,push,pop,push,pop,push,push后，输出序列为 2,3 。

4．在一个无向图中，所有顶点的度数之和等于所有边数的 2 倍 5.对于一棵具有n个结点的树，该树中所有结点的度数之和为 n-1。

6. 在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有 6个

7.在霍夫曼编码中，若编码长度只允许小于等于4，则除了已对两个字符编码为0和10外，还可以最多对 4 个字符编码。

8. 对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为 n 和 n-1 。

9. 对20个记录进行归并排序时，共需要进行 5 趟归并，在第三趟归并时是把长度为 4 的有序表两两归并为长度为 8 的有序表。

三、问答题 1. 简述下面算法的功能（栈和队列的元素类型均为int）

void algo3(Queue &Q){

Stack S; int d;

InitStack(S);

while(!QueueEmpty(Q)){

DeQueue(Q,d);Push(S,d);

}

while(!StackEmpty(S)){

Pop(S,d); EnQueue(Q,d);

}

}

算法的功能：利用栈作辅助，将队列中的数据元素进行逆置

2. 已知一棵二叉树的中序遍历序列和先序遍历序列为，试问能不能唯一确定一棵二叉树。若给定先序遍历序列和后序遍历序列，能不能唯一确定呢？

由中序遍历序列和先序遍历序列能唯一确定一棵二叉树。由先序遍历和后序遍历序列不能唯一确定一棵二叉树.。

一、选择题

1. 下面程序段的执行次数为（ ）

for(i=0;i＜n-1;i++)

for(j=n;j＞i;j--)

state;

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

2. 判定一个栈ST（最多元素为m0）为空的条件是：（ ）A. ST-top0 B .ST-top＝0C. ST-topm0 D. ST-top＝m0

3. 一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（ ）A. edcba B .decba C. dceab D. abcde

4. 在一个单链表中，若p所指的结点不是最后结点，在p之后插入s所指结点，则执行（ ）A. s-next=p;p-next=s;B .s-next=p-next;p-next=s;C. s-next=p-next;p=s;D. p-next=s;s-next=p; 5． 在一个链队中，假设f和r分别为队首和队尾指针，则删除一个 …… 此处隐藏：3611字，全部文档内容请下载后查看。喜欢就下载吧 ……