計算機專業(yè)基礎(chǔ)綜合直播課件

考研專業(yè)課輔導計算機專業(yè)基礎(chǔ)綜合

考前直播答疑主講教師：趙劍鋒錯過直播的看這里！錄播地址：復制粘貼地址到瀏覽器即可進入看錄播，下面為大家分享下直播課表，想看直播的同學可進群（258435645）等候直播入口！群里也有其他專業(yè)課錄播地址！詳情進群咨詢?nèi)褐鳎。▓D片可放大觀看）

一、考試性質(zhì)

二、考察目標

三、形式和試卷結(jié)構(gòu)

四、考研真題有規(guī)律嗎

五、考研技巧及對策

六、梳理重點、難點

七、歷年真題舉例一、考試性質(zhì)

計算機學科專業(yè)基礎(chǔ)綜合考試是為高等院校和科研院所招收計算機科學與技術(shù)學科的碩士研究生而設(shè)置的具有選拔性質(zhì)的聯(lián)考科目，其目的是科學、公平、有效地測試考生掌握計算機科學與技術(shù)學科大學本科階段專業(yè)基礎(chǔ)知識、基本理論、基本方法的水平和分析問題、解決問題的能力，評價的標準是高等院校計算機科學與技術(shù)學科優(yōu)秀本科畢業(yè)生所能達到的及格或及格以上的水平，以利于各高等院校和科研院所擇優(yōu)選拔，確保碩士研究生的招生質(zhì)量。

二、考察目標

計算機學科專業(yè)基礎(chǔ)綜合考試涵蓋數(shù)據(jù)結(jié)

構(gòu)、計算機組成原理、操作系統(tǒng)和計算機網(wǎng)絡(luò)等學科專業(yè)基礎(chǔ)課程。要求考生系統(tǒng)地掌握上述專業(yè)基礎(chǔ)課程的基本概念、基本原理和基本方法，能夠綜合運用所學的基本原理和基本方法分析、判斷和解決有關(guān)理論問題和實際問題。三、形式和試卷結(jié)構(gòu)

1．試卷滿分及考試時間

本試卷滿分150分，考試時間為180分鐘。

2．答題方式

答題方式為閉卷、筆試。

3．試卷內(nèi)容結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)

45分

計算機組成原理45分

操作系統(tǒng)

35分

計算機網(wǎng)絡(luò)

25分

4．試卷題型結(jié)構(gòu)

單項選擇題80分（40小題，每小題2分）

綜合應用題70分

四、考研真題有規(guī)律嗎

根據(jù)所報考學校，做歷年真題。梳理考點、難點，及其對應的知識點。

做真題要當真做。要按照實戰(zhàn)要求來做。做完之后，要自己做評價，做統(tǒng)計，這樣才能對自己的實際情況有真實的了解。才能找到自己的優(yōu)勢和劣勢，才能知己知彼，有的放矢，打有準備之仗。五、考研技巧及對策

1．適當調(diào)整心情

2．每天抽出時間溫習

3．該得要得，可能舍的盡量得

4．基本功要扎實，比如C語言等

六、梳理重點、難點

直播時間有限，選取一些重點、難點作講

解。

1．數(shù)據(jù)結(jié)構(gòu)的考試內(nèi)容包括：線性表、棧、隊列和數(shù)組、樹和二叉樹、圖、查找和內(nèi)部排

序。重點掌握數(shù)據(jù)結(jié)構(gòu)的三要素：邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)以及在其上定義的各種基本操作。

2．計算機組成原理的考試內(nèi)容包括：計算機系統(tǒng)概述、數(shù)據(jù)的表示和運算、存儲器層次結(jié)

構(gòu)、指令系統(tǒng)、中央處理器、總線、輸入/輸出系統(tǒng)。要重點掌握單處理機計算機系統(tǒng)中各個部件的組成結(jié)構(gòu)和基本工作原理。3．計算機操作系統(tǒng)的考試內(nèi)容主要包括：操作系統(tǒng)概述、進程管理、內(nèi)存管理、文件管理和輸入/輸出管理。重點掌握基本概念和基本原理

上，一些常用的算法，如：并發(fā)和并行的概念、進程的概念與狀態(tài)及相互轉(zhuǎn)化、信號量和P、V操作、死鎖及其預防、避免、檢測與解除、頁式、段式和段頁式存儲管理、磁盤調(diào)度算法、設(shè)備管理等。難點如：運用P、V操作實現(xiàn)進程之間的同步和互斥。4．計算機網(wǎng)絡(luò)的考試內(nèi)容主要圍繞TCP/IP協(xié)議層次的具體展開，包括以下內(nèi)容：物理層、數(shù)據(jù)鏈路層、網(wǎng)絡(luò)層、傳輸層、應用層。每一層的協(xié)議有哪些、重要算法有哪些、算法的內(nèi)容是什么、每一層和上下層之間的關(guān)系、每一層用到的硬件設(shè)備及作用等。四門專業(yè)課的關(guān)系，數(shù)據(jù)結(jié)構(gòu)和組成原理是操作系統(tǒng)的先修課程，計算機網(wǎng)絡(luò)課程相對來說比較獨立，或者說不需要先修課程。計算機組成原理和操作系統(tǒng)這兩門專業(yè)課之間內(nèi)容有一些交叉，都包含了存儲系統(tǒng)和輸入/輸出系統(tǒng)的內(nèi)容，如：內(nèi)存管理的各種頁面置換算法、虛擬存儲器等。對于跨專業(yè)考生而言，要先學完數(shù)據(jù)結(jié)構(gòu)和組成原理后再學習操作系統(tǒng)，否則有些概念和原理難以理解。四門課的復習時間合理分配，重點放在數(shù)據(jù)結(jié)構(gòu)和組成原理上，尤其數(shù)據(jù)結(jié)構(gòu)更要多花一些時間;操作系統(tǒng)和計算機網(wǎng)絡(luò)的很多知識點需要在理解的基礎(chǔ)上進行記憶，相對來說容易一些。難易相對，因人而異，具體情況具體分

析。七、歷年真題舉例

【數(shù)據(jù)結(jié)構(gòu)】

【計算機組成原理】

【計算機操作系統(tǒng)】

【計算機網(wǎng)絡(luò)】

【數(shù)據(jù)結(jié)構(gòu)】

下列程序段的時間復雜度是（

）。

[2014年真題]

count＝0;

for（k＝1;k<＝n;k*=2）

for（j＝1;j<＝n;j++）

count++;

A．Ｏ（log2n）

B．Ｏ（n）

C．Ｏ（nlog2n）

D．Ｏ（n2）

【答案】C

【解析】外部循環(huán)的退出條件是k>n，而對于k，每次循環(huán)都執(zhí)行k＝k*2,所以循環(huán)次數(shù)為

log2n；內(nèi)部循環(huán)的退出條件是j>n,對于j，每次循環(huán)都執(zhí)行j＝j(luò)+1，所以循環(huán)次數(shù)為n次。所以此程序段的時間復雜度為Ｏ（nlog2n），即選C。

5個字符有如下4種編碼方案，不是前綴編碼的是（

）。[2014年真題]

A．01,0000,0001,001,1

B．011,000,001,010,1

C．000,001,010,011,100

D．0,100,110,1110,1100

【答案】D

【解析】前綴編碼是指在一個字符集中，任何一個字符的編碼都不是另一個字符編碼的前

綴。約定左分支表示字符‘0’，右分支表示字符‘1’，則可以用從根結(jié)點到葉子結(jié)點的路徑上的分支字符串作為該葉子結(jié)點字符的編碼。如此得到的編碼必是前綴編碼。D選項中，編碼110是編碼1100的前綴，故不符合前綴編碼的定義。

已知程序如下：

intS（intn）

{return（n<＝0）?0:S（n-1）+n;}

voidmain（）

{cout<<S（1）;}

程序運行時使用棧來保存調(diào)用過程的信息，自棧底到棧頂保存的信息依次對應的是（

）。[2015年真題]

A．main（）→S（1）→S（0）

B．S（0）→S（1）→main（）

C．main（）→S（0）→S（1）

D．S（1）→S（0）→main（）

【答案】A

【解析】函數(shù)S（intn）是一個遞歸函數(shù)：①當實際參數(shù)小于等于零時則返回0，并終止遞

歸；②當實際參數(shù)大于零時則遞歸調(diào)用S（n-

1），并將S（n-1）的結(jié)果加上n作為返回值。程序從main（）函數(shù)開始，首先調(diào)用main（）函

數(shù)；在main（）函數(shù)中調(diào)用S（1）函數(shù)時，將main（）函數(shù)的上下文保存到棧中，并進入函數(shù)S（1）；由于函數(shù)S（1）的實際參數(shù)大于零，需要調(diào)用S（0），故將S（1）函數(shù)的上下文保存到棧

中，進入S（0）；在S（0）中，實際參數(shù)小于等于零，遞歸終止。

一個棧的入棧序列為1,2,3,……,n，其出棧序列是P1，P2，P3,，……，Pn。若P2＝3，則P3可能取值的個數(shù)是（

）。[2013年真題]

A．n-3

B．n-2

C．n-1

D．無法確定

【答案】C

【解析】除了3本身以外,其他的值均可以取到,因此可能取值的個數(shù)為n-1。

先序序列為a，b，c，d的不同二叉樹的個數(shù)是（

）。[2015年真題]

A．13

B．14

C．15

D．16

【答案】B

【解析】二叉樹的先序遍歷定義為：若二叉樹為空，則空操作；否則，訪問根節(jié)點，然后先序遍歷左子樹，最后先序遍歷右子樹。本題中，結(jié)點a為二叉樹的根節(jié)點，左右子樹的先序遍歷可能存在下面四種情況：①左子樹為空，bcd為右子樹；②b為左子樹，cd為右子樹；③bc為左子樹，d為右子樹；④bcd為左子樹，右子樹為空。

然后將左右子樹繼續(xù)分解，如第①種情況的右子樹先序遍歷（bcd）可能有：a．左子樹為空，右子樹為cd；b．左子樹為c，右子樹為d；c．左子樹為cd，右子樹為空。按照這種方法繼續(xù)分解左右子樹，直到不能再分解為止，可得第①和④種情況各包含5種不同情況，第②和③種情況各包含2種情況，因此總共有14種不同的二叉樹。

若對如下的二叉樹進行中序線索化，則結(jié)點x的左、右線索指向的結(jié)點分別是（

）。

[2014年真題]

A．e,c

B．e,a

C．d,c

D．b,a

【答案】D

【解析】此二叉樹的中序遍歷序列為：debxac，由于結(jié)點x左右孩子都為空，所以進行中序線索化時，它的左右孩子指針分別指向它的中序遍歷序列的直接前驅(qū)結(jié)點b和直接后繼結(jié)點a，所以選D。

設(shè)有向圖G＝（V，E），頂點集V＝{v0，v1，v2，v3}，邊集E＝{<v0,v1>，<v0,v2>，<v0,

v3>，<v1,v3>}，若從頂點v0開始對圖進行深度優(yōu)先遍歷，則可能得到的不同遍歷序列個數(shù)是

（

）。[2015年真題]

A．2

B．3

C．4

D．5

v0v2v3v1

【答案】D

【解析】根據(jù)題意知，有向圖的結(jié)構(gòu)如圖所示。深度優(yōu)先遍歷的特點是盡可能先對縱深方向進行搜索，所以可能得到的不同遍歷序列分別

是：

①v0→v2→v1→v3；

②v0→v2→v3→v1；

③v0→v1→v3→v2；

④v0→v3→v2→v1；

⑤v0→v3→v1→v2。下列選項中，不能構(gòu)成折半查找中關(guān)鍵字比較序列的是（

）。[2015年真題]

A．500，200，450，180

B．500，450，200，180

C．180，500，200，450

D．180，200，500，450

【答案】A

【解析】折半查找的過程是：先確定待查找記錄所在的范圍，然后逐步縮小范圍直到找到或找不到該記錄為止。折半查找的關(guān)鍵字序列滿

足：對每一個關(guān)鍵字，其后面的所有關(guān)鍵字序列或者都小于等于該關(guān)鍵字或者都大于等于該關(guān)鍵字。A項錯誤，第三次比較的關(guān)鍵字為450，說明待查關(guān)鍵字位于200～450間，所以第四次比較時不會遇到關(guān)鍵字180。

（15分）用單鏈表保存m個整數(shù)，結(jié)點的結(jié)構(gòu)為：

，且|data|≤n（n為正整數(shù)）?，F(xiàn)要求設(shè)計一個時間復雜度盡可能高效地算法，對于鏈表中data絕對值相等的結(jié)點，僅保留第一次出現(xiàn)的結(jié)點而刪除其余絕對值相等的結(jié)點。

例如，若給定的單鏈表head如下：

則刪除結(jié)點后的head為：

要求：

（1）給出算法的基本思想。

（2）使用C或C++語言，給出單鏈表結(jié)點的數(shù)據(jù)類型定義。

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

（4）說明你所設(shè)計算法的時間復雜度和空間復雜度。[2015年真題]

解：（1）算法思想：

定義一個大小為n的布爾數(shù)組flag，初始時

所有的元素都賦值為false，用來標識遍歷過程中是否出現(xiàn)元素絕對值為flag的結(jié)點。然后遍歷鏈表，遍歷過程中，每一個當前結(jié)點data域的絕對值所對應的flag位：若為真，則刪除該結(jié)點；若為假（false），則將flag位置為真（true）。（2）結(jié)點的數(shù)據(jù)結(jié)構(gòu)定義如下：

（3）boolflag[n]； //全局數(shù)組標志結(jié)點的絕對值是否出現(xiàn)過

Node*deleteABSEnqualNode（Node*head）

{

memset（flag,false,sizeof（flag））;

Node*pre＝head;

Node*p＝head->next;

while（p!＝NULL）{

if（flag[abs（p->data）]）{//如果此絕對值已經(jīng)在結(jié)點值的絕對值中出現(xiàn)過則刪除該結(jié)點

pre->next＝p->next;

deletep;

p＝pre->next;

}else{//否則，將flag中對應的位置置為true，并將指針指向下一個元素

flag[abs（p->data）]＝true;

p＝p->next;

}

}

returnhead;

}

（4）只遍歷一次鏈表，所以時間復雜度為O（m）（m為單鏈表中元素的個數(shù)），申請大小為n的數(shù)組，所以空間復雜度為O（n）（n為結(jié)點絕對值的最大值）。

（8分）已知有5個頂點的圖G如下圖所示。

請回答下列問題。

（1）寫出圖G的鄰接矩陣A（行、列下標從0開始）。

（2）求A2，矩陣A2中位于0行3列元素值的含義是什么？

（3）若已知具有n（n≥2）個頂點的鄰接矩陣為B，則Bm（2≤m≤n）中非零元素的含義是什么？[2015年真題]

解：（1）鄰接矩陣為（2）A2為：

0行3列的元素的含義是頂點0到頂點3之間是相通的，并且路徑長度為2的路徑有3條。

（3）Bm(2≤m≤n)中非零元素的含義是：假設(shè)此頂點位于i行j列，表示從i頂點到j(luò)頂點路徑長度為m的路徑的條數(shù)。

（13分）已知一個整數(shù)序列,其中,若存在

且

，則稱x為A的主元素。例如

，則稱5為主元素；又如

，則A中沒有主元素。假設(shè)A中的n個元素保存在一個一維數(shù)組中，請設(shè)計一個盡可能高效的算法，找出A的主元素。若存在主元素，則輸出該元素；否則輸出-1。要求：

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

（2）根據(jù)設(shè)計思想，采用C、C++或Java語言描述算法，關(guān)鍵之處給出注釋。（3）說明你所設(shè)計算法的時間復雜度和空間復雜度。[2013年真題]

解：

（1）算法的策略是從前向后掃描數(shù)組元素，標記出一個可能成為主元素的元素Num。然后重新計數(shù)，確認Num是否是主元素。

算法可分為以下兩步：

①選取候選的主元素：依次掃描所給數(shù)組

中的每個整數(shù)，將第一個遇到的整數(shù)Num保存到c中，記錄Num的出現(xiàn)次數(shù)為1；若遇到的下一個整數(shù)仍等于Num，則計數(shù)加1，否則計數(shù)減1；當計數(shù)減到0時，將遇到的下一個整數(shù)保存到c中，計數(shù)重新記為1，開始新一輪計數(shù)，即從當前位置開始重復上述過程，直到掃描完全部數(shù)組元素。

②判斷c中元素是否是真正的主元素，再次

掃描該數(shù)組，統(tǒng)計c中元素出現(xiàn)的次數(shù)，若大于n/2，則為主元素；否則，序列中不存在主元素。

（2）算法實現(xiàn)如下：

（3）時間復雜度為O（n）,空間復雜度為O（1）。

【計算機組成原理】

由3個“1”和5個“0”組成的8位二進制補

碼，能表示的最小整數(shù)是（

）。[2015年真

題]

A．-126B．-125C．-32D．-3

【答案】B

【解析】能表示的最小整數(shù)一定是負數(shù)，

符號位占用1個“1”；負數(shù)的補碼和原碼的轉(zhuǎn)

化是：原碼符號位不變，數(shù)值部分按位取反，末位加“1”。因此最小的整數(shù)的補碼是“10000011”，原碼為“11111101”，即-12510。假定主存地址為32位，按字節(jié)編址，主存和Cache之間采用直接映射方式，主存塊大小為4個字，每字32位，采用回寫（WriteBack）方式，則能存放4K字數(shù)據(jù)的Cache的總?cè)萘康奈粩?shù)至少是（

）。[2015年真題]

A．146K

B．147K

C．148K

D．158K

【解析】Cache和主存直接映射方式的規(guī)則

為：主存儲器分為若干區(qū)，每個區(qū)與緩存容量相同；每個區(qū)分為若干數(shù)據(jù)塊，每個塊和緩存塊容量相同；主存中某塊只能映象到Cache的一個特定的塊中。本題中，Cache總共存放4K字數(shù)據(jù)，塊大小為4個字，因此Cache被分為4K/4＝1K個塊，由10位表示。塊內(nèi)共16字節(jié)，所以由4位表示，于是標記位為32-10-4＝18位。所以，Cache的每一行需要包含所存的數(shù)據(jù)

4個字，每個字32位，18位標記位、一個有效位

和一個一致性維護位（回寫方式），因此總?cè)萘繛椋海?×32+18+1+1）×1K＝148K。

【答案】C

若磁盤轉(zhuǎn)速為7200轉(zhuǎn)/分，平均尋道時間為8ms，每個磁道包含1000個扇區(qū)，則訪問一個扇區(qū)的平均存取時間大約是（

）。[2015年真題]

A．8.1ms

B．12.2ms

C．16.3ms

D．20.5ms

【答案】B

【解析】磁盤的平均尋址時間包括平均尋道時間和平均等待時間。平均尋道時間為8ms，平均等待時間與磁盤轉(zhuǎn)速有關(guān)，為[60s/7200]×0.5≈4.165ms。磁盤的存取一個扇區(qū)的時間為60s/（7200×1000）≈0.0083ms。因此總的時間為：8+4.165+0.0083＝12.1733ms。處理外部中斷時，應該由操作系統(tǒng)保存的是（

）。[2015年真題]

A．程序計數(shù)器（PC）的內(nèi)容

B．通用寄存器的內(nèi)容

C．快表（TLB）的內(nèi)容

D．Cache中的內(nèi)容

【答案】B

【解析】外部中斷處理過程首先要保護現(xiàn)

場，使得中斷處理完后能夠恢復程序的狀態(tài)繼續(xù)執(zhí)行。保護現(xiàn)場有兩個含義：①由中斷隱指令保存程序的斷點（程序計數(shù)器）；②由中斷服務(wù)程序保存通用寄存器和狀態(tài)寄存器的內(nèi)容。中斷服務(wù)程序是操作系統(tǒng)的一部分。

若系統(tǒng)S1采用死鎖避免方法，S2采用死鎖檢測方法，下列敘述中正確的是（

）。[2015年真題]

Ⅰ．S1會限制用戶申請資源的順序，而S2不會

Ⅱ．S1需要進程運行所需資源總量信息，而S2不需要

Ⅲ．S1不會給可能導致死鎖的進程分配資

源，而S2會

A．僅Ⅰ、Ⅱ

B．僅Ⅱ、Ⅲ

C．僅Ⅰ、Ⅲ

D．Ⅰ、Ⅱ、Ⅲ

【答案】B

【解析】死鎖避免的策略是：必須知道將來的資源需求，以尋找可能的安全允許順序，如果不存在安全序列就阻塞；死鎖檢測的策略是：只要允許就分配資源，它只定期檢查死鎖是否已經(jīng)發(fā)生，如果發(fā)生就通過剝奪解除死鎖。在請求分頁系統(tǒng)中，頁面分配策略與頁面置換策略不能組合使用的是（

）。[2015年真

題]

A．可變分配，全局置換

B．可變分配，局部置換

C．固定分配，全局置換

D．固定分配，局部置換

【答案】C

【解析】分配和置換策略有下面三個組合：①固定分配、局部置換；②可變分配、全局置

換；③可變分配、局部置換。固定分配是指基于進程的類型（交互型或批處理型等），或根據(jù)程序員、程序管理員的建議，為每個進程分配一定數(shù)目的物理塊，在整個運行期間都不再改變，采用該策略時，如果進程在運行中發(fā)現(xiàn)缺頁，則只能從該進程在內(nèi)存的n個頁面中選出一個頁換出，然后再調(diào)入一頁，才能保證分配給該進程的內(nèi)存空間不變，因此不能有固定分配，全局置換組合

文件系統(tǒng)用位圖法表示磁盤空間的分配情況，位圖存于磁盤的32～127號塊中，每個盤塊占1024個字節(jié)，盤塊和塊內(nèi)字節(jié)均從0開始編號。假設(shè)要釋放的盤塊號為409612，則位圖中要修改的位所在的盤塊號和塊內(nèi)字節(jié)序號分別是

（

）。[2015年真題]

A．81、1

B．81、2

C．82、1

D．82、2

【答案】C

【解析】位圖中要修改的位所在的盤塊號=起始塊號+└盤塊號/（1024×8）┘=32+└409612/（1024×8）┘=32+50=82，塊內(nèi)字節(jié)號=└（盤塊號%（1024×8））/8┘=1。

某硬盤有200個磁道(最外側(cè)磁道號為0)，磁道訪問請求序列為：130，42，180，15，199，當前磁頭位于第58號磁道并從外側(cè)向內(nèi)側(cè)移動。按照SCAN調(diào)度方法處理完上述請求后，磁頭移過的磁道數(shù)是（

）。[2015年真題]

A．208

B．287

C．325

D．382

【答案】C

【解析】SCAN算法是在磁頭當前移動方向

上選擇與當前磁頭所在磁道距離最近的請求作為下一次服務(wù)的對象。當前磁頭位于第58號磁道并從外側(cè)向內(nèi)側(cè)移動，所以先依次訪問130、180和199，然后再返回從內(nèi)側(cè)向外側(cè)移動，依次訪問42和15，那么磁頭需要移動的磁道數(shù)是（199-58）+（199-15）=325。（13分）某16位計算機的主存按字節(jié)編址，存取單位為16位；采用16位定長指令字格式；CPU采用單總線結(jié)構(gòu)，主要部分如下圖所示。圖中R0～R3為通用寄存器；T為暫存器；SR為移位寄存

器，可實現(xiàn)直送（mov）、左移一位（left）和

右移一位（right）3種操作，控制信號為SRop，SR的輸出由信號SRout控制；ALU可實現(xiàn)直送A（mova）、A加B（add）、A減B（sub）、A與B（

and）、A或B（or）、非A（not）、A加1（inc）7種操作，控制信號為ALUop。

請回答下列問題。

（1）圖中哪些寄存器是程序員可見的？為何要設(shè)置暫存器T？（2）控制信號ALUop和SRop的位數(shù)至少各是多少？

（3）控制信號SRout所控制部件的名稱或作用是什么？

（4）端點①～⑨中，哪些端點須連接到控制部件的輸出端？

（5）為完善單總線數(shù)據(jù)通路，需要在端點①～⑨中相應的端點之間添加必要的連線。寫出連線的起點和終點，以正確表示數(shù)據(jù)的流動方向。

（6）為什么二路選擇器MUX的一個輸入端是

2？[2015年真題]

解：（1）圖中程序員可見的寄存器有通用寄存器R0～R3和程序計數(shù)器PC；當執(zhí)行算術(shù)或邏輯操作時，由于ALU本身是沒有內(nèi)部存儲功能的組合電路，因此如要執(zhí)行加法運算，被相加的兩個數(shù)必須在ALU的兩個輸入端同時有效，因此設(shè)置暫存器T用于暫存數(shù)據(jù)總線發(fā)送的數(shù)據(jù)。

【解析】程序員可見的寄存器包括：程序計數(shù)器、通用寄存器和狀態(tài)寄存器。其他的IR、MAR和MDR等是CPU的內(nèi)部工作寄存器，對程序員不可見。

（2）ALUop和SRop的位數(shù)分別為3，2。

【解析】ALU中共有7種命令，用三位即可區(qū)別表示；SR共有三種命令，用二位二進制即可表示。

（3）SRout所控制的部件是一個三態(tài)門，

用于控制移位器與總線之間數(shù)據(jù)通路的連接與斷開。

（4）須連接到控制部件的輸出端端口有①②③⑤⑧。

【解析】操作符命令，傳輸?shù)榷夹枰刂菩盘栠M行控制。

（5）⑥→⑨，⑦→④。（6）數(shù)據(jù)寬度是16位，以字節(jié)編址，輸入端是2是為了增加地址獲取ALU的第二個操作數(shù)，也就是執(zhí)行（PC）+2操作。

（8分）某計算機主存按字節(jié)編址，邏輯地址和物理地址都是32位，頁表項大小為4字節(jié)。請回答下列問題。

（1）若使用一級頁表的分頁存儲管理方式，邏輯地址結(jié)構(gòu)為：

則頁的大小是多少字節(jié)？頁表最大占用多少字節(jié)？

（2）若使用二級頁表的分頁存儲管理方式，邏輯地址結(jié)構(gòu)為：

設(shè)邏輯地址為LA，請分別給出其對應的頁目錄號和頁表索引的表達式。

（3）采用（1）中的分頁存儲管理方式，一個代碼段起始邏輯地址為00008000H，其長度為8KB，被裝載到從物理地址00900000H開始的連續(xù)主存空間中。頁表從主存00200000H開始的物理地址處連續(xù)存放，如下圖所示（地址大小自下向上遞增）。請計算出該代碼段對應的兩個頁表項的物理地址、這兩個頁表項中的頁框號以及代碼頁面2的起始物理地址。[2013年真題]

解：

（1）因為頁內(nèi)偏移量是12位，所以頁大小為4KB。

頁表項數(shù)為232/4K＝220

，該一級頁表最大為220×4B＝4MB。

（2）頁目錄號可表示為：(((unsignedint)(LA))>>22)&0x3FF。

頁表索引可表示為：(((unsignedint)(LA))>>12)&0x3FF。

（3）代碼頁面1的邏輯地址為00008000H，表明其位于第8個頁處，對應頁表中的第8個頁表項，所以第8個頁表項的物理地址＝頁表起始地址+8×頁表項的字節(jié)數(shù)＝00200000H+8×4＝00200020H，如下圖所示。

【計算機操作系統(tǒng)】

下列調(diào)度算法中，不可能導致饑餓現(xiàn)象的是（

）。[2014年真題]

A．時間片輪轉(zhuǎn)

B．靜態(tài)優(yōu)先數(shù)調(diào)度

C．非搶占式短作業(yè)優(yōu)先

D．搶占式短作業(yè)優(yōu)先

【答案】A

【解析】時間片輪轉(zhuǎn)方法能在一個周期內(nèi)使每個進程都得到一個時間片的CPU使用時間，不會產(chǎn)生饑餓的現(xiàn)象，其余三個都會產(chǎn)生饑餓。

下列指令中，不能在用戶態(tài)執(zhí)行的是

（

）。[2014年真題]

A．trap指令

B．跳轉(zhuǎn)指令

C．壓棧指令

D．關(guān)中斷指令

【答案】D

【解析】關(guān)中斷指令必須在核心態(tài)才能執(zhí)

行，trap指令可以在用戶態(tài)下執(zhí)行，執(zhí)行了就轉(zhuǎn)到核心態(tài)，跳轉(zhuǎn)與壓棧指令都是可以在用戶態(tài)下執(zhí)行的指令。

現(xiàn)有一個容量為10GB的磁盤分區(qū)，磁盤空間以簇（Cluster）為單位進行分配，簇的大小為4KB，若采用位圖法管理該分區(qū)的空閑空間，即用一位（bit）標識一個簇是否被分配，則存放該位圖所需簇的個數(shù)為（

）。[2014年真題]

A．80

B．320

C．80K

D．320K

【答案】A

【解析】磁盤的簇的個數(shù)為：10GB/4KB＝2.5*220個，而一個簇的位示圖能管理的簇的個數(shù)為：4KB*8＝32K，所以需要簇的個數(shù)為2.5*220/32K＝80個。

下列措施中，能加快虛實地址轉(zhuǎn)換的是

（

）。[2014年真題]

1．增大快表（TLB）容量2．讓頁表常駐內(nèi)存3．增大交換區(qū)（swap）

A．僅1

B．僅2

C．僅1,2

D．僅2,3

【答案】C

【解析】加大快表容量能增加快表的命中率，即減少了訪問內(nèi)存的次數(shù)；讓頁表常駐內(nèi)存能夠使CPU不用訪問內(nèi)存找頁表，從而加快了虛實地址轉(zhuǎn)換。而增大交換區(qū)只是對內(nèi)存的一種擴充作用，對虛實地址轉(zhuǎn)換并無影響。

下列關(guān)于管道（Pipe）通信的敘述中，正確的是（

）。[2014年真題]

A．一個管道可實現(xiàn)雙向數(shù)據(jù)傳輸

B．管道的容量僅受磁盤容量大小限制

C．進程對管道進行讀操作和寫操作都可能被阻塞

D．一個管道只能有一個讀進程或一個寫進程對其操作

【答案】C

【解析】寫進程對管道寫入數(shù)據(jù)，讀進程對管道進行讀取數(shù)據(jù)，管道只能半雙工通信，即某一時刻只能單向傳輸。管道為空，則讀操作被阻塞；管道滿時，則寫進程被阻塞，所以C正確。

（7分）某博物館最多可容納500人同時參

觀，有一個出入口，該出入口一次僅允許一個人通過。參觀者的活動描述如下：

[2013年真題]

cobegin

參觀者進程i：

{

…

進門；

…

參觀；

…

出門；

…

}

coend

請?zhí)砑颖匾男盘柫亢蚉、V（或wait（）、signal（））操作，以實現(xiàn)上述操作過程中的互斥與同步。要求寫出完整的過程，說明信號量含義并賦初值。[2013年真題]

解：

定義兩個信號量

Semaphoreempty＝500;//博物館可以容納的最多人數(shù)

Semaphoremutex＝1;//用于出入口資源的控制

cobegin

參觀者進程i:

{

……

P（empty）;

P（mutex）;

進門;

V（mutex）;

參觀;

P（mutex）;

出門;

V（mutex）;

V（empty）;

……

}

coend

（9分）有A、B兩人通過信箱進行辯論，每

人都從自己的信箱中取得對方的問題，將答案和向?qū)Ψ教岢龅男聠栴}組成一個郵件放入對方的郵箱中。假設(shè)A的信箱最多放M個郵件，B的信箱最多放N個郵件。初始時A的信箱中有x個郵件（0<x<M），B的信箱中有y個郵件（0<y<N）。辯論者每取出一個郵件，郵件數(shù)減1。A、B兩人的操作過程描述如下：

CoBegin

A{

while（TRUE）{

從A的信箱中取出一個郵件；

回答問題并提出一個新問題；

將新郵件放入B的信箱；

}

}

B{

while（TRUE）{

從B的信箱中取出一個郵件；

回答問題并提出一個新問題；

將新郵件放入A的信箱；

}

}

CoEnd

當信箱不為空時，辯論者才能從信箱中取郵件，否則等待。當信箱不滿時，辯論者才能將新郵件放入信箱，否則等待。

請?zhí)砑颖匾男盘柫亢蚉、V（或wait、signal）操作，以實現(xiàn)上述過程的同步。要求寫出完整過程，并說明信號量的含義和初值。[2015年真題]

解：首先定義兩個互斥信號量：mutexA和mutexB，初始時為1，分別用來實現(xiàn)對A的郵箱和B的郵箱的互斥使用；然后針對A的郵箱再定義兩個信號量emptyA和fullA，初值分別為M–x和x，分別表示信箱中仍能存放信的數(shù)量和已經(jīng)存放的信的數(shù)量，同理設(shè)置emptyB和fullB，初值為N–y和y。

初始代碼：

semaphoremutexA＝1，mutexB＝1；

semaphoreemptyA＝M–x，fullA＝x；

semaphoreemptyB＝N–y,，fullB＝y(tǒng)；

通信代碼：

CoBegin

A｛

while（TRUE）{

P（fullA）;

P（mutexA）;

從A的信箱中取出一個郵件;

V（mutexA）;

V（emptyA）;

回答問題并提出一個新問題;

P（emptyB）;

P（mutexB）;

將新郵件放入B的信箱;

V（mutexB）;

V（fullB）;

}

}

B{

while（TRUE）{

P（fullB）;

P（mutexB）;

從B的信箱中取出一個郵件;

V（mutexB）;

V（emptyB）;

回答問題并提出一個新問題;

P（emptyA）;

P（mutexA）;

將新郵件放入A的信箱;

V（mutexA）;

V（fullA）;

}

}

【計算機網(wǎng)絡(luò)】

使用兩種編碼方案對比特流01100111進行編碼的結(jié)果如下圖所示，編碼1和編碼2分別是

（

）。[2015年真題]

A．NRZ和曼徹斯特編碼

B．NRZ和差分曼徹斯特編碼

C．NRZI和曼徹斯特編碼

D．NRZI和差分曼徹斯特編碼

【答案】A

【解析】NRZ編碼用高電平表示1，低電平表示0。NRZI編碼用電平的一次翻轉(zhuǎn)來表示1，與前一個電平相同的電平表示0。曼徹斯特編碼是根據(jù)每一個碼元中間的電平變化來編碼的，用正的電壓跳變表示1，用負的電壓跳變表示0。差分曼徹斯特編碼在信號位開始時改變信號極性，表示0，在信號位開始時不改變信號極性，表示1。下列關(guān)于CSMA／CD協(xié)議的敘述中，錯誤的是（

）。[2015年真題]

A．邊發(fā)送數(shù)據(jù)幀，邊檢測是否發(fā)生沖突

B．適用于無線網(wǎng)絡(luò)，以實現(xiàn)無線鏈路共享

C．需要根據(jù)網(wǎng)絡(luò)跨距和數(shù)據(jù)傳輸速率限定最小幀長

D．當信號傳播延遲趨近0時，信道利用率趨近100％

【答案】B

【解析】CSMA／CD協(xié)議是用于有線網(wǎng)絡(luò)的協(xié)議。

下列關(guān)于交換機的敘述中，正確的是

（

）。[2015年真題]

A．以太網(wǎng)交換機本質(zhì)上是一種多端口網(wǎng)橋

B．通過交換機互連的一組工作站構(gòu)成一個沖突域

C．交換機每個端口所連網(wǎng)絡(luò)構(gòu)成一個獨立的廣播域

D．以太網(wǎng)交換機可實現(xiàn)采用不同網(wǎng)絡(luò)層協(xié)議的網(wǎng)絡(luò)互聯(lián)

【答案】A

【解析】交換機實質(zhì)上就是一個多端口網(wǎng)橋是數(shù)據(jù)鏈路層上的網(wǎng)絡(luò)設(shè)備。B選項錯，交換機能經(jīng)濟地將網(wǎng)絡(luò)分成小的沖突域，為每個工作站提供更高的帶寬。C選項錯，路由器是用來構(gòu)成廣播域的設(shè)備。D選項錯，交換機是數(shù)據(jù)鏈路層上的網(wǎng)絡(luò)設(shè)備。某路由器的路由表如下表所示：

若路由器