学 1999五（10分）】
58．奇偶交换排序如下所述：对于初始序列A[1]，A[2],?,A[n],第一趟对所有奇数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分)】 类似本题的另外叙述有： (1)某个待排序的序列是一个可变长度的字符串序列，这些字符串一个接一个地存储于唯一的字符数组中。请改写快速排序算法，对这个字符串序列进行排序。【西安电子科技大学 2000计应用 七（11分）】 (2) 若待排序列用单链表存储，试给出其快速排序算法。 【北京邮电大学 2000 七（15分）】 9．设有一个数组中存放了一个无序的关键序列K1、K2、?、Kn。现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n。（注：用程序实现） 【南京航空航天大学 1997 六（12分）】 10．借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[l..h]中。若查找成功，则输出该记录在r数组中的位置及其值，否则显示“not find”信息。请编写出算法并简要说明算法思想。 【北京邮电大学 1998 七（15分）】 11．已知关键字序列（K1，K2，K3，?，Kn-1）是大根堆。 (1) 试写出一算法将（K1，K2，K3，?，Kn-1，Kn）调整为大根堆； (2) 利用（1）的算法写一个建大根堆的算法。【中科院软件所 1999 七、2 （7分）】 类似本题的另外叙述有： (1)设文件（R1，R2，?，Rn）是一个堆，Rn+1是任意一个节点，试设计一个算法，该算法把Rn+1添加到堆中，并使添加后形成的文件仍是一个堆，要求算法的时间复杂性为O(log2n)。 【吉林大学 1999 二、2 (8分) 】 12．辅助地址表的排序是不改变结点物理位置的排序。辅助地址表实际上是一组指针，用它来指出结点排序后的逻辑顺序地址。设用K[1]，K[2]，?，K[N]表示N个结点的值,用T[1],T[2],?,T[N]表示辅助地址表.初始时T[i]:=i ,在排序中,凡需对结点交换就用它的地址来进行。例如当N＝3时，对K（31，11，19）则有T（2，3，1）。试编写实现辅助地址表排序（按非递减序）算法的语句序列。 【重庆大学 2000 四、2 】 13．关于堆排序方法，完成如下工作： (1) 简述该方法的基本思想。 (2) 写出堆排序算法。 (3) 分析该算法的时间复杂度。 【西南财经大学 1999 五】 类似本题的另外叙述有： (1)N个元素的序列满足什么条件才能称之为堆？用类PASCAL语言写出堆排序和算法。 【南开大学 1997 七 (15分)】 14．设待排序的文件用单链表作存储结构，其形式如下： TYPE pointer=↑node; node=RECORD key:integer; next:pointer; END; 写出以head为头指针的选择排序算法。 【中山大学 1999 二 （10分）】 15．非递归的快速排序算法。【中科院软件所 1997 三 (10分)】 16．一最小最大堆（min max heap）是一种特定的堆，其最小层和最大层交替出现，根 总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小（或最大）。如图所示为一最小最大堆； min level 7 max level 40 70 7777 9 30 min level 10 15 45 50 20 30 12 max level (1) 画出在上图中插入关键字为5的结点后的最小最大堆。 (2) 画出在上图中插入关键字为80 的结点后的最小最大堆； (3) 编写一算法实现最小最大堆的插入功能。假定最小最大堆存放在数组中，关键字为整数。 (4) 用C或PASCA；实现上述算法。 【浙江大学 1996 八 (26分 )】 17. 二路插入排序是将待排关键字序列r[1..n]中关键字分二路分别按序插入到辅助向量d[1..n]前半部和后半部（注:向量d可视为循环表），其原则为，先将r[l]赋给d[1]，再从r[2] 记录开始分二路插入。编写实现二路插入排序算法。 【北京工业大学 1998 八 (10分)】 18． 叙述基数排序算法，并对下列整数序列图示其基数排序的全过程。（179,208,93,306,55,859,984,9,271,33） 【南京航空航天大学 2000 一 】 19．输入N个只含一位数字的整数，试用基数排序的方法，对这N个数排序。 【中国人民大学 2001 三、1（10分）】 20．设记录R[i]的关键字为R[i].KEY（1<=i<=k），树结点T[i]（1<=i<=K-1）指向败者记录，T[0]为全胜记录下标。写一算法产生对应上述R[i]（1<=i<= k）的败者树，要求除R[1..k]和T[0..k-1]以外，只用O(1)辅助空间。 【东南大学 1995 九 （15分）】 21．设有顺序放置的n个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红,白,蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后，重新安排时对每粒砾石的颜色只能看一次，并且只允许交换操作来调整砾石的位置。【上海大学 1999 二 2（18分）】 22. 数据结构DEAP的定义如下：DEAP是一棵完全二叉树，它或者是一棵空树，或者满足下列特性： （1）树根不包含元素．（2）其左子树是一小堆（MINHEAP），其右子树是一大堆（MAXHEAP）． （3）若右子树非空，设ｉ是左子树的任一结点，ｊ是右子树中与ｉ相应的结点．若这样的ｊ结点不存在，则取ｊ为右子树中与ｉ的父结点相应的结点；结点ｉ的关键字总是小于或等于结点ｊ的关键字值。 一个DEAP的例子如右图所示， 与结点15相对应的结点为20，与结点19对应的结点为25． （1） 给出在该DEAP中插入结点4后的结果． （2） 写出在DEAP中插入新结点的算法． （3） 用C或PASCAL语言编写实现上述算法的程序．（20分） 【浙江大学 1997 7 （20分）】 5 10 8 45 25 40 20 15 9 19 30