2018年北京师范大学脑与认知科学研究院408计算机学科专业基础综合之数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1． 假定用两个一维数组L 【N 】和R 【N 】作为有N 个结点1，2，…，N
的二叉树的存储结构。
和
分别指示结点i 的左儿子和右儿子，
，使
) 表示i 的左(右) 儿子为空。试写一个
存放结点i 的父亲；然后再写一个判别结点u 是否
算法，由L 和R 建立一个一维数组为结点V 的后代的算法。
【答案】算法如下:
和
是含有N 个元素且指示二叉树结点i 左儿子和右儿子的一维数组
T 数组初始化
若结点i 的左子女是则结点L 的
双亲是结点
i
若结点i 的右子女是R , 则R 的
双亲是
i
判断U 是否是V 的后代
2． 以顺序存储结构表示串，设计算法。求串S 中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。
【答案】算法如下:
//串用一维数组s 存储，本算法求最长重复子串，返回其长度
//index记最长的串在s 串中的开始位置，max
记其长度
//length记局部重复子串长度，i 为字符数组下标
//上一个重复子串结束
//当前重复子串长
第 2 页，共 37 页
本算法据此建立结点i 的双亲数组T , 并判断结点U 是否是结点V 的后代
度大，则更新
max
//初始化下一重复子串的起始位置和长度
(”最长重复子串的长度为
.//算法结束
，在串中的位置
，max ，index) ；
时间复杂度:算法的时间复杂度为O(n)，每个字符与其后继比较一次。 3． 对给定关键字序号j(1 中找到关键字从小到大排在第j 位上的记 录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间) 。 例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下； 在后半部分继续进行划分 在前半部分继续进行划分 4． 请运用快速排序思想，设计递归算法实现求n(n>1)个不同元素集合中的第f( 【答案】算法如下: 第 3 页，共 37 页 ) 小元素。 在后半部分继续进行划分 在前半部分继续进行划分 5． 试编写一算法对二叉树按前序线索化。 【答案】算法如下: 设置前驱 对以线索链表为存储结构的二叉树BT 进行前序线索化 设置左线索 设置前驱的右线索 为建立右链做准备 前驱后移 左子树前序线索化 右子树前序线索化 结束 二、应用题 6． 有A 、B 两人通过邮箱进行辩论, 每人都从自己的信箱中取得对方的问题。将答案和向对方提出的新问题组成一个邮件放入对方的邮箱中, 设A 的信箱最多放M 个邮件, B 的信箱最多放N 个邮件。初始时A 的信箱有x 个邮件(0 A 、B 两人操作过程: 当信箱不为空时, 辩论者才能从信箱中取邮件, 否则等待。 当信箱不满时, 辩论者才能将新邮件放入信箱, 否则等待。 第 4 页，共 37 页
相关内容
相关标签