数据结构Ch9习题答案

《数据结构Ch9习题答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、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(n2）B．O(nlog2n)C．O(n)D．O(log2n)5．二分查找和

2、二叉排序树的时间性能B。A．相同B．不相同就平均时间性能而言，二叉排序树上的查找和二分查找差不多。就维护表的有序性而言，二叉排序树无须移动结点，只需修改指针即可完成插入和删除操作，且其平均的执行时间均为O(log2n)，因此更有效。二分查找所涉及的有序表是一个向量，若有插入和删除结点的操作，则维护表的有序性所花的代价是O(n)。当有序表是静态查找表时，宜用向量作为其存储结构，而采用二分查找实现其查找操作；若有序表里动态查找表，则应选择二叉排序树作为其存储结构。6．有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查

3、找值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的结点时需要进行旋转调整。99．向一棵二叉搜索树中插入一个新元素时，若该新元素的值大于根结点的值，则应把它插入到根结点右子树上。10．根据一组记录(56,42,73,50,64,48,22)依次插入结点生成一棵AV

4、L树（高度平衡的二叉搜索树）时，当插入到值为48的结点时才出现不平衡，需要进行旋转调整。11．以顺序搜索方法从长度为n的顺序表或单链表中搜索一个元素时，其时间复杂度为O(n)。12．在一棵AVL树（高度平衡的二叉搜索树）中，每个结点的左子树高度与右子树高度之差的绝对值不超过1。13．在线性表的散列存储中，装载因子a又称为装载系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则a等于n/m。14．以折半搜索方法从长度为n的有序表中搜索一个元素时，时间复杂度为O(log2n)。15．假定一个顺序表的长度为40，并假定搜索每个元素的概率都相同，则在搜索成功情

5、况下的平均搜索长度为20.5。16．假定要对长度n=100的线性表进行散列存储，并采用开散列法处理冲突，则对于长度m=20的散列表，每个散列地址的同义词子表（单链表）的长度平均为5。17．假定对长度n=50的有序表进行折半搜索，则对应的判定树中最后一层的结点数为19个。12481619918．根据n个元素建立一棵二叉搜索树(二叉排序树)的时间复杂度性大致为O(nlog2n)。19．从一棵二叉搜索树中搜索一个元素时，若给定值小于根结点的值，则需要向左子树继续搜索。20．假定一个线性表为(”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkw

6、te”,”ccdt”,”aayb”)，若按照字符串的第一个字母进行划分，使得第一个字母相同的字符串被划分在一个子表中，则得到的以a为第一个字母的子表长度3。21．假设在有序线性表A[1．．20]上进行二分查找，则比较一次查找成功的结点数为1，则比较二次查找成功的结点数为2，则比较三次查找成功的结点数为4，则比较四次查找成功的结点数为8，则比较五次查找成功的结点数为5，平均查找长度为3．7。22．对于长度为n的线性表，若进行顺序查找，则时间复杂度为O(n)；若采用二分法查找，则时间复杂度为O(log2n)。23、对长度为3的顺序表进行搜索，若搜索第一个元素的概率为

7、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

8、．4D．526、向一棵A