2017年南京师范大学数据结构(同等学力加试)考研复试核心题库
● 摘要
一、应用题
1． 试叙述动态存储分配伙伴系统的基本思想，它和边界标识法不同点是什么？
【答案】（1）动态存储分配伙伴系统的基本思想
在伙伴系统中，无论占用块或空闲块，其大小均为（k 为大于等于0的正整数）。若内存容
量为
则空闲块大小只能是
由同一大块分裂而得的两个小块互称“伙伴空
（若
）
，
如内存大小为
间”或
的块分裂成两个大小为的块。只有两个“伙伴空间”才能合并成一个大（若
（2）和边界标识法的不同
边界标识法在每块的首尾均有“占用”/“空闲”标志，空闲块合并方便。伙伴系统算法简单、速度快，但只有互为伙伴的两个空闲块才可合并，因而易产生虽空闲但不能归并的碎片。
2． 设目标为 模式为
（1）计算模式p 的nextval 函数值；
（2）不写出算法，只画出利用KMP 算法进行模式匹配时每一趟的匹配过程。 【答案】（1）P 的nextval 函数值为0110132（P 的next 函数值为0111232）。 （2）利用KMP （改进的nextval ）算法，每趟匹配过程如下： 第一趟匹配：abcab （i=5, j=5） 第二趟匹配：abc （i=7，j=3） 第三趟匹配：a （i=7，j=l） 第四趟匹配：
（成功）abcabaa （i=15，j=8）
3． 已知n 阶下三角矩阵A （即当
时，有
，按照压缩存储的思想，可以将其主对角线以）
）。
空间。起始地址为P ，
大小为的内存块，其伙伴的起始地址为：
下所有元素（包括主对角线上元素）依次存放于一维数组B 中，请写出从第一列开始采用列序为主序分配方式时在B 中确定元素的存放位置的公式。
【答案】2
阶下三角矩阵元素第1列到第
列是梯形，元素数为
第1列有n 个元素，第j 列有而在第j 列上的位置是为
个元素，所以n
阶下三角矩阵A 按列存储，其元素在一维数组B 中的存储位置k 与i 和j 的关系为：
4． 已知世界六大城市为：北京（Pe ）、纽约（N ）、巴黎（Pa ）、伦敦（L ）、东京（T ）、墨西哥，下表给定了这六 大城市之间的交通里程：
（M ）
（1）画出这六大城市的交通网络图； （2）画出该图的邻接表表示法；
（3）画出该图按权值递增的顺序来构造的最小（代价）生成树。 【答案】（1）这六大城市的交通网络图如图1所示：
图1
（2）该图的邻接表表示法如图2所示：
图2
（3）最小生成树有6个顶点与条边：V （G ）={Pe，N ，Pa ，L , T，M}
E （G ）=（ {（L , Pa, 3）, （Pe , T, 21）, （M , N, 32）, （L , N, 55）, （L , Pe, 81）}
5． 将下列出三棵树组成的森林转换为二叉树（只要求给出转换结果）。
图1
【答案】森林转换为二叉树分以下三步：
（1）连线（将兄弟结点相连，各树的根看作兄弟）。
（2）切线（保留最左边子女为独生子女，将其他子女分支切掉）。 （3）旋转（以最左边树的根为轴. 顺时针向下旋转45度）。 所以由上面三棵树转换得到的二叉树如图2所示：
图2
6． 给出模式串
在KMP 算法中的next 和nextval 数组。
【答案】模式串的next 函数定义如下：
根据此定义，
可求解模式串
的next 和nextval 值如下：