DOC《全真模拟试题（一）参考答案》

全真模拟试题

(一)参考答案 单项选择题 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 填空题 R->next =s. P->next= = NULL Ls= =NULL 、ls=ls->link.

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 双亲表示法. N-1 I,j,k. 冒泡排序、快速排序 T= =NULL、searchinsert(x,t->rchild). 应用题 EBFGCKHIJDA. 答案如图应用题I 9. 2.2 所示. 3.分析:本题实际上是求最小生成树问题.由于衅中有两条权值为6的边,故可以得到两种方案.答案如图应用题I 9. 3.2 所示. 答案: (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] 以上"-"表示当前经比较不交换位置的元素." "表示当前经比较交换位置的元素. 设计题 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);

}