我下vip免费资源网 www.woxia.net (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）是一种特定的堆，其最小层和最大层交替出现，根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元
我下vip免费资源网 www.woxia.net 素中最小（或最大）。如图所示为一最小最大堆；
min level
7 max level 40 70 7777 min level 30 9 10 15 50 20 45 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．
45 5 （1） 给出在该DEAP中插入结点4后的结果． 8 （2） 写出在DEAP中插入新结点的算法． 10 25 40 （3） 用C或PASCAL语言编写实现上述算法的程序．（20分） 30 15 19 9 20 【浙江大学 1997 7 （20分）】
我下vip免费资源网 www.woxia.net