长春理工大学数据结构2017年真题

春理工大学

2017年全国硕士研究生统一入学考试自命题试题

********************************************************************************************

学科与专业名称：计算机科学技术学院所有专业

考试科目代码与名称：809数据结构

】考试科目：数据结构共4 页，第1页

考试科目：数据结构共 4 页，第2 页

三．简答题（共60分）

1.已知一棵二叉树的中序为CDBAGFHE, 后序为DCBGHFEA,画出这棵二叉树的先序和后序线索二叉树.(6分)

2.对下列关键字序列进行快速排序(从小至大) (48, 38, 65, 95, 73, 13, 27, 50)要求给出快速排序的算法思想,并画出排序过程示意图。（10）

3.如图所示，求出改图的最短路径和拓扑排序，用2种方法画出图二的最小生出树。（14）

图一图二

4.已知输入关键字序列为（100,90,120,60,78,35,42,31,15）地址区间为0～11。设计一个哈希表函数把上述关键字散到0～11中，画出散列表（冲突用线性探测法）；写出查找算法，计算在等概率情况下查找成功的平均查找长度。（15）

5.设有关键码序列10,20,35,40,44,51,65,70,85,91,93,95。试试着写出冒泡排序，快速排序，直接插入排序，希尔排序。(15分)

考试科目：数据结构共4 页，第3 页

考试科目：数据结构共 4 页，第 4 页