2018年中国科学技术大学信息科学技术学院834软件工程基础[专业硕士]之数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1． 当一棵有n(
) 个结点的二叉树按顺序存储方式存储在
中时，试写一个算法，求
出二叉树中结点值分别为X 和Y 的两个结点的最近公共祖先结点的值。
【答案】算法如下:
二叉树顺序存储在数组
中，本算法求结点i 和j 的最近公共祖先结点的值
下标为i 的结点的双亲结点的下标
下标为j 的结点的双亲结点的下标
所査结点的最近公共祖先的下标是
整型
2． 对给定关键字序号j(1 ，值是 设元素类型为 中找到关键字从小到大排在第j 位上的记 录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间) 。 例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下； 在后半部分继续进行划分 在前半部分继续进行划分 3． 给定nxm 矩阵并设 设计一算法判定x 的值是否在A 中，要求时间复杂度 为O(m＋n) 。 【答案】算法如下: //n*m矩阵A ，行下标从a 到b ，列下标从c 到d ，本算法査找x 是否在矩阵A 中 //flag是成功査到x 的标志 //假定x 为整型 (“矩阵A 中无 算法search 结束。 4． 已知顺序表中有m 个记录，表中记录不依关键字有序排列，编写算法为该顺序表建立一个有序的索引表，索引表中的每一项含记录的关键字和该记录在顺序表中的序号，要求算法的时间复杂度在最好的情况下能达到O(m)。 【答案】算法如下: 顺序表中记录个数 关键字 该关键字在顺序表中的下标 索引表的一项 关键字 记录中的其他数据 给有m 个记录的顺序表seq 建立索引表 index 监视哨 关键字放入正确位置 第i 个记录的下标 元素\n"，x) ； 5． 试编写一算法对二叉树按前序线索化。 【答案】算法如下: 设置前驱 对以线索链表为存储结构的二叉树BT 进行前序线索化 设置左线索 设置前驱的右线索 为建立右链做准备 前驱后移 左子树前序线索化 右子树前序线索化 结束 二、应用题 6． (1)判定起泡排序的结束条件是什么？ (2)请简单叙述希尔排序的基本思想。 (3)将下列序列调整成堆(堆顶为最小值) 。 (4)在16个关键字中选出最小的关键字至少要进行多少次比较? 再选出次小的关键字至少要进行多少次比较? 请简要说明选择的方法和过程。 【答案】(1)至多进行n －1趟起泡排序，或一趟起泡排序中未发生交换(即已有序) 时，结束排序。 (2)希尔排序是对直接插入排序算法的改进，它从“记录个数少”和“基本有序”出发，将待排序的记录划分成几组(缩小增量分组) ，从而减少参与直接插入排序的数据量，当经过几次分组排序后，记录的排列已经基本有序，这个时候再对所有的记录实施直接插入排序。 (3)13，24，33，65，70，56，48，92，80，112 (4)采用树形锦标赛排序选出最小关键字至少要15次比较。再选出次小关键字比较4次(两两比较8次选出8个优胜，再两两比较4次选出4个优胜，半决赛两场，决赛一场，共比较了15次。将冠军的叶结点改为最 大值，均与兄弟比较，共4次选出亚军) 。 7． 己知n 阶下三角矩阵A(即当i ＜j 时，有序分配方式时在B 中确定元素 ) ，按照压缩存储的思想，可以将其主对角线以 下所有元素(包括主对角线上元素) 依次存放于一维数组B 中，请写出从第一列开始采用列序为主 的存放位置的公式。 第1列有n 个元素，第j 列有n ﹣j ＋1个 【答案】2阶下三角矩阵元素