数据结构习题第九章查找答案.docx

《数据结构习题第九章查找答案.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第9章集合一．选择题1.C2.A3.1D3.2C4.D5.B6.D7.D8.C9.A10.D11.B12.1C12.2C13.1C13.2D13.3G13.4H14.1E14.2B14.3E14.4B14.5B15.1B15.2A16.A17.C18.C19.C20.D21.B22.C23.B24.C25.1B25.2F25.3I26.A27.D28.C29.1A29.2C30.B31.D32.D33.C34.D35.1D35.2C36.C二．判断题1.√2.√3.×4.×5.×6.√7.√8.×9.×10.×11.×12.√1

2、3.√14.×15.×16.×17.√18.×19.√20.×21.×22.×23.×24.×25.√26.×27.×28.√29.√30.×31.×32.√33.√34.×35.√36.√部分答案解释如下。4．不能说哪种哈希函数的选取方法最好，各种选取方法有自己的适用范围。8．哈希表的结点中可以包括指针，指向其元素。11．单链表不能使用折半查找方法。20．按插入后中序遍历是递增序列的原则，若某结点只有右子树，而插入元素的关键字小于该结点的关键字，则会插入到该结点的左侧，成为其左孩子。这种插入就不是插入到叶子下面。21．从平衡因

3、子定义看，完全二叉树任一结点的平衡因子的绝对值确实是小于等于1。但是，平衡二叉树本质上是二叉排序树，完全二叉树不一定是排序树。故不能说完全二叉树是平衡二叉树。23．某结点的左子树根结点不一定是它的中序前驱，其右子树根结点也不一定是它的中序后继。24．在等概率下，查找成功时的平均查找长度相同，查找失败时的平均查找长度不相同。26．只有被删除结点是叶子结点时命题才正确。三．填空题1．nn+12．43．6,9,11,124．55．26（第4层是叶子结点，每个结点两个关键字）6．1,3,6,8,11,13,16,197．5,968．m-

4、1,「m/2ù-19．2,4,310．(1)哈希函数(2)解决冲突的方法(3)选择好的哈希函数(4)处理冲突的方法(5)均匀(6)简单11．AVL树（高度平衡树，高度平衡的二叉排序树），或为空二叉树，或二叉树中任意结点左子树高度与右子树高度差的绝对值小于等于1。12．小于等于表长的最大素数或不包含小于20的质因子的合数13．1614．ë㏒2n」+115．(1)45(2)45(3)46（块内顺序查找）16．k(k+1)/217．30，31.5（块内顺序查找）18．(1)顺序存储或链式存储(2)顺序存储且有序(3)块内顺序存储，块间

5、有序(4)散列存储19．(n+1)/220．(n+1)/n*log2(n+1)-121．结点的左子树的高度减去结点的右子树的高度22．(1)顺序表(2)树表(3)哈希表(4)开放定址方法(5)链地址方法(6)再哈希(7)建立公共溢出区23．直接定址法24．logém/2ù()+125．O(N)26．n(n+1)/227．5428．3129．37/1230．主关键字31．左子树右子树32．插入删除33．1434．(1)126(2)64(3)33(4)6535．（1）low<=high(2)(low+hig)DIV2(3)binsr

6、ch:=mid(4)binsrch:=036．(1)k(2)Irear38．(1)p!=null(2)pf=p(3)p!=*t(4)*t=null四．应用题1．概念是基本知识的主要部分，要牢固掌握。这里只列出一部分，目的是引起重视，解答略。2．（1）散列表存储的基本思想是用关键字的值决定数据元素的存储地址（2）散列表存储中解决碰撞的基本方法：①开放定址法形成地址序列的公式是：Hi=（H（key）+di）%m，其中m是表长，di是增量。根据di取法不

7、同，又分为三种：a．di=1，2，…，m-1称为线性探测再散列，其特点是逐个探测表空间，只要散列表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一散列地址。b．di=12，-12，22，-22，…，±k2（k≤m/2）称为二次探测再散列，它减少了聚集，但不容易探测到全部表空间，只有当表长为形如4j+3（j为整数）的素数时才有可能。c．di=伪随机数序列，称为随机探测再散列。②再散列法Hi=RHi（key）i=1，2，…，k，是不同的散列函数，即在同义词产生碰撞时，用另一散列函数计算散列地址，直到解

8、决碰撞。该方法不易产生“聚集”，但增加了计算时间。③链地址法将关键字为同义词的记录存储在同一链表中，散列表地址区间用H[0..m-1]表示，分量初始值为空指针。凡散列地址为i（0≤i≤m-1）的记录均插在以H[i]为头指针的链表中。这种解决方法中数据元素个数不受