本科目包括《數(shù)據(jù)結(jié)構(gòu)》和《計(jì)算機(jī)操作系統(tǒng)》兩門課程，總分150分，兩門課程各占75分

《數(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)行問題求解，具備采用C 或C++或JAVA 語言設(shè)計(jì)與實(shí)現(xiàn)算法的能力。

二、內(nèi)容

1. 數(shù)據(jù)結(jié)構(gòu)及算法的相關(guān)概念和術(shù)語

（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） 遞歸過程的特點(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．樹和二叉樹

（1） 樹與森林的基本概念

（2） 樹與森林的存儲(chǔ)結(jié)構(gòu)及遍歷

（3） 二叉樹的定義及6大性質(zhì)

（4） 二叉樹的順序儲(chǔ)存與鏈?zhǔn)絻?chǔ)存結(jié)構(gòu)

（5） 二叉樹的先序、中序、后序三種遍歷方式的關(guān)系以及實(shí)現(xiàn)；層序遍歷的實(shí)現(xiàn)

（6） 線索二叉樹的基本概念與構(gòu)造方法

（7） 樹與二叉樹的應(yīng)用：二叉排序樹；二叉平衡樹；哈夫曼樹與哈夫曼編碼

5．圖

（1） 圖的基本概念和術(shù)語

（2） 圖的存儲(chǔ)結(jié)構(gòu)：鄰接矩陣、鄰接表、逆鄰接表

（3） 遍歷算法：深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法

（4） 應(yīng)用：最小生成樹；最短路徑，拓?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)閱讀算法：閱讀指定算法，回答使用的數(shù)據(jù)結(jié)構(gòu)、算法實(shí)現(xiàn)的功能或執(zhí)行的結(jié)果；

(2)修改算法：閱讀指定算法，指出算法的錯(cuò)誤并修正；指出算法的不足并改進(jìn)；按給定功能填寫算法空缺部分；

(3)編寫算法：根據(jù)算法功能要求，選擇或者設(shè)計(jì)合適的數(shù)據(jù)結(jié)構(gòu)，用程序設(shè)計(jì)語言編寫算法，實(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ù)分析問題和解決問題的能力。

二、內(nèi)容

1. 操作系統(tǒng)的基本概念

1) 批處理與多道程序設(shè)計(jì)

2) 分時(shí)系統(tǒng)與實(shí)時(shí)系統(tǒng)

3) 操作系統(tǒng)的基本類型與特征

4) 并發(fā)與并行的概念

5) 操作系統(tǒng)的層次結(jié)構(gòu)與功能模塊

6) 程序的并發(fā)執(zhí)行與順序執(zhí)行

2. 進(jìn)程管理

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)程同步與互斥問題、信號(hào)量機(jī)制以及P、V操作、管程機(jī)制

3) 進(jìn)程間通信：進(jìn)程通信的類型（直接通信和間接通信方式）、消息傳遞系統(tǒng)中的幾個(gè)問題、消息緩沖隊(duì)列通信機(jī)制

4) 線程與進(jìn)程的調(diào)度:線程與進(jìn)程的基本概念，調(diào)度的類型、調(diào)度隊(duì)列模型、調(diào)度方式、進(jìn)程調(diào)度算法（先來先服務(wù)、短進(jìn)程優(yōu)先、時(shí)間片輪轉(zhuǎn)、基于優(yōu)先級(jí)的調(diào)度算法等）

5) 死鎖:死鎖的基本概念，死鎖定理、死鎖預(yù)防、死鎖避免與處理死鎖的基本方法、銀行家

算法

6) 綜合應(yīng)用：生產(chǎn)者消費(fèi)者問題、讀者和寫者問題、哲學(xué)家進(jì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) 段式管理與頁式管理：段、頁、碎片等基本概念、段式管理與頁式管理機(jī)制

5) 虛擬內(nèi)存：局部性原理、虛擬內(nèi)存概念、請(qǐng)求分段與請(qǐng)求分頁、段頁式管理、段頁式地址結(jié)構(gòu)與地址轉(zhuǎn)換、頁面置換算法（OPT、先進(jìn)先出、LRU、Clock、改進(jìn)型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) 磁盤管理與磁盤調(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文件）、文件共享（基于索引節(jié)點(diǎn)、基于符號(hào)鏈接實(shí)現(xiàn)文件共享）

2) 外存分配方法：連續(xù)分配、鏈接分配、索引分配

3) 目錄管理：?jiǎn)渭?jí)目錄、二級(jí)目錄、多級(jí)目錄

4) 文件存儲(chǔ)空間的管理技術(shù)：位示圖、空閑鏈表、索引