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

考試科目：計(jì)算機(jī)專業(yè)基礎(chǔ)（B）

注意事項(xiàng)：

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

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

3、必須用藍(lán)黑鋼筆或簽字筆答題，其他均無(wú)效。

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

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

一、單項(xiàng)選擇題（每小題1分，共10分）

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

A、硬件 B、軟件 C、計(jì)算機(jī)資源 D、應(yīng)用程序

2、在單處理機(jī)系統(tǒng)中實(shí)現(xiàn)并發(fā)技術(shù)后，(   )。

A、進(jìn)程在一個(gè)時(shí)間段內(nèi)并行運(yùn)行，CPU與外設(shè)間并行工作。

B、進(jìn)程在一個(gè)時(shí)刻點(diǎn)上并行運(yùn)行，CPU與外設(shè)間并行工作.

C、進(jìn)程在一個(gè)時(shí)間段內(nèi)并行運(yùn)行，CPU與外設(shè)間串行工作.

D、進(jìn)程在一個(gè)時(shí)刻點(diǎn)上并行運(yùn)行，CPU與外設(shè)間串行工作.

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

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

4、某系統(tǒng)中有3個(gè)并發(fā)進(jìn)程，都需要4個(gè)同類資源。試問(wèn)該系統(tǒng)不會(huì)產(chǎn)生死鎖的最少資源總數(shù)應(yīng)該是(   )。

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

5、若信號(hào)量S初值為2，當(dāng)前值為1，則表示有(   )個(gè)進(jìn)程在與S相關(guān)的隊(duì)列上等待。

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

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

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

C、 段式存儲(chǔ)管理      D、段頁(yè)式存儲(chǔ)管理

7、以下(   )不是設(shè)備管理使用的數(shù)據(jù)結(jié)構(gòu)。

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

8、假設(shè)一個(gè)扇區(qū)大小為512B，1塊=1扇區(qū)，F(xiàn)AT16可以管理的磁盤空間大小為(   )。  

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

9、用戶可以通過(guò)調(diào)用(   )文件操作，來(lái)歸還文件的使用權(quán)。

A．建立   B．打開(kāi)   C．關(guān)閉   D．刪除

10、在設(shè)備管理中,通常采用主設(shè)備號(hào)和次設(shè)備號(hào)來(lái)表示一臺(tái)機(jī)器, 主設(shè)備號(hào)和次設(shè)備號(hào)分別表示(  )。

A． 設(shè)備類型和內(nèi)部標(biāo)識(shí)符   B. 設(shè)備驅(qū)動(dòng)程序及參數(shù)

C． 設(shè)備名字及其類型     D. 設(shè)備名字及參數(shù)

二、應(yīng)用題（每小題15分，共60分）

1、桌子上有一只盤子，每次只能放入一只水果，爸爸專門往盤子里放蘋果，媽媽專門往盤子里放橘子，一個(gè)兒子專門吃盤子里的橘子，一個(gè)女兒專門等吃盤子里的蘋果，用信號(hào)量實(shí)現(xiàn)爸爸、媽媽、兒子、女兒之間的同步與互斥關(guān)系。

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

作業(yè)號(hào) 到達(dá)時(shí)間 所需CPU時(shí)間

1 9:00 70分鐘

2 9:40 30分鐘

3 9:50 10分鐘

4 10:10 5分鐘

分別采用先來(lái)先服務(wù)和短作業(yè)優(yōu)先作業(yè)調(diào)度算法。試問(wèn)它們的調(diào)度順序、作業(yè)周轉(zhuǎn)時(shí)間以及平均周轉(zhuǎn)時(shí)間各是什么？

3、在某個(gè)請(qǐng)求分頁(yè)管理系統(tǒng)中，假設(shè)某進(jìn)程的頁(yè)表內(nèi)容如下所示有效位（存在位）

0 120H 1 

1 ---- 0 

2 850H 1

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

a．依次訪問(wèn)上述三個(gè)虛地址，各需多少時(shí)間？給出計(jì)算過(guò)程。

b．基于上述訪問(wèn)序列，虛地址1876H的物理地址是多少？請(qǐng)說(shuō)明理由。

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

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

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

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

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

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

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

3、中序遍歷結(jié)果為DBEAFC，一棵二叉樹的前序遍歷結(jié)果為ABDECF，則后序遍歷結(jié)果為_(kāi)_________。       

4、在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)__________倍。

5、具有10個(gè)葉結(jié)點(diǎn)的二叉樹中有__________個(gè)度為2的結(jié)點(diǎn)。       

6、對(duì)于隊(duì)列操作數(shù)據(jù)的原則是__________。 

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

9、對(duì)具有15個(gè)關(guān)鍵字的關(guān)鍵字序列進(jìn)行順序查找時(shí)，查找成功的平均查找長(zhǎng)度__________。           

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

二、應(yīng)用題（每題15分，共45分）

1、給定如下無(wú)向帶權(quán)連通圖G, 從頂點(diǎn)v0開(kāi)始，使用普里姆(Prim)算法，求G的最小生成樹T。請(qǐng)回答下列問(wèn)題。

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

（2）（6分）計(jì)算T中各邊權(quán)值之和。

2、若有一個(gè)無(wú)向圖，

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

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

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

三、算法設(shè)計(jì)題（15分）

下面給出二叉樹的結(jié)點(diǎn)定義：

typedef struct node

{

  int data;

struct node *lchild, *rchild;

} BinTnode;

typedef BinTNode BinTree;

請(qǐng)編寫函數(shù)SearchXNum，計(jì)算任意二叉樹T中其數(shù)據(jù)域的值大于或等于x的結(jié)點(diǎn)的個(gè)數(shù)并返回該值。函數(shù)原型如下：

int searchXNum(BinTree *T, int x);

（以下空白）