2023年四川省資料總結要領

1、兩棵空二叉樹或僅有根結點的二叉樹相似；對非空二叉樹，可判左右子樹是否相似，採用遞迴演算法。

int similar(bitree p,q) //判斷二叉樹p和q是否相似

//結束similar

2、已知有向圖g=(v,e)，其中v=，e=

寫出g的拓撲排序的結果。

g拓撲排序的結果是：v1、v2、v4、v3、v5、v6、v7

3、矩陣中元素按行和按列都已排序，要求查詢時間複雜度為o（m+n），因此不能採用常規的二層迴圈的查詢。可以先從右上角（i=a,j=d）元素與x比較，只有三種情況：一是a[i,j]>x， 這情況下向j 小的方向繼續查詢；二是a[i,j]void search(datatype a[ ][ ], int a,b,c,d, datatype x)

//n*m矩陣a,行下標從a到b,列下標從c到d,本演算法查詢x是否在矩陣a中.

else if (a[i][j]>x) j--; else i++;

if(flag) printf(「a[%d][%d]=%d」,i,j,x假定x為整型.

else printf(「矩陣a中無%d 元素」，x)；

}演算法search結束。

[演算法討論]演算法中查詢x的路線從右上角開始，向下（當x>a[i,j]）或向左（當x

2023年四川省資料總結要領

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

2023年四川省資料總結要領

1 陣列a和b的元素分別有序，欲將兩陣列合併到c陣列，使c仍有序，應將a和b拷貝到c，只要注意a和b陣列指標的使用，以及正確處理一陣列讀完資料後將另一陣列餘下元素複製到c中即可。void union int a,b,c,m,n 整型陣列a和b各有m和n個元素，前者遞增有序，後者遞減有序，本演算法將a...

2023年四川省資料總結高階

1 有一種簡單的排序演算法，叫做計數排序 count sorting 這種排序演算法對乙個待排序的表 用陣列表示 進行排序，並將排序結果存放到另乙個新的表中。必須注意的是，表中所有待排序的關鍵碼互不相同，計數排序演算法針對表中的每個記錄，掃瞄待排序的表一趟，統計表中有多少個記錄的關鍵碼比該記錄的關鍵...