第七章测试1.
有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当用二分法查找值82的结点时,()次比较后查找成功。
A:4 B:8 C:1
D:2
答案:A
2.
若根据查找表建立长度为 m 的哈希表,采用线性探测法处理冲突,假定对一个元素第一次计算的哈希地址为 d,则下一次的哈希地址为( )。
A:d+1
B:(d+1)/m C:(d+1)%m D:d 3.
若根据查找表(23,44,36,48,52,73,64,58)建立哈希表,采用 h(K)=K%13 计算哈希地址,则元素 64 的哈希地址为( )。
A:13 B:12 C:4 D:8 4.
从具有 n 个结点的二叉排序树中查找一个元素时,在最坏情况下的时间复杂度为( )。
A:O(logn) B:O(n^2) C:O(1) D:O(n) 5.
对具有 n 个元素的有序表采用折半查找,则算法的时间复杂度为( )。
A:O(n) B:O(n^2) C:O(1) D:O(logn) 6.
对于长度为 18 的顺序存储的有序表,若采用折半查找,则查找第 15 个元素的比较次数为( )。
A:6 B:3 C:4 D:5 7.
二叉排序树的左右子树都是二叉排序树。
A:错 B:对 8.
若查找每个元素的概率相等,则在长度为 n 的顺序表上查找任一元素的平均查找长度为( )。
A:n+1 B:(n+1)/2 C:n D:(n-1)/2 9.
具有12个关键字的有序表,折半查找的平均查找长度是()。
A:4 B:2.5 C:5 D:3.1 10.
下面关于哈希查找的说法正确的是()。
A:除留余数法是所有哈希函数中最好的 B:不存在特别好和特别坏的哈希函数,要视情况而定 C:哈希函数构造的越复杂越好,因为这样随机性好,冲突小 D:若需要在一个哈希表中删去一个元素,不管何种方法解决冲突都只要将该元素删去即可 11.
将10个元素散列到长度为100000的哈希表中,则()产生冲突。
A:一定会 B:一定不会 C:仍可能会 12.
完全二叉树肯定是平衡二叉树。
A:错 B:对 13.
查找n个元素的有序表时,最有效的查找方法是()。
A:折半查找 B:分块查找 C:二叉排序树 D:顺序查找 14.
当在一个有序顺序存储表中查找一个数据时,既可用折半查找,也可以用顺序查找,但前者比后者的查找速度()。
A:一定慢
B:大部分情况下快 C:一定快 D:取决于表递增还是递减 15.
有n个数据存在在一维数组a中,进行顺序查找时,这n个数据的排列有序或无序其平均查找长度不同。
A:错 B:对 16.
n个结点的二叉排序树有多种形态,其中高度最小的二叉排序树是最佳的。
A:对 B:错 17.
假定有k个关键字互为同义词,若用线性探测法把这k个关键字存入哈希表中,至少要进行()次探测。
A:k+1 B:k-1 C:k(k+1)/2 D:k 18.
对包含N个元素的哈希表进行查找,平均查找长度为
A:O(N) B:O(1) C:不确定 D:O(logN) 19.
含有25个结点的二叉排序树上,查找关键字为35的结点,则依次比较的关键字序列有可能是
A:18,36,28,46,35 B:46,36,18,28,35 C:46,28,18,36,35 D:28,36,18,46,35