中国人民公安大学数据结构2004年考研真题考研试题-考博信息网

中国人民公安大学数据结构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 个顶点的有向图的邻接矩阵如下：

，更多更新年份持续更新，请在本站的考博信息网|www.kaoboinfo.com中的“考研试卷库”学校栏目中查询下载。

上一篇文章：中国人民公安大学数据结构2005年考研真题考研试题

下一篇文章：中国人民公安大学实验心理学2005年考研真题考研试题

考博信息网提供全国高校历年考研真题，电子扫描版样张:

北京第二外国语学院821国际贸易与国际金融2010年考研真题

北京外国语大学翻译硕士专业学位（MTI）英汉互译（笔译）2010年考研真题