2023年全國資料總結摘要

2021-10-23 04:37:07 字數 2603 閱讀 7053

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、因為後序遍歷棧中保留當前結點的祖先的資訊,用一變數儲存棧的最高棧頂指標,每當退棧時,棧頂指標高於儲存最高棧頂指標的值時,則將該棧倒入輔助棧中,輔助棧始終儲存最長路徑長度上的結點,直至後序遍歷完畢,則輔助棧中內容即為所求。

void longestpath(bitree bt)//求二叉樹中的第一條最長路徑長度

//沿左分枝向下

if(tag[top]==1) //當前結點的右分枝已遍歷

//保留當前最長路徑到l棧,記住最高棧頂指標,退棧

}else if(top>0) //沿右子分枝向下

}//while(p!=null||top>0)

}//結束longestpath

3、我們可用「破圈法」求解帶權連通無向圖的一棵最小代價生成樹。所謂「破圈法」就是「任取一圈,去掉圈上權最大的邊」,反覆執行這一步驟,直到沒有圈為止。請給出用「破圈法」求解給定的帶權連通無向圖的一棵最小代價生成樹的詳細演算法,並用程式實現你所給出的演算法。

注:圈就是迴路。

4、後序遍歷最後訪問根結點,即在遞迴演算法中,根是壓在棧底的。採用後序非遞迴演算法,棧中存放二叉樹結點的指標,當訪問到某結點時,棧中所有元素均為該結點的祖先。本題要找p和q 的最近共同祖先結點r ,不失一般性,設p在q的左邊。

後序遍歷必然先遍歷到結點p,棧中元素均為p的祖先。將棧拷入另一輔助棧中。再繼續遍歷到結點q時,將棧中元素從棧頂開始逐個到輔助棧中去匹配,第乙個匹配(即相等)的元素就是結點p 和q的最近公共祖先。

typedef struct

stack;

stack s,s1;//棧,容量夠大

bitree ancestor(bitree root,p,q,r)//求二叉樹上結點p和q的最近的共同祖先結點r。 //沿左分枝向下

if(bt==p) //不失一般性,假定p在q的左側,遇結點p時,棧中元素均為p的祖先結點//將棧s的元素轉入輔助棧s1 儲存

if(bt==q) //找到q 結點。

for(i=top;i>0;i--)//;將棧中元素的樹結點到s1去匹配

}while(top!=0 && s[top].tag==1) top退棧

if (top!=0){s[top].tag=1;bt=s[top].t->rchild;} //沿右分枝向下遍歷

}//結束while(bt!=null ||top>0)

return(null);//q、p無公共祖先

}//結束ancestor

5、假設以i和o分別表示入棧和出棧操作。棧的初態和終態均為空,入棧和出棧的操作序列可表示為僅由i和o組成的序列,稱可以操作的序列為合法序列,否則稱為非法序列。(15分)

(1)a和d是合法序列,b和c 是非法序列。

(2)設被判定的操作序列已存入一維陣列a中。

int judge(char a)

//判斷字元陣列a中的輸入輸出序列是否是合法序列。如是,返回true,否則返回false。

}i++; //不論a[i]是『i』或『o』,指標i均後移。}

if(j!=k)

else

}//演算法結束。

6、給定n個村莊之間的交通圖,若村莊i和j之間有道路,則將頂點i和j用邊連線,邊上的wij表示這條道路的長度,現在要從這n個村莊中選擇乙個村莊建一所醫院,問這所醫院應建在哪個村莊,才能使離醫院最遠的村莊到醫院的路程最短?試設計乙個解答上述問題的演算法,並應用該演算法解答如圖所示的例項。(20分)

7、假設以i和o分別表示入棧和出棧操作。棧的初態和終態均為空,入棧和出棧的操作序列可表示為僅由i和o組成的序列,稱可以操作的序列為合法序列,否則稱為非法序列。(15分)

(1)a和d是合法序列,b和c 是非法序列。

(2)設被判定的操作序列已存入一維陣列a中。

int judge(char a)

//判斷字元陣列a中的輸入輸出序列是否是合法序列。如是,返回true,否則返回false。

}i++; //不論a[i]是『i』或『o』,指標i均後移。}

if(j!=k)

else

}//演算法結束。

8、二路插入排序是將待排關鍵字序列r[1..n]中關鍵字分二路分別按序插入到輔助向量d[1..n]前半部和後半部(注:

向量d可視為迴圈表),其原則為,先將r[l]賦給d[1],再從r[2] 記錄開始分二路插入。編寫實現二路插入排序演算法。

2023年全國資料總結摘要

1 氣泡排序演算法是把大的元素向上移 氣泡的上浮 也可以把小的元素向下移 氣泡的下沉 請給出上浮和下沉過程交替的氣泡排序演算法。48.有n個記錄儲存在帶頭結點的雙向鍊錶中,現用雙向起泡排序法對其按上公升序進行排序,請寫出這種排序的演算法。注 雙向起泡排序即相鄰兩趟排序向相反方向起泡 2 證明由二叉樹...

2023年全國資料總結摘要

1 氣泡排序演算法是把大的元素向上移 氣泡的上浮 也可以把小的元素向下移 氣泡的下沉 請給出上浮和下沉過程交替的氣泡排序演算法。48.有n個記錄儲存在帶頭結點的雙向鍊錶中,現用雙向起泡排序法對其按上公升序進行排序,請寫出這種排序的演算法。注 雙向起泡排序即相鄰兩趟排序向相反方向起泡 2 證明由二叉樹...

2023年福建省資料總結摘要

while s next q next p s next q l next s linklist reverse 4 矩陣中元素按行和按列都已排序,要求查詢時間複雜度為o m n 因此不能採用常規的二層迴圈的查詢。可以先從右上角 i a,j d 元素與x比較,只有三種情況 一是a i,j x,這情況...