2018年东北大学信息科学与工程学院842计算机专业基础之数据结构考研基础五套测试题
● 摘要
一、综合题
1． 在改进了的(无回溯) 字符串模式匹配中，要先求next 数组的值。下面是求nextval 值的算法。
{在模式P 中求nextval 数组的值
}
算法中第4行有P[J]＝P[K]，第六行中也有P[J]＝P[K]。两处比较语句相同。请分析说明此两处比较语句的含义是什么? 分析此算法在最坏情况下的时间复杂度是多少？
【答案】第4行的P[J]＝P[K]语句是测试模式串的第J 个字符是否等于第K 个字符，如是，则指针J 和K 均增加1，继续比较。第6行的p[J]＝p[K]语句的意义是，当第J 个字符在模式匹配中失配时，若第K 个字符和第J 个字符不等，则下个与主串匹配的字符是第K 个字符；否则，若第K 个字符和第J 个字符相等，则下个与主串匹配的字符是第K 个字符失配时的下一个(即NEXTV AL[K])。该算法在最坏情况下的时间复杂度0(m2)。
2． 某请求分页系统的局部页面置换策略如下:系统从0时刻开始扫描, 每隔5个时间单位扫描一轮驻留集(扫描时间忽略不计) , 本轮没有被访问过的页框将被系统回收, 并放入到空闲页框链尾, 其中内容在下一次被分配之前不被清空。当发生缺页时, 如果该页曾被使用过且还在空闲页框链表中, 则重新放回进程的驻留集中; 否则, 从空闲页框链表头部取出一个页框。假设不考虑其他进程的影响和系统开销, 初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为32、15、21、41。进程P 依次访问的<虚拟页号, 访问时刻>是:
。
请回答下列问题。
(1)访问<0, 4>时, 对应的页框号是什么？
(2)访问<1, 11>时, 对应的页框号是什么? 说明理由。
(3)访问<2, 14>时, 对应的页框号是什么? 说明理由。
(4)该策略是否适合于时间局部性好的程序? 说明理由。
【答案】(1)页框号为21。因为起始驻留集为空, 而0页对应的页框为空闲链表中的第三个空闲页框, 其对应的页框号为21。
(2)页框号为32。理由:因11>10故发生第三轮扫描, 页号为1、3的页框32、15在第二轮已处于空闲页框链表中, 此刻1页又被重新访问, 因此应被重新放回到驻留集中。其页框号为32。
(3)页框号为41。理由:因为第2页从来没有被访问过, 它不在驻留集中, 因此从空闲页框链表中取出链表头的页框41, 页框号为41。
(4)适合。理由:如果程序的时间局部性越好, 从空闲页框链表中重新取回的机会越大, 该策略的优势越明显。
3． 已知有5个顶点的图如下图所示
图
请回答下列问题
(1)写出上图的邻接矩阵A(行、列下标从0开始) 。
(2)求A2, 矩阵
(3)
若已知具有
么？
【答案】(1)邻接矩阵为
中位于0行3列元素值的含义是什么？ 个顶点的邻接矩阵为B ,
则非零元素的含义是什
(2)为:
0行3列的元素的含义是顶点0到顶点3间是相通的, 并且路径长度为2的路径有2条。 (3)中非零元素的含义是:假设此顶点位于i 行j 列, 表示从i 结点到j 结点路径长度为m 的路径的条数。。
4． 以归并算法为例，比较内部排序和外部排序的不同，说明外部排序如何提高操作效率。
【答案】(1)内部排序中的归并排序是在内存中进行的归并排序，辅助空间为O(n)。外部归并排序是将外存中的多个有序子文件合并成一个有序子文件，将每个子文件中记录读入内存后的排序方法可采用多种内排序方法。外部排序的效率主要取决于读写外存的次数，即归并的趟数。
(2)因为归并的趟数，其中，m 是归并段个数，k 是归并路数。增大k 和减少m 都可减少归并趟数。应用中通过败者树进行多(k)路平衡归并和置换一选择排序减少m ，来提高外部排序的效率。
5． 输入一个正整数序列(53，17，12，66，58，70，87，25，56，60) ，试完成下列各题。
(1)按次序构造一棵二叉排序树BS 。
(2)依此二叉排序树，如何得到一个从大到小的有序序列？
(3)画出在此二叉排序树中删除“66”后的树结构。
【答案】(1)构造的二叉排序树如图1所示:
图1二叉排序树
(2)若二叉树非空，要得到一个从大到小的有序序列可以先中序遍历右子树；再访问根结点；最后中序遍历左子树。
(3)如图2所示: