3.(1)初始堆如图应用题Ⅱ9.3.2所示 (2)输出13后重建的堆如图应用题Ⅱ9.3.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.52所示 6.(1)建立的二叉排序树如图应用题Ⅱ9.62所示。 (2)在等概率情况下,查找成功的平均查找长度为 1/2(1*1+2*2+3*3+4*3+5*2+6*1)=42/12=7/2=3.5 五、设计题 单链表的结构图如图设计题Ⅱ9.12所示。 [a子一[a…一 算法: Int arise( Iklist L) (p=L->next; b=p-> data-L->data while(p-> next 1= NULL) q→p->next; if(q-> data-p->data I=b)return(O) return(D) 2. Void Nchar(bitreptr t) f if(t =Null) f if(t->data >=0)&&(t->data <=9) printf( %d', t->data ) Nchar(t->Child) Nchar(t->chi3．⑴初始堆如图应用题Ⅱ 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 所示。 算法：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); } } a1 a2 an ．．．