2017年中山大学S3405005数学综合考试之数据结构复试仿真模拟三套题
● 摘要
一、应用题
1． 在堆排序、快速排序和合并排序中：
（1）若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法？
（2）若只从排序结果的稳定性考虑，则应选取哪种排序方法？ （3）若只从平均情况下排序最快考虑，则应选取哪种排序方法？
（4）若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？ 【答案】（1）应首先选取堆排序方法，其次选取快速排序方法，最后选取归并排序方法。 （2）应选取归并排序方法 （3）应选取快速排序方法 （4）应选取堆排序方法
2． 在采用线性探测法处理冲突的哈希表中，所有同义词在表中是否一定相邻？
【答案】不一定相邻。哈希地址为
同义词，都争夺哈希地址i 。
3． 在某程序中，有两个栈共享一个一维数组空间的栈底。
（1）对栈1、栈2, 试分别写出（元素x ）入栈的主要语句和出栈的主要语句。 （2）对栈1、栈2, 试分别写出栈满、栈空的条件。 【答案】（1）入栈主要语句
出栈主要语句
的关键字，和为解决冲突形成的探测序列f 的
分别是两个栈
（2）
4． 设有正文AADBAACACCDACACAAD ，字符集为A , B , C , D , 设计一套二进制编码，使得上述正文的编码最短。
A :1, B :000，C :01，D :001。 【答案】字符A , B , C , D 出现的次数为9, 1, 5, 3。其哈夫曼编码如下：
5． 试证明：同一棵二叉树的所有叶结点，在前序序列、对称序序列以及后序序列中都按相同的，例如前序后序运对称序。 相对位置出现（即先后顺序相同）
，中序遍历是“左根右”，后序遍历是“左右根”【答案】前序遍历是“根左右”。三种遍历中只是访问 " 根”结点的时机不同，对左右子树均是按左右顺序来遍历的，因此所有叶子都按相同的相对位罝出现。
6． 试举一例，说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其运算效率不同。
【答案】线性表中的插入、删除操作，在顺序存储方式下平均移动近一半的元素，时间复杂度为O （n ）; 而在链式存储方式下，插入和删除时间复杂度都是0（1）。
7． 设二叉树BT 的存储结构如表：
表 二叉树BT 的存储结构
其中BT 为树根结点的指针，其值为6, Lchild 、Rchild 分別为结点的左、右孩子指针域data 为结点的数据域。试完成下列各题：
（1）画出二叉树BT 逻辑结构；
（2）写出按前序、中序、后序遍历该二叉树所得到的结点序列： （3）画出二叉树的后序线索树。
【答案】（1）二叉树的逻辑结构如图1所示：
图1
（2）前序序列：ABCEDFHGIJ 中序序列：ECBHFDJIGA 后序序列：ECHFJIGDBA
（3）:二叉树的后续线索树如图2所示：
图2
8． 设依以下次序给出关键字：34，16，19，21，5，49，24，62，3，17，45，8，构造3阶树。要求从空树开始，每插入一个关键字，画出一棵树。
【答案】如图所示：
图
二、算法设计题