资源描述：
《哈工大2003年春季学期 (2)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、哈工大2003年春季学期数据结构与算法试卷一．填空题（每空2分，共20分）1．一个n×n的下三角矩阵A中的元素aij(i≥j,1≤i,j≤n)挖取行存于一个一维数组B[1..n(n+1)/2]中，对其中的任一元素aij,若在B中的位置为k,则k=________。2．一棵二元树有67个结点,这些结点的度要么是0，要么是2。这棵二元树中度数为2的结点有______________个。3．在一个无环路有向图G中,若存在一条从顶点i到j的边，则在顶点的拓扑序列中，顶点i与顶点j的先后次序是________。4．在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是_____。5．采用堆排序
2、、快速排序、冒泡排序，对初态有序的表，最省时间的是______。6．设二元树结点的先根序列为ABDECFGH，中根序列为DEBAFCHG,则二元树中叶结点是_________.7．一个哈夫曼(Huffman)树有19个结点，则其叶结点的个数是______。8．将两个长度分别为m和n(m>n)排好序的表归并成一个排好序的表至少要进行____次关键字的值比较。9．线性表L=(a1,a2,…,an)采用顺序结构存储,假定在不同的位置上插入的概率相同，则插入一个新元素平均需要移动的元素个数是_________。10．栈S和队列Q的初始状态皆为空,元素a1,a2,a3,a4,a5和a6依次通过S栈，
3、一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3,a5,a4,a6,a2,a1，则栈S至少应该容纳_______个元素。二．单项选择题（每题2分，共20分）1．算法分析的目的是()A.找出数据结构的合理性B.研究算法的输入/输出关系C.分析算法的效率以求改进D.分析算法的易读性2．在需要经常查找结点的前驱与后继的情况下，使用（）比较合适。A.单链表B.双链表C.顺序表D.循环链表.3．下面关于线性表的叙述中，错误的是()。A.顺序表使用一维数组实现的线性表.B.顺序表必须占用一片连续的存储单元.C.顺序表的空间利用率高于链表D.在单链表中,每个结点只有一个链域.4．队列通常采用的两
4、种存储结构是()。A.顺序存储结构和链式存储结构B.散列方式和索引方式C.链表存储结构和线性存储结构D.线性存储结构和非线性存储结构5．按二元树的定义，具有三个结点的二元树共有()种形态。A.3B.4C.5D.66．深度为5的二元树至多有()个结点。A.16B.32C.31D.107．对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组(顶点表)的大小为()。A.nB.n+1C.n-1D.n/28.在一个具有n个顶点的无向图中，要连通全部顶点至少需要()条边.。A.nB.n+1Cn-1D.n+边数9．静态查找表和动态查找表二者的根本差别在于()。A.它们的逻辑结构不同B.施
5、加在其上的操作不同C.所包含的数据元素的类型不一样D.存储实现不一样.10．散列文件使用散列函数对记录的关键字值进行计算转化为记录的地址。.因为散列函数不是一对一的关系,所以选择好的()方法是散列文件的关键。A．散列函数B．除余法中的质数C．冲突处理D．散列函数和冲突处理三．判断题，正确的在括号内画∨，错误的在括号内画╳。（每小题1分，共10分）1．在线性结构中，每个结点都有一个直接前驱和一个直接后继。（）.2．在链式存储的栈的头部必须要设头结点。.（）3．在二元树中插入结点，则该项二元树便不再是二元树。（）4．由二元树结点的先序序列和后序序列可以唯一确定一棵二元树。（）5．在堆中，以任何
6、结点为根的子树仍然为堆。（）6．有向图的邻接矩阵一定不是对称的。()7．在AOE网中，关键路径是唯一的。()8．若将一株树转换成二元树，则该二元树的根结点一定没有右子树（）。9．索引顺序存取方法ISAM是一种专门为磁盘存取设计的索引顺序文件的组织方法（）。10．基数分类只适用于以数字为关键字的情形，不适用以字符串为关键字的情形（）。四．应用题(共15分)1.请画出与下列二元树对应的森林(6分).2.有一份电文中共使用五个字符:a,b,c,d,e，它们的出现频率依次为8,14,10,4,18，请构造相应的哈夫曼(Huffman)树(左子树根结点的权小于右子树根结点的权)，求出每个字符的哈夫曼
7、编码，并计算编码的平均长度。(9分)五．算法设计(共3题,共35分)1.已知排队采用带头结点的链式存储结构。.试设计一个出队算法，要求在任何情况下都不必修改排队尾指针。(10分)2.已知无向图采用邻接表存储方式，,试写出删除边(i,j)的算法。..3.二元树以左右链表示法为存储结构，分别写出在二元树中查找值为x的结点及求结点X所在的树中层数的算法.(13分)
