61．对由n个记录所组成的表按关键码排序时,下列各个常用排序算法的平均比较次数分别是:二路归并排序为(  1  ),直接插入排序为(  2  ),快速排序为(  3  ),其中,归并排序和快速排序所需要的辅助存储分别是(  4  )和(  5  )。  【上海海运学院 1998 二、4 （5分）】
1-5:a. o(1)   b. o（nlog2n）  c. o（n）  d. o（n2）  e. o（n(log2n)2）  f. o（log2n） 
62．将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是(     )
a．n       b．2n-1          c．2n          d．n-1
【中科院计算所    1998 二、7 （2分）】 【中国科技大学 1998 二、7 （2分）】
63. 基于比较方法的n个数据的内部排序。最坏情况下的时间复杂度能达到的最好下界是（    ）。
a. o(nlogn)  b. o(logn)  c. o(n)    d. o(n*n) 【南京理工大学 1996 一、2 （2分）】
64．已知待排序的n个元素可分为n/k个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为（    ）。
  a. o(nlog2n) b. o(nlog2k) c. o(klog2n) d. o(klog2k) 【中国科技大学 1998 二、9 （2分）】
类似本题的另外叙述有：
(1)已知待排序的n个元素可分为n/k个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素,若采用基于比较的排序,其时间下界应为(     )
a. o(klog2k) b. o(klog2n) c. o(nlog2k)  d. o(nlog2n)  【中科院计算所 1998 二、9 （2分）】
65．采用败者树进行k路平衡归并的外部排序算法，其总的归并效率与k （   ）
a． 有关     b．无关   【北京工业大学 2000 一 、2 (3分)】
66．采用败者树进行k路平衡归并时，总的（包括访外）归并效率与k（   ）。
a．有关               b．无关   【北京工业大学 2001 一、4 (2分)】 
类似本题的另外叙述有：
   (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）是一种特定的堆，其最小层和最大层交替出现，根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小（或最大）。如图所示为一最小最大堆；

(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分）】

上一页345下一页