数据结构与算法-考研试题(计算机统考 2023年置换-选择排序)

问答题（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，63FO：37，51，63WA：94，92，14，15FO：37，51，63，92WA：94，14，15，99FO：37，51，63，92，94WA：14，15， 99，48FO：37，51，63，92，94，99WA：14，15，48，56此时已选不出新的MINIMAX，得第一个归并段：37，51，63，92，94，99第二趟：WA：14，15，48，56FO：14WA：15，48，56，23FO：14，15WA：48，56，23，60FO：14，15，23WA：48，56，60，31FO：14，15，23，31WA：48，56，60，17FO：14，15，23，31，48WA：56，60，17，43FO：14，15，23，31，48，56WA：60，17，43，8FO：14，15，23，31，48，56，60WA：17，43，8，90FO：14，15，23，31，48，56，60，90WA：17，43，8，166FO：14，15，23，31，48，56，60，90，166WA：17，43，8，100此时已选不出新的MINIMAX，得第二个归并段：14，15，23，31，48，56，60，90，166第三趟：WA：17...

查看完整答案

讨论

数据结构与算法

已知有向图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++描述，并注释。

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

下列排序算法中，不稳定的是【】。Ⅰ. 希尔排序Ⅱ. 归并排序Ⅲ. 快速排序Ⅳ. 堆排序Ⅴ. 基数排序

现有长度为 5，初始为空的散列表HT，散列函数H(k)=(k+4) mod 5，用线性探查再散列法解决冲突。若将关键字序列 2022, 12, 25 依次插入HT中，然后删除关键字 25 ，则HT中查找失败的平均查找长度为【】。

对含有 600 个元素的有序顺序表进行折半查找，关键字之间的比较次数最多是【】

下列关于非空 B 树的叙述中，正确的是【】Ⅰ. 插入操作可能增加树的高度Ⅱ. 删除操作一定会导致叶结点的变化Ⅲ. 查找某关键字一定是要查找到叶结点Ⅳ. 插入的新关键字最终位于叶结点中

已知无向连通图 G 中各边的权值均为 1，下列算法中一定能够求出图 G 中从某顶点到其余各个顶点最短路径的是【】Ⅰ.普利姆算法；Ⅱ.克鲁斯卡尔算法；Ⅲ.图的广度优先搜索

已知一棵二叉树的树形如图，若其后序遍历为 f、d、b、e、c、a，则其先序列为【】

在有 6 个字符组成的字符集 S 中，各个字符出现的频次分别为 3、4、5、6、8、10，为 S 构造的哈夫曼树的加权平均长度为【】

若采用三元组表存储结构存储系数矩阵 M.则除三元组外，下列数据中还需要保存的是【】Ⅰ. M 的行数；Ⅱ. M 中包含非零元素的行数；Ⅲ. M 的列数；Ⅳ. M 中包含非零元素的列数.

置换-选择排序

下列对顺序存储的有序表 (长度为 n)实现给定操作的算法中平均时间复杂度为 O(1)的是【】

现有非空双向链表 L，其结点结构为：prer|data|next。prer 是指向前直接前驱结点的指针，next 是指向直接后继结点的指针。若要在 L 中指针 p 所指向的结点（非尾结点）之后插入指针 s 指向的新结点，则在执行了语句序列： “s->next=p->next;p->next=s”后，还要执行【】

对含有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)，生成的第一个初试归并段长度最大值和最小值分别多少？

对含有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)，生成的第一个初试归并段长度最大值和最小值分别多少？

对含有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)，生成的第一个初试归并段长度最大值和最小值分别多少？

对含有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)，生成的第一个初试归并段长度最大值和最小值分别多少？

对含有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)，生成的第一个初试归并段长度最大值和最小值分别多少？

对含有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)，生成的第一个初试归并段长度最大值和最小值分别多少？

对含有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)，生成的第一个初试归并段长度最大值和最小值分别多少？

对含有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)，生成的第一个初试归并段长度最大值和最小值分别多少？

外部排序

对含有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)，生成的第一个初试归并段长度最大值和最小值分别多少？

对含有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)，生成的第一个初试归并段长度最大值和最小值分别多少？

对含有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)，生成的第一个初试归并段长度最大值和最小值分别多少？

对含有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)，生成的第一个初试归并段长度最大值和最小值分别多少？

对含有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)，生成的第一个初试归并段长度最大值和最小值分别多少？

对含有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)，生成的第一个初试归并段长度最大值和最小值分别多少？

对含有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)，生成的第一个初试归并段长度最大值和最小值分别多少？

对含有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)，生成的第一个初试归并段长度最大值和最小值分别多少？

对含有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)，生成的第一个初试归并段长度最大值和最小值分别多少？

对含有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)，生成的第一个初试归并段长度最大值和最小值分别多少？