数据结构考试复习：经典选择题与填空解析

"数据结构经典试题及答案，包含中国人民大学数据结构考试的复习题目，涵盖了数据结构的基础概念、操作及应用。" 以下是基于给定内容提取的数据结构相关知识点： 1. **栈和队列的特点**： - 栈是后进先出（LIFO）的数据结构，只允许在栈顶进行插入（压栈）和删除（弹栈）操作。 - 队列是先进先出（FIFO）的数据结构，允许在队尾进行插入（入队）和队首进行删除（出队）。 2. **链式存储的队列操作**： - 在链式存储的队列中，插入操作通常只修改尾指针，而删除操作可能需要修改头指针和尾指针。 3. **数据结构的线性与非线性**： - 栈、队列和线性表是线性结构，它们的元素之间存在一对一的关系。 - 二叉树是非线性结构，元素间存在分支层次关系。 4. **二维数组的计算**： - 通过给定的数组元素位置，可以推算其他元素的位置。如果每个元素占一个空间，A[2][2]到A[3][3]会间隔4个元素（因为是按行优先存储），所以A[3][3]在676 + 4 = 680（10）的位置。 5. **树的应用**： - 树最适合表示元素之间具有分支层次关系的数据，如组织结构、文件系统等。 6. **二叉树的性质**： - 二叉树的第k层最多有2^(k-1)个节点。 7. **二分查找**： - 二分查找在有序表中进行，查找A[3]的过程可能涉及的比较序列下标为9（中间元素位置），5（中间元素的中间位置），然后是2和3。 8. **快速排序的空间复杂度**： - 快速排序的平均和最好情况下的辅助空间复杂度为O(log2n)，但最坏情况下需要O(n)的空间。 9. **散列存储**： - 使用H(K) = K % 9作为散列函数，散列地址为1的元素是通过取余9来确定的，题目中的线性表中有多个元素的个位数是1，所以可能有多个元素散列到地址1。 10. **连通图的最少边数**： - 为了构建一个连通的无向图，至少需要n-1条边，其中n是图的结点数。所以6个结点至少需要5条边。 11. **算法评价指标**： - 评价算法通常考虑时间复杂度、空间复杂度、正确性和易读性。 12. **时间复杂度表示**： - 时间复杂度表示为(n^3+n^2log2n+14n)/n^2，当n趋向于无穷大时，主要项是n^3，所以数量级表示为O(n^3)。 13. **树的结点数计算**： - 给定广义表表示的树，结点数包括所有子树的结点数。对于树A(C, D(E, F, G), H(I, J))，结点数为1（根结点A）+ 2（子树C和D）+ 3（子树E, F, G）+ 2（子树I, J）= 9。 这些知识点涵盖了数据结构的基本概念，包括栈、队列、树、二叉树、数组、算法效率评估、散列表和图等核心概念。