else{List[(2) ]=list[child]; child*=2;

} }

list[child/2]=rootkey;

}

(2)．判断下列序列能否构成最大堆：（12，70，33，65，24，56，48，92，86，33）； 若不能按上述算法将其调整为堆，调整后的结果为：

（ ）。

四、算法设计题：

1． 设计一个用链表表示的直接选择排序算法。

2．冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替进行的冒泡排序算法（即双向冒泡排序法）。

3．输入50个学生的记录（每个学生的记录包括学号和成绩），组成记录数组，然后按成绩由高到低的次序输出（每行10个记录）。排序方法采用选择排序。

4．已知（k1,k2……，kn）是堆，试写一个算法将（k1,k2,……，kn,kn+1）调整为堆。按此思想写一个从空堆开始一个一个填入元素的建堆算法（题示：增加一个k n+1后应从叶子向根的方向调整）。

39

习题十 文件

一、单项选择题

1．索引无序文件是指（ ）。

A. 主文件无序，索引表有序 B. 主文件有序，索引表无序 C. 主文件有序，索引表有序 D. 主文件无序，索引表无序

2. 散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的（ ）方法是散列文件的关键。

A. 散列函数 B. 除余法中的质数 C. 冲突处理 D. 散列函数和冲突处理

3．下述文件中适合于磁带存储的是（ ）。

A. 顺序文件 B. 索引文件 C. 散列文件 D. 多关键字文件 4. ISAM文件和VASM文件属于（ ）。

A. 索引非顺序文件 B. 索引顺序文件 C. 顺序文件 D. 散列文件 5．倒排文件的主要优点是（ ）。

A. 便于进行插入和删除运算 B. 便于进行文件的合并 C. 能大大提高次关键字的查找速度 D. 能大大节省存储空间

二、填空题

1. 文件可按其记录的类型不同而分成两类，即___________和____________文件。

2. 数据库文件按记录中关键字的多少可分成____________和____________两种文件。

3. 文件由_________组成；记录由_________组成。

4. 顺序文件中，要存取第I个记录，必须先存取_________个记录。

5. 索引顺序文件既可以顺序存取，也可以_________存取。

6. 散列检索技术的关键是_______________和 _______________。 7. VSAM(虚拟存储存取方法)文件的优点是：动态地_________，不需要文件进行_________，并能较快地_________进行查找。

三、应用题

1. 什么是索引顺序文件？

2. 试比较顺序文件，索引非顺序文件，索引顺序文件，散列文件的存储代价，检索，插入，删除记录时的优点和缺点。

3．已知职工文件中包括职工号、职工姓名、职务和职称4个数据项（见下表）。职务有校长、系主任、室主任和教员；校长领导所有系主任，系主任领导他所在系的所有室主任，室主任领导他所在室的全体教员；职称有教授、副教授和讲师3种。请在职工文件的数据

40

结构中设置若干指针和索引，以满足下列两种查找的需要：

（1） 能够检索出全体职工间领导与被领导的情况；

（2） 能够分别检索出全体教授、全体副教授、全体讲师。 要求指针数量尽可能少，给出各指针项索引的名称及含义即可。

表 职工文件 职工号 001 002 003 004 005 006 007 008 009 010 …

职工姓名 张军 沈灵 叶明 张莲 叶宏 周芳 刘光 黄兵 李民 赵松 … 职务 教员 系主任 校长 室主任 系主任 教员 系主任 教员 室主任 教员 … 职称 讲师 教授 教授 副教授 教授 教授 教授 讲师 教授 副教授 … 41

参考文献

[1]严蔚敏等 数据结构 北京：清华大学出版社，1997.4 [2]殷人昆 数据结构 北京：清华大学出版社，2001.3

[3]李春葆 数据结构习题与解析 北京：清华大学出版社，2003

[4]前沿考试研究室 计算机专业研究生入学考试全真题解----数据结构与程序设计分册 北京：人民邮电出版社，2003.6

[5]何军等 数据结构500题 北京：人民邮电出版社，2003.4

[6]徐孝凯 数据结构辅导与提高 北京：清华大学出版社，2003.12

42