数据结构复习题-第9章答案2014-6-16

1、若查找每个元素的概率相同，则平均查找长度为C. ND. （ 1+N ） *N /2n的顺序表时，搜索成功的平均搜索长度为（D.（ n+1）/2A )°3. 当在一个有序的顺序存储表上查找一个数据时，既可用折半查找，也可用顺序查找，但前 者比后者的查找速度（C ）。A.必定快C.在大部分情况下要快B.不一定D.取决于表递增还是递减（D4. 适用于折半查找的表的存储方式及元素排列要求为A.链接方式存储，元素无序C.顺序方式存储，元素无序5. 采用折半搜索算法搜索长度为A. O （n2）B. O （nlog 2n）6. 折半查找有序表（4，6，10， 它将依次与表中（AA. 20，70，3

2、0，507. 对二叉排序树进行（A.前序B.中序B.链接方式存储，元素有序D.顺序方式存储，元素有序n的有序表时，元素的平均搜索长度为（C. O （ log 2n） D. O （n）12，20，30，50，70，88，100）。若查找表中元素C )°58,则8. 下列二叉排序树中，满足平衡二叉树定义的是（）比较大小，查找结果是失败。B. 30，88，70，50C. 20，50 D. 30，88，50B ）遍历，可以得到关键字的有序序列。C.后序D.层次B)°第9章查找一、选择题（每小题 1分，共10分）1. 对长度为N的表做顺序查找时，A. （ N+1）12B. N/22.

3、 采用顺序搜索方法查找长度为A.n B. n/2C.（ n-1）/29. 链表适用于（ A ）查找A.顺序B.二分法C.顺序，也能二分法D.随机10. 以下说法错误的是（ B ） °A. 散列法存储的基本思想是由关键码值决定数据的存储地址B. 散列表的结点中只包含数据元素自身的信息，不包含任何指针C. 负载因子是散列表的一个重要参数，它反映了散列表的饱满程度D. 散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法11 有一个有序表为 1，3，9，12，32，41，45, 62，75，77，82，95，100，当折半查 找值为82的结点时，（C ）次比较后查找成功。A

4、.11B 5C 4 D 812. 查找效率最高的二叉排序树是（C ）°A.所有结点的左子树都为空的二叉排序树。B.所有结点的右子树都为空的二叉排序树。C.平衡二叉树。 D.没有左子树的二叉排序树。13. 有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素等概率的情况下查找成功所需的平均比较次数为（B ）°A. 35/12B 37/12C 39/12 D43/12二、判断题（每小题 1分，共10分）1顺序查找方法只能在顺序存储结构上进行。（错）2二叉排序树删除一个叶子结点后，仍是二叉排序树。（对）3在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面

5、。（对）4在二叉排序树中，新结点总是作为叶子结点来插入。（对）5.Hash表的平均查找长度与处理冲突的方法无关。（错）6哈希表的查找效率主要取决于哈希表造表时选取的哈希函数和处理冲突的方法。（对 ）7对线性表进行折半查找时，要求线性表必须以链式方式存储，且结点按关键字有序排列。（X ）8散列法存储的思想是由关键字值决定数据的存储地址。（V ）9二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右 孩子的值。（X ）10直接选择排序算法在最好情况下的时间复杂度为0（n）。（X ）11. 二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右 孩子的值

6、。（X ）三、填空题（每空1分，共10分）1折半查找的时间复杂性为 。log 2n2. 设h是一哈希函数，key1和key2为关键码值，且 key1丰key2，但h （key1） =h （key2）,这种现象称为。冲突3. 顺序查找不要求关键字 ，其ASL（平均查找长度）为;折半查找要求关键字，其ASL为。有序O（n）有序 问4. 平衡二叉排序树上任一结点的平衡因子只可能是 、或。-1, 0, 1四、简答题1. 叙述什么是二叉排序树？答：二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：（1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值；（2）若它的右子树不空，则右子树上所有结

7、点的值均大于根结点的值；（3）它的左、右子树也都分别是二叉排序树。二叉排序树又称二叉查找树。2. 什么是平衡二叉树（AVL树）？答：平衡二叉树又称 AVL树，它或是一棵空树，或是具有下列性质的树：它的左子树和右 子树均是平衡二叉树，且左子树和右子树的深度之差绝对值不超过1。3. 为什么有序的单链表不能进行折半查找？答：因为链表无法进行随机访问， 如果要访问链表的中间结点， 就必须先从头结点开始进行 依次访问，这就要浪费很多时间，还不如进行顺序查找，而且，用链存储结构将无法判定二分的过程是否结束，因此无法用链表实现二分查找。五、应用题无答案六、算法题1. （ 6分）编写折半查找算法。答案一：in

8、t Search_Bin ( SSTable ST, KeyType key ) low = 1; high = ST.length; / 置区间初值while (low <= high) mid = (low + high) / 2;if ( EQ (key , ST.elemmid.key) ) return mid; / 找到待查元素else if ( LT (key , ST.elemmid.key) )high = mid - 1; / 继续在前半区间进行查找 else low = mid + 1;/ 继续在后半区间进行查找return 0; / 顺序表中不存在待查元素 / S

9、earch_Bin答案二：int Locate_Bin(SSTable ST,int key)int *r; r=ST.elem; if(key<r .key) return 0;else if(key>=rST.length.key) return ST.length; low=1;high=ST.length; 1 分 while(low<high) mid=(low+high)/2; if(key>=rmid.key&&key<rmid+1.key) return mid; 3 分 else if(key<rmid.key) high=

10、mid-1;else low=mid+1; 6 分 2. (6 分)编写顺序查找算法。答案一：int Search_Seq( SSTable ST , KeyType key )/ 在顺序表 ST 中，查找关键字与 key 相同的元素；若成功，返回其位置信息，否则返回 0 ST.elem0.key =key; / 设立哨兵 for( i=ST.length; ST.elem i .key!=key; - - i ) ;return i; / 查找不成功，返回 0 值 (i=0) 。 成功时则返回找到的那个元素的位置 i 。 / Search_Seq 答案二： int Search_Seq(SSTable ST, KeyType key)int i;for(i=1; i<=ST.length ; i+ );if(k=ST.elemi.key)return i