资源描述：
《杭师A-试卷-数据结构期末试卷答案.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、班级：学号：姓名：装订线杭州师范大学国际服务工程学院2008-2009学年第二学期期末考试《数据结构与算法分析》试卷（A）题号一二三四五总分得分注意：请将答案填写在答题纸上。得分一、选择（共30分,每小题3分,把最恰当的答案题号填到答题卷上）1.对于具有n个顶点的连通图（连通的无向图）,其最少的边数目为().A.nB.n(n–1)/2C.n+1D.n–12.给定某二叉树的先序遍历序列为ABDCEFHG，中序遍历序列为BDAFHEGC,则该二叉树的后序遍历序列为().A.DBAHFGCEB.BDHFGECAC.DBHFGECAD.DBCFHEGA3.给定
2、某整数序列为{1,2,3,4,5,9,8,6,7}.现要对其递增排序，则最快的排序算法为(),附助存储空间要求最多的排序算法为().A.直接插入排序B.堆排序C.归并排序D.起泡排序4.将m个元素存储在具有s个单元的哈希表中，则其装填因子为().A.s+mB.m/sC.m*sD.m–s5.图的广度优先搜索与二叉树的()相类似.A.先序遍历B.中序遍历C.后序遍历D.层次遍历6.在下列三种二叉树中，对()中的元素进行中序遍历结果得到的序列是有顺序的。.A.堆（heap）B.二叉搜索树（binarysearchtree）C.完全二叉树7．下列各整数序列中(
3、)不是堆.A.{100,85,98,77,80,60,82,40,20,10,66}B.{100,98,85,82,80,77,66,60,40,20,10}C.{10,20,40,60,66,77,80,82,85,98,100}D.{100,85,40,77,80,60,66,98,82,10,20}8.如果一个栈中的进栈次序为1,2,3,4,…,n,第一个输出的元素为n，则第i个输出的元素为().A.n–i+1B.n–iC.iD.无法确定9．一个深度为k的二叉树的最多的元素个数为().A.2k+1–1B.2k-1C.2k-1–1D.2k+110.
4、下列()方法不是哈希表中用于处理冲突的方法.A.线性探测B.链地址法C.折半查找D.二次探测得分二、问答题（共10分,请将答案填到答题卷上）1.给定某英文文本为“this_is_an_ideal_string”,采用等长编码时的总编码长度为________位,采用哈夫曼编码方法时的总编码长度为________位.(6分)2.给定某整数序列为25,84,21,47,15,27,68,35,20,步长为3的第一轮希尔排序后得到的序列为(3-sort):《数据结构与算法分析》试题（第1页共3页）________________________________
5、__________________.(4分)得分三、问答题（共38分,请将答案填到答题卷上）1.对于给定的某有向图（如右图所示）,要求：①写出每个顶点的入度和出度(2分)②画出其邻接矩阵表示的示意图;(3分)③画出其邻接表表示的示意图;(3分)④画出其十字链表表示的示意图;(3分)⑤画出其强连通分量;(3分)⑥给出从顶点“1”出发的DFS（深度优先搜索）结果;(2分)⑦给出从顶点“2”出发的BFS（广度优先搜索）结果.(2分)2.给定一整数序列为{40,30,20,50,60,45,25,55,35,38}.将其依次插入到初始为空的二叉搜索树（BST
6、：BinarySearchTree）中.请画出每个元素插入后的BST示意图.(10分)3.将关键字序列11,5,29,20,0,27,18依次插入表长为9的初始为空的哈希表中，其哈希函数为hash(k)=k%9，处理冲突的方法为开放定址法中的线性探测(即di=i).请画出该哈希表,并计算查找成功时的平均查找长度(ASL:AverageSearchTime).(10分)三、完善程序(共8分,每空格2分,将答案填写在答题卷的相应位置)请完成下列图的深度优先搜索算法，在空白处填写正确的语句。#defineMAX_VERTEX_NUM20typedefstru
7、ctArcNode{intadjvex;//该弧所指向的顶点的位置structArcNode*nextarc;//指向下一条弧的指针}ArcNode;typedefstructVNode{VertexTypedata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;//图的当前顶点数和弧数intvexnum,arcnum;//图的种类标志intkind;}ALGraph;voidDFSTraverse
8、(ALGraphG){//对图G作深度优先遍历for(v=0;v
