数据结构Ch9习题答案

Ｃ h9 查找一、单项选择题1．顺序查找法适合于存储结构为Ｂ得线性表。A。散列存储 B．顺序存储或链接存储 C.压缩存储 Ｄ.索引存储2．对线性表进行二分查找时,要求线性表必须 C.A.以顺序方式存储 B。以链接方式存储C.以顺序方式存储,且结点按关键字有序排序 Ｄ。以链接方式存储,且结点按关键字有序排序3．采纳顺序查找方法查找长度为 n 得线性表时,每个元素得平均查找长度为 C.Ａ。ｎ B.n/2 C．（n+1）/2 D。（ｎ—1）/2４。 采纳二分查找方法查找长度为 n 得线性表时，每个元素得平均查找长度为Ｄ.A.Ｏ（n2） B. Ｏ(ｎｌ o ｇ 2n） C。O(n） D．O(ｌ og2n)5.二分查找与二叉排序树得时间性能 B。Ａ.相同 B.不相同就平均时间性能而言,二叉排序树上得查找与二分查找差不多。就维护表得有序性而言,二叉排序树无须移动结点，只需修改指针即可完成插入与删除操作，且其平均得执行时间均为Ｏ（log2n),因此更有效.二分查找所涉及得有序表就是一个向量,若有插入与删除结点得操作，则维护表得有序性所花得代价就是 O（n）。当有序表就是静态查找表时,宜用向量作为其存储结构，而采纳二分查找实现其查找操作；若有序表里动态查找表,则应选择二叉排序树作为其存储结构.6.有一个有序表为｛1,3,9，12，３ 2，41,４５，６ 2，７ 5,７ 7，82，95，100｝，当二分查找值 82 为得结点时，Ｃ次比较后查找成功。Ａ.1 B。2 C.4 D。87。有一个长度为 12 得有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需得平均比较次数为 B。Ａ．35/1 ２ B.37/１ 2 C.3 ９/12 D.４３/１２８．根据一组记录 ( 5 ６， 42， 50， 6 ４， 48 ) 依次插入结点生成一棵 AVL 树(高度平衡得二叉搜索树)时，当插入到值为 50 得结点时需要进行旋转调整。 9。向一棵二叉搜索树中插入一个新元素时，若该新元素得值大于根结点得值，则应把它插入到根结点 右子树 上。 10。根据一组记录 ( 56， 4 ２， 73， 50， 6 ４, 48, 22 ） 依次插入结点生成一棵 A Ｖ L树(高度平衡得二叉搜索树)时,当插入到值为 48 得结点时才出现不平衡，需要进行旋转调整。 11．以顺序搜索方法从长度为 n 得顺序表或单链表中搜索一个元素时,其时间复杂度为 Ｏ（ｎ） . 12。在一棵 AVL 树（高度平衡得二叉搜索树）中，每个结点得左子树高度与右子树高度之差得绝对值不超过 1 。 13。在线性表得散列存储...