华中科技大学计算机学院数据结构(计算机专业)试题

华中科技大学计算机学院华中科技大学计算机学院PAGE7PAGE71《数据结构》试卷（A卷)2010—2011年度第二学期计算机学院班级

学号

姓名 考试时间：2011年月 日 考试形式：闭卷题号一二三四五六七八总分核对人题分得分101010123210610100得分评卷人（从下列各题四个备选答案中选出一个正确答案将其代号(A，B，C,D）1分,10得分评卷人题号题号答案12345678910对于栈的进栈和出栈运算，采用 存储结构时运算效率最高.单链表 B．容量足够大的顺序C．单向循环链表 D．双向循环链表链式队列和顺序队列比较，具有 这个优势.进队操作方便 B．出队操作方便C．通常不会出现满队列情况D．求队列元素个数方下列关于串的叙述中,正确的是 .A．2个串的长度相等，则2个串相等 B．空串至少包一个空格C．替换操作可以实现字符的删除 D．一个串的长度至少是二叉树在线索化后，下列问题中相对难解决的是 .B．中根线索二叉树中求中根前趋C．中根线索二叉树中求中根后继D5．对序列进行2遍 排序后得到序列26，30，66）.A．选择 B．冒泡C．插入 D．归并在下列排序算法中， 算法可能出现如下情况:在最后一趟排序之前，有元素均不在其最终的位置上。A．堆排序 B．快速排序C．冒泡排序D．插入排7．由4个结点可以组成 棵不同形态的二叉树。A．10 B．12 C．14 D．16对包含n个元素的散列表进行检索，平均查找长度为 .A．O（logn) B．O(n） C．O(nlogn） Dn9．广义表（(（b）,c）,（）,(）（（(e），））,（）的长度是 。A．2 B．3 C．4 D．510．对某无向图进行一次深度优先搜索遍历，如果能访问到所有的顶点,图一定是 .A．连通图 B．树图 C．有回路的连通图 D．完全图得分评卷人二、填空题得分评卷人题号题号答案12345678910具有n个单元、用首尾指针、无标志位的循环队列中，队满时共有 元素。设顶点数为n，弧数为e的有向图的用邻接表存储，求顶点值为V的顶点的度的算法时间复杂度为 .某哈夫曼树有11个结点，则它有 个度为2的结点。设森林T中有三棵树,第一、二、三棵树的结点个数分别是n1，n2，n3，那当把森林转换成二叉树后，其根结点的右子树上有 个结点。当线性表经常进行插入和删除操作时，应该选择使用 存储结构。设栈S和队列Q的初始状态为空，元素abcdef依次通过栈S，一个元素出栈后即进入队列Q。若这6个元素出队列的顺序是b、d、c、f、e、a，则栈S的容量至少应该是 。满足先根遍历序列为a、b、c,后根序列为c、b、a的二叉树共有 棵.按广度优先搜索遍历图的算法需要借助的辅助数据结构是 。高度为4的平衡二叉树至少有 个结点。对n个元素的序列进行简单选择排序，最多进行 次元素的交换.得分得分评卷人三、判断题(判断下列各题叙述的正确性，用√表示正确，×表示错误，每小题1分,共10分）题号答案12345678910可以以随机方式访问以三元组方式存放的稀疏矩阵的非零元素.hh层的结点数，一定能求二叉树的结点数。算法分析的目的之一是分析算法的效率以求改进。正确性是算法的特征之一.线性表的逻辑结构与存储顺序总是一致的。在循环链表中,任何一个结点的指针部分都指向其直接后继元素的结点。将递归算法改写成非递归算法时，通常需要使用的数据结构为栈.n条弧的有向图不一定是强连通图。是二叉排序树。快速排序方法的每一趟都能找到一个元素把它放到最终的位置上。得分评卷人四、存储结构图(要求标明各结点的数据域、指针域、权值等，每小题6分，共12分得分评卷人T的一种线索二叉树逻辑48后的线索二叉树的物理存储结构图。36362355NULL NULL123066二叉排序T试画出如下图所示无向网的邻接多重表存储结构图。AA4C48910D6B8EG得分得分评卷人五、求解问题(832分)1n2n—1.2n-1]，现以行为主序进行压缩（1)m假定非零元素j]SA［k](i，j）k的转换公式。0 0 00 0 0 0a1,n a 0a2,n-12,n 2,n+1 0 0...a... a... a ...0 i,n-i+1

i,n

i,n+i-1 a a a an,1n,2 n,n n,2n-12．如下图所示为有序表(10，15，21，33,44，60，67，68，70，86）的判定树,试问该判定树是否正确?如果正确，说明理由，错误则指出错误处并给出正确结果.4444156810336770216086(6728868663843（1T定每个元素的查找概率相等,计算查找成功时的平均查找长度。A出发求图的深度遍历的结果。B45^C16^D25^E24^F13^123456A236 ^1得分评卷人123456A236 ^1得分评卷人2．证明有n个结点的完全二叉树的高度为log2（n+1）。得分评卷人七、编程题(6分得分评卷人CreateBiTree相关说明如下：typedef structnode｛ElemTypestructnode＊lchild，＊rchild；｝NODE,＊bitTree;bitTreeCreateBiTree(ElemType［],ElemTypeY,intn/*型说明,X、Yn个结点的二叉树的先根和中根遍历序列＊/得分评卷人八、阅读并改进算法（每小题5分，共10得分评卷人#defineN10voidmain(）｛inta[N］={1,4,，6,，10，11,13,15,20，]scanf(”%d”，&k）;for(i=0;i〈N；i++）i=j=0；while（i<N

b[N—i—1］=—a[i；if(a[i]==b［j]) break;elseif（a[i〈b［j） else j++;if(i〉=N||j〉=N）printf（”NoSolution！")；else printf％5d％5d”,［i],k-b［j；｝阅读上面的算法程序，叙述算法的功能，并给出算法的时间与空间复杂度。(2)改写算法，使改进算法的时间和空间效率尽可能提高.《数据结构》试卷参考答案(A卷)2010—2011年度第二学期计算机学院一、单项选择题(从下列各题四个备选答案中选出一个正确答案,将其代号(A,B，C，D）写在下表中,每小题1分，共10分)题号 1 2 3 4 5 6 7 8 9 10答案答案BCCDADCDCA二、填空题（在下表中填写正确的答案，每空1分，共10分)题号题号12（n+e)345678910答案n-15n2+n3链式34队列7n—1三、判断题(判断下列各题叙述的正确性，用√表示正确，×表示错误，每小题1分，共10分)题号12345678910答案×√√×××√×√√四、存储结构图（6分,分)2．如下图所示为二叉树排序树T的一种线索二叉树逻辑结构图，试画出插入结点48后的线索二叉树的物理存储结构图.03600230036002300550^1121130114811661^2．试画出如下图所示无向网的邻接多重表存储结构图.参考答案:ABCDABCDE102 ^ 4 ^80140240^3912613 ^81^41234华中科技大学计算机学院华中科技大学计算机学院PAGE10PAGE1010五、求解问题(每小题8分，共32分）n2n-1A[1。.n，1.。2n—1，现以行为主序进行压缩（1）试问mj］SA［k]中,试写出由下标（i，j)k的转换公式。0 0 00 0 0 0a1,n a 0a2,n-12,n 2,n+1 0 0...a... a... a ...0 i,n-i+1

i,n

i,n+i-1 a a a an,1n,2 n,n n,2n-1答案：(1）m=n2(2)k=(i-1)2+i+j—n （当｜j-n|〈i)528136947102.如下图所示为有序表(10，15,21，33,44，60，52813694710注：没按序号作为结点值扣1分试用元素序列(63、72、88、68、66、38、43）,生成平衡二叉排序树按T假定每个元素的查找概率相等，计算查找成功时的平均查找长度.答案：6643（1）38

7263 68 88（2）38，43，63，66，68,72，88（3）ASL=（1+2*2+3＊4)/7=17/7A出发求图的深度遍历的结果.A23A236^B145^C16^D25^E24^F13^23456答案:ABDECF六、证明题(每小题5分,共10分）2略2n个结点的完全二叉树的高度为略七、编程题（6分）1NA［N]B［N］分别存放着有N个结点的某二叉树的先CreateBiTree参考答案：bitTreeCreateBiTre（ElemType［],ElemTypeY[intn){inti;if(!n）returnNULL；T=（BitTree)malloc(sizeof（NODE）;T-〉data=X[0]；for(i=0;Y[i]==X[0］；i++）;T-〉lchild=CreateBiTree（&X［1］,Y,i)；T->rchild=CreateBiTree（＆X［i+1］,&Y［i+1］,n-i-1)；ReturnT；｝八、阅读并改进算法(每小题4分，共8分）（1).阅读上面的算法程序,叙述算法的功能，并给出算法的时间与空间复杂度.答案：输入一个数k，在有序序列中找2个数,使其和等于kT(n）=O