電子科技大學(xué)計(jì)算機(jī)考研820專業(yè)課考點(diǎn).docx

考試科目820計(jì)算機(jī)專業(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é)科的核心課程。要求：1.理解數(shù)據(jù)結(jié)構(gòu)的基本概念；掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其差異，以及各種基本操作的實(shí)現(xiàn)。2.掌握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠分析算法的時(shí)間復(fù)雜度與空間復(fù)雜度。 3.能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和算法策略進(jìn)行問(wèn)題求解，具備采用C或C+或JAVA語(yǔ)言設(shè)計(jì)與實(shí)現(xiàn)算法的能力。二、內(nèi)容1. 數(shù)據(jù)結(jié)構(gòu)及算法的相關(guān)概念和術(shù)語(yǔ)（1）數(shù)據(jù)結(jié)構(gòu)及算法的概念；（2）數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)；（3）算法的定義及特性；（4）算法時(shí)間復(fù)雜度和空間復(fù)雜度的分析方法。2線性表（1）線性表的定義（2）線性表的基本操作及在順序存儲(chǔ)及鏈?zhǔn)酱鎯?chǔ)上的實(shí)現(xiàn)；（3）各種變形鏈表（循環(huán)鏈表、雙向鏈表、帶頭結(jié)點(diǎn)的鏈表等）的表示和基本操作的實(shí)現(xiàn)；（4）遞歸過(guò)程的特點(diǎn)及實(shí)現(xiàn)方法；（5）棧和隊(duì)列的基本概念；棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)絻?chǔ)存結(jié)構(gòu)及其存儲(chǔ)特點(diǎn)；（6）棧和隊(duì)列的應(yīng)用（7）循環(huán)隊(duì)列的判滿、判空方法；（8）特殊矩陣的壓縮儲(chǔ)存； 3廣義表的基本概念、存儲(chǔ)結(jié)構(gòu)和基本操作4樹(shù)和二叉樹(shù)（1）樹(shù)與森林的基本概念（2）樹(shù)與森林的存儲(chǔ)結(jié)構(gòu)及遍歷（3）二叉樹(shù)的定義及6大性質(zhì)（4）二叉樹(shù)的順序儲(chǔ)存與鏈?zhǔn)絻?chǔ)存結(jié)構(gòu)（5）二叉樹(shù)的先序、中序、后序三種遍歷方式的關(guān)系以及實(shí)現(xiàn)；層序遍歷的實(shí)現(xiàn)（6）線索二叉樹(shù)的基本概念與構(gòu)造方法（7）樹(shù)與二叉樹(shù)的應(yīng)用：二叉排序樹(shù)；二叉平衡樹(shù)；哈夫曼樹(shù)與哈夫曼編碼5圖（1）圖的基本概念和術(shù)語(yǔ)；（2）圖的存儲(chǔ)結(jié)構(gòu)：鄰接矩陣、鄰接表、逆鄰接表；（3）遍歷算法：深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法；（4）應(yīng)用：最小生成樹(shù)；最短路徑，拓?fù)渑判蚝完P(guān)鍵路徑。6查找（1）查找的基本概念；靜態(tài)查找與動(dòng)態(tài)查找；（2）順序查找、折半查找、索引查找（3）哈希查找哈希函數(shù)的基本構(gòu)造方法，解決地址沖突的基本策略；（4）各種查找算法的時(shí)間復(fù)雜度和空間復(fù)雜度。7排序（1）排序的基本概念（2）插入排序（3）簡(jiǎn)單選擇排序（4）希爾排序（5）快速排序（6）堆排序（7）歸并排序（8）基數(shù)排序（9）排序算法的比較。三、題型及分值比例1. 填空題（10分）2. 單選題（20分）3. 簡(jiǎn)答題（30分）4. 算法題（15分）其中算法題分為閱讀、修改和編寫(xiě)算法三類(lèi)：(1)閱讀算法：閱讀指定算法，回答使用的數(shù)據(jù)結(jié)構(gòu)、算法實(shí)現(xiàn)的功能或執(zhí)行的結(jié)果；(2)修改算法：閱讀指定算法，指出算法的錯(cuò)誤并修正；指出算法的不足并改進(jìn)；按給定功能填寫(xiě)算法空缺部分；(3)編寫(xiě)算法：根據(jù)算法功能要求，選擇或者設(shè)計(jì)合適的數(shù)據(jù)結(jié)構(gòu)，用程序設(shè)計(jì)語(yǔ)言編寫(xiě)算法，實(shí)現(xiàn)指定功能。以上皆可分析給定或者設(shè)計(jì)的算法時(shí)空復(fù)雜度。操作系統(tǒng)部分一、總體要求主要考察學(xué)生對(duì)操作系統(tǒng)基本概念、原理的理解程度，重點(diǎn)考察操作系統(tǒng)的設(shè)計(jì)方法與實(shí)現(xiàn)技術(shù)，同時(shí)能夠具備運(yùn)用所學(xué)的操作系統(tǒng)原理、方法與技術(shù)分析問(wèn)題和解決問(wèn)題的能力。二、內(nèi)容及比例1. 操作系統(tǒng)的基本概念 1) 批處理與多道程序設(shè)計(jì)2) 分時(shí)系統(tǒng)與實(shí)時(shí)系統(tǒng)3) 操作系統(tǒng)的基本類(lèi)型與特征4) 并發(fā)與并行的概念5) 操作系統(tǒng)的層次結(jié)構(gòu)與功能模塊6) 程序的并發(fā)執(zhí)行與順序執(zhí)行2. 處理機(jī)管理 1) 進(jìn)程: 進(jìn)程控制塊、進(jìn)程的幾種基本狀態(tài)與狀態(tài)轉(zhuǎn)換（進(jìn)程的創(chuàng)建、進(jìn)程的終止、進(jìn)程的阻塞與喚醒、進(jìn)程的掛起與激活等）2) 進(jìn)程的同步與互斥：臨界資源、臨界區(qū)、進(jìn)程同步與互斥問(wèn)題、信號(hào)量機(jī)制以及P、V操作、管程機(jī)制。3) 進(jìn)程間通信：進(jìn)程通信的類(lèi)型（直接通信和間接通信方式）、消息傳遞系統(tǒng)中的幾個(gè)問(wèn)題、消息緩沖隊(duì)列通信機(jī)制。4) 線程與進(jìn)程的調(diào)度:線程與進(jìn)程的基本概念，調(diào)度的類(lèi)型、調(diào)度隊(duì)列模型、調(diào)度方式、進(jìn)程調(diào)度算法（先來(lái)先服務(wù)、短進(jìn)程優(yōu)先、時(shí)間片輪轉(zhuǎn)、基于優(yōu)先級(jí)的調(diào)度算法等）。5) 死鎖:死鎖的基本概念，死鎖定理、死鎖預(yù)防、死鎖避免與處理死鎖的基本方法、銀行家算法。6) 綜合應(yīng)用：生產(chǎn)者消費(fèi)者問(wèn)題、讀者和寫(xiě)者問(wèn)題、哲學(xué)家進(jìn)餐問(wèn)題等。3. 內(nèi)存管理1) 內(nèi)存管理的需求：重定位、內(nèi)存保護(hù)、內(nèi)存共享2) 程序的裝入和鏈接：靜態(tài)裝入和可重定位裝入、靜態(tài)鏈接、動(dòng)態(tài)鏈接、運(yùn)行時(shí)動(dòng)態(tài)鏈接。3) 分區(qū)存儲(chǔ)管理：分區(qū)方式（單一連續(xù)分區(qū)、固定分區(qū)、可變式分區(qū)）、分區(qū)分配算法（首次適應(yīng)算法、循環(huán)首次適應(yīng)算法、最佳適應(yīng)法、最壞適應(yīng)法等）。4) 段式管理與頁(yè)式管理：段、頁(yè)、碎片等基本概念、段式管理與頁(yè)式管理機(jī)制5) 虛擬內(nèi)存：局部性原理、虛擬內(nèi)存概念、請(qǐng)求分段與請(qǐng)求分頁(yè)、段頁(yè)式管理、段頁(yè)式地址結(jié)構(gòu)與地址轉(zhuǎn)換、頁(yè)面置換算法（先進(jìn)先出、LRU、Clock置換）、抖動(dòng)4. 設(shè)備管理1) I/O系統(tǒng)的：基本概念、I/O控制方式（程序I/0、中斷、DMA、通道）、相關(guān)數(shù)據(jù)結(jié)構(gòu)、緩沖管理（單緩沖、雙緩沖、循環(huán)緩沖、緩沖池）2) 磁盤(pán)管理與磁盤(pán)調(diào)度算法：SSTF算法，SCAN算法，CSCAN算法，N-STEP-SCAN算法，F(xiàn)SCAN算法3) 設(shè)備分配、設(shè)備處理、虛擬設(shè)備，Spooling系統(tǒng)5. 文件系統(tǒng)1) 基本概念：文件和文件系統(tǒng)、目錄、文件結(jié)構(gòu)的物理結(jié)構(gòu)和邏輯結(jié)構(gòu)（順序文件、索引順序文件、索引文件、HASH文件）