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

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

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

　　《數(shù)據(jù)結構》

　　一、總體要求

　　 《數(shù)據(jù)結構》是計算機程序設計的重要理論技術基礎，是計算機科學與技術學科的核心課程。要求學生通過數(shù)據(jù)結構課程的學習，能夠針對具體的應用和算法策略選擇和設計恰當?shù)臄?shù)據(jù)結構，并能編程實現(xiàn)。

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

　　《數(shù)據(jù)結構》部分主要考試內(nèi)容（帶下劃線文字表示重點部分）：

　　1. 數(shù)據(jù)結構及算法的相關概念和術語

　　重點：數(shù)據(jù)結構及算法的概念；數(shù)據(jù)的邏輯結構和存儲結構；算法的定義及特性；算法時間復雜度和空間復雜度的分析方法。

　　2．線性表（包括棧、隊列和數(shù)組）的存儲結構、基本運算及應用

　　重點：線性表、棧和隊列的存儲結構及其存儲特點；線性表的基本操作在順序存儲及鏈式存儲上的實現(xiàn)；各種變形鏈表（循環(huán)鏈表、雙向鏈表、帶頭結點的鏈表等）的表示和基本操作的實現(xiàn)；遞歸過程的特點及實現(xiàn)方法；循環(huán)隊列的判滿、判空方法；稀疏矩陣的存儲方法（三元組、十字鏈表）和基本運算的實現(xiàn)（轉(zhuǎn)置、矩陣加法等）。

　　3．廣義表的存儲結構、基本運算及應用

　　重點：廣義表的基本概念、基本操作及存儲結構。

　　4．樹和二叉樹的存儲結構、遍歷算法及應用

　　重點：二叉樹和樹的遞歸定義、基本術語、基本性質(zhì)；滿二叉樹和完全二叉樹的概念及特征；二叉樹、樹及森林的順序存儲及鏈式存儲，以及相互轉(zhuǎn)換算法；線索二叉樹、二叉排序樹的構建；各種遍歷算法；哈夫曼樹和哈夫曼編碼的構建和應用。

　　5．圖的存儲結構、遍歷算法及應用

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

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

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

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

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

　　三、題型及分值

　　單項選擇題：10 %

　　填空題： 10 %

　　簡答題：50 %

　　算法題：30 %

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

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

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

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

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

　　一、 總體要求

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

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

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

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

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

　　l 理解和掌握：操作系統(tǒng)中的基本概念：脫機輸入輸出技術、批處理技術、多道程序設計、什么是操作系統(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 了解：讀者和寫者問題、哲學家進餐問題、管程機制。

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

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

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

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

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

　　第四章存儲器管理

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

　　第五章 設備管理

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

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

　　了解：緩沖管理的分類和應用。

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

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

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

　　第六章文件管理

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

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

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

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

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

　　三、考試題型及分值

　　選擇題：20%

　　填空題：30%

　　簡答題：40%

　　計算題：10%