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

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

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

41、（13分）設(shè)線性表L=(a1,a2,a3,…,an-2,an-1,an)采用帶頭結(jié)點(diǎn)的單鏈表保存，鏈表中的結(jié)點(diǎn)定義如下:

typedef struct node

{ int data ;

struct node*next;

} NODE;

請(qǐng)?jiān)O(shè)計(jì)一個(gè)空間復(fù)雜度為O(1)且時(shí)間上盡可能高效的算法，重新排列L中的各結(jié)點(diǎn)，得到線性表L'=(a1,an,a2,an-1,a3,an-2,…)。要求：

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

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

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

42、（10分）請(qǐng)?jiān)O(shè)計(jì)一個(gè)隊(duì)列，要求滿足：① 初始時(shí)隊(duì)列為空；② 入隊(duì)時(shí)，允許增加隊(duì)列占用空間；③ 出隊(duì)后，出隊(duì)元素所占用的空間可重復(fù)使用，即整個(gè)隊(duì)列所占用的空間只增不減；④ 入隊(duì)操作和出隊(duì)操作的時(shí)間復(fù)雜度始終保持為O(1)。請(qǐng)回答下列問(wèn)題：

（1）該隊(duì)列是應(yīng)選擇鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，還是應(yīng)選擇順序存儲(chǔ)結(jié)構(gòu)?

（2）畫出隊(duì)列的初始狀態(tài)，并給出判斷隊(duì)空和隊(duì)滿的條件。

（3）畫出第一個(gè)元素入隊(duì)后的隊(duì)列狀態(tài)。

（4）給出入隊(duì)操作和出隊(duì)操作的基本過(guò)程。