閩南師范大學2018年碩士研究生入學考試試題

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

注意事項：

1、本卷滿分為150分，考試時間為3小時；

2、本卷屬試題卷，另有答題紙，答案一律寫在答題紙上，寫在該試卷或草稿紙上均無效；

3、必須用藍黑鋼筆或簽字筆答題，其他均無效。

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

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

一、單項選擇題（每小題1分，共10分）

1、操作系統(tǒng)是對(   )進行管理的軟件。

A、硬件 B、軟件 C、計算機資源 D、應用程序

2、在單處理機系統(tǒng)中實現并發(fā)技術后，(   )。

A、進程在一個時間段內并行運行，CPU與外設間并行工作。

B、進程在一個時刻點上并行運行，CPU與外設間并行工作.

C、進程在一個時間段內并行運行，CPU與外設間串行工作.

D、進程在一個時刻點上并行運行，CPU與外設間串行工作.

3、計算機系統(tǒng)在執(zhí)行(   )時，會自動從目態(tài)變換到管態(tài)。

A. P操作    B．V操作   C．系統(tǒng)調用     D．I/O指令

4、某系統(tǒng)中有3個并發(fā)進程，都需要4個同類資源。試問該系統(tǒng)不會產生死鎖的最少資源總數應該是(   )。

A．9  B．10  C．11  D．12

5、若信號量S初值為2，當前值為1，則表示有(   )個進程在與S相關的隊列上等待。

A．0  B．1  C．2  D．3

6、以下(   )不可以提供虛存。

A、 可變分區(qū)存儲管理    B、頁式存儲管理

C、 段式存儲管理      D、段頁式存儲管理

7、以下(   )不是設備管理使用的數據結構。

A．JCB   B.DCT   C.COCT   D. CHCT

8、假設一個扇區(qū)大小為512B，1塊=1扇區(qū)，FAT16可以管理的磁盤空間大小為(   )。  

A.32MB   B.64MB  C.128MB  D.512MB

9、用戶可以通過調用(   )文件操作，來歸還文件的使用權。

A．建立   B．打開   C．關閉   D．刪除

10、在設備管理中,通常采用主設備號和次設備號來表示一臺機器, 主設備號和次設備號分別表示(  )。

A． 設備類型和內部標識符   B. 設備驅動程序及參數

C． 設備名字及其類型     D. 設備名字及參數

二、應用題（每小題15分，共60分）

1、桌子上有一只盤子，每次只能放入一只水果，爸爸專門往盤子里放蘋果，媽媽專門往盤子里放橘子，一個兒子專門吃盤子里的橘子，一個女兒專門等吃盤子里的蘋果，用信號量實現爸爸、媽媽、兒子、女兒之間的同步與互斥關系。

2、設有一組作業(yè)，它們的到達時間和所需CPU時間如下所示。

作業(yè)號 到達時間 所需CPU時間

1 9:00 70分鐘

2 9:40 30分鐘

3 9:50 10分鐘

4 10:10 5分鐘

分別采用先來先服務和短作業(yè)優(yōu)先作業(yè)調度算法。試問它們的調度順序、作業(yè)周轉時間以及平均周轉時間各是什么？

3、在某個請求分頁管理系統(tǒng)中，假設某進程的頁表內容如下所示有效位（存在位）

0 120H 1 

1 ---- 0 

2 850H 1

頁面大小為4KB，一次內存的訪問時間是200ns，一次快表（TLB）的訪問時間是20ns，處理一次缺頁的平均時間為 ns（己含更新TLB和頁表的時間），進程的駐留集大小固定為二頁，采用最近最久未使用置換算法（LRU）和局部置換策略。假設①TLB初始為空；②地址轉換時先訪問TLB，若TLB未命中，再訪問頁表（忽略訪問頁表之后的TLB更新時間）；③有效位為0表示頁面不在內存，產生缺頁中斷，缺頁中斷處理后，返回到產生缺頁中斷的指令處重新執(zhí)行。設有虛地址訪問序列2345H、1876H、258FH，請問：

a．依次訪問上述三個虛地址，各需多少時間？給出計算過程。

b．基于上述訪問序列，虛地址1876H的物理地址是多少？請說明理由。

4、假設某文件系統(tǒng)的硬盤空間為500MB，盤塊大小為1KB，采用顯示鏈接分配，請回答以下問題：

(1)其FAT表（文件分配表）需占用多少存儲空間？

(2)如果文件A占用硬盤的盤塊號依次為120、130、145、135、125共五個盤塊，請畫圖示意文件A的FCB與FAT表的關系以及FAT表中各盤塊間的鏈接情況。

數據結構

一、填空題（每題2分，共20分）

1、已知一無向圖G=（V，E），其中V={a,b,c,d,e,f } E={(a,b),(d,e), (b,c),(a,f),(a,d)}現用某一種圖遍歷方法從頂點a開始遍歷圖，得到的序列為abfdce，則采用的是__________遍歷方法。               

2、在循環(huán)隊列中，若front與rear分別表示隊頭元素和隊尾的位置，則判斷循環(huán)隊列空的條件是__________。 

3、中序遍歷結果為DBEAFC，一棵二叉樹的前序遍歷結果為ABDECF，則后序遍歷結果為__________。       

4、在一個無向圖中，所有頂點的度數之和等于所有邊數__________倍。

5、具有10個葉結點的二叉樹中有__________個度為2的結點。       

6、對于隊列操作數據的原則是__________。 

7、假定一組記錄的排序碼為（46，79，56，38，40，80），對其進行快速排序的一次劃分的結果__________。 8、廣義表A=( a, ( b, c ( d, e, f ) ) )的長度是__________。             

9、對具有15個關鍵字的關鍵字序列進行順序查找時，查找成功的平均查找長度__________。           

10、在鏈表中進行刪除操作和_________操作的效率高于順序表。

二、應用題（每題15分，共45分）

1、給定如下無向帶權連通圖G, 從頂點v0開始，使用普里姆(Prim)算法，求G的最小生成樹T。請回答下列問題。

（1）（9分）畫出最小生成樹T。

（2）（6分）計算T中各邊權值之和。

2、若有一個無向圖，

（1）（7分）畫出該無向圖的鄰接矩陣；

（2）（8分）畫出該無向圖的鄰接表。

3、設哈希表的地址范圍0~17，哈希函數為H(k)=k MOD 16。k為關鍵字，用線性探測法處理沖突，輸入關鍵字序列:(10, 24, 32, 17, 31, 30, 46, 47, 40, 63, 49)。畫出哈希表的示意圖;若查找關鍵字63，需要依次與哪些關鍵字進行比較？若查找關鍵字60，需要依次與哪些關鍵字比較？

三、算法設計題（15分）

下面給出二叉樹的結點定義：

typedef struct node

{

  int data;

struct node *lchild, *rchild;

} BinTnode;

typedef BinTNode BinTree;

請編寫函數SearchXNum，計算任意二叉樹T中其數據域的值大于或等于x的結點的個數并返回該值。函數原型如下：

int searchXNum(BinTree *T, int x);

（以下空白）