2018年齐鲁工业大学理学院872数据结构考研强化五套模拟题
● 摘要
一、应用题
1． 在模试匹配KMP 算法中所用失败函数的定义中，为何要求P 1P 2......P j 为P 1P 2......P j 两头匹配的真子串？且为最大真子串？
【答案】失败函数(即next) 的值只取决于模式串自身，若第j 个字符与主串第i 个字符失配时，假定主串不回溯，模式串用第k(即next[j])个字符与第i 个相比，有
为了不因
模式串右移与主串第i 个字符比较而丢失可能的匹配，对于上式中可能存在的多个k 值，应取其中最大的一个。这样，因j ﹣k 最小，即模式串向右滑动的位数最小，避免因右移造成可能匹配的丢失。
2． 某博物馆最多可容纳500人同时参观, 有一个出入口, 该出入口一次仅允许个通过。参观者的活动描述如下:
Cobegin
参观者进程i : {
进门;
参观; 出门; } coend
请添加必要的信号量和P 、V(或wait （ ）、signal （ ）) 操作, 以实现上述操作过程中的互斥与同步。要求写出完整的过程, 说明信号量含义并赋初值。
【答案】定义两个信号量
博物馆可以容纳的最多人数
用于出入口资源的控制
第 2 页，共 33 页
3． 对于后序线索二叉树，怎样查找任意结点的直接后继? 对于中序线索二叉树，怎样查找任意结点的直接前驱？
【答案】(1)后序线索树中结点的后继的方法如下:根结点无后继；当结点的rtag=1时，其右线索指向后继；当结点的rtag=0且是其双亲的右孩子，或是双亲的左孩子且双亲无右孩子时，其双亲是该结点的后继；当结点是其双亲的左孩子且双亲有右孩子时，其双亲结点右子树中最左下的叶结点是其后继。
(2)对中序线索二叉树的某结点，若其左标记等于1，则左孩子为线索，指向直接前驱；否则，其前驱是其左子树上按中序遍历的最后一个结点。
4． 请阅读下列算法，回答问题。
问题一:这是什么类型的排序算法，该排序算法稳定吗？
问题二:设置r[0]的作用是什么? 若将WHILE--DO 语句中判断条件改为X 。该算法将会有什么变化，是否还能正确工作？
【答案】问题一:此为直接插入排序算法，该算法稳定。
问题二:r[0]的作用是监视哨，免去每次检测文件是否到尾，提高了排序效率。 采用x.
5． 画出对算术表达式表所示。
表 操作数栈和运算符栈的变化过程
描述算法后，算法变为不稳定排序，但能正常工作。
F 求值时操作数栈和运算符栈的变化过程。
F 求值，过程如
，
【答案】设操作数栈是opnd ，运算符栈是optt ，对算术表达式
第 3 页，共 33 页
二、算法设计题
6． 按图的宽度优先搜索法写一算法判别以邻接矩阵存储的有向图中是否存在由顶点到顶点的路径
。
设有向图有n 个顶点
判断以邻接矩阵方式存储的有向图中是否存在由顶点到顶点的路径
是队列，容量足够大，元素是顶点编号
人队
到顶点
第 4 页，共 33 页
【答案】算法如下:
不存在路径