数据结构与算法（仲恺农业工程学院）知到智慧树章节测试课后答案2024年秋仲恺农业工程学院

数据结构与算法（仲恺农业工程学院）知到智慧树章节测试课后答案2024年秋仲恺农业工程学院第二章单元测试

线性表是（）。

A:一个有限序列，可以为空B:一个元限序列，不可以为空C:一个无限序列，可以为空D:一个有限序列，不可以为空

答案:一个有限序列，可以为空在一个长度为n的顺序表中于第i个元素(1≤i≤n+1)之前插入一个新元素，需要向后移动（）个元素。

A:n-iB:n-i+1C:iD:n-i-1

答案:n-i+1链表不具有的特点是（）。

A:插入删除不需要移动元素B:不必事先估计存储空间C:可随机访问任一元素D:所需空间与线性表长度成正比

答案:可随机访问任一元素线性表采用链式存储结构时，各节点之间的地址（）。

A:连续与否均可以B:一定是不连续的C:必须是连续的

答案:连续与否均可以若线性表最常用的运算是存取第i个元素及其前驱的值，则采用（）存储方式最节省时间。

A:循环单链表B:单链表C:双链表D:顺序表

答案:顺序表对于用一维数组d[0..n-1]顺序存储的线性表，其算法的时间复杂度为O(1)的操作是（）。

A:查找第i个元素(1≤i≤n)B:将n个元素从小到大排序C:从线性表中删除第i个元素(1≤i≤n)D:在线性表中第i个元素之后插入一个元素

答案:查找第i个元素(1≤i≤n)在单链表中，若*p节点不是尾节点，在其后插入*s节点的操作是（）。

A:s->next=p->next;p->next=s;B:s->next=p->next;p=s;C:p->next=s;s->next=p;D:s--->next=p;p->next=s;

答案:s->next=p->next;p->next=s;在一个单链表中，删除*p节点(非尾节点)之后的一个节点的操作是（）。

A:p->next->next=p->nextB:p->next=pC:p->next->next=pD:p->next=p->next->next

答案:p->next=p->next->next在一个双链表中，在*p节点(非尾节点)之后插入一个节点*s的操作是（）。

A:s->next=p->next;p->next->prior=s;p->next=s;s->prior=p;B:s->prior=p;p->next=s;p->next->prior=s;s->next=p->next;C:p->next=s;s->prior=p;s->next=p->next;p->next->prior=s;D:p->prior=s;s->next=p;s->next->prior=p;p->next=s->next;

答案:s->next=p->next;p->next->prior=s;p->next=s;s->prior=p;在一个双链表中，删除*p节点(非尾节点)之后的一个节点的操作是（）。

A:p->next=p->next->next;p->next->prior=p;B:p->next->prior=p;p->next=p->next->next;C:p->next->next=p->next;p->next->prior=p;D:p->next=p->next->next;p->next->next->prior=p;

答案:p->next=p->next->next;p->next->prior=p;

第三章单元测试

设有一顺序栈S，元素s1,s2,s3,s4,s5,s6 依次进栈，如果6个元素出栈的顺序是s2,s4,s3,s6,s5,s1，则栈的容量至少应该是

A:2B:3C:5D:4

答案:3一个栈的入栈序列是1，2，3，4，5，则栈的不可能输出序列是

A:1,2,3,4,5B:5,4,3,1,2C:3,2,4,5,1D:3,5,4,2,1

答案:5,4,3,1,2一个队列的入队序列是1，3，5，7，9，则出队的输出序列只能是

A:1,3,5,7,9B:9,5,1,7,3C:9,7,5,3,1D:1,5,9,3,7

答案:1,3,5,7,9设循环队列中数组的下标范围是1～n，其头尾指针分别为f和r，则其元素个数为

A:r-f+1B:(r-f+n)%nC:r-fD:(r-f)%n+1

答案:(r-f+n)%n设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行入队操作后其尾指针rear值为

A:rear=(rear+1)%(m-1)B:rear=rear+1C:rear=(rear+1)%mD:rear=(rear-1)%m

答案:rear=(rear+1)%m递归过程或函数调用时，处理参数及返回地址，使用的数据结构是

A:多维数组B:线性表C:栈D:队列

答案:栈栈中元素的进出原则是

A:栈空则进B:栈满则出C:后进先出D:先进先出

答案:后进先出判定一个栈ST（最多元素为m0）为空的条件是

A:ST->top<>0B:ST->top==m0C:ST->top<>m0D:ST->top==0

答案:ST->top==0判定一个队列QU（最多元素为m0）为满队列的条件是

A:QU->front = = QU->rear B:QU->rear － QU->front －1= = m0 C:QU->rear － QU->front = = m0 D:QU->front = = QU->rear +1

答案:QU->rear － QU->front = = m0 在一个链式队列中.假设f和r分别为队头和队尾指针,则插入s所指的结点运算是

A:f->next=s;f=s; B:s->next=s;r=s; C:s->next=f;f=s; D:r->next=s;r=s; 

答案:r->next=s;r=s; 向一个栈指针为HS的链式栈中插入一个s所指的结点时,则执行

A:S->NEXT=HS->NEXT;HS->NEXT=S;B: S->NEXT=HS;HS=HS->NEXT; C:HS->NEXT=S; 

答案:S->NEXT=HS->NEXT;HS->NEXT=S;设一个栈的输入序列是1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（ ）。

A:45 1 32B:43 1 25C:5 1 23 4 D:3 2 15 4 

答案:3 2 15 4 进栈序列为a，b，c，则通过入、出栈可能得到的a，b，c的不同排列个数是（）。

A:7B:6C:5D:4

答案:5表达式a*(b+c)-d 的后缀表达式是( )。

A:-+*abcd B:abcd*+-C:abc*+d- D:abc+*d- 

答案:abc+*d- 设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。

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

答案:栈用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时()。

A:队头、队尾指针都可能要修改B:队头、队尾指针都要修改C:仅修改队尾指针D:仅修改队头指针

答案:队头、队尾指针都可能要修改假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（）。

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

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

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

答案:(rear-front+m)%m 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？() 

A:1 和5B:4和2C:5 和1 D:2和4

答案:1 和5栈和队都是（）。 

A:顺序存储的线性结构 B:限制存取点的非线性结构C:限制存取点的线性结构D:链式存储的非线性结构 

答案:限制存取点的线性结构栈的操作原则是（ ）。 

A:先进先出B:后进先出C:后进后出 D:顺序进出 

答案:后进先出下面术语中，与数据的存储结构无关的是（ ）。 

A:栈B:顺序表C:循环队列 D:顺序栈 

答案:栈栈和队列具有相同的（ ）。 

A:逻辑结构 B:运算C:存储结构D:抽象数据类型

答案:逻辑结构 递归算法必须包括（ ）。 

A:终止条件和迭代部分 B:迭代部分C:递归部分D:终止条件和递归部分  

答案:终止条件和递归部分  

第四章单元测试

串s="ABCDEF"的串长度为

A:8B:3C:7D:4

答案:7设有串s="ABCBBCBBCBBA"和串t="CB"，则串t在s中的匹配位置是

A:9B:6C:1D:3

答案:3串是

A:不少于一个字符的序列B:有限个字符的序列C:不少于一个字母的序列D:任意个字母的序列

答案:有限个字符的序列设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为

A:求子串B:联接C:求串长D:匹配

答案:匹配设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为

A:33B:13C:18D:40

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

A:i(i-l)/2+jB:j(j-l)/2+iC:j(j-l)/2+i-1D:i(i-l)/2+j-1

答案:j(j-l)/2+i对稀疏矩阵进行压缩存储目的是

A:节省存储空间B:便于输入和输出C:便于进行矩阵运算D:降低运算的时间复杂度

答案:节省存储空间有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是

A:66B:33C:60D:180

答案:66广义表（a,(b,c),d,e）的表头为

A:a,(b,c)B:aC:(a)D:(a,(b,c))

答案:a下面说法不正确的是

A:广义表难以用顺序存储结构B:广义表可以是一个多层次的结构C:广义表至少有一个元素D:广义表可以是一个递归表

答案:广义表至少有一个元素设广义表L=（（a,b,c）），则L的长度和深度分别为

A:

1和1B:1和3C:2和3D:1和2

答案:1和2广义表运算式Tail(((a,b),(c,d)))的操作结果是

A:(c,d)B:dC:c,dD:((c,d))

答案:((c,d))串是一种数据对象和操作都特殊的线性表。

A:错B:对

答案:对KMP算法的特点是在模式匹配时指示主串的指针不会变小。

A:对B:错

答案:对稀疏矩阵压缩存储后，必会失去随机存取功能。

A:错B:对

答案:对数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。

A:对B:错

答案:错若一个广义表的表头为空表，则此广义表亦为空表。

A:对B:错

答案:错广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。

A:对B:错

答案:错

第五章单元测试

设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（）

A:7B:6C:5D:8

答案:8一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）

A:501B:250C:499D:500

答案:501设给定权值总数有n个，其哈夫曼树的结点总数为()

A:2n-1B:2n+1C:不确定D:2n

答案:2n-1一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有()结点

A:2hB:2h-1C:h+1D:2h+1

答案:2h-1将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（）

A:6B:4C:7D:5

答案:6对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，

同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用()次序的遍历实现编号

A:后序B:层序C:先序D:中序

答案:后序树的后根遍历序列等同于该树对应的二叉树的()

A:后序B:中序C:层序D:先序

答案:中序在下列存储形式中，哪一个不是树的存储形式？（）

A:孩子链表示法B:孩子兄弟表示法C:顺序存储结构D:双亲表示法

答案:顺序存储结构已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。

A:不确定B:CBEFDAC:FEDCBAD:CBEDFA

答案:CBEFDA某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。

A:任一结点无左子树B:空或只有一个结点C:任一结点无右子树D:高度等于其结点数

答案:高度等于其结点数若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为()

A:X的双亲B:X的左子树中最右叶结点C:X的右子树中最左结点D:X的左子树中最右结点

答案:X的左子树中最右结点二叉树的第i层上最多含有结点数为（

）。

A:B:

C:

D:

答案:

n个结点的线索二叉树上含有的线索数为（

）

A:n+1B:nC:2nD:n-1

答案:n+1由3

个结点可以构造出多少种不同的二叉树？（

）

A:5B:2C:3D:4

答案:5当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组

A[l..n]中时，数组中第i个结点的左孩子为（

）

A:A[2i](2i=<n)

B:A[2i+1](2i+1=<n)C:A[i/2]D:无法确定

答案:无法确定度为4，高度为h的树，（

）。

A:至多有个结点B:至少有h+4个结点C:至少有4h个结点D:至少有h+3个结点

答案:至少有h+3个结点用孩子链存储结构表示树，其优点之一是（

）比较方便。

A:判断两个结点是不是兄弟B:判断指定结点在第几层C:计算机指定结点的度D:找指定结点的双亲

答案:计算机指定结点的度根据使用频率为5个字符设计的哈夫曼编码不可能是（

）。

A:100，11，10，1，0B:000，001，010，011，1C:001，000，01，11，10D:111，110，10，01，00

答案:100，11，10，1，0一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（

）。

A:DACEFBG

B:ABCDEFGC:ADBCFEG

D:CABDEFG

答案:ABCDEFG二叉树是度为2的有序树。（

）

A:对B:错

答案:错对于有N个结点的二叉树，其高度为。（

）

A:错B:对

答案:错二叉树的遍历只是为了在应用中找到一种线性次序。（

）

A:对B:错

答案:对一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。（

）

A:错B:对

答案:错中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（

）

A:错B:对

答案:对由一棵二叉树的前序序列和后序序列可以唯一确定它。（

）

A:错B:对

答案:错完全二叉树中，若一个结点没有左孩子，则它必是树叶。（

）

A:对B:错

答案:对将一棵树转成二叉树，根结点没有左子树。（

）

A:对B:错

答案:错一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和。（

）

A:对B:错

答案:错当一棵具有n个叶子结点的二叉树的WPL值为最小时，称其树为Huffman树，且其二叉树的形状必是唯一的。（

）

A:错B:对

答案:错

第六章单元测试

要连通具有n个顶点的有向图，至少需要（）条边。

A:n+1B:nC:n-1D:2n

答案:n在一个无向图中，所有顶点的度数之和等于所有边数（）倍

A:2B:1/2C:1D:4

答案:2下列说法不正确的是（）

A:图的深度遍历不适用于有向图B:图的深度遍历是一个递归过程C:图的遍历是从给定的源点出发每一个顶点仅被访问一次

D:遍历的基本算法有两种：深度遍历和广度遍历

答案:图的深度遍历不适用于有向图下列哪一种图的邻接矩阵是对称矩阵？（）

A:有向图B:AOE网C:无向图D:AOV网

答案:无向图已知有向图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,V7B:V1,V3,V2,V6,V4,V5,V7C:V1,V2,V5,V3,V4,V6,V7D:V1,V3,V4,V5,V2,V6,V7

答案:V1,V3,V4,V6,V2,V5,V7关键路径是事件结点网络中（）

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

答案:从源点到汇点的最长路径下列关于AOE网的叙述中，不正确的是（）。

A:所有的关键活动提前完成，那么整个工程将会提前完成B:某些关键活动提前完成，那么整个工程将会提前完成C:关键活动不按期完成就会影响整个工程的完成时间D:任何一个关键活动提前完成，那么整个工程将会提前完成

答案:任何一个关键活动提前完成，那么整个工程将会提前完成任何一个带权无向连通图（）最小生成树

A:只有一棵B:可能不存在C:一定有多棵D:有一棵或多棵

答案:有一棵或多棵判断一个有向图是否存在回路除了可以使用拓扑排序算法，还可以使用（）

A:求最短路径的Dijkstra算法B:求关键路径的方法C:广度优先遍历算法D:深度优先遍历算法

答案:深度优先遍历算法如果从无向图的任一个顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）

A:完全图B:有回路C:连通图D:一棵树

答案:连通图采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）算法

A:中序遍历B:先序遍历C:层序遍历D:后序遍历

答案:先序遍历采用邻接表存储的图的广度优先遍历算法类似于二叉树的（）算法

A:后序遍历B:先序遍历C:中序遍历D:层序遍历

答案:层序遍历一个无向连通图的最小生成树是含有该连通图的全部顶点的（）

A:极小连通子图B:极大连通子图C:极大子图D:极小子图

答案:极小连通子图无权有向图G用邻接矩阵A存储，则顶点i的入度等于A中（）。

A:第i行0的元素个数B:第i列非0的元素个数C:第i行非0的元素个数D:第i列0的元素个数

答案:第i列非0的元素个数设无向图的顶点个数为n，则该图最多有（

）条边。

A:B:n*(n+1)/2

C:n-1D:n*(n-1)/2

答案:n*(n-1)/2

由n个顶点、e条边构成的图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为（

）。

A:B:O(n)C:D:O(n+e)

答案:O(n+e)一个具有n个顶点的五项图，采用邻接矩阵表示，这该矩阵大小为（

）。

A:B:n-1C:nD:

答案:设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（

）。

A:aedfbcB:acfebdC:aedfcbD:aebcfd

答案:aedfcb一个有n个结点的图，最少有（

）个连通分量。

A:n-1B:1C:0D:n

答案:1

第七章单元测试

对线性表进行二分查找时，要求线性表必须

A:顺序但键值不一定有序B:键值有序的顺序表C:链接表但键值不一定有序D:键值有序的链接表

答案:键值有序的顺序表有一个有序表{1，4，6，10，18，35，42，53，67，71，78，84，92，99},当用二分查找法查找键值为84的结点时，经()比较后查找成功

A:3B:4C:2D:12

答案:4设散列表长度为m，散列函数为H（key）=key%p，为了减少发生冲突的可能性，p应取

A:小于m的最大素数B:小于m的最大奇数C:小于m的最大合数D:小于m的最大偶数

答案:小于m的最大素数查找效率最高的二叉排序树是

A:所有结点的右子树都为空的二叉排序树B:没有左子树的二叉排序树C:所有结点的左子树都为空的二叉排序树D:平衡二叉树

答案:平衡二叉树以下说法错误的是

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

答案:散列表的结点中只包含数据元素自身的信息，不包含指针顺序查找法适合于存储结构为()的线性表

A:散列存储B:压缩存储C:顺序存储或链式存储D:索引存储

答案:顺序存储或链式存储下列排序方法中，( )是稳定的排序方法

A:快速排序，堆排序B:归并排序，冒泡排序C:堆排序，冒泡排序D:直接选择排序，归并排序

答案:归并排序，冒泡排序若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为(   )。

A:(n+1)/2B: (n-1)/2C:n/2 D:n

答案:(n+1)/2适用于折半查找的表的存储方式及元素排列要求为(    )  

A:链接方式存储，元素有序 B:顺序方式存储，元素有序 C:顺序方式存储，元素无序 D:链接方式存储，元素无序

答案:顺序方式存储，元素有序 当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度(    )  

A:不一定B:取决于表递增还是递减C:必定快D:在大部分情况下要快

答案:在大部分情况下要快二叉查找树的查找效率与二叉树的(  )有关

A:高度 B:结点的多少C:结点的位置 D:树型

答案:树型二叉查找树在 (   )时其查找效率最低。

A:结点太复杂B:呈单枝树C:完全二叉树D:结点太多

答案:呈单枝树如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用(    )查找法。

A:分快查找B:顺序查找C:基于属性D:折半查找

答案:分快查找分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是(    )。 

A:（100，60， 80， 90， 120，110，130）B:（100，80， 90， 60， 120，110，130）C:（100，120，110，130，80， 60， 90）D:(100，80， 60， 90， 120，130，110) 

答案:（100，60， 80， 90， 120，110，130）设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地