2020年計(jì)算機(jī)考研408真題（41-42）

考研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分。為了方便大家更好的來備考，小編為大家整理了“2020年408計(jì)算機(jī)考研真題”，希望可以幫助大家更好的復(fù)習(xí)408計(jì)算機(jī)考研內(nèi)容。

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

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

41、（13分）定義三元組（a，b，c）（其中a，b，c均為正數(shù)）的距離D=|a-b|+|b-c|+|c-a|。給定3個(gè)非空整數(shù)集合S1、S2和S3，按升序分別存儲(chǔ)在3個(gè)數(shù)組中。設(shè)計(jì)一個(gè)盡可能高效的算法，計(jì)算并輸出所有可能的三元組（a，b，c）（a∈S1，b∈S2，c∈S3）中的最小距離。例如S1={-1，0，9}，S2={-25，-10，10，11}，S3={2，9，17，30，41}，則最小距離為2，相應(yīng)的三元組為（9，10，9）。要求：

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

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

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

42、（10分）若任一個(gè)字符的編碼都不是其他字符編碼的前綴，則稱這種編碼具有前綴特性?，F(xiàn)有某字符集（字符個(gè)數(shù)≥2）的不等長(zhǎng)編碼，每個(gè)字符的編碼均為二進(jìn)制的0、1序列，最長(zhǎng)為L(zhǎng)位，且具有前綴特性。請(qǐng)回答下列問題：

（1）哪種數(shù)據(jù)結(jié)構(gòu)適宜保存上述具有前綴特性的不等長(zhǎng)編碼？

（2）基于你所設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)，簡(jiǎn)述從0/1串到字符串的譯碼過程。

（3）簡(jiǎn)述判定某字符集的不等長(zhǎng)編碼是否具有前綴特性的過程。