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

考研408計算機統考分兩部分，80分單項選擇題和70分大題，滿分150分。單項選擇題總共80分，每小題2分，40小題。單項選擇題，1-10題是數據結構部分；11-22題是計算機組成原理部分；23-32題是操作系統部分；33-40題是計算機網絡部分。綜合應用題70分，共7小題，41和42題是數據結構題，分值各為10分和15分；43和44題是計算機組成原理題，各占8分和13分；45和46題是操作系統題，各占7分和8分；47題是計算機網絡題，分值為9分。為了方便大家更好的來備考，小編為大家整理了“2019年408計算機考研真題”，希望可以幫助大家更好的復習。

2019年考研408計算機統考考研真題

二、綜合應用題（第41~47小題，共70分）

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

typedef struct node

{ int data ;

struct node*next;

} NODE;

請設計一個空間復雜度為O(1)且時間上盡可能高效的算法，重新排列L中的各結點，得到線性表L'=(a1,an,a2,an-1,a3,an-2,…)。要求：

（1）給出算法的基本設計思想。

（2）根據設計思想，采用C或C++語言描述算法，關鍵之處給出注釋。

（3）說明你所設計的算法的時間復雜度。

42、（10分）請設計一個隊列，要求滿足：① 初始時隊列為空；② 入隊時，允許增加隊列占用空間；③ 出隊后，出隊元素所占用的空間可重復使用，即整個隊列所占用的空間只增不減；④ 入隊操作和出隊操作的時間復雜度始終保持為O(1)。請回答下列問題：

（1）該隊列是應選擇鏈式存儲結構，還是應選擇順序存儲結構?

（2）畫出隊列的初始狀態，并給出判斷隊空和隊滿的條件。

（3）畫出第一個元素入隊后的隊列狀態。

（4）給出入隊操作和出隊操作的基本過程。