科目代碼:842
科目名稱:數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)
本門課程由數(shù)據(jù)結(jié)構(gòu)和操作系統(tǒng)兩門課程組成,兩門課程各占75分,具體要求如下:
第一部分:數(shù)據(jù)結(jié)構(gòu)
一、考試的總體要求
掌握數(shù)據(jù)結(jié)構(gòu)中常用的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和基本操作,靈活運用所學(xué)的數(shù)據(jù)結(jié)構(gòu)解決實際問題;掌握典型的查找和排序算法,并能夠針對不同特征的數(shù)據(jù)集進行有效應(yīng)用;能夠分析算法的時間復(fù)雜度,設(shè)計具有較高時空性能的算法。
二、考試的內(nèi)容
1、基本概念和術(shù)語
2、線性表
線性表的定義;線性表的邏輯結(jié)構(gòu);線性表的存儲結(jié)構(gòu)(順序存儲、鏈?zhǔn)酱鎯?;不同存儲方式下操作的實現(xiàn);線性表的應(yīng)用。
3、棧與隊列
棧:棧的定義;棧的邏輯結(jié)構(gòu);棧的存儲結(jié)構(gòu)(順序存儲,鏈?zhǔn)酱鎯?;不同存儲方式下操作的實現(xiàn);棧的應(yīng)用。
隊列:隊列的定義;隊列的邏輯結(jié)構(gòu);隊列的存儲結(jié)構(gòu)(順序,鏈?zhǔn)?;不同存儲方式下操作的實現(xiàn);隊列的應(yīng)用。
4、樹和二叉樹
二叉樹:二叉樹的概念;二叉樹的基本性質(zhì);二叉樹的邏輯結(jié)構(gòu);二叉樹的存儲結(jié)構(gòu)(順序、鏈?zhǔn)?;各存儲結(jié)構(gòu)上的基本操作實現(xiàn);二叉樹的應(yīng)用。
樹和森林:樹(森林)的基本概念;樹(森林)的邏輯結(jié)構(gòu);樹(森林)的存儲結(jié)構(gòu)(雙親表示法,孩子鏈表表示法,孩子兄弟鏈表表示法);樹(森林)的基本操作實現(xiàn);樹(森林)的應(yīng)用。
樹(森林)與二叉樹之間的相互轉(zhuǎn)換;
哈夫曼樹(最優(yōu)二叉樹):哈夫曼樹的定義、哈夫曼樹的存儲與應(yīng)用。
5、圖
圖的定義與基本術(shù)語;圖的邏輯結(jié)構(gòu);圖的存儲結(jié)構(gòu)(鄰接矩陣,鄰接表及逆鄰接表);不同存儲結(jié)構(gòu)上的基本操作實現(xiàn);圖的應(yīng)用。
6、查找
基本概念與術(shù)語;靜態(tài)查找(順序查找、折半查找、分塊查找);動態(tài)查找(二叉排序樹、二叉平衡樹和B-樹的查找、插入和刪除);哈希查找(哈希表的概念、常用的哈希函數(shù)、解決沖突的方法);查找性能分析(平均查找長度);
7、排序
插入類排序(直接插入排序、折半插入排序、希爾排序)、交換類排序(冒泡排序、快速排序)、選擇類排序(簡單選擇排序、堆排序)、歸并類排序(二路歸并排序)、基數(shù)排序;各種排序方法的穩(wěn)定性和時間性能分析。
8.綜合應(yīng)用:根據(jù)實際問題,設(shè)計有效的數(shù)據(jù)結(jié)構(gòu)和算法,并進行時間復(fù)雜度分析。
三、考試的題型
選擇題、填空題、綜合題、算法設(shè)計題
第二部分:操作系統(tǒng)
一、考試的總體要求
要求考生熟練掌握計算機操作系統(tǒng)中的基本概念、基本原理; 從資源管理角度掌握計算機操作系統(tǒng)的主要功能及設(shè)計思想;了解和掌握現(xiàn)代計算機系統(tǒng)對其各種軟硬資源的管理方法及實現(xiàn)技術(shù);了解當(dāng)代計算機操作系統(tǒng)的新技術(shù)與發(fā)展趨勢。
二、考試的內(nèi)容
1.操作系統(tǒng)概述:
包括操作系統(tǒng)的定義;操作系統(tǒng)的發(fā)展過程;操作系統(tǒng)的分類;操作系統(tǒng)的特征和服務(wù);操作系統(tǒng)的功能;常用操作系統(tǒng)的結(jié)構(gòu)特點。
2.進程管理:
包括進程的基本概念;進程控制(進程的狀態(tài)機轉(zhuǎn)換);進程同步;經(jīng)典的進程同步互斥問題;進程通信;線程的定義及實現(xiàn)。
3.處理機調(diào)度與死鎖:
包括處理機調(diào)度的基本概念;調(diào)度方式及算法;死鎖的基本概念;死鎖的概念; 死鎖的處理策略。
4.存儲器管理:
包括程序的裝入和鏈接;連續(xù)分配存儲管理方式;覆蓋與交換;分頁存儲管理方式;分段存儲管理方式。虛擬存儲器的基本概念;請求分頁存儲管理方式;頁面置換算法;請求分段存儲管理方式。
5.設(shè)備管理:
包括I/O系統(tǒng)的組成;I/O控制方式;I/O軟件層次結(jié)構(gòu);設(shè)備獨立性;緩沖管理;假脫機技術(shù);設(shè)備分配;設(shè)備處理。
6.文件管理:
包括文件和文件系統(tǒng);文件邏輯結(jié)構(gòu);目錄管理;文件共享;文件保護。
7.磁盤管理:
包括磁盤I/O;外存分配方法;空閑存儲空間的管理;磁盤容錯技術(shù)。
三、考試的題型
單向選擇題、填空題、應(yīng)用題