2017年中国海洋大学数据结构复试实战预测五套卷
● 摘要
一、应用题
1． 请回答下列关于图（Graph ）的一些问题：
（1）有n 个顶点的有向强连通图最多有多少条边? 最少有多少条边？
（2）表示一个有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素? 是否稀疏矩阵？
（3）对于一个有向图，不用拓扑排序，如何判断图中是否存在环？
【答案】⑴最多有n （n-l ）条边；最少有n 条边。
（2） 有有个矩阵元素；不一定是稀疏矩阵（稀疏矩阵的定义是非零元素个数远小于该矩阵元素个数，且分 布无规律）。
（3）使用深度优先遍历，按退出DFS 过程的先后顺序记录下的顶点是逆向拓扑有序序列。如果在执行DFS （V ） 未退出前，出现顶点u 到v 的回边，则说明存在包含顶点v 和顶点u 的环。
2． 下图是5阶B 树，画出删去P 后的B 树，再画出删去D 后的B 树。
【答案】删除P 后
删除D 后
3． 设有一棵算术表达式树，用什么方法可以对该树所表示的表达式求值？
【答案】有两种方法，具体如下：
（1）对该算术表达式（二叉树> 进行后序遍历. 得到表达式的后序遍历序列，再按后缀表达式求值。
（2）递归求出左子树表达式的值，再递归求出右子树表达式的值，最后按根结点运算符（+、
一、*、/等） 进行求值。
4． 模式匹配算法是在主串中快速寻找模式的一种有效的方法，如果设主串的长度为m , 模式的长度为n ，则在主串中寻找模式的KMP 算法的时间复杂性是多少? 如果某一模式
给出它的next 函数值及next 函数的修正值nextval 之值。
【答案】KMP 算法的时间复杂性是p 的next 和nextval 值分别为01112212321和01102201320。
5． 试叙述动态存储分配伙伴系统的基本思想，它和边界标识法不同点是什么？
【答案】（1）动态存储分配伙伴系统的基本思想
在伙伴系统中，无论占用块或空闲块，其大小均为（k 为大于等于0的正整数）。若内存容
量为
则空闲块大小只能是由同一大块分裂而得的两个小块互称“伙伴空
（若）
，
如内存大小为
间”
或的块分裂成两个大小为的块。只有两个“伙伴空间”才能合并成一个大（若
（2）和边界标识法的不同
边界标识法在每块的首尾均有“占用”/“空闲”标志，空闲块合并方便。伙伴系统算法简单、速度快，但只有互为伙伴的两个空闲块才可合并，因而易产生虽空闲但不能归并的碎片。
6． 数据类型和抽象数据类型是如何定义的? 二者有何相同和不同之处? 抽象数据类型的主要特点是什么? 使用抽象数据类型的主要好处是什么？
【答案】（1）数据类型的定义
数据类型是程序设计语言中的一个概念，它是一个值的集合和操作的集合。如c 语言中的整
，其操作有加、减、乘、除、型、实型、字符型等。整型值的范围（对具体机器都应有整数范围）
求余等。实际上数据类型是厂家提供给用户的已实现了的数据结构。
（2）抽象数据类型的定义
“抽象数据类型（ADT ）”指一个数学模型及定义在该模型上的一组操作。“抽象”的意义在于数据类型的数学抽象特性。抽象数据类型的定义仅取决于它的逻辑特性，而与其在计算机内部
如何表示和实现无关。无论其内部结构如何变化，只要它的数学特性不变就不影响它的外部使用。
（3）两者的不同
抽象数据类型和数据类型实质上是一个概念。此外，抽象数据类型的范围更广，它已不再局限于机器已定义和实现的数据类型，还包括用户在设计软件系统时自行定义的数据类型。
（4）抽象数据类型的主要特点
请空间。起始地址为P ，
大小为的内存块，其伙伴的起始地址为：）。
，而是向“科学”迈进了一步。 抽象数据类型的出现使程序设计不再是“艺术”
（5）使用抽象数据类型的好处
使用抽象数据类型定义的软件模块含定义、表示和实现三部分，封装在一起，对用户透明（提
，而不必了解实现细节。 供接口）
7． 请写出应填入下列叙述中（ ）内的正确答案。
排序有各种方法，如插入排序、快速排序、堆排序等。
设一数组中原有数据如下：15，13，20，18，12，60。下面是一组用不同排序方法进行一遍排序后的结果。
（ ）排序的结果为：12，13，15，18，20，60
（ ）排序的结果为：13，15，18，12，20，60
（ ）排序的结果为：13，15，20，18，12，60
（ ）排序的结果为：12，13，20，18，15，60
【答案】①快速排序②起泡排序③直接插入排序④堆排序
8． 某请求分页系统的局部页面置换策略如下：系统从0时刻开始扫描，每隔5个时间单位扫描
，本轮没有被访问过的页框将被系统回收，并放入到空闲页框链一轮驻留集（扫描时间忽略不计）
尾，其中内容在下一次被分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲页框链表中，则重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。假设不考虑其他进程的影响和系统开销，初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为32、15、21、41。进程
（1）访问
（2）访问
（3）访问
【答案】
（1）页框号为21。因为起始驻留集为空，而0页对应的页框为空闲链表中的第三个空闲页框，其对应的页框号为21。
（2）页框号为32。理由：因11>10故发生第三轮扫描，页号为1、3的页框32、15在第二轮已处于空闲页框链表中，此刻1页又被重新访问，因此应被重新放回到驻留集中。其页框号为32。
（3）页框号为41。理由：因为第2页从来没有被访问过，它不在驻留集中，因此从空闲页框链表中取出链表头的页框41，页框号为41。
（4）适合。理由：如果程序的时间局部性越好，从空闲页框链表中重新取回的机会越大，该策略的优势越明显。
P 依次访问的<虚拟页号，访问时刻>是
：请回答下列问题。 时，对应的页框号是什么？ 时，对应的页框号是什么? 说明理由。 . 时，对应的页框号是什么? 说明理由。 （4）该策略是否适合于时间局部性好的程序? 说明理由。
相关内容
相关标签