2018年北京市培养单位材料科学与光电技术学院408计算机学科专业基础综合之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 有n 个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法(注:双向起泡排序即相邻两趟排序向相反方向起泡) 。
【答案】算法如下:
对存储在带头结点的双向链表head 中的元素进行双向起泡排序
设标记
双向链表尾，算法过程中是向上起泡的开始结点
是工作指针，指向当前结点
假定本趟无交换
向下(右) 起泡，一趟有一个最大元素沉底
交换两结点指针，涉及6条链
有交换
先将结点从链表上摘下
将temp 插到p 结点前
无交换，指针后移
准备向上起泡
向上(左) 起泡，一趟有一个最小元素冒
出
交换两结点指针，涉及6条链
有交换
先将temp 结点从链表上摘
下
将temp 插到p 结点后(右
)
无交换，指针前移
准备向下起泡
算法结束
2． 试为二叉树写出一个建立三叉链表的算法，并在此三叉链表中删去每一个元素值为x 的结点，以及以它为根的子树，且释放相应存储空间。二叉树的三叉链表的描述为:
{二叉树根结点的指针}
【答案】算法如下:
生成三叉链表的二叉树(题目给出PASCAL 定义，下面用类C 语言书写
)
是二叉树结点指针的一维数组，容量足够大
一维数组最后元素的下标
元素或虚结点
根结点
双亲结点和子女结点用指针链上
结束
3． 假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT 中，写出计算该算术表达式值的算法。
【答案】算法如下:
以后序遍历算法求以二叉树表示的算术表达式的
值
.
求左子树表示的子表达式的值
求右子树表示的子表达式的值
4． 编写一算法，利用叶结点中的空指针域将所有叶结点链接为一个带有头结点的双链表，算法返回头结点的地址。
【答案】算法如下:
全局变量链表头指针
将
若bt 不空
中序遍历左子树
叶结点
第一个叶结点
生成头结点
头结点的左链空，右链指向第一个结点
第一个叶结点左链指向头结点，pre 指向当前叶结点
中序遍历右子树
最后一个叶结点的右链置空(链表结束标记
)
结束
；
5． 已知顺序表中有m 个记录，表中记录不依关键字有序排列，编写算法为该顺序表建立一个有序的索引表，索引表中的每一项含记录的关键字和该记录在顺序表中的序号，要求算法的时间复杂度在最好的情况下能达到O(m)。
【答案】算法如下:
顺序表中记录个数
关键字
该关键字在顺序表中的下标
索引表的一项
关键字
记录中的其他数据
树中的所有叶结点链成带头结点的双链表
当前叶结点链入双链表