数据结构试题解析（2002）

"这是一份2002年的数据结构试题，包含单项选择题和问答题，主要测试学生对数据结构的基本概念、逻辑结构、存储结构、操作实现、链表、二叉树、树、图等知识的掌握情况。" 在数据结构这个领域，试题中的各个题目涉及了以下几个关键知识点： 1. 数据结构的研究范围：数据结构不仅关注数据的逻辑结构（如线性结构、树形结构、图形结构等），也包括数据在计算机内存中的存储结构（如顺序存储、链式存储等）以及对这些结构的操作实现。选项D正确地概述了这一概念。 2. 单循环链表空表判断：在带头结点的单循环链表中，如果链表为空，则头结点的next指针应指向头结点自身。因此，选项B "head->next=NULL" 表示链表为空。 3. 双向链表结点插入：在结点p后插入结点q，需要更新p、p的下一个结点和q的相关指针。选项B的代码正确地完成了这个操作，首先将p的next指向q，然后将p的下一个结点的prior指向q，接着设置q的prior为p，最后设置q的next为p的下一个结点。 4. 二叉排序树：二叉排序树是一种特殊的二叉树，其左子树上的所有节点的键值都小于父节点，右子树上的所有节点的键值都大于父节点。如果从任一节点到根的路径上结点的关键字有序，那么它就是二叉排序树。所以选项A正确。 5. 二叉树遍历：在二叉树的遍历中，中序遍历可以得到有序序列。因此，选项B "中序" 是正确的。 6. 树的度：在一个树中，结点的度指的是其子结点的数量。如果结点A有四个兄弟，那么它们的共同父结点B有五个子结点（包括A本身），所以B的度是5，选项C正确。 7. 连通图的最少边数：一个含有n个顶点的连通图至少需要n-1条边来连接所有顶点，形成一棵树。因此，选项A "n-1" 是正确的。 8. 二分查找：对于有序的顺序表，二分查找可以有效地定位元素。在查找72时，需要与4、38、67进行比较，共进行3次比较，因此选项A "3" 是正确的。 9. 数据结构类型：根据给定的关联关系，可以判断这是一个有向图，因为存在从一个顶点到另一个顶点的定向边。选项B "有向图" 正确。 10. 栈的合法操作序列：栈遵循“后进先出”（LIFO）原则。序列A、B和D都符合这一原则，而C序列中，先进行了两次入栈操作，然后立即出栈，导致栈为空，再尝试出栈就会发生错误，因此C序列是不合法的。 以上就是这份试题中涉及的主要数据结构概念和操作，涵盖了数据结构的基础理论和实际操作。