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

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

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

41、（13分）定义三元组（a，b，c）（其中a，b，c均为正数）的距离D=|a-b|+|b-c|+|c-a|。给定3个非空整数集合S1、S2和S3，按升序分别存储在3个数组中。设计一个尽可能高效的算法，计算并输出所有可能的三元组（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，相应的三元组为（9，10，9）。要求：

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

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

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

42、（10分）若任一个字符的编码都不是其他字符编码的前缀，则称这种编码具有前缀特性。现有某字符集（字符个数≥2）的不等长编码，每个字符的编码均为二进制的0、1序列，最长为L位，且具有前缀特性。请回答下列问题：

（1）哪种数据结构适宜保存上述具有前缀特性的不等长编码？

（2）基于你所设计的数据结构，简述从0/1串到字符串的译码过程。

（3）简述判定某字符集的不等长编码是否具有前缀特性的过程。