文档介绍：数据结构第三次单元测验答案一、选择题个元素的表做顺序查找时,若查找每个元素的概率相同,则平均查找长度为() A.( N+1 ) /2 B. N/2 D.[( 1+N ) *N] /2 2. 适用于折半查找的表的存储方式及元素排列要求为() A .链接方式存储,元素无序 B .链接方式存储,元素有序 C .顺序方式存储,元素无序 D .顺序方式存储,元素有序 3. 当在一个有序的顺序存储表上查找一个数据时, 即可用折半查找, 也可用顺序查找, 但前者比后者的查找速度() A .必定快 B. 不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减 4. 有一个长度为 12 的有序表, 按二分查找法对该表进行查找, 在表内各元素等概率情况下查找成功所需的平均比较次数为( )。 A. 35/12 B. 37/12 C. 39/12 D. 43/12 5. 折半查找的时间复杂性为( ) (n 2) (n) ( nlogn ) ( logn ) 6. 对有 18 个元素的有序表作折半查找,则查找 A[3] 的比较序列的下标为( ) ,2,3 ,5,2,3 ,5,3 ,4,2,3 7. 设有序表的关键字序列为{1,4,6, 10, 18, 35, 42, 53, 67, 71, 78, 84, 92, 99} , 当用二分查找法查找健值为 84 的结点时,经( )次比较后查找成功。个键值构造一棵二叉排序树,最低高度为( ) B.、n +1 9 .分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是() A.( 100 , 80, 90, 60, 120 , 110 , 130 ) B.( 100 , 120 , 110 , 130 , 80, 60, 90) C.( 100 , 60, 80, 90, 120 , 110 , 130 ) D.(100 , 80, 60, 90, 120 , 130 , 110) 10. 设有一组记录的关键字为{19 , 14, 23,1, 68, 20, 84, 27, 55, 11, 10, 79} , 用链地址法构造散列表,散列函数为 H( key ) =key% 13, 散列地址为 1 的链中有( )个记录。 11. 已知一采用开放地址法解决 Hash 表冲突,要从此 Hash 表中删除出一个记录,正确的做法是() A. 将该元素所在的存储单元清空。 B. 将该元素用一个特殊的元素代替 C. 将与该元素有相同 Hash 地址的后继元素顺次前移一个位置。 D. 用与该元素有相同 Hash 地址的最后插入表中的元素替代。 12. 假定有 k 个关键字互为同义词,若用线性探测法把这 k 个关键字存入散列表中,至少要进行多少次探测? () A. k-1 次 C. k+1 次 ( k+1 ) /2次 13. 散列表的地址区间为 0-17, 散列函数为 H(K)=K mod 17 。采用线性探测法处理冲突,并将关键字序列 26, 25, 72, 38,8, 18, 59 依次存储到散列表中。(1 )元素 59 存