数据结构与算法教程 习题答案作者 朱明方 吴及 第6章习题解答.doc

《数据结构与算法教程 习题答案作者 朱明方 吴及 第6章习题解答.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第6章习题解答6.1对于规模分别为210，220，250，2100的有序查找表，请比较采用折半查找和顺序查找的比较次数。[解答]顺序查找的比较次数分别是折半查找的大约100，5*104，2*1013，1028倍。6.2向一棵空的二叉搜索树中顺序插入关键字algorithm，画出得到的BST。[解答]得到的BST如图6-1所示。图6-16.3假设我们在建立二叉搜索树之前预先对其中的关键字被访问的频率进行了估算，那么把这些关键字插入到树时，应该以可能的访问频率的递增顺序还是递减顺序插入？试进行解释。[解答]应该以递减顺序插入。因为对二叉搜索树中结点的查找效率决定于查找值

2、与结点值的比较次数，而比较次数等于被查找结点所在的层次，所以离根越近的结点查找速度越快，使被访问频率高的结点离根结点近，可以使查找效率尽可能高。6.4通过向一棵空的二叉搜索树插入关键字algorithm，要求构造一种插入序列，使得在以下的意义下，生成的BST等价于折半查找树：对于同一关键字集合，在BST中对任意关键字所做的查找和折半查找使用相同的比较操作序列。试描述你的构造方法。[解答]按题中要求所构造的插入序列为：lgoahmrit。实际上要求构造一个序列，使得顺序插入得到的二叉搜索树恰好是折半查找树。因此可以先对原序列排序(建立一棵BST，再做中序遍历)，再对有

3、序序列建立折半查找树，然后对折半查找树进行层序遍历，得到的序列就是所要求的序列。6.5存在多少棵N个结点构成且高度为N的二叉搜索树？存在多少种不同方法，把N个不同的关键字插入到一棵原先为空的二叉搜索树，得到高度为N的BST？[解答]由N个节点构成且高度为N的不同构型的二叉搜索树可以有2N-1棵。6.6对有序表进行折半查找形成的折半查找树和二叉搜索树有何异同之处？13［解答］相同点：折半查找树和二叉搜索树都满足二叉搜索树的特性；不同点：折半查找树是平衡的二叉搜索树，而一般的二叉搜索树不一定平衡；折半查找树是用来描述对有序表进行折半查找过程，并不实际存在，而二叉搜索树是

4、实际存在的动态搜索结构；6.7一棵有12个结点的AVL树的最大深度是多少，请画出这样的AVL树。［解答］有12个结点的AVL树的最大深度为5；它可以有不同的构型，图6-2所示的是其中的一种构型，读者还可以画出其他的构型。图6-26.8已知某二叉搜索树的前序遍历序列为：18,12,6,49,40,55，67，86(1)请画出该二叉树的结构图；(2)该二叉树是不是AVL树？若不是，请画出平衡化后的结构图；(3)在该AVL树中插入元素52，仍保持其为AVL树，画出插入后的AVL树结构图；(4)在(3)的基础上删除元素12，仍使其为AVL树，画出删除后的结构图。［解答］(1

5、)该二叉树的结构如图6-3所示。(2)图6-3所示的二叉树不是AVL树，因为二叉树中数据元素18和数据元素55所在的结点其平衡因子都大于1；对其进行平衡化以后得到的二叉树是AVL树，其结构如图6-4所示。图6-3图6-4(3)插入数据元素52以后的AVL树如图6-5所示。13图6-5图6-6(4)删除数据元素12以后的AVL树如图6-6所示。6.9含9个叶子结点的3阶B-树至少有多少个非叶子结点？含10个叶子结点的3阶B-树至多有多少个非叶子结点？［解答］根据B-树的定义可知，含9个叶子结点的3阶B-树至少有4个非叶子结点，此时B-树中所有分支结点都拥有最大的分支数

6、。含10个叶子结点的3阶B-树至多有8个非叶子结点。此时B-树中的各分支结点应具有尽可能少的分支。6.10图6-42表示一棵3阶B-树，现要删除关键字74：(1)说明其操作步骤；(2)画出删除关键字74后B-树的结构。13图6-42[解答](1)删除关键字74步骤为：☆删除关键字74，用其右子树最小关键字88替代(或左子树最大关键字58替代)；☆删除叶子结点上关键字88(或者58)，需要合并。将双亲结点上关键字下移和左兄弟上关键字58(右兄弟上关键字88)合并；☆双亲结点上已没有关键字，其左兄弟上尚有两个关键字，可以进行调用；将其双亲结点上关键字50下移，其左兄弟上

7、关键字32上移至双亲结点，32对应的子树平移到本结点最左位置。(2)删除74后B-树的结构如图6-7所示。图6-76.11有如图6-43所示的一棵树，图6-43(1)如果这是一棵AVL树，向图中依次插入19，20，25，分别图示出上述数据元素插入和调整的详细步骤。(2)如果这是一棵3阶的B-树，向图中依次插入数据元素20，25，32，再依次删除数据元素46,12，32，分别图示出上述数据元素插入和删除的详细步骤。[解答](1)如果是AVL树：13插入19后如图6-8(a)所示；插入20后如图6-8(b)、(c)所示；插入25后如图6-8(d)、(e)所示。(a)