2023年陝西省資料總結要領

1、有乙個帶頭結點的單鏈表，每個結點包括兩個域，乙個是整型域info，另乙個是指向下乙個結點的指標域next。假設單鏈表已建立，設計演算法刪除單鏈表中所有重複出現的結點，使得info域相等的結點只保留乙個。

#include

typedef char datatype;

typedef struct node listnode;

typedef listnode* linklist;

/* 刪除單鏈表中重複的結點 */linklist deletelist(linklist head)else

p=p->next;

}return head;

}2、已知有向圖g=(v,e)，其中v=，e=寫出g的拓撲排序的結果。

g拓撲排序的結果是：v1、v2、v4、v3、v5、v6、v73、二部圖（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為結點個數）。請在程式中

加必要的注釋。若有必要可直接利用堆疊或佇列操作。【