2018年五邑大学计算机学院408计算机学科专业基础综合之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 编写一算法，利用叶结点中的空指针域将所有叶结点链接为一个带有头结点的双链表，算法返回头结点的地址。
【答案】算法如下:
全局变量链表头指针
将
若bt 不空
中序遍历左子树
叶结点
第一个叶结点
生成头结点
头结点的左链空，右链指向第一个结点
第一个叶结点左链指向头结点，pre 指向当前叶结点
中序遍历右子树
最后一个叶结点的右链置空(链表结束标记
)
结束
；
2． 已知两个链表A 和B 分别表示两个集合，其元素递增排列。编一函数，求A 与B 的交集，并存放于A 链表中。
【答案】算法如下:
//设工作指针pa 和pb ；
//结果表中当前合并结点的前驱的指针
//交集并入结果表中
//释放结点空
间
第 2 页，共 36 页
树中的所有叶结点链成带头结点的双链表
当前叶结点链入双链表
//释放结点空间
//释放结点空间
//置链表尾标记
//注:本算法中也可对B 表不作释放空间的处理
3． 已知深度为h 的二叉树，以一维数组应的算法。
【答案】算法如下:
计算深度为h 、以一维数组BT 作为其存储结构的二叉树的叶结点数，n 为数组长度
记叶结点数
若结点无孩子，则
是叶子
存储在数组后一半的元素是叶结点
4． 己知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结点开始逆置
第 3 页，共 36 页
作为其存储结构，试编写一算法，求该二叉
树中叶结点的个数，为简单起见，设二叉树中元素结点为非负整数，要求写出算法基本思想及相
//暂存P 的后继结点
+
//逆置P 结点
//P恢复为当前待逆置结点
//计数器增
1
//将原第i 个结点的后继指针指向原第m 个结点
5． 已知顺序表中有m 个记录，表中记录不依关键字有序排列，编写算法为该顺序表建立一个有序的索引表，索引表中的每一项含记录的关键字和该记录在顺序表中的序号，要求算法的时间复杂度在最好的情况下能达到O(m)。
【答案】算法如下:
顺序表中记录个数
关键字
该关键字在顺序表中的下标
索引表的一项
关键字
记录中的其他数据
给有m 个记录的顺序表seq 建立索引表
index
监视哨
关键字放入正确位置
第i 个记录的下标
二、应用题
6． 设有n 个元素采用起泡排序法进行排序，通常需要进行多少趟排序? 对于第J 趟起泡通常需要进行多少次关键字比较? 在程序设计中如何设置判断条件，有可能使起泡趟数可以减少并且能完成排序。
【答案】n 个元素采用起泡排序法进行排序，通常需要进行n －1趟排序。第j 趟起泡排序要进行n －j 次比较。在一趟排序中，若没有记录交换，则表示排序完成。因而，可通过设标记来控
第 4 页，共 36 页