2019湖北省資料理論基礎

1、本題要求建立有序的迴圈鍊錶。從頭到尾掃瞄陣列a，取出a[i]（0<=ilinkedlist creat(elemtype a,int n)

//由含n個資料的陣列a生成迴圈鍊錶，要求鍊錶有序並且無值重複結點

//查詢a[i]的插入位置

if(p==h || p->data!=a[i重複資料不再輸入

}//for

return(h);

}演算法結束

2、設計乙個盡可能的高效演算法輸出單鏈表的倒數第k個元素。

3、假設k1，…，kn是n個關鍵詞，試解答：

試用二叉查詢樹的插入演算法建立一棵二叉查詢樹，即當關鍵詞的插入次序為k1，k2，…，kn 時，用演算法建立一棵以llink / rlink 鏈結表示的二叉查詢樹。

4、二叉樹的層次遍歷序列的第乙個結點是二叉樹的根。實際上，層次遍歷序列中的每個結點都是「區域性根」。確定根後，到二叉樹的中序序列中，查到該結點，該結點將二叉樹分為「左根右」三部分。

若左、右子樹均有，則層次序列根結點的後面應是左右子樹的根；若中序序列中只有左子樹或只有右子樹，則在層次序列的根結點後也只有左子樹的根或右子樹的根。這樣，定義乙個全域性變數指標r，指向層次序列待處理元素。演算法中先處理根結點，將根結點和左右子女的資訊入佇列。

然後，在佇列不空的條件下，迴圈處理二叉樹的結點。佇列中元素的資料結構定義如下：

typedef struct

qnode;

bitree creat(datatype in,level,int n)

//由二叉樹的層次序列level[n]和中序序列in[n]生成二叉樹。 n是二叉樹的結點數

qnode s,qq是元素為qnode型別的佇列，容量足夠大

init(q); int r=0; //r是層次序列指標，指向當前待處理的結點

bitree p=(bitree)malloc(sizeof(binode生成根結點

p->data=level[0]; p->lchild=null; p->rchild=null; //填寫該結點資料

for (i=0; iif (in[i]==level[0]) break;

if (i==0) //根結點無左子樹，遍歷序列的1—n-1是右子樹

else if (i==n-1) //根結點無右子樹，遍歷序列的1—n-1是左子樹

else //根結點有左子樹和右子樹

while (!empty(q)) //當佇列不空，進行迴圈，構造二叉樹的左右子樹

else if (i==

else

}//結束while (!empty(q))

return(p);

}//演算法結束

5、二部圖（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為結點個數）。請在程式中加必要的注釋。若有必要可直接利用堆疊或佇列操作。【

6、給定n個村莊之間的交通圖，若村莊i和j之間有道路，則將頂點i和j用邊連線，邊上的wij表示這條道路的長度，現在要從這n個村莊中選擇乙個村莊建一所醫院，問這所醫院應建在哪個村莊，才能使離醫院最遠的村莊到醫院的路程最短?試設計乙個解答上述問題的演算法，並應用該演算法解答如圖所示的例項。（20分）