数据结构（山东联盟-临沂大学）智慧树知到期末考试答案2024年

数据结构（山东联盟-临沂大学）智慧树知到期末考试答案2024年数据结构（山东联盟-临沂大学）对一组包含10个元素的非递减有序序列，采用直接插入排序排成非递增序列，其可能的比较次数和移动次数分别是：（）

A:100,100B:100,54C:54,63D:45,44答案:54,63若要检查有向图中有无回路，除了可以利用拓扑排序算法外，下列哪种算法也可以用？（）

A:广度优先搜索B:深度优先搜索C:Dijkstra算法D:Prim算法答案:深度优先搜索若用大小为6的数组来实现循环队列，且当前front和rear的值分别为0和4。当从队列中删除两个元素，再加入两个元素后，front和rear的值分别为多少？（）

A:2和4B:2和6C:2和0D:2和2答案:2和0假设有5个整数以1、2、3、4、5的顺序被压入堆栈，且出栈顺序为3、5、4、2、1，那么为了获得这样的输出，堆栈大小至少为：（）

A:3B:2C:5D:4答案:4关于图的邻接矩阵，下列哪个结论是正确的？（）

A:无向图的邻接矩阵可以是不对称的，也可以是对称的B:有向图的邻接矩阵可以是对称的，也可以是不对称的C:无向图的邻接矩阵总是不对称的D:有向图的邻接矩阵总是不对称的答案:有向图的邻接矩阵可以是对称的，也可以是不对称的给定初始待排序列{15，9，7，8，20，-1，4}。如果希尔排序第一趟结束后得到序列为{15，-1，4，8，20，9，7}，则该趟增量为：（）

A:2B:4C:3D:1答案:4若采用带头、尾指针的单向链表表示一个堆栈，那么该堆栈的栈顶指针top应该如何设置？（）

A:随便哪端作为top都可以B:将链表头设为topC:其余说法都不对D:将链表尾设为top答案:将链表头设为top对于一个具有N个顶点的无向图，要连通所有顶点至少需要多少条边？（）

A:N+1B:N−1C:ND:N/2答案:N−1已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是：（）

A:52B:119C:111D:39答案:111在一个无向图中，所有顶点的度数之和等于所有边数的多少倍？

（）

A:4B:2C:1/2D:1答案:2有一个四叉树，度2的结点数为4，度3的结点数为2，度4的结点数为1。问该树的叶结点个数是多少？

（）

A:8B:20C:18D:12答案:12下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(NlogN)的是：（）

A:直接选择排序B:冒泡排序C:堆排序D:快速排序答案:堆排序下面的叙述正确的是（）

A:线性表在顺序存储时，查找第i个元素的时间同i的值成正比B:线性表在顺序存储时，所有元素的存储单元是连续的C:线性表在链式存储时，所有元素节点的存储单元是连续的D:线性表在链式存储时，删除第i个元素的时间同i的值无关答案:无若数据元素序列{12,13,8,11,5,16,2,9}是采用下列排序方法之一得到的第一趟排序后的结果，则该排序算法只能是：（）

A:归并排序B:选择排序C:堆排序D:快速排序答案:归并排序用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是？

（）

A:拓扑有序B:无序的C:其余选项都不对D:逆拓扑有序答案:逆拓扑有序若线性表最常用的操作是存取第i个元素及其前驱的值，则采用()存储方式节省时间。

A:双向链表B:顺序表C:单链表D:单循环链表答案:顺序表图的广度优先遍历类似于二叉树的：（）

A:中序遍历B:层次遍历C:后序遍历D:先序遍历答案:层次遍历设每个d叉树的结点有d个指针指向子树，有n个结点的d叉树有多少空链域？（）

A:n(d−1)B:其余选项都不是C:n(d−1)+1D:nd答案:n(d−1)+1在下述结论中，正确的是：①只有2个结点的树的度为1；②二叉树的度为2；③二叉树的左右子树可任意交换；④在最大堆（大顶堆）中，从根到任意其它结点的路径上的键值一定是按非递增有序排列的。（）

A:②③④B:②④C:①②③D:①④答案:①④如果一棵非空k（k≥2）叉树T中每个非叶子结点都有k个孩子，则称T为正则k叉树。若T有m个非叶子结点，则T中的叶子结点个数为：（）

A:m(k−1)−1B:m(k−1)+1C:m(k−1)D:mk答案:m(k−1)+1给定输入序列{4371,1323,6173,4199,4344,9679,1989}以及散列函数

h(X)=X%10。如果用大小为10的散列表，并且用链地址法解决冲突，则输入各项经散列后在表中的下标为：（-1表示相应的插入无法成功）（）

A:1,3,3,9,4,9,9B:1,3,4,9,5,0,8C:1,3,4,9,7,5,-1D:1,3,4,9,5,0,2答案:1,3,3,9,4,9,9如果二叉树的后序遍历结果是FDEBGCA，中序遍历结果是FDBEACG，那么该二叉树的前序遍历结果是什么？（）

A:ABDFEGCB:ABCDEFGC:ABDFECGD:ABDEFCG答案:ABDFECG设树T的度为4，其中度为1、2、3、4的结点个数分别为4、2、1、1。则T中有多少个叶子结点？

（）

A:10B:8C:6D:4答案:8将5个字母ooops按此顺序入栈，则有多少种不同的出栈顺序可以仍然得到ooops（）

A:1B:3C:5D:6答案:5在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是（）

A:122B:82C:41D:113答案:82数据序列{3,1,4,11,9,16,7,28}只能是下列哪种排序算法的两趟排序结果？（）

A:插入排序B:冒泡排序C:快速排序D:堆排序答案:快速排序将元素序列{18，23，11，20，2，7，27，33，42，15}按顺序插入一个初始为空的、大小为11的散列表中。散列函数为：H(Key)=Key%11，采用线性探测法处理冲突。问：当第一次发现有冲突时，散列表的装填因子大约是多少？（）

A:0.73B:0.64C:0.27D:0.45答案:0.45如果二叉树的前序遍历结果是12345，后序遍历结果是32541，那么该二叉树的中序遍历结果是什么？（）

A:23145B:24135C:无法确定D:23154答案:无法确定已知无向图G含有16条边，其中度为4的顶点个数为3，度为3的顶点个数为4，其他顶点的度均小于3。图G所含的顶点个数至少是：（）

A:15B:11C:10D:13答案:11已知一棵二叉树的先序遍历结果是ABC，则以下哪个序列是不可能的中序遍历结果：（）

A:CABB:CBAC:ABCD:BAC答案:CAB在对N个元素进行排序时，基于比较的算法中，其“最坏时间复杂度”中最好的是：（）

A:O(NlogN)B:O(N)C:O(N​2​​)D:O(logN)答案:O(NlogN)设有1000个元素的有序序列，如果用二分插入排序再插入一个元素，则最大比较次数是：（）

A:500B:10C:999D:1000答案:10某二叉树的前序和后序遍历序列正好相反，则该二叉树一定是

（）

A:高度等于其结点数B:空或只有一个结点C:任一结点无左孩子D:任一结点无右孩子答案:高度等于其结点数现有长度为7、初始为空的散列表HT，散列函数H(k)=k%7，用线性探测再散列法解决冲突。将关键字22,43,15依次插入到HT后，查找成功的平均查找长度是：（）

A:1.5B:3C:1.6D:2答案:2用二分查找从100个有序整数中查找某数，最坏情况下需要比较的次数是：（）

A:10B:50C:99D:7答案:7采用线性探测法解决冲突时所产生的一系列后继散列地址：（）

A:必须小于等于原散列地址B:对地址在何处没有限制C:必须大于等于原散列地址D:可以大于或小于但不等于原散列地址答案:可以大于或小于但不等于原散列地址在有n（n>1000）个元素的升序数组A中查找关键字x。查找算法的伪代码如下所示：k=0;while(kif(kelseif(k-1elseif(k-2else查找失败;本算法与二分查找（折半查找）算法相比，有可能具有更少比较次数的情形是：（）

A:当x接近数组开头处B:当x位于数组中间位置C:当x接近数组结尾处D:当x不在数组中答案:当x接近数组开头处设高为h的二叉树（规定叶子结点的高度为1）只有度为0和2的结点，则此类二叉树的最少结点数和最多结点数分别为：（）

A:2h−1+1,

2h−1B:2h−1,

2h−1−1C:2h−1,

2h−1D:2h,

2h−1答案:2h−1,

2h−1若一个栈的输入序列为1，2，3，…，N，输出序列的第一个元素是i，则第j个输出元素是j−i−1。（）

A:正确B:错误答案:错误任何二叉搜索树中同一层的结点从左到右是有序的（从小到大）。（）

A:错B:对答案:对希尔排序是不稳定的算法。（）

A:错误B:正确答案:正确在散列中，函数“插入”和“查找”具有同样的时间复杂度（）

A:正确B:错误答案:正确如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则G中一定有回路。（）

A:错B:对答案:错无向连通图边数一定大于顶点个数减1。（）

A:对B:错答案:错对N个记录进行快速排序，在最好的情况下，其时间复杂度是O(NlogN)。（）

A:对B:错答案:对在用数组表示的循环队列中，front值一定小于等于rear的值。（）

A:正确B:错误答案:错误如果表示有向图的邻接矩阵是对称矩阵，则该有向图一定是完全有向图（）

A:错误B:正确答案:错误通过对堆栈S操作：Push(S,1),Push(S,2),Pop(S),Push(S,3),Pop(S),Pop(S)。输出的序列为：123。（）

A:对B:错答案:错对于顺序存储的长度为N的线性表，删除第一个元素和插入最后一个元素的时间复杂度分别对应为O(1)和O(N)。（）

A:错B:对答案:错Prim算法是通过每步添加一条边及其相连的顶点到一棵树，从而逐步生成最小生成树。（）

A:对B:错答案:对若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用单链表存储最节省时间。（）

A:错B:对答案:错已知一棵二叉树的先序遍历结果是CBA,则ACB不可能是中序遍历结果。（）

A:错误B:正确答案:正确二叉树的前序遍历并不能唯一确定这棵树，但是如果我们还知道该树的