2015年全國碩士研究生入學統一考試計算機科學與技術學科聯考計算機學科專業基礎綜合真題及詳解

一、單項選擇題：1～40小題，每小題2分，共80分。下列每題給出的四個選項中，只有一個選項符合題目要求。請在答題卡上將所選項的字母涂黑。

1已知程序如下：

程序運行時使用棧來保存調用過程的信息，自棧底到棧頂保存的信息依次對應的是（　　）。

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

【解析】函數S（int n）是一個遞歸函數：①當實際參數小于等于零時則返回0，并終止遞歸；②當實際參數大于零時則遞歸調用S（n－1），并將S（n－1）的結果加上n作為返回值。程序從main（）函數開始，首先調用main（）函數；在main（）函數中調用S（1）函數時，將main（）函數的上下文保存到棧中，并進入函數S（1）；由于函數S（1）的實際參數大于零，需要調用S（0），故將S（1）函數的上下文保存到棧中，進入S（0）；在S（0）中，實際參數小于等于零，遞歸終止。

2先序序列為a，b，c，d的不同二叉樹的個數是（　　）。

A．13

B．14

C．15

D．16

【答案】B

【解析】二叉樹的先序遍歷定義為：若二叉樹為空，則空操作；否則，訪問根節點，然后先序遍歷左子樹，最后先序遍歷右子樹。本題中，結點a為二叉樹的根節點，左右子樹的先序遍歷可能存在下面四種情況：①左子樹為空，bcd為右子樹；②b為左子樹，cd為右子樹；③bc為左子樹，d為右子樹；④bcd為左子樹，右子樹為空。然后將左右子樹繼續分解，如第①種情況的右子樹先序遍歷（bcd）可能有：a．左子樹為空，右子樹為cd；b．左子樹為c，右子樹為d；c．左子樹為cd，右子樹為空。按照這種方法繼續分解左右子樹，直到不能再分解為止，可得第①和④種情況各包含5種不同情況，第②和③種情況各包含2種情況，因此總共有14種不同的二叉樹。

3下列選項給出的是從根分別到達兩個葉節點路徑上的權值序列，能屬于同一棵哈夫曼樹的是（　　）。

A．24，10，5和24，10，7

B．24，10，5和24，12，7

C．24，10，10和24，14，11

D．24，10，5和24，14，6

【答案】D

【解析】哈夫曼樹是帶權路徑長度最短的二叉樹。由根節點出發到兩個葉子節路徑中，第二個被訪問的兩個結點的權值要么相等，要么和為根節點的權值，故B項錯誤。同理，通過第三個被訪問的節點排除A項。C項，由兩條路徑可推出三個葉子節點的權值分別是：3、10和11，而根據哈夫曼樹的定義可知，權值為3的節點應該和權值為10的結點結合，故C項錯誤。D項，反推出有四個葉子節點，權值分別為：5、5、6和8，滿足哈夫曼樹的條件。

4現在有一顆無重復關鍵字的平衡二叉樹（AVL樹），對其進行中序遍歷可得到一個降序序列。下列關于該平衡二叉樹的敘述中，正確的是（　　）。

A．根節點的度一定為2

B．樹中最小元素一定是葉節點

C．最后插入的元素一定是葉節點

D．樹中最大元素一定是無左子樹

【答案】D

【解析】二叉樹的中序遍歷定義是“若二叉樹為空，則空操作；否則：①中序遍歷左子樹；②訪問根節點；③中序遍歷右子樹”。A項錯誤，當樹中僅有一個或者兩個結點時，根節點的度就可能不為2；B項錯誤，樹中最小元素是中序遍歷時最后訪問的節點，當沒有右子樹時，最后訪問的節點是根節點；C項錯誤，當最后插入的元素破壞樹的平衡后，樹會進行調整，使其成為中間節點；D項正確，由中序遍歷的特點可知，左子樹的值大于根節點，所以最大元素一定沒有左子樹。

5設有向圖G＝（V，E），頂點集V＝{V0，V1，V2，V3}，邊集E＝{＜V0，V1＞，＜V0，V2＞，＜V0，V3＞，＜V1，V3＞}，若從頂點V0開始對圖進行深度優先遍歷，則可能得到的不同遍歷序列個數是（　　）。

A．2

B．3

C．4

D．5

【答案】D

【解析】根據題意知有向圖的結構如圖所示。深度優先遍歷的特點是盡可能先對縱深方向進行搜索，所以可能得到的不同遍歷序列分別是：①V0→V2→V1→V3；②V0→V2→V3→V1；③V0→V1→V3→V2；④V0→V3→V2→V1；⑤V0→V3→V1→V2。

6暫缺

7下列選項中，不能構成折半查找中關鍵字比較序列的是（　　）。

A．500，200，450，180

B．500，450，200，180

C．180，500，200，450

D．180，200，500，450

【答案】A

【解析】折半查找的過程是：先確定待查找記錄所在的范圍，然后逐步縮小范圍直到找到或找不到該記錄為止。折半查找的關鍵字序列滿足：對每一個關鍵字，其后面的所有關鍵字序列或者都小于等于該關鍵字或者都大于等于該關鍵字。A項錯誤，第三次比較的關鍵字為450，說明待查關鍵字位于200～450間，所以第四次比較時不會遇到關鍵字180。

8已知字符串S為“abaabaabacacaabaabcc”，模式串t為“abaabc”，采用KMP算法進行匹配，第一次出現“失配”（s[i]!＝t[i]）時，i＝j＝5，則下次開始匹配時，i和j的值分別是（　　）。

A．i＝1，j＝0

B．i＝5，j＝0

C．i＝5，j＝2

D．i＝6，j＝2

【答案】C

【解析】模式匹配（KMP）算法對普通的暴力匹配的改進在于：每當匹配過程中匹配失敗時，主串（本題為S）的指針（i）不需要回溯，而是利用已經得到的“部分匹配”的結果將模式串（t）向右“滑動”盡可能遠的一段距離后，繼續進行比較。模式串“滑動”的距離是由模式串（t）本身決定的，即t的子串t[0…j－1]中前綴串和后綴串相等的最長長度。本題中第一次失配i＝5，字串為“abaab”，其相等且最長的前后綴為“ab”，一次下一個j＝2。

9下列排序算法中元素的移動次數和關鍵字的初始排列次序無關的是（　　）。

A．直接插入排序

B．起泡排序

C．基數排序

D．快速排序

【答案】C

【解析】C項，基數排序是采用分配和收集實現的，不需要進行關鍵字的比較。ABD三項都依賴關鍵字的比較，不同的初始排列次序下元素移動的次數有很大變化，最好情況元素正序，則不用移動，最壞情況元素反序，則需要移動n（n－1）/2次（n為元素個數）。

10已知小根堆為8，15，10，21，34，16，12，刪除關鍵字8之后需重建堆，在此過程中，關鍵字之間的比較數是（　　）。

A．1

B．2

C．3

D．4

【答案】C

【解析】堆排序中，依次輸出堆頂的最小值，然后重新調整堆，如此反復執行，便得到一個有序序列。本題中，刪除堆頂元素8后將最后一個元素12置于堆頂，然后調整堆：首先與15比較，12小于15，所以不用交換；然后與10比較，因為10小于12，所以交換10和12的位置；調整后12再與16比較，12小于16，調整堆過程結束。因此12共與15、10、16進行了三次比較。

11希爾排序的組內排序采用的是（　　）。

A．直接插入排序

B．折半插入排序

C．快速排序

D．歸并排序

【答案】A

【解析】希爾排序基本思想是：先將整個待排元素序列按某個增量分割成若干個子序列，在子序列內進行直接插入排序，然后依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序。

12計算機硬件能夠直接執行的是（　　）。

Ⅰ．機器語言程序

Ⅱ．匯編語言程序

Ⅲ．硬件描述語言程序

A．僅Ⅰ

B．僅Ⅰ Ⅱ

C．僅Ⅰ Ⅲ

D．ⅠⅡ Ⅲ

【答案】A

【解析】機器語言是計算機唯一可以直接執行的語言。匯編語言屬于低級語言，但其源程必須要翻譯成目標程序成為機器語言程序后才能被直接執行。硬件描述語言是電子系統硬件行為描述、結構描述、數據流描述的語言。

13由3個“1”和5個“0”組成的8位二進制補碼，能表示的最小整數是（　　）。

A．－126

B．－125

C．－32

D．－3

【答案】B

【解析】能表示的最小整數一定是負數，符號位占用1個“1”；負數的補碼和原碼的轉化是：原碼符號位不變，數值部分按位取反，末位加“1”。因此最小的整數的補碼是“10000011”，原碼為“11111101”，即－125₁₀。

14下列有關浮點數加減運算的敘述中，正確的是（　　）。

Ⅰ．對階操作不會引起階碼上溢或下溢

Ⅱ．右規和尾數舍入都可能引起階碼上溢

Ⅲ．左規時可能引起階碼下溢

Ⅳ．尾數溢出時結果不一定溢出

A．Ⅱ、Ⅲ

B．Ⅰ、Ⅱ、Ⅳ

C．Ⅰ、Ⅲ、Ⅳ

D．Ⅰ、Ⅱ、Ⅲ、Ⅳ

【答案】D

【解析】浮點數的加減運算步驟包括：①對階，使兩個操作數的小數點位置對齊，階碼小的尾數右移，可能產生溢出，但是階碼不會溢出；②尾數求和，將對階后的尾數按定點數加（減）運算規則運算；③規格化，包括左規和右規，左規時階碼減少，可能出現階碼下溢，而右規時，階碼增加可能出現階碼上溢；④舍入，該過程可能需要右規調整，因此可能出現階碼上溢；⑤溢出判斷，浮點數的溢出與否是由階碼的符號決定的，而不是由尾數溢出判斷的，因此尾數溢出時結果不一定溢出。因此Ⅰ、Ⅱ、Ⅲ、Ⅳ均正確。

15假定主存地址為32位，按字節編址，主存和Cache之間采用直接映射方式，主存塊大小為4個字，每字32位，采用回寫（Write Back）方式，則能存放4K字數據的Cache的總容量的位數至少是（　　）。

A．146k

B．147K

C．148K

D．158K

【答案】B

【解析】Cache和主存直接映射方式的規則為：主存儲器分為若干區，每個區與緩存容量相同；每個區分為若干數據塊，每個塊和緩存塊容量相同；主存中某塊只能映象到Cache的一個特定的塊中。本題中，Cache總共存放4K字數據，塊大小為4個字，因此cache被分為4K/4＝1K個塊，由10位表示。塊內共16字節，所以由4位表示，于是標記位為32－10－14＝18位。所以，Cache的每一行需要包含所存的數據4個字，每個字32位，18位標記位和一個有效位，因此總容量為：（4*32＋18＋1）*1K＝147K。

16假定編譯器將賦值語句“x＝x＋3；”轉換為指令“add xaddt，3”，其中xaddt是x對應的存儲單元地址，若執行該指令的計算機采用頁式虛擬存儲管理方式，并配有相應的TLB，且Cache使用直寫（Write Through）方式，則完成該指令功能需要訪問主存的次數至少是（　　）。

A．0

B．1

C．2

D．3

【答案】C

【解析】采用頁式虛擬存儲管理方式時，若頁表全部放在內存中，則存取一個數據最少要訪問兩次內存：第一次是訪問頁表，得到所存取的數據或指令的物理地址；第二次根據該地址存取數據或指令。在配有TLB的頁式虛擬管理方式中，如果給出的地址在TLB中，則直接根據該地址取數據或指令，僅需要一次訪問內存。Cache使用直寫方式時，計算完需要將數據寫回到內存中，因此完成整個指令功能至少需要訪問主存2次。

17下列存儲器中，在工作期間需要周期性刷新的是（　　）。

A．SRAM

B．SDRAM

C．ROM

D．FLASH

【答案】B

【解析】動態隨機存儲器（DRAM）是利用存儲元電路中柵極電容上的電荷來存儲信息的，電容上的電荷一般只能維持1～2ms，因此即使電源不掉電，信息也會自動消失。為此，每隔一定時間必須刷新。

18某計算機使用4體交叉存儲器，假定在存儲器總線上出現的主存地址（十進制）序列為8005，8006，8007，8008，8001，8002，8003，8004，8000，則可能發生發生緩存沖突的地址對是（　　）。

A．8004、8008

B．8002、8007

C．8001、8008

D．8000、8004

【答案】D

【解析】交叉存儲器，又稱低位交叉編址，即低位地址為體號，高位地址為體內地址。本題中，主存地址對應的體號分別是：1，2，3，4，1，2，3，4，4。地址為8004和8000都是存取的四號儲存器，可能導致8004存儲還未完成而又存取8000地址，因此可能發生緩存沖突。

19下列有關總線定時的敘述中，錯誤的是（　　）。

A．異步通信方式中，全互鎖協議最慢

B．異步通信方式中，非互鎖協議的可靠性最差

C．同步通信方式中，同步時鐘信號可由多設備提供

D．半同步通信方式中，握手信號的采樣由同步時鐘控制

【答案】C

【解析】A項正確，異步通信方式中，全互鎖協議最慢，主從模塊都需要等待確認后才能撤銷其信號；B項正確，異步通信方式中，非互鎖協議沒有相互確認機制，因此可靠性最差；C項錯誤，同步通信要遵循統一的時鐘信號，不能由多設備提供；D項正確，半同步通信方式中，握手信號的采樣由同步時鐘控制。

20若磁盤轉速為7200轉/分，平均尋道時間為8ms，每個磁道包含1000個扇區，則訪問一個扇區的平均存取時間大約是（　　）。

A．8.1ms

B．12.2ms

C．16.3ms

D．20.5ms

【答案】B

【解析】磁盤的平均尋址時間包括平均尋道時間和平均等待時間。平均尋道時間為8ms，平均等待時間與磁盤轉速有關，為[60s/7200]*0.5≈4.165ms。磁盤的存取一個扇區的時間為60s/（7200*1000）≈0.0083ms。因此總的時間為：8＋4.165＋0.0083＝12.1733ms。

21在采用中斷I/O方式控制打印輸出的情況下，CPU和打印控制接口中的I/O端口之間交換的信息不可能是（　　）。

A．打印字符

B．主存地址

C．設備狀態

D．控制命令

【答案】B

【解析】I/O接口的功能包括：①選址功能；②傳送命令功能；③傳送數據功能；④反映I/O設備工作狀態功能。A項為數據，C項為設備狀態，D項為命令。B項，主存地址在中斷方式控制下是不需要的，因此，它不可能是CPU和打印控制接口中的I/O端口之間交換的信息。

22內部異常（內中斷）可分為故障（fault）、陷阱（trap）和終止（abort）三類。下列有關內部異常的敘述中，錯誤的（　　）。

A．內部異常的產生與當前執行指令相關

B．內部異常的檢測由CPU內部邏輯實現

C．內部異常的響應發生在指令執行過程中

D．內部異常處理后返回到發生異常的指令繼續執行

【答案】D

【解析】內中斷分為：①由軟中斷指令啟動的中斷；②在一定條件下由CPU自身啟動的中斷。D項錯誤，如突然掉電引發的內中斷經處理后不會繼續執行。

23處理外部中斷時，應該由操作系統保存的是（　　）。

A．程序計數器（PC）的內容

B．通用寄存器的內容

C．快表（TLB）的內容

D．Cache中的內容

【答案】B

【解析】外部中斷處理過程首先要保護現場，使得中斷處理完后能夠恢復程序的狀態繼續執行。保護現場有兩個含義：①由中斷隱指令保存程序的斷點（程序計數器）；②由中斷服務程序保存通用寄存器和狀態寄存器的內容。中斷服務程序是操作系統的一部分。

24假定下列指令已裝入指令寄存器。則執行時不可能導致CPU從用戶態變為內核態（系統態）的是（　　）。

A．DIV R0，R1；（R0）/（R1）→R0

B．INT n；產生軟中斷

C．NOT R0；寄存器R0的內容取非

D．MOV R0，addr；把地址處的內存數據放入寄存器R0中

【答案】C

【解析】A項，除法操作出現除數為零的情況時，會產生內中斷，CPU切換為內核態進行中斷處理；B項，直接產生中斷，會切換到內核態；D項，addr出現非法地址，會出現中斷，進而切換到內核態。

25下列選項中會導致進程從執行態變為就緒態的事件是（　　）。

A．執行P（wait）操作

B．申請內存失敗

C．啟動I/O設備

D．被高優先級進程搶占

【答案】D

【解析】D項，被高優先級進程搶占，進程會由執行態變為就緒態。ABC三項，程序由于缺少資源而由執行態轉為阻塞態。

26若系統S1采用死鎖避免方法，S2采用死鎖檢測方法，下列敘述中正確的是（　　）。

Ⅰ．S1會限制用戶申請資源的順序

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

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

A．Ⅰ、Ⅱ

B．Ⅱ、Ⅲ

C．Ⅰ、Ⅲ

D．Ⅰ、Ⅱ、Ⅲ

【答案】C

【解析】死鎖避免的策略是：必須知道將來的資源需求，以尋找可能的安全允許順序，如果不存在安全序列就阻塞；死鎖檢測的策略是：只要允許就分配資源，它指定期檢查死鎖是否已經發生，如果發生就通過剝奪解除死鎖。兩種方式都需要所需資源的總量信息，但S1是用于在分配資源時判斷是否會導致死鎖，而S2是用于檢測是否出現死鎖。

27系統為某進程分配了4個頁框，該進程已訪問的頁號序列為2，0，2，9，3，4，2，8，2，3，8，4，5，若進程要訪問的下一頁的頁號為7，依據LRU算法，應淘汰頁的頁號是（　　）。

A．2

B．3

C．4

D．8

【答案】B

【解析】LRU置換算法是選擇最近最久未使用的頁面予以淘汰。進程有4個頁框，題中訪問過程中頁框的變化如下：

訪問頁號為7的頁時，內存中存在的頁的頁號是：3、8、4和5，根據LRU定義應淘汰的是3。

28在系統內存中設置磁盤緩沖區的主要目的是（　　）。

A．減少磁盤I/O次數

B．減少平均尋道時間

C．提高磁盤數據可靠性

D．實現設備無關性

【答案】A

【解析】訪問磁盤的開銷遠遠大于訪問內存的開銷。磁盤緩沖區便是利用主存中的存儲空間，來暫存從磁盤中讀出（或寫入）的信息，頻繁使用的一部分磁盤數據和信息，暫時存放在磁盤緩存中，可減少訪問磁盤的次數。

29在文件的索引節點中存放直接索引指針10個，一級二級索引指針各1個，磁盤塊大小為1KB。每個索引指針占4個字節。若某個文件的索引節點已在內存中，到把該文件的偏移量（按字節編址）為1234和307400處所在的磁盤塊讀入內存。需訪問的磁盤塊個數分別是（　　）。

A．1，2

B．1，3

C．2，3

D．2，4

【答案】B

【解析】文件的索引結點的直接索引指針有10個，因此直接索引的偏移量范圍是0～2559，一級索引的偏移量范圍是2560～65791，二級索引訪問的偏移量范圍是65792～45183907。偏移量1234可以通過直接索引得到在磁盤塊的地址，因此需要一次訪問，307400需要通過二級索引查找其在磁盤的位置，需要分別訪問存放二級索引的兩個索引塊以及對應的數據塊。

30在請求分頁系統中，頁面分配策略與頁面置換策略不能組合使用的是（　　）。

A．可變分配，全局置換

B．可變分配，局部置換

C．固定分配，全局置換

D．固定分配，局部置換

【答案】C

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

31～40．暫缺

二、綜合應用題：41～47小題，共70分。

41（9分）用單鏈表保存m個整數，節點的結構為（data，link），且|data|＜n（n為正整數）。現要求設計一個時間復雜度盡可能高效地算法，對于鏈表中絕對值相等的節點，僅保留第一次出現的節點而刪除其余絕對值相等的節點。

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

刪除節點后的head為

要求

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

（2）使用c或C＋＋語言，給出單鏈表節點的數據類型定義。

（3）根據設計思想，采用c或C＋＋語言描述算法，關鍵之處給出注釋。

（4）說明所涉及算法的時間復雜度和空間復雜度。

答：（1）算法思想：

定義一個大小為n的布爾數組flag，初始時所有的元素都賦值為false，用來標識遍歷過程中是否出現元素絕對值為flag的節點。然后遍歷鏈表，遍歷過程中，每一個當前結點data域的絕對值所對應的flag位：若為真，則刪除該結點；若為假（false），則將flag位置為真（true）。

（2）節點的數據結構定義如下：

（3）

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

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

請回答下列問題

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

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

（3）若已知具有n（n＞＝2）個頂點的鄰接矩陣為B，則B^m（2＜＝m＜＝n）非零元素的含義是什么？

答：（1）鄰接矩陣為

（2）A²為：

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

（3）B^m中非零元素的含義是：假設此頂點位于i行j列，表示從i結點到j結點路徑長度為m的路徑的條數。

43（12分）某16位計算機主存按字節編碼。存取單位為16位；采用16位定長指令格式；CPU采用單總線結構，主要部分如下圖所示。圖中R0～R3為通用寄存器；T為暫存器；SR為移位寄存器，可實現直送（mov）、左移一位（left）、右移一位（right）3種操作，控制信號為SRop，SR的輸出信號SRout控制；ALU可實現直送A（mova）、A加B（add）、A減B（sub）、A與B（and）、A或B（or）、非A（not）、A加1（inc）7種操作，控制信號為ALUop。

請回答下列問題。

（1）圖中哪些寄存器是程序員可見的？為何要設置暫存器T？

（2）控制信號ALUop和SRop的位數至少各是多少？

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

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

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

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

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

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

（2）ALUop和SRop的位數分別為3，2。

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

（3）SRout所控制的部件是狀態字寄存器，用來存放ALU及CPU的指令狀態。

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

【解析】操作符命令，傳輸等都需要控制信號進行控制。

（5）⑥→⑨，⑦→④。

（6）數據寬度是16位，以字節編址，輸入端是2是為了增加地址獲取ALU的第二個操作數。

44（10分）題43中描述的計算機，其部分指令執行過程的控制信號如如題44圖a所示。

題44圖a　部分指令控制信號

該機指令格式如題44圖b所示，支持寄存器直接和寄存器間接兩種尋址方式，尋址方式位分別為0和1，通用寄存器R0～R3的編號分別為0、1、2和3。

題44圖　b指令格式

請回答下列問題。

（1）該機的指令系統最多可定義多少條指令？

（2）假定inc、shl和sub指令的操作碼分別為01H、02H和03H，則以下指令對應的機器代碼各是什么？

①inc R1；R1＋1→R1

②shl R2，R1；（R1）＜＜1→R2

③sub R3，（R1），R2；（（R1））－（R2）→R3

（3）假定寄存器X的輸入和輸出控制信號分別為Xin和Xout，其值為1表示有效，為0表示無效（例如，PCout＝1表示PC內容送總線）；存儲器控制信號為MEMop，用于控制存儲器的讀（read）和寫（write）操作。寫出題44圖a中標號①⑧處的控制信號或控制信號的取值。

（4）指令“sub R1，R3，（R2）”和“inc R1”的執行階段至少各需要多少個時鐘周期？

答：（1）128

【解析】支持兩種尋址方式，使用1位標識，四個寄存器，使用2位標識，因此對于每一個操作數需要3位，每條指令三個操作數，一條指令總共16位，因此剩余7位，所以可以定義2⁷條指令。

（2）①0240H，②0464H，③06EEH

【解析】“inc R1；”中R1是直接尋址的單地址指令，代碼是“0000001 001 000 000”，前面七位是操作碼（01H），001是第一個操作數地址（R1）；

“shl R2，R1；（R1）＜＜1→R2”中R1是間接尋址，R2是直接尋址，代碼是“0000010 010 101 000”，前面七位是操作碼（02H），010是第一個操作數地址（R2），101是第二個操作數地址；

“sub R3，（R1），R2；（（R1））－（R2）→R3”中R1和R2是間接尋址，R3是直接尋址，代碼是“000011 011 101 110”，前面七位是操作碼（03H），011是第一個操作數地址（R3），101是第二個操作數地址，110是第三個操作數地址。

（3）①0，②mov，③mova，④left，⑤read，⑥sub，⑦mov，⑧Srout。

（4）至少各需要8和1個時鐘周期。

【解析】在一個時鐘周期內CPU僅完成一個動作。

sub R1，R3，（R2）；（R3）－（（R2））→R1執行周期的微操作序列是：

T0：R3→MAR

T1：M（MAR）→MDR

T2：MDR→R3

T3：R2→MAR

T4：M（MAR）→MDR

T5：MDR→MAR

T6：M（MAR）→MDR

T7：R3＋MDR→R1

所以至少需要8個時鐘周期。

inc R1；R1＋1→R1執行周期的微操作序列是：

T0：R1＋1→R1

所以至少需要1個時鐘周期。

45（15分）有A、B兩人通過信箱進行辯論，每人都從自己的信箱中取得對方的問題。將答案和向對方提出的新問題組成一個郵件放入對方的郵箱中，設A的信箱最多放M個郵件，B的信箱最多放N個郵件。初始時A的信箱中有x個郵件（0＜x＜M），B中有y個（0＜y＜N）。辯論者每取出一個郵件，郵件數減1。

A、B兩人操作過程：

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

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

請添加必要的信號量和P、V（或wait signed）操作，以實現上述過程的同步，要求寫出完整過程，并說明信號量的含義和初值。

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

初始代碼：

通信代碼：

46～47．暫缺