哈尔滨工程大学2002年硕士研究生入学考试数据结构



文件信息
文件来源 来自免费考研网每个热心网友无偿提供 
文件作者  
更新时间 2005-11-29 16:42:18 
添加编辑 viewsnake 

辅助信息
打印功能 打印本文
背景颜色 杏黄 秋褐 胭红 芥绿 天蓝 雪青 炭灰 奶白
字体大小 特大号字 大号字 中号字 小号字
免责声明 本网站所有文章均来自网络,仅提供预览形式,不提供纸张形式,若涉及到版权的文章,请购买正版,毕竟在电脑上看也不舒服啊,呵呵,这是viewsnake个人网站,纯粹交流学习资料的地方。无商业行为。
搜索更多免费考研资料:
阅读正文内容
一 填空题 (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。加入判别队列空的条件是(front+1)MODm=rear,那么判别队列满的条件是什么?front,rear的初值应是多少?
答 front=rear    初值front=0 rear=1
 
四 应用题(25分)
1 对一组记录的关键字(49,38,66,80,75,19,22)进行快速排序,请写出各趟排序后的状态,并说明总共比较了多少次?
 
2 设哈希表的地址空间为0-6,哈希函数H(K)=K MOD 7。请对关键字序列(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 将二叉树的结点按层编号(从根还是往下,同层自左至右)。请设计一算法,将该二叉树的结点按编号从小到大顺序输出。设二叉树用二叉链表表示。


<<<返回上一页 <<<返回网站首页
<<<您的位置:首页>专业试卷>黑龙江区>哈尔滨工程大学考研专业课试卷>正文