2016年計(jì)算機(jī)考研408真題（43-44）

考研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)備考，小編為大家整理了“2016年408計(jì)算機(jī)考研真題匯總”，希望可以幫助大家更好的復(fù)習(xí)408計(jì)算機(jī)考研內(nèi)容。

2016年考研408計(jì)算機(jī)統(tǒng)考考研真題匯總

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

43、已知由n(n≥2)個(gè)正整數(shù)構(gòu)成的集合A={ak|0≤k<n}，將其劃分為兩個(gè)不相交的子集A1和A2，元素個(gè)數(shù)分別是n1和n2，A1和A2中元素之和分別為S1和S2。設(shè)計(jì)一個(gè)盡可能高效的劃分算法，滿足｜n1-n2|最小且|S1-S2|最大。要求：

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

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

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

44、（9分）假定CPU主頻為50MHz，CPI為4。設(shè)備D采用異步串行通信方式向主機(jī)傳送7位ASCII字符，通信規(guī)程中有1位奇校驗(yàn)位和1位停止位，從D接收啟動(dòng)命令到字符送入I/O端口需要0.5ms。請(qǐng)回答下列問(wèn)題，要求說(shuō)明理由。

（1）每傳送一個(gè)字符，在異步串行通信線上共需傳輸多少位？在設(shè)備D持續(xù)工作過(guò)程中，每秒鐘最多可向I/O端口送入多少個(gè)字符？

（2）設(shè)備D采用中斷方式進(jìn)行輸入/輸出，示意圖如下：

I/O端口每收到一個(gè)字符申請(qǐng)一次中斷，中斷響應(yīng)需10個(gè)時(shí)鐘周期，中斷服務(wù)程序共有20條指令，其中第15條指令啟動(dòng)D工作。若CPU需從D讀取1000個(gè)字符，則完成這一任務(wù)所需時(shí)間大約是多少個(gè)時(shí)鐘周期？CPU用于完成這一任務(wù)的時(shí)間大約是多少個(gè)時(shí)鐘周期？在中斷響應(yīng)階段CPU進(jìn)行了哪些操作？