华中科技大学计算机学院
得分 评卷人 #define N 10 void main()
八、阅读并改进算法(每小题5分，共10分)
{ int a[N] ={1,4,5,6, 8,10,11,13,15,20 }, b[N],i,j,k; scanf（”%d”,&k）; for(i=0;i while(i if (a[i]==b[j]) break; else if (a[i] else j++; if (i>=N ||j>=N) printf(\else printf(\} (1) 阅读上面的算法程序，叙述算法的功能，并给出算法的时间与空间复杂度。 (2) 改写算法，使改进算法的时间和空间效率尽可能提高。 b[N-i-1]=k-a[i]; 《数据结构》试卷参考答案 (A卷) 2010 —2011 年度第二学期计算机学院 一、单项选择题(从下列各题四个备选答案中选出一个正确答案,将其代号(A,B,C,D)写在下表中,每小题1分,共10分) 题号 1 2 3 4 5 6 7 8 9 10 答案 B C C D A D C D C A 6 6 华中科技大学计算机学院 二、填空题(在下表中填写正确的答案,每空1分,共10分) 题号 1 2 3 4 5 6 7 8 答案 n-1 (n+e) 5 n2+n3 链式 3 4 队列 9 7 10 n-1 三、判断题(判断下列各题叙述的正确性,用√表示正确，×表示错误，每小题1分,共10分) 题号 1 2 3 4 5 6 7 8 9 10 答案 × √ √ × × × √ × √ √ 四、存储结构图(要求标明各结点的数据域、指针域、权值等，每小题6分，共12分) 2．如下图所示为二叉树排序树T的一种线索二叉树逻辑结构图，试画出插入结点 48后的线索二叉树的物理存储结构图。 答案： 0360 0230 0550 ^1121 1301 1481 1661^ 2． 试画出如下图所示无向网的邻接多重表存储结构图。 参考答案： 0A1B2C3D4E 844968100001112 ^ ^^1232344 ^ ^ 7 7 华中科技大学计算机学院 五、求解问题(每小题8分，共32分) 2．如下图所示为n行2n-1列矩阵A[1..n，1..2n-1]，现以行为主序进行压缩存储到 一维数组SA[1…m]中。（1）试问m值是什么？（2）假定非零元素A[i，j]保存在SA[k]中，试写出由下标(i，j)到k的转换公式。 ?0 0 0 .... 0 a1,n 0 .... 0???0 0 0 .... a a a .... 02,n-12,n2,n+1??? ....??? ?0 0 ... ai,n-i+1... ai,n ... ai,n+i-1 ... 0??? ....???aa .... a .... a?n,n n,2n-1 ??n,1 n,2 答案：（1）m=n2 （2）k=(i-1) 2+i+j-n (当 |j-n| 2. 如下图所示为有序表（10，15，21，33，44，60，67，68，70，80）的判定树，试问该判定树是否正确？如果正确，说明理由，错误则指出错误处并给出正确结果。 答案： 52134678910注：没按序号作为结点值扣1分 3．试用元素序列(63、72、88、68、66、38、43),生成平衡二叉排序树T,(1)按步骤画出该平衡二叉排序树T,(2)写出平衡二叉排序树T的中序遍历序列,(3)假定每个元素的查找概率相等,计算查找成功时的平均查找长度。 答案： 6643（1） 72636888 38（2）38，43，63，66，68，72，88 （3）ASL=（1+2*2+3*4）/7=17/7 8 8 华中科技大学计算机学院 4．已知图的邻接表法存储结构如下，从顶点A出发求图的深度遍历的结果。 1A2B3C4D5E6F 211221 346543 ^^^^65^^ 答案： ABDECF 六、证明题(每小题5分，共10分) 2，证明在哈夫曼树种最小权值所对应的叶结点的层数正好是哈夫曼树的高度。 略 2．证明有n个结点的完全二叉树的高度为?log2(n+1)?。 略 七、编程题(6分) 1． 已知大小为N的数组A[N]、B[N]分别存放着有N个结点的某二叉树的先根和 中根遍历序列，试编写函数CreateBiTree构造该二叉树。相关说明如下： 参考答案： bitTree CreateBiTree(ElemType X[]，ElemType Y[N]，int n) { int i; if (!n) return NULL; 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); Return T; } 八、阅读并改进算法(每小题4分，共8分) （1）. 阅读上面的算法程序，叙述算法的功能，并给出算法的时间与空间复杂度。 答案：输入一个数k，在有序序列中找2个数，使其和等于k T(n)= O(n) S(n)= O(n) （2） 改写算法，使改进算法的时间和空间效率尽可能提高。 参考答案： 9 9 华中科技大学计算机学院 #include int a[MAXSIZE]= ={1,4,5,6, 8,10,11,13,15,20 }; int k,i,j; scanf(\ i=0,j=MAXSIZE-1; while(i if(a[i]+a[j]==k) break; if(a[i]+a[j]>k j--; else i++; } if(i 10 10