2023年山東省資料總結加強

1、設一組有序的記錄關鍵字序列為(13，18，24，35，47，50，62，83，90)，查詢方法用二分查詢，要求計算出查詢關鍵字62時的比較次數並計算出查詢成功時的平均查詢長度。

2、給出折半查詢的遞迴演算法，並給出演算法時間複雜度性分析。

3、連通圖的生成樹包括圖中的全部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()是測試圖是否連通的函式，可用圖的遍歷實現，

4、設有一組初始記錄關鍵字序列（k1，k2，…，kn），要求設計乙個演算法能夠在o(n)的時間複雜度內將線性表劃分成兩部分，其中左半部分的每個關鍵字均小於ki，右半部分的每個關鍵字均大於等於ki。

void quickpass(int r, int s, int t)

r[i]=x;}

2023年山東省資料總結加強

1 設一組有序的記錄關鍵字序列為 13，18，24，35，47，50，62，83，90 查詢方法用二分查詢，要求計算出查詢關鍵字62時的比較次數並計算出查詢成功時的平均查詢長度。2 題目中要求矩陣兩行元素的平均值按遞增順序排序，由於每行元素個數相等，按平均值排列與按每行元素之和排列是乙個意思。所以應...

2023年山東省資料總結加強

1 矩陣中元素按行和按列都已排序，要求查詢時間複雜度為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,d...

2019山東省資料結構分析加強

1 假設以鄰接矩陣作為圖的儲存結構，編寫演算法判別在給定的有向圖中是否存在乙個簡單有向迴路，若存在，則以頂點序列的方式輸出該迴路 找到一條即可 注 圖中不存在頂點到自己的弧 有向圖判斷迴路要比無向圖複雜。利用深度優先遍歷，將頂點分成三類 未訪問 已訪問但其鄰接點未訪問完 已訪問且其鄰接點已訪問完。下...