哈工大2004年春季学期 (3)

《哈工大2004年春季学期 (3)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、哈工大2004年春季学期数据结构与算法试卷答案一．填空题（每空1分，共15分）1．某程序的时间复杂性为(3n+nlog2n+n2+8),其数量级表示为_nlogn__。2．在一个图中,所有顶点的度数之和等于所有边数的_______2______倍。3．在外部排序中，可以使用___选择树法产生初始归并段。4．在散列法查找中，解决冲突的方法有开放定址法，内散列表、外散列表等。5．对于一株具有n个结点的树，该树中所有结点的度数之和为n-16．Kruskal算法的时间复杂性为eloge边稀疏向图求最小生成树。7．从具有n个结点的二元查找树中查找一

2、个元素，最坏情况下的时间复杂性为logn8．归并分类中，对于n个元素，归并的趟数是。logn9．从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较n+1/210．广义表（（a）,a）的表头和表尾分别是(a)、(a)11．设高度为h的二元树上只有度数为0和度数为2的结点，则此类二元树中所包含的结点数至少为2h-1二．选择题（每题1分，共10分）1．不带头结点的单链表head为空的判定条件是（）A.head=NULLB.head->next=NULLC.head->next=headD.head!=NULL.2

3、．在下列叙述中，不正确的是（）。A.关键活动不按期完成就会影响整个工程的完成时间。B.任何一个关键活动提前完成，将使整个工程提前完成。C.关键路径上的关键活动若提前完成，则整个工程提前完成.D.所有关键活动都提前完成,则整个工程将提前完成.3．一个向量第一个元素的存储地址是100，每个元素的占2个存储空间，则第五个元素的地址是()。A.110B.108C.100D.1204．一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是()。A.edcbaB.decbaC.dceabD.abcde5．判定一个有向图是否存在回路，除了可以用

4、拓扑排序方法外,还可以利用()A.关键路径的方法B.求最短路径的Dijkstra方法C.宽度优先遍历算法D.深度优先遍历算法6．设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点:addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7其余地址为空。如果用线性探测再散列方法处理冲突，关键字为49的结点的地址是()A.8B.3C.5D.97．一组记录的输入顺序为(46,79,56,38,40,84)，则利用堆排序方法建立的初始堆为()。A.79,46,56,38,40,80B.38,40,

5、56,79,46,84C.84,79,56,46,40,38D.84,56,79,40,46,388．外排序是指()。A.在外存上进行的排序方法B.不需要使用内存的排序方法C.数据量很大，需要人工干预的排序方法D.排序前数据在外存，排序时数据调入内存的排序方法.9．索引非顺序文件是指()。A．主文件无序,索引表有序B．主文件有序,索引表无序C．主文件有序,索引表有序.D．主文件无序,索引表无序.10．有向图如图1,添上一条弧后,则可能有唯一的拓扑结构,画上该弧。三．判断题，正确的在括号内画∨，错误的在括号内画╳。（每小题1分，共10分）1

6、．就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。（X.2．在外部分类中使用K路平衡归并，采用选择树法时,归并效率与K有关。.（X）3．对于n个记录的集合进行归并分类，最坏情况下所需要时间为O(n)。（X）4．倒排文件与多重表文件的次关键字索引结构不同。（V）5．将一棵树转换成二元树后，根结点没有左子树。（X6．用树的前序遍历序列和中序遍历序列可以导出树的后序遍历序列。(V7．即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得到的序列也一定相同。(X)8．哈夫曼(Huffman)树是带权路径长度最

7、短的树。路径上权值较大的结点离根较近（V）。9．对于任一个图，从某顶点出发进行一次深度或广度优先搜索,可以访问图中每一个顶点（X）。10．对于一个堆结构，按层遍历可以得到一个有序序列（X）。四．简答题1.在单链表、双链表和单循环链表中，若仅知道指针P指向某结点，不知道头指针，能否将结点P从相应的链表中删去?若可以，其时间复杂度各为多少?(6分)2.已知某二元树按层遍历序列为ABCDEFGHIJ，中序遍历序列为DBGEHJACIF，画出该二元树.（4分）3.已知某数列输入顺序为10,5,7,14,3,1,18,12,15,16，按输入顺序画

8、出其二元查找树，并画出删除结点14后的查找树.(5分)五．算法设计1.(8分)设有一个长度为n的由”0”和”1”元素组成的输入序列，存于数组A[n]中。设计一个算法，依次让每个元素通过一个栈S