专注在线职业教育23年
下载APP
小程序
希赛网小程序
导航

2021年计算机考研408真题(41-42)

责编:胡陆 2023-07-28
考研资料领取

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

试题练习:考试科目在线试题库

备考资料:免费课程学习资料包

更多资料
更多课程
更多真题
温馨提示:因考试政策、内容不断变化与调整,本网站提供的以上信息仅供参考,如有异议,请考生以权威部门公布的内容为准!
相关阅读
查看更多

加群交流

公众号

客服咨询

考试资料

每日一练

咨询客服