09年408真题解析6～10题

选B：

选A。

I 每条边贡献2度。

II 边数最少n-1，最多n（n-1）/2，大于等于

III 可以没有

选D，D是B+树

选A。

冒泡排序： 从左到右两两相邻比较，如果左边 > 右边就交换，每一轮把当前最大的数一步步“冒”到末尾，重复直到整个数组有序。第二趟排序后前面为最小值，或者后面为最大值。错误。

插入排序：分为已排序区域和待排序区域，把未排序区域的第一个元素与已排序区域做比较，插入到比该元素小的位置，插入到已排序区域的正确位置，使已排序部分始终有序。重复该过程，使所有元素排列正确。第二趟排序后，已排序区域是有序的，但不一定是最值。

选择排序：分为已排序区域和待排序区域，选择待排序区域最小的元素与已排序区域交换。第二趟排序后，已排序区域是最值。

归并排序：递归拆分，有序合并。第二趟排序后，头四个位数有序。

• 冒泡排序：每一趟把当前最大元素移到末尾，第 k 趟后末尾 k 个元素是全局最大的 k 个，且已有序。

• 插入排序：第 k 趟后前 k+1 个元素已有序。

• 选择排序：第 k 趟后前 k 个元素是全局最小的 k 个，且已有序。

• 归并排序：第 k 趟后长度为 2^k 的子数组已有序。

选B。