2012年广东省基础数据加强

1、二部图（bipartite graph） G=（V，E）是一个能将其结点集V分为两不相交子集V 1和V2=V-V1的无向图，使得：V1中的任何两个结点在图G中均不相邻，V2中的任何结点在图G中也均不相邻。

（1）．请各举一个结点个数为5的二部图和非二部图的例子。

（2）．请用C或PASCAL编写一个函数BIPARTITE判断一个连通无向图G是否是二部图，并分析程序的时间复杂度。设G用二维数组A来表示，大小为n*n（n为结点个数）。请在程序中加必要的注释。若有必要可直接利用堆栈或队列操作。【

2、4、void LinkList_reverse(Linklist &L)

//链表的就地逆置;为简化算法,假设表长大于2

{

p=L->next;q=p->next;s=q->next;p->next=NULL;

while(s->next)

{

q->next=p;p=q;

q=s;s=s->next; //把L的元素逐个插入新表表头

}

q->next=p;s->next=q;L->next=s;

}//LinkList_reverse

3、设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。