中国人民公安大学数据结构2004年考研真题考研试题

中国人民公安大学 2004 年硕士研究生入学考试
数据结构试题（425）
请将所有答案标明题号，写在答题本上，试题纸上请勿答题。严禁在答题
纸密封线以外留下姓名、考号等任何标记，否则该卷无效。
一、名词解释或名词比较（每题 5 分，共 30 分）
1． 区别数据结构与数据类型
2． 区别广义表与线性表
3． 哈夫曼树
4． 区别深度优先搜索遍历和广度优先搜索遍历
5． 堆
6． 哈希表
二、简答题（每题 10 分，共 60 分）
1． 何谓算法，如何评价一个算法的质量？
2． 区别栈与队列。并各举一个实例，用示意图和简要说明，阐述栈和队列在程序设计
中所起的作用。
3． 设一系列正整数存放在一个数组中，请设计算法，将所有奇数放在数组的前半部分，
将所有偶数存放在数组的后半部分。要求尽可能少用辅助存储单元并使时间最少。
分析你实现的算法的时间复杂度和空间复杂度。
4． 特殊矩阵和稀疏矩阵哪种压缩存储后会失去随机存取的功能？为什么？
5． 已知一个二叉树的中序序列为 ABCDEFGHIJ，后序序列为 ACDBFIHGJE。请构造
出该二叉树，写出它的先序序列，并画出该二叉树的先序线索二叉树。
6． 画出对长度为 10 的有序表进行的折半查找的判定树，并求其等概率时查找成功的
平均查找长度。
三、综合题（每题 20 分，共 60 分）
1． 对于以二叉链表存储的非空二叉树，请设计算法（先用文字写出基本思想，再用 C
语言写出算法），从右向左依次释放所有叶子节点，释放的同时，把节点值存放到
一个向量中。
2． 对给定的 7 个顶点的有向图的邻接矩阵如下：