智慧树知到答案数据结构与算法（仲恺农业工程学院）最新答案

第三章 单元测试

1、单选题：
设有一顺序栈S，元素s1,s2,s3,s4,s5,s6 依次进栈，如果6个元素出栈的顺序是s2,s4,s3,s6,s5,s1，则栈的容量至少应该是
选项：
A:5
B:3
C:2
D:4
答案:

2、单选题：
一个栈的入栈序列是1，2，3，4，5，则栈的不可能输出序列是
选项：
A:1,2,3,4,5
B:3,5,4,2,1
C:3,2,4,5,1
D:5,4,3,1,2
答案:

3、单选题：
一个队列的入队序列是1，3，5，7，9，则出队的输出序列只能是
选项：
A:9,5,1,7,3
B:1,5,9,3,7
C:9,7,5,3,1
D:1,3,5,7,9
答案:

4、单选题：
设循环队列中数组的下标范围是1～n，其头尾指针分别为f和r，则其元素个数为
选项：
A:r-f
B:(r-f+n)%n
C:(r-f)%n+1
D:r-f+1
答案:

5、单选题：
设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行入队操作后其尾指针rear值为
选项：
A:rear=rear+1
B:rear=(rear-1)%m
C:rear=(rear+1)%m
D:rear=(rear+1)%(m-1)
答案:

6、单选题：
递归过程或函数调用时，处理参数及返回地址，使用的数据结构是
选项：
A:栈
B:多维数组
C:线性表
D:队列
答案:

7、单选题：
栈中元素的进出原则是
选项：
A:栈空则进
B:先进先出
C:后进先出
D:栈满则出
答案:

8、单选题：
判定一个栈ST（最多元素为m0）为空的条件是
选项：
A:ST->top==0
B:ST->top0
C:ST->top==m0
D:ST->topm0
答案:

9、单选题：
判定一个队列QU（最多元素为m0）为满队列的条件是
选项：
A:QU->rear － QU->front －1= = m0
B:QU->rear － QU->front = = m0
C:QU->front = = QU->rear
D:QU->front = = QU->rear +1
答案:

10、单选题：
在一个链式队列中.假设f和r分别为队头和队尾指针,则插入s所指的结点运算是
选项：
A:r->next=s;r=s;
B:s->next=s;r=s;
C:s->next=f;f=s;
D:f->next=s;f=s;
答案:

11、单选题：
向一个栈指针为HS的链式栈中插入一个s所指的结点时,则执行
选项：
A: S->NEXT=HS;HS=HS->NEXT;
B:HS->NEXT=S;
C:S->NEXT=HS->NEXT;HS->NEXT=S;
答案:

12、单选题：
设一个栈的输入序列是1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（ ）。
选项：
A:43 1 25
B:5 1 23 4
C:45 1 32
D:3 2 15 4
答案:

13、单选题：
进栈序列为a，b，c，则通过入、出栈可能得到的a，b，c的不同排列个数是（）。
选项：
A:5
B:7
C:6
D:4
答案:

14、单选题：
表达式a*(b+c)-d 的后缀表达式是( )。
选项：
A:-+*abcd
B:abcd*+-
C:abc*+d-
D:abc+*d-
答案:

15、单选题：
设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。
选项：
A:线性表的顺序存储结构
B:线性表的链式存储结构
C:队列
D:栈
答案:

16、单选题：
用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( )。
选项：
A:仅修改队头指针
B:队头、队尾指针都要修改
C:队头、队尾指针都可能要修改
D:仅修改队尾指针
答案:

17、单选题：
假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（）。
选项：
A:(rear-front+m)%m
B:rear-front+1
C:(front-rear+m)%m
D:(rear-front)%m
答案:

18、单选题：
循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是(  )。
选项：
A:rear-front+1
B:rear-front-1
C:rear-front
D:(rear-front+m)%m
答案:

19、单选题：
若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？()
选项：
A:2和4
B:4和2
C:1 和5
D:5 和1
答案:

20、单选题：
栈和队都是（）。
选项：
A:限制存取点的非线性结构
B:顺序存储的线性结构
C:链式存储的非线性结构
D:限制存取点的线性结构
答案:

21、单选题：
栈的操作原则是（ ）。
选项：
A:后进先出
B:后进后出
C:顺序进出
D:先进先出
答案:

22、单选题：
下面术语中，与数据的存储结构无关的是（ ）。
选项：
A:顺序表
B:循环队列
C:顺序栈
D:栈
答案:

23、单选题：
栈和队列具有相同的（ ）。
选项：
A:存储结构
B:逻辑结构
C:运算
D:抽象数据类型
答案:

24、单选题：
递归算法必须包括（ ）。
选项：
A:迭代部分
B:终止条件和递归部分
C:递归部分
D:终止条件和迭代部分
答案:

第四章 单元测试

1、单选题：
串s=”ABC DEF”的串长度为
选项：
A:7
B:4
C:8
D:3
答案:

2、单选题：
设有串s=”ABCBBCBBCBBA”和串t=”CB”，则串t在s中的匹配位置是
选项：
A:3
B:9
C:1
D:6
答案:

3、单选题：
串是
选项：
A:不少于一个字符的序列
B:任意个字母的序列
C:不少于一个字母的序列
D:有限个字符的序列
答案:

4、单选题：
设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为
选项：
A:匹配
B:联接
C:求子串
D:求串长
答案:

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

6、单选题：
设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为
选项：
A:i(i-l)/2+j-1
B:j(j-l)/2+i
C:i(i-l)/2+j
D:j(j-l)/2+i-1
答案:

7、单选题：
对稀疏矩阵进行压缩存储目的是
选项：
A:便于输入和输出
B:降低运算的时间复杂度
C:便于进行矩阵运算
D:节省存储空间
答案:

8、单选题：
有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是
选项：
A:180
B:60
C:66
D:33
答案:

9、单选题：
广义表（a,(b,c),d,e）的表头为
选项：
A:(a,(b,c))
B:a
C:a,(b,c)
D:(a)
答案:

10、单选题：
下面说法不正确的是
选项：
A:广义表可以是一个递归表
B:广义表可以是一个多层次的结构
C:广义表难以用顺序存储结构
D:广义表至少有一个元素
答案:

11、单选题：
设广义表L=（（a,b,c）），则L的长度和深度分别为
选项：
A:2和3
B:1和2
C:1和3
D: 1和1
答案:

12、单选题：
广义表运算式Tail(((a,b),(c,d)))的操作结果是
选项：
A:c,d
B:d
C:(c,d)
D:((c,d))
答案:

13、判断题：
串是一种数据对象和操作都特殊的线性表。
选项：
A:错
B:对
答案:

14、判断题：
KMP算法的特点是在模式匹配时指示主串的指针不会变小。
选项：
A:对
B:错
答案:

15、判断题：
稀疏矩阵压缩存储后，必会失去随机存取功能。
选项：
A:错
B:对
答案:

16、判断题：
数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。
选项：
A:对
B:错
答案:

17、判断题：
若一个广义表的表头为空表，则此广义表亦为空表。
选项：
A:对
B:错
答案:

18、判断题：
广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。
选项：
A:对
B:错
答案:

第五章 单元测试

1、单选题：
设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）
选项：
A:7
B:8
C:5
D:6
答案:

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

3、单选题：
设给定权值总数有n 个，其哈夫曼树的结点总数为( )
选项：
A:2n
B:2n-1
C:不确定
D:2n+1
答案:

4、单选题：
一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点
选项：
A:h+1
B:2h-1
C:2h
D:2h+1
答案:

5、单选题：
将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（ ）
选项：
A:4
B:6
C:5
D:7
答案:

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

7、单选题：
树的后根遍历序列等同于该树对应的二叉树的( )
选项：
A:后序
B:层序
C:中序
D:先序
答案:

8、单选题：
在下列存储形式中，哪一个不是树的存储形式？（ ）
选项：
A:孩子兄弟表示法
B:孩子链表示法
C:顺序存储结构
D:双亲表示法
答案:

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

10、单选题：
某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。
选项：
A:空或只有一个结点
B:高度等于其结点数
C:任一结点无右子树
D:任一结点无左子树
答案:

11、单选题：
若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( )
选项：
A:X的左子树中最右结点
B:X的双亲
C:X的右子树中最左结点
D:X的左子树中最右叶结点
答案:

12、单选题：
二叉树的第i层上最多含有结点数为（ ）。
选项：
A:
B:
C:
D:
答案:

13、单选题：
n个结点的线索二叉树上含有的线索数为（     ）
选项：
A:2n
B:n
C:n-1
D:n+1
答案:

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

15、单选题：

当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组 A[l..n]中时，数组中第i个结点的左孩子为（     ）
选项：
A:A[2i+1](2i+1=<n)
B:A[i/2]
C:无法确定
D:A[2i](2i=<n)
答案:

16、单选题：
度为4，高度为h的树，（   ）。
选项：
A:至少有h+3个结点
B:至少有4h个结点
C:至多有个结点
D:至少有h+4个结点
答案:

17、单选题：
用孩子链存储结构表示树，其优点之一是（   ）比较方便。
选项：
A:计算机指定结点的度
B:判断两个结点是不是兄弟
C:找指定结点的双亲
D:判断指定结点在第几层
答案:

18、单选题：
根据使用频率为5个字符设计的哈夫曼编码不可能是（   ）。
选项：
A:001，000，01，11，10
B:000，001，010，011，1
C:111，110，10，01，00
D:100，11，10，1，0
答案:

19、单选题：
一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（   ）。
选项：
A:DACEFBG
B:CABDEFG
C:ABCDEFG
D:ADBCFEG
答案:

20、判断题：
二叉树是度为2的有序树。（ ）
选项：
A:错
B:对
答案:

21、判断题：
对于有N个结点的二叉树，其高度为。（ ）
选项：
A:对
B:错
答案:

22、判断题：
二叉树的遍历只是为了在应用中找到一种线性次序。（ ）
选项：
A:对
B:错
答案:

23、判断题：
一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。（ ）
选项：
A:对
B:错
答案:

24、判断题：
中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（ ）
选项：
A:对
B:错
答案:

25、判断题：
由一棵二叉树的前序序列和后序序列可以唯一确定它。（ ）
选项：
A:对
B:错
答案:

26、判断题：
完全二叉树中，若一个结点没有左孩子，则它必是树叶。（ ）
选项：
A:错
B:对
答案:

27、判断题：
将一棵树转成二叉树，根结点没有左子树。（ ）
选项：
A:错
B:对
答案:

28、判断题：
一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和。（ ）
选项：
A:对
B:错
答案:

29、判断题：
当一棵具有n个叶子结点的二叉树的WPL值为最小时，称其树为Huffman树，且其二叉树的形状必是唯一的。（ ）
选项：
A:对
B:错
答案:

第六章 单元测试

1、单选题：
要连通具有n个顶点的有向图，至少需要（ ）条边。
选项：
A:n+1
B:n-1
C:2n
D:n
答案:

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

3、单选题：
下列说法不正确的是（ ）
选项：
A:图的深度遍历不适用于有向图
B:遍历的基本算法有两种：深度遍历和广度遍历
C:图的深度遍历是一个递归过程
D:图的遍历是从给定的源点出发每一个顶点仅被访问一次
答案:

4、单选题：
下列哪一种图的邻接矩阵是对称矩阵？（ ）
选项：
A:有向图
B:AOE网
C:无向图
D:AOV网
答案:

5、单选题：
已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，
E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>}，G的拓扑序列是（  ）。
选项：
A:

V1,V3,V4,V6,V2,V5,V7

B:

V1,V3,V2,V6,V4,V5,V7

C:

V1,V3,V4,V5,V2,V6,V7

D:

V1,V2,V5,V3,V4,V6,V7

答案:

6、单选题：
关键路径是事件结点网络中（ ）
选项：
A:从源点到汇点的最长路径
B:最长回路
C:最短回路
D:从源点到汇点的最短路径
答案:

7、单选题：
下列关于AOE网的叙述中，不正确的是（ ）。
选项：
A:任何一个关键活动提前完成，那么整个工程将会提前完成
B:关键活动不按期完成就会影响整个工程的完成时间
C:某些关键活动提前完成，那么整个工程将会提前完成
D:所有的关键活动提前完成，那么整个工程将会提前完成
答案:

8、单选题：
任何一个带权无向连通图（ ）最小生成树
选项：
A:只有一棵
B:有一棵或多棵
C:可能不存在
D:一定有多棵
答案:

9、单选题：
判断一个有向图是否存在回路除了可以使用拓扑排序算法，还可以使用（ ）
选项：
A:求关键路径的方法
B:广度优先遍历算法
C:求最短路径的Dijkstra算法
D:深度优先遍历算法
答案:

10、单选题：
如果从无向图的任一个顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（ ）
选项：
A:一棵树
B:有回路
C:连通图
D:完全图
答案:

11、单选题：
采用邻接表存储的图的深度优先遍历算法类似于二叉树的（ ）算法
选项：
A:后序遍历
B:层序遍历
C:先序遍历
D:中序遍历
答案:

12、单选题：
采用邻接表存储的图的广度优先遍历算法类似于二叉树的（ ）算法
选项：
A:先序遍历
B:中序遍历
C:后序遍历
D:层序遍历
答案:

13、单选题：
一个无向连通图的最小生成树是含有该连通图的全部顶点的（ ）
选项：
A:极小连通子图
B:极大子图
C:极大连通子图
D:极小子图
答案:

14、单选题：
无权有向图G用邻接矩阵A存储，则顶点i的入度等于A中（ ）。
选项：
A:第i列非0的元素个数
B:第i列0的元素个数
C:第i行非0的元素个数
D:第i行0的元素个数
答案:

15、单选题：
设无向图的顶点个数为n，则该图最多有（ ）条边。
选项：
A:n*(n-1)/2
B:
C:n*(n+1)/2
D:n-1
答案:

16、单选题：
由n个顶点、e条边构成的图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为（ ）。
选项：
A:
B:O(n)
C:O(n+e)
D:
答案:

17、单选题：
一个具有n个顶点的五项图，采用邻接矩阵表示，这该矩阵大小为（    ）。
选项：
A:n-1
B:
C:n
D:
答案:

18、单选题：
设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（   ）。
选项：
A:aebcfd
B:aedfcb
C:aedfbc
D:acfebd
答案:

19、单选题：
一个有n个结点的图，最少有（     ）个连通分量。
选项：
A:0
B:n
C:n-1
D:1
答案:

第七章 单元测试

1、单选题：
对线性表进行二分查找时，要求线性表必须
选项：
A:键值有序的顺序表
B:链接表但键值不一定有序
C:顺序但键值不一定有序
D:键值有序的链接表
答案:

2、单选题：
有一个有序表{1，4，6，10，18，35，42，53，67，71，78，84，92，99},当用二分查找法查找键值为84的结点时，经( )比较后查找成功
选项：
A:3
B:12
C:4
D:2
答案:

3、单选题：
设散列表长度为m，散列函数为H（key）=key%p，为了减少发生冲突的可能性，p应取
选项：
A:小于m的最大奇数
B:小于m的最大偶数
C:小于m的最大合数
D:小于m的最大素数
答案:

4、单选题：
查找效率最高的二叉排序树是
选项：
A:所有结点的左子树都为空的二叉排序树
B:没有左子树的二叉排序树
C:所有结点的右子树都为空的二叉排序树
D:平衡二叉树
答案:

5、单选题：
以下说法错误的是
选项：
A:散列表的结点中只包含数据元素自身的信息，不包含指针
B:负载因子是散列表的一个重要参数，它反映了散列表的饱满程度
C:散列表的查找效率主要取决于散列表构造时选取的散列函数和处理冲突的方法
D:散列法存储的思想是由关键字值决定数据的存储地址
答案:

6、单选题：
顺序查找法适合于存储结构为( )的线性表
选项：
A:散列存储
B:压缩存储
C:索引存储
D:顺序存储或链式存储
答案:

7、单选题：
下列排序方法中，( )是稳定的排序方法
选项：
A:快速排序，堆排序
B:堆排序，冒泡排序
C:归并排序，冒泡排序
D:直接选择排序，归并排序
答案:

8、单选题：
若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为(   )。
选项：
A:n/2
B:(n+1)/2
C: (n-1)/2
D:n
答案:

9、单选题：
适用于折半查找的表的存储方式及元素排列要求为(    )
选项：
A:链接方式存储，元素有序
B:链接方式存储，元素无序
C:顺序方式存储，元素有序
D:顺序方式存储，元素无序
答案:

10、单选题：
当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度(    )
选项：
A:必定快
B:不一定
C:取决于表递增还是递减
D:在大部分情况下要快
答案:

11、单选题：
二叉查找树的查找效率与二叉树的(  )有关
选项：
A:结点的位置
B:结点的多少
C:树型
D:高度
答案:

12、单选题：
二叉查找树在 (   )时其查找效率最低。
选项：
A:呈单枝树
B:结点太复杂
C:结点太多
D:完全二叉树
答案:

13、单选题：
如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用(    )查找法。
选项：
A:折半查找
B:基于属性
C:顺序查找
D:分快查找
答案:

14、单选题：
分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是(    )。
选项：
A:（100，120，110，130，80， 60， 90）
B:(100，80， 60， 90， 120，130，110)
C:（100，60， 80， 90， 120，110，130）
D:（100，80， 90， 60， 120，110，130）
答案:

15、单选题：
设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（    ）记录。
选项：
A:1
B:2
C:3
D:4
答案:

16、单选题：
将10个元素散列到100000个单元的哈希表中，则（    ）产生冲突。
选项：
A: 一定不会
B:一定会
C:仍可能会
答案:

第八章 单元测试

1、单选题：
下列排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一段的方法，称为（     ）
选项：
A:归并排序
B:基数排序
C:选择排序
D:插入排序
答案:

2、单选题：
为实现快速排序算法，待排序列适合采用(     )存储方式。
选项：
A:索引存储
B:顺序存储
C:链式存储
D:散列存储
答案:

3、单选题：
对序列进行排序，一趟排序后序列变为，则采用的排序方法是(     )。
选项：
A:堆排序
B:直接插入排序
C:希尔排序
D:选择排序
答案:

4、单选题：
有一组数据，用堆排序的筛选方法建立的初始小根堆为(     )。
选项：
A:
B:
C:
答案:

5、单选题：
一组记录的关键字为，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为(     )。
选项：
A:
B:
C:
D:
答案:

6、单选题：
对下列整数序列使用基数排序，一趟分配收集之后的结果是(     ) 。
选项：
A:
B:
C:
D:
答案:

7、单选题：
对N个不同的排序码进行冒泡 (递增) 排序，在下列(     )情况比较的次数最多。
选项：
A:元素无序
B:从小到大排列好的
C:从大到小排列好的
D:元素基本有序
答案:

8、多选题：
在下列排序算法中，(  )算法的效率与待排数据的原始状态有关。
选项：
A:插入排序
B:冒泡排序
C:快速排序
D:基数排序
答案:

9、判断题：
采用堆排序时，若关键字的排列杂乱无序，则效率最高。（   ）
选项：
A:对
B:错
答案:

10、判断题：
对N个记录采用快速排序，所需要的平均时间是。（   ）
选项：
A:对
B:错
答案:

11、判断题：
在插入排序、选择排序、交换排序、归并排序算法中,要求内存量最大的是归并排序。（   ）
选项：
A:对
B:错
答案:

12、判断题：
快速排序的最坏情况，可以通过适当选择中轴元素避免。（   ）
选项：
A:对
B:错
答案:

13、判断题：
内部排序要求数据元素全部在内存完成排序，且顺序存储。（   ）
选项：
A:对
B:错
答案:

14、判断题：
采用希尔方法排序时，若关键字的排列杂乱无序，则效率最高。（   ）
选项：
A:错
B:对
答案:

15、判断题：
堆排序所需的时间与待排序的记录个数无关。（   ）
选项：
A:错
B:对
答案:

16、判断题：
快速排序算法在每一趟排序中都能找到一个元素放在其最终位置上。（   ）
选项：
A:对
B:错
答案:

17、判断题：
堆是完全二叉树，完全二叉树不一定是堆。（   ）
选项：
A:错
B:对
答案: