2021年計(jì)算機(jī)考研408真題（41-42）

考研408計(jì)算機(jī)統(tǒng)考分兩部分，80分單項(xiàng)選擇題和70分大題，滿分150分。單項(xiàng)選擇題總共80分，每小題2分，40小題。單項(xiàng)選擇題，1-10題是數(shù)據(jù)結(jié)構(gòu)部分；11-22題是計(jì)算機(jī)組成原理部分；23-32題是操作系統(tǒng)部分；33-40題是計(jì)算機(jī)網(wǎng)絡(luò)部分。綜合應(yīng)用題70分，共7小題，41和42題是數(shù)據(jù)結(jié)構(gòu)題，分值各為10分和15分；43和44題是計(jì)算機(jī)組成原理題，各占8分和13分；45和46題是操作系統(tǒng)題，各占7分和8分；47題是計(jì)算機(jī)網(wǎng)絡(luò)題，分值為9分。為了方便大家更好的來(lái)備考，小編為大家整理了“2021年408計(jì)算機(jī)考研真題”，希望可以幫助大家更好的復(fù)習(xí)408計(jì)算機(jī)考研內(nèi)容。完整版大家可以點(diǎn)擊文中附件下載查看。

2021年408計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)真題

二、綜合應(yīng)用題（第41~47小題，共70分）

41、（15分）已知無(wú)向連通圖G由頂點(diǎn)集V和邊集E組成|E|>0，當(dāng)G中度為奇數(shù)的頂點(diǎn)個(gè)數(shù)為不大于2的偶數(shù)時(shí)，G存在包含所有邊且長(zhǎng)度為|E|的路徑（稱為EL路徑），設(shè)圖G采用鄰接矩陣存儲(chǔ)，類型定義下：

Typedef struct{ //圖的定義

int numVertices，numEdges; //圖中實(shí)際的頂點(diǎn)數(shù)和邊數(shù)

Char VertticesList[MAXV]; //頂點(diǎn)表。MAXV為已定義常量

Int Edge[MAXV][MAXV]; //鄰接矩陣

};MGraph;

請(qǐng)?jiān)O(shè)計(jì)算法：int IsExistEL(MGraph G)，判斷G是否存在EL路徑，若存在，則返回1，否則，返回0，要求：

（1）給出算法的基本設(shè)計(jì)思想。

（2）根據(jù)設(shè)計(jì)思想采用C或者C++語(yǔ)言描述算法，關(guān)鍵之處給出注釋。

（3）說(shuō)明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度。

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

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

int i,j, *count;

count=(int *)malloc(sizeof(int) *n); //C++語(yǔ)言：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++語(yǔ)言：delete count;

}

請(qǐng)回答下列問(wèn)題。

（1）若有int a[]={25，-10，25，10，11，19}，b[6]，則調(diào)用cmpCountSort(a，b，6)后數(shù)組b中的內(nèi)容是什么？

（2）若a中含有n個(gè)元素，則算法執(zhí)行過(guò)程中，元素之間的比較次數(shù)是多少？

（3）該算法是穩(wěn)定的嗎？若是，則闡述理由；否則，修改為穩(wěn)定排序算法。