对含有n (n>0)个记录的文件进行外部排序,采用置换-选择排序生成初始归并段时需要使用一个工作,工作区中能保存m个记录,请回答下列问题。
(1) 如果文件中有19条记录,其关键字分别为:51,94,37,92,14,63,15,99,48,56,23,60,31,17,43,8,90,166,100,当m=4时,可生成几个初试归并段,各是什么?
(2)对任意m (n≫m>0),生成的第一个初试归并段长度最大值和最小值分别多少?
⑴ 对题目所给关键字序列进行置换-选择排序:
初始FI:51,94,37,92,14,63,15,99,48,56,23,60,31,17,43,8,90,166,100;
WA和FO均为空。
第一趟:
从FI读4个记录到WA:51,94,37,92
从WA选择最小的值,记不MINIMAX,输出到FO:37
从FI读1个记录到WA:51,94,92,14
从WA选择最小,但不小于当前MINIMAX的值,输出到FO:37,51
重复上面两步操作,依次得:
WA:94,92,14,63
FO:37,51,63
WA:94,92,14,15
FO:37,51,63,92
WA:94,14,15,99
FO:37,51,63,92,94
WA:14,15, 99,48
FO:37,51,63,92,94,99
WA:14,15,48,56
此时已选不出新的MINIMAX,得第一个归并段:37,51,63,92,94,99
第二趟:
WA:14,15,48,56
FO:14
WA:15,48,56,23
FO:14,15
WA:48,56,23,60
FO:14,15,23
WA:48,56,60,31
FO:14,15,23,31
WA:48,56,60,17
FO:14,15,23,31,48
WA:56,60,17,43
FO:14,15,23,31,48,56
WA:60,17,43,8
FO:14,15,23,31,48,56,60
WA:17,43,8,90
FO:14,15,23,31,48,56,60,90
WA:17,43,8,166
FO:14,15,23,31,48,56,60,90,166
WA:17,43,8,100
此时已选不出新的MINIMAX,得第二个归并段:14,15,23,31,48,56,60,90,166
第三趟:
WA:17,43,8,100
FO:8
WA:17,43,100
FO:8,17
WA:43,8,100
FO:8,17,43
WA:100
FQ:8,17,43,100
最后分成三个归并段:
37,51,63,92,94,99
14,15,23,31,48,56,60,90,166
8,17,43,100
(2) 设输入序列为x1,x2,...,xn,且所有关键字互不相同。
考虑最大值的情况:
显然,刚开始进入WA的m个关键字一定能被输出,如果后面每次进入WA的关键字都能被输出,只要该关键字恰巧大于刚刚输出的关键字即可。特殊地,取x1<x2<...<xn,则所有的关键字都能被输出到第一个归并段,此时第一归并段的长度取最大值n。
再考虑最小值的情况:
同样,刚开始进入WA的m个关键字一定能被输出,如果后面每次进入WA的关键字都不能被输出,只要该关键字恰巧小于刚刚输出的关键字即可。特殊地,取x1>x2>...>xn,则只有前m个关键字被输出到第一个归并段,此时第一归并段的长度取最小值m。
假设初始待排序文件为输入文件FI,初始归并段文件为输出文件FO,内存工作区为WA,FO和WA初始为空,设内存工作区WA的容量可容纳w个记录。则置换-选择排序的操作过程为:
① 从FI输入w个记录到缓冲区WA;
② 从WA中选出其中关键字取最小值的记录,记为MINIMAX记录;
③ 将MINIMAX记录输出到FO中去;
④ 若FI不空,则从FI输入下一个记录到WA中;
⑤ 从WA中所有比MINIMAX记录的关键字大的记录中选出最小关键字记录,作为新的MINIMAX记录;
⑥ 重复③~⑤,直到在WA中选不出新的MINIMAX为止,由此得到一个初始归并段,输出归并段结束标志到FO中;
⑦ 重复②~⑥,直到WA为空,由此得到全部初始归并段。
已知有向图G采用邻接矩阵存储,其定义如下:
typedef struct{//图的定义
int numberVertices,numEgges;//图中实际的顶点数和边数
char verticesList[maxV];//顶点表
int edge[maxV][maxV];//邻接矩阵
}MGraph;
将图中出度大于入度的顶点称为K顶点,如图,a和b都是K顶点,设计算法 int printVertices(MGraph G)对给定任意非空有向图G,输出G中所有K顶点,并返回K顶点的个数。
(1)给出算法的设计思想。
(2)根据算法思想,写出C/C++描述,并注释。
⑴ 有向图G采用邻接矩阵G.Edge表示,G.Edge[i][j]=1表示存在有向边(i,j),G.Edge[i][j]=0 表示不存在有向边(i,j).
本题算法基本设计思想如下:
第一步:统计所有顶点的入度和出度。若存在边(i,j),即G.Edge[i][j]=1,则顶点i 的出度加1,顶点j的入度加1。若不存在边(i,j),即G.Edge[i][j]=0 ,则顶点i 的出度不变,顶点j 的入度不变。
第二步:统计所有顶点中出度大于入度的顶点的个数,并输出。
(2) C语言代码:
int printVertices(MGraph G) {
int indegrees[G.numVertices];
int outdegrees[G.numVertices];
memset(indegrees, 0, sizeof(indegrees));
memset(outdegrees, 0, sizeof(outdegrees));
// 遍历无向图统计所有点的出度和入度
for (int i = 0; i < G.numVertices; i++) {
for (int j = 0; j < G.numVertices; j++) {
outdegrees[i] += G.Edge[i][j];
indegrees[j] += G.Edge[i][j];
}
}
int count = 0;
// 遍历indegrees和outdegrees数组统计出度大于入度的顶点
for (int i = 0; i < G.numVertices; i++) {
if (outdegrees[i] > indegrees[i]) {
printf("%d", i);
count++;
}
}
return count;
}
使用快速排序算法对数据进行升序排序, 若经过一次划分后得到的数据序列是 68, 11, 70, 23, 80, 77, 48, 81, 93, 88,则该次划分的轴枢【】。
A、11
B、70
C、80
D、81
快速排序算法通过多次比较和交换来实现,其排序流程如下:
(1)首先设定一个分界值,通过该分界值将数组分成左右两部分。
(2)将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于分界值,而右边部分中各元素都大于或等于分界值。
(3)然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。
A选项,枢轴为11 ,左边 68 > 11 。错误。
B选项,枢轴为70 ,右边 23 < 70 。错误。
C选项,枢轴为80,右边 48 < 80 。错误。
D选项,枢轴为81。正确。
下列排序算法中,不稳定的是【 】。
Ⅰ. 希尔排序
Ⅱ. 归并排序
Ⅲ. 快速排序
Ⅳ. 堆排序
Ⅴ. 基数排序
A、仅Ⅰ和Ⅱ
B、仅Ⅱ和Ⅴ
C、仅Ⅰ、Ⅲ和Ⅳ
D、仅Ⅲ、Ⅳ和Ⅴ
假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。
在八大排序算法中,
稳定的排序有:插入排序、冒泡排序、归并排序、基数排序。
不稳定的排序有:选择排序、希尔排序、快速排序、堆排序。
现有长度为 5,初始为空的散列表HT,散列函数H(k)=(k+4) mod 5, 用线性探查再散列法解决冲突。若将关键字序列 2022, 12, 25 依次插入HT中,然后删除关键字 25 ,则HT中查找失败的平均查找长度为【 】。
A、1
B、1.6
C、1.8
D、2.2
1)插入2022,H(2022)=(2022+4) mod 5 =1;1位为空,可插入;
2)插入12,H(12)=(12+4) mod 5 =1,冲突,采用线性探测法,每次向右探索一位,当前为空,可插入;
3)插入25,H(25)=(25+4) mod 5 =4,4位为空,可插入。
4)删除25,该散列表采用线性探测再散列法,属于开放寻址法,从中删除关键字时,不能简单地置NIL,而是作一个标记,如DELETED,简记为D。
5)计算查找失败时的平均查找长度:
查找元素失败统计项数目与散列表空间大小和散列函数均有关,这里取5。
按照冲突处理方法,计算出每种情况查找失败需要的次数,即失败查找长度:
散列到0:
查找次数为1;
散列到1:
查找次数为3;
散列到2:
查找次数为2;
散列到3:
查找次数为1;
散列到4:
查找次数为2。
查找失败时的平均查找长度为:(1+3+2+1+2)/5=1.8