?????????? ??????????γ???????????? - ??????

答题： A. B. C. D. （已提交） 参考答案：C 问题解析： 6. 要进行线性查找，则线性表 a ；要进行二分查找，则线性表 b ；要进行散列查找，则线性表 c 。 某顺序存储的表格，其中有90000个元素，已按关键项的值的上升顺序排列。现假定对各个元素进行查找的概率是相同的，并且各个元素的关键项的值皆不相同。当用顺序查找法查找时，平均比较次数约为 d ，最大比较次数为 e 。 供选择的答案： A~C：① 必须以顺序方式存储 ② 必须以链表方式存储 ③ 必须以散列方式存储 ④ 既可以以顺序方式，也可以以链表方式存储 ⑤ 必须以顺序方式存储且数据元素已按值递增或递减的次序排好 ⑥ 必须以链表方式存储且数据元素已按值递增或递减的次序排好 D，E： ① 25000 ② 30000 ③ 45000 ④ 90000 A. a=4,b=5,c=3,d=4,e=3 B. a=4,b=5,c=1,d=3,e=4 C. a=4,b=3,c=5,d=1,e=4 D. a=4,b=5,c=3,d=3,e=4 答题： A. B. C. D. （已提交） 参考答案：D 问题解析： 7. 数据结构反映了数据元素之间的结构关系。链表是一种 a ，它对于数据元素的插入和删除 b 。通常查找线性表数据元素的方法有 c 和 d 两种方法，其中 c 是一种只适合于顺序存储结构但 e 的方法；而 d 是一种对顺序和链式存储结构均适用的方法。 供选择的答案： a：①顺序存储线性表 ②非顺序存储非线性表 ③顺序存储非线性表 ④非顺序存储线性表 b：① 不需要移动结点，不需改变结点指针 ②不需要移动结点，只需改变结点指针 ③只需移动结点，不需改变结点指针 ④既需移动结点，又需改变结点指针 c：① 顺序查找 ②循环查找 ③条件查找 ④二分法查找 d：① 顺序查找 ②随机查找 ③二分法查找 ④分块查找 e：① 效率较低的线性查找 ②效率较低的非线性查找 ③ 效率较高的非线性查找 ④效率较高的线性查找 A. a=4,b=1,c=4,d=1,e=3 B. a=4,b=2,c=4,d=1,e=3 C. a=3,b=2,c=4,d=1,e=4 D. a=4,b=1,c=3,d=1,e=3 答题： A. B. C. D. （已提交） 参考答案：B 问题解析： 8. 在二叉排序树中，每个结点的关键码值 a ， b 一棵二叉排序，即可得到排序序列。同一个结点集合，可用不同的二叉排序树表示，人们把平均检索长度最短的二叉排序树称作最佳二叉排序，最佳二叉排序树在结构上的特点是 c 。 供选择的答案 a： ①比左子树所有结点的关键码值大，比右子树所有结点的关键码值小 ②比左子树所有结点的关键码值小，比右子树所有结点的关键码值大 ③比左右子树的所有结点的关键码值都大 ④与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的大小关系 b： ①前序遍历 ② 中序（对称）遍历 ③ 后序遍历 ④ 层次遍历 c： ① 除最下二层可以不满外，其余都是充满的 ②除最下一层可以不满外，其余都是充满的 ③ 每个结点的左右子树的高度之差的绝对值不大于1 ④ 最下层的叶子必须在最左边 A. a=4,b=1,c=4 B. a=2,b=1,c=3 C. a=1,b=2,c=2 D. a=2,b=1,c=4 答题： A. B. C. D. （已提交） 参考答案：C 问题解析： 9. 散列法存储的基本思想是根据 a 来决定 b ，碰撞（冲突）指的是 c ，处理碰撞的两类主要方法是 d 。 供选择的答案 a，b： ①存储地址 ② 元素的符号 ③ 元素个数 ④ 关键码值 ⑤ 非码属性 ⑥ 平均检索长度 ⑦ 负载因子 ⑧ 散列表空间 c： ①两个元素具有相同序号 ② 两个元素的关键码值不同，而非码属性相同 ③ 不同关键码值对应到相同的存储地址 ④ 负载因子过大 ⑤ 数据元素过多 d： ① 线性探查法和双散列函数法 ② 建溢出区法和不建溢出区法 ③ 除余法和折叠法 ④ 拉链法和开地址法 A. a=4,b=1,c=4,d=1 B. a=2,b=1,c=3,d=4 C. a=4,b=1,c=3,d=4 D. a=2,b=1,c=4,d=1 答题： A. B. C. D. （已提交） 参考答案：C 问题解析： 10. 考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值。并小于等于其右子树上的一切结点的值。 现把9个数1，2，3，…，8，9填入右图所示的二叉树的9个结点中，并使之具有上述性质。此时，n1的值是 a ，n2的值是 b ，n9的值是 c 。现欲把放入此树并使该树保持前述性质，增加的一个结点可以放在 d 或 e 。 供选择的答案 a～c： ①1 ② 2 ③ 3 ④ 4 ⑤ 5 ⑥ 6 ⑦ 7 ⑧ 8 ⑨ 9 d～e： ① n7下面 ② n8下面 ③ n9下面 ④ n6下面 ⑤ n1与n2之间 ⑥ n2与n4之间 ⑦ n6与n9之间 ⑧ n3与n6之间 A. a=7,b=4,c=6,d=2,e=6 B. a=6,b=4,c=6,d=2,e=6 C. a=7,b=4,c=6,d=2,e=4 D. a=7,b=4,c=5,d=2,e=6 答题： A. B. C. D. （已提交） 参考答案：A 问题解析： 11. 采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。( ) 答题： 对. 错. （已提交） 参考答案：√ 问题解析： 12. 在散列检索中，“比较”操作一般也是不可避免的。( ) 答题： 对. 错. （已提交） 参考答案：√ 问题解析： 13. 散列函数越复杂越好，因为这样随机性好，冲突概率小。( ) 答题： 对. 错. （已提交） 参考答案：× 问题解析： 14. 哈希函数的选取平方取中法最好。( ) 答题： 对. 错. （已提交） 参考答案：× 问题解析： 15. Hash表的平均查找长度与处理冲突的方法无关。( ) 答题： 对. 错. （已提交） 参考答案：× 问题解析： 16. 负载因子 (装填因子)是散列表的一个重要参数，它反映散列表的装满程度。( ) 答题： 对. 错. （已提交） 参考答案：√ 问题解析： 17. 散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。( ) 答题： 对. 错. （已提交） 参考答案：√ 问题解析： 18. 哈希表的结点中只包含数据元素自身的信息，不包含任何指针。 ( ) 答题： 对. 错. （已提交） 参考答案：× 问题解析： 19. 若散列表的负载因子α<1，则可避免碰撞的产生。 ( ) 答题： 对. 错. （已提交） 参考答案：× 问题解析： 20. 查找相同结点的效率折半查找总比顺序查找高。( ) 答题： 对. 错. （已提交） 参考答案：× 问题解析： 21. 用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。( ) 答题： 对. 错. （已提交） 参考答案：× 问题解析： 22. 在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。( ) 答题： 对. 错. （已提交） 参考答案：√ 问题解析： 23. 顺序查找法适用于存储结构为顺序或链接存储的线性表。( ) 答题： 对. 错. （已提交） 参考答案：√ 问题解析： 24. 折半查找法的查找速度一定比顺序查找法快 。( ) 答题： 对. 错. （已提交） 参考答案：× 问题解析： 25. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。( ) 答题： 对. 错. （已提交） 参考答案：× 问题解析： 26. 对无序表用二分法查找比顺序查找快。( ) 答题： 对. 错. （已提交） 参考答案：× 问题解析： 27. 对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。( ) 答题： 对. 错. （已提交） 参考答案：√ 问题解析： 28. 任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间。( ) 答题： 对. 错. （已提交） 参考答案：× 问题解析： 29. 最佳二叉树是AVL树（平衡二叉树）。( ) 答题： 对. 错. （已提交） 参考答案：√ 问题解析： 30. 在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面。( )