数据结构与算法：排序与图遍历

"数据结构与算法相关的选择题集" 这些题目涵盖了数据结构和算法的一些核心概念，主要包括排序算法、时间复杂度分析、数据结构的操作以及图论和树的相关知识。 1. 归并排序的时间复杂度是O(nlog2n)，选项B。归并排序是一种分治策略的排序算法，其平均和最坏情况下的时间复杂度都是线性对数级。 2. 二分查找的时间复杂度是O(log2n)，选项D。二分查找适用于有序列表，每次查找都将搜索范围减半，因此时间复杂度较低。 3. 图的广度优先搜索(BFS)使用的数据结构是队列，选项A。BFS按照从起点到终点的层次顺序遍历图中的节点。 4. 冒泡排序是一种比较简单的排序算法，第一次执行交换后，序列可能未完全排序，选项D描述了可能的一种情况。 5. 单链表中，指针域通常指向该结点的直接后继，选项B。这样可以实现对链表的遍历。 6. 在单链表尾部插入新节点的时间复杂度是O(1)，选项A。因为只需要修改最后一个节点的指针即可。 7. 链队列执行入队操作时，通常在链表尾部进行，选项D。入队操作不会涉及队列是否为空或满的判断。 8. 二路归并排序的第一阶段是将两个已排序的子序列合并，选项C给出了正确的中间结果。 9. 二叉树的第i层最多有2^(i-1)个节点，选项C。这是满二叉树的性质。 10. 要删除单链表中节点A的直接后继，需要将A的next指针指向后继节点的下一个节点，选项A。 11. 直接插入排序在每趟结束后，至少能将一个元素放到其最终位置，而选项C的排序算法，即直接插入排序，每一趟可能无法确保这一点。 12. 哈夫曼树的带权路径长度等于所有叶子节点的权重乘以其到根节点的距离之和，计算得到答案是44，选项C。 13. 有n个顶点的有向完全图的弧数是每一对顶点之间都有一个弧，所以弧数为n(n-1)，选项C。 14. 无向完全图G有n个结点，每对不同的结点间有一条边，所以边数为n(n-1)/2。 这些题目体现了数据结构和算法学习的基础知识，包括排序算法的性能分析、数据结构（如链表、队列、二叉树）的操作，以及图论的基本概念。掌握这些知识点对于理解和解决问题至关重要。