2015年電子科技大學考研專業(yè)課試題計算機專業(yè)基礎

電子科技大學

2015年攻讀碩士學位研究生入學考試試題

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

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

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

一、填空題（5分，每空1分）

1.在生產(chǎn)者——消費者問題中，若10個生產(chǎn)者、5個消費者共享容量為8的緩沖區(qū)，則互

斥使用緩沖區(qū)的信號量的初值為。

2.某簡單段式存儲管理系統(tǒng)中，地址長度為32位，若允許的最大段長為64KB，則段號占

位。

3.設文件F1的當前引用計數(shù)值為1，先建立文件F1的符號鏈接（軟鏈接）文件F2，再建

立文件F1的硬鏈接文件F3，然后刪除文件F1。此時，文件F2和文件F3的引用計數(shù)值

分別為、。

4.某文件占10個磁盤塊，現(xiàn)要把該文件磁盤塊逐個讀入主存緩沖區(qū)，并送用戶區(qū)進行分

析。假設一個緩沖區(qū)與一個磁盤塊大小相同，把一個磁盤塊讀入緩沖區(qū)的時間為200μs，

將緩沖區(qū)的數(shù)據(jù)傳送到用戶區(qū)的時間為100μs，CPU分析一塊數(shù)據(jù)的時間為100μs，則

在雙緩沖區(qū)結構下，讀入并分析完該文件的時間為μs。

二、選擇題（10分，每題1分）

1.提高單機資源利用率的關鍵技術是（）。

A．脫機技術B．多道程序設計技術

C．虛擬技術D．緩沖技術

2.進程的基本狀態(tài)（）可以由其它兩種基本狀態(tài)轉變而來。

A．就緒狀態(tài)B．執(zhí)行狀態(tài)

C．阻塞狀態(tài)D．新建狀態(tài)

3.在高響應比進程調度算法中，其主要影響因素是（）。

A．等待時間B．剩余運行時間

C．已運行時間D．靜態(tài)優(yōu)先級

4.系統(tǒng)中資源R的數(shù)量為12，進程P1、P2、P3對資源R的最大需求分別為10、4、9。

若當前已分配給P1、P2、P3的資源R的數(shù)量分別為5、2、2，則系統(tǒng)（）。

A．處于不安全狀態(tài)

B．處于安全狀態(tài)，且安全序列為P1->P2->P3

C．處于安全狀態(tài)，且安全序列為P2->P3->P1

D．處于安全狀態(tài)，且安全序列為P2->P1->P3

5.分頁系統(tǒng)中的頁面為（）。

A．用戶所感知B．操作系統(tǒng)所感知

第1頁共8頁

C．編譯程序所感知D．鏈接、裝載程序所感知

6.虛擬存儲管理系統(tǒng)的基礎是程序的（）理論。

A．動態(tài)性B．虛擬性

C．局部性D．共享性

7.DMA是在（）建立一條直接數(shù)據(jù)通路。

A．I/O設備和主存之間B．I/O設備之間

C．I/O設備和CPU之間D．CPU和主存之間

8.程序員利用系統(tǒng)調用打開I/O設備時，通常使用的設備標識是（）。

A．主設備號B．次設備號

C．物理設備名D．邏輯設備名

9.虛擬設備是指（）

A．允許用戶以統(tǒng)一的接口使用物理設備

B．允許用戶使用比系統(tǒng)具有的物理設備更多的設備

C．把一個物理設備變換為多個對應的邏輯設備

D．允許用戶程序部分裝入內存即可使用系統(tǒng)中的設備

10.對目錄和文件的描述正確的是（）。

A．文件大小只受磁盤容量的限制

B．多級目錄結構形成一顆嚴格的多叉樹

C．目錄也是文件

D．目錄中可容納的文件數(shù)量只受磁盤容量的限制

三簡答題（20分，每題10分）

1.什么是臨界資源、死鎖？若采用以下算法解決哲學家就餐問題，是否會導致死鎖？為什

么？

semaphorefork[5]={1,1,1,1,1};

voidmain()

{

cobegin{

philosopher(0);

philosopher(1);

philosopher(2);

philosopher(3);

philosopher(4);

}coend

}

voidphilosopher(inti)

{

while(1){

thinking;

if(i==0){

P(fork[i]);

P(fork[(i+1)%5]);

}else{

第2頁共8頁

P(fork[(i+1)%5]);

P(fork[i]);

}

eating;

V(fork[i]);

V(fork[(i+1)%5]);

}

}

2.文件物理結構是指一個文件在外存上的存儲組織形式，主要有連續(xù)結構、鏈接結構和索

引結構三種，請分別簡述它們的優(yōu)缺點。

四、分析計算題（40分，每題20分）

1.某32位計算機采用二級頁表的分頁存儲管理方式，按字節(jié)編址，頁大小為4KB，頁表

項大小為4B。某進程的頁表內容如下圖所示（圖中數(shù)字為十進制），請回答以下問題：

（1）給出邏輯地址結構示意圖，請說明理由；

（2）計算邏輯地址4206501（十進制）對應的物理地址。

第3頁共8頁

…

頁表項序號

0

242

1372

2485101

……

n

…

0428

1367

2496242

……

n

物理塊號

…

0506

1607

2709372

……

n

…

0812

1942

一級頁表：

2321485

……

二級頁表：n

2.某雙車道公路中一小段因發(fā)生塌方事故，變成了單車道（對向行駛的車輛無法同時通

行），如下圖所示。為保證車輛順利通行，必須對經(jīng)過塌方路段的車輛予以控制。請用

信號量描述此控制過程，并說明信號量含義。

第4頁共8頁

塌方路段

單車道

正常路段正常路段

雙車道雙車道

第5頁共8頁

《數(shù)據(jù)結構》

一、填空題（共10分，每空1分）

1．數(shù)據(jù)的邏輯結構是對數(shù)據(jù)之間關系的描述，主要有和兩大類。

2．程序for(inti=0;i<n;i+=5)；的時間復雜度為。

3．在單鏈表L中的p結點之后插入q結點的操作是和。

4．循環(huán)隊列的容量為MAXSIZE，采用犧牲一個存儲空間進行構造，隊頭指針是front，隊

尾指針是rear，則隊空的條件是。

5．具有512個結點的完全二叉樹的深度為。

6．若以{5,6,7,8,9}作為葉結點的權值構造哈夫曼樹，則其帶權路徑長度是。

7．G是一個非連通無向圖，共有15條邊，則該圖至少有個頂點。

8．設有一組初始關鍵字序列（46,79,56,38,40,84），執(zhí)行第一趟快速排序后所得序列

是。

二、單選題（共20分，每題2分）

1．具有n個元素的線性表采用順序存儲結構，在其第i個位置插入一個新元素的算法時間

復雜度為（）（1≤i≤n+1）。

A．O（1）B．O（i）C．O（n）D．O（n2）

2．一個棧的輸入序列為1,2,3，…，n，若輸出序列的第一個元素是n，輸出第i（1≤i≤n）

個元素是（）。

A．n-iB．n-i-1C．n-iD．i

3．廣義表（（a,（b,c））,d,e）的表頭是（）。

A．a(chǎn)B．（a,（b，c））C．（a）D．（b，c）

4．以下哪些遍歷序列的組合可以還原二叉樹（）。

A．先序遍歷序列和后序遍歷序列B．后序遍歷序列和中序遍歷序列

C．先序遍歷序列和層序遍歷序列D．中序遍歷序列和層序遍歷序列

5．與克魯斯卡爾（Kruskal）相比，普里姆（Prim）算法更適于求哪種網(wǎng)的最小生成樹（）。

A．邊稠密的網(wǎng)B．邊稀疏的網(wǎng)C．頂點稠密的網(wǎng)D．以上都不是

6．關鍵路徑是事件結點網(wǎng)絡中（）。

A．從源點到匯點的最短路徑B．從源點到匯點邊數(shù)最多的路徑

C．從源點到匯點結點數(shù)最多的路徑D．從源點到匯點的最長路徑

7．若用鄰接矩陣存儲有向圖，矩陣中主對角線以下元素均為零，則關于該圖拓撲序列的結

論是（）。

A．存在，且唯一B．存在，但不唯一

C．存在，可能不唯一D．無法確定是否存在

8．在下列排序算法中，占用輔助空間最多的是（）

A．歸并排序B．快速排序C．希爾排序D．堆排序

9．設哈希表長m=9,哈希函數(shù)H（key）=key%7。表中已填關鍵字：13,25,68，其余地址為

空，如用二次探測再散列處理沖突，關鍵字為75的地址是（）。

A．1B．3C．7D．9

10.已知關鍵字序列5,8,12,19,28,20,15,22是小根堆（堆頂元素為最小值），插入關鍵字

3，調整后得到的小根堆是（）。

A．3,5,12,8,28,20,15,22,19B．3,5,12,19,20,15,22,8,28

第6頁共8頁

C．3,8,12,5,20,15,22,28,19D．3,12,5,8,28,20,15,22,19

三、簡答題（共20分，每題5分）

1.對任何一顆二叉樹T