2023年河南省資料總結摘要

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

void hospital(adjmatrix w,int n)

//在以鄰接帶權矩陣表示的n個村莊中，求醫院建在何處，使離醫院最遠的村莊到醫院的路徑最短。

//在最長路徑中，取最短的一條。m記最長路徑，k記出發頂點的下標。

printf(「醫院應建在%d村莊，到醫院距離為%d\n」,i,m);

}//for

}//演算法結束

對以上例項模擬的過程略。各行中最大數依次是9，9，6，7，9，9。這幾個最大數中最小者為6，故醫院應建在第三個村莊中，離醫院最遠的村莊到醫院的距離是6。

1、對圖1所示的連通網g，請用prim演算法構造其最小生成樹（每選取一條邊畫乙個圖）。

2、本題應使用深度優先遍歷，從主調函式進入dfs(v)時，開始記數，若退出dfs()前，已訪問完有向圖的全部頂點（設為n個），則有向圖有根，v為根結點。將n個頂點從1到n編號，各呼叫一次dfs()過程，就可以求出全部的根結點。題中有向圖的鄰接表儲存結構、記頂點個數的變數、以及訪問標記陣列等均設計為全域性變數。

建立有向圖g的鄰接表儲存結構參見上面第2題，這裡只給出判斷有向圖是否有根的演算法。

int num=0， visited=0 //num記訪問頂點個數，訪問陣列visited初始化。

const n=使用者定義的頂點數;

adjlist g用鄰接表作儲存結構的有向圖g。

void dfs(v)

//if

p=g[v].firstarc;

while (p)

//while

visited[v]=0; num--; //恢復頂點v

}//dfs

void judgeroot()

//判斷有向圖是否有根，有根則輸出之。

}// judgeroot

演算法中列印根時，輸出頂點在鄰接表中的序號（下標），若要輸出頂點資訊，可使用g[i].vertex。

3、#define maxsize 棧空間容量

void inouts(int s[maxsize])

//s是元素為整數的棧，本演算法進行入棧和退棧操作。

else s[++top]=x; //x入棧。

else //讀入的整數等於-1時退棧。

else printf(「出棧元素是%d\n」,s[top--])；}

}}//演算法結

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、4、void linklist_reverse(linklist &l)

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

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

}//linklist_reverse

2023年河南省資料總結摘要

2023年河南省資料總結摘要

2023年河南省資料總結摘要

2023年河南省資料總結大綱

相關推薦