发布时间 : 2024/5/16 2:58:24 星期四 文章数据结构考研试题精选及答案第10章 排序更新完毕开始阅读f23476232f60ddccda38a060

yes no yes no no

yes yes no yes no

yes

注：a是整数数组，存放要排序的数组集合，n是a的长度，p,i,j,k,m,t是临时变量，p为整型数组，i,j,k,m,t为整型变量。本题给出的是将数组a的元素a1,a2，?,an从大到小排序的子程序的框图，如上图，填空完善此算法框图。该子程序采用改进的选择排序方法，该方法基于以下思想：在选择第一大元过程中：a1与aj (j=n,n-1,?,2)逐个比较，若发现aj1>a1,则aj1与a1交换，交换后新的aj1有性质aj1>= at( j1ai(j2=at(j2=0)个，依次为aj1,aj2,?,ajk，则它们都满足这一性质。它们的下标满足n>=j1>j2>?>jk>1。有了这些下标，在确定第二大元时，可只考虑a2与aj(j=jk,jk-1,?,3)逐一比较。倘若jk=2,则可不经比较就知道a2就是第二大元。在选择第二大元的过程中，将与a2交换过的元素下标也记录下来，可供选择其他大元使用。但在选择第二大元时，应保证与a2交换的那些位置上的新值也都满足上述性质。依次类推，顺序选择第一，第二，?,第n-1大元，实现对a的排序。 【哈尔滨工业大学 1999 六 （14分）】

57．给定一个关键字序列{24，19，32，43，38，6，13，22}，请写出快速排序第一趟的结果；堆排序时所建的初始堆；归并排序的全过程。然后回答上述三中排序方法中那一种方法使用的辅助空间最少？在最坏情况下那种方法的时间复杂度最差？ 【西安电子科技大学 1999五（10分）】

58．奇偶交换排序如下所述：对于初始序列A[1]，A[2],?,A[n],第一趟对所有奇数i（1<=iA[i+1]，则将两者交换；第二趟对所有偶数i（2<=iA[i+1]，则将两者交换；第三趟对所有奇数i（1<=i

(1) 分析这种排序方法的结束条件。

(2) 写出用这种排序方法对35，70，33，65，24，21，33进行排序时，每一趟的结果。 【山东科技大学 2001 四（10分）】

59．设某文件经内排序后得到100个初始归并段(初始顺串),若使用多路归并排序算法，并要求三趟归并完成排序，问归并路数最少为多少？【山东大学1992 一、4(3分)】【东南大学1999一、3（5分）】

60．证明：置换-选择排序法产生的初始归并段的长度至少为m。(m是所用缓冲区的长度)。

【西安电子科技大学 1996 二、5 （5分）】

61．给定8个权值集合（2，5，3，10，4，7，9，18）画出含有8个叶子结点的最佳三叉归并树，并计算出wpl=? 【东北大学 1996 一、2 (5分)】 类似本题的另外叙述有：

(1) 假设有12个初始归并段，其长度分别为85，68，62，9，18，60，20，3，6，8，44，30；现要作4路外部归并排序，试画出表示归并过程的最佳归并树，并计算树的wpl。 【厦门大学 2001 二、3（24%/3分）】

(2) 设有12个初始归并段，其长度分别为8，6，30，44，62，18，85，68，9，60，3，20；试画出表示归并过程的最佳归并树，并计算树的WPL。 【厦门大学 1998 七、2 （8分）】

(3) 现有12个初始归并段，其记录数分别为：{30，44，8，6，3，20，60，18，9，62，68，85}，现用3路平衡归并，画出最佳归并树。【北京邮电大学 2002 二、1 （5分）】 (4) 设有13个初始归并段,其长度分别为28,16,37,42,5,9,13,14,20,17,30,12,18.试画出4路归并时的最佳归并树，并计算它的带权路径长度WPL。 【清华大学 1998 九 （10分）】

62．已知有31个长度不等的初始归并段，其中8段长度为2；8段长度为3；7段长度为5；5段长度为12；3段长度为20(单位均为物理块)，请为此设计一个最佳5-路归并方案，并计算总的（归并所需的）读/写外存的次数。 【清华大学 1994 四 （10分）】 类似本题的另外叙述有：

(1) 已知在进行置换-选择排序时得到14个有序段，其长度分别为2，3，4，5，6，7，8，9，11，13，17，20，21，23；现进行4路平衡归并，要求给出所对应的最佳归并树和总的读/写次数。

【中科院计算所 2000 二 （10分）】

(2) 已知某文件经过置换-选择排序后，得到长度分别为47，9，31，18，4，12，23，7的8个初始归并段。试为3路平衡归并设计读写外存次数最少的归并方案，并求出读写外存的次数。

【东南大学 2000 一、6 （8分）】

(3)置换选择排序得到初始归并段长（k字节数）为37，34，300，41，70，120，35，43作图表示出这些磁盘文件进行归并所用的4阶最佳归并树，算出归并的总读写字节数，每读写1字节计为1。

【北京工业大学 1999 六 (8分)】

63．以归并算法为例，比较内排序和外排序的不同，说明外排序如何提高操作效率。

【华南师范大学 1999四(10分)】

64．对输入文件（101，51，19，61，3，71，31，17，19，100，55，20，9，30，50，6，90）；当k=6时，使用置换-选择算法，写出建立的初始败者树及生成的初始归并段。【北方交通大学 1999 四（12分）】 类似本题的另外叙述有：

(1)给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18),设内存工作区可容纳4个记录，写出用置换-选择排序得到的全部初始归并段。 【上海交通大学 1999 十】 (2)用置换-选择排序法产生文件 F（长度为 n）的初始归并段(设内存缓冲区的长度为m)， ① 平均情况下，初始归并段的长度为多少？为什么？

② 初始归并段的长度最长与最短时，其长度分别为多少？在何种情况下出现？简单解释一下。

【上海交通大学 2000 九（8分）】

65．设有N个记录的一个文件，经内部排序后得到650个初始归并段。

(1) 试问在四台磁带机上分别用平衡归并和多步归并进行外部排序各需要多少趟归并？ (2) 给出多步归并排序前五趟归并的情况。（10分）【北方交通大学 1997 六 （16分）】 类似本题的另外叙述有：

(1)已知有8个初始归并段，其长度分别为10，20，25，30，45，12，16，2，现用T0，T1，T2三条磁带进行二路多步归并排序，写出每遍归并后各归并段的分布，并给出初始归并段在磁带上的最佳初始分布。

【西北工业大学 1998 二、1 (10分)】

66. 写出或画出下面两题的结果： 【北京邮电大学 1997 四 （10分）】

(1) 归并段长度分别为9，4，7，3，8，6，15，试画出3路平衡最佳归并树。

(2) 有二叉树中序序列为：A B C E F G H D ;后序序列为：A B F H G E D C . 请画出此二叉树。

类似本题的另外叙述有：

(1)设有11个长度（即包含记录的个数）不同的初始归并段，它们所包含的记录个数分别为25,40,16,38,77, 64,53, 88,9,48,98。试根据它们做4路平衡归并，要求：

（1）指出总的归并趟数； （3分） （2）构造最佳归并树； （8分）

（3）根据最佳归并树计算每一趟及总的读记录数。（5分）【清华大学 1997 八 （16分）】

67. 外排序中为何采用k-路（k>2）合并而不用2-路合并？这种技术用于内排序有意义吗？为什么？

【东南大学 1995 三 （8分）】

68．给定输入文件：101，48，19，65，3，74，33，17，21，20，99，53，21，并设记录缓冲区个数k=4，写出基于败者树的外排序顺串生成算法runs输出的顺串。【东南大学 1996 一、6 （6分）】

五、算法设计题：

1．冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。【吉林大学 2001 二、3 （9分）】 类似本题的另外叙述有：

(1) 编写一个双向气泡排序的算法，即相邻两遍向相反方向起泡。【北京邮电大学1992六(10分)】

2．有n个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法。（注：双向起泡排序即相邻两趟排序向相反方向起泡）【北京邮电大学 1997 七（15分）】

3．请编写直接插入排序算法。

TYPE rcdtype=RECORD

key: integer;

otheritem: anytype; END;

listtype=ARRAY[0..n] OF rcdtype; 【北京轻工业学院 1998 七 （10分）】 4．（此题单考生做）用类PASCAL语言（或PASCAL语言）完成下列各题：

设单链表头结点指针为L，结点数据值为整型，试写出对链表L按“插入方法”排序的算法：LINSORT（L）。

【北京科技大学 1999 十、1（10分） 2000 十、1 （10分）】 5．输入50个学生的记录（每个学生的记录包括学号和成绩），组成记录数组，然后按成绩由高到低的次序输出（每行10个记录）。排序方法采用选择排序。 【北京师范大学 1999 五 】

6.有一种简单的排序算法，叫做计数排序（count sorting）。这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小，假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。 (1) (3分)给出适用于计数排序的数据表定义;

(2) (7分)使用Pascal或C语言编写实现计数排序的算法； (3) (4分)对于有n个记录的表，关键码比较次数是多少? (4) (3分)与简单选择排序相比较，这种方法是否更好?为什么? 【清华大学 2000 三（17分）】

类似本题的另外叙述有： 结点类型和存储方式如下： (1)TYPE node=RECORD

key:integer; info:datatype; count:integer

END;

VAR r:ARRAY[1..n] OF node; 请给出一个排序方法，不移动结点存储位置，只在结点的count字段记录结点在排序中的序号（设排序码最大的结点序号为1）。 【国防科技大学 1999 七 】

7．快速分类算法中，如何选取一个界值（又称为轴元素），影响着快速分类的效率，而且界值也并不一定是被分类序列中的一个元素。例如，我们可以用被分类序列中所有元素的平均值作为界值。编写算法实现以平均值为界值的快速分类方法。 【石油大学 1998 五 (18分)】

8．写出一趟快速排序算法。【山东师范大学2000 二、4(10分) 2001 二、5(10分)】 类似本题的另外叙述有：