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