数据结构期末考试要点回顾：非线性与链表操作

一、数据结构类型 1. 非线性数据结构： 在给出的选择题中，栈和队列属于线性数据结构，因为它们都遵循先进先出(FIFO)或后进先出(LIFO)的原则，节点之间存在线性的关系。而字符串(串)虽然看似一维，但本质上是线性结构，因为它可以通过索引访问每个字符，形成连续的逻辑顺序。相比之下，树是一种非线性数据结构，因为它的节点可以有任意数量的子节点，形成分支结构，每个节点与父节点之间的路径可能不同。 2. 单链表判断空表： 判定一个带头结点的单链表为空表的条件是`head->next==NULL`。这是因为头结点的下一个节点通常是第一个实际的数据节点，如果这个指针为NULL，说明链表中没有后续元素，即为空表。 3. 单链表插入操作： 要在链表中指针`q`和`p`之间插入指针`s`，正确的操作是`q->next=s;s->next=p`，这样保持了原有的链接关系，并将`s`插入到`p`之前。 4. 单链表删除操作： 删除`p`所指结点时，考虑到`q`是`p`的前驱，应先更新`q`的`next`指向`p`的下一个节点，然后释放`p`，所以正确操作是`q->next=p->next; free(p)`。 二、栈和队列应用及性质 5. 循环队列与出栈序列： 循环队列的出队操作不会导致出栈序列出现问题，选项XYZD都是可能的序列，而C.ZXY由于先出栈Z，再出栈X，不符合先进先出原则。 6. 循环队列操作： 入队操作对于循环队列来说，需要确保索引不会超出数组范围，所以`rear=(rear+1)%m`是正确的。 7. 栈的应用： 栈的应用包括递归调用、括号匹配检验、表达式求值，而图的广度优先搜索遍历通常使用邻接矩阵或邻接表实现，不是典型栈操作。 8. 图论概念： A.连通图的生成树是一棵包括所有顶点且无环的子树，不一定是最大连通子图。B.有向无环图(DAG)的拓扑排序可能存在多个序列，只要它们符合顶点的入度依赖关系。C.广度优先搜索(BFS)是基于队列的算法，不是递归过程。D.在各边权值均不相同的情况下，连通图的最小生成树是唯一的，Kruskal's或Prim's算法可以找到唯一解。 9. 二叉树的性质： 树的度数、节点分布和叶子节点的关系可以计算，给定树T的度为4，叶子节点总是度为0的节点，根据题目信息，度为1、2、3的节点共7个，因此叶子节点数为总节点数减去度数之和，即`n = 4 + 2 + 1 + 1 - (4*4 + 2*2 + 1*1) = 7 - 19 = -12`，显然是错误的。可能是题目描述有误，或者缺失了度为4的叶子节点的信息。 综上，这部分内容主要涉及了数据结构中的链表操作，栈和队列的区别，以及图论和二叉树的基础概念，其中可能存在一些错误或不完整的信息，需要进一步确认。