2018年内蒙古科技大学信息工程学院408计算机学科专业基础综合之数据结构考研核心题库
● 摘要
一、算法设计题
1． 当一棵有n(
) 个结点的二叉树按顺序存储方式存储在
中时，试写一个算法，求
出二叉树中结点值分别为X 和Y 的两个结点的最近公共祖先结点的值。
【答案】算法如下:
二叉树顺序存储在数组
中，本算法求结点i 和j 的最近公共祖先结点的值
下标为i 的结点的双亲结点的下标
下标为j 的结点的双亲结点的下标
所査结点的最近公共祖先的下标是
，值是
设元素类型为
整型
2． 有n 个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法(注:双向起泡排序即相邻两趟排序向相反方向起泡) 。
【答案】算法如下:
对存储在带头结点的双向链表head 中的元素进行双向起泡排序
设标记
双向链表尾，算法过程中是向上起泡的开始结点
是工作指针，指向当前结点
假定本趟无交换
向下(右) 起泡，一趟有一个最大元素沉底
交换两结点指针，涉及6条链
有交换
先将结点从链表上摘下
将temp 插到p 结点前
无交换，指针后移
准备向上起泡
向上(左) 起泡，一趟有一个最小元素冒
出
交换两结点指针，涉及6条链
有交换
先将temp 结点从链表上摘
下
将temp 插到p 结点后(右
)
无交换，指针前移
准备向下起泡
算法结束
3． 编写对有序表进行顺序查找的算法，并画出对有序表进行顺序查找的判定树。假设每次查找时的给定值为随机值，又查找成功和不成功的概率也相等，试求进行每一次查找时和给定值进行比较的关键字个数的期望值。
【答案】算法如下:
在具有个元素的有序表R 中，顺序査找值为K 的结点，査找成功返回其位置
否则返回-1表示失败
元素序号
结束
，查找失败的平均查找
期望值分析:在等概率情况下，则查找成功的平均查找长度为
长度为(n+2)/2(失败位置除小于每一个，还存在大于最后一个) 。若查找成功和不成功的概率也相等，则查找成功时和关键字比较的个数的期望值约为。
4． 编写一算法，利用叶结点中的空指针域将所有叶结点链接为一个带有头结点的双链表，算法返回头结点的地址。
【答案】算法如下:
全局变量链表头指针
将
若bt 不空
树中的所有叶结点链成带头结点的双链表
中序遍历左子树
叶结点
第一个叶结点
生成头结点
头结点的左链空，右链指向第一个结点
第一个叶结点左链指向头结点，pre 指向当前叶结点
中序遍历右子树
最后一个叶结点的右链置空(链表结束标记
)
结束
；
5． 假设以I 和0分别表示入栈和出栈操作。栈的初态和终态均为空，入桟和出找的操作序列可表示为仅由I 和0组成的序列，称可以操作的序列为合法序列，否则称为非法序列。
(1)下面所示的序列中哪些是合法的？
A.
B.
C.
D.
(2)通过对(1)的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true ，否则返回false(假定被判定的操作序列已存入一维数组中) 。
【答案】(1)A和D 是合法序列，B 和C 是非法序列。 (2)设被判定的操作序列已存入一维数组A 中，算法如下:
//判断字符数组A 中的输入输出序列是否是合法序列。
//i为下标
//j和k 分别为I 和字母O 的个数
//入栈次数增
1
//不论A[i]是’I'或’〇' ，指针i 均后移
//算法结束
当前叶结点链入双链表
相关内容
相关标签