数据结构习题(5) 学号________ 姓名_______ 课堂号(___________) 1. 选择题 1) 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( A ) A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/2 2) 下面关于二分查找的叙述正确的是 ( D ) A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 B. 表必须有序且表中数据必须是整型，实型或字符型 C. 表必须有序，而且只能从小到大排列 D. 表必须有序，且表只能以顺序方式存储 3) 折半查找的时间复杂性为（ D ） A. O（n2） B. O（n） C. O（nlog(n)） D. O（log(n)） 4) 概率不同的有序表，最适合的查找算法是（ C ） A．顺序查找 B．折半查找 C．静态树表查找 D．索引顺序表查找 5) 平均查找长度最短的查找方法是____C________。 A．折半查找 B.顺序查找 C.哈希查找 4.其他 6) 折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中 A 比较大小，查找结果是失败。 A．20，70，30，50 B．30，88，70，50 C．20，50 D．30，88，50 7) 当采用分快查找时，数据的组织方式为 ( B ) A．数据分成若干块，每块内数据有序 B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块 C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D. 数据分成若干块，每块（除最后一块外）中数据个数需相同 8) 分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( C ) 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) 9) 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（ D ）个记录。 A．1 B. 2 C. 3 D. 4 10) 散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。 （1）元素59存放在散列表中的地址是（ D ）。 A． 8 B. 9 C. 10 D. 11 （2）存放元素59需要搜索的次数是（ C ）。 A． 2 B. 3 C. 4 D. 5 11) 下面给出的...
