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

一、应用题

1． 假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，“loading ”和“being ”的存储映像如图所示。

图 存储映像7K 意图

设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为符i 所在结点的位置p ）。要求：

（1）给出算法的基本设计思想。 （2）根据设计思想，采用C 或【答案】

（1）算法的基本设计思想：

①分别求出strl 和str2所指的两个链表的长度m 和n ;

②将两个链表以表尾对齐：令指针p 、q 分别指向strl 和str2的头结点，若表中的第

个结点；若

则使q 指向链表中的第

表尾的长度相等。

③反复将指针p 和q 同步向后移动，并判断它们是否指向同一结点。若p 和q 指向同一结点，则该点即为所 求的共同后缀的起始位置。

（2）用C 语言算法描述如下：

两个指针同步向后移动

第 2 页，共 35 页

请设计一

个时间上尽可能高效的算法，找出由strl 和str2所指的两个链表共同后缀的起始位置（如图中字

或JA V A 语言描述算法，关键之处给出注释。

（3）说明你所设计算法的时间复杂度。

则使p 指向链

个结点，即使指针p 和q 所指的结点到

（3）参考答案的时间复杂度为：长度。

2． 外排序中为何采用k 一路么？

【答案】外排序用路归并

返回共同C 缀的起始点

或

其中m 、n 分别为两个链表的

合并而不用2—路合并? 这种技术用于内排序有意义吗? 为什是因为k 越小，归并趟数越多，读写外存次数越多，时间效

率越低，故一般应大于最少的2-路归并。若将k-路归并的败者树思想单纯用于内排序，因其由胜者树改进而来，且辅助空间大，完全可由堆排序取代，故将其用于内排序效率并不高。

3． 队列可以用循环单链表来实现，故可以只设置一个头指针或者只设置一个尾指针。请你分析对于循环单链表实现的队列，用哪种方案更合适。

【答案】循环单链表若只设头指针，则出队操作时间复杂度是是

若只设尾指针，则出队和入队操作时间复杂度都是

而如对操作时间复杂度

因此，用循环单链表来实现队

列，设置一个尾指针更合适。

4． 两个字符串s1和s2的长度分别为m 和n 。求这两个字符串最大共同子串算法的时间复杂度，并简要说明理由。 为T （m ，n ）。估算最优的T （m , n ）

【答案】最优的T （m ，n ）是D （n ）。串S2是串S1的子串，且在S1中的位置是1。开始求 出最大公共子串的长度恰是串S2的长度。一般情况下，

5． （1）如果G1是一个具有n 个顶点的连通无向图，那么G1最多有多少条边?G1最少有多少条边？

（2）如果G2是一个具有n 个顶点的强连通有向图，那么G2最多有多少条边?G2最少有多少条边？

（3）如果G3是一个具有n 个顶点的弱连通有向图，那么G3最多有多少条边?G3最少有多少条边？

1）G1最多n （n-l ）/2条边，最少n-1条边。 【答案】（（2）G2最多n （n-l ）条边，最少n 条边。 （3）G3最多n （n-l ）条边，最少n-1条边。

第 3 页，共 35 页

6． 在如图1所示的伙伴系统中，回收两块首地址分别为768及128、大小为的存储块，请画出回收后该伙伴系统的状态图。

图1

【答案】因为小为

因为

所以768和所以首址

大小为

互为伙伴，伙伴合并后，首址为768，块大的块和首址512、大小为的块合并，成为首址

将其插入可利用空间表中。回

其伙伴地址为

512、；大小为的空闲块。因为收后该伙伴系统的状态图如图2所示：

图2 回收后该伙伴系统的状态图

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

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

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

【答案】（1）因为要最少访问，所以选择将前29块前移一个存储块单元，然后将要写入的记

第 4 页，共 35 页