數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)

1、數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)考試大綱一、考查目標(biāo)數(shù)據(jù)結(jié)構(gòu)和操作系統(tǒng)是計算機類專業(yè)的核心課程。數(shù)據(jù)結(jié)構(gòu)和操作系統(tǒng)科目考察的內(nèi)容包括數(shù)據(jù)結(jié)構(gòu)和操作系統(tǒng)的基本內(nèi)容，要求考生掌握相關(guān)的概念、方法和技術(shù)，并具備較強的程序設(shè)計能力，能夠靈活應(yīng)用相關(guān)的方法和技術(shù)解決實際問題。二、考試形式與試卷結(jié)構(gòu)（一）試卷成績及考試時間本試卷滿分為150分，考試時間為180分鐘。（二）答題方式答題方式為閉卷、筆試。（三）試卷內(nèi)容結(jié)構(gòu)各部分內(nèi)容所占分值為： 數(shù)據(jù)結(jié)構(gòu) 75分 操作系統(tǒng) 75分（四）試卷題型結(jié)構(gòu)1數(shù)據(jù)結(jié)構(gòu)選擇題：15小題，每小題2分，共30分簡答題：3小題，每小題10分，共30分算法題：1小題，每小題 15分，共15分2

2、.操作系統(tǒng)三、考查范圍數(shù)據(jù)結(jié)構(gòu)一、考查目標(biāo)1、掌握數(shù)據(jù)結(jié)構(gòu)的基本概念、方法和技術(shù)。2、掌握程序設(shè)計的基本方法和技巧。3、能夠應(yīng)用相關(guān)知識解決一些有實際背景的問題。二、考查內(nèi)容1. 緒論 數(shù)據(jù)結(jié)構(gòu)的概念；基本概念與術(shù)語；算法的概念，算法的特性，以及算法設(shè)計的要求，算法效率的度量。2. 線性表線性表相關(guān)的基本概念和結(jié)構(gòu)特點；線性表的順序存儲方式以及兩種不同的實現(xiàn)方法：表空間的靜態(tài)分配和動態(tài)分配；線性表的鏈?zhǔn)酱鎯Ψ绞降膶崿F(xiàn)；鏈表與順序表的相似及不同之處，優(yōu)缺點比較，各自適用的場合；線性表的各種實現(xiàn)方式能夠?qū)崿F(xiàn)指定的操作。3.棧和隊 棧、隊列的定義及其相關(guān)數(shù)據(jù)結(jié)構(gòu)的概念，包括：順序棧，鏈棧，共享棧，循

3、環(huán)隊列，鏈隊列等；棧與隊列插入刪除操作的特點；棧和遞歸的關(guān)系；棧和隊列各種實現(xiàn)方式。4. 串 串的基本概念，樸素的模式匹配算法。5.數(shù)組數(shù)組的定義；數(shù)組的存儲，行序和列序；特殊矩陣的定義；特殊矩陣的壓縮存儲。6.樹和二叉樹 二叉樹的概念；二叉樹的五個性質(zhì)；二叉樹的存儲結(jié)構(gòu)：順序存儲和二叉鏈表存儲的各自優(yōu)缺點及適用場合；二叉樹的三種遍歷方法：先序，中序和后序；線索二叉樹，線索化后二叉樹的遍歷方法；哈夫曼樹概念，哈夫曼樹的構(gòu)造方法，前綴碼概念，哈夫曼編碼。樹的存儲表示方法，樹與森林轉(zhuǎn)化為二叉樹，樹和森林的遍歷問題。7. 圖圖的基本概念，圖的定義和特點；圖的幾種存儲形式，重點是鄰接矩陣和鄰接表；深度

4、遍歷和廣度遍歷是圖的兩種基本的遍歷算法；生成樹、最小生成樹的概念以及最小生成樹的構(gòu)造：PRIM算法和KRUSKAL算法；有向無環(huán)圖，拓撲排序和關(guān)鍵路徑問題；最短路徑問題：DIJSKTRA算法和FLOYD算法。8. 查找 關(guān)鍵字、主關(guān)鍵字、次關(guān)鍵字的含義；靜態(tài)查找與動態(tài)查找的含義及區(qū)別；平均查找長度ASL的概念及在各種查找算法中的計算方法和計算結(jié)果；順序表的查找，折半查找，索引順序表；二叉排序樹，平衡二叉樹，B樹；哈希表的概念，哈希函數(shù)的設(shè)計，沖突解決方法的選擇及沖突處理過程。9. 內(nèi)排序要求掌握各種排序方法的思想和算法實現(xiàn)，排序算法穩(wěn)定性的概念，以及各自的特點。插入排序：直接插入、折半插入、2

5、路插入、希爾排序；冒泡排序，快速排序；選擇排序：簡單選擇、樹選擇、堆排序；歸并排序；基數(shù)排序。 操作系統(tǒng)一、考查目標(biāo)1、了解操作系統(tǒng)在計算機系統(tǒng)中的作用、地位、發(fā)展和特點。2、了解操作系統(tǒng)的基本概念、原理，掌握操作系統(tǒng)實現(xiàn)技術(shù)。3、能夠運用所學(xué)的操作系統(tǒng)原理、方法與技術(shù)分析和解決問題。二、考查內(nèi)容1.操作系統(tǒng)概述操作系統(tǒng)的概念、特征、功能和提供的服務(wù)；操作系統(tǒng)的發(fā)展與分類。2用戶界面作業(yè)的概念及作業(yè)的建立過程、SPOOLING系統(tǒng)；命令控制界面接口3CPU管理（1）.進程與線程，進程的概念，進程的狀態(tài)與轉(zhuǎn)換，進程控制，進程互斥與同步和經(jīng)典問題，死鎖的概念，處理策略，死鎖的預(yù)防，死鎖的避免（2）

6、.處理機調(diào)度調(diào)度的基本概念，調(diào)度的目標(biāo)、功能與性能衡量指標(biāo)，典型調(diào)度算法：先來先服務(wù)、短作業(yè)（短進程）優(yōu)先、時間片輪轉(zhuǎn)、優(yōu)先級、最高響應(yīng)比優(yōu)先、多級反饋輪轉(zhuǎn)調(diào)度。4、存儲管理存儲管理的功能：虛擬存儲器、地址變換、內(nèi)外存數(shù)據(jù)傳輸?shù)目刂?、?nèi)存的分配與回收、內(nèi)存信息的共享與保護；分區(qū)存儲管理，覆蓋與交換技術(shù)，請求頁式管理，請求頁式管理中的置換算法：先進先出置換算法（FIFO）、最近最少置換算法（LRU）、最佳置換算法（OPT）、時鐘置換算法（CLOCK），段式與段頁式管理， 局部性原理和抖動問題5、文件管理文件系統(tǒng)的概念、功能，常用的文件的邏輯結(jié)構(gòu)與存取方法，文件的物理結(jié)構(gòu)與存取設(shè)備：連續(xù)文件、串聯(lián)文件、索引文件，磁盤組織與管理:磁盤調(diào)度算法，文件存儲空間管理：空閑文件目錄、空閑塊鏈、位示圖，單級目錄、兩級級目錄、多級目錄，文件存取控制，文件系統(tǒng)的層次模型6、設(shè)備管理設(shè)備管理的目的、設(shè)備管理的功能和任務(wù)，數(shù)據(jù)傳輸控制方式：DMA技術(shù)、