全真模拟试题(-)参考答案 单项选择题 1④2③ 3④分析:按题意,矩阵A是个三角矩阵,A[I,j的首地址可用下列公式计算: LOC (aii)=LoC(a)+(k-1)*L 其中K为A[I,j在A中的序号k=I*(I-1)/2+j,L为每个元素所占的单元数 所以有:LOC(au)=2000+(9*(9-1)/2+5-1)*4=2000+160=2160。故为答案④ 7.① 8.②分析:如果G’为G的生成树,那么G’是G的子图,也是G的无环子图,并且还是 G的极小连通子图,且V=V,而连通分量则是指无向图的极大连通子图。 故答案②是错误的。 9.④10。③11。④12。③ 二、判断题 1.2.x3.V4.V5.x6.x7.x8.v9.v10.x 三、填空题 1. R->next 2. P->next== NULL 4.12分析:设n=2,n2=3,n=4 树的总结点数为n=n+n1+n2+n3 树的分支数为n-1=n1+2n2+3n3 ②-①得:-1=n2+2n-n0 有n=n+2n+1=3+2*4+1=12 5.双亲表示法 6.N-1 7. I,j, k 8.冒泡排序、快速排序 9. T==NULL, searchinsert(, t->rchild) 四、应用题 1. EBFGCKHIJDA。 2.答案如图应用题I9.2.2所示 3.3.分析:本题实际上是求最小生成树问题。由于衅中有两条权值为6的边,故可 以得到两种方案。答案如图应用题I9.3.2所示
全真模拟试题(一)参考答案 一、单项选择题 1④ 2③ 3④ 分析：按题意，矩阵 A 是个三角矩阵，A[ I,j]的首地址可用下列公式计算： LOC（aij）=LOC(a11)+(k-1)*L 其中 K 为 A[I,j]在 A 中的序号 k=I*(I-1)/2+j，L 为每个元素所占的单元数。 所以有：LOC（aij）=2000+（9*（9-1）/2+5-1）*4=2000+160=2160。故为答案④ 4．③ 5．④ 6．④ 7．① 8．② 分析：如果 G’为 G 的生成树，那么 G’是 G 的子图，也是 G 的无环子图，并且还是 G 的极小连通子图，且 V’=V，而连通分量则是指无向图的极大连通子图。 故答案②是错误的。 9．④ 10。③ 11。④ 12。③ 二、判断题 1.v 2.x 3.v 4.v 5.x 6.x 7.x 8.v 9.v 10.x 三、填空题 1． R->next =s. 2． P->next= = NULL 3． Ls= =NULL 、ls=ls->link. 4． 12 分析： 设 n1=2,n2=3,n3=4, 树的总结点数为 n=n0+ n1+n2+n3 树的分支数为 n-1= n1+2n2+3n3 ②-①得：-1= n2+2n3-n0 有 n0=n2+2n3+1=3+2*4+1=12 5． 双亲表示法。 6． N-1 7． I,j,k. 8． 冒泡排序、快速排序 9． T= =NULL、searchinsert(x,t->rchild). 四、应用题 1． EBFGCKHIJDA。 2． 答案如图应用题 I 9. 2.2 所示。 3． 3．分析：本题实际上是求最小生成树问题。由于衅中有两条权值为 6 的边，故可 以得到两种方案。答案如图应用题 I 9. 3.2 所示
4.答案: (1)答案如图应用题19.42所示。 (2) V1 V2 V4 V5 V3 N VI V4 v2 V3 V5o 5.(1)经过改动以后,有可能出现死循环,比如当查找的键值K小于有序表中的最小 键值时,就会出现死循环。故算法不能正常进行。 (2)假设有序表的查找序列为(2,3,4,5,6),当待查的键值K=1时,出现死 循环 6.答案 第一趟 47 第二趟[2115] 27] 第三趟[5]212 27 得到15 21 84 第一趟排序过程中键值的移动情况如下: 第一趟: 21 3524] 次交换之后84 27 二次交换之后2 国 21 527683584] 252 15 三次交换之后(24国 国 1521 27 四次交换之后[2415 84] 以上“”表示当前经比较不交换位置的元素。“囗”表示当前经比较交换位置的元素 五、设计题 Bitreptr search(bitreptr t, int k) icount++ if (count==k)return(t) else(search(t->lchild, k) search(t->rchild, k) 2.单链表L的结构如图设计题I922所示 Int isviser(Iklist L) while(p->nextI=null) if(p-datanext->data)p=p->next
4． 答案： （1）答案如图应用题 I 9. 4.2 所示。 （2）v1 v2 v4 v5 v3 和 v1 v4 v2 v3 v5。 5．（1）经过改动以后，有可能出现死循环，比如当查找的键值 K 小于有序表中的最小 键值时，就会出现死循环。故算法不能正常进行。 （2）假设有序表的查找序列为（2，3，4，5，6），当待查的键值 K=1 时，出现死 循环。 6．答案： 25 84 21 47 15 27 68 35 24 第一趟 [24 15 21] 25 [47 27 68 35 84] 第二趟 [21 15] 24 25 [35 27] 47 [68 84] 第三趟 [15] 21 24 25 [27] 35 47 68 [84] 得到 15 21 24 25 27 35 47 68 84 第一趟排序过程中键值的移动情况如下： 第一趟： [25 84 21 47 15 27 68 35 24 ] 一次交换之后 [24 84 21 47 15 27 68 35 25] 二次交换之后 [24 25 21 47 15 27 68 35 84] [24 25 21 47 15 27 68 35 84] [24 25 21 47 15 27 68 35 84] [24 25 21 47 15 27 68 35 84] 三次交换之后 [24 15 21 47 25 27 68 35 84] [24 15 21 47 25 27 68 35 84] 四次交换之后 [24 15 21 25 47 27 68 35 84] 以上“-”表示当前经比较不交换位置的元素。“ ”表示当前经比较交换位置的元素。 五、设计题 1． Bitreptr search(bitreptr t ,int k) {if (t!=null) {count++; if (count= =k)return (t); else {search(t->lchild,k); search(t->rchild,k); } } } 2. 单链表 L 的结构如图设计题 I 9. 2.2 所示。 Int isviser(lklist L) {p=L; while(p->next!=null) if (p->data next->data) p=p->next;
else return(0) return(1)
else return(0); return(1); }