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

1、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. 1203. 一个栈的入栈序列是a,b,c,d,e ， 则栈的不可能的输出序列是( C ) A. edcba B .decba C.dceab D. abcde4. 循环队列用数组 A0,m 1存放其元素值，已知其头尾指针分别

2、是front和rear,则当前队列中的元素个数是( D )A. (rear-front+m)%m B .read-front+1C. read-front-1 D. read-front5不带头结点的单链表head 为空的判定条件是( A ) A. head=NULLB .head-next=NULLC. head-next=head D. head!=NULL6 在一个单链表中，若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;

3、 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. 数据元素可以是

4、多个字符11. 二维数组 M 的元素是 4 个字符(每个字符占一个存储单元)组成的串，行下标i 的范围从 0到 4，列下标j 的范围从 0 到 5 ， M 按行存储时元素M35 的起始地址与 M 按列存储时下列哪一元素的起始地址相同 ( B ) A. M24 B .M34 C. M35 D. M4412. 数组 A 中，每个元素A 的长度为 3 个字节，行下标 i 从 1 到 8，列下标j 从 1 到 10 ，从首地址 SA 开始连续存放在存储器内，该数组按行存放时，元素A85 的起始地址为( C )A.SA+144 B .SA+180 C. SA+222 D. SA+22513. 设高度为

5、h 的二叉树上只有度为 0 和度为 2 的结点， 则此类二叉树中所包含的结点数至少为：( B )A. 2h B .2h-1 C. 2h+1 D. h+114. 已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是( D )A. acbed B .decab C. deabc D. cedba15. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把 由树转化得到的二叉树叫做这棵树对应的二叉树。下列结论哪个正确 ( A )A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同B . 树的后根遍历序列与其

6、对应的二叉树的后序遍历序列相同 C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同D. 以上都不对 16. 具有 6 个顶点的无向图至少应有多少条边才能确保是一个连通图( A )A. 5 B .6 C. 7 D. 817 . 顺序查找法适合于存储结构为( B )的线性表A. 散列存储 B . 顺序存储或链接存储 C.压缩存储 D. 索引存储B .n2C.18 .采用顺序查找方法查找长度为 n 的线性表每个元素的平均查找长度为( C )A. n(n+1)2 D. (n-1)219 . 有一个长度为12 的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数

7、为 ( B )A. 3512 B .3712 C. 3912 D. 431220 .有一个有序表为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

8、.有一空栈，现有输入序列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 条边的连通图，其生成树中的顶

9、点数和边数分别为 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. 已知一棵二叉树的中序遍历序列和先序

10、遍历序列为，试问能不能唯一确定一棵二叉树。若给定先序遍历序列和后序遍历序列，能不能唯一确定呢？由中序遍历序列和先序遍历序列能唯一确定一棵二叉树。 由先序遍历和后序遍历序列不能唯一确定一棵二叉树.。一、选择题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)A. ST-top0 B .ST-top =0C.2. 判定一个栈ST (最多元素为m0 )为空的条件是：(ST-topm0 D. ST-top = m03. 一个栈

11、的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是()A. edcba B .decba C.dceab D. abcde4. 在一个单链表中，若 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 分别为队首和队尾指针，则删除一个结点的运算时( )A. r=f-next; B .r=r-next; C. f=f-next;D. f=r-next;6 串是一种

12、特殊的线性表， 其特殊性体现在()A. 可以顺序存储 B . 数据元素是一个字符C. 可以链接存储D. 数据元素可以是多个字符7.稀疏矩阵一般的压缩方法有两种， 即 () A. 二维数组和三维数组 B . 三元组和散列 C. 三元组和十字链表D. 散列和十字链表8 将递归算法转换成对应的非递归算法时，通常需要使用()A. 栈 B .队列 C. 链表 D. 树 9二维数组 M 的元素是 4 个字符(每个字符占一个存储单元)组成的串，行下标i 的范围从 0 到 4，列下标j 的范围从 0 到 5， M 按行存储时元素 M35 的起始地址与 M 按列存储时下列哪一元素的起始地址相同 ()A. M24

13、B .M34 C. M35 D. M4410. 数组 A 中，每个元素A 的长度为 3 个字节，行下标 i 从 1 到 8，列下标j 从 1 到 10，从首地址SA 开始连续存放在存储器内，该数组按行存放时，元素 A85 的起始地址为 ()A. SA+144 B .SA+180 C. SA+222 D. SA+22511.如果 T2 是由有序树 T 转换而来的二叉树，那么 T 中结点的后序就是T2 中结点的 ()A. 前序 B . 中序 C. 后序D. 层次序 12. 一个有 n 个顶点的无向图最多有多少边()A. n B .n(n-1) C. n(n-1)2 D. 2n13.按照二叉树的定义

14、， 具有 3 个结点的二叉树有()种 A. 3 B .4 C. 5 D. 614.在一非空二叉树的中序遍历序列中，根结点的右边()A. 只有右子树上的所有结点 B .只有右子树上的部分结点 C. 只有左子树上的部分结点 D. 只有左子树上的所有结点15. 在一个图中，所有顶点的度数之和等于所有边数的多少倍 ()A. 12 B .1 C. 2 D.416. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的 ()A. 先序遍历B . 中序遍历 C. 后序遍历D. 按层遍历17. 采用顺序查找方法查找长度为 n 的线性表每个元素的平均查找长度为 ()A. n B .n2C. (n+1)2 D. (

15、n-1)2二、填空题 1. 算法的计算量的大小称为计算的 _。2 数据结构是研究数据的 和 以及他们之间的相互关系， 并对这种结构定义相应的运算,设计出相应的 ,而确保经过这些运算后所得的新结构是 结构类型。3在一个单链表中删除p 结点，应执行下列操作：q=p-next;p-data=p-next-data;p-next=;free(q);4.有一空栈，现有输入序列5,4,3,2,1，经 push,push,pop,push,pop,push,push 后，输出序列为。结点，另一个指向,存储结构是7.对于一棵含有5在双向链表中每个结点包含两个指针域，一个指向 结点。6一维数组的逻辑结构是40

16、个结点的理想平衡树，它的高度为8.假定对长度n= 50的有序表进行折半搜索，则对应的判定树高度为，判定树中前5层的结点数为 ,最后一层的结点数为 。9. 假定一组记录的排序码为( 46 ， 79 ，56 ， 38 ， 40 ，80 ) ， 对其进行归并排序的过程中， 第二趟归并后的结果为 。10. 假定一组记录的排序码为( 46， 79 ， 56 ， 38， 40 ， 80)，对其进行快速排序的一次划分的结果为 。三、简答题 1.假定有四个元素A,B,C,D 依次进栈，进栈过程中允许出栈，试写出所有可能的出栈序列？2.一棵含有n 个结点的 k 叉树，可能达到的最大深度和最小深度各为多少？ 3.

17、 设有5000 个无序的元素，希望用最快速度挑选出其中前10 个最大的元素，在以下的排序方法中，采用哪种方法最好？为什么？(快速排序，堆排序，基数排序)1、 选择题 1. B 2. B 3. C 4. B 5 C 6 B9 C 10 A 11 B 12. C 13. B 14.C15. C16. A17. C18.A 19.C2、 填空题1.复杂度 2物理结构， 逻辑结构， 算法 , 原来的 3q-next; 4. 4,35.前驱 ， 后续 6 线性结构, 顺序结构7. 58. 5,3119。9.38 46 56 7940 84。 10.(84,79,56,38,40,46)。三、问答题1.答

18、：共有14 种可能的出栈序列为： ABCD, ABDC, ACBD, ACDB, BACD, ADCB,BADC, BCAD,BCDA,BDCA,CBAD,CBDA,CDBA,DCBA2. 答： 显然能达到最大深度的是单支树其深度为 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)

19、2 C. n(n+1)2 D. (n-1)(n+2)2. 一个向量第一个元素的存储地址是100 ， 每个元素的长度为2， 则第 5 个元素的地址是( B )A. 110 B .108 C. 100 D. 1203. 一个栈的入栈序列是a,b,c,d,e ，则栈的不可能的输出序列是( C ) A. edcba B .decba C.dceab D. abcde4. 循环队列用数组A0,m 1存放其元素值，已知其头尾指针分别是front和rear,则当前队列中的元素个数是( D )A. (rear-front+m)%m B .read-front+1C. read-front-1 D. read-

20、front5不带头结点的单链表head 为空的判定条件是( A ) A. head=NULLB .head-next=NULLC. head-next=head D. head!=NULL6 在一个单链表中，若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

21、 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 按行存储时元素M35

22、 的起始地址与 M 按列存储时下列哪一元素的起始地址相同 ( B ) A. M24 B .M34 C. M35 D. M4412. 数组 A 中，每个元素A 的长度为 3 个字节，行下标 i 从 1 到 8，列下标j 从 1 到 10 ，从首地址 SA 开始连续存放在存储器内，该数组按行存放时，元素A85 的起始地址为( C )A.SA+144 B .SA+180 C. SA+222 D. SA+22513. 设高度为 h 的二叉树上只有度为 0 和度为 2 的结点， 则此类二叉树中所包含的结点数至少为： ( B )A. 2h B .2h-1 C. 2h+1 D. h+114. 已知某二叉树的

23、后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是( D )A. acbed B .decab C. deabc D. cedba15. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把 由树转化得到的二叉树叫做这棵树对应的二叉树。下列结论哪个正确 ( A )A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同B . 树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C. 树的先根遍历序列与其对应的 二叉树的中序遍历序列相同D. 以上都不对 16. 具有 6 个顶点的无向图至少应有多少条边才能确保是一个连通

24、图( A )A. 5 B .6 C. 7 D. 817 . 顺序查找法适合于存储结构为( B)的线性表A. 散列存储 B . 顺序存储或链接存储 C.压缩存储 D. 索引存储18 .采用顺序查找方法查找长度为 n 的线性表每个元素的平均查找长度为( C )A. n B .n2 C.(n+1)2 D. (n-1)219 . 有一个长度为12 的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为 ( B )A. 3512 B .3712 C. 3912 D. 431220 .有一个有序表为 1 ， 3， 9， 12， 32， 41 ， 45， 62， 75，

25、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在一个无向图中，所有顶点的

26、度数之和等于所有边数的 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 的有序表。三、问答

27、题 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. 已知一棵二叉树的中序遍历序列和先序遍历序列为，试问能不能唯一确定一棵二叉树。若给定先序遍历序列和后序遍历序列，能不能唯一确定呢？由中序遍历序列和先序遍历序列能唯一确定一棵二叉树。 由先序遍历和后序遍历序

28、列不能唯一确定一棵二叉树.。一、选择题 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 = m03. 一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是()A. edcba B .decba C.dceab D. abcde4. 在一个单链表中，若 p 所指

29、的结点不是最后结点，在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 分别为队首和队尾指针，则删除一个结点的运算时( )A. r=f-next; B .r=r-next; C. f=f-next;D. f=r-next;6 串是一种特殊的线性表， 其特殊性体现在()A. 可以顺序存储 B . 数据元素是一个字符C. 可以链接存储D. 数据元素可以是多个字符7.稀疏矩阵一般的压缩方法有两种，

30、即 () A. 二维数组和三维数组 B . 三元组和散列 C. 三元组和十字链表D. 散列和十字链表8将递归算法转换成对应的非递归算法时，通常需要使用()A. 栈 B .队列 C. 链表 D. 树9二维数组M 的元素是 4 个字符(每个字符占一个存储单元)组成的串，行下标i 的范围从 0 到 4，列下标j 的范围从 0 到 5， M 按行存储时元素 M35 的起始地址与 M 按列存储时下列哪一元素的起始地址相同 ()A. M24B .M34 C. M35 D. M4410. 数组 A 中，每个元素A 的长度为 3 个字节，行下标 i 从 1 到 8，列下标j 从 1 到 10，从首地址 SA

31、开始连续存放在存储器内，该数组按行存放时，元素 A85 的起始地址为 ()A. SA+144 B .SA+180 C. SA+222 D. SA+22511.如果 T2 是由有序树 T 转换而来的二叉树，那么 T 中结点的后序就是T2 中结点的 ()A. 前序 B . 中序 C. 后序D. 层次序 12. 一个有 n 个顶点的无向图最多有多少边()A. n B .n(n-1) C. n(n-1)2 D. 2n13.按照二叉树的定义，具有 3 个结点的二叉树有()种 A. 3 B .4 C. 5 D. 614.在一非空二叉树的中序遍历序列中，根结点的右边()A. 只有右子树上的所有结点 B .只有右子树上的部分结点 C. 只有左子树上的部分结点 D. 只有左子树上的所有结点15 . 在一个图中，所有顶点的度数之和等于所有边数的多少倍 ()A. 12 B .1 C. 2 D.416 .采用邻接表存储的图的深度优先遍历算法类似于二叉树的()A. 先序遍历B . 中序遍历 C. 后序遍历D. 按层遍历17 .采用顺序查找方法查找长度为n 的线性表每个元素的平均查找长度为 ()A. n B .n2C. (n+1)2 D. (n-1)2二、填空题 1. 算法的计算量的大小称为计算的 _。2 数据结构是研究数据的 和 以及他们之间的相互