暨南大學2020年《848計算機基礎綜合》碩士研究生入學考試真題

1、2020年招收攻讀碩士學位研究生入學考試試題（B）*招生專業(yè)與代碼：計算機系統(tǒng)結構081201、計算機軟件與理論081202、計算機應用技術081203、電子信息(專業(yè)學位) 085400考試科目名稱及代碼：計算機基礎綜合848考生注意：所有答案必須寫在答題紙（卷）上，寫在本試題上一律不給分。 第一部分 數(shù)據(jù)結構（75分）單項選擇題(每題2分，共20分) 1. 含有m個結點的二叉樹鏈式存儲結構中空指針的個數(shù)為 ( )。A2m Bm-1 Cm+1 Dm2. 下列排序算法中元素的移動次數(shù)和關鍵字的初始排列次序無關的是（ ）。A. 快速排序 B. 插入排序 C. 選擇排序 D. 希爾排序3. 一個棧

2、的進棧序列是a b c d e，則棧的輸出序列不可能的是（ ）。 Aa b c d e Be d c b a Cd e c b a Dd c e a b4. 需要的輔助空間最多的排序算法為（ ）。 A. 歸并排序 B. 快速排序 C. 基數(shù)排序 D. 堆排序5. 哈希表的平均查找長度說法錯誤的是 ( )。 A. 與處理沖突方法有關而與表的長度無關 B. 與選用的哈希函數(shù)有關 C. 與哈希表的飽和程度有關 D. 與表中填入的記錄數(shù)有關6. 有n個頂點 、e條邊且使用了鄰接表存儲的有向圖進行深度優(yōu)先遍歷，其算法的時間復雜度是（ ）。 A. O（n+e） B. O（n2） C. O（n+2e） D.

3、 O（n*e）7. 已知一個長度為11的順序表，其元素按關鍵字有序排列，若采用折半查找查找一個其中不存存在的元素，則關鍵字的比較次數(shù)最多是（ ）。A3 B4 C5 D68. 一棵完全二叉樹上有3001個結點，其中葉子結點的個數(shù)是（ ）。 A. 1500 B.1501 C. 1000 D.10019. 若一棵二叉樹度為2的結點有18個，度為1的結點有10個，則度為0的結點個數(shù)是（ ）。 A. 46 B. 28 C. 19 D. 1710. m階B-樹是一棵（ ）。A .m叉排序樹 B. m-1叉平衡排序樹 C. m叉平衡排序樹 D. m+1叉平衡排序樹填空題(每空2分，共14分)1. 已知一棵二

4、叉樹的中序遍歷序列為GDHBAECIF，后序遍歷序列為GHDBEIFCA，那么先序遍歷序序列為 。考試科目：計算機基礎綜合 共 4 頁，第 1 頁2. 若某記錄的關鍵字序列是（491，77，572，16，996，101，863，258，689，325），以第一個關鍵字為樞軸，寫出采用快速排序算法第一趟排序的結果 。3. 將對稱矩陣A88的下三角部分逐行存儲到起始地址為2000的內存單元中，已知每個元素占4個單元，假設第一個元素是A00，則A46的地址是 。4. 在順序表中插入一個元素，需要平均移動表中一半元素，具體移動元素的個數(shù)與 有關。5.在哈希查找方法中，要解決兩方面的問題，它們是 和 。

5、6. 循環(huán)隊列中，Q.rear = Q.front表示循環(huán)隊列空，表示循環(huán)隊列滿的條件是 。簡答題（共3小題，每題7分，共21分）1. 將下面的森林轉換為二叉樹（3分），并給出該二叉樹的中序線索鏈表（4分）。 ABCDEFGH 2. 設Huffman編碼的長度不超過4，若已對兩個字符編碼為01和11，則最多還可以對多少個字符編碼，為什么？(7分）3. 假設圖的頂點是A、B、C、D、E，請根據(jù)下面的鄰接矩陣畫出相應的有向圖（3分），然后畫出圖的鄰接表和逆鄰接表（4分）。編寫算法（共2小題，每題10分，共20分）1. 試編寫一個算法完成下面的功能：對于輸入的任意一個非負十進制整數(shù)，輸出與其等值的八

6、進制數(shù)。（10分）2. 試編寫一個算法，在有向圖G中，判定從頂點Vi到頂點Vj是否有通路。（10分）第二部分 操作系統(tǒng)（75分）判斷題(每小題1分，共10分，正確的打，錯誤的打)1. 系統(tǒng)調用中的被調用程序運行在系統(tǒng)態(tài)。2. 銀行家算法采用了死鎖預防的方法。3. 文件系統(tǒng)采用樹形目錄結構可以節(jié)省內存空間。4. 虛存管理允許用戶程序大于主存容量，而且還可以提高系統(tǒng)的吞吐量?？荚嚳颇浚河嬎銠C基礎綜合 共 4 頁，第 2 頁5. SPOOLing系統(tǒng)實現(xiàn)了設備的獨立性。6. 分時系統(tǒng)的時間片越小，用戶的滿意度就越高。7. 管程每次只允許一個進程進入。8. 操作系統(tǒng)既可看作虛擬機，也可看作資源管理器。

7、9. 在作業(yè)調度時，采用最高響應比優(yōu)先的作業(yè)調度算法可以得到最短的作業(yè)平均周轉時間。10. 并行程序設計中，使用信號量比使用管程更能保證程序的正確性。填空題 (每小題1分，共10分)1. 對于速率為9.6KB/s的數(shù)據(jù)通信而言，如果設置一個具有8位的緩沖寄存器，則CPU中斷時間和響應時間分別大約為 （1） 、 （2） 。2. 如果計算機連接了三個同類型的激光打印機及五個同類型的噴墨打印機，需要安裝的驅動程序數(shù)目是 （3） 。3. 在具有n個進程的系統(tǒng)中，允許m個進程(nm1)同時進入它們的臨界區(qū)，其信號量S的值的變化范圍是 （4） ，處于等待狀態(tài)的進程數(shù)最多有 （5） 個。4. 動態(tài)分區(qū)的 （

8、6） 算法可以使內存中的空閑分區(qū)分布得更均勻。5. UNIX的目錄項由文件名和 （7） 構成。6. 若干事件在同一時間間隔內發(fā)生稱為 （8） 。7. 虛擬存儲器具有 （9） 、 （10） 和虛擬性三大特征。單選題(每小題1分，共10分)1. 請求調頁系統(tǒng)中，如下算法中，( ) 淘汰自上次訪問以來經歷時間最長的頁面。 A. FIFO B. OPT C. NRU D. LRU2. 下列進程調度算法中，( ) 可能會出現(xiàn)進程長期得不到調度的情況。 A. 靜態(tài)優(yōu)先權法 B. 搶占式調度中采用動態(tài)優(yōu)先權法 C. 分時處理中的時間片輪轉調度算法 D. 非搶占式調度中采用FIFO算法3. 分時系統(tǒng)中，CPU

9、進程切換需要3ms，為使得100個用戶均能在1秒內得到響應，可以選擇的時間片是（ ）。A. 2ms B. 50 ms C. 10ms D. 7 ms4. 磁盤的I/O控制主要采取( ) 方式。 A. 程序I/O B. 中斷 C. DMA D. SPOOLing5. 系統(tǒng)產生死鎖是指( ) 。A. 系統(tǒng)發(fā)生重大故障 B. 若干進程同時處于阻塞狀態(tài) C. 請求的資源數(shù)大于系統(tǒng)提供的資源數(shù) D. 若干進程等待被其他進程所占用而又不可能被釋放的資源6. 通道又稱I/O處理機，它用于實現(xiàn)( ) 之間的信息傳輸。 A. CPU與外存 B. CPU與外設 C. 內存與外存 D. 內存與外設7. 下面敘述正確

10、的是( ) 。 A. 程序段是進程存在的唯一標志 B. 系統(tǒng)通過PCB來控制和管理進程，用戶可以從PCB中讀出與本身運行狀態(tài)相關的信息 C. 當進程有執(zhí)行狀態(tài)變?yōu)榫途w狀態(tài)時，CPU現(xiàn)場信息必須被保存在PCB中 D. 當進程申請CPU得不到滿足時，它將處于阻塞狀態(tài)8. 在沒有快表的情況下，分頁系統(tǒng)要訪問( )次內存。 A. 1 B. 2 C .3 D. 4考試科目：計算機基礎綜合 共 4 頁，第 3 頁9. 計算機操作系統(tǒng)中，若WAIT、SIGNAL操作的信號量S初值為3，當前值為-4，則表示當前有( ) 個等待信號量S的進程。 A. 1 B. 2 C. 3 D. 410. 有10個進程共享5個打印機，若信號量S的當前值是-2，則當前有( )個進程提出了打印請求？A. 10 B. 7 C. 5 D. 2簡答題(每小題5分，共25分)1. 什么是文件目錄、目錄文件，各起什么作用？ 2. 多級樹形目錄的文件系統(tǒng)，怎樣才能提高查找文件的速度?3. 多線程系統(tǒng)與傳統(tǒng)多進程系統(tǒng)相比有哪些優(yōu)點？4. 分頁存儲管理和分段存儲管理的主要區(qū)別有哪些？5. 用偽代碼或文字描述fork()系統(tǒng)調用是如何創(chuàng)建進程的。應用題(每小題10分，共20分)1. 某類Unix系統(tǒng)采用成組鏈接法來管理磁盤的空閑空間，目前磁