2018年4月自考数据结构导论：知识点与习题详解

在2018年4月的高等教育自学考试全国统一命题的《数据结构导论》试卷中，包含了丰富的理论和实践题型。本卷旨在考察学生对数据结构基础知识的理解和应用能力。 14. 题目讨论的是散列函数的设计，其中提到的散列函数H(k)=k MOD m通常用于将关键字k映射到一个较小的范围内。选项中，选择一个足够大的素数（C）作为m有利于减少冲突（两个不同的关键字映射到同一个哈希地址），因为素数的分布更均匀，能提供更好的哈希性能。 15. 排序算法的选择题中，A. 堆排序通常需要较少的辅助空间，因为它只需要一个固定大小的堆；B. 快速排序在平均情况下表现良好，但最坏情况下的辅助空间复杂度较高；C. 直接选择排序在内部循环过程中不需要额外的辅助空间；D. 归并排序需要额外的存储空间来合并两个已排序的子序列，因此所需辅助存储量最多。因此，答案是D. 归并排序。 **填空题部分** 16. 在线性表中，除了第一个结点（起始结点）没有直接前驱，其他结点每个都只有一个直接前驱，体现了线性表的单向链接特性。 17. 单链表中的结点在内存中并非物理上连续存储，它们通过指针相连。 18. 栈初始化的目的是确保栈为空，为后续的操作如入栈（E）做准备，保证数据的正确性和顺序。 19. 通过给出的操作序列，我们可以推断出栈的特性。E表示入栈，O表示出栈。输入序列a, b, c, d, e经过一系列操作后，栈中最后出栈的元素是第一个入栈的，所以输出序列应该是原始输入的逆序，即e, d, c, b, a。 20. 二叉树的定义要求每个节点最多有两个子节点，且子树之间不存在交叉关系，而是具有左右子树的结构性质。 21. 树的高度定义为从根节点到最远叶子节点的最长路径，高度为h的树至少有2^(h-1)个叶子节点。 22. 完全二叉树的高度与叶子节点数量有关，对于高度为h的树，最少的叶子节点数为2^(h-1)。 23. 广度优先搜索（BFS）是图的遍历策略，它按照层次顺序访问节点，类似树的层次遍历。 24. 稀疏矩阵由于非零元素较少，可以采用压缩存储方法，如压缩行存储（Compressed Row Storage, CRS）或压缩列存储（Compressed Column Storage, CCS）。 25. 拓扑排序的前提是AOV网（有向无环图）中不存在回路，即不存在循环依赖关系。 26. 散列函数是将数据元素的关键字（键值）映射到一个唯一的哈希值，这对应关系可以理解为数据元素与其哈希索引之间的函数关系。 27. 静态查找表（Static Search Table）不包含插入和删除操作，仅用于查找已经存在的元素。 28. 对于按递增顺序排序，堆排序的时间复杂度为O(n log n)，而快速排序、冒泡排序和归并排序在最好情况下都是O(n log n)，但在实际应用中，堆排序因为其原地操作（In-place）的特点，在处理部分有序的数据时效率更高，所以答案是堆排序。 这份试卷主要考察了数据结构的基本概念，如散列函数、排序算法、线性表、树和图的性质，以及查找和排序算法的性能比较等。解答这些题目不仅需要扎实的理论基础，还需要一定的分析和实践能力。