数据结构答案第7章

第7章查找技术1970-01-01第7章查找技术课后习题讲解1.填空题⑴顺序查找技术适合于存储结构为（）的线性表，而折半查找技术适用于存储结构为（）的线性表，并且表中的元素必须是（）。【解答】顺序存储和链接存储，顺序存储，按关键码有序⑵设有一个已按各元素值排好序的线性表，长度为125，用折半查找与给定值相等的元素，若查找成功，则至少需要比较（）次，至多需比较（）次。【解答】1，7【分析】在折半查找判定树中，查找成功的情况下，和根结点的比较次数最少，为1次，最多不超过判定树的深度。⑶对于数列{25，30，8，5，1，27，24，10，20，21，9，28，7，13，15}，假定每个结点的查找概率相同，若用顺序存储结构组织该数列，则查找一个数的平均比较次数为（）。若按二叉排序树组织该数列，则查找一个数的平均比较次数为（）。【解答】8，59/15【分析】根据数列将二叉排序树画出，将二叉排序树中查找每个结点的比较次数之和除以数列中的元素个数，即为二叉排序树的平均查找长度。⑷长度为20的有序表采用折半查找，共有（）个元素的查找长度为3。【解答】4【分析】在折半查找判定树中，第3层共有4个结点。⑸假定一个数列{25，43，62，31，48，56}，采用的散列函数为H(k)=kmod7，则元素48的同义词是（）。【解答】62【分析】H(48)=H(62)=6⑹在散列技术中，处理冲突的两种主要方法是（）和（）。【解答】开放定址法，拉链法⑺在各种查找方法中，平均查找长度与结点个数无关的查找方法是（）。【解答】散列查找【分析】散列表的平均查找长度是装填因子的函数，而不是记录个数n的函数。⑻与其他方法相比，散列查找法的特点是（）。【解答】通过关键码计算记录的存储地址，并进行一定的比较2.选择题⑴静态查找与动态查找的根本区别在于（）。A它们的逻辑结构不一样B施加在其上的操作不同C所包含的数据元素的类型不一样D存储实现不一样【解答】B【分析】静态查找不涉及插入和删除操作，而动态查找涉及插入和删除操作。⑵有一个按元素值排好序的顺序表（长度大于2），分别用顺序查找和折半查找与给定值相等的元素，比较次数分别是s和b，在查找成功的情况下，s和b的关系是（）；在查找不成功的情况下，s和b的关系是（）。As=bBsbCs【解答】D，D【分析】此题没有指明是平均性能。例如，在有序表中查找最大元素，则顺序查找比折半查找快，而平均性能折半查找要优于顺序查找，查找不成功的情况也类似。⑶长度为12的有序表采用顺序存储结构，采用折半查找技术，在等概率情况下，查找成功时的平均查找长度是（），查找失败时的平均查找长度是（）。A37/12B62/13C39/12D49/13【解答】A，B【分析】画出长度为12的折半查找判定树，判定树中有12个内结点和13个外结点。⑷用n个键值构造一棵二叉排序树，其最低高度为（）。An/2BnClog2nDlog2n+1【解答】D【分析】二叉排序树的最低高度与完全二叉树的高度相同。⑸二叉排序树中，最小值结点的（）。A左指针一定为空B右指针一定为空C左、右指针均为空D左、右指针均不为空【解答】A【分析】在二叉排序树中，值最小的结点一定是中序遍历序列中第一个被访问的结点，即二叉树的最左下结点。⑹散列技术中的冲突指的是（）。A两个元素具有相同的序号B两个元素的键值不同，而其他属性相同C数据元素过多D不同键值的元素对应于相同的存储地址【解答】D⑺设散列表表长m=14，散列函数H(k)=kmod11。表中已有15、38、61、84四个元素，如果用线性探侧法处理冲突，则元素49的存储地址是（）。A8B3C5D9【解答】A【分析】元素15、38、61、84分别存储在4、5、6、7单元，而元素49的散列地址为5，发生冲突，向后探测3个单元，其存储地址为8。⑻在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值（）。A一定都是同义词B一定都不是同义词C不一定都是同义词D都相同【解答】C【分析】采用线性探测法处理冲突会产生堆积，即非同义词争夺同一个后继地址。3.判断题⑴二叉排序树的充要条件是任一结点的值均大于其左孩子的值，小于其右孩子的值。【解答】错。分析二叉排序树的定义，是左子树上的所有结点的值都小于根结点的值，右子树上的所有结点的值都大于根结点的值。例如图7-7所示二叉树满足任一结点的值均大于其左孩子的值，小于其右孩子的值，但不是二叉排序树。⑵二叉排序树的查找和折半查找的时间性能相同。【解答】错。二叉排序树的查找性能在最好情况和折半查找相同。⑶若二叉排序树中关键码互不相同，则其中最小元素和最大元素一定是叶子结点。【解答】错。在二叉排序树中，最小元素所在结点一定是中序遍历序列中第一个被访问的结点，即是二叉树的最左下结点，但可能有右子树。最大元素所在结点一定是中序遍历序列中最后一个被访问的结点，即是二叉树的最右下结点，但可能有左子树。如图7-8所示，5是最小元素，25是最大元素，但5和25都不是叶子结点。⑷散列技术的查找效率主要取决于散列函数和处理冲突的方法。【解答】错。更重要的取决于装填因子，散列表的平均查找长度是装填因子的函数。⑸当装填因子小于1时，向散列表中存储元素时不会引起冲突。【解答】错。装填因子越小，只能说明发生冲突的可能性越小。4．分别画出在线性表（a，b，c，d，e，f，g）中进行折半查找关键码e和g的过程。【解答】查找关键码e的过程如图7-9所示，查找关键码g的过程如图7-10所示。5．画出长度为10的折半查找判定树，并求等概率时查找成功和不成功的平均查找长度。【解答】参见7.2.1。6．将数列（24，15，38，27，121，76，130）的各元素依次插入一棵初始为空的二叉排序树中，请画出最后的结果并求等概率情况下查找成功的平均查找长度。【解答】二叉排序树如图7-11所示，其平均查找长度=1+2×2+3×2+4×2=19/77．一棵二叉排序树的结构如图7-12所示，结点的值为1～8，请标出各结点的值。【解答】二叉排序树中各结点的值如图7-13所示。8．已知散列函数H(k)=kmod12，键值序列为(25,37,52,43,84,99,120,15,26,11,70,82)，采用拉链法处理冲突，试构造开散列表，并计算查找成功的平均查找长度。【解答】H(25)=1,H(37)=1,H(52)=4,H(43)=7,H(84)=0,H(99)=3,H(120)=0,H(15)=3,H(26)=2,H(11)=11,H(70)=10,H(82)=10构造的开散列表如下：平均查找长度ASL=(8×1+4×2)/12=16/129.算法设计⑴设计顺序查找算法，将哨兵设在下标高端。【解答】将哨兵设置在下标高端，表示从数组的低端开始查找，在查找不成功的情况下，算法自动在哨兵处终止。具体算法如下：⑵编写算法求给定结点在二叉排序树中所在的层数。【解答】根据题目要求采用递归方法，从根结点开始查找结点p，若待查结点是根结点，则深度为1，否则到左子树（或右子树）上去找，查找深度加1。具体算法如下：⑶编写算法，在二叉排序树上找出任意两个不同结点的最近公共祖先。【解答】设两个结点分别为A和B，根据题目要求分下面情况讨论：⑴若A为根结点，则A为公共祖先；⑵若A-datadata且root-datadata，root为公共祖先；⑶若A-datadata且B-datadata，则到左子树查找；⑷若A-dataroot-data且B-dataroot-data，则到右子树查找。具体算法如下：⑷设计算法判定一棵二叉树是否为二叉排序树。【解答】对二叉排序树来讲，其中序遍历序列为一个递增序列。因此，对给定二叉树进行中序遍历，如果始终能够保证前一个值比后一个值小，则说明该二叉树是二叉排序树。具体算法如下：学习自测及答案1．已知一个有序表为（12，18，24，35，47，50，62，83，90，115，134），当折半查找值为90的元素时，经过（）次比较后查找成功。A2B3C4D5【解答】A2．已知10个元素（54，28，16，73，62，95，60，26，43），按照依次插入的方法生成一棵二叉排序树，查找值为62的结点所需比较次数为（）。A2B3C4D5【解答】B3．已知数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为（）。A4B5C6D7【解答】B4．按（）遍历二叉排序树得到的序列是一个有序序列。A前序B中序C后序D层次【解答】B5．将二叉排序树T按前序遍历序列依次插入初始为空的二叉排序树T'中，则T与T'是相同的，这种说法是否正确？【解答】正确6.一棵高度为h的平衡二叉树，最少含有个结点。A2hB2h-1C2h+1D2h-1【解答】D7．在散列函数H(k)=kmodm中，一般来讲，m应取（）。A奇数B偶数C素数D充分大的数【解答】C8．已知关键码序列为（Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec），散列表的地址空间为0~16，设散列函数为H(x)=，其中i为关键码中第一个字母在字母表中的序号，采用线性探测法和链地址法处理冲突，试分别构造散列表，并求等概率情况下查找成功的平均查找长度。【解答】H(Jan)=10/2=5,H(Feb)=6/2=3,H(Mar)=13/2=6,H(Apr)=1/2=0H(May)=13/2=6,H(Jun)=10/25,H(Jul)=10/25,H(Aug)=1/2=0H(Sep)=19/2=8,H(Oct)=15/2=7,H(Nov)=14/2=7,H(Dec)=4/2=2采用线性探测法处理冲突，得到的闭散列表如下：平均查找长度=(1+1+1+1+2+4+5+2+3+5+6+1)/12=32/12采用链地址法处理冲突，得到的开散列表如下：平均查找长度=(1×7+2×4+3×1)/12=18/129.试推导含有12个结点的平衡二叉树的最大深度，并画出以棵这样的树。【解答】令Fk表示含有最少结点的深度为k的平衡二叉树的结点树目，则：F1=1，F2=2，…，Fn=Fn-2+Fn-1+1。含有12个结点的平衡二叉树的最大深度为5，例如：关闭