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）给出入队操作和出队操作的基本过程。