2018年东北大学秦皇岛分校842计算机专业基础之数据结构考研核心题库
● 摘要
一、综合题
1． 输入一个正整数序列(53，17，12，66，58，70，87，25，56，60) ，试完成下列各题。
(1)按次序构造一棵二叉排序树BS 。
(2)依此二叉排序树，如何得到一个从大到小的有序序列？
(3)画出在此二叉排序树中删除“66”后的树结构。
【答案】(1)构造的二叉排序树如图1所示:
图1二叉排序树
(2)若二叉树非空，要得到一个从大到小的有序序列可以先中序遍历右子树；再访问根结点；最后中序遍历左子树。
(3)如图2所示:
图2
2． 已知一个整数序列
且
又如
要求:
(1)给出算法的基本设计思想。
(2)根据设计思想, 采用C 或或Java 语言描述算法, 关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度。
【答案】(1)算法的策略是从前向后扫描数组元素, 标记出一个可能成为主元素的元素Num 。
, 其中, 则称x 为A 的主元素。例如, 若存在
, 则称5为主元素; 则A 中没有主元素。假设A 中的n 个元素保存在一个一维数组中, 请设计一个尽可能高效的算法, 找出A 的主元素。若存在主元素, 则输出该元素; 否则输出-1。
然后重新计数, 确认Num 是否是主元素。
算法可分为以下两步:
①选取候选的主元素:依次扫描所给数组中的每个整数, 将第一个遇到的整数Num 保存到c 中, 记录Num 的出现次数为1; 若遇到的下一个整数仍等于Num , 则计数加1否则计数减1; 当计数减到0时, 将遇到的下一个整数保存到c 中, 计数重新记为1, 开始新一轮计数, 即从当前位置开始重复上述过程, 直到扫描完全部数组元素。
②判断c 中元素是否是真正的主元素, 再次扫描该数组, 统计c 中元素出现的次数, 若大于则为主元素; 否则, 序列中不存在主元素。
(2)算法实现如下:
用来保存候选主元素, count 用来计数
设置A
为A 中的候选主元素计数
处理不是候选主元素的情况
更换候选主元素
统计候选主元素的实际出现次数
确认候选主元素
不存在主元素
(3)时间复杂度为
, 空间复杂度为。 为候选主元素
查找候选主元素
,
3． 某请求分页系统的局部页面置换策略如下:系统从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)适合。理由:如果程序的时间局部性越好, 从空闲页框链表中重新取回的机会越大, 该策略的优势越明显。
4． 如果输入序列为123456，试问能否通过栈结构得到以下两个序列:435612和135426; 请说明为什么不能或如何才能得到。
【答案】输入序列为123456，不能得出435612，其理由是，输出序列最后两元素是12，前面4个元素(4356)得到后，栈中元素剩12，且2在栈顶，栈底元素1不可能在栈顶元素2之前出栈。得到135426的过程如下:1入栈并出栈，得到部分输出序列1; 然后2和3入栈，3出栈，部分输出序列变为13; 接着4和5入栈，5、4和2依次出栈，部分输出序列变为13542; 最后6入栈并出栈，得到最终结果135426。
5． 写出下面算法中带标号语句的频度。
TYPE
Ar ＝ARRAY[l...n]OF datatype；
PROCEDURE penn(a:ar ；k ，n :integer) ；
V AR x:datatype ；i :integer ；
BEGIN
(1)IF k＝n
THENBEGIN