2017年中国地质大学(北京)数据结构复试实战预测五套卷
● 摘要
一、应用题
1． 设散列表为数分别为
：
注：％是求余数运算中，函数码序列为
（2）计算搜索成功的平均搜索长度
表示颠倒十进制数x 的各位，如
即表的大小为
其
等。若插入的关键
，现采用双散列法解决冲突。散列函数和再哈希函
（1）试画出插入这8个关键码后的哈希表；
【答案】（1）插入这8个关键码后的哈希表如表所示：
表 插入关键字后的哈希表
（2）
2． 将下列出三棵树组成的森林转换为二叉树（只要求给出转换结果）。
图1
【答案】森林转换为二叉树分以下三步：
（1）连线（将兄弟结点相连，各树的根看作兄弟）。
（2）切线（保留最左边子女为独生子女，将其他子女分支切掉）。 （3）旋转（以最左边树的根为轴. 顺时针向下旋转45度）。 所以由上面三棵树转换得到的二叉树如图2所示：
图2
3． 给出模式串
在KMP 算法中的next 和nextval 数组。
【答案】模式串的next 函数定义如下：
根据此定义，
可求解模式串
的next 和nextval 值如下：
4． 某文件系统空间的最大容量为4TB
以磁盘块为基本分配单位，磁盘块大小为1KB 。
文件控制块（FCB ）包含一个512B 的索引表区。请回答下列问题。
（1）假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号。索引表项中块号最少占多少字节? 可支持的单个文件最大长度是多少字节？
（2）假设索引表区采用如下结构：第0〜7字节采用<起始块号，块数>格式表示文件创建时预分配的连续存储空间，其中起始块号占6B ，块数占2B ; 剩余504字节采用直接索引结构，一个索引项占6B ，则可支持的单个文件最大长度是多少字节? 为了使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理 值并说明理由。
【答案】
（1）文件系统存储空间共有块数可存放
（2）
为表示
个块号，索引表项占
512B
个索引项，每个索引项对应一个磁盘块，故最大文件长度：
块号占6字节，块数占2字节的情形下，最大文件长度：
合理的起始块号和块数所占字节数分别为
理由：
块数占4B 或以上，就可表示4TB 大小的文件长度，达到文件系统的空间上限。
5． 设G=（V , E）以邻接表存储，如图所示，试画出图1的深度优先生成树和广度优先生成树。
图1
【答案】设从顶点1开始遍历，则深度优先生成树如图2所示，广度优先生成树如图3所示：
图2 图3
6． 阅读下面的算法，说明算法实现的功能。
【答案】本算法功能是将两个无头结点的循环链表合并为一个循环链表。Head1最后一个结点的链域指向head2, head2最后一个结点的链域指向headl ，headl 为结果循环链表的指针。
7． 已知n 阶下三角矩阵A （即当，按照压缩存储的思想，可以将其主对角线以时，有）下所有元素（包括主对角线上元素）依次存放于一维数组B 中，请写出从第一列开始采用列序为主序分配方式时在B 中确定元素的存放位置的公式。
【答案】2
阶下三角矩阵元素第1列到第
列是梯形，元素数为
第1列有n 个元素，第j 列有而在第j 列上的位置是为
个元素，所以n
阶下三角矩阵A 按列存储，其元素在一维数组B 中的存储位置k 与i 和j 的关系为：