2018年广西大学计算机与电子信息学院408计算机学科专业基础综合之数据结构考研核心题库
● 摘要
一、算法设计题
1． 己知L 为链表的头结点地址，表中共有m(m＞3) 个结点，从表中第i 个结点(l＜i ＜m) 起到第m 个结点构成一个循环部分链表，设计将这部分循环链表中所有结点顺序完全倒置的算法。
【答案】算法如下:
//L是有m 个结点的链表的头结点的指针。表中从第个结点到第m 个结点构成循环部分链表//本算法将这部分循环链表倒置
//p是工作指针，初始指向第二结点(已假定i ＞
l) //pre是前驱结点指针，最终指向第i ﹣i 个结点
//计数器
//查找第i 个结点
//査找结束，P 指向第i 个结点
//暂存第i 个结点的指针
//p指向第i ＋l 个结点，准备逆置
//上面while 循环结束时，j ＝i ﹣1现从第i ＋1结点开始逆置
//暂存P 的后继结点
+
//逆置P 结点
//P恢复为当前待逆置结点
//计数器增
1
//将原第i 个结点的后继指针指向原第m 个结点
2． 设T 是一棵满二叉树，写一个把T 的后序遍历序列转换为前序遍历序列的递归算法。
【答案】算法如下:
将满二叉树的后序序列转为前序序列，
第 2 页，共 39 页
是序列初始和最后结点的下
标。
根结点
左子树或右子树的结点数
将左子树前序序列转
为后序序列
将右子树前序序列转为
后序序列
3． 已知二叉树丁的结点形式为(llink，data ，count ，riink) ，在树中查找值为X 的结点，若找到， 则记数(count)加1; 否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。
【答案】算法如下:
在二叉排序树t 中査找值为x 的结点，若査到，则其结点的count 域值增1，否则，
将其
插入到二叉排序树中
f 指向当前结点的査找值为x 的结点，
双亲
无值为x 的结点，插入之
査询成功，值域为x 的结点的count 增
1
4． 编写递归算法，从大到小输出给定二叉排序树中所有关踺字不小于X 的数据元素。要求你的算法的时间复杂度为
【答案】算法如下:
从大到小输出二叉排序树bst 中所有关键字不小于x 的数据元素
第 3 页，共 39 页
，其中，2为排序树中所含结点数，m 为输出的关键字个数。
5． 己知两个定长数组，它们分别存放两个非降序有序序列，请编写程序把第二个数组序列中的数逐个插入到前一个数组序列中，完成后两个数组中的数分别有序(非降序) 并且第一数组中所有的数都不大于第二个数组中的任意一个数。注意，不能另开辟数组，也不能对任意一个数组进行排序操作。
例如:
第一个数组为:4，12，28 第二个数组为:1，7，9，29，45 输出结果为:
第一个数组
第二个数组
【答案】算法如下:
//A和B 是各有m 个和n 个整数的非降序数组，本算法将B 数组元素逐个插入到A 中 //使A 中各元素均不大于B 中各元素，且两数组仍保持非降序排列
.
" 交换A[m﹣1]和
B[0]
//寻找A[m﹣1]的插入位置
//寻找B[0]的插入位置
算法结束
二、应用题
6． 某计算机主存按字节编址, 逻辑地址和物理地址都是32位, 页表项大小为4字节。请回答下列问题。
(1)若使用一级页表的分存储管理方式, 逻辑地址结构为:
则页的大小是多少字节？页表最大占用多少字节？ (2)若使用二级页表的分存储管理方式, 逻辑地址结构为:
设逻辑地址为LA , 请分别给出其对应的页目录号和表索引达式。
第 4 页，共 39 页