当前位置：问答库＞考研试题

一、应用题

1． 为什么在倒排文件组织中，实际记录中的关键字域可删除以节约空间? 而在多重表结构中这样做为什么要牺牲性能？

【答案】因倒排文件组织中，倒排表有关键字值及同一关键字值的记录的所有物理记录号，可方便地查询具有同一关键字值的所有记录；而多重表文件中次关键字索引结构不同，删除关键字域后查询性能受到影响。

2． 试叙述动态存储分配伙伴系统的基本思想，它和边界标识法不同点是什么？

【答案】（1）动态存储分配伙伴系统的基本思想

在伙伴系统中，无论占用块或空闲块，其大小均为（k 为大于等于0的正整数）。若内存容

量为

则空闲块大小只能是由同一大块分裂而得的两个小块互称“伙伴空

（若）

，

如内存大小为

间”

或的块分裂成两个大小为的块。只有两个“伙伴空间”才能合并成一个大（若

（2）和边界标识法的不同

边界标识法在每块的首尾均有“占用”/“空闲”标志，空闲块合并方便。伙伴系统算法简单、速度快，但只有互为伙伴的两个空闲块才可合并，因而易产生虽空闲但不能归并的碎片。

3． 在树和树中查找关键字时，有什么不同？

【答案】在树中查找关键字从根结点开始，从根往下查找结点，然后在结点内查找关键字，得出查找成功与否的结论。树的非终端结点是索引部分，其查找从根开始，从根往下查到关键

. 树还可以在最下层从最小关字后，要继续查到最下层结点，得到查找成功与否的结论。另外，）。 空间。起始地址为P ，

大小为的内存块，其伙伴的起始地址为：键字开始，从左往右进行顺序查找，B-树则不能作顺序查找。

4． 如果输入序列为123456, 试问能否通过栈结构得到以下两个序列：435612和135426; 请说明为什么不能或如何才能得到。

【答案】输入序列为123456, 不能得出435612, 其理由是，输出序列最后两元素是12, 前面4个元素（4356）得到后，栈中元素剩12, 且2在栈顶，栈底元素1不可能在栈顶元素2之前出栈。得到135426的过程如下：1入栈并出栈，得到部分输出序列1; 然后2和3入找，3出栈，部分输出序列变为13; 接着4和5入栈，5、4和2依次出栈，部分输出序列变为13542; 最后6入栈并出栈，得到最终结果135426。

5． 试证明：同一棵二叉树的所有叶结点，在前序序列、对称序序列以及后序序列中都按相同的

，例如前序后序运对称序。 相对位置出现（即先后顺序相同）

，中序遍历是“左根右”，后序遍历是“左右根”【答案】前序遍历是“根左右”。三种遍历中

只是访问 " 根”结点的时机不同，对左右子树均是按左右顺序来遍历的，因此所有叶子都按相同的相对位罝出现。

6． 请阅读下列算法，回答问题。

问题一：这是什么类型的排序算法，该排序算法稳定吗？

问题二：设置|的作用是什么? 若将WHILE--DO 语句中判断条件改为该算法将会有什么变化，是否还能正确工作？

【答案】问题一：此为直接插入排序算法，该算法稳定。

问题二：

采用的作用是监视哨，免去每次检测文件是否到尾，提高了排序效率。 描述算法后，算法变为不稳定排序，但能正常工作。

7． 文件F 由200条记录组成，记录从1开始编号，用户打开文件后，欲将内存中的一条记录插入文件F 中，作为其第30条记录，请回答下列问题，并说明理由。

（1）若文件系统为顺序分配方式，每个存储块存放一条记录，文件F 的存储区域前后均有足够空闲的存储空间，则要完成上述操作最少要访问多少存储块？ F 的文件控制区内容会有哪些改变？

（2）若文件系统为链接分配方式，每个存储块存放的一条记录和一个链接指针，则要完成上述操作最少要 访问多少存储块？若每个存储块大小为1KB ，其中4个字节存放指针，则该系统支撑文件的最大长度是多少？

【答案】（1）因为要最少访问，所以选择将前29块前移一个存储块单元，然后将要写入的记录写入到当前的第30条的位置上。由于前移都要先访问原存储块将数据读出，再访问目标存储块将数据写入，所以最少需要访问

块存储块

F 的文件区的文件长度加1，起始块号减1

（2）采用链接方式则需要顺序访问前29块存储块，然后将新纪录的存储块插入链中即可，把新的块存入磁盘要1次访存，然后修改第29块的链接地址存回磁盘又一次访存。一共就是

次。

4个字节的指针的地址范围为 所以此系统支撑文件的最大长度为

8． 将下列出三棵树组成的森林转换为二叉树（只要求给出转换结果）。

图1

【答案】森林转换为二叉树分以下三步：

（1）连线（将兄弟结点相连，各树的根看作兄弟）。

（2）切线（保留最左边子女为独生子女，将其他子女分支切掉）。 （3）旋转（以最左边树的根为轴. 顺时针向下旋转45度）。 所以由上面三棵树转换得到的二叉树如图2所示：

图2

二、算法设计题

9． 请编写完整的程序。如果矩阵A 中存在这样的一个元素矩阵A 的所有马鞍点。

【答案】算法如下：

满足条件：是第i 行中值的最小的元素，且又是第j 列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出