2023年河南省資料總結章程

1、設一棵二叉樹的結點結構為 (llink,info,rlink),root為指向該二叉樹根結點的指標，p 和q分別為指向該二叉樹中任意兩個結點的指標，試編寫一演算法ancestor（root，p,q,r），該演算法找到p和q的最近共同祖先結點r。

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

3、對二叉樹的某層上的結點進行運算，採用佇列結構按層次遍歷最適宜。

int leafklevel(bitree bt, int k) //求二叉樹bt 的第k(k>1) 層上葉子結點個數

//last移到指向下層最右一元素

if(level>k) return (leaf層數大於k 後退出執行

}//while }//結束leafklevel

4、二部圖（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為結點個數）。請在程式中加必要的注釋。

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

5、若第n件物品能放入揹包，則問題變為能否再從n-1件物品中選出若干件放入揹包（這時揹包可放入物品的重量變為s-w[n]）。若第n件物品不能放入揹包，則考慮從n-1件物品選若干件放入揹包（這時揹包可放入物品仍為s）。若最終s=0，則有一解；否則，若s<0或雖然s>0但物品數n<1，則無解。

（1）s-w[n],n-1 //knap(s-w[n],n-1)=true

（2）s,n-1knap←knap(s,n-1)

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

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

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

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

}//for

return(h);

}演算法結束

7、陣列a和b的元素分別有序，欲將兩陣列合併到c陣列，使c仍有序，應將a和b拷貝到c，只要注意a和b陣列指標的使用，以及正確處理一陣列讀完資料後將另一陣列餘下元素複製到c中即可。

void union(int a,b,c,m,n)

//整型陣列a和b各有m和n個元素，前者遞增有序，後者遞減有序，本演算法將a和b歸併為遞增有序的陣列c。

演算法結束

4、要求二叉樹按二叉鍊錶形式儲存。15分

（1）寫乙個建立二叉樹的演算法。（2）寫乙個判別給定的二叉樹是否是完全二叉樹的演算法。bitree creat建立二叉樹的二叉鍊錶形式的儲存結構

else error(「輸入錯誤」)；

return(bt);

}//結束 bitree

int judgecomplete(bitree bt) //判斷二叉樹是否是完全二叉樹,如是，返回1，否則，返回0

//while

return 1; } //judgecomplete

8、我們可用「破圈法」求解帶權連通無向圖的一棵最小代價生成樹。所謂「破圈法」就是「任取一圈，去掉圈上權最大的邊」，反覆執行這一步驟，直到沒有圈為止。請給出用「破圈法」求解給定的帶權連通無向圖的一棵最小代價生成樹的詳細演算法，並用程式實現你所給出的演算法。

注：圈就是迴路。

9、4、void linklist_reverse(linklist &l)

//鍊錶的就地逆置;為簡化演算法,假設表長大於2

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

}//linklist_reverse