2010广东工大数据结构试题B：关键知识点与解题技巧

本资源是一份2010年广东工业大学数据结构课程的B卷考试试题，涵盖了多项选择题和可能涉及的知识点。以下是详细解读： 1. **存储结构的选择**：题目1询问在频繁进行存取指定元素和末尾操作的情况下，哪种存储方式最节省时间。顺序表由于连续存储，存取速度较快，因此对于这类操作较为适合，答案是A - 顺序表。 2. **广义表的理解**：第二题涉及广义表的概念。选项A错误，因为表头为空的广义表并不意味着它是空表；B正确，广义表可以共享；C正确，表尾可以是原子或子表；D是关于矩阵压缩存储，但这里没有给出具体条件，所以不能断言只需存储一半元素。 3. **二叉树的空链域**：第三题关注二叉树的链接表示。对于n个节点的二叉树，无论是否是完全二叉树，最坏情况下每个节点都可能有一个前驱和一个后继，所以总的空链域数为2n-1，答案是D。 4. **遍历顺序与树的性质**：第四题涉及先序遍历和二叉树的关系。选项C正确，先根遍历和中序遍历转换后的二叉树的顺序相反，而(2)是二叉树的先序遍历特性，即父节点在子节点之前。 5. **循环队列操作**：第五题考察队列的基本操作。在给定的队列中，删除一个元素、加入两个元素后，front会后移一位，但由于队列长度固定为6，front不会超过rear，所以rear变为front+2取模，答案是B - 2和4。 6. **图的度数**：第六题涉及有向图中顶点的最大度数。在一个有N个顶点的图中，每个顶点最多可以有一条指向每个其他顶点的边，加上出度本身，度最大为N-1，因此答案是B - 2(N-1)。 7. **存储结构类型**：第七题描述了数据结构与地址映射的关系，这里的“映射关系”对应于索引或哈希，答案是D - 索引存储结构，因为它涉及到通过键值找到存储地址。 8. **折半查找**：最后，第八题提到了折半查找，这是一种高效的搜索算法，用于已排序的列表中查找特定元素。题目给出了部分有序表，包括元素2, 5, 8, 20, 25, 36, 40，但没有完成。 这些题目涵盖了数据结构中的基本概念，如存储结构、图论、广义表、遍历、队列和查找算法等，是数据结构课程学习的重要组成部分。