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

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

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

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

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

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

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

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