2017年淮北师范大学数据结构考研复试核心题库
● 摘要
一、应用题
1． 已知有5个顶点的图G 如下图所示
请回答下列问题
（1）写出图G 的邻接矩阵A （行、列下标从0开始）。 （2）求什么？
【答案】（1）邻接矩阵为
矩阵
中位于0行3列元素值的含义是什么？
非零元素的含义是
（3）若已知具有n （n>=2）个顶点的邻接矩阵为B ，则
（2）
为：
0行3列的元素的含义是顶点0到顶点3间是相通的，并且路径长度为2的路径有2条。 （3）
中非零元素的含义是：假设此顶点位于i 行j 列，表示从i 结点到j 结点路径长度为
m 的路径的条数。
2． 用一个数组S （设大小为MAX ）作为两个堆栈的共享空间。请说明共享方法，栈满/栈空的，其中i 为0或1，用判断条件，并用C 语言或PASCAL 语言设计公用的入栈操作push （i ，x ）于表示栈号，x 为入栈值。
，栈底设在数组的两端，两栈顶相邻时为栈满。设【答案】两栈共享一向量空间（一维数组）
共享数组为S[MAX]，则一个栈顶指针为一1，另一个栈顶指针为MAX 时，栈为空。用C 语言写
的入栈操作push （i ，x ）如下：
3． 文件F 由200条记录组成，记录从1开始编号，用户打开文件后，欲将内存中的一条记录插入文件F 中，作为其第30条记录，请回答下列问题，并说明理由。
（1）若文件系统为顺序分配方式，每个存储块存放一条记录，文件F 的存储区域前后均有足够空闲的存储空间，则要完成上述操作最少要访问多少存储块？ F 的文件控制区内容会有哪些改变？
（2）若文件系统为链接分配方式，每个存储块存放的一条记录和一个链接指针，则要完成上述操作最少要 访问多少存储块？若每个存储块大小为1KB ，其中4个字节存放指针，则该系统支撑文件的最大长度是多少？
【答案】（1）因为要最少访问，所以选择将前29块前移一个存储块单元，然后将要写入的记录写入到当前的第30条的位置上。由于前移都要先访问原存储块将数据读出，再访问目标存储块将数据写入，所以最少需要访问
块存储块
F 的文件区的文件长度加1，起始块号减1
（2）采用链接方式则需要顺序访问前29块存储块，然后将新纪录的存储块插入链中即可，把新的块存入磁盘要1次访存，然后修改第29
块的链接地址存回磁盘又一次访存。一共就是
次。
4个字节的指针的地址范围为
所以此系统支撑文件的最大长度为
4． 两个字符串s1和s2的长度分别为m 和n 。求这两个字符串最大共同子串算法的时间复杂度，并简要说明理由。 为T （m ，n ）。估算最优的T （m , n ）
【答案】最优的T （m ，n ）是D （n ）。串S2是串S1的子串，且在S1中的位置是1。开始求出最大公共子串的长度恰是串S2的长度。一般情况下，
5． 在采用线性探测法处理冲突的哈希表中，所有同义词在表中是否一定相邻？
【答案】不一定相邻。哈希地址为同义词，都争夺哈希地址i 。
6． 请回答下列关于堆（Heap ）的一些问题：
（1）堆的存储表示是顺序的还是链接的？
（2）设有一个最小堆，即堆中任意结点的关键码均不大于它的左子女和右子女的关键码。其具有最大值的元素可能在什么地方？
（3）对n 个元素进行初始建堆的过程中，最多做多少次数据比较（不用大0表示法）？ 【答案】（1）堆的存储是顺序的。
（2）最大值元素一定是叶结点，在最下两层上。
（3）在建含有n 个元素、深度为h 的堆时，其比较次数不超过4n ，推导如下： 由于第i 层上的结点数至多是
以它为根的二叉树的深度为
则调用
次筛选算
法时总共进行的关键字比较次数不超过下式之值：
7． 证明：在二叉树的三种遍历序列中，所有叶结点间的先后关系都是相同的。要求毎步论断都指出根据。
【答案】前序遍历是“根左右”. 中序遍历是“左根右”. 后序遍历是“左右根”。若将“根”去掉，三祌遍历就剩“左右”。三种遍历中的差别耽足访问根结点的时机不同。二叉树是递归定义的，对左右子树均是按左右顺序来遍历的，因此所有叶结点间的先后关系都是相同的。
8． 设某文件经内排序后得到100个初始归并段（初始顺串），若使用多路归并排序算法，并要求三趟归并完成排序，问归并路数最少为多少？
【答案】设归并路数为k ，归并趟数为s ，则最少5-路归并完成排序。
因
且k 为整数，故k=5，即
的关键字，和为解决冲突形成的探测序列f 的
二、算法设计题
9． 设给定关键字输入序列为（100，90，120，60，78，35，42，31，15）用哈希法散列0-10的地址区间。要求设计一合理的哈希函数；冲突时用链表法解决，写出哈希算法，并构造出哈希表，在等概率查找情况下查找成功的平均查找长度是多少？
【答案】算法如下：