12年電科大計算機專業(yè)基礎(chǔ)大綱_跨考網(wǎng)

　　電子科技大學(xué)計算機專業(yè)基礎(chǔ)大綱

　　本科目包括《數(shù)據(jù)結(jié)構(gòu)》和《計算機操作系統(tǒng)》兩門課程，總分150分，兩門課程各占75分

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

　　一、總體要求

　　 《數(shù)據(jù)結(jié)構(gòu)》是計算機程序設(shè)計的重要理論技術(shù)基礎(chǔ)，是計算機科學(xué)與技術(shù)學(xué)科的核心課程。要求學(xué)生通過數(shù)據(jù)結(jié)構(gòu)課程的學(xué)習(xí)，能夠針對具體的應(yīng)用和算法策略選擇和設(shè)計恰當?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ù)組）的存儲結(jié)構(gòu)、基本運算及應(yīng)用

　　重點：線性表、棧和隊列的存儲結(jié)構(gòu)及其存儲特點；線性表的基本操作在順序存儲及鏈式存儲上的實現(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ì)；滿二叉樹和完全二叉樹的概念及特征；二叉樹、樹及森林的順序存儲及鏈式存儲，以及相互轉(zhuǎn)換算法；線索二叉樹、二叉排序樹的構(gòu)建；各種遍歷算法；哈夫曼樹和哈夫曼編碼的構(gòu)建和應(yīng)用。

　　5．圖的存儲結(jié)構(gòu)、遍歷算法及應(yīng)用

　　重點：圖的基本概念和術(shù)語；圖的基本存儲方法：鄰接矩陣、關(guān)聯(lián)矩陣、鄰接表、逆鄰接表、十字鏈表；圖的遍歷算法：深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法；圖的基本應(yīng)用：最小生成樹、最短路徑，拓撲排序和關(guān)鍵路徑。

　　6．靜態(tài)查找表、動態(tài)查找表和哈希表（包括二叉排序樹、AVL樹）

　　重點：靜態(tài)查找表、動態(tài)查找表和哈希表上的查找方法；哈希函數(shù)的基本構(gòu)造方法，解決地址沖突的基本策略；理解各查找算法的時間復(fù)雜度和空間復(fù)雜度。

　　7．五類內(nèi)部排序算法的算法思想、時間特性及穩(wěn)定性

　　重點：插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序等五類排序算法的算法思想和時間復(fù)雜度；五類排序算法的特性和適用情形。

　　三、題型及分值

　　單項選擇題：10 %

　　填空題： 10 %

　　簡答題：50 %

　　算法題：30 %

　　分為閱讀、修改和編寫算法三類：

　　閱讀算法：閱讀指定算法，回答使用的數(shù)據(jù)結(jié)構(gòu)、算法實現(xiàn)的功能或執(zhí)行的結(jié)果；

　　修改算法：閱讀指定算法，指出算法的錯誤并修正；指出算法的不足并改進；按給定功能填寫算法空缺部分；

　　編寫算法：根據(jù)算法功能要求和選定的數(shù)據(jù)結(jié)構(gòu)，用程序設(shè)計語言（C和Pascal均可）編寫算法，實現(xiàn)指定功能。

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

　　一、 總體要求

　　認識OS的學(xué)術(shù)和工程意義；理解和掌握OS的目標、總體結(jié)構(gòu)及主要的設(shè)計思想，以及基本原理和原型實現(xiàn)技術(shù)；了解現(xiàn)代操作系統(tǒng)的一些重要前沿技術(shù)和實現(xiàn)原理；使學(xué)生擁有能夠進一步學(xué)習(xí)、應(yīng)用和研發(fā)實際操作系統(tǒng)的知識和工程技術(shù)基礎(chǔ)。

　　二、內(nèi)容及比例

　　第一章 操作系統(tǒng)引論

　　l 理解：操作系統(tǒng)的目標和作用、理解用戶接口的意義和類型。

　　l 了解：傳統(tǒng)操作系統(tǒng)的結(jié)構(gòu)設(shè)計、軟件工程的概念和微內(nèi)核概念。

　　l 理解和掌握：操作系統(tǒng)中的基本概念：脫機輸入輸出技術(shù)、批處理技術(shù)、多道程序設(shè)計、什么是操作系統(tǒng)、操作系統(tǒng)的基本類型，各類型的基本概念和特點、操作系統(tǒng)的特征、理解操作系統(tǒng)的功能模塊。

　　第二章進程的描述與控制

　　l 理解和掌握的概念有：前趨圖、程序順序執(zhí)行、程序并發(fā)執(zhí)行、進程的定義與特征、進程的基本狀態(tài)、進程的掛起狀態(tài)、進程控制塊、進程的創(chuàng)建、進程的終止、進程的阻塞與喚醒、進程的掛起與激活。

　　l 理解和掌握：臨界資源、臨界區(qū)、利用軟件和硬件解決進程互斥問題、整型信號量機制、記錄型信號量機制、整型信號量機制、信號量集機制、生產(chǎn)者－消費者問題、進程通信的類型、直接通信和間接通信方式、消息傳遞系統(tǒng)中的幾個問題、消息緩沖隊列通信機制。

　　l 了解：讀者和寫者問題、哲學(xué)家進餐問題、管程機制。

　　l 理解：線程的概念、線程間的同步和通信、用戶線程和內(nèi)核支持線程的概念。

　　第三章處理機調(diào)度與死鎖

　　l 理解和掌握：調(diào)度的類型、調(diào)度隊列模型、調(diào)度方式和各種調(diào)度算法、產(chǎn)生死鎖的原因和必要條件、處理死鎖的基本方法、死鎖的預(yù)防和避免、死鎖的檢查和解除。

　　l 理解：滿足實時系統(tǒng)要求時，應(yīng)選擇適合實時系統(tǒng)中的調(diào)度算法。

　　l 了解：多處理器系統(tǒng)的類型、進程的分配方式、進程（線程）的調(diào)度方式。

　　第四章存儲器管理

　　l 理解和掌握：程序的裝入和鏈接、連續(xù)分配存儲管理方式、對換技術(shù)的應(yīng)用、分頁存儲管理方式、分段存儲管理方式、段頁式存儲管理方式、虛擬存儲器的基本概念、請求分頁存儲管理方式、各種頁面置換算法、請求分段存儲管理方式、請求分頁系統(tǒng)的性能分析、頁式管理的其它置換算法。

　　第五章 設(shè)備管理

　　理解:I/O系統(tǒng)中設(shè)備控制器基本功能和組成、通道的概念和分類，系統(tǒng)總線的概念。

　　理解和掌握：I/O控制方式中的循環(huán)測試方式、程序中斷方式、通道I/O方式的概念。

　　了解：緩沖管理的分類和應(yīng)用。

　　理解和掌握：設(shè)備分配中的數(shù)據(jù)結(jié)構(gòu)：設(shè)備控制表、控制器表、通道表、系統(tǒng)設(shè)備表的概念。設(shè)備分配時應(yīng)考慮的因素有設(shè)備的固有屬性、分配算法、SPOOLing技術(shù)、設(shè)備分配的獨立性和分配時的安全性。

　　理解和掌握：磁盤存儲管理的調(diào)度策略：先來先服務(wù)（FIFO）、最短尋找時間優(yōu)先服務(wù)（SSTE）、掃描法（SCAN）和循環(huán)掃描法（CSCAN）。

　　了解：提高磁盤性能的技術(shù)，例如磁盤高速緩存。

　　第六章文件管理

　　理解和掌握：文件和文件系統(tǒng)、文件邏輯結(jié)構(gòu)、外存分配方法、目錄管理、文件存儲空間的管理、文件共享與文件保護。

　　了解：磁盤容錯技術(shù)和數(shù)據(jù)一致性控制。

　　第七章操作系統(tǒng)接口

　　理解和掌握：聯(lián)機命令接口、系統(tǒng)調(diào)用、圖形用戶接口元素、圖形用戶接口元素的基本操作。

　　了解：對UNIX的SHELL和UNIX的系統(tǒng)調(diào)用作一般了解

　　三、考試題型及分值

　　選擇題：20%

　　填空題：30%

　　簡答題：40%

　　計算題：10%