1、在有向圖g中,如果r到g中的每個結點都有路徑可達,則稱結點r為g的根結點。編寫乙個演算法完成下列功能:
(1).建立有向圖g的鄰接表儲存結構;
(2).判斷有向圖g是否有根,若有,則列印出所有根結點的值。
2、設一組有序的記錄關鍵字序列為(13,18,24,35,47,50,62,83,90),查詢方法用二分查詢,要求計算出查詢關鍵字62時的比較次數並計算出查詢成功時的平均查詢長度。
3、根據二叉排序樹中序遍歷所得結點值為增序的性質,在遍歷中將當前遍歷結點與其前驅結點值比較,即可得出結論,為此設全域性指標變數pre(初值為null)和全域性變數flag,初值為true。若非二叉排序樹,則置flag為false。
#define true 1
#define false 0
typedef struct node
*btree;
void judgebst(btree t,int flag)
// 判斷二叉樹是否是二叉排序樹,本演算法結束後,在呼叫程式中由flag得出結論。
//不是完全二叉樹
judgebst (t->rlink,flag);// 中序遍歷右子樹
}//judgebst演算法結束
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、請設計乙個演算法,要求該演算法把二叉樹的葉子結點按從左到右的順序連成乙個單鏈表,表頭指標為head。 二叉樹按二叉鍊錶方式儲存,鏈結時用葉子結點的右指標域來存放單鏈表指標。分析你的演算法的時、空複雜度。
6、給出折半查詢的遞迴演算法,並給出演算法時間複雜度性分析。
2023年全國資料總結摘要
1 題目中要求矩陣兩行元素的平均值按遞增順序排序,由於每行元素個數相等,按平均值排列與按每行元素之和排列是乙個意思。所以應先求出各行元素之和,放入一維陣列中,然後選擇一種排序方法,對該陣列進行排序,注意在排序時若有元素移動,則與之相應的行中各元素也必須做相應變動。void translation f...
2023年全國資料總結基礎
1 本題要求建立有序的迴圈鍊錶。從頭到尾掃瞄陣列a,取出a i 0 ilinkedlist creat elemtype a,int n 由含n個資料的陣列a生成迴圈鍊錶,要求鍊錶有序並且無值重複結點 查詢a i 的插入位置 if p h p data a i重複資料不再輸入 for return ...
2023年全國資料總結要領
1 因為後序遍歷棧中保留當前結點的祖先的資訊,用一變數儲存棧的最高棧頂指標,每當退棧時,棧頂指標高於儲存最高棧頂指標的值時,則將該棧倒入輔助棧中,輔助棧始終儲存最長路徑長度上的結點,直至後序遍歷完畢,則輔助棧中內容即為所求。void longestpath bitree bt 求二叉樹中的第一條最長...