哈尔滨工程大学-考研数据结构真题 (3)

一填空题（13分）1数据结构从逻辑上分（线性）结构和（非线性）结构。2若广义表中的每个元素都是（原子），则广义表变成为线性表。3连通图的极小连通子图称为改图的（生成树）。4哈希（hash）法存储的基本思想是根据（关键字）来决定（存储地址）。5迪杰斯特拉算法是按（路径长度递增）次序产生最短路径。6两个字符串相等的充要条件是：两个串的（长度）相等，且（对应位置）的字符相等。7哈夫曼树是叶子节点（带权路径长度）最短的二叉树。8稀疏矩阵一般的压缩方法有两种（三元组表）和（十字链表）。9N个结点的线索树有（n+1）根线索。二选择题（12分）1一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输入序列是dceab2深度为h的4阶B-树（根在第一层，叶子在第h层），叶子结点的数目最少为2^h-13广义表(a,b,(c,(d,e)))的尾是（b,(c,(d,e))）。4具有5层结点的平衡二叉树至少有12个结点。5设二叉树是由森林变换得来的，若森林中有n个非终端结点，则二叉树中无右孩子的结点有n＋1个。6下列不属于内部排序的算法是BA归并排序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＋24A4,75设循环队列最大空间为m（0，…，m－1），头，尾指针为front，rear。加入判别队列空的条件是（front＋1）MODm＝rear，那么判别队列满的条件是什么？front，rear的初值应是多少？答front＝rear初值front＝0rear＝1四应用题（25分）1对一组记录的关键字（49，38，66，80，75，19，22）进行快速排序，请写出各趟排序后的状态，并说明总共比较了多少次？2设哈希表的地址空间为0－6，哈希函数H(K)=KMOD7。请对关键字序列（32，13，49，18，22，38，21）按链地址法解决冲突的办法构造哈希表。并求出查找成功的平均查找长度。3已知二叉树的左，右子树各含3个结点。试分别构造满足如下要求的二叉树：（1）左子树的先序序列与中序序列相同，右子树的先序序列与中序序列相同。（2）左子树的中序序列与后序序列相同，右子树的先序序列与中序序列相同。4对关键字（67，49，80，14，22，31，95，38，43，56，73）构造平衡二叉树。5请写出表达式a+b*(c-d)-e/f的二叉树表示，并使其成为后序线索树。五算法题（30分）1设计一算法，在单链表中删除数据元素的值相同的多余结点。2设计一算法，在中序线索树上求指针P所指结点的前驱结点。3将二叉树的结点按层编号（从根还是往下，同层自左至右）。请设计一算法，将该二叉树的结点按编号从小到大顺序输出。设二叉树用二叉链表表示。