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

1、1. 下面程序段的执行次数为(A )for(i=0;i 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. edcbaB .decba C. dceab D. abcde4. 循环队列用数组A0,m 1存放其元素值，已知其头尾指针分别是front 和 rear, 则当前队列中的元素个数是(

2、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; D.p-n

3、ext=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. 可以链

4、接存储D. 数据元素可以是多个字符11二维数组M的元素是4 个字符(每个字符占一个存储单元)组成的串，行下标i 的范围从 0 到 4， 列下标 j 的范围从0 到 5， M按行存储时元素M35 的起始地址与M按列存储时下列哪一元素的起始地址相同( B ) A. M24 B .M34 C. M35D. 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 的二叉

5、树上只有度为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. 索引存储18. 采用顺序查找方法查找长度为n 的线性表每个元素的平均查找长度为( C )A. n B .n2C. (n+1)2 D. (n-1)219. 有一个长度为12 的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为( B

7、)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 个字符编码。4，则除了已对两个字符编码为0 和 10 外，8. 对于一个具有n 个顶点和e 条边的连通图，其生成树中的顶点数和边数分别为n和 n-1。9. 对 20

9、个记录进行归并排序时，共需要进行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 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. edcbaB .decba C. dceab D.

11、 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串是一种特殊的线性表，其特殊性体现在() A. 可以顺序存储B . 数据元素是一个字符C. 可以链接存储D. 数据元素可以是多个字符7

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

13、开始连续存放在存储器内，该数组按行存放时，元素A85 的起始地址为 ()A.SA+144 B .SA+180 C. SA+222 D. SA+22511.如果 T2是由有序树 T转换而来的二叉树，那么T中结点的后序就是T2中结点的()A. 前序 B .中序 C. 后序 D. 层次序 12. 一个有 n 个顶点的无向图最多有多少边( )A. nB .n(n-1) C. n(n-1)2 D. 2n13. 按照二叉树的定义，具有 3 个结点的二叉树有( ) 种 A. 3 B .4 C. 5 D.6 14. 在一非空二叉树的中序遍历序列中，根结点的右边( )A. 只有右子树上的所有结点 B . 只有右

14、子树上的部分结点C. 只有左子树上的部分结点D. 只有左子树上的所有结点15. 在一个图中，所有顶点的度数之和等于所有边数的多少倍( )A.12 B .1 C. 2D. 416. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的( )A. 先序遍历B . 中序遍历C. 后序遍历D. 按层遍历17. 采用顺序查找方法查找长度为n 的线性表每个元素的平均查找长度为( )A. nB .n2 C. (n+1)2 D. (n-1)2二、填空题1. 算法的计算量的大小称为计算的 。2 数据结构是研究数据的和以及他们之间的相互关系，并对这种结构定义相应的运算, 设计出相应的, 而确保经过这些运算后所得的新

15、结构是结构类型。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 后，输出序列为。5在双向链表中每个结点包含两个指针域，一个指向结点，另一个指向结点。6一维数组的逻辑结构是,存储结构是。 7. 对于一棵含有 40 个结点的理想平衡树，它的高度为 。8. 假定对长度n 50 的有序表进行折半搜索，则对应的判定树高度为, 判定树中前5 层的结点数为, 最后一层的结点数为。9. 假定一组记录的排序

16、码为(46， 79， 56， 38， 40， 80) ，对其进行归并排序的过程中，第二趟归并后的结果为。 10. 假定一组记录的排序码为(46， 79， 56， 38， 40， 80) ，对其进行快速排序的一次划分的结果为。三、简答题1. 假定有四个元素A,B,C,D 依次进栈，进栈过程中允许出栈，试写出所有可能的出栈序列？2. 一棵含有n 个结点的k叉树， 可能达到的最大深度和最小深度各为多少？3.设有 5000 个无序的元素，希望用最快速度挑选出其中前10 个最大的元素，在以下的排序方法中，采用哪种方法最好？为什么？(快速排序，堆排序，基数排序)一、选择题1. B 2. B 3. C 4.

17、 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逻辑结构，算法 , 原来的 3 q-next;线性结构,顺序结构7. 5 8.9.38 46 56 7940 84。 10.二、填空题1. 复杂度2 物理结构4 . 4,3 5. 前驱 ， 后续 65 ,31,19(84,79,56,38,40,46)。三、 问答题 1. 答： 共有 14 种可能的出栈序列为：ABCD, ABDC, ACBD, ACDB, BACD, ADCB, BADC,BCAD,BCDA,BDCA,CBAD,CBDA,CDBA,DC

18、BA 2.答：显然能达到最大深度的是单支树其深度为 n；深度最小的是完全k 叉树。3. 答： 用堆排序最好，因为堆排序不需要等整个排序结束就可挑出前10 个最大元素，而快速排序和基数排序都需等待整个排序结束才能知道前10 个最大元素。1. 下面程序段的执行次数为(A )for(i=0;i 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,

19、d,e ，则栈的不可能的输出序列是(C ) A. edcbaB .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-front5 不 带 头 结 点 的 单 链 表 head 为 空 的 判 定 条 件 是 ( A ) A. head=NULL B .head-next=NULLC. head-next=head D. head!=NULL6 在一个单链表中

20、，若 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-n

21、ext;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 的起始地址与M按列存储时下列哪一元素的起始地址相同( B ) A. M24 B .M34 C. M35D. M4412. 数组A中，每个元素A的长度为3个字节，行下标i 从

22、 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. 已知某二叉树的后序遍历序列是dabec， 中序遍历序列是debac， 它的前序遍历序列是( D )A. acbed B .decab C. deabc D. cedba15. 树的基本遍历策略可分为先根遍历和后根遍历

23、；二叉树的基本遍历策略可分为先序遍历、 中序遍历和后序遍历。这里， 我们把 由树转化得到的二叉树叫做这棵树对应的二叉树。下列结论哪个正确( A )A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同B . 树的后根遍历序列与其对应的二叉树的后序遍历序列相同C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同D. 以上都不对16. 具有 6 个顶点的无向图至少应有多少条边才能确保是一个连通图( A )A. 5 B .6 C. 7 D. 817. 顺序查找法适合于存储结构为( B ) 的线性表A. 散列存储B . 顺序存储或链接存储 C. 压缩存储D. 索引存储18. 采用顺序查找方法查找

24、长度为n 的线性表每个元素的平均查找长度为( C )A. n B .n2C. (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，77，82，95，100，当二分查找值 82 为的结点时，几次比较后查找成功(C )二、填空题(每空1 分，共 20 分)1. 在线性表的顺序存储中，元素之间的逻辑关系是通过物理存储位置，决定的；在线性表的链接存储中，元素

25、之间的逻辑关系是通过链域的指针值决定的。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. 在霍夫

26、曼编码中，若编码长度只允许小于等于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(!Stac

27、kEmpty(S)Pop(S,d); EnQueue(Q,d);算法的功能：利用栈作辅助，将队列中的数据元素进行逆置2. 已知一棵二叉树的中序遍历序列和先序遍历序列为，试问能不能唯一确定一棵二叉树。 若给定先序遍历序列和后序遍历序列，能不能唯一确定呢？由中序遍历序列和先序遍历序列能唯一确定一棵二叉树。由先序遍历和后序遍历序列不能唯一确定一棵二叉树. 。一、选择题1. 下面程序段的执行次数为()for(i=0;i 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

28、. ST-top0 B .ST-top 0C.ST-topm0 D. ST-top m03. 一个栈的入栈序列是a,b,c,d,e ，则栈的不可能的输出序列是() A. edcbaB .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-ne

29、xt; B .r=r-next; C. f=f-next;D. f=r-next;6串是一种特殊的线性表，其特殊性体现在() 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

30、 的起始地址与M按列存储时下列哪一元素的起始地址相同()A. M24 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. nB .n(n-1) C. n(n-1)

31、2 D. 2n13. 按照二叉树的定义，具有 3 个结点的二叉树有( ) 种 A. 3 B .4 C. 5 D.6 14. 在一非空二叉树的中序遍历序列中，根结点的右边( )A. 只有右子树上的所有结点 B . 只有右子树上的部分结点C. 只有左子树上的部分结点D. 只有左子树上的所有结点15. 在一个图中，所有顶点的度数之和等于所有边数的多少倍( )A.12 B .1 C. 2D. 416. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的( )A. 先序遍历B . 中序遍历C. 后序遍历D. 按层遍历17. 采用顺序查找方法查找长度为n 的线性表每个元素的平均查找长度为( )A. nB .n2 C. (n+1)2 D. (n-1)2二、填空题1. 算法的计算量的大小称为计算的以及他们之间的相互关系，并对这而确保经过这些运算后所得