1、已知有向圖g=(v,e),其中v=,e=
寫出g的拓撲排序的結果。
g拓撲排序的結果是:v1、v2、v4、v3、v5、v6、v7
2、給定n個村莊之間的交通圖,若村莊i和j之間有道路,則將頂點i和j用邊連線,邊上的wij表示這條道路的長度,現在要從這n個村莊中選擇乙個村莊建一所醫院,問這所醫院應建在哪個村莊,才能使離醫院最遠的村莊到醫院的路程最短?試設計乙個解答上述問題的演算法,並應用該演算法解答如圖所示的例項。(20分)
3、二叉樹的層次遍歷序列的第乙個結點是二叉樹的根。實際上,層次遍歷序列中的每個結點都是「區域性根」。確定根後,到二叉樹的中序序列中,查到該結點,該結點將二叉樹分為「左根右」三部分。
若左、右子樹均有,則層次序列根結點的後面應是左右子樹的根;若中序序列中只有左子樹或只有右子樹,則在層次序列的根結點後也只有左子樹的根或右子樹的根。這樣,定義乙個全域性變數指標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==s.h)
else
}//結束while (!empty(q))
return(p);
}//演算法結束
4、本題應使用深度優先遍歷,從主調函式進入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。
2023年雲南省資料總結基礎
1 根據二叉排序樹中序遍歷所得結點值為增序的性質,在遍歷中將當前遍歷結點與其前驅結點值比較,即可得出結論,為此設全域性指標變數pre 初值為null 和全域性變數flag,初值為true。若非二叉排序樹,則置flag為false。define true 1 define false 0 typede...
2023年雲南省資料總結入門
1 設有一組初始記錄關鍵字序列 k1,k2,kn 要求設計乙個演算法能夠在o n 的時間複雜度內將線性表劃分成兩部分,其中左半部分的每個關鍵字均小於ki,右半部分的每個關鍵字均大於等於ki。void quickpass int r,int s,int t r i x 2 對一般二叉樹,僅根據乙個先序...
2023年雲南省資料總結要領
1 設t是一棵滿二叉樹,編寫乙個將t的先序遍歷序列轉換為後序遍歷序列的遞迴演算法。2 兩棵空二叉樹或僅有根結點的二叉樹相似 對非空二叉樹,可判左右子樹是否相似,採用遞迴演算法。int similar bitree p,q 判斷二叉樹p和q是否相似 結束similar 3 設一棵樹t中邊的集合為,要求...