|
哈尔滨工程大学
2002 年招收研究生入学考试试题
科目名称：数据结构
注意：本试题的答案必须写在规定的答题卡或答题本上，写在试卷上无效。
一、填空题 （13 分）
1. 数据结构从逻辑上分（线性）结构和（非线性）结构。
2 .若广义表中的每个元素都是（原子），则广义表变成为线性表。
3 .连通图的极小连通子图称为改图的（生成树）。
4 .哈希（hash）法存储的基本思想是根据（关键字）来决定（存储地址）。
5 .迪杰斯特拉算法是按（路径长度递增）次序产生最短路径。
6 .两个字符串相等的充要条件是：两个串的（长度）相等，且（对应位置）的字符相等。
7 .哈夫曼树是叶子节点（带权路径长度）最短的二叉树。
8 .稀疏矩阵一般的压缩方法有两种（三元组表）和（十字链表）。
9. n 个结点的线索树有（n+1）根线索。
二 、选择题 （12 分）
1 .一个栈的入栈序列是 a,b,c,d,e,则栈的不可能的输入序列是 dceab
2 .深度为 h 的 4 阶 b-树（根在第一层，叶子在第 h 层），叶子结点的数目最少为 2^h-1
3. 广义表(a,b,(c,(d,e))) 的尾是 （b,(c,(d,e))）。
4 .具有 5 层结点的平衡二叉树至少有 12 个结点。
5 .设二叉树是由森林变换得来的，若森林中有 n 个非终端结点，则二叉树中无右孩子的结
点有 n＋1 个。
6 .下列不属于内部排序的算法是 b
a 归并排序 b 拓扑排序 c 树型排序 d 折半插入排序
三、 回答问题（20 分）
1 .对 n 个结点的二叉树进行中序遍历，算法中所设的栈，栈中元素最少时可能是多少个？
最多时可能是多少个？
答：2 个 ，n+1 个
2 .对 n 个记录进行简单的插入排序，最少共需要比较多少次？最多共需要比较多少次？
答 最少 n－1 次 最多 1＋2＋3…………＋（n－1）次
3 .对 13 个有序记录进行折半查找，查找成功和不成功的平均查找长度各为多少？
4 .采用上三角压缩存储 10 阶对称矩阵 a，若以行序为主存储，且起始地址为 d 则 a3，8 的
存储地址为多少？它与以列序为主序存储时的哪一个元素的起始位置一致？
答：d＋24 a4,7
5 .设循环队列最大空间为 m（0，…，m－1），头，尾指针为 front，rear。加入判别队列空
，更多更新年份持续更新，请在本站的考博信息网|www.kaoboinfo.com中的“考研试卷库”学校栏目中查询下载。
|
您现在的位置： 
