1、證明由二叉樹的中序序列和後序序列,也可以唯一確定一棵二叉樹。
29. ①試找出滿足下列條件的二叉樹
1)先序序列與後序序列相同 2)中序序列與後序序列相同
3)先序序列與中序序列相同 4)中序序列與層次遍歷序列相同
2、連通圖的生成樹包括圖中的全部n個頂點和足以使圖連通的n-1條邊,最小生成樹是邊上權值之和最小的生成樹。故可按權值從大到小對邊進行排序,然後從大到小將邊刪除。每刪除一條當前權值最大的邊後,就去測試圖是否仍連通,若不再連通,則將該邊恢復。
若仍連通,繼續向下刪;直到剩n-1條邊為止。
void spntree (adjlist g)
//用「破圈法」求解帶權連通無向圖的一棵最小代價生成樹。
node; //設頂點資訊就是頂點編號,權是整型數
node edge;
scanf( "%d%d",&e,&n) ; //輸入邊數和頂點數。
for (i=1;i<=e;i輸入e條邊:頂點,權值。
scanf("%d%d%d" ,&edge[i].i ,&edge[i].j ,&edge[i].w);
for (i=2;i<=e;i++) //按邊上的權值大小,對邊進行逆序排序。
//for
k=1; eg=e;
while (eg>=n破圈,直到邊數e=n-1.
//測試下一條邊edge[k],權值置0表示該邊被刪除
k++; //下條邊
}//while
}//演算法結束。
connect()是測試圖是否連通的函式,可用圖的遍歷實現,
3、有乙個帶頭結點的單鏈表,每個結點包括兩個域,乙個是整型域info,另乙個是指向下乙個結點的指標域next。假設單鏈表已建立,設計演算法刪除單鏈表中所有重複出現的結點,使得info域相等的結點只保留乙個。
#include <
typedef char datatype;
typedef struct node listnode;
typedef listnode* linklist;
/* 刪除單鏈表中重複的結點 */
linklist deletelist(linklist head)
else
p=p->next;
}return head;
}4、設有兩個集合a和集合b,要求設計生成集合c=a∩b的演算法,其中集合a、b和c用鏈式儲存結構表示。
typedef struct node lklist;
void intersection(lklist *ha,lklist *hb,lklist *&hc) }}
2019山西省資料結構分析深入
1 請編寫乙個判別給定二叉樹是否為二叉排序樹的演算法,設二叉樹用llink rlink法儲存。2 設有乙個陣列中存放了乙個無序的關鍵序列k1 k2 kn。現要求將kn放在將元素排序後的正確位置上,試編寫實現該功能的演算法,要求比較關鍵字的次數不超過n。51.借助於快速排序的演算法思想,在一組無序的記...
2023年雲南省資料總結深入
1 有乙個帶頭結點的單鏈表,每個結點包括兩個域,乙個是整型域info,另乙個是指向下乙個結點的指標域next。假設單鏈表已建立,設計演算法刪除單鏈表中所有重複出現的結點,使得info域相等的結點只保留乙個。include typedef char datatype typedef struct no...
2023年山東省資料總結深入
1 將頂點放在兩個集合v1和v2。對每個頂點,檢查其和鄰接點是否在同乙個集合中,如是,則為非二部圖。為此,用整數1和2表示兩個集合。再用一佇列結構存放圖中訪問的頂點。int bpgraph adjmatrix g 判斷以鄰接矩陣表示的圖g是否是二部圖。初始化,各頂點未確定屬於那個集合 q 1 1 r...