全真模拟二参考答案一、单项选择题
1.② 2.③ 3.④ 4,④ 5.① 6.,③ 7,② 8,④ 9,①
10,①　对键值有序的、具有n个记录的表来讲，当所建立的二叉排序树是一棵深度为n的单支树时，在它上面的查找操作已经退化为顺序查找，所以其平均查找长度的量级为O（n）.
11．②
12．②　按题意要求，将对称矩阵A的上三角部分按行优先进行存放数组了B中，那么B[k]与aij的对应关系为：
当i<=j时，k=(i-1)/2*(2*n-i+2)+j-i+1
因此有：k=(6-1)/2*(2*8-6+2)+7-6+1=32
故 LOC（a67）=LOC(a11)+(k-1)*l=1000+(32-1)*3=1093
二、判断题
1,× 2,× 3,√ 4,× 5,√ 6,√ 7,× 8,× 9,× 10,
三、填空题
U=L - > next
4。　分析：二分查找的过程可以用一棵有序树来表示，该树第三层上有4个结点，表示经过三次比较查找成功的元素个数为4。
n-1、n(n-1)/2。　分析：采用冒泡排序时，若初始时已经自然有序，那么经过一趟n-1次比较后，算法就自动终止了。若初始状态为递减排列，希望排序成递增排列，则排序过程中比较一次，交换一次，总的比较、交换次数为n(n-1)/2，其中n-1为趟数，n/2为平均每趟的比较交换次数。
p - > prior = NULL。
连通回路或环
28-1 = 27 = 128
24
HT[j]!=NULL或HT[j]不为空、H(HT[j])=I
rear - > next = p、rear = p
四、应用题修改后的有向图G的邻接表如图应用题Ⅱ 9.1.2所示。
顶点　入度
V1
0
V2
1
V3
4
∧
V4
0
V5
0
V6
0
∧
2
3
∧
1
∧
3
∧
3
∧
　图应用题Ⅱ 9.1.2
1，2，5，4，3，6
1，3，6，4，5，2
1，3，5，4，6，2
3．⑴初始堆如图应用题Ⅱ 9.3.2所示。
　 ⑵输出13后重建的堆如图应用题Ⅱ 9.3.3所示。
　 ⑶输出27后重建的堆如图应用题Ⅱ 9.3.4所示。
4．分析：在满k叉树中，除编号为1的根结点外，其余结点依次为每k个结点拥有一个共同的双亲。比如：
第二号－第k+1号结点的双亲是第1号结点；
第k+2号－第2k+1号结点的双亲是第2号结点；
第2k+1号－第3k+1号结点的双亲是第3号结点；
,．．．．．
从中可以看出，若编号为n，那么当(n-1)%k = 0时，它一定是某个结点的最右边的孩子，即它的右边不会再有兄弟了。反之，当(n-1)%k≠0，它的右边一定还有兄弟。
答案：编号为n的结点有兄弟的条件是(n-1)%k≠0，该点的右兄弟的编号是n+1。
5．哈夫曼树的构造过程如图应用题Ⅱ 9.5.2所示。
6．⑴建立的二叉排序树如图应用题Ⅱ 9.6.2所示。
　 ⑵在等概率情况下，查找成功的平均查找长度为
1/2(1*1+2*2+3*3+4*3+5*2+6*1) = 42/12 = 7/2 = 3.5。
五、设计题
1．单链表的结构图如图设计题Ⅱ 9.1.2所示。
a1
a2
an
算法：int isrise (lklist L)
{ p = L -> next; b = p -> data – L -> data;
while (p -> next != NULL)
{ q =p -> next;
if (q -> data – p -> data !=b) return(0)
else p = q;
}
return(1);
}
2．Void Nchar (bitreptr t)
{ if (t != Null)
{ if (t -> data >= ’0’ ) && (t -> data <= ‘9’) printf (“%d”,t -> data );
Nchar (t -> lchild);
Nchar (t -> rchild);
}
}