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

2018年考研408計(jì)算機(jī)統(tǒng)考考研真題

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

41、（13分）給定一個含n（n>=1）個整數(shù)的數(shù)組，請?jiān)O(shè)計(jì)一個在時間上盡可能高效的算法，找出數(shù)組中未出現(xiàn)的最小正整數(shù)。例如，數(shù)組{-5，3，2，3}中未出現(xiàn)的最小正整數(shù)是1；數(shù)組{1，2，3}中未出現(xiàn)的最小正整數(shù)是4。要求：

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

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

（3）說明你所設(shè)計(jì)算法的時間復(fù)雜度和空間復(fù)雜度。

42、（12分）擬建設(shè)一個光通信骨干網(wǎng)絡(luò)連通BJ、CS、XA、QD、JN、NJ、TL和WH等8個城市，題42圖中無向邊上的權(quán)值表示兩個城市間備選光纜的鋪設(shè)費(fèi)用。

請回答下列問題。

（1）僅從鋪設(shè)費(fèi)用角度出發(fā)，給出所有可能的最經(jīng)濟(jì)的光纜鋪設(shè)方案（用帶權(quán)圖表示），并計(jì)算相應(yīng)方案的總費(fèi)用。

（2）題42圖可采用圖的哪一種存儲結(jié)構(gòu)？給出求解問題（1）所使用的算法名稱。

（3）假設(shè)每個城市采用一個路由器按（1）中得到的最經(jīng)濟(jì)方案組網(wǎng)，主機(jī)H1直接連接在TL的路由器上，主機(jī)H2直接連接在BJ的路由器上。若H1向H2發(fā)送一個TTL=5的IP分組，則H2是否可以收到該IP分組？