数据结构Ch9习题答案

./Ch9查找一、单项选择题1．顺序查找法适合于存储结构为B的线性表。A．散列存储B．顺序存储或存储C．压缩存储D．索引存储2．对线性表进行二分查找时,要求线性表必须C。A．以顺序方式存储B．以方式存储C．以顺序方式存储,且结点按关键字有序排序D．以方式存储,且结点按关键字有序排序3．采用顺序查找方法查找长度为n的线性表时,每个元素的平均查找长度为C。A．nB．n/2C．<n+1>/2D．<n-1>/24．采用二分查找方法查找长度为n的线性表时,每个元素的平均查找长度为D。A．O<n2B．O<nlog2n>C．O<n>D．O<log2n>5．二分查找和二叉排序树的时间性能B。A．相同B．不相同就平均时间性能而言,二叉排序树上的查找和二分查找差不多。就维护表的有序性而言,二叉排序树无须移动结点,只需修改指针即可完成插入和删除操作,且其平均的执行时间均为O<log2n>,因此更有效。二分查找所涉及的有序表是一个向量,若有插入和删除结点的操作,则维护表的有序性所花的代价是O<n>。当有序表是静态查找表时,宜用向量作为其存储结构,而采用二分查找实现其查找操作；若有序表里动态查找表,则应选择二叉排序树作为其存储结构。6．有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值82为的结点时,C次比较后查找成功。A．1B．2C．4D．87．有一个长度为12的有序表,按二分查找法对该表进行查找,在表各元素等概率情况下查找成功所需的平均比较次数为B。A．35/12B．37/12C．39/12D．43/128．根据一组记录<56,42,50,64,48>依次插入结点生成一棵AVL树〔高度平衡的二叉搜索树时,当插入到值为50的结点时需要进行旋转调整。9．向一棵二叉搜索树中插入一个新元素时,若该新元素的值大于根结点的值,则应把它插入到根结点右子树上。10．根据一组记录<56,42,73,50,64,48,22>依次插入结点生成一棵AVL树〔高度平衡的二叉搜索树时,当插入到值为48的结点时才出现不平衡,需要进行旋转调整。11．以顺序搜索方法从长度为n的顺序表或单链表中搜索一个元素时,其时间复杂度为O<n>。12．在一棵AVL树〔高度平衡的二叉搜索树中,每个结点的左子树高度与右子树高度之差的绝对值不超过1。13．在线性表的散列存储中,装载因子a又称为装载系数,若用m表示散列表的长度,n表示待散列存储的元素的个数,则a等于n/m。14．以折半搜索方法从长度为n的有序表中搜索一个元素时,时间复杂度为O<log2n>。15．假定一个顺序表的长度为40,并假定搜索每个元素的概率都相同,则在搜索成功情况下的平均搜索长度为20.5。16．假定要对长度n=100的线性表进行散列存储,并采用开散列法处理冲突,则对于长度m=20的散列表,每个散列地址的同义词子表〔单链表的长度平均为5。17．假定对长度n=50的有序表进行折半搜索,则对应的判定树中最后一层的结点数为19个。1248161918．根据n个元素建立一棵二叉搜索树<二叉排序树>的时间复杂度性大致为O<nlog2n>。19．从一棵二叉搜索树中搜索一个元素时,若给定值小于根结点的值,则需要向左子树继续搜索。20．假定一个线性表为<"abcd","baabd","bcef","cfg","ahij","bkwte","ccdt","aayb">,若按照字符串的第一个字母进行划分,使得第一个字母相同的字符串被划分在一个子表中,则得到的以a为第一个字母的子表长度3。21．假设在有序线性表A[1．．20]上进行二分查找,则比较一次查找成功的结点数为1,则比较二次查找成功的结点数为2,则比较三次查找成功的结点数为4,则比较四次查找成功的结点数为8,则比较五次查找成功的结点数为5,平均查找长度为3．7。22．对于长度为n的线性表,若进行顺序查找,则时间复杂度为O<n>；若采用二分法查找,则时间复杂度为O<log2n>。23、对长度为3的顺序表进行搜索,若搜索第一个元素的概率为1/2,搜索第二个元素的概率为1/3,搜索第三个元素的概率为1/6,则搜索到表中任一元素的平均搜索长度为A。A．5/3B．2C．7/3D．4/31/2*3+1/3*2+1/6*1=9/6+4/6+1/6=7/31/2*1+1/3*2+1/6*3=3/6+4/6+3/6=5/324、向一棵AVL树〔高度平衡的二叉搜索树插入元素时,可能引起对最小不平衡子树的双向旋转的调整过程,此时需要修改相关C个结点指针域的值。A．2B．3C．4D．525、向一棵AVL树〔高度平衡的二叉搜索树插入元素时,可能引起对最小不平衡子树的调整过程,此调整分为C种旋转类型。A．2B．3C．4D．526、向一棵AVL树〔高度平衡的二叉搜索树插入元素时,可能引起对最小不平衡子树的左单或右单旋转的调整过程,此时需要修改相关C个结点指针域的值。A．2B．3C．4D．5三、判断题：1．<×>对二叉搜索树进行前序遍历得到的结点序列是一个有序序列。2．<√>折半搜索所对应的判定树,既是一棵二叉搜索树,又是一棵理想平衡二叉树〔它的特点是除最底层结点外其他各层结点数都是满的,最底层的若干结点可能散布在该层各处。3．<√>装载因子是散列表的一个重要参数,它反映了散列表的装满程度。4．<√>对于两棵具有相同记录集合而具有不同结构的二叉搜索树,按中序遍历得到的结点序列是相同的。三、综合练习题:1．画出对长度为10的有序表进行折半查找的判定树,并求其等概率时查找成功的平均查找长度。等概率时查找成功的平均查找长度=<1*1+2*2+4*3+3*4>/10=2．92．已知一组关键字{49,38,65,97,76,13,27,44,82,35,50},画出由此生成的二叉排序树和平衡二叉树。二叉排序树：平衡二叉树：3．设某字典组成如下∶D={016,087,154,170,275,426,503,509,512,612,653,677,703,765,897,908}依次顺序表示在存中,现用二分法的方法查找字典中是否有元素612,问需要进行多少次比较才能得到结论?每次选择的比较对象是什么元素?解：比较次数为3次,第一次和509比较,第二次和677比较,第三次和612比较。4．试给出一个关键码序列,使构造AVL树时四种调整平衡操作<LL,LR,RR,RL>各至少执行一次,并画出其构造过程。:解：设输入序列为{12,6,4,16,24,15,13,1,3}5．设顺序表中关键字是递增有序的,试写一顺序查找算法,将哨兵设在表的高下标端。解：Search_Seq<SSTableST,KeyTypekey>{//顺序查找的算法,n号元素为监视哨 ST．elem[n]．key=key;//哨兵 for<i=0;!EQ<ST．elem[i]．key,key>;++i>;returni;}6．什么叫静态查找？什么叫动态查找？什么样的存储结构适宜于进行静态查找？什么样的存储结构适宜于进行动态查找？7．什么叫平均查找长度？写出平均查找长度的定义。8．已知一个个数为12的数据元素序列为{Dec,Feb,Nov,Oct,June,Sept,Aug,Apr,May,July,Jan,Mar},要求：〔1按各数据元素的顺序构造一棵二叉排序树。〔2设各数据元素的查找概率相等,给出该二叉排序树的平均查找长度。〔注：字母的大小是指字母的ASCII码数值大小〔3按各数据元素的顺序构造一棵平衡二叉树。解：〔1构造的二叉排序树：〔2平均查找长度为：〔1*1+2*2+2*3+2*4+3*5+2*6/12=46/12=23/6〔3构造的平衡二叉树：9．使用散列函数hash<x>=x%11,把一个整数值转换成散列表地址。现要把数据1,13,12,34,38,33,27,22插入到散列表中。<1>使用线性探查再散列法来构造散列表。<2>使用链地址法构造散列表。针对这两种情况,确定其装载因子,搜索成功所需的平均探查次数,以及搜索不成功所需的平均探查次数。解：<1>Hash<1>=1；成功hash<13>=2；成功hash<12>=1；冲突；hash<12>=2；冲突；hash<12>=3；成功；hash<34>=1；hash<34>=2；冲突；hash<34>=3；冲突；hash<34>=3；冲突；hash<34>=4；成功hash<38>=5；成功hash<33>=0；成功hash<27>=5；冲突；hash<27>=6；成功hash<22>=0；冲突；hash<22>=1；冲突；hash<22>=2；冲突；hash<22>=3；冲突；hash<22>=4；冲突；hash<22>=5；冲突；hash<22>=6；冲突；hash<22>=7；成功线性探查再散列法来构造的散列表012345678910331131234382722搜索次数1