数据结构部分
一、辨析题
(每小题3分，共15分。)
1、若有一个栈的输入序列是1,2,3,……,100，输出序列的第一个元素是100，则第50个输出元素是50。
2、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。
3、在拓扑排序序列中，任意两个结点i和j，都存在从i到j的路径。
4、在哈希表中，装填因子的值越小，存取元素时发生冲突可能性就越小。
5、任何一个无向连通图的最小生成树只有一棵。
二、问答题
(每小题15分，共60分。)
6、简述堆排序算法的基本思想。对于快速排序而言，堆排序有哪些优势?对于归并排序而言，堆排序有哪些优势?假定有8000个整数，需要找出最大的10个数，在堆排序、快速排序、基数排序方法中，采用哪种方法最好?请说明理由。
7、一棵由字符元素构成的二叉树以完全二叉树的数组结构进行存储。设计创建该二叉树的二叉链表结构的递归算法。
8、一个由整数元素构成的递增有序线性表存放在一个双向链表中，设计一个时间复杂度为O(n)的算法，在链表中获得两个和为x的结点的值，并以x=a+b的形式输出；若不存在，则给出提示信息。
9 ……此处隐藏13745个字…… sp; (2)查询姓名为“安娜”的记录过程如下：
①题干已知文件的目录已在内存，即FCB已在内存，读取一级索引，访问一次磁盘块；
②遍历一级索引，找到索引项‘A’，其指向二级索引表中的索引项“AA”，读入二级索引，访问一次磁盘块；
③从索引项“AA”开始遍历二级索引表，找到索引项“AN”，其指向文件中第一条姓名首字母组合为“A-N”的记录；
④假设文件记录分布均匀，则一百万条记录中平均有1000000divide26divide26≈1480条读音为“A-N”的记录，每条记录大小为286B。1480×286Bdivide1024B≈413.4，则占用414个磁盘块，平均访问(1+414)/2=207.5个磁盘块(最好只需要比较一次，读入一个磁盘块，在第一个磁盘块就找到“安娜”；最坏需要比较414次，读入414个磁盘块，在第414个磁盘块找到“安娜”)。
因此，查询姓名为“安娜”的记录，平均需要访问1+1+207.5=209.5个磁盘块。
