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

計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題

參考答案（2017年）

一、單項選擇題

1.B2.C3.A4.B5.B

6.D7.B8.A9.B10.B

11.D12.C13.C14.A15.D

16.A17.C18.B19.A20.D

21.D22.B23.D24.C25.B

26.D27.B28.D29.B30.D

31.B32.B33.A34.D35.B

36.A37.D38.C39.A40.C

二、綜合應(yīng)用題

41.【答案要點(diǎn)】

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

表達(dá)式樹的中序序列加上必要的括號即為等價的中綴表達(dá)

式。可以基于二叉樹的中序遍歷策略得到所需的表達(dá)

式。（3分）

去達(dá)式樹中分支結(jié)點(diǎn)所對應(yīng)的子表達(dá)式的計算次序，由該分

支結(jié)點(diǎn)所處的位置決定。為得到正確的中綴表達(dá)式，需要在

生成遍歷序列的同時，在適當(dāng)位置增加必要的括號顯然，表

達(dá)式的最外層（對應(yīng)根結(jié)點(diǎn)）及操作數(shù)（對應(yīng)葉結(jié)點(diǎn)）不需要添

加括號。（2分）

（2）算法實現(xiàn)（10分）

voidBt?-ceToE(BTree*root)

BtreeToExp(root,1)；〃根的高度為1

voidBtrccToE\p(BTree*root,intdeep)

if(root==\lLL)return；

elseif(root->left==NULL&&root->right-=NULL)

//若為葉結(jié)點(diǎn)

printf(”％s”,root->dala)；//輸出操作數(shù)

else

if(deep>1)printf("(")；//若有子表達(dá)式則加1層括號

BtreeToExp(root->left,deep+1)；

printf("%s",root->data)；//輸出操作符

BtreeToExp(root->right,deep+1);

if(deep>1)printf(")?');〃若布.F表達(dá)式則力口1層括號

【評分說明】

①若考生設(shè)計的算法滿足題II的功能要求，則（】）、（2）根據(jù)所實

現(xiàn)算法的策略及輸出結(jié)果給分,細(xì)則見下表。

分?jǐn)?shù)備注

15采用中序遍歷算:法H正確，括號嵌隹正確，層數(shù)適當(dāng)

采用中序遍歷算法且正確，括號嵌套正確,但括號嵌套層數(shù)

14過多例如，表達(dá)式處外層加1:括號，或操作數(shù)加括號如

（U）“

采用中序遺歷算法，但括號嵌套層數(shù)不完全正確例如，左

11

右括號數(shù)=不匹配。

續(xù)我

分散備注

9果用中序遍歷算法，但沒行考慮括號

W7兒他

②若考生采用其他方法得到正確結(jié)果，可參照Q的評分標(biāo)準(zhǔn)給分。

③如果程序中使用了求結(jié)點(diǎn)深度等輔助函數(shù)，但沒有給出相應(yīng)的

實現(xiàn)過程，只要考生進(jìn)行了必要的說明，可不扣分。

④若在算法的基本設(shè)計思想描述中因文字表達(dá)沒有清晰反映出算

法思路，但在算法實現(xiàn)中能夠表達(dá)出算法思想旦正確的，可參照

①的標(biāo)準(zhǔn)給分。

⑤若n法的基本設(shè)計思想描述或算法實現(xiàn)中部分正確，可參照①

中各種情況的相應(yīng)給分標(biāo)準(zhǔn)酌情給分。

⑥參考答案中只給出了使用c語言的版本，使用C++語育的答案

參照以上評分標(biāo)準(zhǔn)。

42.【答案要點(diǎn)】

(1)依次選出的邊為：

(A,D),(D,E),(C,E),(B,C)(4分)

【評分說明】每正確選對一條邊f(xié)L次序正確，給?分。若考生選擇

的邊正確，但次序不完全正確，酌情給分。

(2)圖C的MST是唯一的。(2分)

(3)當(dāng)帶權(quán)連通圖的任意一個環(huán)中所包含的邊的權(quán)值均不相同時,

其MST是唯一的。(2分)

【評分說明】

①若考生答案中給出的是其他充分條件，例如“帶權(quán)連通圖的所有

邊的權(quán)值均不相同”，同樣給分。

②若考生給出的充分條件對圖的頂點(diǎn)數(shù)和邊數(shù)做了某些限制，例

如，限制了圖中頂點(diǎn)的個數(shù)(頂點(diǎn)個數(shù)少于3個)、限制「圖的

形狀(圖中沒有環(huán))等，則最高給1分。

&答案部分正確，酌情給分，

43.【答案要點(diǎn)】

(1)由于i和。是unsigned型，故"i<=n-1”是無符號數(shù)比較，n=0

時，〃一1的機(jī)器數(shù)為全1,值是為unsigned型可衣示的最

大數(shù)，條件"i<=n-l”永真，因此出現(xiàn)死循環(huán)(2分)

若i和〃改為H類型，則不會出現(xiàn)死循環(huán).(1分)

因為"i<=nT"是帶符號整數(shù)比較,〃=0時，幾-1的值是7,當(dāng)

i=0時條件"i<=n-l”不J或立，此n寸退出for循環(huán)。(1分)

(2)口(23)與(2(23)的返|可值相等。(1分)

fl(23)MillOOFFFFFFH,(1分)

也(23)的tIL器數(shù)是4B7FFFFFH。(1分)

(3)當(dāng)”24時,/(24)=11111)1111111111!11111111B,而

float型數(shù)只有24位才?效位.舍人后數(shù)值增大，所以f2(24)比

“(24)大lo(1分)

【評分說明】只要說明『2(24)需舍人處理即可給分。

(4)顯然/(31)已超出了int型數(shù)據(jù)的表示范圍，用fl(31)實現(xiàn)時

得到的機(jī)器數(shù)為32個1,作為int型數(shù)解釋時其值為-1,即

fl(31)的返回值為-1。(1分)

因為int型最大可表示數(shù)是0后面加31個1,故使H(n)的返

回值與f(〃)相等的最大幾值是30。(1分)

【評分說明】對于第二問，只要給出n=30即可給分。

(5)1EEE754標(biāo)準(zhǔn)用“階碼全1、尾數(shù)全0”表示無窮大。f2返

回值為“間型，機(jī)器數(shù)7F800000H對應(yīng)的值是+8。

(1分)

當(dāng)n=126時,/(126)=2,;7-1=1.1…1x23,對應(yīng)階碼為127+

126=253,尾數(shù)部分舍入后階碼加1,最終階碼為254,是IEEE

754單精度格式表示的最大階碼。故使［2結(jié)果不溢出的最大n

值為126。(I分)

當(dāng)建=23時,/(23)為24位1,float型數(shù)有24位有效位，所以不

需舍人，結(jié)果精確，故使f2獲得精確結(jié)果的最大n值為23o

（1分）

【評分說明】對于第二問，只要給出〃=23,即可給分對于第三問，

只要給出n=126,即可給分。

44.【答案要點(diǎn)】

（1）M為CISC。（1分）

M的指令長短不一，不符合RISC指令系統(tǒng)特點(diǎn)。（1分）

（2）fl的機(jī)器代碼占96Bo（1分）

因為fl的第一條指令"pushebp”所在的虛擬地址為0040

1020H,最后一條指令“rel”所在的虛擬地址為0040I07FH,所

以，力的機(jī)器指令代碼長度為0040107FH-00401020H+1=

60H=96個字節(jié)。（1分）

（3）CF=1O（1分）

cmp指令實現(xiàn)i與幾-1的比較功能，進(jìn)行的是減法運(yùn)算在執(zhí)

行門（0）過程「打，n=0,當(dāng)i=0時，i=00000000H,并H.n-1=

FFFFFFFFHC因此，當(dāng)執(zhí)行第20條指令時，在補(bǔ)碼加/減運(yùn)算

器中執(zhí)行"0減FFFFFFFFH”的操作，即00000000H+0000

0000H+l=00000001H,此時，進(jìn)位輸出C=0,減法運(yùn)算時的

借位標(biāo)志CF=C十1=1。（2分）

（4）門中不能用shl指令實現(xiàn)power*2。（1分）

因為shl指令用來將一個整數(shù)的所有有效數(shù)位作為一個整體

左移;而f2中的變Mpower是floal型，其機(jī)器數(shù)中不包含最高

有效數(shù)位，但包含「階碼部分，將其作為一個整體左移時并不

能實現(xiàn)“乘2”的功能.因而［2中不能用shl指令實現(xiàn)power.2。

（2分）

45.【答案要點(diǎn)】

（1）函數(shù)門的代碼段中所有指令的虛擬地址的高20位相同，因此

fl的機(jī)器指令代碼在同一頁中，僅占用1頁。（1分）

（2）pushebp指令的虛擬地址的最高10位（頁目錄號）為000000

0001,中間10位（頁表索引）為000000000】，所以，取該指令

時訪問了頁目一的第1個表項,a分）在對應(yīng)的頁表中訪問r

第1個表項。（1分）

（3）在執(zhí)行scunf（）的過程中，進(jìn)程P因等待輸入而從執(zhí)行態(tài)變?yōu)?/p>

阻塞態(tài)。（1分）輸入結(jié)束時，P被中斷處理程序喚醒，變?yōu)榫?/p>

結(jié)態(tài)。（1分）P被調(diào)度程序調(diào)度，變?yōu)檫\(yùn)行態(tài)。（1分）CPL狀

態(tài)會從用戶態(tài)變?yōu)閮?nèi)核態(tài)。（1分）

46.【答案要點(diǎn)】

semaphoremutex_yl=1；//mutex_y1用于threadI與thread3對變.

y的互斥訪問。（1分）

semaphoremulex_y2=1；//mutex_y2用于thread2與thread?對'￡：心

y的互斥訪問。（1分）

semaphoremutex_z=1;//mutex_z用于變Mz的反斥訪問o（?分）

互斥代碼如下：（5分）

threadithread2lhread3

11

cnumw；cnumw；cnuinw；

wail(mutex_y1)；wait(mutex\2);w.a=1；

w=u<ld(xty);wail(mulex_z)；w.b=1；

signal(mutex_yl)；w=add(y,z)；wait(mulex_z);

signal(mutex_z)；z=add(z,w)；

1signa](mulex_v2);signal(inulrxz)；

wail(mutrx.51);

1wail(mutex_y2)；

y二add(y,w);

signal(mutex.y1)；

signal(nwtex_y2)；

【評分說明】

①各線程與變盤之間的互斥、并發(fā)情況及相應(yīng)評分見下表。

ihrcad1和lhreud2和thread）和

給分

lhread2lhread