数据结构考研分类复习真题 第十章 排序[61]

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

TYPE rcdtype=RECORD

key: integer;

otheritem: anytype;

END;

listtype=ARRAY[n] OF rcdtype; 【北京轻工业学院 七 (分)】

．(此题单考生做)用类PASCAL语言(或PASCAL语言)完成下列各题

设单链表头结点指针为L结点数据值为整型试写出对链表L按插入方法排序的算法LINSORT(L)【北京科技大学 十(分) 十 (分)】

．输入个学生的记录(每个学生的记录包括学号和成绩)组成记录数组然后按成绩由高到低的次序输出(每行个记录)排序方法采用选择排序【北京师范大学 五 】

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

() (分)给出适用于计数排序的数据表定义

() (分)使用Pascal或C语言编写实现计数排序的算法

() (分)对于有n个记录的表关键码比较次数是多少?

() (分)与简单选择排序相比较这种方法是否更好?为什么? 【清华大学 三(分)】

类似本题的另外叙述有

结点类型和存储方式如下

()TYPE node=RECORD

key:integer;

info:datatype;

count:integer

END;

VAR r:ARRAY[n] OF node;

请给出一个排序方法不移动结点存储位置只在结点的count字段记录结点在排序中的序号(设排序码最大的结点序号为)【国防科技大学 七 】

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []