考試科目名稱：數(shù)據(jù)結(jié)構(gòu)與組成原理

科目代碼：

(一)數(shù)據(jù)結(jié)構(gòu)部分

一、數(shù)據(jù)結(jié)構(gòu)的一般概念

1.掌握數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語。

2.了解抽象數(shù)據(jù)類型的概念。

3.掌握算法的特性，算法的描述和算法的分析。

二、線性表

1.理解線性表的邏輯結(jié)構(gòu)。

2.掌握線性表的順序存貯結(jié)構(gòu)和鏈?zhǔn)酱尜A結(jié)構(gòu);掌握線性表基本操作的實(shí)現(xiàn)。

3.了解線性表的應(yīng)用。

三、其他線性結(jié)構(gòu)

1.掌握棧的定義、棧的存貯結(jié)構(gòu)及基本操作的實(shí)現(xiàn)。

2.理解用棧實(shí)現(xiàn)表達(dá)式的求值，遞歸過程及其實(shí)現(xiàn)。

3.掌握隊(duì)列的定義、存貯結(jié)構(gòu)及基本操作的實(shí)現(xiàn)

4.理解串的邏輯定義及其基本操作;理解串的存貯結(jié)構(gòu)。

5.理解數(shù)組的定義、數(shù)組的順序存貯結(jié)構(gòu)及矩陣的存貯壓縮。

6.理解廣義表的定義及存貯結(jié)構(gòu)。

四、樹和二叉樹

1.掌握樹型結(jié)構(gòu)的定義。

2.掌握二叉樹的定義、性質(zhì)及各種存貯結(jié)構(gòu)。

3.掌握遍歷二叉樹、線索二叉樹及其他基本操作。

4.掌握樹、森林與二叉樹的相互轉(zhuǎn)換;理解樹的遍歷;掌握哈夫曼樹及其應(yīng)用。

五、圖

1.掌握?qǐng)D的定義和術(shù)語。

2.掌握?qǐng)D的存貯結(jié)構(gòu);理解圖的基本操作。

3.掌握?qǐng)D的遍歷算法;了解利用圖的遍歷解決圖的應(yīng)用問題。

4.理解圖的有關(guān)應(yīng)用：求最小生成樹、求最短路徑、拓?fù)渑判蚣瓣P(guān)鍵路徑等算法的基本思想。

六、查找

1.掌握靜態(tài)查找表。

2.掌握二叉排序樹和平衡二叉樹。

3.理解B-樹;了解B+樹。

4.掌握哈希表。

5.掌握各種查找方法的時(shí)間性能分析。

七、內(nèi)部排序

1.掌握直接插入排序、希爾排序、冒泡排序、快速排序、簡(jiǎn)單選擇排序、堆排序、歸并排序;理解基數(shù)排序。

2.學(xué)會(huì)各種內(nèi)部排序方法的比較(時(shí)間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性)。

參考書目：

1. 《數(shù)據(jù)結(jié)構(gòu)》(C語言版)，嚴(yán)蔚敏 吳偉民編著，清華大學(xué)出版社，2006.3

2. 《數(shù)據(jù)結(jié)構(gòu)實(shí)用教程》(C++版)，萬健主編，電子工業(yè)出版社，2011.1

(二)計(jì)算機(jī)組成原理部分

一、計(jì)算機(jī)系統(tǒng)概述

1.計(jì)算機(jī)系統(tǒng)的發(fā)展與分類。

2.計(jì)算機(jī)系統(tǒng)的組成與層次結(jié)構(gòu)。

3.馮·諾伊曼體系結(jié)構(gòu)計(jì)算機(jī)的主要特點(diǎn)。

4.計(jì)算機(jī)硬件系統(tǒng)的組成部件及其功能。

5.計(jì)算機(jī)的主要性能指標(biāo)。

6.計(jì)算機(jī)中的三種語言：機(jī)器語言、匯編語言、高級(jí)語言。

二、信息編碼與數(shù)據(jù)表示

1.計(jì)算機(jī)信息編碼

(1)進(jìn)位計(jì)數(shù)制及其相互轉(zhuǎn)換。

(2)BCD碼。

(3)真值、機(jī)器數(shù)與數(shù)據(jù)格式。

(4)非數(shù)值數(shù)據(jù)的表示：字符、漢字。

(5)校驗(yàn)碼校驗(yàn)方法及其校驗(yàn)?zāi)芰Α?/p>

2.定點(diǎn)機(jī)器數(shù)的表示

(1)無符號(hào)數(shù)的表示。

(2)有符號(hào)數(shù)的表示：原碼、反碼、補(bǔ)碼、移碼。

3.浮點(diǎn)機(jī)器數(shù)的表示

(1)浮點(diǎn)數(shù)的格式與特點(diǎn)。

(2)浮點(diǎn)數(shù)的規(guī)格化表示。

(3)IEEE754浮點(diǎn)數(shù)標(biāo)準(zhǔn)。

三、運(yùn)算方法與運(yùn)算器

1.定點(diǎn)機(jī)器數(shù)的運(yùn)算方法

(1)補(bǔ)碼定點(diǎn)機(jī)器數(shù)的加/減運(yùn)算。

(2)定點(diǎn)機(jī)器數(shù)的乘/除運(yùn)算。

(3)機(jī)器數(shù)的移位運(yùn)算。

(4)運(yùn)算溢出概念和判別方法。

2.浮點(diǎn)機(jī)器數(shù)的運(yùn)算方法

(1)浮點(diǎn)機(jī)器數(shù)的加/減運(yùn)算。

(2)浮點(diǎn)機(jī)器數(shù)的乘/除運(yùn)算方法。

3.運(yùn)算器的組成與功能

(1)加法器：串行進(jìn)位加法器與并行進(jìn)位加法器。

(2)補(bǔ)碼加/減運(yùn)算器。

(3)算術(shù)邏輯單元ALU：功能與結(jié)構(gòu)。

(4)定點(diǎn)運(yùn)算器的結(jié)構(gòu)與數(shù)據(jù)通路。

(5)浮點(diǎn)運(yùn)算器。

(6)標(biāo)志寄存器。

四、存儲(chǔ)體系

1.存儲(chǔ)器的分類。

2.存儲(chǔ)器的技術(shù)指標(biāo)與層次結(jié)構(gòu)。

3.主存儲(chǔ)器

(1)主存儲(chǔ)器的訪問操作與構(gòu)成。

(2)半導(dǎo)體隨機(jī)存取存儲(chǔ)器：SRAM與DRAM的構(gòu)成及工作原理。

(3)只讀存儲(chǔ)器ROM。

4.主存儲(chǔ)器與CPU的連接

(1)存儲(chǔ)容量的擴(kuò)展與地址譯碼。

(2)主存儲(chǔ)器與CPU的連接方法。

5.提高存儲(chǔ)器訪問速度的方法與高速存儲(chǔ)器

(1)雙端口存儲(chǔ)器

(2)多體交叉存儲(chǔ)器

(3)相聯(lián)存儲(chǔ)器

6.高速緩沖存儲(chǔ)器(Cache)

(1)Cache的特點(diǎn)。

(2)設(shè)置Cache的目的和理論基礎(chǔ)。

(3)Cache的構(gòu)成與基本工作原理。

(4)Cache的地址映射方法。

(5)Cache的替換策略與寫策略。

7.虛擬存儲(chǔ)器

(1)虛擬存儲(chǔ)器的基本概念。

(2)虛擬存儲(chǔ)器的實(shí)現(xiàn)方式。

8.外存儲(chǔ)器

(1)磁盤存儲(chǔ)器。

(2)光盤存儲(chǔ)器。

五、指令系統(tǒng)

1.機(jī)器指令與指令系統(tǒng)的基本概念。

2.指令格式

(1)機(jī)器指令的基本格式。

(2)指令操作碼擴(kuò)展技術(shù)。

3.尋址方式

(1)尋址方式的基本概念：定義、設(shè)置的目的與意義。

(2)數(shù)據(jù)尋址與指令尋址。

(3)常見的數(shù)據(jù)尋址方式和指令尋址方式。

4.指令類型。

5.CISC和RISC的特點(diǎn)。

6.機(jī)器語言程序的編寫與閱讀。

六、控制器

1.控制器的組成與功能。

2.兩種控制器的特點(diǎn)和區(qū)別：硬布線控制器、微程序控制器。

3.系統(tǒng)結(jié)構(gòu)與數(shù)據(jù)通路。

4.指令執(zhí)行過程。

5.指令周期、機(jī)器周期與時(shí)鐘周期。

6.硬布線控制器

(1)硬布線控制器的組成。

(2)硬布線控制器的設(shè)計(jì)。

7.微程序控制器

(1)基本概念：微命令、微指令、微程序、微地址、控制存儲(chǔ)器。

(2)微指令格式與微指令編碼。

(3)微程序控制器的組成。

8.指令流水線的基本概念。

七、輸入輸出系統(tǒng)

1.I/O系統(tǒng)與接口的基本概念。

2.4種I/O傳送方式：原理與特點(diǎn)。

3.中斷系統(tǒng)基本概念。

參考書目：《計(jì)算機(jī)組成原理與系統(tǒng)結(jié)構(gòu)》，包健等，高等教育出版社，2009.9