智慧树知到答案数据结构最新答案

第三章 单元测试

1、单选题：
若让元素C，h，i，n，a依次进栈，则出栈次序不可能出现在（ ）种情况。
选项：
A:h，i，a，n，C

B:h，C，a，n，i

C:n，i，C，h，a
D:a，n，i，h，C
答案: 【】

2、单选题：
若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（ ）。
选项：
A:不确定

B:i
C:n-i
D:n-i+1
答案: 【

3、单选题：
设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。
选项：
A:栈

B:线性表的顺序存储结构
C:线性表的链式存储结构
D:队列

答案: 【
】

4、单选题：
若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈（i=1,2）栈顶，栈1的底在V[1]，栈2的底在V[m]，则栈满的条件是（ ）
选项：
A:top[1]+1= top[2]

B:|top[2]-top[1]|=0

C:top[1]+ top[2]=m

D:top[1] = top[2]

答案: 【
】

5、单选题：
为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。
选项：
A:线性表
B:栈
C:有序表

D:队列
答案: 【】

6、单选题：
用链接方式存储的队列，在进行删除运算时( )。
选项：
A:仅修改头指针

B:头、尾指针都要修改

C:头、尾指针可能都要修改

D:仅修改尾指针
答案: 【
】

7、单选题：
栈和队列的共同点是（ ）。
选项：
A:都是先进先出
B:都是先进后出

C:只允许在端点处插入和删除元素
D:没有共同点

答案: 【】

8、单选题：
设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（ ）。
选项：
A:4
B:2
C:6

D:3
答案: 【】

9、单选题：
循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。
选项：
A:rear=rear+1
B:rear=(rear+1)%(m-1)

C:rear=(rear+1)%(m+1)

D:rear=(rear+1)%m
答案: 【
】

10、单选题：
递归过程或者函数调用时处理参数和返回地址需要用到（ ）数据结构。
选项：
A:栈

B:线性表

C:二叉树

D:队列

答案: 【
】

第四章 单元测试

1、单选题：
串是一种特殊的线性表，其特殊性体现在（ ）。
选项：
A:数据元素是一个字符

B:可以链式存储
C:数据元素可以是多个字符若

D:可以顺序存储
答案: 【
】

2、单选题：
若串S=“master”其子串的个数是（ ）。
选项：
A:21
B:22
C:23

D:20
答案: 【】

3、单选题：
串的长度是指（ ）。
选项：
A:串中所含字符的个数

B:串中所含不同字符的个数
C:串中所含不同字母的个数
D:串中所含非空格字符的个数
.

答案: 【
】

4、单选题：
设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）。
选项：
A:求串长

B:匹配

C:联接

D:求子串

答案: 【
】

5、单选题：
数组A[0..4,-1..-3,5..7]中含有元素的个数（ ）。
选项：
A:55
B:45
C:36
D:16

答案: 【】

6、单选题：
假设以行序为主序存储二维数组A=array[1..100,1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]=（ ）。
选项：
A:1010
B:818
C:808
D:1020

答案: 【】

7、单选题：
设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为（ ）。
选项：
A:BA+225

B:BA+141
C:BA+222
D:BA+180
答案: 【

8、单选题：
设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。
选项：
A:32
B:33
C:13
D:40

答案: 【】

9、单选题：
广义表((a,b,c,d))的表头是（ ）。
选项：
A:(a,b,c,d)
B:( b,c)
C:(b,c,d)

D:a
答案: 【】

10、单选题：
广义表A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))的值为（ ）。
选项：
A:d

B:c
C:(g)
D:(d)
答案: 【
】

第五章 单元测试

1、单选题：
由3个结点可以构造出多少种不同的二叉树？（ ）
选项：
A:3
B:2
C:4
D:5

答案: 【

2、单选题：
一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）。
选项：
A:254
B:500
C:250
D:501

答案: 【
】

3、单选题：
一个具有1025个结点的二叉树的高h为（ ）。
选项：
A:10至1024之间

B:11至1025之间
C:10
D:11
答案: 【】

4、单选题：
对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（ ）遍历实现编号。
选项：
A:先序
B:中序
C:从根开始按层次遍历

D:后序
答案: 【】

5、单选题：
已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（ ）。
选项：
A:CBEFDA
B:FEDCBA
C:不确定

D:CBEDFA
答案: 【】

6、单选题：
引入二叉线索树的目的是（ ）。
选项：
A:加快查找结点的前驱或后继的速度

B:为了能方便的找到双亲
D使二叉树的遍历结果唯一

C:为了能在二叉树中方便的进行插入与删除

答案: 【
】

7、单选题：
在下列存储形式中，（ ）不是树的存储形式？
选项：
A:双亲表示法
B:顺序存储表示法

C:孩子链表表示法

D:孩子兄弟表示法
答案: 【
】

8、单选题：
利用二叉链表存储树，则根结点的右指针是（ ）。
选项：
A:指向最左孩子
B:非空

C:指向最右孩子
D:空
答案: 【】

9、单选题：
设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。
选项：
A:n
B:n + 2

C:n + 1
D:n−1
答案: 【】

10、单选题：
设哈夫曼树中有199个结点，则该哈夫曼树中有（ ）个叶子结点。
选项：
A:101
B:102

C:99
D:100

答案: 【
】

第六章 单元测试

1、单选题：
具有4个顶点的无向完全图有（ ）条边。
选项：
A:6
B:16
C:12
D:20

答案: 【】

2、单选题：
具有6个顶点的无向图至少应有（ ）条边才能确保是一个连通图。
选项：
A:7
B:6
C:8

D:5
答案: 【】

3、单选题：
在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。
选项：
A:1
B:1/2
C:2
D:4

答案: 【】

4、单选题：
任何一个无向连通图的最小生成树（ ）。
选项：
A:可能不存在

B:只有一棵
C:有一棵或多棵
D:一定有多棵
答案: 【】

5、单选题：
设无向图G=（V，E），G’=（V’，E’），如果G’是G的生成树，则下面说法错误的是（ ）。
选项：
A:G’为G的无环子图

B:G’为G的连通分量

C:G’为G的子图
D:G’为G的极小连通子图，且V’=V
答案: 【
】

6、判断题：
无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定不是对称矩阵。（ ）
选项：
A:对
B:错
答案: 【】

7、单选题：
某无向图G=（V，E），其中：V=（a,b,c,d,e,f），E=（(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)），对该图进行深度优先遍历，则顶点序列正确的是（ ）。
选项：
A:a,e,b,c,f,d
B:a,c,f,e,b,d
C:a,b,e,c,d,f
D:a,e,d,f,c,b

答案: 【
】

8、单选题：
已知有向图G=(V,E)，其中V={v1,v2,v3,v4,v5,v6},E={＜v1,v2＞,＜v1,v4＞,＜v2,v6＞,
＜v3,v1＞,＜v3,v4＞,＜v4,v5＞,＜v5,v2＞,＜v5,v6＞},G的拓扑序列是（ ）。
选项：
A:v1,v3,v4,v5,v2,v6
B:v3,v4,v1,v5,v2,v6

C:v3,v1,v4,v5,v2,v6
D:v1,v4,v3,v5,v2,v6

答案: 【】

9、单选题：
关键路径是事件结点网络中（ ）。
选项：
A:从源点到汇点的最短路径
B:最短的回路

C:最长的回路
D:从源点到汇点的最长路径

答案: 【
】

10、单选题：
普里姆算法是一种通过选点法构造最小生成树的算法。时间复杂度为（ ）。
选项：
A:O（eloge）
B:O（n^2）
C:O（n+e）
D:O（e^2）

答案:

第七章 单元测试

1、单选题：
有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素等概率的情况下查找成功所需的平均比较次数为（ ）。
选项：
A:39/12
B:35/12

C:43/12

D:37/12
答案: 【

2、单选题：
对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ ）个，
选项：
A:1
B:2
C:3
D:4

答案: 【4
】

3、单选题：
顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（ ）。
选项：
A:O(n)
B:O(n^(1/2))
C:O(n^2)
D:O(1og2n)

答案: 【

4、单选题：
设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（ ）。
选项：
A:1
B:2
C:4

D:3
答案: 【2】

5、单选题：
设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（ ）。
选项：
A:99

B:91
C:93
D:97
答案: 【】

6、单选题：
设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为（ ）。
选项：
A:4
B:7

C:5
D:6
答案: 【】

7、单选题：
二叉排序树中左子树上所有结点的值均（ ）根结点的值。
选项：
A:!=

B:＞
C:＜
D:=
答案: 【】

8、单选题：
从n个结点的二叉排序树中查找一个元素时，最坏情况下时间复杂度为（ ）。
选项：
A:O(n)
B:O(1og2n)

C:O(n^(1/2))
D:O(n^2)
答案: 【】

9、单选题：
在平衡二叉树中，每个结点平衡因子的绝对值必须（ ）。
选项：
A:小于1
B:小于等于1
C:等于0
D:大于1

答案: 【】

10、单选题：
深度为4的平衡二叉树中至少有（ ）个结点。
选项：
A:10
B:8
C:7
D:6

答案: 【】

第八章 单元测试

1、单选题：
用某种排序方法对线性表{25,84,21,47,15,27,68,35,20}进行排序时，元素序列的变化情况如下：
（1）25，84，21，47，15，27，68，35，20
（2）20，15，21，25，47，27，68，35，84
（3）15，20，21，25，35，27，47，68，84
（4）15，20，21，25，27，35，47，68，84
则采用的排序方法是（ ）。
选项：
A:希尔排序

B:快速排序

C:归并排序
D:直接选择排序
答案: 【
】

2、单选题：
对记录的关键字为｛51,26,38,80,70,90,8,30,40,20｝进行排序，各趟排序结束时的结果为：
（1）51，26，38，80，70，90，8，30，40，20
（2）51，8，30，40，20，90，26，38，80，70
（3）26，8，30，40，20，80，51，38，90，70
（4）8，20，26，30，38，40，51，70，80，90
则采用的排序方法是（ ）。
选项：
A:快速排序

B:归并排序
C:直接选择排序

D:希尔排序
答案: 【】

3、单选题：
设一组初始记录关键字序列(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

答案: 【】

4、单选题：
下列四种排序中（ ）的空间复杂度最大。
选项：
A:冒泡排序
B:插入排序
C:归并排序

D:堆排序
答案: 【
】

5、单选题：
快速排序的空间复杂度为（ ）。
选项：
A:O(log2n)
B:O(n)
C:O(n^2)
D:O(n^3)

答案: 【】

6、单选题：
下面哪种排序算法是稳定的排序算法（ ）。
选项：
A:希尔排序
B:归并排序

C:直接选择排序
D:快速排序
答案: 【
】

7、单选题：
下面哪种排序算法的时间复杂度为O(nlog2n)。（ ）
选项：
A:快速排序
B:冒泡排序
C:直接插入排序
D:直接选择排序

答案: 【】

8、单选题：
设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（ ）。
选项：
A:15，25，35，50，80，20，36，40，70，85

B:15，25，35，50，80，20，85，40，70，36

C:15，25，35，50，20，40，80，85，36，70

D:15，25，35，50，80，85，20，36，40，70

答案: 【
】

9、单选题：
利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（ ）。
选项：
A:O(nlog2n)
B:O(n^2)
C:O(n)
D:O(log2n)

答案: 【】

10、单选题：
设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是（ ）。
选项：
A:F，H，C，D，P，A，M，Q，R，S，Y，X

B:A，D，C，R，F，Q，M，S，Y，P，H，X

C:H，C，Q，P，A，M，S，R，D，F，X，Y

D:P，A，C，S，Q，D，F，X，R，H，M，Y

答案: 【
】