電子科技大學(xué)820計算機(jī)基礎(chǔ)考試大綱

1、考試科目820計算機(jī)專業(yè)基礎(chǔ)考試形式筆試（閉卷）考試時間180分鐘考試總分150分本科目包括數(shù)據(jù)結(jié)構(gòu)和計算機(jī)操作系統(tǒng)兩門課程，總分150分，兩門課程各占75分?jǐn)?shù)據(jù)結(jié)構(gòu)一、總體要求 數(shù)據(jù)結(jié)構(gòu)是計算機(jī)程序設(shè)計的重要理論技術(shù)基礎(chǔ)，是計算機(jī)科學(xué)與技術(shù)學(xué)科的核心課程。要求學(xué)生通過數(shù)據(jù)結(jié)構(gòu)課程的學(xué)習(xí)，能夠針對具體的應(yīng)用和算法策略選擇和設(shè)計恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)，并能編程實現(xiàn)。二、內(nèi)容及比例數(shù)據(jù)結(jié)構(gòu)部分主要考試內(nèi)容（帶下劃線文字表示重點部分）：1. 數(shù)據(jù)結(jié)構(gòu)及算法的相關(guān)概念和術(shù)語重點：數(shù)據(jù)結(jié)構(gòu)及算法的概念；數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)；算法的定義及特性；算法時間復(fù)雜度和空間復(fù)雜度的分析方法。2線性表（包括棧、隊列和數(shù)組

2、）的存儲結(jié)構(gòu)、基本運算及應(yīng)用重點：線性表、棧和隊列的存儲結(jié)構(gòu)及其存儲特點；線性表的基本操作在順序存儲及鏈?zhǔn)酱鎯ι系膶崿F(xiàn)；各種變形鏈表（循環(huán)鏈表、雙向鏈表、帶頭結(jié)點的鏈表等）的表示和基本操作的實現(xiàn)；遞歸過程的特點及實現(xiàn)方法；循環(huán)隊列的判滿、判空方法；稀疏矩陣的存儲方法（三元組、十字鏈表）和基本運算的實現(xiàn)（轉(zhuǎn)置、矩陣加法等）。3廣義表的存儲結(jié)構(gòu)、基本運算及應(yīng)用重點：廣義表的基本概念、基本操作及存儲結(jié)構(gòu)。4樹和二叉樹的存儲結(jié)構(gòu)、遍歷算法及應(yīng)用重點：二叉樹和樹的遞歸定義、基本術(shù)語、基本性質(zhì)；滿二叉樹和完全二叉樹的概念及特征；二叉樹、樹及森林的順序存儲及鏈?zhǔn)酱鎯Γ约跋嗷マD(zhuǎn)換算法；線索二叉樹、二叉排序樹

3、的構(gòu)建；各種遍歷算法；哈夫曼樹和哈夫曼編碼的構(gòu)建和應(yīng)用。5圖的存儲結(jié)構(gòu)、遍歷算法及應(yīng)用重點：圖的基本概念和術(shù)語；圖的基本存儲方法：鄰接矩陣、關(guān)聯(lián)矩陣、鄰接表、逆鄰接表、十字鏈表；圖的遍歷算法：深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法；圖的基本應(yīng)用：最小生成樹、最短路徑，拓?fù)渑判蚝完P(guān)鍵路徑。6靜態(tài)查找表、動態(tài)查找表和哈希表（包括二叉排序樹、AVL樹）重點：靜態(tài)查找表、動態(tài)查找表和哈希表上的查找方法；哈希函數(shù)的基本構(gòu)造方法，解決地址沖突的基本策略；理解各查找算法的時間復(fù)雜度和空間復(fù)雜度。7五類內(nèi)部排序算法的算法思想、時間特性及穩(wěn)定性重點：插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序等五類排序算法的算

4、法思想和時間復(fù)雜度；五類排序算法的特性和適用情形。三、題型及分值單項選擇題：10 %填空題： 10 %簡答題：50 % 算法題：30 %分為閱讀、修改和編寫算法三類：閱讀算法：閱讀指定算法，回答使用的數(shù)據(jù)結(jié)構(gòu)、算法實現(xiàn)的功能或執(zhí)行的結(jié)果；修改算法：閱讀指定算法，指出算法的錯誤并修正；指出算法的不足并改進(jìn)；按給定功能填寫算法空缺部分；編寫算法：根據(jù)算法功能要求和選定的數(shù)據(jù)結(jié)構(gòu)，用程序設(shè)計語言（C和Pascal均可）編寫算法，實現(xiàn)指定功能。計算機(jī)操作系統(tǒng)一、 總體要求認(rèn)識OS的學(xué)術(shù)和工程意義；理解和掌握OS的目標(biāo)、總體結(jié)構(gòu)及主要的設(shè)計思想，以及基本原理和原型實現(xiàn)技術(shù)；了解現(xiàn)代操作系統(tǒng)的一些重要前沿

5、技術(shù)和實現(xiàn)原理；使學(xué)生擁有能夠進(jìn)一步學(xué)習(xí)、應(yīng)用和研發(fā)實際操作系統(tǒng)的知識和工程技術(shù)基礎(chǔ)。二、內(nèi)容及比例第一章 操作系統(tǒng)引論l理解：操作系統(tǒng)的目標(biāo)和作用、理解用戶接口的意義和類型。l了解：傳統(tǒng)操作系統(tǒng)的結(jié)構(gòu)設(shè)計、軟件工程的概念和微內(nèi)核概念。l理解和掌握：操作系統(tǒng)中的基本概念：脫機(jī)輸入輸出技術(shù)、批處理技術(shù)、多道程序設(shè)計、什么是操作系統(tǒng)、操作系統(tǒng)的基本類型，各類型的基本概念和特點、操作系統(tǒng)的特征、理解操作系統(tǒng)的功能模塊。第二章進(jìn)程的描述與控制l理解和掌握的概念有：前趨圖、程序順序執(zhí)行、程序并發(fā)執(zhí)行、進(jìn)程的定義與特征、進(jìn)程的基本狀態(tài)、進(jìn)程的掛起狀態(tài)、進(jìn)程控制塊、進(jìn)程的創(chuàng)建、進(jìn)程的終止、進(jìn)程的阻塞與喚醒、

6、進(jìn)程的掛起與激活。l理解和掌握：臨界資源、臨界區(qū)、利用軟件和硬件解決進(jìn)程互斥問題、整型信號量機(jī)制、記錄型信號量機(jī)制、整型信號量機(jī)制、信號量集機(jī)制、生產(chǎn)者消費者問題、進(jìn)程通信的類型、直接通信和間接通信方式、消息傳遞系統(tǒng)中的幾個問題、消息緩沖隊列通信機(jī)制。l了解：讀者和寫者問題、哲學(xué)家進(jìn)餐問題、管程機(jī)制。l理解：線程的概念、線程間的同步和通信、用戶線程和內(nèi)核支持線程的概念。第三章處理機(jī)調(diào)度與死鎖l理解和掌握：調(diào)度的類型、調(diào)度隊列模型、調(diào)度方式和各種調(diào)度算法、產(chǎn)生死鎖的原因和必要條件、處理死鎖的基本方法、死鎖的預(yù)防和避免、死鎖的檢查和解除。l理解：滿足實時系統(tǒng)要求時，應(yīng)選擇適合實時系統(tǒng)中的調(diào)度算法。

7、l了解：多處理器系統(tǒng)的類型、進(jìn)程的分配方式、進(jìn)程（線程）的調(diào)度方式。第四章存儲器管理l理解和掌握：程序的裝入和鏈接、連續(xù)分配存儲管理方式、對換技術(shù)的應(yīng)用、分頁存儲管理方式、分段存儲管理方式、段頁式存儲管理方式、虛擬存儲器的基本概念、請求分頁存儲管理方式、各種頁面置換算法、請求分段存儲管理方式、請求分頁系統(tǒng)的性能分析、頁式管理的其它置換算法。第五章 設(shè)備管理l理解:I/O系統(tǒng)中設(shè)備控制器基本功能和組成、通道的概念和分類，系統(tǒng)總線的概念。l理解和掌握：I/O控制方式中的循環(huán)測試方式、程序中斷方式、通道I/O方式的概念。l了解：緩沖管理的分類和應(yīng)用。l理解和掌握：設(shè)備分配中的數(shù)據(jù)結(jié)構(gòu)：設(shè)備控制表、控制器表、通道表、系統(tǒng)設(shè)備表的概念。設(shè)備分配時應(yīng)考慮的因素有設(shè)備的固有屬性、分配算法、SPOOLing技術(shù)、設(shè)備分配的獨立性和分配時的安全性。l理解和掌握：磁盤存儲管理的調(diào)度策略：先來先服務(wù)（FIFO）、最短尋找時間優(yōu)先服務(wù)（SSTE）、掃描法（SCAN）和循環(huán)掃描法（CSCAN）。l了解：提高磁盤性能的技術(shù)，例如磁盤高速緩存。第六章文件管理l理解和掌握：文件和文件系統(tǒng)、文件邏輯結(jié)構(gòu)、外存分配方法、目錄管理、文件存儲空間的管理、文件共享與文件保護(hù)。l了解：磁盤容錯技術(shù)和數(shù)據(jù)一