1、西北師范大學(xué)專升本招生計算機科學(xué)與技術(shù)專業(yè)考試大綱一、考試目的西北師范大學(xué)專升本招生計算機科學(xué)與技術(shù)專業(yè)考試包括兩部分內(nèi)容：數(shù)據(jù)結(jié)構(gòu)和操作系統(tǒng)。考試目的是檢查學(xué)生是否牢固掌握數(shù)據(jù)結(jié)構(gòu)和操作系統(tǒng)兩門課程相關(guān)知識的一次水平測定，全面考核普通高校計算機專科（含高職）應(yīng)屆畢業(yè)生對專業(yè)核心課程數(shù)據(jù)結(jié)構(gòu)和操作系統(tǒng)的掌握程度，要求學(xué)生比較系統(tǒng)地理解數(shù)據(jù)結(jié)構(gòu)和操作系統(tǒng)的基本概念和基本理論。二、考試內(nèi)容數(shù)據(jù)結(jié)構(gòu)部分（一）數(shù)據(jù)結(jié)構(gòu)的概念1、什么是數(shù)據(jù)結(jié)構(gòu)（邏輯結(jié)構(gòu)，存儲結(jié)構(gòu)，運算）；2、算法，算法分析，算法特性；3、算法與程序的差別。（二）線性表1、線性表（向量）的定義，操作，算法；2、順序表的概念，存儲表示，查

2、找，插入，刪除等運算和算法；3、鏈表的概念及其特點；4、單鏈表的概念，存儲表示，查找，插入，刪除等運算和算法；5、雙鏈表的概念，存儲表示，查找，插入，刪除等運算和算法。（三）棧和隊列1、棧的定義，順序、鏈?zhǔn)奖硎九c實現(xiàn)，算法；2、隊列的定義，順序、鏈?zhǔn)奖硎九c實現(xiàn)，算法。（四）樹和二叉樹1、樹和二叉樹的概念；2、樹（林）與二叉樹的相互轉(zhuǎn)換；3、二叉樹的存儲表示（1）二叉鏈表（2）完全二叉樹的順序存儲；4、二叉樹與樹的遍歷的概念，各種遍歷方法；5、二叉樹遍歷的算法；6、二叉樹中其他算法（結(jié)點統(tǒng)計，高度計算，左右子樹交換等）。（五）圖1、圖的概念和相關(guān)術(shù)語；2、圖的存儲表示方法：鄰接矩陣，鄰接表，鄰接

3、多重表；3、圖的遍歷： 深度優(yōu)先遍歷，廣度優(yōu)先遍歷；4、最小生成樹的概念，構(gòu)造方法，算法；5、拓撲排序的概念，算法思想，算法；6、最短路徑的概念，構(gòu)造方法，算法。 （六）查找1、順序查找的概念，算法，時間復(fù)雜度；2、折半查找的概念，算法，時間復(fù)雜度；3、二叉排序樹的概念，插入，刪除運算；5、平衡二叉排序樹（AVL）的概念，構(gòu)造方法（如何調(diào)整。）6、哈希法：（1）基本概念；（2）哈希函數(shù)的構(gòu)造方法；（3）沖突的處理：拉鏈法，開地址法，算法。（七）內(nèi)排序1、排序的概念，內(nèi)排序和外排序，排序算法的穩(wěn)定性；2、內(nèi)排序的分類；3、各種排序的基本思想，例子，算法，穩(wěn)定性，時空復(fù)雜度。操作系統(tǒng)部分（一）操作

4、系統(tǒng)的基本概念1、理解操作系統(tǒng)的定義、特征以及設(shè)置操作系統(tǒng)的目的；2、了解操作系統(tǒng)在計算機系統(tǒng)中的地位、操作系統(tǒng)的形成和發(fā)展；3、掌握多道程序設(shè)計的思想、特點和優(yōu)點；4、了解操作系統(tǒng)的分類；理解批處理、分時和實時系統(tǒng)的特征；5、理解操作系統(tǒng)的功能；6、理解操作系統(tǒng)為用戶提供的接口；7、掌握系統(tǒng)調(diào)用的概念、過程及其與一般的過程調(diào)用的區(qū)別；8、了解操作系統(tǒng)內(nèi)核的概念和分類。（二）進程管理和處理器管理1、理解并掌握程序的并發(fā)執(zhí)行和資源共享；2、掌握程序并發(fā)執(zhí)行的特性；3、掌握進程的概念、特征和狀態(tài)轉(zhuǎn)換；4、了解進程控制及進程控制原語；5、熟練掌握常用的調(diào)度算法；6、熟練掌握作業(yè)、進程和程序之間的區(qū)別

5、和聯(lián)系；7、理解并掌握進程間的同步與互斥；8、理解信號量及P，V操作，并能利用信號量機制實現(xiàn)進程間的同步與互斥； 9、 理解并熟練掌握利用信號量機制實現(xiàn)的生產(chǎn)者消費者問題；10、了解高級通訊原語（消息緩沖方式，信箱方式）；11、理解并掌握死鎖的概念、起因及產(chǎn)生死鎖的必要條件；12、了解處理死鎖的四種對策（預(yù)防策略，避免策略，檢測和解除）；13了解單項資源的銀行家算法和多種資源的銀行家算法；（三）存儲管理1、理解并掌握存儲管理的基本概念功能及物理地址和邏輯地址之間的關(guān)系；2、了解早期計算機系統(tǒng)中主要采用的單一連續(xù)分配，分區(qū)分配，覆蓋和交換的存儲管理方案；3、理解并掌握頁式、段式和段頁式虛擬存儲管

6、理的基本原理和地址轉(zhuǎn)換關(guān)系；4、理解并熟練掌握各種頁面置換算法（FIFO，LRU，LRU近似算法）。（四）文件管理系統(tǒng)1、理解文件和文件系統(tǒng)的概念；2、了解文件的基本類型及文件系統(tǒng)的基本功能；3、理解文件的邏輯結(jié)構(gòu)（記錄式文件，流式文件）；4、理解文件的物理結(jié)構(gòu)（連續(xù)結(jié)構(gòu)，串連結(jié)構(gòu)，索引文件）；5、掌握文件的存取方法（順序存取法，直接存取法，按鍵存取法）；6、理解文件結(jié)構(gòu)，文件存儲設(shè)備和存取法的關(guān)系；7、掌握簡單的文件目錄、二級目錄和多級目錄；8、掌握文件存儲空間管理的各種辦法；9、掌握文件存取控制的各種方法；10、了解文件系統(tǒng)和用戶間的接口。（五）設(shè)備管理1、了解I/O設(shè)備類型及設(shè)備管理的設(shè)計目標(biāo)；2、了解設(shè)備管理的基本功能；3、掌握I/O控制的幾種方式；4、掌握通道功能及類型；5、了解通道命令和通道程序；6、了解順序存取存儲設(shè)備和直接存取存儲設(shè)備;7、掌握磁盤的驅(qū)動調(diào)度算法。（六）常用操作系統(tǒng)了解WINDOWS操作系統(tǒng)和UNIX操作系統(tǒng)的概念和基本特點。三、試卷結(jié)構(gòu)選擇題 約20/% 填空題 約10/% 判斷題 約10/% 簡答題約40/% 算法設(shè)計題選擇題 約20/% （針對數(shù)據(jù)結(jié)構(gòu)）計算或應(yīng)用題約20/% （針對操作系統(tǒng)）四、試題難易度較容易題 約30%中等難度題 約50%較難題約20%五、說明試卷滿分為200分，數(shù)據(jù)結(jié)構(gòu)和操作系統(tǒng)各100分，考試