中山大学十套数据结构试题及答案_加水印1

数据结构是计算机科学中的核心课程，它研究如何高效地组织和存储数据，以便进行各种操作。本题涉及栈、队列、线性结构、非线性结构、数组、树、二叉树、查找算法、排序算法以及散列表等多个知识点。 1. 栈和队列都是线性数据结构，它们的主要区别在于操作方式。栈遵循“后进先出”（LIFO）原则，而队列遵循“先进先出”（FIFO）原则。共同点是它们都只允许在两端进行插入和删除操作。 2. 链接方式存储的队列，插入运算时，通常需要修改尾指针，因为新元素会被添加到队尾。如果队列为空，可能还需要修改头指针。 3. 非线性结构是指数据元素之间的关系不是简单的线性序列，比如树（包括二叉树）、图等。在提供的选项中，二叉树是非线性结构。 4. 二维数组A[m][n]的存储方式类似于一维数组，可以通过行优先或列优先顺序计算元素位置。已知A[0][0]在644，A[2][2]在676，可以推断出每个元素占4个位置。那么A[3][3]的位置可以通过A[2][2]加上3行3列的偏移量（12个位置）得到，即676 + 12 = 688。 5. 树适合表示元素间具有分支层次关系的数据，例如组织结构、文件系统等。 6. 二叉树的第k层最多有2^(k-1)个节点。 7. 二分查找中，查找A[3]的比较序列下标应该是从中间开始，所以是9，然后根据中间值与目标值的比较结果，逐步缩小范围，最终找到目标，因此下标依次为9，4，2，3。 8. 快速排序的平均时间复杂度为O(n log n)，最好情况为O(n log n)，最坏情况为O(n^2)，但辅助空间复杂度为O(log n)，这里应该是指辅助空间。 9. 散列函数H(K)=K%9，对于线性表（7，34，55，25，64，46，20，10），散列地址1的元素有34和10，共2个。 10. 6个结点的无向图要成为连通图，至少需要5条边。 二、填空题 1. 算法质量的评价通常考虑时间复杂度、空间复杂度、正确性和可读性。 2. 时间复杂度为(n^3+n^2 log2n+14n)/n^2，简化后主要项为n^3，数量级为O(n^3)。 3. 给定的广义表表示的树包含7个结点，深度为3，度为3。 4. 后缀表达式9 2 3 + - 10 2 / - 的值为7，中缀表达式（3+4*）-2/3 对应的后缀表达式为3 4 * 2 - 3 /。 5. n个结点的二叉树有2n个指针域，其中n个存放地址，n-1个为空。 6. 有向图的边结点为e个，无向图的边结点为2e个。 7. AOV网是指活动-on-vertex的图，也就是有向无环图。 8. 无向完全图有n*(n-1)/2条边，有向完全图有n*(n-1)条边。 9. 按Key % 4划分，子表分别为{12, 55}, {23, 40}, {74}, {63}。 10. 插入元素导致B_树根节点分裂，新树高度增加1。 11. 堆排序中，对分支结点进行筛选（heapify）的时间复杂度为O(log n)。 这些题目涵盖了数据结构的基础知识，包括基本概念、操作、算法效率分析等，对于理解和应用数据结构至关重要。