2023年山東省資料總結大綱

1、題目中要求矩陣兩行元素的平均值按遞增順序排序，由於每行元素個數相等，按平均值排列與按每行元素之和排列是乙個意思。所以應先求出各行元素之和，放入一維陣列中，然後選擇一種排序方法，對該陣列進行排序，注意在排序時若有元素移動，則與之相應的行中各元素也必須做相應變動。

void translation（float *matrix，int n）

//本演算法對n×n的矩陣matrix，通過行變換，使其各行元素的平均值按遞增排列。

//for i

for(i=0; i

sum=p[i]; p[i]=p[k]; p[k]=sum; //交換一維陣列中元素之和.

}//if

}//for i

free(p); //釋放p陣列.

}// translation

[演算法分析] 演算法中使用選擇法排序，比較次數較多，但資料交換(移動)較少.若用其它排序方法，雖可減少比較次數，但資料移動會增多.演算法時間複雜度為o(n2).

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

3、設一棵二叉樹的結點結構為 (llink,info,rlink),root為指向該二叉樹根結點的指標，p 和q分別為指向該二叉樹中任意兩個結點的指標，試編寫一演算法ancestor（root，p,q,r），該演算法找到p和q的最近共同祖先結點r。

4、二叉樹的層次遍歷序列的第乙個結點是二叉樹的根。實際上，層次遍歷序列中的每個結點都是「區域性根」。確定根後，到二叉樹的中序序列中，查到該結點，該結點將二叉樹分為「左根右」三部分。

若左、右子樹均有，則層次序列根結點的後面應是左右子樹的根；若中序序列中只有左子樹或只有右子樹，則在層次序列的根結點後也只有左子樹的根或右子樹的根。這樣，定義乙個全域性變數指標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);

}//演算法結束

5、設有兩個集合a和集合b，要求設計生成集合c=a∩b的演算法，其中集合a、b和c用鏈式儲存結構表示。

typedef struct node lklist;

void intersection(lklist *ha,lklist *hb,lklist *&hc) }}