全真模拟二参考答案 单项选择题 ③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<=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. 三、填空题 1． U=L - > 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 ∧