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

一、应用题

1． 在

树和

树中查找关键字时，有什么不同？

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

. 树还可以在最下层从最小关

【答案】在树中查找关键字从根结点开始，从根往下查找结点，然后在结点内查找关键字，得出查找成功与否的结论。

字后，要继续查到最下层结点，得到查找成功与否的结论。另外，键字开始，从左往右进行顺序查找，B-树则不能作顺序查找。

2． 用单链表保存m 个整数，节点的结构为（data , link ）, 且点而删除其余绝对值相等的节点。

例如若给定的单链表head 如下

删除节点后的head 为

要求

（1）给出算法的基本思想 （2）使用c 或

语言，给出单链表节点的数据类型定义。

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

（3）根据设计思想，采用c 或【答案】（1）算法思想：

定义一个大小为n 的布尔数组flag ，初始时所有的元素都赋值为false , 用来标识遍历过程中是否出现元素绝对值为flag 的节点。然后遍历链表，遍历过程中，每一个当前结点data 域的绝对值，则将flag 位置为真（true ）所对应的flag 位：若为真，则删除该结点；若为假（false ）。

（2）节点的数据结构定义如下：

（3）

全局数组标志节点的绝对值是否出现过

第 2 页，共 31 页

（n 为正整数）。现要求

设计一个时间复杂度尽可能高效地算法，对于链表中绝对值相等的节点，仅保留第一次出现的节

（4）说明所涉及算法的时间复杂度和空间复杂度。

则删除该节点

如果此绝对值已经在节点值的绝对值中出现过

否则，将flag 中对应的位置置为true ，并将指针指向下一个元素

，申请大小（4）只遍历一次链表，所以时间复杂度为0 （m ） （m 为单链表中元素的个数）

为n 的数组，所以空间复杂度为0 （n ） （n 为节点绝对值的最大值）。

3． 请写出应填入下列叙述中（ ）内的正确答案。

某一工程作业的网络图如图1所示，其中箭头表示作业，箭头边的数字表示完成作业所需的天 数。箭头前后的圆圈表示事件，圆圈中的数字表示事件的编号。用事件编号的序列（例如0-2-7-9-11）表示进行作业的路径。

完成此工程的关键路径是（A ）完成此工程所需的最少天数为（B ）天，此工程中具有最大充，充裕天数是（D ）裕天数的事件是（C ）。关键路径上的事件的充裕天数是（E ）。

图1

【答案】A. 0-2-6-9-11; B. 20; C.事件顶点1、5和7各充裕两天；D. 4天；E. 0

4． KMP 算法（字符串匹配算法）较Brute （朴素的字符串匹配）算法有哪些改进？

【答案】朴素的模式匹配度达到

时，KMP 算法的优点更为突出。

第 3 页，共 31 页

时间复杂度是KMP 算法有一定改进，时间复杂

主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配

5． （1）对于有向无环图，叙述求拓扑有序序列的步骤；

（2）对于图1，写出它的四个不同的拓扑有序序列。

图1

【答案】（1）对有向图，求拓扑序列步骤为：

1）在有向图中选一个没有前驱（即入度为0）的顶点并输出。 2）在图中删除该顶点及所有以它为尾的弧。

3）重复1）和2）, 直至全部顶点输出，这时拓扑排序完成；否则，图中存在环，拓扑排序失败。

（2）拓扑有序序列如图2:

图2 拓扑有序序列

6． 某文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但可多次 创建新文件。请回答如下问题。

（1）在连续、链式、索引三种文件的数据块组织方式中，哪种更合适? 要求说明理由。为定位文件数据块。需要在FCB 中设计哪些相关描述字段？

（2）为快速找到文件，对于FCB ，是集中存储好，还是与对应的文件数据块连续存储好? 要求说明理由。

【答案】根据题目所给条件，文件系统为一级目录结构，文件的数据一次性写入磁盘，已写

第 4 页，共 31 页