设G是一个用邻接表表示的连通无向图。对于G中某个顶点v，若从G中删去顶点v及与顶点v相关联的边后，G

学1994四(1 8分)】

天大学2005八(10分)】

将a[i]和a[i+1]进行比较，每次比较时若a[i]＞a[i+1]，则将二者交换，以后重复上述二趟过程交换进行，直至整个数组有序。 (1)试问排序结束的条件是什么? (2)编写一个实现上述排序过程的算法。

过查找以后得到各个插入的位置在ki与ki+1之间，则ki+1，…，kn应依次后移一个位置。采用二分插入排序方法能否将查找与后移同时在一个循环中进行?若可以，试写出其算法。

_______算法，最后选取_________算法；若只从排序结果的稳定性考虑，则应选取_________算法，若只从最坏情况下排序要快，并且要节省内存考虑，则选取_________算法。

时，在最好情况下需进行多少次比较?请说明理由。 (2)对n=7，给出一个最好情况的初始排列的实例。

一组记录的排序码为46，79，56，38，40，84，从这个状态出发，用siR算法逐层过筛，建立的堆为________。

A．79，46，56，38，40，80

B．84，79，56，38，40，46

C．4，79，56，46，40，38

D．84，56，79j 40j 46，38

比较次数与排序码的初始排列状态无关的排序算法是__________。

A．直接插入排序

B．冒泡排序

C．快速排序

D．直接选择排序

对n个记录文件进行插入排序，平均比较次数为_________。

A．O(nlog2n)

B．O(n2)

C．O(log2n)

D．O(n)