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

一、应用题

1． 索引顺序存取方法（ISAM ）中，主文件已按关键字排序，为何还需要主关键字索引？

【答案】ISAM 是专为磁盘存取设计的文件组织方式。即使主文件关键字有序，但因磁盘是以盘组、柱面和磁道（盘面）三级地址存取的设备，因此通常对磁盘上的数据文件建立盘组、柱面和磁道（盘面）三级索引。在ISAM 文件上检索记录时，先从主索引（柱面索引的索引）找到相应柱面索引。再从柱面索引找到记录所在柱面的磁道索引，最后从磁道索引找到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直到查到为止；反之，若找遍该磁道而未找到所查记录，则文件中无此记录。

2． 设内存中可利用空间已连成一个单链表，对用户的存储空间需求，一般有哪三种分配策略？

【答案】（1）首次适配法

从链表头指针开始查找，找到第一个大于等于所需空间的结点即分配。首次适配法适合事先不知道请求分配和释放信息的情况，分配时需查询，释放时插在表头。

（2）最佳适配法

链表结点大小增序排列，找到第一个大于等于所需空间的结点即分配。最佳适配法适用于请求分配内存大小范围较宽的系统，释放时容易产生存储量很小难以利用的内存碎片，同时保留那些很大的内存块以备将来可能发生的大内存量的需求，分配与回收均需查询。

（3）最差适配法

链表结点大小逆序排列，总从第一个结点开始分配，将分配后结点所剩空间插入到链表适当位置。最差适配法适合请求分配内存大小范围较窄的系统，分配时不查询，回收时查询，以便插入适当位置。

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

树的非终端结点是索引部分，其查找从根开始，从根往下查到关键

. 树还可以在最下层从最小关【答案】在树中查找关键字从根结点开始，从根往下查找结点，然后在结点内查找关键字，得出查找成功与否的结论。字后，要继续查到最下层结点，得到查找成功与否的结论。另外，

键字开始，从左往右进行顺序查找，B-树则不能作顺序查找。

4． 假设利用边界标识法，并以首次拟合策略分配，己知在某个时刻可利用空间表的状态如图所示（注：存储块头部域的值和申请分配的存储量均包括头部和尾部的存储空间）请画出：

（1）当系统回收一个起始地址为559，大小为45的空闲块之后的链表状态；

（2）系统继而在接受存储块大小为100的请求后，又回收一个起始地址为515，大小为44的空闲块之后的链表状态。

【答案】（1）系统回收一个起始地址为559，大小为45的空闲块后，因右侧起始地址604为空闲块，应与之合并。合并后，成为起始地址为559，大小为167的空闲块。链表状态如图1所示：

图1

（2）系统在接受存储块大小为100的请求后，将大小为117的空闲块分出100给予用户。在回收一个起始地址为515，大小为44的空闲块之后，因左侧起始地址为462、大小为53和右侧起始地址为559、大小为167均为空闲块，应与之合并。合并后，起始地址为462、大小为264的空闲块。链表状态如图2所示：

图2

5． 画出对算术表达式

表所示。

表 操作数栈和运算符找的变化过程 求值时操作数栈和运算符栈的变化过程。 求值，过程如【答案】设操作数栈是opnd ，运算符栈是optr ，对算术表达式

6． 写出下列排序算法的基本思想，并写出对序列（23，12，35，47，16，25，36，19，21，16）进行排序时每一趟的结果。

【答案】此排序为双向起泡排序：从前向后一趟排序下来得到一个最大值，若其中发生交换，则再从后向前一趟排序，得到一个最小值。

第一趟：12，23，35，16，25，36， 19，21，16， 47

第二趟：12，16，23，35，16，25，36， 19，21，47

第三趟：12，16，23，16，25，35， 19，21，36， 47

第四趟：12， 16， 16，23， 19， 25， 35， 21， 36，47

第五趟：12，16，16，19，23，25，21，35， 36， 47

第六趟：12，16，16，19，21， 23，25，35， 36， 47