提示:内容已经过期谨慎付费，点击上方查看最新答案
数据结构（山东联盟-临沂大学）
对一组包含10个元素的非递减有序序列，采用直接插入排序排成非递增序列，其可能的比较次数和移动次数分别是：（）
- 若要检查有向图中有无回路，除了可以利用拓扑排序算法外，下列哪种算法也可以用？（）
- 若用大小为6的数组来实现循环队列，且当前front和rear的值分别为0和4。当从队列中删除两个元素，再加入两个元素后，front和rear的值分别为多少？（）
- 假设有5个整数以1、2、3、4、5的顺序被压入堆栈，且出栈顺序为3、5、4、2、1，那么为了获得这样的输出，堆栈大小至少为：（）
给定有权无向图的邻接矩阵如下，其最小生成树的总权重是：（）
- 关于图的邻接矩阵，下列哪个结论是正确的？（）
- 给定初始待排序列{ 15，9，7，8，20，-1，4 }。如果希尔排序第一趟结束后得到序列为{ 15，-1，4，8，20，9，7 }，则该趟增量为：（）
若采用带头、尾指针的单向链表表示一个堆栈，那么该堆栈的栈顶指针top应该如何设置？（）
- 对于一个具有N个顶点的无向图，要连通所有顶点至少需要多少条边？（）
- 若一个栈的入栈序列为1、2、3、…、N，其输出序列为p1、p2、p3、…、pN。若p1=N，则pi为： （）
- 已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是：（）
- 在一个无向图中，所有顶点的度数之和等于所有边数的多少倍？ （）
- 有一个四叉树，度2的结点数为4，度3的结点数为2，度4的结点数为1。问该树的叶结点个数是多少？ （）
- 下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(NlogN)的是：（）
下面的叙述正确的是（ ）
- 若数据元素序列{ 12, 13, 8, 11, 5, 16, 2, 9 }是采用下列排序方法之一得到的第一趟排序后的结果，则该排序算法只能是：（）
用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是？ （）
- 若线性表最常用的操作是存取第i个元素及其前驱的值，则采用( )存储方式节省时间。
- 图的广度优先遍历类似于二叉树的：（）
设每个d叉树的结点有d个指针指向子树，有n个结点的d叉树有多少空链域？（）
- 在下述结论中，正确的是：① 只有2个结点的树的度为1；
② 二叉树的度为2；
③ 二叉树的左右子树可任意交换；
④ 在最大堆（大顶堆）中，从根到任意其它结点的路径上的键值一定是按非递增有序排列的。（） - 如果一棵非空k（k≥2）叉树T中每个非叶子结点都有k个孩子，则称T为正则k叉树。若T有m个非叶子结点，则T中的叶子结点个数为：（）
给定输入序列 {4371, 1323, 6173, 4199, 4344, 9679, 1989} 以及散列函数 h(X)=X%10。如果用大小为10的散列表，并且用链地址法解决冲突，则输入各项经散列后在表中的下标为：（-1表示相应的插入无法成功）（）
- 如果二叉树的后序遍历结果是FDEBGCA，中序遍历结果是FDBEACG，那么该二叉树的前序遍历结果是什么？（）
- 设树T的度为4，其中度为1、2、3、4的结点个数分别为4、2、1、1。则T中有多少个叶子结点？ （）
- 将5个字母ooops按此顺序入栈，则有多少种不同的出栈顺序可以仍然得到ooops（）
在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是（）
- 数据序列{ 3, 1, 4, 11, 9, 16, 7, 28 }只能是下列哪种排序算法的两趟排序结果？（）
- 将元素序列{18，23，11，20，2，7，27，33，42，15}按顺序插入一个初始为空的、大小为11的散列表中。散列函数为：H(Key)=Key%11，采用线性探测法处理冲突。问：当第一次发现有冲突时，散列表的装填因子大约是多少？（）
- 如果二叉树的前序遍历结果是12345，后序遍历结果是32541，那么该二叉树的中序遍历结果是什么？（）
- 已知无向图G含有16条边，其中度为4的顶点个数为3，度为3的顶点个数为4，其他顶点的度均小于3。图G所含的顶点个数至少是：（）
已知一棵二叉树的先序遍历结果是ABC，则以下哪个序列是不可能的中序遍历结果：（）
- 在对N个元素进行排序时，基于比较的算法中，其“最坏时间复杂度”中最好的是：（）
- 设有1000个元素的有序序列，如果用二分插入排序再插入一个元素，则最大比较次数是：（）
- 某二叉树的前序和后序遍历序列正好相反，则该二叉树一定是 （）
- 现有长度为 7、初始为空的散列表HT，散列函数H(k)=k%7，用线性探测再散列法解决冲突。将关键字 22, 43, 15 依次插入到HT后，查找成功的平均查找长度是：（）
- 用二分查找从100个有序整数中查找某数，最坏情况下需要比较的次数是：（）
- 采用线性探测法解决冲突时所产生的一系列后继散列地址：（）
- 在有n（n>1000）个元素的升序数组A中查找关键字x。查找算法的伪代码如下所示：
k = 0;
while ( kif ( k else if ( k-1 else if ( k-2 else 查找失败;
本算法与二分查找（折半查找）算法相比，有可能具有更少比较次数的情形是：（） 设高为h的二叉树（规定叶子结点的高度为1）只有度为0和2的结点，则此类二叉树的最少结点数和最多结点数分别为：（）
- 若一个栈的输入序列为1，2，3，…，N，输出序列的第一个元素是i，则第j个输出元素是j−i−1。（）
- 任何二叉搜索树中同一层的结点从左到右是有序的（从小到大）。（）
希尔排序是不稳定的算法。（）
在散列中，函数“插入”和“查找”具有同样的时间复杂度（）
- 如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则G中一定有回路。（）
- 无向连通图边数一定大于顶点个数减1。（）
对N个记录进行快速排序，在最好的情况下，其时间复杂度是O(NlogN)。（）
- 在用数组表示的循环队列中，front值一定小于等于rear的值。（）
如果表示有向图的邻接矩阵是对称矩阵，则该有向图一定是完全有向图（）
- 通过对堆栈S操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为：123。（）
- 对于顺序存储的长度为N的线性表，删除第一个元素和插入最后一个元素的时间复杂度分别对应为O(1)和O(N)。（）
- Prim 算法是通过每步添加一条边及其相连的顶点到一棵树，从而逐步生成最小生成树。（）
若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用单链表存储最节省时间。（）
已知一棵二叉树的先序遍历结果是CBA, 则ACB不可能是中序遍历结果。（）
二叉树的前序遍历并不能唯一确定这棵树，但是如果我们还知道该树的根结点是那一个，则可以确定这棵二叉树（ ）
- 用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。（）
- 栈和队列的存储方式，既可以是顺序方式，也可以是链式方式。（）
如果一个无向图有多于一个连通分量，则该图必不连通（）
- 在任一有向图中，所有顶点的入度之和等于所有顶点的出度之和。（）
- 若A和B都是一棵二叉树的叶子结点，则存在这样的二叉树，其前序遍历序列为...A...B...，而中序遍历序列为...B...A…。（）
A:100, 100 B:100, 54 C:54, 63 D:45,44
答案:54,63
A:广度优先搜索 B:深度优先搜索 C:Dijkstra算法 D:Prim算法
答案:深度优先搜索
A:2和4 B:2和6 C:2和0 D:2和2
答案:2和4
A:3 B:2 C:5 D:4
答案:4
A:20 B:8 C:22 D:15
答案:23
A:无向图的邻接矩阵可以是不对称的，也可以是对称的 B:有向图的邻接矩阵可以是对称的，也可以是不对称的 C:无向图的邻接矩阵总是不对称的 D:有向图的邻接矩阵总是不对称的
A:2 B:4 C:3 D:1
AI参考:正确答案是C：3。希尔排序是一种分组插入排序，增量序列为g1，g2，…，gn，其中gi由小到大。增量序列在希尔排序中是逐步减小的，第一趟增量为g1=3（对于题目初始序列3是不合适的），由于排序的第一趟对整个序列的排列进行了4次划分（平均分配，排序至剩下9，然后整体继续按照初始增量对这剩下的序列排序，此次减少2个数即增加分组大小进行第二次分组）。当序列分布均衡（数据少的那一部分数组可以排的很短时）再次进行分组插入排序时，可以减少增量的大小。因此本题中增量为3。所以正确选项为C。'
A:随便哪端作为top都可以 B:将链表头设为top C:其余说法都不对 D:将链表尾设为top
A:N+1 B:N−1 C:N D:N/2
AI参考:正确答案是B:N−1。一个具有N个顶点的无向图，要连通所有顶点至少需要N-1条边。因为连通所有顶点需要从一个顶点出发，经过一条边到达另一个顶点，直到所有顶点都被连通，所以要满足图的所有顶点连通至少需要一个起点的边，再加上从其他顶点到达起点的边。因此答案为B。'
A:i B:不确定 C:n−i D:n−i+1
A:52 B:119 C:111 D:39
A:4 B:2 C:1/2 D:1
AI参考:正确答案是D：1。在一个无向图中，所有顶点的度数之和等于所有边的数量，所以所有顶点的度数之和等于所有边数的1倍。因此，答案为D。'
A:8 B:20 C:18 D:12
A:直接选择排序 B:冒泡排序 C:堆排序 D:快速排序
A:线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 B:线性表在顺序存储时，所有元素的存储单元是连续的 C:线性表在链式存储时，所有元素节点的存储单元是连续的 D:线性表在链式存储时，删除第i个元素的时间同i 的值无关
AI参考:下面的叙述正确的是（B:线性表在顺序存储时，所有元素的存储单元是连续的）。线性表在顺序存储时，所有元素的存储单元是连续的，这样可以快速进行随机访问，即查找第i个元素的时间同i的值无关。而链式存储时，元素的存储单元不一定是连续的，节点之间的链接可能存在多种情况，这会影响到删除第i个元素的时间。因此，选项B是正确的。选项A、C、D都存在一定的局限性，不能完全描述线性表在顺序存储时的特性。'
A:归并排序 B:选择排序 C:堆排序 D:快速排序
AI参考:根据题意，数据元素序列{ 12, 13, 8, 11, 5, 16, 2, 9 }第一趟排序后的结果。考虑到选项，我们可以逐一分析：A. 归并排序：在归并排序中，通常会采用分治策略，将大问题分解为小问题来解决，然后逐步合并得到最终结果。题目中的数据元素序列只有几个元素，且都是较小的整数，不太可能使用归并排序进行排序。B. 选择排序：选择排序是一种简单直观的排序算法。在每一趟排序中，都会从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。但题目中的数据元素序列并未显示出明显的不规则性或差异性，不太可能选择排序算法进行排序。C. 堆排序：堆排序是一种树形选择排序，是对直接选择排序的有效改进。在堆排序中，将待排序序列构造成一个大顶堆（或小顶堆），此时序列的第一个元素将是最大（或最小）的元素，将其与最后一个元素交换得到最终结果。考虑到题目中的数据元素序列是一个有序序列{ 12, 13, 8, 11, 5, 16, 2, 9 }，我们可以得出这个序列是可以通过堆排序算法得到的有序结果。D. 快速排序：快速排序是一种使用分治法（Divide and conquer）的排序算法。它的工作原理是，通过一趟排序将待排序列分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再按照这种方法对这两部分继续进行排序，以达到整个序列有序。但考虑到题目中的数据元素序列为有序序列{ 12, 13, 8, 11, 5, 16, 2, 9 }，无法直接通过快速排序进行排序。综上所述，选项C“堆排序”符合题意，即数据元素序列{ 12, 13, 8, 11, 5, 16, 2, 9 }是采用堆排序方法之一得到的第一趟排序后的结果。'
A:拓扑有序 B:无序的 C:其余选项都不对 D:逆拓扑有序
A:双向链表 B:顺序表 C:单链表 D:单循环链表
A:中序遍历 B:层次遍历 C:后序遍历 D:先序遍历
A:n(d−1) B:其余选项都不是 C:n(d−1)+1 D:nd
AI参考:正确答案是C：n(d−1)+1。每个d叉树的结点有d个指针指向子树，有n个结点的d叉树，除根节点外有n个节点，因此除了指向根节点的指针外，剩下的指针个数为n(d−1)，加上根节点自身的一条链域，因此空链域的个数为n(d−1)+1。因此，正确答案为C。'
A:②③④ B:②④ C:①②③ D:①④
A:m(k−1)−1 B:m(k−1)+1 C:m(k−1) D:mk
A:1, 3, 3, 9, 4, 9, 9 B:1, 3, 4, 9, 5, 0, 8 C:1, 3, 4, 9, 7, 5, -1 D:1, 3, 4, 9, 5, 0, 2
A:ABDFEGC B:ABCDEFG C:ABDFECG D:ABDEFCG
A:10 B:8 C:6 D:4
A:1 B:3 C:5 D:6
A:122 B:82 C:41 D:113
A:插入排序 B:冒泡排序 C:快速排序 D:堆排序
A:0.73 B:0.64 C:0.27 D:0.45
A:23145 B:24135 C:无法确定 D:23154
A:15 B:11 C:10 D:13
A:CAB B:CBA C:ABC D:BAC
A:O(NlogN) B:O(N) C:O(N2) D:O(logN)
A:500 B:10 C:999 D:1000
A:高度等于其结点数 B:空或只有一个结点 C:任一结点无左孩子 D:任一结点无右孩子
A:1.5 B:3 C:1.6 D:2
A:10 B:50 C:99 D:7
A:必须小于等于原散列地址 B:对地址在何处没有限制 C:必须大于等于原散列地址 D:可以大于或小于但不等于原散列地址
A:当x接近数组开头处 B:当x位于数组中间位置 C:当x接近数组结尾处 D:当x不在数组中
A:2h−1+1, 2h−1 B:2h−1, 2h−1−1 C:2h−1, 2h−1 D:2h, 2h−1
A:对 B:错
A:错 B:对
A:错 B:对
A:对 B:错
A:错 B:对
A:对 B:错
A:对 B:错
AI参考:答案是A：对。快速排序是一种常用的排序算法，其时间复杂度在最坏的情况下是O(n^2)，但在最好的情况下是O(n log n)。在这种情况下，排序算法利用了数据集的有序性质，可以将排序过程分为两部分，第一部分只遍历一次数组就能完成排序，第二部分只需比较两次即可完成排序。因此，最好的情况下，快速排序的时间复杂度为O(n log n)。因此，题目中的描述是正确的。'
A:对 B:错
A:错 B:对
A:对 B:错
A:错 B:对
AI参考:正确答案是B:对。对于顺序存储的线性表，删除第一个元素只需将头指针向前移动一位，时间复杂度为O(1)。插入最后一个元素时，需要将尾指针向前移动一位并添加新元素，时间复杂度为O(N)。因此，这个判断题是正确的。'
A:对 B:错
A:错 B:对
A:错 B:对
A:错 B:对
A:对 B:错
A:对 B:错
A:对 B:错
A:错 B:对
A:错 B:对
温馨提示支付 ￥2.60 元后可查看付费内容,请先翻页预览!
