考研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)该算法是稳定的吗?若是,则阐述理由;否则,修改为稳定排序算法。