/ 知识库     / 试卷库

考研2023年计算机统考( )

对含有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为空,由此得到全部初始归并段。

考研2023年计算机统考( )

已知有向图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;

}

考研2023年计算机统考( )

使用快速排序算法对数据进行升序排序, 若经过一次划分后得到的数据序列是 68, 11, 70, 23, 80, 77, 48, 81, 93, 88,则该次划分的轴枢【】。

A、11

B、70

C、80

D、81

81

快速排序算法通过多次比较和交换来实现,其排序流程如下:

(1)首先设定一个分界值,通过该分界值将数组分成左右两部分。

(2)将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于分界值,而右边部分中各元素都大于或等于分界值。 

(3)然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。 

(4)重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。

A选项,枢轴为11 ,左边 68 > 11 。错误。

B选项,枢轴为70 ,右边 23 < 70 。错误。

C选项,枢轴为80,右边 48 < 80 。错误。

D选项,枢轴为81。正确。

考研2023年计算机统考( )

下列排序算法中,不稳定的是【 】。

Ⅰ. 希尔排序

Ⅱ. 归并排序

Ⅲ. 快速排序

Ⅳ. 堆排序

Ⅴ. 基数排序

A、仅Ⅰ和Ⅱ

B、仅Ⅱ和Ⅴ

C、仅Ⅰ、Ⅲ和Ⅳ

D、仅Ⅲ、Ⅳ和Ⅴ

仅Ⅰ、Ⅲ和Ⅳ

假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。

在八大排序算法中,

稳定的排序有:插入排序、冒泡排序、归并排序、基数排序。

不稳定的排序有:选择排序、希尔排序、快速排序、堆排序。

考研2023年计算机统考( )

现有长度为 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.8

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