《數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)》考試大綱
一、考查目標(biāo)
數(shù)據(jù)結(jié)構(gòu)和操作系統(tǒng)是計(jì)算機(jī)類專業(yè)的核心課程?！稊?shù)據(jù)結(jié)構(gòu)和操作系統(tǒng)》科目考察的內(nèi)容包括《數(shù)據(jù)結(jié)構(gòu)》和《操作系統(tǒng)》的基本內(nèi)容，要求考生掌握相關(guān)的概念、方法和技術(shù)，并具備較強(qiáng)的程序設(shè)計(jì)能力，能夠靈活應(yīng)用相關(guān)的方法和技術(shù)解決實(shí)際問(wèn)題。
二、考試形式與試卷結(jié)構(gòu)
（一）試卷成績(jī)及考試時(shí)間
本試卷滿分為150分，考試時(shí)間為180分鐘。
（二）答題方式
答題方式為閉卷、筆試。
（三）試卷內(nèi)容結(jié)構(gòu)
各部分內(nèi)容所占分值為：
數(shù)據(jù)結(jié)構(gòu) 75分
操作系統(tǒng) 75分
（四）試卷題型結(jié)構(gòu)
選擇題，簡(jiǎn)答題，綜合題，程序設(shè)計(jì)題
三、考查范圍
數(shù)據(jù)結(jié)構(gòu)
一、考查目標(biāo)
1、掌握數(shù)據(jù)結(jié)構(gòu)的基本概念、方法和技術(shù)。
2、掌握程序設(shè)計(jì)的基本方法和技巧。
3、能夠應(yīng)用相關(guān)知識(shí)解決一些有實(shí)際背景的問(wèn)題。
二、考查內(nèi)容
1. 數(shù)據(jù)結(jié)構(gòu)概述
數(shù)據(jù)結(jié)構(gòu)的概念；
基本概念與術(shù)語(yǔ)；
算法的概念，算法的特性，以及算法設(shè)計(jì)的要求，算法效率的度量。
2. 線性表
線性表的基本概念和結(jié)構(gòu)特點(diǎn)；
線性表的順序存儲(chǔ)方式以及兩種不同的實(shí)現(xiàn)方法，線性表存儲(chǔ)空間的靜態(tài)分配和動(dòng)態(tài)分配；
線性表的鏈?zhǔn)酱鎯?chǔ)方式的實(shí)現(xiàn)，鏈表與順序表的相似及不同之處，優(yōu)缺點(diǎn)比較，各自適用的場(chǎng)合；
線性表的各種實(shí)現(xiàn)方式下能夠?qū)崿F(xiàn)指定的操作。
3.棧和隊(duì)
棧、隊(duì)列的定義及其相關(guān)數(shù)據(jù)結(jié)構(gòu)的概念，包括：順序棧，鏈棧，共享?xiàng)＃h(huán)隊(duì)列，鏈隊(duì)列等；
棧與隊(duì)列插入刪除操作的特點(diǎn)；棧和遞歸的關(guān)系；棧和隊(duì)列各種實(shí)現(xiàn)方式。
4. 串
串的基本概念，樸素的模式匹配算法。
5.數(shù)組
數(shù)組的定義，數(shù)組的存儲(chǔ)，行序和列序；
特殊矩陣的定義；特殊矩陣的壓縮存儲(chǔ)。
6.樹和二叉樹
二叉樹的概念，二叉樹的五個(gè)性質(zhì)；
二叉樹的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)和二叉鏈表存儲(chǔ)的各自優(yōu)缺點(diǎn)及適用場(chǎng)合；
二叉樹的三種遍歷方法：先序，中序和后序，線索二叉樹，線索化后二叉樹的遍歷方法；
哈夫曼樹概念，哈夫曼樹的構(gòu)造方法，前綴碼概念，哈夫曼編碼。
樹的存儲(chǔ)表示方法，樹與森林轉(zhuǎn)化為二叉樹，樹和森林的遍歷問(wèn)題。
7. 圖
圖的基本概念，圖的定義和特點(diǎn)；
圖的幾種存儲(chǔ)形式，重點(diǎn)是鄰接矩陣和鄰接表；
深度遍歷和廣度遍歷是圖的兩種基本的遍歷算法；
生成樹、最小生成樹的概念以及最小生成樹的構(gòu)造：PRIM算法和KRUSKAL算法；
有向無(wú)環(huán)圖，拓?fù)渑判蚝完P(guān)鍵路徑問(wèn)題；
最短路徑問(wèn)題：DIJSKTRA算法和FLOYD算法。
8. 查找
關(guān)鍵字、主關(guān)鍵字、次關(guān)鍵字的含義；
靜態(tài)查找與動(dòng)態(tài)查找的含義及區(qū)別，平均查找長(zhǎng)度ASL的概念及在各種查找算法中的計(jì)算方法和計(jì)算結(jié)果；
順序表的查找，折半查找，索引順序表；
二叉排序樹，平衡二叉樹，B樹；
哈希表的概念，哈希函數(shù)的設(shè)計(jì)，沖突解決方法的選擇及沖突處理過(guò)程。
9.排序
要求掌握各種排序方法的思想和算法實(shí)現(xiàn)，排序算法穩(wěn)定性的概念，以及各自的特點(diǎn)。
插入排序：直接插入、折半插入、2路插入、希爾排序；
冒泡排序，快速排序；
選擇排序：簡(jiǎn)單選擇、樹選擇、堆排序；
歸并排序；
基數(shù)排序。
操作系統(tǒng)
一、考查目標(biāo)
1、了解操作系統(tǒng)在計(jì)算機(jī)系統(tǒng)中的作用、地位，操作系統(tǒng)的發(fā)展歷史，各類型操作系統(tǒng)的特點(diǎn)。
2、掌握操作系統(tǒng)資源管理的原理、機(jī)制、策略和關(guān)鍵技術(shù)，理解操作系統(tǒng)的運(yùn)行過(guò)程。
3、能夠運(yùn)用所學(xué)的操作系統(tǒng)原理、方法與技術(shù)分析和解決問(wèn)題。
二、考查內(nèi)容
1、操作系統(tǒng)概述
操作系統(tǒng)的概念、特征、功能和提供的服務(wù)；
操作系統(tǒng)的發(fā)展歷史與分類；
操作系統(tǒng)的運(yùn)行環(huán)境
2、用戶界面
作業(yè)的概念及作業(yè)的建立過(guò)程；
命令控制界面接口；
系統(tǒng)調(diào)用
3、處理機(jī)管理
(1)進(jìn)程管理
進(jìn)程與線程，進(jìn)程的狀態(tài)與轉(zhuǎn)換，進(jìn)程控制，進(jìn)程間通信；
進(jìn)程同步與互斥，信號(hào)量機(jī)制與P、V操作，經(jīng)典的同步互斥模型；
死鎖的預(yù)防、避免、檢測(cè)和解除
(2)處理機(jī)調(diào)度
調(diào)度的基本概念，調(diào)度的目標(biāo)，功能與性能衡量；
典型調(diào)度算法：先來(lái)先服務(wù)、短作業(yè)（短進(jìn)程）優(yōu)先、時(shí)間片輪轉(zhuǎn)、基于優(yōu)先級(jí)、最高響應(yīng)比優(yōu)先、多級(jí)反饋輪轉(zhuǎn)等調(diào)度算法。
4、存儲(chǔ)管理
存儲(chǔ)管理的功能：虛擬存儲(chǔ)器、地址變換、內(nèi)存的分配與回收、內(nèi)存信息的共享與保護(hù)；
覆蓋與交換技術(shù)；
分區(qū)存儲(chǔ)管理：基本原理、分區(qū)的分配與回收；
頁(yè)式存儲(chǔ)管理：基本原理和實(shí)現(xiàn)，請(qǐng)求頁(yè)式管理中的頁(yè)面置換算法：先進(jìn)先出置換算法（FIFO）、最近最少使用置換算法（LRU）、最佳置換算法（OPT）、時(shí)鐘置換算法（CLOCK）等；
段式與段頁(yè)式管理：基本原理和實(shí)現(xiàn)；
工作集、局部性原理和抖動(dòng)問(wèn)題
5、文件管理
文件和文件系統(tǒng)的基本概念；
文件邏輯結(jié)構(gòu)與物理結(jié)構(gòu)；
文件存儲(chǔ)管理：文件存儲(chǔ)空間管理，文件目錄管理，文件存取控制，文件系統(tǒng)層次結(jié)構(gòu)；
磁盤組織與管理:磁盤調(diào)度算法
6、設(shè)備管理
設(shè)備管理的目的、設(shè)備管理的功能和任務(wù)；
數(shù)據(jù)傳輸控制方式：程序直接控制、中斷、DMA、通道；
中斷技術(shù)：中斷的概念、中斷的分類、軟中斷、中斷的處理過(guò)程；
緩沖技術(shù)：緩沖的種類、緩沖池的管理；
設(shè)備分配與回收：設(shè)備分配用數(shù)據(jù)結(jié)構(gòu)、分配原則和分配算法；
虛擬設(shè)備，Spooling技術(shù)
