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

一、应用题

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

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

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

量为

则空闲块大小只能是

由同一大块分裂而得的两个小块互称“伙伴空

（若

）

，

如内存大小为

间”或

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

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

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

2． 设阶稀疏矩阵A 有t 个非零元素，其三元组表示为试问：非零元素的个数t 达到什么程度时用，共占用三元组表

元组）

时，用

的

表示A 才有意义？

个存储单元，用二维数组存储时占用

个单元，

只有当

【答案】稀疏矩阵A 有t 个非零元素，加上行数mu 、列数皿和非零元素个数tu （也算一个三

表示A 才有意义。解不等式得

）。

空间。起始地址为P ，

大小为的内存块，其伙伴的起始地址为：

3． 特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能? 为什么？

【答案】特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律，因此可以对非零元，将非零元素存储在向量中，元素的下标i 和j 和该素分配单元（对值相同元素只分配一个单元）

元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能。而稀疏矩阵是指非零元素和矩阵容量相比很小

且分布没有规律。用十字链表作存储结构自然失去了随机

最差情况下是

因此也失去

存取的功能。即使用三元组表的顺序存储结构，存取下标为i 和j 的元素时，要扫描三元组表，下标不同的元素，存取时间也不同，最好情况下存取时间为了随机存取的功能。

4． 在模试匹配KMP 算法中所用失败函数的定义中，为何要求真子串？且为最大真子串？

【答案】失败函数（即next ）的值只取决于模式串自身，若第j 个字符与主串第i 个字符失配时，假定主串不回溯，模式串用第k （即next[j]个字符与第i 个相比，有

为了

不因模式串右移与主串第i 个字符比较而丢失可能的匹配，对于上式中可能存在的多个k 值，应取其中最大的一个。这样，因j-k 最小，即模式串向右滑动的位数最小，避免因右移造成可能匹配

两头匹配的

的丢失。

5． S 是字符数组

，

中存放的是该字符串的有效长度，

假设中字符串的内容为

说明下列程序的功能及执行结果。

【答案】本程序的功能是求字符串的nextval 函数，程序执行结果是0110132。

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

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

（1）试指出判别给定序列是否合法的一般规则；

（2）两个不同合法序列（对同一输入序列）能否得到相同的输出元素序列? 如能得到，请举列说明。

【答案】（1）通常有两条规则。第一是给定序列中S 的个数和X 的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，S 的个数要大于或等于X 的个数。

（2）可以得到相同的输出元素序列。例如，输入元素为A , B , C , 则两个输入的合法序列ABC 和BAC 均可得到输出元素序列ABC 。对于合法序列ABC ，使用SXSXSX 操作序列；对于合法序列BAC ，使用SSXXSX 操作序列。

8． 用一个数组S （设大小为MAX ）作为两个堆栈的共享空间。请说明共享方法，栈满/栈空的，其中i 为0或1，用判断条件，并用C 语言或PASCAL 语言设计公用的入栈操作push （i ，x ）于表示栈号，x 为入栈值。

，栈底设在数组的两端，两栈顶相邻时为栈满。设【答案】两栈共享一向量空间（一维数组）

共享数组为S[MAX]，则一个栈顶指针为一1，另一个栈顶指针为MAX 时，栈为空。用C 语言写的入栈操作push （i ，x ）如下：

二、算法设计题

9． 已知二叉树丁的结点形式为

【答案】算法如下：

在树中查找值为的结点，若找到，则记

数（count ）加1；否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。

10．设计算法将一个带头结点的单链表A 分解为两个具有相同结构的链表B 、C ，其中B 表的结点为A 表中值小于零的结点，而C 表的结点为A 表中值大于零的结点（链表A 的元素类型为整型，要求B 、C 表利用A 表的结点）。

【答案】算法如下：