数据结构与算法（B） 期中后MOOC课程小测 1300012864 鲁泠溪

图 Question 1 下图中的强连通分量的个数为多少个？ 答案：3 考点：强连通分量的概念

Question 2 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前， 则下列情形不可能出现的是（ ）。 A. G中有边(Vi，Vj) B.G中有一条从Vj到Vi的路径 C.G中没有边(Vi,Vj) D.G中有一条从Vi到Vj的路径 答案：B 考点：拓扑排序

Question 3 无向图G=(V,E)，其中： V={a,b,c,d,e,f}, E={(a,b),(a,e),(a,c),(b,e),(c,f),(f, d),(e,d)}，对该图进行深度优先遍历（优先访问编 号小的结点），得到的顶点序列为？注意：答案中 没有空格 答案：abedfc 考点：图的深搜

Question 4 下列关于最短路算法的说法正确的有： A.当图中不存在负权边时，Dijkstra算法能求出每 对顶点间最短路径。 B. Dijkstra算法不能用于每对顶点间最短路计算。 C. 当图中存在负权回路时，Dijkstra算法也一定能 求出源点到所有点的最短路。 答案：A 考点：Dijkstra算法的应用范围

Question 5 请使用Prim算法从结点0出发求下图的最小生成树， 依次写出每次被加入到最小生成树中边的编号（如 果同时存在多条边满足要求，选择编号最小的）。 顶点a到顶点b (a < b)之间的边编号为ab，例如图 中权值为1的边编号为02。(不同编号之间用一个空 格分隔）  答案：02 25 35 12 14 考点：最小生成树的Prim算法

内排序（1） Question 1 已知一组元素的排序码为(46，74，16，53，14， 26，40，38，86，65，27，34)，利用直接插入 排序的方法（第一个数字不用插入）,写出第四次向 前面有序表插入一个元素后的排列结果。 注意：数 字中间用一个空格隔开，不要写逗号和括号。答案 一共有12个数字。 答案： 14 16 46 53 74 26 40 38 86 65 27 34 考点：直接插入排序

Question 2 对于序列{E，A，S，Y，Q，U，E，S，T，I，O， N}，以{6，3，1}为增量采用Shell排序。头两趟{6， 3}增量排序后，关键字的累积比较次数为()。 答案：6+11=17 考点：Shell排序、直接插入排序

Question 3 某整型数组Ａ的１０个元素值依次为 6,2,9,7,3,8,4,5,0,1,用快速排序方法（课程中介 绍的快速排序实现方式），取第一个元素值６作为 分割数，将Ａ中元素由小到大排序，写出快速排序 第一次分隔后Ａ中的结果()。数字中间用一个空格 隔开。 答案：1 2 0 5 3 4 6 8 7 9 考点：快速排序

Question 4 某整型数组Ａ有11个元素，用最大堆排序方法，将 Ａ中元素构造成一个最大堆，该最大堆的元素序列 为X,T,S,P,L,R,A,M,O,E,E ,试写出将第一个选出的 数据与Ａ的最后位置上的元素交换后，将Ａ重新调 整成最大堆后，堆的元素序列为()。中间用一个空 格隔开。 答案：T P S O L R A M E E 考点：堆排序

Question 5 n个记录的直接插入排序所需记录关键码的最大比较次 数为（ ）。 A.n^2/2 B.nlog2n C.n(n−1)/2 D. n−1 答案：C 考点：直接插入排序

内排序（2） Question 1 请问下面哪些操作在已排序数据上实施比在无序的 数据上快()？ A.计算标准差 B. 计算算术平均值 C.找中位数 D.找最小值 答案：CD 考点：统计性质

Question 2 对初始状态为递增的表按递增顺序排序，最省时间 的是（ ）算法 A.归并排序 B.堆排序 C.插入排序 D.快速排序 答案：C 考点：不同排序直接的比较

Question 3 大部分排序算法是通过不断交换记录来减小序列中 的逆置数，从而实现排序。假设有n个记录，那么 交换序列中两个不同的记录，最多能减少()个逆置？ 答案：2*n-3 考点：算数？

Question 4 对于排序算法特性的叙述正确的是() A.选择排序需要访问那些已排好序的记录 B. shell排序过程中，当对确定规模的这些小序列 进行插入排序时，要访问序列中的所有记录 C. 归并排序过程中，递归树上每个层次的归并操作 不需要访问序列中的所有记录 D.快速排序过程中，递归树上根据深度划分的每个 层次都要访问序列中的所有记录 答案：BD 考点：不同排序算法的性质

Question 5 15个记录的冒泡排序算法所需最大交换次数为 ______，最小交换次数为______。 注意：答案中， 两个数字之间用一个空格隔开，其余不含任何符号。 答案：105 0 考点：冒泡排序

检索 Question 1 在包含n个关键码的线性表里进行顺序检索，若检索第i 个关键码的概率为pi，pi如下分布：  pi=2−i(1≤i≤n) 求平均检索长度。 A.2−1/(2^(n−1)) B.2−(n+2)/(2^(n−1)) C.2−1/2^n D.2−(n+2)/2^n 答案：D（答案好像给错了..） 考点：顺序检索

Question 2 给定关键码序列26, 25, 20, 33, 21, 24, 45, 204, 42, 38, 29, 31，用散列法进行存储(本题采用闭散列方法 解决冲突)，规定负载因子α=0.4。 请给出最合理的除 余法的散列函数。 A.H(key)=key%31 B.H(key)=key%29 C.H(key)=key%30 D.H(key)=key%23 答案：B 考点：除余法散列函数

Question 3 假定把关键码K散列到有n个槽(从0到n-1编号)的散列 表中，散列表用开散列的冲突解决策略。对于下面的每 一个函数h(K)，这个函数作为散列函数可以使得插入和 检索操作一定能正常工作的有（）  注：  1.函数Random(n)返回一个0到n-1之间的随机整数(包 含这两个数在内)。  2不考虑散列函数的性能，只考虑其正确性 A.h(k)=1 B.h(k)=kmodn, 其中n是一个素数 C.h(k)=k/n, 其中k和n都是整数 D.h(k)=(k+Random(n)) 答案：AB 考点：散列函数的理论合理性

Question 4 有一个表长为m的散列表，初始状态为空，现将n (n小于m) 个不同的关键码插入到散列表中，解决 冲突的方法是用线性探测法。如果这n个关键码的 散列地址都相同，则探测的总次数是 _____________。  提示：答案为含n的表达式，如果有分号，请用/表 示，乘法不打乘号 答案：n(n-1)/2 考点：散列表的冲突解决

Question 5 在包含n个关键码的线性表里进行顺序检索，若检 索第i个关键码的概率为Pi，Pi如下分布： P1=1/2,P2=1/4,…,Pn−1=1/2^(n−1),Pn=1/2 ^n 求成功检索的平均检索长度  提示：答案是n趋于无穷大的时候的极限，所以是 一个数字 答案：2 考点：平均检索长度 等差比数列求和

推荐视频 6分钟演示15中排序方法 http://bilibili.kankanews.com/video/av68567 0/ 方便复习！ 各种排序方法的舞蹈 （仅供娱乐~）

谢谢大家！