2016年電子科技大學(xué)考研專業(yè)課試題計算機專業(yè)基礎(chǔ)

電子科技大學(xué)

2016年攻讀碩士學(xué)位研究生入學(xué)考試試題

考試科目：820計算機專業(yè)基礎(chǔ)

注：所有答案必須寫在答題紙上，寫在試卷或草稿紙上均無效。

《計算機操作系統(tǒng)》

一、填空題（10分，每空2分）

1.若信號量S的初值為4，當(dāng)前有6個進程在等待信號量S，則當(dāng)前信號量S的值為。

2.某系統(tǒng)中共有11臺打印機，X個進程共享此打印機，每個進程最多請求使用3臺打印

機，則該系統(tǒng)中不會發(fā)生死鎖的最大X值是。

3.虛擬存儲管理系統(tǒng)的基礎(chǔ)是程序的理論。

4.為滿足264地址空間的作業(yè)運行，采用多級分頁存儲管理方式，假設(shè)頁面大小為4KB，

在頁表中的每個頁表項需要占8字節(jié)。那么，為了滿足系統(tǒng)的分頁存儲管理，至少應(yīng)采

用級頁表。

5.某文件系統(tǒng)的文件控制塊占64B，單個盤塊大小為1KB，采用一級目錄結(jié)構(gòu)。假設(shè)文件

目錄中有3200個目錄項，則查找一個文件平均需要訪問次磁盤。

二、選擇題（14分，每題2分）

1.若下列指令已裝入指令寄存器，執(zhí)行時不可能導(dǎo)致CPU從用戶態(tài)變?yōu)閮?nèi)核態(tài)的是（）。

A．DIVR0，R1；(R0)/(R1)→R0

B．INTn；產(chǎn)生軟中斷

C．NOTR0；寄存器R0的內(nèi)容取非

D．MOVR0,addr；把地址處的內(nèi)存數(shù)據(jù)放入寄存器R0中

2.在下列進程調(diào)度算法中，不存在進程饑餓現(xiàn)象的調(diào)度算法是（）。

A．先來先服務(wù)B．反饋調(diào)度算法

C．短進程優(yōu)先D．基于靜態(tài)優(yōu)先級調(diào)度算法

3.資源的有序分配策略是為了破壞死鎖產(chǎn)生的（）條件。

A．互斥B．請求和保持

C．非剝奪D．循環(huán)等待

4.在段式存儲管理系統(tǒng)中，若不考慮快表，為獲得一條指令或數(shù)據(jù)，至少需要訪問（）

次內(nèi)存。

A．1B．2

C．3D．4

5.在設(shè)備管理中，不屬于I/O控制方式的是（）。

A．程序查詢方式B．中斷驅(qū)動方式

C．DMA方式D．重定位方式

第1頁共4頁

6.下列文件物理結(jié)構(gòu)中，適合隨機訪問且易于文件擴展的是（）。

A．哈希文件B．索引文件

C．鏈?zhǔn)浇Y(jié)構(gòu)文件D．連續(xù)結(jié)構(gòu)文件

7.設(shè)置當(dāng)前工作目錄的主要作用是（）。

A．加快文件的讀/寫速度B．加快文件的檢索速度

C．節(jié)省外存空間D．節(jié)省內(nèi)存空間

三、簡答題（4題，共21分）

1.PCB的主要存儲內(nèi)容是什么？為什么說PCB是進程存在的唯一標(biāo)志？（6分）

2.什么是虛擬存儲器？如何實現(xiàn)頁式虛擬存儲器？（5分）

3.什么是設(shè)備的獨立性，應(yīng)如何實現(xiàn)？（5分）

4.文件物理結(jié)構(gòu)是指一個文件在外存上的存儲組織形式，那么何謂文件的混合索引結(jié)構(gòu)？

其主要優(yōu)點是什么？（5分）

四、分析計算題（2題，共30分）

1.某計算機采用段頁式虛擬存儲器，已知虛擬地址為32位，按字節(jié)編址，每個段最多可

以有2K頁，頁大小為16KB，物理主存容量為512MB。請回答以下問題：（10分）

（1）虛擬存儲器的容量是多少？

（2）給出邏輯地址結(jié)構(gòu)并說明理由。

（3）計算邏輯地址0X4EB9FDE3的段號，段內(nèi)頁號及頁內(nèi)偏移值（最后計算結(jié)果須

用十六進制表示）。

2.N個生產(chǎn)者進程和M個消費者進程共享大小為K的緩沖區(qū)，遵循規(guī)則如下：

（1）進程之間必須以互斥方式訪問緩沖區(qū)；

（2）對每1條放入緩沖區(qū)的數(shù)據(jù)，所有消費者都必須接收1次；

（3）緩沖區(qū)滿時，生產(chǎn)者必須阻塞；

（4）緩沖區(qū)空時，消費者必須阻塞。

請用P、V操作實現(xiàn)其同步過程，須說明信號量含義。（20分）

第2頁共4頁

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

一、填空題(共10空，每空1分，共10分)

1.順序表采用的是_________存取方式，線性鏈表采用的是_________存取方式。

2.深度為dd,(1)的完全二叉樹至少含有_________個節(jié)點，至多含有_________個節(jié)點。

3.3個節(jié)點構(gòu)成的二叉樹有____種不同形狀。3個元素依次入?？赡艿某鰲Ｐ蛄杏衉___種。

4.無向連通圖G含有n個節(jié)點e條邊。求G的最小生成樹，采用Prim算法的時間復(fù)雜度

是________，采用Kruskal算法的時間復(fù)雜度是________。

5.快速排序算法平均情況下的時間復(fù)雜度是_________，空間復(fù)雜度是_________。

二、單選題(共10題，每題2分，共20分)

1.循環(huán)隊列為了防止假上溢采用取模運算折疊空間，解決隊頭隊尾指針同指一個單元時候

空滿判定問題，下列()選項不是常見的方案。

A.犧牲一個存儲空間B.設(shè)置一個計數(shù)器C.設(shè)置一個布爾變量D.再配置一個指針

2.下列選項中不屬于規(guī)則矩陣的是()。

A.三角矩陣B.對稱矩陣C.對角矩陣D.稀疏矩陣

3.下列選項中符合前綴碼要求的是()。

A.{0,1}B.{0,01,001,0001}C.{10,010,110,101}D.{01,10,1001,0110}

4.下列關(guān)于哈夫曼樹的論述不正確的是()。

A.哈夫曼樹又被稱為最優(yōu)二叉樹

B.哈夫曼樹是帶權(quán)路徑最短的二叉樹

C.一棵哈夫曼樹任意交換左右子樹仍然是一棵哈弗曼樹

D.對給定的輸入數(shù)值集合所生成的哈夫曼樹深度是確定的

5.無向圖做深度優(yōu)先搜索和廣度優(yōu)先搜索共有的特點是()

A.都是遞歸類算法B.都必須用到棧C.都是遍歷類算法D.搜索結(jié)果都是唯一的

6.對于AOE網(wǎng)絡(luò)，若它的關(guān)鍵路徑存在，那么該路徑一定是()。

A.最長路徑B.最短路徑C.拓?fù)渑判蛐蛄蠨.唯一的一條路徑

7.拓?fù)渑判蚪鉀Q的問題是()。

A.對一個有向圖進行遍歷操作B.計算一個有向圖的回路個數(shù)

C.判斷一個有向圖是否有回路D.對一個有向圖進行線索化

8.已知廣義表GL=((a,b),(c,d,e),(f,g))，定義取表頭函數(shù)為H()，取表尾函數(shù)為T()，那么

從GL中取出數(shù)據(jù)元素d的操作是()。

A.H(T(T(H(GL))))B.H(T(H(GL))))C.H(T(H(T(GL))))D.H(T(H(H(GL))))

9.對序列(2,4,6,8,10,12,14,16,18,20)進行折半查找元素14，需要依次比較()。

A.10,18,14B.10,16,14C.10,18,12,14D.10,16,12,14

第3頁共4頁

10.下列哪種排序算法在一趟過后不能保證至少有一個元素落在最終位置上的是()。

A.冒泡排序B.希爾排序C.快速排序D.簡單選擇排序

三、簡答題(共6題，每題5分，共30分)

1.設(shè)計一種盡可能高效的策略使得單循環(huán)鏈表成為隊列，給出入隊和出隊的時間復(fù)雜度。

2.輸入數(shù)據(jù)序列為(5,1,9,3,7)，請按輸入序構(gòu)造排序二叉樹，并繪制出它的中序線索。

3.輸入數(shù)據(jù)序列為(10,30,40,20,15,25)，請按輸入序構(gòu)造平衡二叉樹。給出每添加一個節(jié)

點后平衡二叉樹的調(diào)整結(jié)果。

4.已知輸入關(guān)鍵字序列為(13,14,15,16,17,5,4,3,2,1)，根據(jù)哈希函數(shù)建立哈希表，采用公

共溢出區(qū)法解決沖突。已知哈希函數(shù)為Hash(key)=keyMOD11，哈希表長為11，溢出表長

為5。請畫出哈希表和溢出表，并計算查找成功時(等概率情況下)的平均查找長度ASL。

5.已知7項數(shù)據(jù)記錄為(7,6,5,4,3,2,1)。將它調(diào)整成為小頂堆，給出篩選過程。

6.全源最短路徑問題采用Floyd算法進行求解。下面給出了一個由4個頂點構(gòu)成的有向圖

鄰接矩陣Dist[4][4]和路徑矩陣Path[4][4]。約定Dist中用∞表示不能到達，Path中

用-1表示沒有前驅(qū)的情況。請計算并給出每一次迭代的結(jié)果。(請將答案謄寫在答題紙上)

Dist(-1)Dist(0)Dist(1)Dist(2)Dist(3)

01230123012301230123

0014∞

1∞025

2∞∞01

32∞∞0

Path(-1)Path(0)Path(1)Path(2)Path(3)

01230123012301230123

0-100-1

1-1