数据结构（B卷）1

数据结构是计算机科学中的核心概念，它涉及到如何高效地组织和操作数据。在这个主题中，我们看到多个关于数据结构和算法的问题。 1. 单项选择题的第一题问及算法必须具备的三个特性，答案是B，即可执行性、确定性和有穷性。这三个特性确保了一个算法是可以被计算机理解并有限时间内执行完毕的。 2. 第二题提到非线性数据结构，选项C的完全二叉树是非线性的，因为它不是简单的线性序列，而是具有分枝的结构。 3. 算法分析关注的是时间和空间复杂度，选项A正确。这两个度量分别衡量算法运行时间和所需的内存空间。 4. 对于非空循环单链表，如果head是头结点，那么尾结点p满足p->next==head，表示链表的最后一个节点指向头节点，形成循环。 5. 在单链表中插入节点，正确做法是B，即将新节点s链接在p之后，然后更新p的next指针。 6. 具有3个结点的二叉树有5种可能形态，包括线性、分支和叶节点的组合。 7. 在有向图中，所有顶点的入度之和等于出度之和，因为每条边都有一个起点和终点。 8. 二叉排序树是中序遍历得到升序序列的二叉树，B选项正确。 9. 循环队列的处理，根据题目描述，删除一个元素后再加入两个元素，rear和front会变成2和4。 10. 正确的说法是C，队列是一端操作、先进先出（FIFO）的线性表。 11. 不带头结点的单链表为空的判定条件是head==NULL。 12. 森林转化为二叉树，根结点的右子树结点个数为第三棵树的结点个数M3。 13. 一个二叉树的叶子结点数是度为2的结点数加1的减1，所以10个叶结点的二叉树有9个度为2的结点。 14. 哈夫曼树的结点总数为2n-1，其中n是叶子结点的数量。 15. 利用二叉链表存储树，根结点的右指针通常是空的，表示根结点没有右孩子。 16. 深度优先遍历无向图，从V0出发可能的序列是B。 17. 要连通具有n个顶点的无向图，最少需要n-1条边。 18. 二分查找要求线性表必须以顺序方式存储且结点关键字有序排列。 19. 静态查找表和动态查找表的区别在于存储实现，静态表在创建后大小固定，而动态表可以随需改变大小。 20. 有n个顶点的有向图最多有n(n-1)条边，因为每个顶点可以指向其他任何顶点。 判断对错： 1. 正确，连通图至少有n条边，确保每个顶点与其他所有顶点相连。 2. 错误，虽然A2的时间复杂度更高，但在n较小的情况下，A1可能更快，需要综合考虑实际应用。 3. 正确，链表的节点可以不连续，这是链式存储的特点。 4. 完全二叉树中，没有左孩子的节点可能是叶节点或根节点。 以上是对题目中涉及的各个知识点的详细解释，涵盖了算法基础、数据结构特性和操作，以及图论和查找方法等多个领域。