2017年計算機考研408真題（41-42）

考研408計算機統(tǒng)考分兩部分，80分單項選擇題和70分大題，滿分150分。單項選擇題總共80分，每小題2分，40小題。單項選擇題，1-10題是數(shù)據(jù)結(jié)構(gòu)部分；11-22題是計算機組成原理部分；23-32題是操作系統(tǒng)部分；33-40題是計算機網(wǎng)絡(luò)部分。綜合應(yīng)用題70分，共7小題，41和42題是數(shù)據(jù)結(jié)構(gòu)題，分值各為10分和15分；43和44題是計算機組成原理題，各占8分和13分；45和46題是操作系統(tǒng)題，各占7分和8分；47題是計算機網(wǎng)絡(luò)題，分值為9分。為了方便大家更好的來備考，小編為大家整理了“2017年408計算機考研真題”，希望可以幫助大家更好的復(fù)習(xí)408計算機考研內(nèi)容。

2017年考研408計算機統(tǒng)考考研真題

二、綜合應(yīng)用題（第41~47小題，共70分）

41、（15分）請設(shè)計一個算法，將給定的表達式樹（二叉樹）轉(zhuǎn)換為等價的中綴表達式（通過括號反映操作符的計算次序）并輸出。例如，當(dāng)下列兩棵表達式樹作為算法的輸入時：

輸出的等價中綴表達式分別為(a+b)*(c*(-d))和(a*b)+(-(c-d))。

二叉樹結(jié)點定義如下：

typedef structnode{

char data[10];//存儲操作數(shù)或操作符；

struct node*left,*right;

}BTree;

要求：

（1）給出算法的基本設(shè)計思想。

（2）根據(jù)設(shè)計思想，采用C或C++語言描述算法，關(guān)鍵之處給出注釋。

42、（8分）使用Prim（普里姆）算法求帶權(quán)連通圖的最?。ù鷥r）生成樹（MST）。請回答下列問題。

（1）對下列圖G，從頂點A開始求G的MST，依次給出按算法選出的邊。

（2）圖G的MST是唯一的嗎？

（3）對任意的帶權(quán)連通圖，滿足什么條件時，其MST是唯一的？