文档详情

数据结构第七章参考答案.doc

发布:2017-06-03约3.47千字共4页下载文档
文本预览下载声明
习题7 填空题 (1)由10000个结点构成的二叉排序树,在等概率查找的条件下,查找成功时的平均查找长度的最大值可能达到(___________)。 答案:5000.5 (2)长度为11的有序序列:1,12,13,24,35,36,47,58,59,69,71进行等概率查找,如果采用顺序查找,则平均查找长度为(___________),如果采用二分查找,则平均查找长度为(___________),如果采用哈希查找,哈希表长为15,哈希函数为H(key)=key%13,采用线性探测解决地址冲突,即di H key +i %15,则平均查找长度为(保留1位小数)(___________)。 答案:6,3,1.6 (3)在折半查找中,查找终止的条件为(___________)。 答案:找到匹配元素或者low high? (4)某索引顺序表共有元素275个,平均分成5块。若先对索引表采用顺序查找,再对块元素进行顺序查找,则等概率情况下,分块查找成功的平均查找长度是(___________)。 答案:31 (5)高度为8的平衡二叉树的结点数至少是(___________)。 答案: 54 计算公式:F n F n-1 +F n-2 +1 (6)对于这个序列 25,43,62,31,48,56 ,采用的散列函数为H k k%7,则元素48的同义词是(___________)。 答案:62 (7)在各种查找方法中,平均查找长度与结点个数无关的查找方法是(___________)。 答案:散列查找 (8)一个按元素值排好的顺序表(长度大于2),分别用顺序查找和折半查找与给定值相等的元素,平均比较次数分别是s和b,在查找成功的情况下,s和b的关系是(___________);在查找不成功的情况下,s和b的关系是(___________)。 答案: 1 2s-1 b 2s [log2 2s-1 ]+1 -2[log2 2s-1 ]+1+1 2 分两种情况考虑,见解答。 解: 1 设所有元素的个数为n,显然有s n* n+1 / 2n ,则 n 2s-1 设折半查找树高度为k,则前k-1层是满二叉树,最后一层的节点数为 n- 2k-1 -1) 因此,总比较次数 nb 20*1+21*2+22*3+…+2k-2* k-1 + n- 2k-1 -1 *k, 而 20*1+21*2+22*3+…+2k-2* k-1 2k-1*k-2k+1 因此 nb 2k-1*k-2k+1+ n- 2k-1-1 *k n+1 k-2k+1 又k [log2n]+1,n 2s-1,所以有 2s-1 b 2s [log2 2s-1 ]+1 -2[log2 2s-1 ]+1+1 2 查找不成功,对于顺序查找有:s n。对于折半查找,找不到的情况有n+1种,查找到每个叶子节点或度为1的节点后就不再查找,设折半查找树高度为k,则第k-1层的节点数x 2k-2,第k层的节点数y n- 2k-1 -1) (a)当第k层的节点数y小于等于第k-1层的节点数x时, 则第k-1层有y结点度为1,其余x-y个结点度为0。 则查找次数为: n+1 b 2yk+2 x-y k-1 +y k-1 2x k-1 +yk n+1 b 2k-1 * k-1 + n- 2k-1 -1 *k (b)当第k层的节点数y大于第k-1层的节点数x时, 则第k-1层不存在度为0的结点,有2x-y个结点度为1,其余y-x个结点度为2 则查找次数为: n+1 b 2yk+ 2x-y k-1 2x k-1 +y k+1 n+1 b 2k-1 * k-1 + n- 2k-1 -1 * k+1 将k [log2n]+1,n s分别代入(a)(b)两个等式即得。 选择题 (1)从一个具有n个结点的单链表中查找其值等于x的结点时,在查找成功的情况下,需平均比较( )个结点。 A. n B. n/2 C. n-1 /2 D. n+1 /2 (2)对一个长度为50的有序表进行折半查找,最多比较( )次就能查找出结果。 A. 6 B. 7 C. 8 D. 9 (3)对有18个元素的有序表做折半查找,则查找A[3](下标从1开始)的比较序列的下标依次为( )。 A. 1-2-3 B. 9-5-2-3 C. 9-5-3 D. 9-4-2-3 (4)在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡点为A,并已知A的左孩子的平衡因子为-1,右孩子的平衡因子为0,则做( )型调整以使其平衡。 A. LL B. LR C. RL D. RR (5)理论上,散列表的平均比较次数为( )次。 A. 1 B. 2 C. 4 D. n (6)二叉排序树中,最小值结点的
显示全部
相似文档