2018年齐鲁工业大学信息学院872数据结构考研基础五套测试题
● 摘要
一、应用题
1． 设目标为
(1)计算模式p 的nextval 函数值；
(2)不写出算法，只画出利用KMP 算法进行模式匹配时每一趟的匹配过程。
【答案】(1)P的nextval 函数值为0110132(P的next 函数值为0111232) 。
(2)利用KMP(改进的nextval) 算法，每趟匹配过程如下:
第一趟匹配:abcaabbabcabaacbacba
abcab(i＝5，j ＝5)
第二趟匹配:abcaabbabcabaacbacba
abc(i＝7jj ＝3)
第三趟匹配:abcaabbabcabaacbacba
a(i＝7，j ＝l)
第四趟匹配:abcaabbabcabaacbacba
(成功)abcabaa(i＝15，j ＝8)
2． 对于具有n 个叶结点且所有非叶结点都有左、右孩子的二叉树。
(1)试问这种二叉树的结点总数是多少？
(2)试证明。其中:表示第i 个叶结点所在的层号(设根结点所在层号为1) 。 ，模式为
【答案】(1)根据二叉树中度为2的结点个数等于叶结点个数减1的性质，故具有n 个叶结点且非叶子结点均有左子树的二叉树的结点数是2n －1。
(2)当i=1时，，公式成立。设当i=n－1时公式成立，证明当i=n时公式仍成立。 设某叶结点的层号为t ，当将该结点变为内部结点，从而再增加两个叶结点时，这两个叶结点的层号都是t+1，对于公式的变化，是减少了一个原来的叶结点，增加了两个新叶结点，反映到公
，所以结果不变，这就证明当i=n时公式仍成立。 式中，因为
3． 设依以下次序给出关键字:34，16，19，21，5，49，24，62，3，17，45，8，构造3阶B-树。要求从空树开始，每插入一个关键字，画出一棵树。
【答案】如图所示:
图
4． 在某程序中，有两个栈共享一个一维数组空间SPACE[N]、SPACE[0]、SPACE[N﹣1]分别是两个栈的栈底。
(1)对栈1、栈2，试分别写出(元素X) 入栈的主要语句和出栈的主要语句。
(2)对栈1、栈2，试分别写出栈满、栈空的条件。
【答案】(1)入栈主要语句
//设X 为入栈元素
.
出栈主要语句
//返回出栈元素
//返回出栈元素
(2)
栈满条件:top2﹣topl ＝l
栈空条件:topl ＝﹣l 并且top2＝N //topl＝﹣l 为左栈空，top2＝N 为右栈空
5． 某网络中的路由器运行OSPF 路由协议, 下表是路由器R1维护的主要链路状态信息(LSI), 下图是根据下表及R1的接口名构造出来的网络拓扑。
表 R1所维护的LSI
图 R1构造的网络拓扑
请回答下列问题。
本题中的网络可抽象为数据结构中的哪种逻辑结构？
针对上表中的内容, 设计合理的链式存储结构, 以保存上表中的链路状态信息(LSI)。要求给出链式存储结构的数据类型定义, 并画出对应上表的链式存储结构示意图(示意图中可仅以ID 标识节点) 。
按照迪杰斯特拉(Dijiksta)算法的策略, 依次给出R1到达上图中子网
用。
【答案】(1)图
(2)使用图的邻接表存储结构进行存储, 数据类型定义如下:
的最短路径及费