09年408真题解析6～10题

选B选A。I 每条边贡献2度。II 边数最少n-1最多nn-1/2大于等于III 可以没有选DD是B树选A。冒泡排序 从左到右两两相邻比较如果左边 右边就交换每一轮把当前最大的数一步步“冒”到末尾重复直到整个数组有序。第二趟排序后前面为最小值或者后面为最大值。错误。插入排序分为已排序区域和待排序区域把未排序区域的第一个元素与已排序区域做比较插入到比该元素小的位置插入到已排序区域的正确位置使已排序部分始终有序。重复该过程使所有元素排列正确。第二趟排序后已排序区域是有序的但不一定是最值。选择排序分为已排序区域和待排序区域选择待排序区域最小的元素与已排序区域交换。第二趟排序后已排序区域是最值。归并排序递归拆分有序合并。第二趟排序后头四个位数有序。• 冒泡排序每一趟把当前最大元素移到末尾第 k 趟后末尾 k 个元素是全局最大的 k 个且已有序。• 插入排序第 k 趟后前 k1 个元素已有序。• 选择排序第 k 趟后前 k 个元素是全局最小的 k 个且已有序。• 归并排序第 k 趟后长度为 2^k 的子数组已有序。选B。