2017年上海大学数据结构与应用算法之数据结构考研复试核心题库

目录

2017年上海大学数据结构与应用算法之数据结构考研复试核心题库（一） ............................. 2

2017年上海大学数据结构与应用算法之数据结构考研复试核心题库（二） ............................. 8

2017年上海大学数据结构与应用算法之数据结构考研复试核心题库（三） ........................... 16

2017年上海大学数据结构与应用算法之数据结构考研复试核心题库（四） ........................... 23

2017年上海大学数据结构与应用算法之数据结构考研复试核心题库（五） ........................... 29

第 1 页，共 38 页

2017年上海大学数据结构与应用算法之数据结构考研复试核心题库（一）

说明：本资料为学员内部使用，整理汇编了2017考研复试重点题及历年复试常考题型。 ————————————————————————————————————————

一、应用题

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

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

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

【答案】根据题目所给条件，文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但是可以多次创建新文件，我们得知该文件系统是不能修改原文件的，只能将修改后的文件按新文件来存储，这与一次刻录光盘的存储方式相似。对于这样的系统，因为不需要随时添加或删除文件的内容，所以一次写入的文 件的大小是固定不变的，也是可预知的，而连续存放文件的方式就有其优点。这种方式只需要知道文件的起始地 址和文件的大小，便可以通过计算的方法找到文件的任何位置。文件若需要修改，则原文件作废，修改以后的文 件以新文件的形式重新写入，不会产生存储碎片，高效，高利用率。所以，如下作答。

（1）连续的数据块组织方式更合适，因为文件的数据一次性写入磁盘，已写入的文件不可修改，但是可以 多次创建新文件，我们得知该文件系统是不能修改原文件的，只能将修改后的文件按新文件来存储。不需要随时添加或删除文件的内容，所以一次写入的文件的大小是固定不变的，也是可预知的。这样，只需要知道文件的起 始地址和文件的大小，便可以通过计算的方法访问文件的任意位置。

为定位文件数据块。需要在FCB 中设计相关描述字段有： 或者〈起始块号，结束块号>。

（2）将所有的FCB 集中存放，文件数据集中存放。这样在随机查找文件名时，只需访问FCB 对应的块，可减少磁头移动和磁盘I/O访问次数。

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

图 存储映像7K 意图

设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为

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

符i 所在结点的位置p ）。要求：

（1）给出算法的基本设计思想。

（2）根据设计思想，采用C 或

【答案】

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

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

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

表中的第个结点；若则使q 指向链表中的第

表尾的长度相等。

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

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

两个指针同步向后移动

（3）参考答案的时间复杂度为：或其中m 、n 分别为两个链表的长度。

3． 证明：具有n 个顶点和多于n-1条边的无向连通图G —定不是树。

【答案】具有n 个顶点n-1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于n-1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。形 成回路的连通图不再是树。

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

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

返回共同C 缀的起始点

则使p 指向链个结点，即使指针p 和q 所指的结点到或JA V A 语言描述算法，关键之处给出注释。 （3）说明你所设计算法的时间复杂度。

第 3 页，共 38 页

图1

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

1）在有向图中选一个没有前驱（即入度为0）的顶点并输出。

2）在图中删除该顶点及所有以它为尾的弧。

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

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

图2 拓扑有序序列

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

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

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

（2）最佳适配法

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

（3）最差适配法

链表结点大小逆序排列，总从第一个结点开始分配，将分配后结点所剩空间插入到链表适当

第 4 页，共 38 页