数据结构(c++版)课后答案 (王红梅)第7章 查找技术

《数据结构(c++版)课后答案 (王红梅)第7章 查找技术》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章查找技术课后习题讲解1.填空题⑴顺序查找技术适合于存储结构为（）的线性表，而折半查找技术适用于存储结构为（）的线性表，并且表中的元素必须是（）。【解答】顺序存储和链接存储，顺序存储，按关键码有序⑵设有一个已按各元素值排好序的线性表，长度为125，用折半查找与给定值相等的元素，若查找成功，则至少需要比较（）次，至多需比较（）次。【解答】1，7【分析】在折半查找判定树中，查找成功的情况下，和根结点的比较次数最少，为1次，最多不超过判定树的深度。⑶对于数列{25，30，8，5，1，27，24，10，20，21

2、，9，28，7，13，15}，假定每个结点的查找概率相同，若用顺序存储结构组织该数列，则查找一个数的平均比较次数为（）。若按二叉排序树组织该数列，则查找一个数的平均比较次数为（）。【解答】8，59/15【分析】根据数列将二叉排序树画出，将二叉排序树中查找每个结点的比较次数之和除以数列中的元素个数，即为二叉排序树的平均查找长度。⑷长度为20的有序表采用折半查找，共有（）个元素的查找长度为3。【解答】4【分析】在折半查找判定树中，第3层共有4个结点。⑸假定一个数列{25，43，62，31，48，56}，采用的散列

3、函数为H(k)=kmod7，则元素48的同义词是（）。【解答】62【分析】H(48)=H(62)=6⑹在散列技术中，处理冲突的两种主要方法是（　　）和（　　）。【解答】开放定址法，拉链法⑺在各种查找方法中，平均查找长度与结点个数无关的查找方法是（）。【解答】散列查找【分析】散列表的平均查找长度是装填因子的函数，而不是记录个数n的函数。页脚⑻与其他方法相比，散列查找法的特点是（）。【解答】通过关键码计算记录的存储地址，并进行一定的比较2.选择题⑴静态查找与动态查找的根本区别在于（）。A它们的逻辑结构不一样　　　

4、　　B施加在其上的操作不同C所包含的数据元素的类型不一样　D存储实现不一样【解答】B【分析】静态查找不涉及插入和删除操作，而动态查找涉及插入和删除操作。⑵有一个按元素值排好序的顺序表（长度大于2），分别用顺序查找和折半查找与给定值相等的元素，比较次数分别是s和b，在查找成功的情况下，s和b的关系是（）；在查找不成功的情况下，s和b的关系是（）。As=bBs>bCs

5、找不成功的情况也类似。⑶长度为12的有序表采用顺序存储结构，采用折半查找技术，在等概率情况下，查找成功时的平均查找长度是（），查找失败时的平均查找长度是（）。A37/12B62/13C39/12D49/13【解答】A，D【分析】画出长度为12的折半查找判定树，判定树中有12个内结点和13个外结点。⑷用n个键值构造一棵二叉排序树，其最低高度为（）。An/2BnClog2nDlog2n+1【解答】D【分析】二叉排序树的最低高度与完全二叉树的高度相同。⑸二叉排序树中，最小值结点的（）。A左指针一定为空B右指针一定为

6、空C左、右指针均为空D左、右指针均不为空【解答】A【分析】在二叉排序树中，值最小的结点一定是中序遍历序列中第一个被访问的结点，即二叉树的最左下结点。⑹散列技术中的冲突指的是（）。A两个元素具有相同的序号B页脚两个元素的键值不同，而其他属性相同C数据元素过多D不同键值的元素对应于相同的存储地址【解答】D⑺设散列表表长m=14，散列函数H(k)=kmod11。表中已有15、38、61、84四个元素，如果用线性探侧法处理冲突，则元素49的存储地址是（）。A8B3C5D9【解答】A【分析】元素15、38、61、84分

7、别存储在4、5、6、7单元，而元素49的散列地址为5，发生冲突，向后探测3个单元，其存储地址为8。⑻在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值（）。A一定都是同义词B一定都不是同义词C不一定都是同义词D都相同【解答】C【分析】采用线性探测法处理冲突会产生堆积，即非同义词争夺同一个后继地址。3.判断题⑴二叉排序树的充要条件是任一结点的值均大于其左孩子的值，小于其右孩子的值。【解答】错。分析二叉排序树的定义，是左子树上的所有结点的值都小于根结

8、点的值，右子树上的所有结点的值都大于根结点的值。例如图7-7所示二叉树满足任一结点的值均大于其左孩子的值，小于其右孩子的值，但不是二叉排序树。⑵二叉排序树的查找和折半查找的时间性能相同。【解答】错。二叉排序树的查找性能在最好情况和折半查找相同。⑶若二叉排序树中关键码互不相同，则其中最小元素和最大元素一定是叶子结点。【解答】错。在二叉排序树中，最小元素所在结点一定是中序遍历序列中第一个被访问的结点，即