数据结构练习3答案.doc

数据结构练习3主要涉及了数据结构中的搜索算法及其性能分析，包括线性表、二分查找、分块查找、平衡二叉树、B-树和B+树、哈希表等多种数据结构和查找方法。以下是对各个题目知识点的详细解释： 1. 顺序查找法适合于任何存储结构的线性表，包括顺序存储和链式存储。 2. 在长度为100的已排序表中，最坏情况下二分查找不成功需要比较9次（每次比较排除一半）。 3. 顺序查找法的平均比较次数是（n+1）/2。 4. 二分查找要求线性表以顺序方式存储且按关键字有序排列。 5. 二分查找法的平均查找长度为O(log2n)。 6. 对于长度为12的有序表，采用折半查找，平均比较次数为37/12。 7. 折半查找法查找82，由于82位于中间位置，所以比较2次即可找到。 8. 分块查找时，数据分为若干块，每块数据不必有序，但块间必须有序，每块最大(或最小)的数据组成索引块。 9. 最佳情况下，分块查找每块应该有25个结点，这样查找效率最高。 10. 二叉排序树的构建规则决定了选项A、B、C能生成，但D不能。 11. 二叉排序树的中序遍历可以得到递增或递减的键值序列。 12. 平衡二叉树中，每个结点的平衡因子范围是-1到1。 13. 5层结点的AVL树至少有12个结点（包括空结点）。 14. 在平衡二叉树上查找28，可能的路径是C选项。 15. 深度为k且非叶子结点平衡因子为0的平衡二叉树，结点总数为2k-1。 16. 查找效率最高的二叉排序树是平衡二叉树。 17. B-树和B+树都不能有效地支持顺序查找，因为它们设计的目标是随机查找和磁盘I/O优化。 18. 哈希查找法的平均查找长度与哈希函数和处理冲突的方法有关，这里没有具体信息，无法确定。 19. 散列到大量空单元的哈希表仍可能出现冲突。 20. 二次探测再散列处理冲突，49%11=7，但7已被占用，所以继续探测8、19...直到找到空位，这里是9。 21. 线性探测再散列法存储k个同义词，至少要探查k次。 22. 链地址法需要17个链表，数组下标范围为0-16。 23. 直接插入排序在最好情况（输入已排序）下的时间复杂度为O(n)。 24. 稳定的排序算法包括直接插入排序。 以上是针对数据结构练习3中各题目的详细解析，涵盖了多种数据结构和算法的基本概念及特性。这些知识对于理解和应用数据结构至关重要。