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

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

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

41、（15分）请设计一个算法，将给定的表达式树（二叉树）转换为等价的中缀表达式（通过括号反映操作符的计算次序）并输出。例如，当下列两棵表达式树作为算法的输入时：

输出的等价中缀表达式分别为(a+b)*(c*(-d))和(a*b)+(-(c-d))。

二叉树结点定义如下：

typedef structnode{

char data[10];//存储操作数或操作符；

struct node*left,*right;

}BTree;

要求：

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

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

42、（8分）使用Prim（普里姆）算法求带权连通图的最小（代价）生成树（MST）。请回答下列问题。

（1）对下列图G，从顶点A开始求G的MST，依次给出按算法选出的边。

（2）图G的MST是唯一的吗？

（3）对任意的带权连通图，满足什么条件时，其MST是唯一的？