数据结构与算法智慧树知到期末考试答案2024年

数据结构与算法智慧树知到期末考试答案2024年数据结构与算法深度为6的二叉树最多有()个结点。

A:64B:63C:32D:31答案:63设二叉树有n个结点，则其深度为（）。

A:n-1B:nC:不确定D:log2n+1答案:不确定对一个算法的评价，不包括如下（）方面的内容。

A:并行性B:时空复杂度C:正确性D:健壮性和可读性答案:并行性对以下数据序列利用快速排序进行排序，速度最快的是()。

A:{21,9,17,30,25,23,5}B:{5,9,17,21,23,25,30}C:{21,25,5,17,9,23,30}D:{25,23,30,17,21,5,9}答案:{21,25,5,17,9,23,30}对于稀疏矩阵，对每个非零元素aij,可以用一个（）唯一确定。

A:非零元素B:三元组(i,j,aij)C:aijD:i,j答案:三元组(i,j,aij)利用二叉链表存储树，则根结点的右指针是（）。

A:指向最右孩子B:指向最左孩子C:非空D:空答案:空连通图是指图中任意两个顶点之间（）。

A:都不连通的有向图B:都不连通的无向图C:都连通的有向图D:都连通的无向图答案:都连通的无向图排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是（）的基本思想。

A:快速排序B:堆排序C:直接插入排序D:冒泡排序答案:冒泡排序由两个栈共享一个向量空间的好处是（）。

A:减少存取时间，降低下溢发生的机率B:减少存取时间，降低上溢发生的机率C:节省存储空间，降低上溢发生的机率D:节省存储空间，降低下溢发生的机率答案:节省存储空间，降低上溢发生的机率在下列存储形式中，哪一个不是树的存储形式？（）。

A:顺序存储表示法B:孩子链表表示法C:双亲表示法D:孩子兄弟表示法答案:顺序存储表示法对采用折半查找法进行查找运算的查找表，要求按（）方式进行存储。

A:顺序存储B:顺序存储且结点按关键字有序C:链式存储且结点按关键字有序D:链式存储答案:顺序存储且结点按关键字有序判断一个循环队列Q（空间大小为M）为空的条件是（）。

A:Q-＞rear-Q-＞front==M+1B:Q-＞front==Q-＞rearC:(Q-＞front+1)%M==Q-＞rearD:(Q-＞rear+1)%M==Q-＞front答案:Q.front==Q.rear快速排序在最好情况下的时间复杂度为（）。

A:O(n)B:O(n2)C:O(log2n)D:O(nlog2n)答案:O(nlog2n)设有100个结点，用二分方法查找时，最大的比较次数是（）。

A:50B:25C:7D:10答案:7一个队列的入队顺序是1，2，3，4，则队列的出队顺序是（）。

A:4321B:1423C:3241D:1234答案:1234已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该（）。

A:将邻接矩阵的第i行删除B:将邻接矩阵的第i列删除C:将邻接矩阵的第i行元素全部置为0D:将邻接矩阵的第i列元素全部置为0答案:将邻接矩阵的第i行元素全部置为0在一个小根堆中，具有最大值的元素一定是叶结点。（）

A:对B:错答案:对在拓朴序列中，如果结点Vi排在结点Vj的前面，则一定存在从Vi到Vj的路径。（）

A:错误B:正确答案:错误在哈夫曼树中，权值最小的结点离根结点最近。（）

A:正确B:错误答案:错误数组元素的下标值越大，存取时间越长。（）

A:错误B:正确答案:错误在单链表中，给定任一结点的地址p，则可用下述语句将新结点s插入结点p的后面：p-＞next=s;s-＞next=p-＞next;。（）

A:错误B:正确答案:错误无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（）

A:对B:错答案:错快速排序的枢轴元素可以任意选定。（）

A:对B:错答案:对树与二叉树是两种不同的树型结构。（）

A:错误B:正确答案:正确完全二叉树一定存在度为1的结点。（）

A:错误B:正确答案:错误若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（）

A:257B:384C:385D:258答案:384允许对队列进行的操作有（）。

A:在队列元素之间插入元素B:取出最后进队的元素C:删除队头元素D:对队列中的元素排序答案:删除队头元素含有20个结点的平衡二叉树的最大深度为（）。

A:5B:7C:4D:6答案:4用S表示进栈操作，用X表示出栈操作，若元素的进栈顺序是1234，为了得到1342的出栈顺序，相应的和X的操作序列为（）。

A:SSSXXSXXB:SXSSXXSXC:SXSSXSXXD:SXSXSSXX答案:SXSSXSXX下列关于排序的叙述中，正确的是()

A:稳定的排序方法优于不稳定的排序方法B:排序方法都是在顺序表上实现的，在链表上无法实现排序方法C:对同一线性表使用不同的排序方法进行排序，得到的排序结果可能不同D:在顺序表上实现的排序方法在链表上也可以实现答案:对同一线性表使用不同的排序方法进行排序,得到的排序结果可能不同单链表中，增加一个头结点的目的是为了（）。

A:说明单链表是线性表的链式存储B:方便运算的实现C:标识表结点中首结点的位直D:使单链表至少有一个结点答案:方便运算的实现对n个记录进行堆排序，最坏情况下其时间复杂度为（）。

A:O(n)B:O(n2)C:O(log2n)D:O(nlog2n)答案:O(nlog2n)具有15个叶子节点的二叉树中有（）个度为2的结点。

A:13B:15C:16D:14答案:14假设一棵二叉树的结点个数为50，则它的最小高度是（）。

A:4B:7C:6D:5答案:6任何一个无向连通图的最小生成树（）。

A:只有一棵B:可能不存在C:一定有多棵D:有一棵或多棵答案:一定有多棵希尔排序的组内排序采用的是（）。

A:归并排序B:折半插入排序C:快速排序D:直接插入排序答案:直接插入一个有n个顶点的无向图最多有____条边。

A:n(n-1)B:n(n-1)/2C:2nD:n答案:n(n-1)/2在下列排序方法中，若待排序的数据已经有序，花费时间反而最多的是

A:冒泡排序B:堆排序C:希尔排序D:快速排序答案:快速排序单链表中，增加一个头结点的目的是（）。

A:标识表结点中首结点的位置。B:说明单链表是线性表的链式存储。C:方便运算的实现。D:使单链表至少有一个结点。答案:方便运算的实现设一个栈的输入序列是1、2、3、4、5，则下列序列中，是栈的合法输出序列的是？

A:45132B:51234C:43125D:32154答案:3若长度为n的非空线性表采用顺序存储结构，在表的第i个位置插入一个数据元素的合法值应该是（）。

A:0≤i≤nB:1≤i≤n+1C:1≤i≤nD:0≤i≤n-1答案:1≤i≤n+1若用大小为6的数组来实现循环队列，且当前front和rear的值分别为0和4。当从队列中删除两个元素，再加入两个元素后，front和rear的值分别为多少？

A:2和6B:2和2C:2和4D:2和0答案:2和0一个深度为k的，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依此对结点编号，则编号最小的叶子的序号是（）。

A:2^(k-2)B:2^(k-1)C:2^(k-2)+1D:2^(k-1)+1答案:2^(k-2)+1设树中某结点不是根结点，则离它最近的祖先结点是（）。

A:父结点B:根结点C:该结点本身D:父结点的父结点答案:父结点若一棵二叉树具有10个度为2的结点、5个度为1的结点，则度为0的结点个数是

A:9B:15C:不确定D:11答案:11线性表的顺序存储结构是一种（）。

A:顺序存取的存储结构B:Hash存取的存储结构C:索引存取的存储结构D:随机存取的存储结构答案:随机存取###顺序存取下面几个符号串编码集合中，不是前缀编码的是（）。

A:{b,c,aa,ac,aba,abb,abc}B:{0,10,110,1111}C:{00,010,0110,1000}D:{11,10,001,101,0001}答案:{11,10,001,101,0001}顺序表中，在向表中第i个元素（1≤i≤n+1）位置插入一个新元素时，为保持插入后表中原有元素的相对次序不变，需要从后向前依次后移（）个元素。

A:n-i-1B:iC:n-iD:n-i+1答案:n-i+1不带头结点的单链表head为空的判定条件是（）。

A:head!=NULL;B:head->next==NULL;C:head==NULL;D:head->next==first;答案:head==NULL单链表又称为线性链表，在单链表上实施插入和删除操作（）。

A:不需移动结点，不需改变结点指针B:只需移动结点，不需改变结点指针C:不需移动结点，只需改变结点指针D:既需移动结点，又需改变结点指针答案:不需移动结点，只需改变结点指针采用邻接表存储的图的广度优先遍历算法类似于二叉树的____算法。

A:先序遍历B:后序遍历C:中序遍历D:层次遍历答案:层次遍历以下关于huffman树说法错误的是（）。

A:一般在huffman树中，权值越大的叶子离根结点越近B:若初始森林中共有n棵二叉树，进行2n-1次合并后才能剩下一棵最终的huffman树C:huffman树中没有度数为1的分支结点D:若初始森林中共有n棵二叉树，最终求得的huffman树共有2n-1个结点答案:若初始森林中共有n棵二叉树，进行2n-1次合并后才能剩下一棵最终的huffman树Dijkstra算法是____方法求出图中从某顶点到其余顶点的最短路径的

A:通过深度优先遍历求出图中某顶点到其余顶点的最短路径B:通过广度优先遍历求出图中某顶点到其余顶点的最短路径C:按长度递减的顺序求出图中某顶点到其余顶点的最短路径D:按长度递增的顺序求出图中某顶点到其余顶点的最短路径答案:按长度递增的顺序求出图中某顶点到其余顶点的最短路径下面关于串的叙述中，哪一个是不正确的？

A:串既可以采用顺序存储，也可以采用链式存储B:空串是由空格构成的串C:串是字符的有限序列D:模式匹配是串的一种重要运算答案:空串是由空格构成的串KMP算法下，长为n的字符串匹配长度为m的字串的时间复杂度为

A:O(n)B:O(n+logm)C:O(m+logn)D:O(m+n)答案:O(m+n)从一个具有n个结点的有序单链表中查找其值等于x的结点时，在查找成功的情况下，需要平均比较（）个结点。

A:(n-1)/2B:(n+1)/2C:nD:n/2答案:(n+1)/2设T是非空二叉树，若T的先序遍历和中序遍历序列相同，则T的形态是（）。

A:所有结点只有右孩子B:只有一个根结点C:没有度为1的结点D:所有结点只有左孩子答案:所有结点只有右孩子已知L是带头结点的单链表，则摘除首元结点的语句是（）。

A:L=L->next->next;B:L->next=L;C:L=L->next;D:L->next=L->next->next;答案:L-next=L-next-如果哈夫曼树有67个结点，则可知叶结点总数为：

A:33B:22C:34D:不确定答案:34设栈S和队列Q的初始状态均为空，元素a、b、c、d、e、f、g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b、d、c、f、e、a、g，则栈S的容量至少是：

A:3B:4C:1D:2答案:3用双亲存储结构表示树，其优点之一是比较方便

A:找指定结点的双亲结点B:判断某结点是不是叶子结点C:找指定结点的兄弟结点D:找指定结点的孩子结点答案:找指定结点的双亲结点带头结点的单链表head为空的判定条件是（）。

A:head->next==first;B:head->next==NULL;C:head!=NULL;D:head==NULL;答案:head==NULL已知单链表中结点p不是链尾结点，若在p之后插入结点s，则应执行以下（）操作。

A:s->next=p->next;p=s；B:p->next=s;s->next=p;C:s->next=p->next;p->next=s;D:s->next=p;p->next=s;答案:s-next=p-p-next=s;数据结构是介于()的之间的一门核心课程。

A:硬件B:数学C:网络D:软件答案:数学;硬件;软件对于有N个结点的二叉树，其高度为log2n。

A:对B:错答案:错数据结构概念包括数据之间的逻辑结构、数据在计算机中的存储方式和数据的运算三个方面。

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

A:错B:对答案:对非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子。

A:错误B:正确答案:正确若一个结点是某二叉树的中序遍历序列的最后一个结点，则它必是该树的前序遍历序列中的最后一个结点。

A:错误B:正确答案:错误对N（≥2）个权值均不相同的字符构造哈夫曼树，则树中任一非叶结点的权值一定不小于下一层任一结点的权值。

A:错误B:正确答案:正确若采用“队首指针和队尾指针的值相等”作为环形队列为空的标志，则在设置一个空队时只需将队首指针和队尾指针赋同一个值，不管什么值都可以。

A:对B:错答案:对栈是一种对进栈、出栈操作总次数做了限制的线性表。

A:错B:对答案:错哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。

A:错B:对答案:对一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定只有一个叶结点（）

A:对B:错答案:对算法至少有1个输入（）

A:错B:对答案:错有向图中顶点V的度等于其邻接矩阵中第V行中1的个数。（）

A:正确B:错误答案:错误消除递归一定需要使用栈这种数据结构。（）

A:对B:错答案:错在图G的最小生成树G中，某条边的权值可能会超过未选边的权值。（）

A:错误B:正确答案:正确链表的物理存储结构具有同链表一样的顺序。（）

A:错误B:正确答案:错误若散列表的装填因子α＜1，则可避免碰撞的产生。（）

A:错B:对答案:错顺序存储结构和链式存储结构都可以进行顺序存取。（）

A:对B:错答案:对下面不属于特殊矩阵的是（）。

A:对角矩阵B:三角矩阵C:稀疏矩阵D:对称矩阵答案:AI参考:不属于特殊矩阵的是：B三角矩阵。\n\n特殊矩阵是一种特殊的矩阵，常见的一些特殊矩阵有对角矩阵、对称矩阵、稀疏矩阵等。三角矩阵只是行数、列数之间存在一定关系的矩阵，并不属于特殊矩阵。'二叉排序树中，最小值结点的（）。

A:左、右指针均不为空B:右指针一定为空C:左指针一定为空D:左、右指针一定为空答案:AI参考:正确答案是B：右指针一定为空。\n\n二叉排序树中，最小值结点的右指针一定为空，因为左子树的所有节点都小于根节点，所以最小值结点的右指针一定为空。而左指针不一定为空，因为有可能存在多个最小值结点。'在顺序表(3,6,8,10,12,15,16,18,21,25,30)中，用折半法查找关键码值11，所需的关键码比较次数为（）。

A:4B:5C:2D:3答案:AI参考:答案：D。对于有序表，折半查找法又称二分查找法，要求待查找的元素与查找表中的关键字已经按顺序排列好。在有序表(3,6,8,10,12,15,16,18,21,25,30)中查找关键码值11，由于该数列已经有序，所以采用折半查找法，查找过程比较了5次（分别是1次，大于大于等于的讨论各进行一次），每次都将搜索范围缩小了一半，最终确定在序列中的位置。因此，答案是D。'折半查找适用的存储结构为（）的线性表。

A:链式存储且结点按关键字有序排列B:链式存储C:顺序存储D:顺序存储且结点按关键字有序排列答案:AI参考:正确选项是D：顺序存储且结点按关键字有序排列的线性表。\n\n折半查找，也称为二分查找，是一种在有序列表中查找特定元素的搜索算法。对于链式存储的线性表，每次查找需要从头到尾进行遍历，效率较低。而顺序存储结构，由于元素是连续存储的，可以通过比较中间元素和目标值，快速定位目标元素的位置。同时，如果结点按关键字有序排列，则可以进一步提高查找效率。因此，选项D“顺序存储且结点按关键字有序排列的线性表”是折半查找适用的存储结构。'链表不具备的特点是（）。

A:可随机访问任一元素B:插入、删除不需要移动元素C:不必事先估计存储空间D:所需空间与线性表长度成正比答案:AI参考:正确答案是A:可随机访问任一元素。\n链表的特点是插入和删除不需要移动元素，不需要事先估计存储空间，并且所需空间与线性表长度成正比。因此，B、C、D选项都是链表的特点。而链表不能像数组一样随机访问任一元素，这是链表与数组的主要区别之一。因此，答案是A。'在二叉树中引入线索的目的是（）。

A:加快查找前驱或后继的速度B:便于进行插入和删除C:使遍历结果唯一D:便于查找双亲答案:AI参考:在二叉树中引入线索的目的是便于进行插入和删除。线索二叉树是一种特殊的二叉树，通过在二叉树的节点上添加指向其前驱或后继的指针，使得在遍历时能够更加方便地找到这些节点。因此，正确答案是B：便于进行插入和删除。其他选项如加快查找前驱或后继的速度、使遍历结果唯一、便于查找双亲都不是引入线索的主要目的。'栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈,问下列哪一个序列是可能的出栈序列C、B、E、D、A、F。（）

A:错B:对答案:AI参考:答案是B：对。\n\n根据题目描述，栈S最多能容纳4个元素，现有6个元素进栈，说明栈中至少有一个元素出栈后才能容纳下一个元素，因此栈中至少有一个元素出栈。根据题目给出的序列A、B、C、D、E、F，C是第一个出栈的元素，接着出栈的元素是B和E，再接着出栈的是D和A，最后出栈的是F。因此，C、B、E、D、A、F这个序列是可能的出栈序列。所以答案是B：对。'若用冒泡排序算法对序列{10,14,26,29,41,52}从大到小排序，则需进行（）次比较。

A:10B:15C:25D:3答案:AI参考:答案：C\n\n解释：\n\n冒泡排序算法是一种简单的排序算法，它会反复地遍历待排序的序列，每次比较相邻的两个元素，如果顺序不对就交换它们的位置，直到所有元素都排好序为止。\n\n对于给定的序列{10,14,26,29,41,52}，我们按照从大到小的顺序进行冒泡排序。每次遍历序列时，都会将最大的元素"浮"到序列的末尾。因此，冒泡排序需要进行n-1次遍历，其中n是序列的长度。\n\n对于给定的序列，共有6个元素，因此需要进行5次遍历。但在最后一次遍历时，最大的元素已经在末尾了，因此无需再进行比较。所以总共需要进行25次比较。\n\n因此，正确选项为C：25次比较。'对关键码序列{23,17,72,60,25,8,68,71,52}进行堆排序，输出两个最小关键码后的剩余堆是（）。

A:{71,25,23,52,60,72,68}B:{23,25,52,60,71,72,68}C:{23,25,68,52,60,72,71}D:{23,72,60,25,68,71,52}答案:AI参考:输出两个最小关键码后的剩余堆是：D:{23,72,60,25,68,71,52}。\n\n堆排序是一种基于二叉堆数据结构的排序算法，它首先将待排序序列构造成一个大顶堆，然后将堆顶元素与堆尾元素交换，并调整剩余元素形成新的堆。在题目中，首先将序列{23,17,72,60,25,8,68,71,52}构造成一个大顶堆，然后交换堆顶元素（23）和堆尾元素（25），得到剩余堆{72,60,68,71,8,52}。再将堆顶元素（68）和堆尾元素（8）交换，得到最终的剩余堆{72,60,52,68,71,8}。因此，正确选项为D:{23,72,60,25,68,71,52}。'以下排序算法中，稳定的是（）。

A:快速排序B:直接插入排序C:简单选择排序D:堆插入排序答案:AI参考:答案是B：直接插入排序。\n\n稳定排序算法的特点是，等值元素的相对位置在排序后保持不变。直接插入排序、二分查找排序、基数排序和就地排序都是稳定的排序算法。而快速排序、堆排序、计数排序、基数排序和桶排序是不稳定的排序算法。因此，正确答案是B：直接插入排序。'已知字符集｛a,b,c,d,e,f｝，若各字符出现的次数分别6,3,8,2,10,4,则对应字符集中各字符的哈夫曼编码可能是（）。

A:00,1011,01,1010,11,100B:10,1011,11,0011,00,010C:00,100,110,000,0010,01D:0011,10,11,0010,01,000答案:AI参考:已知字符集｛a,b,c,d,e,f｝，各字符出现的次数分别为6,3,8,2,10,4，那么字符a和f出现的次数较少，应使用较短的哈夫曼编码；字符b、c、d出现的次数较多，应使用较长的哈夫曼编码。按照以上原则，结合给出的选项，答案为B：10,1011,11,0011,00,010。\n\n这个答案中，只有B选项包含了较短和较长两种编码，且满足上述出现次数较少和较多的字符编码原则。其中，字符a的编码为“10”，字符b的编码为“1011”，字符c的编码为“11”，字符d的编码为“0011”，字符e的编码为“00”，字符f的编码为“010”。所以，B选项是正确答案。'在一个链队列中，假设队头指针为front,队尾指针为rear,x所指向的元素需要入队，则需要执行的操作为（）。

A:x-＞next=front-＞next；front=x；B:front=x；front=front-＞next；C:rear-＞next=x;x-＞next=NULL;rear=x;D:rear-＞nex