数据结构部分

一、辨析题

(每小题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个磁盘块。