2018年计算机考研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分。为了方便大家更好的来备考，小编为大家整理了“2018年408计算机考研真题”，希望可以帮助大家更好的复习408计算机考研内容。

2018年考研408计算机统考考研真题

二、综合应用题（第41~47小题，共70分）

41、（13分）给定一个含n（n>=1）个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5，3，2，3}中未出现的最小正整数是1；数组{1，2，3}中未出现的最小正整数是4。要求：

（1）给出算法的基本设计思想。

（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

（3）说明你所设计算法的时间复杂度和空间复杂度。

42、（12分）拟建设一个光通信骨干网络连通BJ、CS、XA、QD、JN、NJ、TL和WH等8个城市，题42图中无向边上的权值表示两个城市间备选光缆的铺设费用。

请回答下列问题。

（1）仅从铺设费用角度出发，给出所有可能的最经济的光缆铺设方案（用带权图表示），并计算相应方案的总费用。

（2）题42图可采用图的哪一种存储结构？给出求解问题（1）所使用的算法名称。

（3）假设每个城市采用一个路由器按（1）中得到的最经济方案组网，主机H1直接连接在TL的路由器上，主机H2直接连接在BJ的路由器上。若H1向H2发送一个TTL=5的IP分组，则H2是否可以收到该IP分组？