計(jì)算機(jī)專業(yè)（基礎(chǔ)綜合）模擬試卷54

一、單選題（本題共40題，每題1.0分，共40分。）

1、若已知一個(gè)棧的人棧序列是1,2,3,…n,其輸出序列為pl,p2,p3,…pn,

若pl=n,則pi是（）。

A、i

B、n-i

C、n-i+1

D、不確定

標(biāo)準(zhǔn)答案：C

知識點(diǎn)解析：本題中所敘述的情況，棧的輸出序列一定是輸入序列的逆序。

2、將一個(gè)A[I..100,1..100]的三對角矩陣，按行優(yōu)先存入-維數(shù)組

R[1..29陰中,A中元素A66,65（即該元素下標(biāo)i=66,j=65）,在R數(shù)組中的位置k

為（）。

A、198

B、195

C、197

D、196

標(biāo)準(zhǔn)答案：B

知識點(diǎn)解析：根據(jù)三對角矩陣壓縮方法，將A[l..n][l..n]壓縮至B[0..3n-

3]時(shí),aij與bk的對應(yīng)關(guān)系為：k=2i+j?3；將A[l..n][l..川壓縮至B[l?.3n-2]

時(shí)，a.與bk的對應(yīng)關(guān)系為：k-2i+j-2;根據(jù)題目,A中元素Ag6565,在B數(shù)組中

的位置k為：k=2i+j-2=2x66+65-2=195

3、查找效率最高的二叉排序樹是（）。

A、所有結(jié)點(diǎn)的左子樹都為空的二叉排序樹

B、所有結(jié)點(diǎn)的右子樹都為空的二叉排序樹

C、平衡二叉樹

D、沒有左子樹的二叉排序樹

標(biāo)準(zhǔn)答案：C

知識點(diǎn)解析：二叉排序棚的查找效率取決于二叉排序樹的深度，對于結(jié)點(diǎn)個(gè)數(shù)相同

的二叉排序樹，平衡二叉樹的深度最小。

4、一棵深度為k的平衡二叉樹，其每個(gè)非葉子結(jié)點(diǎn)的平衡因子均為0,則該樹的

結(jié)點(diǎn)數(shù)是（）。

A、2k-1-l

B、2kl

C、2k-,+l

D、2k-l

標(biāo)準(zhǔn)答案：D

知識點(diǎn)端析：一棵深度為k的平衡二叉樹，其每個(gè)非葉子結(jié)點(diǎn)的平衡因子均為0,

也就是說每個(gè)非終端結(jié)點(diǎn)都有左子樹和右子樹且高度相等。因此，這樣的平衡二叉

樹即為滿二叉樹，而高度為k的滿二叉樹的結(jié)點(diǎn)數(shù)是2k-lo

5、判斷以下敘述的正確性（）。I對有向圖G,如果以任一頂點(diǎn)出發(fā)講行一次深

度優(yōu)先或廣度優(yōu)先搜索能訪問到每個(gè)頂點(diǎn)，則該圖一定是完全圖n連通圖的廣

度優(yōu)先搜索中一般要采用隊(duì)列來暫存訪問過的頂點(diǎn)印圖的深度優(yōu)先搜索中一般

要采用棧來暫存訪問過的頂點(diǎn)

A、I、口

B、口、m

c、I、m

D、i、口、nt

標(biāo)準(zhǔn)答案：B

知識點(diǎn)解析：I敘述是縉誤的，因?yàn)槿绻邢驁D構(gòu)成雙向有向環(huán)時(shí)，則從任一頂點(diǎn)

出發(fā)均能訪問到每個(gè)頂點(diǎn)，但該圖卻非完全圖。口、ni敘述顯然是正確的。

6、一個(gè)含有n個(gè)頂點(diǎn)和e條邊的簡單無向圖，在其鄰接矩陣存儲結(jié)構(gòu)中零元素的

個(gè)數(shù)是（）。

A、e

B、2e

C>n2-e

D>n2-2c

標(biāo)準(zhǔn)答案：D

知識點(diǎn)解析：由鄰接矩陣的定義可知，無向圖的鄰接矩陣是對稱的，即圖中的一條

邊對應(yīng)鄰接矩陣的兩個(gè)非零元素。因此一個(gè)含有n個(gè)頂點(diǎn)和e條邊的簡單無向圖的

鄰接矩陣中共有nZ2e個(gè)零元素。

7、從二叉樹的任一結(jié)點(diǎn)出發(fā)到根的路徑上，所經(jīng)過的結(jié)點(diǎn)序列必按其關(guān)鍵字降序

排列的是（）。

A、二叉排序樹

B、大頂堆

C、小頂堆

D、平衡二叉樹

標(biāo)準(zhǔn)答案：

知識之解析C：對于一個(gè)堆，若堆頂為最小元素，則稱為小頂堆；若堆頂為最大元

素，則稱為大頂堆。二叉排序樹和平衡二叉樹不符合。

8、順序存儲的某線性表共有123個(gè)元素，按分塊查找的要求等分為3塊。若對索

引表采用順序查找方法來確定子塊，且在確定的子塊中也采用順序查找方法，則在

等概率的情況下，分塊查找成功的平均查找長度為（）。

A、21

B、23

C、41

D、62

標(biāo)準(zhǔn)答案：B

知識點(diǎn)解析：分塊查找成功的平均查找長度為ASL=（s2+s+n）/2s。在本題中，

n=123,s=123/3=41,故平均查找長度為23。

9、在下列存儲結(jié)構(gòu)中，數(shù)據(jù)結(jié)構(gòu)中元素的存儲地址與其關(guān)鍵字之間存在某種映射

關(guān)系的是（）。

A、樹形存儲結(jié)構(gòu)

B、鏈?zhǔn)酱鎯Y(jié)構(gòu)

C、索引存儲結(jié)構(gòu)

D、散列存儲結(jié)構(gòu)

標(biāo)準(zhǔn)答案：D

知識點(diǎn)解析：散列存儲結(jié)構(gòu)將結(jié)點(diǎn)按其關(guān)鍵字的散列地址存儲到散列表中。

10、若對27個(gè)元素只進(jìn)行三趟多路歸并排序，則選取的歸并路數(shù)是（）。

A、2

B、3

C、4

D、5

標(biāo)準(zhǔn)答案：B

知識點(diǎn)解析：歸并就是將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表。設(shè)三趟

歸并中每次歸并x個(gè)有序表，則有27/x31,x=3o所以選取的歸并路數(shù)為3。

11、下列序列中，執(zhí)行第一趟快速排序的結(jié)果是（），

A、[da,ax,eb,de,bb]ff[ha,gc]

B、[cd,eb,ax,da]ff[ha,gc,bb]

C、[gc?ax,eb,cd,bb]ff[da?ha]

D、[ax,bb,cd,da]ff[eb,gc,ha]

標(biāo)準(zhǔn)答案：A

知識點(diǎn)解析：本題要按字典順序進(jìn)行排序，前半?yún)^(qū)間中的所有元素都應(yīng)小于ff,后

半?yún)^(qū)間中的所有元素都應(yīng)大于ffo

12、某計(jì)算機(jī)主存地址空間大小為256MB,按字節(jié)編址。虛擬地址空間大小為

4GB,采用頁式存儲管理，頁面大小為4KB,TLB]快表）采用全相聯(lián)映射，有4個(gè)

頁表項(xiàng)，內(nèi)容如表5-1所列。

G(X)去除，若余數(shù)為0表明該代碼是正確的；若余數(shù)不為0表明某一位出錯(cuò)，再

進(jìn)一步由余數(shù)值確定出錯(cuò)的位置，以便進(jìn)行糾正。現(xiàn)生成多項(xiàng)式為x3+x+l,表示

除數(shù)為lOllo

15、判斷加減法溢出時(shí)，可采用判斷進(jìn)位的方式，如果符號位的進(jìn)位為CO,最高

數(shù)值位為ci,產(chǎn)生溢出的條件是()。ico產(chǎn)生進(jìn)位nci產(chǎn)生進(jìn)位mco.

ci都產(chǎn)生進(jìn)位wco、ci都不產(chǎn)生進(jìn)位vco產(chǎn)生進(jìn)位，ci不產(chǎn)生進(jìn)位VICO

產(chǎn)生進(jìn)位，ci產(chǎn)生進(jìn)位

A、I和U

B、n

C、IV

D、V和VI

標(biāo)準(zhǔn)答案：D

知識點(diǎn)解析：采用進(jìn)位位來判斷溢出時(shí)，當(dāng)最高有效位和符號位的值不相同時(shí)才會

產(chǎn)生溢出。

16、內(nèi)存按字節(jié)編址，地址從90000H至UCFFFFH,若用存儲容量為16Kx8bit芯片

構(gòu)成該內(nèi)存，至少需要的芯片數(shù)是()。

A、2

B、4

C、8

D、16

標(biāo)準(zhǔn)答案：D

知識點(diǎn)解析：CFFFF-90000+1=40000,即256KB,若用存儲容量為16Kx8bit芯片

則需芯片數(shù)=(256Kx8)/(16Kx8)=16(片)。

17、某計(jì)算機(jī)指令字長為16位，指令有雙操作數(shù)、單操作數(shù)和無操作數(shù)3種格

式，每個(gè)操作數(shù)字段均有6位二進(jìn)制表示，該指令系統(tǒng)共有m條(m<16)雙操作數(shù)

指令，并存在無操作數(shù)指令。若采用擴(kuò)展操作碼技術(shù)，那么最多還可設(shè)計(jì)出單操作

數(shù)指令的條數(shù)是()。

A、26

B、(24-m)x26-l

C、(24-m)x26

D、(24-m)x(26-l)

標(biāo)準(zhǔn)答案：B

知識點(diǎn)解析：雙操作數(shù)指令操作碼字段占4位，單操作數(shù)指令操作碼字段占10

位，無操作數(shù)指令操作碼字段占16位?，F(xiàn)指令系統(tǒng)中有m條雙操作數(shù)指令，則給

單操作數(shù)和無操作數(shù)指令留下了(2，口)個(gè)擴(kuò)展窗口。因?yàn)榇嬖谥鵁o操作數(shù)指令，所

以單操作數(shù)指令必須要給無操作數(shù)指令留下一個(gè)擴(kuò)展窗口，最終最多可以設(shè)計(jì)出單

操作數(shù)指令的數(shù)目為(24?m)x2&l。

18、指令流水線將一條指令的執(zhí)行過程分為四步，其中第1、2和4步的經(jīng)過時(shí)間

為△[,如下圖5-1所示。若該流水線順序執(zhí)行，50條指令共用153A3并且不考慮

,r—產(chǎn)fij一"一].間是（）。

—I―2—3—4—

AtAtAi

圖5-1

A、2At

B、3At

C、4At

D、5At

標(biāo)準(zhǔn)答案：B

知識點(diǎn)解析：在圖5—1中，第3個(gè)流水段的執(zhí)行時(shí)間沒有給出，顯然這是一個(gè)瓶

頸段，設(shè)它的執(zhí)行時(shí)間為X。通過列方程（3+X）Zit+49XAt=153A,可以求得X=3。

19、以下關(guān)于CPU的敘述中，錯(cuò)誤的是（）。

A、CPU產(chǎn)生每條指令的操作信號并將操作信號送往相應(yīng)的部件進(jìn)行控制

B、程序計(jì)數(shù)器PC除了存放指令地址，也可以臨時(shí)存儲算術(shù)/邏輯運(yùn)算結(jié)果

C、CPU中的控制器決定計(jì)算機(jī)運(yùn)行過程的自動化

D、指令譯碼器是CPU控制器中的部件

標(biāo)準(zhǔn)答案：B

知識點(diǎn)解析：程序計(jì)數(shù)器PC又稱指令計(jì)數(shù)器，用來存放正在執(zhí)行的指令地址或接

著要執(zhí)行的下一條指令地址，不能用于臨時(shí)存儲算術(shù)/邏輯運(yùn)算結(jié)果。

20、在系統(tǒng)總線中，地址總線的位數(shù)（）。

A、與機(jī)器字長有關(guān)

B、與存儲單元個(gè)數(shù)有關(guān)

C、與存儲字長有關(guān)

D、與存儲器帶寬有關(guān)

標(biāo)準(zhǔn)答案：B

知識點(diǎn)解析：地址總線的位數(shù)與存儲單元個(gè)數(shù)有關(guān)，地址總線的位數(shù)越長，可訪問

的存儲單元個(gè)數(shù)就越多。雙方向的多根信號線組成，CPU可以沿這些線從主存或

外設(shè)讀入數(shù)據(jù)，也可以沿這些線向主存或外設(shè)送出數(shù)據(jù)；控制總線上傳輸?shù)氖强刂?/p>

信息，包括CPU送出的控制命令和主存（或外設(shè)）返回CPU的反饋信號。地址總線

寬度決定了CPU可以訪問的最大的物理地址空間，簡單地說就是CPU到底能夠使

用多大容量的主存。例如，32位地址線，可尋址的最大容量為232=4

096MB（4GB）。

21、假設(shè)某硬盤由5個(gè)盤片構(gòu)成（共有8個(gè)記錄面），盤面有效記錄區(qū)域的外直徑為

30cm,內(nèi)直徑為10cm,記錄位密度為250位/mm,磁道密度為16道/mm,每

磁道分16個(gè)扇區(qū)，每扇區(qū)512字節(jié)，則該硬盤的格式化容量約是()。

8X(3O-1O)X1OX25OX168X(30—10)X10X16X16X512陽、

A-8X1024X1024MRR，2X1024X1024

8X(30-10)X10X250X16X16MRn8X(30—10)X16X16/5叫山

8X1024X1024*2X1024X1024

A、

B、

C、

D、

標(biāo)準(zhǔn)答案：B

知識點(diǎn)解析：格式化容量計(jì)算中根據(jù)扇區(qū)數(shù)和扇區(qū)容量計(jì)算出每條磁道上的信息

量，然后再乘以總磁道數(shù)。而總磁道數(shù)計(jì)算時(shí)，首先求出每面磁道數(shù)(柱面數(shù))，再

乘以記錄面數(shù)。磁盤的容量有格式化容量與非格式化容量之分，磁盤匕標(biāo)稱的容量

為格式化容量。計(jì)算磁盤容量公式中的總磁道數(shù)是指記錄面數(shù)與圓柱面數(shù)的乘積。

其中柱面數(shù)的計(jì)算公式為：柱面數(shù)=(外半徑-內(nèi)半徑)x道密度格式化容量是磁盤實(shí)

際可以使用的容量。新的磁盤在使用之前需要先進(jìn)行格式化，格式化實(shí)際上就是

在磁盤上劃分記錄區(qū)，寫入各種標(biāo)志信息和地址信息。這些信息占用了磁盤的存儲

空間，故格式化之后的有效存儲容量要小于非格式化容量。它的計(jì)算公式為：格

式化容量=每道扇區(qū)數(shù)x扇區(qū)容量x總磁道數(shù)

22、下列說法正確的是()。

A、計(jì)算機(jī)中一個(gè)漢字內(nèi)碼在主存中占有4個(gè)字節(jié)

B、輸出的字型碼16x16點(diǎn)陣在緩沖存儲器中占有32個(gè)字節(jié)

C、輸出的字型碼16x16點(diǎn)陣在緩沖存儲器中占有16個(gè)字節(jié)

D、以上說法都不對

標(biāo)準(zhǔn)答案：B

知識點(diǎn)解析：16x16點(diǎn)陣的漢字共計(jì)有256個(gè)點(diǎn)，相當(dāng)于32個(gè)字節(jié)。

23、下列操作系統(tǒng)的功能中，只需軟件而不需要特殊硬件支持就能完成的功能是

()o

A、中斷系統(tǒng)

B、地址映射

C、進(jìn)程調(diào)度

D、時(shí)鐘管理

標(biāo)準(zhǔn)答案：C

知識點(diǎn)解析：本題考查對操作系統(tǒng)的功能的理解。中斷系統(tǒng)需要硬件的支持是顯而

易見的，在中斷過程中保存和恢復(fù)寄存器的值均需要硬件支持；地址映射中需要

TLB和地址加法器等硬件支持：時(shí)鐘管理需要硬件寄存器保存時(shí)鐘值，進(jìn)程調(diào)度

由相關(guān)進(jìn)程調(diào)度算法完成，不需要硬件支持。

24、計(jì)算機(jī)系統(tǒng)中，創(chuàng)建的進(jìn)程數(shù)量受到制約的主要因素是()。

A、內(nèi)存大小

B、終端數(shù)目

C、打開文件數(shù)

D、處理機(jī)數(shù)量

標(biāo)準(zhǔn)答案：A

知識點(diǎn)解析：本題考查系統(tǒng)中影響進(jìn)程數(shù)量的限制因素。系統(tǒng)中創(chuàng)建進(jìn)程的數(shù)量主

要受到內(nèi)存大小限制。進(jìn)程創(chuàng)建時(shí)需要分配資源，其中最主要的資源是內(nèi)存，為每

個(gè)進(jìn)程分配內(nèi)存是進(jìn)程創(chuàng)建的主要工作。另外，進(jìn)程控制塊本身也要占用內(nèi)存，存

在系統(tǒng)開銷。當(dāng)進(jìn)程創(chuàng)建數(shù)量較多時(shí)，系統(tǒng)開銷本身就很大，剩下的資源分配給進(jìn)

程會不夠；當(dāng)采用虛擬存儲技術(shù)時(shí)，還可能會引起抖動，嚴(yán)重影響系統(tǒng)性能。其余

的選項(xiàng)均不會對進(jìn)程創(chuàng)建的數(shù)量有影響，一個(gè)系統(tǒng)若有大量的處理機(jī)而內(nèi)存較少

時(shí)，也是不能發(fā)揮其作用的。

25、能夠綜合考慮計(jì)算密集型和事務(wù)密集型進(jìn)程的調(diào)度算法是（）。

A、時(shí)間片輪轉(zhuǎn)

B、先來先服務(wù)

C、多重隊(duì)列

D、彩票

標(biāo)準(zhǔn)答案：C

知識點(diǎn)解析：本題考查進(jìn)程的調(diào)度算法。時(shí)間片輪轉(zhuǎn)的主要目的是使得多個(gè)交互的

用戶能夠及時(shí)得到響應(yīng)，使得用戶以為“獨(dú)占”計(jì)算機(jī)在使用。因此它并沒有偏好，

也不會對特殊進(jìn)程進(jìn)行特殊服務(wù)。先來先服務(wù)最為公平，但是不能區(qū)分計(jì)算密集型

還是事務(wù)密集型的進(jìn)程。彩票算法是一種隨機(jī)算法，也不能改善綜合性能，只有多

重隊(duì)列算法可以將不同類型的進(jìn)程排列在不同的隊(duì)列上，并設(shè)計(jì)針對不同隊(duì)列的時(shí)

間片分配和輪轉(zhuǎn)算法，以獲得較優(yōu)的綜合性能。

26、一次分配所有資源的方法可以預(yù)防死鎖的發(fā)生，它破壞的死鎖四個(gè)必要條件中

的哪一個(gè)（）。

A、互斥條件

B、占有并請求

C、非剝奪條件

D、循環(huán)等待

標(biāo)準(zhǔn)答案：B

知識點(diǎn)解析：發(fā)生死鎖的四個(gè)必要條件如下：互斥條件、占有并請求資源、非剝奪

條件和循環(huán)等待條件。一次分配所有資源的方法是當(dāng)進(jìn)程需要資源時(shí)，一次性提出

所有的請求，若請求的所有資源均滿足則分配，只要有一項(xiàng)不滿足，那么不分配任

何資源，該進(jìn)程阻塞，直到所有的資源空閑后，滿足了進(jìn)程的所有需求時(shí)再分配。

這種分配方法不會部分與有資源，所以就打破了死鎖的四個(gè)必要條件之一，實(shí)現(xiàn)了

對死鎖的預(yù)防。但是，這種分配方式需要湊齊所有資源，所以，當(dāng)一個(gè)進(jìn)程所需的

資源比較多時(shí)，資源的利用率會比較低，甚至?xí)斐蛇M(jìn)程的饑餓。正確答案為B。

27、有兩個(gè)處理機(jī)PI和P2,它們各自有一個(gè)cache和主存，分別為Cl、C2和

Ml、M2,其性能如下表5-2所列：

?5-2

C1MlC2M2

12KB128MB12KB128MB

讀寫時(shí)閻40nsI000n?SOns900ns

若兩個(gè)處理機(jī)的指令系統(tǒng)相同，指令的執(zhí)行時(shí)間與存儲器的平均存取周期成i,當(dāng)

執(zhí)行某程序時(shí)，cache的命中率為70%,則P1處理機(jī)的速度相比P2處理機(jī)是(

A、更快的

B、更慢的

C、相等的

D、不能確定的

標(biāo)準(zhǔn)答案：B

知識點(diǎn)解析：本題考查多級存儲層次下的平均訪問時(shí)間的計(jì)算。根據(jù)題意，處理機(jī)

執(zhí)行指令的時(shí)間與存儲器的平均存取周期成正比，因此只要計(jì)算出存儲器的平均存

取周期，即可比較出兩者的優(yōu)劣。對于處理機(jī)P1,存儲器的平均存取周期為：

40x0.7+(1000+40)x(1-0.7)=340ns對于處理機(jī)P2,存儲器的平均存取周期為：

50x0.7+(9004-50)x(1-0.7)=320ns因此可以看出,處理機(jī)P1需要更多的處理機(jī)時(shí)

間，處理機(jī)P1比處理機(jī)P2更慢。

28、在頁式存儲管理中，每個(gè)頁表的表項(xiàng)實(shí)際上是用于實(shí)現(xiàn)()。

A^訪問內(nèi)存單元

B、靜態(tài)重定位

C、動態(tài)重定位

D、裝載程序

標(biāo)準(zhǔn)答案：C

知識點(diǎn)解析：本題考查頁式存儲管理的基本概念。頁式存儲管理的基本點(diǎn)是解決程

序在內(nèi)存中離散存放的問題，其尋址方式是借鑒于動態(tài)重定位的技術(shù)，在動態(tài)重定

位技術(shù)中，通過設(shè)置基址寄存器，將程序的邏輯地址通過基址寄存器和地址加法

器，動態(tài)地實(shí)現(xiàn)了地址轉(zhuǎn)換(即每一條都是自動轉(zhuǎn)換的)，操作系統(tǒng)在裝載程序時(shí)可

以不用像靜態(tài)重定位那樣計(jì)算程序代碼的地址定位，使得地址轉(zhuǎn)換快捷又簡單。頁

式存儲管理將動態(tài)重定位中的基址寄存器用一組頁表來替代，當(dāng)訪問不同的頁面

時(shí)，在基址寄存器中只要存放該頁面的頁框號便可以快速地實(shí)現(xiàn)地址轉(zhuǎn)換。所以

說，頁表項(xiàng)實(shí)際上是實(shí)現(xiàn)了動態(tài)重定位。

29、操作系統(tǒng)中，建立文件系統(tǒng)的時(shí)刻是()。

A、對磁盤進(jìn)行分區(qū)時(shí)

B、對磁盤進(jìn)行格式化時(shí)

C、安裝系統(tǒng)文件時(shí)

D、操作系統(tǒng)啟動時(shí)

標(biāo)準(zhǔn)答案：B

知識點(diǎn)解析：本題考查對文件系統(tǒng)建立時(shí)刻的理解。文件系統(tǒng)是指管理一組信息集

合的具體方式，主要體現(xiàn)在文件物理結(jié)構(gòu)的實(shí)現(xiàn)上，因此只有建立文件系統(tǒng)，在該

文件系統(tǒng)上才可以實(shí)現(xiàn)操作系統(tǒng)的安裝、啟動和加載等工作。磁盤分區(qū)是確定一個(gè)

邏輯存儲單元的大?。荤笫交菍⑽募到y(tǒng)創(chuàng)建到外存儲設(shè)備上；安裝操作系統(tǒng)只

是在己經(jīng)完成格式化，亦即已經(jīng)確定了文件系統(tǒng)的外存儲設(shè)備上建立操作系統(tǒng)啟動

的一系列過程；而操作系統(tǒng)啟動是基于文件系統(tǒng)的使用的。

30、FAT16文件系統(tǒng)的一條目錄項(xiàng)大小是32字節(jié)。該文件系統(tǒng)的根目錄大小為1

個(gè)簇，每個(gè)簇有8個(gè)扇區(qū)，每個(gè)扇512字節(jié)，則根目錄中能容納的最大文件或子目

錄個(gè)數(shù)是（）。

A、64

B、1

C、128

D、256

標(biāo)準(zhǔn)答案：C

知識點(diǎn)解析：FAT16文件系統(tǒng)每個(gè)目錄項(xiàng)是32字節(jié)，根目錄為1個(gè)簇，根據(jù)題

意，簇的大小為8x512=4096B,在根目錄下存放1個(gè)文件或1個(gè)子目錄需占用1

條目錄項(xiàng)，因此，有多少個(gè)目錄項(xiàng)就對應(yīng)有多少個(gè)文件或目錄，因此，在根目錄下

能存放的最多目錄項(xiàng)可以計(jì)算為4096B/32B=128,即在根目錄下最多存放128個(gè)

文件或目錄。

31、一個(gè)文件的絕對路徑名的出發(fā)點(diǎn)是（）。

A、當(dāng)前目錄

B、根目錄

C、磁盤盤符

D、公共目錄

標(biāo)準(zhǔn)答案：B

知識點(diǎn)解析：本題考查文件路徑名的概念C文件的路徑名是從根目錄到目標(biāo)文件所

經(jīng)歷的路徑上各符號的集合。路徑名有二種形式，第一種是絕對路徑名，它由根目

錄出發(fā)，沿著目錄的路徑直到文件，絕對路徑名總是從根目錄出發(fā)，并且是唯一

的。第二種是相對路徑名，它與工作目錄（也稱當(dāng)前目錄）一起使用，用戶一般預(yù)先

指定一個(gè)目錄為當(dāng)前目錄，這時(shí)，所有的路徑名均從當(dāng)前目錄出發(fā)，這樣的路徑

名，只要不是從根目錄出發(fā)的，都稱為相對路徑名。

32、如果一個(gè)沒有內(nèi)存映射的10設(shè)備與主存之間交換數(shù)據(jù)，希望這種數(shù)據(jù)交換不

經(jīng)過CPU來完成，那么，可以采用的方法是（）。

A、程序查詢方式

B、中斷技術(shù)

C、通道技術(shù)

D、DMA方式

標(biāo)準(zhǔn)答案：C

知識點(diǎn)解析：本題考查對通道和DMA的理解。對于CPU干預(yù)的10操作，程序查

詢和中斷技術(shù)都是必要的，而可以解放CPU且能控制數(shù)據(jù)交換的10操作只能是通

道技術(shù)和DMA方式。經(jīng)過分析這兩種方式，我們發(fā)現(xiàn)，DMA方式需要將IO設(shè)備

的數(shù)據(jù)口地址映射到內(nèi)存中，通道是不需要的，所以采用通道控制方式來作此傳送

是最佳的。

33、下面對計(jì)算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu)中協(xié)議所做的描述，錯(cuò)誤的是（）。

A、網(wǎng)絡(luò)協(xié)議的三要素是語法、語義和同步

B、協(xié)議是控制兩個(gè)對等層實(shí)體之間通信的規(guī)則的集合

C、在。S1參考模型中，要實(shí)現(xiàn)第N層的辦議，需要使用N+1層提供的服務(wù)

D、協(xié)議規(guī)定了對等層實(shí)體之間所交換的信息的格式和含義

標(biāo)準(zhǔn)答案：c

知識點(diǎn)解析：協(xié)議是控制兩個(gè)對等層實(shí)體之間通信的規(guī)則的集合，網(wǎng)絡(luò)協(xié)議的三要

素是語法、語義和同步，其中語法和語義規(guī)定了對等層實(shí)體之間所交換的信息的格

式和含義，但第N層協(xié)議要為第N+1層提供服務(wù)，因此選項(xiàng)C的論述是錯(cuò)誤的，

答案是C。

34、對于帶寬為6MHz的信道，若用8種不同的狀態(tài)來表示數(shù)據(jù)，在不考慮熱噪聲

的情況下，該信道每秒最多能傳送的位數(shù)是（）。

A、36xl06bps

B、18xl06bps

C、48xl06bps

D、96xl06bps

標(biāo)準(zhǔn)答案：A

知識點(diǎn)解析：本題考查奈奎斯特定理的直接應(yīng)用，注意這里采用8種不同的狀態(tài)，

因此離散個(gè)數(shù)為8,iC=2xHxlog2N=2x6xlog28=36Mbps,因此答案為A。

35、根據(jù)CSMA/CD協(xié)議的工作原理，下列情形中需要提高最短幀長度的是（）。

A、網(wǎng)絡(luò)傳輸速率不變，沖突域的最大距離變短

B、沖突域的最大距離不變，網(wǎng)絡(luò)傳輸速率提高

C、上層協(xié)議使用TCP的概率增加

D、在沖突域不變的情況下減少線路中的中繼器數(shù)量

標(biāo)準(zhǔn)答案：B

知識點(diǎn)解析：本題考查CSMA/CD協(xié)議原理。在CSMA/CD系統(tǒng)中，如果在幀

傳送的開頭T長度時(shí)間內(nèi)沒有檢測到?jīng)_突，那么隨后也就不會再有沖突發(fā)生。令t

為任意一個(gè)站的發(fā)送設(shè)備到達(dá)所有其他站的接收設(shè)備的延遲時(shí)間的最大值，那么

T=2to也就是說，如果在2t的時(shí)間內(nèi)沒有檢測到?jīng)_突，就表示這次傳送的嘗試成

功了，因此在這段時(shí)間內(nèi)傳輸?shù)臄?shù)據(jù)幀的長度就是最短幀長度，假設(shè)最大距離是

M,信號傳播速度是D,傳輸速率是C,那么最短幀長度就是Cx2x（M/D）在

本題中，如果傳輸速率不變，最大距離變短，最短幀長度也要變短，如果最大距離

不變，傳輸速率提高，最短幀長度要增加，由于工作在數(shù)據(jù)鏈路層，因此傳輸層的

TCP和物理層的中繼器對其都沒有影響，因此答案是B。

36、考慮在一條1000m長的電纜(無中繼器)上建立一個(gè)IGbps速率的CSMA/CD

網(wǎng)絡(luò)，假定信號在電纜中的速度為2xl()8m/s,那么該電纜的最小數(shù)據(jù)幀長是()。

A、1250B

B、1230B

C、1280B

D、1220B

標(biāo)準(zhǔn)答案：A

知識點(diǎn)解析：本題考查CSMA/CD協(xié)議的基本原理，具體見35題答案解析部

分，這里a代表單程端到端的傳播延時(shí),因此2a=2x1000/(2x1()8尸log。在1

Gbps速率下，每位的時(shí)間為1納秒，所以最小幀長為10/IO-3=IOOOOb=l250字

節(jié)，因此答案為A。

37、將一條物理信道按時(shí)間分成若干時(shí)間片輪換的給多個(gè)信號使用，每一時(shí)間片由

復(fù)用的一個(gè)信號占用，這樣可以在一條物理信道上傳輸多個(gè)數(shù)字信號，這就是()。

A、頻分多路復(fù)用

B、時(shí)分多路復(fù)用

C、空分多路復(fù)用

D、頻分與時(shí)分混合多路復(fù)用

標(biāo)準(zhǔn)答案：B

知識點(diǎn)解析：本題考查信道復(fù)用的幾種方式，題意指明這種復(fù)用是通過劃分時(shí)間

片，因此是時(shí)分多路復(fù)用，答案為B。

38、主機(jī)A向主機(jī)B連續(xù)發(fā)送了兩個(gè)TCP報(bào)文段，其序號分別為70和100,如果

主機(jī)B收到第二個(gè)報(bào)文段后發(fā)回的確認(rèn)中的確認(rèn)號是180,主機(jī)A發(fā)送的第二個(gè)

報(bào)文段中的數(shù)據(jù)大小是()。

A、70

B、30

C、80

D、100

標(biāo)準(zhǔn)答案：C

知識點(diǎn)解析：本題考查TCP的可靠連接，重點(diǎn)是報(bào)文段的確認(rèn)字段，由于主機(jī)B

收到第二個(gè)報(bào)文段后發(fā)回的確認(rèn)中的確認(rèn)號是180,說明已經(jīng)收到了第179號字

節(jié)，也就說明第二個(gè)報(bào)文段的序號是從100到179,故第二個(gè)報(bào)文段有80字節(jié)，

因此答案是特別注意在使用TCP傳輸數(shù)據(jù)時(shí)，如果有一個(gè)確認(rèn)報(bào)文段丟失

了，是不是一定會引起與該確認(rèn)報(bào)文段對應(yīng)的數(shù)據(jù)的重傳?答案是不一定。例如某

個(gè)確認(rèn)丟失了，但是在咳報(bào)文的重傳計(jì)時(shí)器到時(shí)之前，卻收到了更高序號的確認(rèn)，

因?yàn)槿绻邮辗經(jīng)]有收到低號的報(bào)文是不可能會發(fā)出高序號的確認(rèn)的，所以說發(fā)送

方此時(shí)不會在重傳那個(gè)丟失確認(rèn)的報(bào)文了。例如主機(jī)A連續(xù)發(fā)送兩個(gè)報(bào)文段：

（SEO=92,共8字節(jié)的數(shù)據(jù)）和（SEQ=100,共20字節(jié)的數(shù)據(jù)），均正確達(dá)到主機(jī)

BoB連續(xù)發(fā)送兩個(gè)確認(rèn)：（ACK=100）和（ACK=120）,但是前者在傳送時(shí)丟失了。

假如A在第一個(gè)報(bào)文段超時(shí)之前收到了對第二個(gè)報(bào)文段的確認(rèn)，此時(shí)A知道，120

號之前的所有字節(jié)（當(dāng)然包括第一個(gè)報(bào)文段中的所有字節(jié)）均已被B正確接收，因此

A不會再重傳第一個(gè)報(bào)文段。

39、以下關(guān)于路由器的路由表說法正確的是（）。I路由表包含目的網(wǎng)絡(luò)和到達(dá)該

目的網(wǎng)絡(luò)的完整路徑II路由表必須包含子網(wǎng)掩碼HI目的網(wǎng)絡(luò)和到達(dá)該目的網(wǎng)絡(luò)路

徑上的下一個(gè)路由器的IP地址W目的網(wǎng)絡(luò)和到達(dá)該目的網(wǎng)絡(luò)路徑上的下一個(gè)路由

器的MAC地址

A>n>m

B、只有m

c、i、川

D、□、m、iv

標(biāo)準(zhǔn)答案：B

知識點(diǎn)解析：本題考查網(wǎng)絡(luò)設(shè)備中路由器的作用結(jié)構(gòu)和工作原理，路由器是網(wǎng)絡(luò)互

連的關(guān)鍵設(shè)備，其任務(wù)是轉(zhuǎn)發(fā)分組。每個(gè)路由器都維護(hù)著一個(gè)路由表以決定分組的

傳輸路徑。當(dāng)目的主機(jī)與源主機(jī)不在同一個(gè)網(wǎng)絡(luò)中，則應(yīng)將數(shù)據(jù)報(bào)發(fā)送給源主機(jī)所

在網(wǎng)絡(luò)上的某個(gè)路由器，由該路由器按照轉(zhuǎn)發(fā)表（由路由表構(gòu)造的）指出的路由將數(shù)

據(jù)報(bào)轉(zhuǎn)發(fā)給下一個(gè)路由器，這種交付方式稱為間接交付。I:為了提高路由器的

查詢效率和減少路由表的內(nèi)容，路由表只保留到達(dá)目的主機(jī)的下一個(gè)路由器的地

址，而不是保留通向目的主機(jī)的傳輸路徑上的所有路由信息，故I錯(cuò)誤。n：路

由表并不一定包含子網(wǎng)逾碼，一般只在劃分了子網(wǎng)的網(wǎng)絡(luò)中，路由器的路由表才使

用子網(wǎng)掩碼，如果不使用就根本不能得到網(wǎng)絡(luò)號。而沒有劃分子網(wǎng)的網(wǎng)絡(luò)，使用默

認(rèn)的就可以，不需要在路由表上顯示，故口錯(cuò)誤。n：路由器的路由表的表項(xiàng)通

常包含目的網(wǎng)絡(luò)和到達(dá)咳目的網(wǎng)絡(luò)的下一個(gè)路由器的IP地址，因?yàn)槁酚善魇枪ぷ?/p>

在網(wǎng)絡(luò)層，網(wǎng)絡(luò)層使用的是IP地址，故in正確，IV：路由器是工作在網(wǎng)絡(luò)層的設(shè)

備，對數(shù)據(jù)鏈路層是透明的，故iv錯(cuò)誤。綜上，只有in正確，因此答案是B。

40、FTP客戶和服務(wù)器之間一般需要建立的連接個(gè)數(shù)是（）。

A、1

B、2

C、3

D、4

標(biāo)準(zhǔn)答案：B

知識點(diǎn)解析：本題考查FTP的基本原理。FTP客戶與服務(wù)器之間一般要建立兩個(gè)

連接，一個(gè)是控制連接，一個(gè)是數(shù)據(jù)連接，控制連接在整個(gè)會話期間一直保持打

開，F(xiàn)TF，客戶發(fā)出的傳送請求通過控制連接發(fā)送給服務(wù)器端的控制進(jìn)程，但控制

連接不用來傳送文件。實(shí)際用于傳輸文件的是“數(shù)據(jù)連接服務(wù)器端的控制進(jìn)程在

接收到FTP客戶發(fā)送來的文件傳輸請求后就創(chuàng)建“數(shù)據(jù)傳送進(jìn)程”和“數(shù)據(jù)連接。用

來連接客戶端和服務(wù)器端的數(shù)據(jù)傳送進(jìn)程。數(shù)據(jù)傳送進(jìn)程實(shí)際完成文件的傳送，在

傳送完畢后關(guān)閉“數(shù)據(jù)傳送連接''并結(jié)束運(yùn)行。因此答案是Bo

二、綜合應(yīng)用題(本題共7題，每題1.0分，共7分0)

41、已知下列各種初始狀態(tài)(長度為n)元素，試問當(dāng)利用直接插入法進(jìn)行排序時(shí)，

至少需要進(jìn)行多少次比較(要求排序后的文件按關(guān)鍵字從大到小順序排列)。

(1)關(guān)鍵字自小到大有序(key1〈key2V……<keyn);(2)關(guān)鍵字自大到小逆序

(keyi>key2>……>keyn);(3)奇數(shù)關(guān)鍵字順序有序，偶數(shù)關(guān)鍵字順序有序

(keyi<keys.......，key2<kcy4<........);(4)前半部分元素按關(guān)鍵字順序有序，

后半部分元素按關(guān)鍵字順序逆序。(key】Vkey2V.......<keym,keym+i>

keym+2>.......>keyn,m為中間位置)。

標(biāo)準(zhǔn)答案：依題意，最好情況下的比較次數(shù)即為最少比較次數(shù)。(1)在這種情況

下，插入第i個(gè)(2SiSn)元素的比較次數(shù)為1,因此，總的比較次數(shù)為

1+1+1+……+l=n-lo(2)在這種情況下,插入第i個(gè)(249沅素的比較次數(shù)為i,因

此，總的比較次數(shù)為2+3+4+……+n=(n-l)(n+2)/2,(3)在這種情況下，比較次數(shù)

最少的情況是所有記錄關(guān)鍵字均按升序排列，這時(shí)，總的比較次數(shù)為『I。(4)在這

種情況下，后半部分元素的關(guān)鍵字均大于前半部分元素的關(guān)鍵字時(shí)需要比較次數(shù)最

少，此時(shí)前半部分的比較次數(shù)=m-1,后半部分的比較次數(shù)=(n-m-l)*(n-m+2)/2,

因此，總的比較次數(shù)為m-l+(n-m-l)*(n-m+2)/2=(n-2)(n+8)/8(假設(shè)n偶數(shù)，m=n

/2)o

知識點(diǎn)解析：暫無解析

42、設(shè)計(jì)一個(gè)算法，求無向圖G(采用鄰接表存儲)的連通分量個(gè)數(shù)。

標(biāo)準(zhǔn)答案：解法一：采用深度優(yōu)先遍歷方法。算法如下：#define

MAX_VERTEX_NUM20//最大頂點(diǎn)數(shù)為20typedefstructArcNode{//邊表結(jié)

點(diǎn)intadjvex；//鄰接點(diǎn)域structArcNode*nextarc；//指向下一個(gè)鄰接點(diǎn)的指

針域//若要表示邊上信息，則應(yīng)增加一個(gè)數(shù)據(jù)域info}ArcNode：typedefstruct

VNodc{//頂點(diǎn)表結(jié)點(diǎn)VcrtcxTypcdata；//頂點(diǎn)域ArcNode*firstarc；//邊

表頭指針}VNode,AdjList|MAX_VERTEX_NUM]；//AdjLisl是鄰接表類型

typedefstruct{AdjListadjlist；//鄰接表intvexnum,arcnum；//頂點(diǎn)數(shù)和邊

數(shù)}ALGraph；//ALGraph是以鄰接表方式存儲的圖類型voidDFS(ALGraph

G,intV){ArcNode*p；visited[v]=l：//置已訪問標(biāo)記prinf("%d",v)；//輸

出被訪問頂點(diǎn)的編號P=G->adjlist[v].firstarc；//p指向頂點(diǎn)v的第一條邊的終

結(jié)點(diǎn)while(p!=NULL){if(visited[p->adjvex]==O)//若p->adjvex頂點(diǎn)未訪問，遞

歸訪問它DFS(G,P->adjvex)；p=p->nextarc；//p指向頂點(diǎn)V的下一條邊的

終結(jié)點(diǎn)}}intConnNumI(ALGraphG){//求圖G的連通分量inti,num=0；

for(i=0；i<G->n；i++)visitcd[i]=O；for(i=0；i<G->n；i++)

if(visited[i]==O)(DFS(G,i)；//調(diào)用DFS算法num++：)return(num)；)解法

二：采用廣度優(yōu)先遍歷方法。算法如下：voidBFS(ALGraphG,int

v){ArcNode*p；intQu|MAX_VERTEX_NUM],front=0,rear=0；//定義循環(huán)

隊(duì)列并初始化intW,i；for(i：0；i<G->n；i++)visited(i]=O；//訪問標(biāo)志數(shù)組

初始化prinf("2%d"，v)：//輸出被訪問頂點(diǎn)的編號visited[v]=l；//置已訪問

標(biāo)記rear=(rear+l)%MAX_VERTEX_NUM；Qu|rear|=v：//v入隊(duì)

while(front!=rear){//若隊(duì)列不空時(shí)循環(huán)front=(front+l)%

MAX_VERTEX_NUM；w=Qu[front]；//出隊(duì)并賦予Wp二G->

adjlisl|w|.firstarc；//找與頂點(diǎn)W鄰接的第一個(gè)頂點(diǎn)

while(p!=NULL){if(visited[p->adjvex]==O){//若當(dāng)前鄰接頂點(diǎn)未被訪問

printf("%2d",p->adjvex)；//訪問相鄰頂點(diǎn)visited[p_>adjvex]=l；//置該

頂點(diǎn)已被訪問的標(biāo)志rear=(rear+l)%MAX_VERTEX_NUM!//該頂點(diǎn)人隊(duì)

Qu[rear]=p->adjvex；)p=p->nextarc；//找下一個(gè)鄰接頂點(diǎn)}}printf("\

n")；}intConnNum2(ALGraphG){//求圖G的連通分量inti,num=O；

for(i=0；i<G->n；i++)visited[i]=O；for(i=0；i<G->n；i++)

if(visited[i]==O)(BFS(G.i)；//調(diào)用BFS算法num++：)return(num)；}

知識點(diǎn)解析：暫無解析

43、在虛擬地址和物理地址均為32位、頁大小為4KB的某種體系結(jié)構(gòu)中，假定存

在表8-1所列的地址映像關(guān)系，問：對應(yīng)于下列虛擬地址的物理地址分別是什么？

(l)22433007H；(2)13385ABCH；(3)ABC89011H<)

?8-1

虛頁號實(shí)頁號

ABC89H97887H

13385H9991OH

22433H00001H

54483H1A8C2H

標(biāo)準(zhǔn)答案：(1)虛擬地址22433007H中，虛頁號為22433H，其對應(yīng)的實(shí)頁號為

00001H,所以對應(yīng)的物理地址00001007H。⑵虛擬地址13385ABCH中，虛頁號

為13385H,其對應(yīng)的實(shí)頁號為99910H,所以對應(yīng)的物理地址99910ABCH。(3)虛

擬地址ARC89011H中，虛頁號為ABC89H,其對應(yīng)的實(shí)頁號為97887H.所以對

應(yīng)的物理地址97887011H。

知識點(diǎn)解析：暫無解析

44、設(shè)某計(jì)算機(jī)有四個(gè)中斷源，優(yōu)先順序按1—2—3一4降序排列，若1、2、3、4

中斷源的服務(wù)程序中對應(yīng)的屏蔽字分別為1110、0100、0110.1111,試寫出這四

個(gè)中斷源的中斷處理次序(按降序排列)。若四個(gè)中斷源同時(shí)有中斷請求，畫出CPU

執(zhí)行程序的軌跡。

標(biāo)準(zhǔn)答案：中斷處理次序(按降序排列)為：4-1-3-2,CPU執(zhí)行程序的軌跡如下圖8-

5所示。圖8T1、2、3、4級中斷源的中斷請

求同時(shí)出現(xiàn)，根據(jù)中斷響應(yīng)次序，首先響應(yīng)第1級中斷，但進(jìn)入中斷服務(wù)程序1之

后，發(fā)現(xiàn)其屏蔽字為1110,即對第4級中斷開放，所以應(yīng)先執(zhí)行中斷服務(wù)程序4,

當(dāng)中斷服務(wù)程序4執(zhí)行完畢，再返回執(zhí)行中斷服務(wù)程序1。接下來還剩下第2和3

級中斷，仍然先響應(yīng)第2級中斷，但進(jìn)入中斷服務(wù)程序2之后，發(fā)現(xiàn)其屏蔽字為

0100,對第3級中斷開放，所以應(yīng)先執(zhí)行中斷服務(wù)程序3,當(dāng)中斷服務(wù)程序3次行

完畢，再返回執(zhí)行中斷服務(wù)程序2。

知識點(diǎn)解析：暫無解析

45、某銀行的營業(yè)廳有多個(gè)柜員窗口，可以同時(shí)辦理業(yè)務(wù)。銀行的營業(yè)廳中安排有

n張座椅供儲戶休息等候。每個(gè)儲戶在進(jìn)入營業(yè)廳時(shí)會在排隊(duì)機(jī)上取得一個(gè)號碼，

若此前沒有客戶，則排隊(duì)機(jī)就會喚醒一個(gè)柜員為儲戶服務(wù)，當(dāng)沒有儲戶時(shí)柜員便可

以休息。若儲戶較多，則所有柜員均會參與服務(wù)，當(dāng)排隊(duì)儲戶數(shù)超過柜員數(shù)時(shí)，沒

有被服務(wù)的儲戶便會在座椅上休息，并等候叫號。當(dāng)座位滿時(shí)，再進(jìn)入營業(yè)廳的儲

戶不再從排隊(duì)機(jī)上獲取號碼，會離開去找另外的營業(yè)廳。若將銀行的柜員和儲戶的

行為看成是不同類型的進(jìn)程，請?jiān)O(shè)計(jì)一個(gè)程序，利用信號量來完成上述操作，用C

語言寫出程序。

標(biāo)準(zhǔn)答案：設(shè)信號量teller,customer和mutex,其中waiting是整型量，表示排隊(duì)

的儲戶數(shù)，其初始為。，最大不超過n。#defineCHAIRS=n//座椅數(shù)，也是最多

排隊(duì)的儲戶數(shù)typedefintsemaphore//定義信號量semaphoreteller：0；//等

待儲戶的柜員羲semaphorecustomer=0；//等待服務(wù)的儲戶數(shù)semaphore

mutex=0；//對排隊(duì)機(jī)操作的互斥量intwaiting=D；//等待的儲戶數(shù)void

teller()｛while(TRUE)//并發(fā)調(diào)度｛P(customer)；//查看有無儲戶P(mutex)；

//需要獲得排隊(duì)機(jī)的控制權(quán)waiting=waiting-l；//將等候的顧客數(shù)減1

V(leller)；//提供1個(gè)可服務(wù)的柜員V(mulex)：//釋放排隊(duì)機(jī)service。；/

/為儲戶服務(wù))｝voidcustomer()//儲戶進(jìn)程｛P(mutex)；//先獲得排隊(duì)機(jī)

if(waiting<CHAIRS)//若還有座椅則取號｛wailing=wailing+1；//取號，占

用座椅等待叫號V(customer)：//告知系統(tǒng)儲戶加1V(mutex)：//釋放排隊(duì)機(jī)

P(teller)；//看是否有柜員空閑serviced。；//進(jìn)入窗口被服務(wù)｝else//若沒

有座椅了，則不取號｛V(mutex)；//不取號，釋放排隊(duì)機(jī)｝｝//離開

知