網(wǎng)站介紹 關(guān)于我們 聯(lián)系方式 友情鏈接 廣告業(yè)務(wù) 幫助信息
1998-2022 ChinaKaoyan.com Network Studio. All Rights Reserved. 滬ICP備12018245號(hào)
828《數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)》復(fù)習(xí)大綱
一、考試的基本要求
要求考生比較系統(tǒng)地理解數(shù)據(jù)結(jié)構(gòu)的基本概念和基本知識(shí),從數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的操作三個(gè)方面掌握線性表、樹、圖等常用的數(shù)據(jù)結(jié)構(gòu)。掌握在各種常用數(shù)據(jù)結(jié)構(gòu)上實(shí)現(xiàn)高效的查找和排序算法,并對(duì)算法的時(shí)間和空間復(fù)雜性有一定的分析能力。針對(duì)簡(jiǎn)單的應(yīng)用問題,能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)有效的算法。
另一方面,要求考生比較系統(tǒng)地掌握操作系統(tǒng)各要素的基本概念、基本原理和方法,對(duì)操作系統(tǒng)如何管理和控制計(jì)算機(jī)系統(tǒng)的所有硬件和軟件資源以達(dá)到方便用戶、提高資源的使用效率有較深入的了解。
要求考生具有較強(qiáng)的抽象思維能力、邏輯推理能力、軟件設(shè)計(jì)和實(shí)現(xiàn)能力以及綜合運(yùn)用所學(xué)的知識(shí)分析問題和解決問題的能力。
二、考試方式和考試時(shí)間
閉卷考試,總分150(數(shù)據(jù)結(jié)構(gòu)90+操作系統(tǒng)60),考試時(shí)間為3小時(shí)。
三、參考書目(僅供參考)
《數(shù)據(jù)結(jié)構(gòu)與算法》(第四版),廖明宏,郭福順,張巖,李秀坤,高等教育出版社,2007年
《計(jì)算機(jī)操作系統(tǒng)》(第三版),湯小丹,梁紅兵,哲鳳屏,湯子瀛,西安電子科技大學(xué)出版社,2007年
四、試題類型:
主要包括選擇題 、編程題、計(jì)算題、綜合題等類型,并根據(jù)每年的考試要求做相應(yīng)調(diào)整。
五、考試內(nèi)容及要求
第一部分 數(shù)據(jù)結(jié)構(gòu)-線性表
掌握:線性表的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及描述方式;順序表的定義、插入、刪除;單鏈表、雙向鏈表和循環(huán)鏈表的定義、插入、刪除;順序棧、鏈棧的表示、入棧和出棧操作;順序隊(duì)列、鏈隊(duì)列的表示、入隊(duì)和出隊(duì)操作;循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿的判斷;串的定義、邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu),串的KMP模式匹配方法;廣義表的定義;矩陣的壓縮存儲(chǔ)的概念以及有關(guān)計(jì)算方法;稀疏矩陣的三元組表示方法;
熟悉:線性結(jié)構(gòu)的定義和特點(diǎn);順序表和單鏈表的組織方法、特點(diǎn)、算法和性能分析;單鏈表、雙向鏈表和循環(huán)鏈表之間的區(qū)別;棧和隊(duì)的特點(diǎn);棧和隊(duì)列的定義;順序棧和鏈棧上基本運(yùn)算的實(shí)現(xiàn)和簡(jiǎn)單算法設(shè)計(jì);鏈隊(duì)上基本運(yùn)算的實(shí)現(xiàn)和簡(jiǎn)單算法設(shè)計(jì);串的基本運(yùn)算,串的傳統(tǒng)匹配方法;多維數(shù)組的定義以及邏輯結(jié)構(gòu);廣義表的鏈表表示和算法;特殊矩陣的非零元下標(biāo)與數(shù)組下標(biāo)的對(duì)應(yīng)關(guān)系。
第二部分 數(shù)據(jù)結(jié)構(gòu)-樹
掌握:樹的邏輯結(jié)構(gòu);二叉樹的定義以及性質(zhì);二叉樹的不同表示方法;二叉樹的構(gòu)建方法;二叉樹的三種遍歷算法;線索二叉樹的定義及構(gòu)造方法;樹的存儲(chǔ)結(jié)構(gòu);哈夫曼樹的構(gòu)建及其應(yīng)用,哈夫曼編碼;表達(dá)式樹的構(gòu)建及其應(yīng)用;集合樹的表示以及集合等價(jià)分類算法;
熟悉:樹的常用術(shù)語和含義;二叉樹性質(zhì)的證明;利用二叉樹的遍歷設(shè)計(jì)有關(guān)算法解決簡(jiǎn)單應(yīng)用問題;線索二叉樹的插入、刪除結(jié)點(diǎn)算法,利用線索二叉樹確定結(jié)點(diǎn)的前驅(qū)和后繼結(jié)點(diǎn);森林與二叉樹的轉(zhuǎn)換;利用表達(dá)式樹求表達(dá)式的值。
第三部分 數(shù)據(jù)結(jié)構(gòu)-圖
掌握:圖的邏輯結(jié)構(gòu)特征;圖的兩種表示方法;圖的深度優(yōu)先搜索的算法及實(shí)現(xiàn);最小生成樹的概念,用Prim算法和Kruskal算法構(gòu)造連通圖的最小生成樹的方法和復(fù)雜度;對(duì)給定的有向圖,給出其中一個(gè)拓?fù)渑判?AOE網(wǎng)的基本原理和實(shí)現(xiàn)方法;單源最短路徑Dijkstra算法的基本思想和性能分析;
熟悉:圖的定義和術(shù)語;圖的廣度優(yōu)先搜索的算法及實(shí)現(xiàn);圖的遍歷和樹的遍歷之間的關(guān)系;生成樹概念,用兩種方法構(gòu)建最小生成樹的實(shí)現(xiàn);拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn);單源最短路徑的實(shí)現(xiàn)方法;Floyd算法的基本思想和性能分析;Warshall的算法實(shí)質(zhì);利用Floyd算法求有向圖的中心點(diǎn)。
第四部分 數(shù)據(jù)結(jié)構(gòu)-查找和排序
掌握:二分查找的基本條件和方法;分塊查找的基本思想和性能分析;二分查找和分塊查找的實(shí)現(xiàn)方法;二叉查找樹和平衡二叉樹的構(gòu)建、插入結(jié)點(diǎn)和刪除結(jié)點(diǎn)的方法;哈希表技術(shù)的相關(guān)概念、哈希函數(shù)的構(gòu)造方法和原則以及產(chǎn)生沖突的原因;插入排序、選擇排序、冒泡排序、快速排序、堆排序、歸并排序、基數(shù)排序基本原理和性能分析;快速排序、歸并排序的算法實(shí)現(xiàn);
熟悉:順序查找、二分查找和分塊查找、二叉排序樹和平衡二叉樹、哈希查找的概念、性質(zhì)及性能;順序查找、二叉排序樹的實(shí)現(xiàn)方法;哈希函數(shù)的構(gòu)造方法和處理沖突的方法;插入排序、希爾排序、快速排序、簡(jiǎn)單選擇排序、堆排序、歸并排序和基數(shù)排序的基本思想;希爾排序、基數(shù)排序的實(shí)現(xiàn)方法;排序算法的穩(wěn)定性分析。
第五部分 操作系統(tǒng)-進(jìn)程管理
掌握:進(jìn)程的基本概念;進(jìn)程的特征與狀態(tài);進(jìn)程的創(chuàng)建、終止、堵塞與喚醒、掛起與激活;進(jìn)程的同步;幾個(gè)經(jīng)典的進(jìn)程同步問題;消息緩沖隊(duì)列通信機(jī)制;線程的同步與通信;
熟悉:程序順序執(zhí)行及其特征;程序并發(fā)執(zhí)行及其特征;進(jìn)程控制塊;進(jìn)程通信類型;消息傳遞通信的實(shí)現(xiàn)方法。
第六部分 操作系統(tǒng)-處理機(jī)調(diào)度與死鎖
掌握:調(diào)度隊(duì)列模型以及選擇調(diào)度算法的若干準(zhǔn)則;高優(yōu)先權(quán)優(yōu)先調(diào)度算法、時(shí)間片輪轉(zhuǎn)調(diào)度算法、最高響應(yīng)比調(diào)度算法;利用銀行家算法避免死鎖;死鎖的檢測(cè)與解除;
熟悉:處理機(jī)調(diào)度的基本概念;先來先服務(wù)調(diào)度算法、短作業(yè)優(yōu)先調(diào)度算法;產(chǎn)生死鎖的原因和必要條件;系統(tǒng)安全狀態(tài)。
第七部分 操作系統(tǒng)-存儲(chǔ)器管理
掌握:程序的裝入和連接;頁面與頁表;地址變換機(jī)構(gòu);兩級(jí)和多級(jí)頁表;段頁式存儲(chǔ)管理方式;虛擬存儲(chǔ)器的特征;請(qǐng)求分頁存儲(chǔ)管理中的內(nèi)存分配策略、分配算法和調(diào)頁策略;最佳置換算法和FIFO算法LRU置換算法;Clock置換算法;
熟悉:存儲(chǔ)器的層次結(jié)構(gòu);連續(xù)分配方式:固定分區(qū)、動(dòng)態(tài)分區(qū)、可重定位分區(qū)、對(duì)換;反向頁表;分段存儲(chǔ)的基本原理;信息共享;虛擬存儲(chǔ)器的實(shí)現(xiàn)方法;請(qǐng)求分頁中的硬件支持;請(qǐng)求分段中的硬件支持;分段的共享與保護(hù)。
第八部分 操作系統(tǒng)-設(shè)備管理
掌握: 程序I/O方式;中斷驅(qū)動(dòng)I/O控制方法;DMA I/O控制方法;循環(huán)緩沖、緩沖池;中斷驅(qū)動(dòng)程序;設(shè)備驅(qū)動(dòng)程序;獨(dú)立型設(shè)備的分配與去配;共享型設(shè)備的分配與去配;磁盤高速緩存;提高磁盤I/O速度的其它方法;
熟悉:I/O設(shè)備;總線系統(tǒng); I/O通道控制方法;I/O軟件的設(shè)計(jì)目標(biāo)與原則;設(shè)備獨(dú)立性軟件;用戶層軟件;設(shè)備分配的相關(guān)數(shù)據(jù)結(jié)構(gòu);磁盤調(diào)度;廉價(jià)磁盤冗陣列。
第九部分 操作系統(tǒng)-文件管理與接口命令
掌握:索引文件、索引順序文件、直接文件和哈希文件;連續(xù)分配、鏈接分派、索引分配;文件存儲(chǔ)的空閑表法、空閑鏈表發(fā)、位示圖法、成組鏈接法;基于索引結(jié)點(diǎn)的共享方式、利用符號(hào)鏈實(shí)現(xiàn)文件共享;數(shù)據(jù)一致性控制;Shell命令語言;
熟悉: 文件、記錄和數(shù)據(jù)項(xiàng)的基本概念;文件類型和文件系統(tǒng)模型;文件的基本操作;文件邏輯結(jié)構(gòu)的類型;順序文件;文件控制塊與索引結(jié)點(diǎn)、目錄結(jié)構(gòu)、目錄查詢技術(shù);重復(fù)數(shù)據(jù)的數(shù)據(jù)一致性問題;聯(lián)機(jī)用戶接口、聯(lián)機(jī)命令類型、鍵盤終端處理程序;系統(tǒng)調(diào)用概念及基本類型;圖像界面接口。
來源未注明“中國考研網(wǎng)”的資訊、文章等均為轉(zhuǎn)載,本網(wǎng)站轉(zhuǎn)載出于傳遞更多信息之目的,并不意味著贊同其觀點(diǎn)或證實(shí)其內(nèi)容的真實(shí)性,如涉及版權(quán)問題,請(qǐng)聯(lián)系本站管理員予以更改或刪除。如其他媒體、網(wǎng)站或個(gè)人從本網(wǎng)站下載使用,必須保留本網(wǎng)站注明的"稿件來源",并自負(fù)版權(quán)等法律責(zé)任。
來源注明“中國考研網(wǎng)”的文章,若需轉(zhuǎn)載請(qǐng)聯(lián)系管理員獲得相應(yīng)許可。
聯(lián)系方式:chinakaoyankefu@163.com
掃碼關(guān)注
了解考研最新消息
網(wǎng)站介紹 關(guān)于我們 聯(lián)系方式 友情鏈接 廣告業(yè)務(wù) 幫助信息
1998-2022 ChinaKaoyan.com Network Studio. All Rights Reserved. 滬ICP備12018245號(hào)