d++;
//求出顶点numb的入度
for(i=0; i d++; //返回顶点numb的度 return (d); } 3. int degree3(GraphL & gl, int numb) //根据无向图的邻接表求出序号为numb的顶点的度数 { int d=0; vexnode * p=gl.adjlist[numb]; while(p!=NULL) { d++; p=p->next; } return (d); } 4. int degree4(GraphL & gl, int numb) //根据有向图的邻接表求出序号为numb的顶点的度数 { int d=0, i; vexnode * p=gl.adjlist[numb]; while (p!=NULL) { d++; p=p->next; } //求出顶点numb的出度 for(i=0; i while(p!=NULL) { if(p->vertex= =numb) d++; p=p->next; } }//求出顶点numb的入度 return (d); //返回顶点numb的度数 } -36- 习题7 一、单项选择题 1. 若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为( )。 A. n 的9分之一。 A. 20 A. 3 次数为( )。 A. 2 A. O(n) B. 3 C. 4 B. O(n) C. O(1) 2 B. n+1 C. (n-1)/2 D. (n+1)/2 2. 对于长度为9的顺序存储的有序表，若采用折半查找，在等概率情况下的平均查找长度为( ) B. 18 C. 25 D. 22 B. 4 C. 5 D. 6 3. 对于长度为18的顺序存储的有序表，若采用折半查找，则查找第15个元素的比较次数为( )。 4. 对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，则查找元素26的比较 D. 5 D. O(log2n) 5. 对具有n个元素的有序表采用折半查找，则算法的时间复杂度为( )。 6. 在索引查找中，若用于保存数据元素的主表的长度为n，它被均分为k个子表，每个子表的长度均为n/k，则索引查找的平均查找长度为( )。 A. n+k B. k+n/k C. (k+n/k)/2 D. (k+n/k)/2+1 7. 在索引查找中，若用于保存数据元素的主表的长度为144，它被均分为12子表，每个子表的长度均为12，则索引查找的平均查找长度为( )。 A. 13 B. 24 C. 12 D. 79 2 8. 从具有n个结点的二叉排序树中查找一个元素时，在平均情况下的时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n) 9. 从具有n个结点的二叉排序树中查找一个元素时，在最坏情况下的时间复杂度为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n) 10. 在一棵平衡二叉排序树中，每个结点的平衡因子的取值范围是( )。 A. -1?1 B. -2?2 C. 1?2 D. 0?1 11. 若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K计算哈希地址，则元素64的哈希地址为( )。 A. 4 B. 8 址等于3的元素个数( )。 A. 1 B. 2 C. 3 D. 4 13. 若根据查找表建立长度为m的哈希表，采用线性探测法处理冲突，假定对一个元素第一次计算的哈希地址为d，则下一次的哈希地址为( )。 A. d B. d+1 二、填空题 1. 以顺序查找方法从长度为n的顺序表或单链表中查找一个元素时，平均查找长度为________，时 C. (d+1)/m D. (d+1)%m C. 12 D. 13 12. 若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%7计算哈希地址，则哈希地 2 -37- 间复杂度为________。 2. 对长度为n的查找表进行查找时，假定查找第i个元素的概率为pi,查找长度（即在查找过程中依次同有关元素比较的总次数）为ci，则在查找成功情况下的平均查找长度的计算公式为________。 3. 假定一个顺序表的长度为40，并假定查找每个元素的概率都相同，则在查找成功情况下的平均查找长度________，在查找不成功情况下的平均查找长度________。 4. 以折半查找方法从长度为n的有序表中查找一个元素时，平均查找长度约等于________的向上取整减1，时间复杂度为________。 5. 以折半查找方法在一个查找表上进行查找时，该查找表必须组织成________存储的________表。 6. 从有序表(12,18,30,43,56,78,82,95)中分别折半查找43和56元素时，其比较次数分别为________和________。 7. 假定对长度n=50的有序表进行折半查找，则对应的判定树高度为________，最后一层的结点数为________。 8. 假定在索引查找中，查找表长度为n，每个子表的长度相等，设为s，则进行成功查找的平均查找长度为____________。 9. 在索引查找中，假定查找表（即主表）的长度为96，被等分为8个子表，则进行索引查找的平均查找长度为________。 10. 在一棵二叉排序树中，每个分支结点的左子树上所有结点的值一定________该结点的值，右子树上所有结点的值一定________该结点的值。 11. 对一棵二叉排序树进行中序遍历时，得到的结点序列是一个________。 12. 从一棵二叉排序树中查找一个元素时，若元素的值等于根结点的值，则表明_______，若元素的值小于根结点的值，则继续向________查找，若元素的值大于根结点的值，则继续向________查找。 13. 向一棵二叉排序树中插入一个元素时，若元素的值小于根结点的值，则接着向根结点的________插入，若元素的值大于根结点的值，则接着向根结点的________插入。 14. 根据n个元素建立一棵二叉排序树的时间复杂度大致为________。 15. 在一棵平衡二叉排序树中，每个结点的左子树高度与右子树高度之差的绝对值不超过________。 16. 假定对线性表(38,25,74,52,48)进行哈希存储，采用H(K)=K % 7作为哈希函数，采用线性探测法处理冲突，则在建立哈希表的过程中，将会碰到________次存储冲突。 17. 假定对线性表(38,25,74,52,48)进行哈希存储，采用H(K)=K % 7作为哈希函数，采用线性探测法处理冲突，则平均查找长度为________。 18. 在线性表的哈希存储中，装填因子?又称为装填系数，若用m表示哈希表的长度，n表示线性表中的元素的个数，则?等于________。 19. 对线性表(18,25,63,50,42,32,90)进行哈希存储时，若选用H(K)=K % 9作为哈希函数，则哈希地址为0的元素有________个，哈希地址为5的元素有________个。 三、应用题 1. 已知一个顺序存储的有序表为(15,26,34,39,45,56,58,63,74,76)，试画出对应的折半查找判定树，求出其平均查找长度。 2. 假定一个线性表为(38,52,25,74,68,16,30,54,90,72)，画出按线性表中元素的次序生成的一棵二叉排序树，求出其平均查找长度。 -38- 3. 假定一个待哈希存储的线性表为(32,75,29,63,48,94,25,46,18,70)，哈希地址空间为HT[13]，若采用除留余数法构造哈希函数和线性探测法处理冲突，试求出每一元素在哈希表中的初始哈希地址和最终哈希地址，画出最后得到的哈希表，求出平均查找长度。 元素 32 75 29 63 48 94 25 46 18 70 初始哈希地址 最终哈希地址 0 1 2 3 4 5 6 7 8 9 10 11 12 哈希表 4. 假定一个待哈希存储的线性表为(32,75,29,63,48,94,25,36,18,70,49,80)，哈希地址空间为HT[12]，若采用除留余数法构造哈希函数和拉链法处理冲突，试画出最后得到的哈希表，并求出平均查找长度。 四、算法设计题 1. 试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作为存储结构，且树中结点的关键字均不同。 2. 试将折半查找的算法改写成递归算法。 习题7参考答案 一、单项选择题 1. D 2. A 3. B 4. C 5. D 6. D 7. A 8. C 9. A 10. A 11. C 12. B 13. D 二、填空题 1. (n+1)/2, O(n) 2. n?picii?1 3. 20.5, 41 4. ?log2(n+1)?，O(log2n) 5. 顺序 有序 6. 1，3 7. 6， 19 8. (n/s+s)/2+1 9. 11 10. 小于，大于 11. 有序序列 12. 查找成功，左子树，右子树 13. 左子树，右子树 14. O(nlog2n) 15. 1 16. 5 17. 2 18. n/m 19. 3， 2 三、应用题 1. 折半查找判定树如图7-3所示，平均查找长度等于29/10。图7-3中的结点与有序表中元素的对应关系如下表所示。 5 2 8 3 6 4 9 图7-3 1 7 10 -39- 1 15 2 26 3 34 4 39 5 45 6 56 7 58 8 63 9 74 10 76 2. 二叉排序树如图7-4所示，平均查找长度等于32/10。 38 25 16 30 68 54 72 52 74 90 图7-4 3. H(K)=K % 13平均查找长度为14/10，其余解答如下。 元素 32 75 29 63 48 94 25 46 18 70 初始哈希地址 6 10 3 11 9 3 12 7 5 5 最终哈希地址 6 10 3 11 9 4 12 7 5 8 0 1 2 3 4 5 6 7 8 9 10 11 12 哈希表 29 94 18 32 46 70 48 75 63 25 4. H(K)=K % 11，哈希表如图7-5所示，平均查找长度17/12。 四、算法设计题 1. 设计思路：进入判别算法之前，pre取初值为min(小于树中任一结点值)，fail=FALSE,即认为bt是二叉排序树。按中序遍历bt，并在沿向根结点，与前趋比较，若逆序，则fail为TRUE,则bt不是二叉排序树。 void bisorttree(bitree bt,keytype pre, bool &fail) { //fail初值为FALSE，若非二叉序树，则fail值TRUE 图7-5 0 ∧ -40-