|
A 卷第卷第卷第卷第 1 页页页页
山东轻工业学院山东轻工业学院山东轻工业学院山东轻工业学院
2002002002007777 年攻读硕士学位研究生入学考试试题年攻读硕士学位研究生入学考试试题年攻读硕士学位研究生入学考试试题年攻读硕士学位研究生入学考试试题
（答案一律写在答题纸上，答在试题上无效，试题附在答卷内交回）
考 试 科 目：数据结构
试题适用专业：计算机应用技术 A 卷共卷共卷共卷共 2 页页页页
一一一一、、、、填空填空填空填空题题题题（（（（每空每空每空每空 2 分分分分，，，，共共共共 10 分分分分））））
1、广义表((a),a)的表头为 （1） ，表尾为 （2） 。
2、 已知二维数组 M，每个元素的存储占 3 个单元，行下标 i 的范围从 1 到 8，列下
标 j 的范围从 1 到 10，从首地址 SA 开始连续存放在存储器内，若按行优先存储，
则元素 M[8][5]的地址是 （3） 。
3、深度为 h（h≥1）的完全二叉树至少有 （4）个结点。
4、从有序表｛3,6,9,13,21,37,50,78,90｝中，用二分法检索出 13 需要 （5） 次比较。
二二二二、、、、简要回答下列问题简要回答下列问题简要回答下列问题简要回答下列问题（（（（共共共共 88 分分分分）
1、（5 分）有 3 个元素，其入栈次序为：A，B，C，写出各种可能的出栈次序。
2、（5 分）树和二叉树之间有什么样的区别与联系？
3、（5 分）快速排序是在所有情况下排序速度最快吗？为什么？
4、（5 分）如果通信字符 a,b,c,d 出现频度分别为：7，
5，2，4。请画出哈夫曼树并给出相应的哈夫曼编
码。
5、已知一棵二叉树如图 1 所示，要求：
(1) （6 分）写出此二叉树的先序、中序、后序遍历
序列；
(2) （6 分）对此二叉树进行中序线索化；
(3) （4 分）将此二叉树变换为森林；
(4) （2 分）用先序遍历该森林，写出遍历后的结点
序列。
6、已知一无向图如图 2 所示，要求：
(1) （4 分）给出该图的邻接矩阵；
(2) （4 分）依据该图的邻接矩阵，写出从顶点 1 出发对图进行深度优先遍历和
广度优先遍历得到的顶点序列；
(3) （6 分）写出用克鲁斯卡尔（Kruskal）算法构造该图的最小生成树的过程。
A
B C
D E
G
F
图1
，更多更新年份持续更新，请在本站的考博信息网|www.kaoboinfo.com中的“考研试卷库”学校栏目中查询下载。
|
您现在的位置： 
