2022年北京交通大學(xué)906計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)碩士研究生考研大綱及參考書(shū)目 正文

906 計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)（90 分）
1、緒論。（1）掌握相關(guān)的基本概念，如數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)類(lèi)型、抽象數(shù)據(jù)類(lèi)型等；（2）掌握算法設(shè)計(jì)的原則，掌握計(jì)算語(yǔ)句頻度和估算算法時(shí)間復(fù)雜度和空間復(fù)雜度的方法；（3）了解使用類(lèi)C 語(yǔ)言描述算法的方法。
2、線性表。（1）掌握線性表的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)；（2）掌握線性表在順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)上實(shí)現(xiàn)基本操作的方法；（3）理解線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合，會(huì)針對(duì)需求選用合適的存儲(chǔ)結(jié)構(gòu)解決實(shí)際問(wèn)題；（4） 了解一元多項(xiàng)式的表示方法和基本運(yùn)算的實(shí)現(xiàn)方法。
3、棧和隊(duì)列。（1）了解棧和隊(duì)列的特點(diǎn)；（2）掌握在兩種存儲(chǔ)結(jié)構(gòu)上棧的基本操作的實(shí)現(xiàn)；（3）掌握棧的各種應(yīng)用，理解遞歸算法執(zhí)行過(guò)程中棧狀態(tài)的變化過(guò)程；（4）掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本運(yùn)算；（5）會(huì)應(yīng)用隊(duì)列結(jié)構(gòu)解決實(shí)際問(wèn)題。
4、串。（1）掌握串的基本運(yùn)算的定義，了解利用基本運(yùn)算來(lái)實(shí)現(xiàn)串的其它運(yùn)算的方法；（2）了解在順序存儲(chǔ)結(jié)構(gòu)和在堆存儲(chǔ)結(jié)構(gòu)以及塊鏈存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)串的各種操作的方法；（3）理解KMP 算法，掌握 NEXT 函數(shù)和改進(jìn) NEXT 函數(shù)的定義和計(jì)算。
5、數(shù)組和廣義表。（1）掌握數(shù)組在以行為主和以列為主的存儲(chǔ)結(jié)構(gòu)中的地址計(jì)算方法；（2）掌握矩陣壓縮存儲(chǔ)時(shí)的下標(biāo)變換方法，了解以三元組表示稀疏矩陣的方法；（3）理解廣義表的定義及其存儲(chǔ)結(jié)構(gòu)，理解廣義表的頭尾和子表兩種分析方法。
6、樹(shù)和二叉樹(shù)。（1）熟練掌握二叉樹(shù)的結(jié)構(gòu)特點(diǎn)和性質(zhì)，掌握二叉樹(shù)各種存儲(chǔ)結(jié)構(gòu)及構(gòu)建方法；（2）掌握按先序、中序、后序和層次次序遍歷二叉樹(shù)的算法，理解二叉樹(shù)的線索化實(shí)質(zhì)和方法；（3）利用二叉樹(shù)的遍歷求解實(shí)際問(wèn)題；
（4）掌握樹(shù)的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)，掌握樹(shù)的各種運(yùn)算的實(shí)現(xiàn)算法；（5）掌握建立最優(yōu)二叉樹(shù)和哈夫曼編碼的方法。
7、圖。（1）熟練掌握?qǐng)D的基本概念，會(huì)構(gòu)建各種圖的存儲(chǔ)結(jié)構(gòu)；（2）掌握深度優(yōu)先搜索遍歷圖和廣度優(yōu)先搜索遍歷圖的算法；（3）靈活運(yùn)用圖的遍歷算法求解各種路徑問(wèn)題，包括最小生成樹(shù)﹑最短路徑﹑拓?fù)渑判颟p關(guān)鍵路徑等。
8、查找。（1）熟練掌握各種靜態(tài)查找和動(dòng)態(tài)查找算法，會(huì)計(jì)算查找成功時(shí)和失敗時(shí)的平均查找長(zhǎng)度；（2）掌握二叉排序樹(shù)的建立、插入和刪除過(guò)程，掌握二叉平衡樹(shù)的建立和旋轉(zhuǎn)平衡方法；（3）掌握 B-樹(shù)的建立、插入和刪除結(jié)點(diǎn)的過(guò)程；（4）熟練掌握哈希表的構(gòu)造方法和處理沖突的方法。
9、排序。（1）掌握各種排序算法，包括插入類(lèi)、交換類(lèi)、選擇類(lèi)、歸并類(lèi)排序及基數(shù)排序；（2）能夠?qū)Ω鞣N排序方法進(jìn)行比較分析，如穩(wěn)定性、時(shí)間和空間性能等，了解各種排序方法的特點(diǎn)和不同并靈活應(yīng)用。
操作系統(tǒng)原理（60 分）
1、引論。（1）要求理解的內(nèi)容包括：操作系統(tǒng)的概念、設(shè)計(jì)目標(biāo)、功能及特征，操作系統(tǒng)運(yùn)行硬件基礎(chǔ)，操作系統(tǒng)接口分類(lèi)及組成，操作系統(tǒng)內(nèi)核用典型數(shù)據(jù)結(jié)構(gòu)；（2）要求掌握的內(nèi)容包括：系統(tǒng)調(diào)用實(shí)現(xiàn)機(jī)制，操作系統(tǒng)啟動(dòng)引導(dǎo)過(guò)程。
2、處理機(jī)管理。（1）要求理解的內(nèi)容包括：多道程序設(shè)計(jì)技術(shù)，程序、進(jìn)程、線程的區(qū)別與聯(lián)系，線程實(shí)現(xiàn)方式，進(jìn)程狀態(tài)變遷，進(jìn)程控制，處理機(jī)調(diào)度類(lèi)型與模型，處理機(jī)調(diào)度實(shí)現(xiàn)機(jī)理，調(diào)度算法與評(píng)價(jià)準(zhǔn)則；（2）要求掌握的內(nèi)容包括：處理機(jī)主要調(diào)度算法設(shè)計(jì)實(shí)現(xiàn)及應(yīng)用。
3、同步通信及死鎖處理。（1）要求理解的內(nèi)容包括：進(jìn)程同步基本準(zhǔn)則， 進(jìn)程同步軟硬件解決方案，整型信號(hào)量、記錄型信號(hào)量、管程，經(jīng)典同步問(wèn)題， 進(jìn)程通信機(jī)制，線程同步機(jī)制，死鎖及處理方法；（2）要求掌握的內(nèi)容包括： 利用記錄型信號(hào)量解決同步問(wèn)題，利用銀行家算法給出避免死鎖的資源分配方案， 死鎖檢測(cè)算法及應(yīng)用。
4、存儲(chǔ)管理。（1）要求理解的內(nèi)容包括：程序處理與內(nèi)存管理，分區(qū)存儲(chǔ)管理及相關(guān)技術(shù)（拼湊、覆蓋、對(duì)換、伙伴系統(tǒng)），分頁(yè)/分段/段頁(yè)式存儲(chǔ)管理， 虛擬存儲(chǔ)技術(shù)，請(qǐng)求分頁(yè)/分段存儲(chǔ)管理，多級(jí)頁(yè)表和反置頁(yè)表，內(nèi)存保護(hù)機(jī)制；
（2）要求掌握的內(nèi)容包括：分頁(yè)/分段地址變換，頁(yè)面淘汰算法設(shè)計(jì)實(shí)現(xiàn)及應(yīng)用，請(qǐng)求分頁(yè)/分段地址變換，動(dòng)態(tài)分區(qū)存儲(chǔ)管理設(shè)計(jì)與實(shí)現(xiàn)。
5、設(shè)備管理。（1）要求理解的內(nèi)容包括：I/O 系統(tǒng)組成及 I/O 控制方式， 設(shè)備管理目標(biāo)、功能及層次結(jié)構(gòu)，緩沖管理，設(shè)備分配及假脫機(jī)技術(shù)，設(shè)備驅(qū)動(dòng)及中斷處理，磁盤(pán)存儲(chǔ)器管理方法與技術(shù)；（2）要求掌握的內(nèi)容包括：磁盤(pán)調(diào)度算法設(shè)計(jì)及應(yīng)用，磁盤(pán)數(shù)據(jù)訪問(wèn)過(guò)程及時(shí)間開(kāi)銷(xiāo)。
6、文件管理。（1）要求理解的內(nèi)容包括：文件及典型存取操作邏輯流程， 文件系統(tǒng)層次模型，文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，外存空間管理方法，文件目錄結(jié)構(gòu)及管理，文件共享與保護(hù)，磁盤(pán)容錯(cuò)技術(shù)，文件系統(tǒng)性能改善策略及數(shù)據(jù)一致性控制；（2）要求掌握的內(nèi)容包括：目錄檢索過(guò)程，文件數(shù)據(jù)訪問(wèn)基本過(guò)程， FAT 文件系統(tǒng)設(shè)計(jì)實(shí)現(xiàn)。
7、操作系統(tǒng)發(fā)展與演化。要求理解的內(nèi)容包括：批處理、分時(shí)和實(shí)時(shí)系統(tǒng)的概念，操作系統(tǒng)結(jié)構(gòu)設(shè)計(jì)及演化，操作系統(tǒng)發(fā)展趨勢(shì)。

北京交通大學(xué)

本文來(lái)源：http://m.zhangjiajieline.cn/beijingjiaotongdaxue/cankaoshu_470188.html