2021年计算机考研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分。为了方便大家更好的来备考，小编为大家整理了“2021年408计算机考研真题”，希望可以帮助大家更好的复习408计算机考研内容。完整版大家可以点击文中附件下载查看。

2021年408计算机学科专业基础真题

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

41、（15分）已知无向连通图G由顶点集V和边集E组成|E|>0，当G中度为奇数的顶点个数为不大于2的偶数时，G存在包含所有边且长度为|E|的路径（称为EL路径），设图G采用邻接矩阵存储，类型定义下：

Typedef struct{ //图的定义

int numVertices，numEdges; //图中实际的顶点数和边数

Char VertticesList[MAXV]; //顶点表。MAXV为已定义常量

Int Edge[MAXV][MAXV]; //邻接矩阵

};MGraph;

请设计算法：int IsExistEL(MGraph G)，判断G是否存在EL路径，若存在，则返回1，否则，返回0，要求：

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

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

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

42、（8分）已知某排序算法：

void cmpCountSort(int a[],int b[], int n){

int i,j, *count;

count=(int *)malloc(sizeof(int) *n); //C++语言：count=new int[n];

for(i=0;i<n;i++) count[i]=0;

for(i=0;i<n-1;i++)

for(j=i+1;j<n;j++)

if(a[i]<a[j]) count[j]++;

else count[i]++;

for(i=0;i<n;i++) b[count[i]]=a[i];

free(count); //C++语言：delete count;

}

请回答下列问题。

（1）若有int a[]={25，-10，25，10，11，19}，b[6]，则调用cmpCountSort(a，b，6)后数组b中的内容是什么？

（2）若a中含有n个元素，则算法执行过程中，元素之间的比较次数是多少？

（3）该算法是稳定的吗？若是，则阐述理由；否则，修改为稳定排序算法。