全真模拟二参考答案 单项选择题 ③3④ 10.①对键值有序的、具有n个记录的表来讲,当所建立的二叉排序树是一棵深 度为n的单支树时,在它上面的查找操作已经退化为顺序查找,所以其平均查找长度的 量级为O(n) 12.②按题意要求,将对称矩阵A的上三角部分按行优先进行存放数组了B中 那么B[k]与a的对应关系为 当三时,k=(-1)/2*(2*n计+2)+计+1 因此有:k=(6-1)2*(2*8-6+2)+7-6+1=32 LOC(a67)=LOC(a)+(k-1)*1=1000+(32-1)*3=1093 判断题 1.×2.×3.√4.×5.√6.√7.×8.×9.×10. 、填空题 1. U=L-> next 2.4。分析:二分查找的过程可以用一棵有序树来表示,该树第三层上有4个结 点,表示经过三次比较查找成功的元素个数为4 n-1、n(n-1)/2。分析:采用冒泡排序时,若初始时己经自然有序,那么经过 趟n-1次比较后,算法就自动终止了。若初始状态为递减排列,希望排序成递 增排列,则排序过程中比较一次,交换一次,总的比较、交换次数为n(n-1)2, 其中n-1为趟数,n/2为平均每趟的比较交换次数 4. p->prior= NULL 6.回路或环 7.28-1=27=128 8.24 9.HIj]=NUL或HI不为空、H(HIj])= 10. rear->next=p rear=p 四、应用题 修改后的有向图G的邻接表如图应用题Ⅱ9.12所示。 顶点入度 ,,T V34|∧ 卧 V60|∧ 图应用题Ⅱ9.1.2 1,2,5,4,3,6 1,3,6,4,5,2 1,3,5,4,6,2
全真模拟二参考答案 一、单项选择题 1.② 2.③ 3.④ 4. ④ 5.① 6. .③ 7. ② 8. ④ 9. ① 10. ① 对键值有序的、具有 n 个记录的表来讲，当所建立的二叉排序树是一棵深 度为 n 的单支树时，在它上面的查找操作已经退化为顺序查找，所以其平均查找长度的 量级为 O（n）. 11．② 12．② 按题意要求，将对称矩阵 A 的上三角部分按行优先进行存放数组了 B 中， 那么 B[k]与 aij 的对应关系为： 当 i next 2． 4。 分析：二分查找的过程可以用一棵有序树来表示，该树第三层上有 4 个结 点，表示经过三次比较查找成功的元素个数为 4。 3． n-1、n(n-1)/2。 分析：采用冒泡排序时，若初始时已经自然有序，那么经过一 趟 n-1 次比较后，算法就自动终止了。若初始状态为递减排列，希望排序成递 增排列，则排序过程中比较一次，交换一次，总的比较、交换次数为 n(n-1)/2， 其中 n-1 为趟数，n/2 为平均每趟的比较交换次数。 4． p - > prior = NULL。 5． 连通 6． 回路或环 7． 28-1 = 27 = 128 8． 24 9． HT[j]!=NULL 或 HT[j]不为空、H(HT[j])=I 10． rear - > next = p、rear = p 四、应用题 1． 修改后的有向图 G 的邻接表如图应用题Ⅱ 9.1.2 所示。 顶点 入度 图应用题Ⅱ 9.1.2 2． 1，2，5，4，3，6 1，3，6，4，5，2 1，3，5，4，6，2 V1 0 V2 1 V3 4 ∧ V4 0 V5 0 V6 0 ∧ 2 3 ∧ 1 ∧ 3 ∧ 3 ∧
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 data ) Nchar(t->Child) Nchar(t->chi
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 所示。 算法：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 data ); Nchar (t -> lchild); Nchar (t -> rchild); } } a1 a2 an ．．．