2015年計算機學(xué)科專業(yè)基礎(chǔ)綜合(408)統(tǒng)考考研試題及答案.pdf

2015 年全國碩士研究生入學(xué)統(tǒng)一考試 計算機科學(xué)與技術(shù)學(xué)科聯(lián)考計算機學(xué)科專業(yè)基礎(chǔ)綜合試題 一、單項選擇題：第 140 小題，每小題 2 分，共 80 分。下列每題給出的四個選項中，只 有一個選項最符合試題要求。 1已知程序如下： int S(int n) return (nlink-data0? p-link-data:-p-link-data; if(*(q+m)=0) /判斷該結(jié)點的data 是否已出現(xiàn)過 *(q+m)=1; /首次出現(xiàn) p=p-link; /保留 else /重復(fù)出現(xiàn) r=p-link; /刪除 p-link=r-link free(r); free(q); 010 【評分說明】若考生設(shè)計的算法滿足題目的功能要求且正確，則酌情給分。 4）參考答案所給算法的時間復(fù)雜度為O(m)，空間復(fù)雜度為O(n)。 【評分說明】若考生所估計的時間復(fù)雜度和空間復(fù)雜度與考生實現(xiàn)的算法一致，可給分。 42解答： 1）圖G 的鄰接矩陣A 如下： 2）A2如下： 0 行3 列的元素值3 表示從頂點0 到頂點3 之間長度為2 的路徑共有3 條。 3）Bm（2mn）中位于 i 行 j 列（0i，jn-1）的非零元素的含義是：圖中從頂點 i 到頂點 j 長度為m 的路徑條數(shù)。 43解答： 1）程序員可見寄存器為通用寄存器（R0R3）和 PC。因為采用了單總線結(jié)構(gòu)，因此，若無暫存 器T，則ALU 的A、B 端口會同時獲得兩個相同的數(shù)據(jù)，使數(shù)據(jù)通路不能正常工作。 【評分說明】回答通用寄存器（R0R3） ，給分；回答PC，給分；部分正確，酌情給分。設(shè)置暫存 器T 的原因若回答用于暫時存放端口A 的數(shù)據(jù)，則給分，其他答案，酌情給分。 2）ALU 共有7 種操作，故其操作控制信號ALUop 至少需要3 位；移位寄存器有3 種操作，其操 作控制信號SRop 至少需要2 位。 3）信號SRout 所控制的部件是一個三態(tài)門，用于控制移位器與總線之間數(shù)據(jù)通路的連接與斷開。 【評分說明】只要回答出三態(tài)門或者控制連接/斷開，即給分。 4）端口、須連接到控制部件輸出端。 【評分說明】答案包含、中任意一個，不給分；答案不全酌情給分。 5）連線1，；連線2，。 【評分說明】回答除上述連線以外的其他連線，酌情給分。 6）因為每條指令的長度為 16 位，按字節(jié)編址，所以每條指令占用 2 個內(nèi)存單元，順序執(zhí)行時， 下條指令地址為(PC)+2。MUX 的一個輸入端為2，可便于執(zhí)行(PC)+2 操作。 44解答： 1）指令操作碼有7 位，因此最多可定義27=128 條指令。 2）各條指令的機器代碼分別如下： 2015 年全國碩士研究生入學(xué)統(tǒng)一考試計算機科學(xué)與技術(shù)學(xué)科聯(lián)考計算機學(xué)科專業(yè)基礎(chǔ)綜合試題 011 “inc R1”的機器碼為：0000001 0 01 0 00 0 00，即0240H。 “shl R2，R1”的機器碼為：0000010 0 10 0 01 0 00，即0488H。 “sub R3，(R1),R2”的機器碼為：0000011 0 11 1 01 0 10，即06EAH。 3）各標(biāo)號處的控制信號或控制信號取值如下： 0；mov；mova；left；read；sub；mov；Srout。 【評分說明】答對兩個給分。 4）指令“sub R1，R3，(R2)”的執(zhí)行階段至少包含4 個時鐘周期；指令“inc R1”的執(zhí)行階段至 少包含2 個時鐘周期。 45解答： semaphore Full_A = x; /Full_A 表示A 的信箱中的郵件數(shù)量 semaphore Empty_A = M-x; / Empty_A 表示A 的信箱中還可存放的郵件數(shù)量 semaphore Full_B = y; /Full_B 表示B 的信箱中的郵件數(shù)量 semaphore Empty_B = N-y; / Empty_B 表示B 的信箱中還可存放的郵件數(shù)量 semaphore mutex_A = 1; /mutex_A 用于 A 的信箱互斥 semaphore mutex_B = 1; /mutex_B 用于B 的信箱互斥 Cobegin A while(TRUE) P(Full_A); P(mutex_A); 從A 的信箱中取出一個郵件; V(mutex_A); V(Empty_A); 回答問題并提出一個新問題; P(Empty_B); P(mutex_B); 將新郵件放入B 的信箱; V(mutex_B); V(Full_B); B while(TRUE) P(Full_B); P(mutex_B); 從B 的信箱中取出一個郵件; V(mutex_B); V(Empty_B); 回答問題并提出一個新問題; P(Empty_A); P(mutex_A); 將新郵件放入A 的信箱; V(mutex_A); V(Full_A); 【評分說明】 1）每對信號量的定義及初值正確，給分。 2）每個互斥信號量的P、V 操作使用正確，各給分。 3）每個同步信號量的P、V 操作使用正確，各給分。 4）其他答案酌情給分。 46解答： 1）頁和頁框大小均為4KB。進(jìn)程的虛擬地址空間大小為232/212=220頁。 2） （210*4）/212（頁目錄所占頁數(shù)）+（220*4）/212（頁表所占頁數(shù)）=1025 頁。 3）需要訪問一個二級也表。因為虛擬地址0100 0000H 和0111 2048H 的最高10 位的值都是4，訪 問的是同一個二級頁表。 012 【評分說明】用其他方法計算，思路和結(jié)果正確同樣給分。 47解答： 1） DHCP 服務(wù)器可為主機2主機N動態(tài)分配IP 地址的最大范圍是： 54； 主機 2 發(fā)送的封裝 DHCP Discover 報文的 IP 分組的源 IP 地址和目的 IP 地址分別是 和 55。 2）主機2 發(fā)出的第一個以太網(wǎng)幀的目的MAC 地址是ff-ff-ff-ff-ff-ff；封裝主機2 發(fā)往Internet 的IP 分組的以太網(wǎng)幀的目的MAC 地址是00-a1-a1-a1-a1-a1。 3）主機 1 能訪問 WWW 服務(wù)器，但不能訪問 Internet。由于主機 1 的子網(wǎng)掩碼配置正確而默認(rèn)網(wǎng) 關(guān)IP 地址被錯誤地配置為111