数据结构11 DFS&Insert Sort_after the first run of insertion sort, it is possi

DFS

按照深度优先遍历一张图

无向图：

input:源点根V

1.visit[V]=True

2.对于所有与V邻接的点，if ( !visited[ W ] )     DFS( W );

 复杂度为O(E+V)

articulation point：删除后联通分量会增加

biconnected graph ：G是联通的，且没有衔接点

biconnected component：最大的双连通子图

寻找衔接点：

1.使用DFS生成树，但是不在树中的边需要用虚线加入到树中（back edge）

2.根节点是连接点：至少有两个孩子

3.其他结点是连接点：从该结点往下走不能回到祖先。（孩子中没有后继边）

 Num(u):该结点的编号，对应生成树时的顺序。Num(root)=0

Low(u)=min{Num(u),Low(any u's child),Low(u),w和v用后继边相连。}

算法2：

1.使用DFS生成树

2.计算num和Low

3.根是连接点：至少有两个孩子

4.非根节点是连接点：有一个孩子：Low(child)>Num(u)

插入排序

void InsertionSort ( ElementType A[ ], int N ) 
{ 
      int  j, P; 
      ElementType  Tmp; 
 
      for ( P = 1; P < N; P++ ) { 
	    Tmp = A[ P ];  /* the next coming card */
	for ( j = P; j > 0 && A[ j - 1 ] > Tmp; j-- ) 
	      A[ j ] = A[ j - 1 ]; 
	      /* shift sorted cards to provide a position 
                       for the new coming card */
	    A[ j ] = Tmp;  /* place the new card at the proper position */
      }  /* end for-P-loop */
}

总是将有序数组的后一个元素插入到有序数组中。

有序数组从一个元素开始。

最坏情况：逆序O(N^2)

最好情况：顺序O(N)

平均情况：O(N^2)

inversion:两个元素的位置是逆序的。

有几个逆序对就需要交换几次，若有I个逆序对,时间复杂度为O(N+I)

题目

1.For a graph, if each vertex has an even degree or only two vertexes have odd degree, we can find a cycle that visits every edge exactly once

欧拉环的条件是所有点的度数为偶数，也没说是联通的，F

2.After the first run of Insertion Sort, it is possible that no element is placed in its final position.

如果是逆序，只有3个元素，则可以。T

3.Apply DFS to a directed acyclic graph, and output the vertex before the end of each recursion. The output sequence will be:

A.unsorted

B.topologically sorted

C.reversely topologically sorted

D.None of the above

递归的顺序是遍历1->遍历2->遍历3->.....->遍历n->返回n->返回n-1...->返回3->返回2->返回1

返回的时候打印，因此是从最后一个结点开始打印到源点。是逆拓扑序。

4.Graph G is an undirected completed graph of 20 nodes. Is there an Euler circuit in G? If not, in order to have an Euler circuit, what is the minimum number of edges which should be removed from G?

A.Yes, Graph G has an Euler circuit

B.No, Graph G has no Euler circuit. 10 edges should be removed.

C.No, Graph G has no Euler circuit. 20 edges should be removed.

D.No, Graph G has no Euler circuit. 40 edges should be removed.

20个点的完全图，每个点的度数为19，欧拉图每个点的必须是一个偶数，因此使得每一个点的度数是18，一条边对应两度，减少的边为：20*1/2=10

5.Given the adjacency matrix of a graph as shown by the figure. Then starting from V5, an impossible DFS sequence is:

A.V5, V6, V3, V1, V2, V4

B.V5, V1, V2, V4, V3, V6

C.V5, V1, V3, V6, V4, V2

D.V5, V3, V1, V2, V4, V6

邻接矩阵是对称的，所以是一个无向图。注意到头以后是一个一个退回去，从令一个节点开始 C

6.Use simple insertion sort to sort 10 numbers from non-decreasing to non-increasing, the possible numbers of comparisons and movements are:

A.100, 100

B.100, 54

C.54, 63

D.45, 44

看似好像很复杂：10个元素逆序的话：有C(10,2)=45的逆序对，因此交换的数目不会大于45 D

7.Given a sorted file of 1000 records. To insert a new record by insertion sort with binary search, the maximum number of comparisons is:

A.1000

B.999

C.500

D.10

注意不是线性插入，是二叉插入，因此是log2 100,应该是D