|
友情提示：本站提供全国400多所高等院校招收硕士、博士研究生入学考试历年考研真题、考博真题、答案，部分学校更新至2012年，2013年；均提供收费下载。 下载流程： 考研真题 点击“考研试卷””下载; 考博真题 点击“考博试卷库” 下载
哈尔滨工程大学
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。加入判别队列空
免责声明：本文系转载自网络，如有侵犯，请联系我们立即删除，另：本文仅代表作者个人观点，与本网站无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
|
文章搜索
您现在的位置： 
