考試科目名稱：數據結構與組成原理
科目代碼：
(一)數據結構部分
一、數據結構的一般概念
1.掌握數據結構的基本概念和術語。
2.了解抽象數據類型的概念。
3.掌握算法的特性，算法的描述和算法的分析。
二、線性表
1.理解線性表的邏輯結構。
2.掌握線性表的順序存貯結構和鏈式存貯結構;掌握線性表基本操作的實現。
3.了解線性表的應用。
三、其他線性結構
1.掌握棧的定義、棧的存貯結構及基本操作的實現。
2.理解用棧實現表達式的求值，遞歸過程及其實現。
3.掌握隊列的定義、存貯結構及基本操作的實現
4.理解串的邏輯定義及其基本操作;理解串的存貯結構。
5.理解數組的定義、數組的順序存貯結構及矩陣的存貯壓縮。
6.理解廣義表的定義及存貯結構。
四、樹和二叉樹
1.掌握樹型結構的定義。
2.掌握二叉樹的定義、性質及各種存貯結構。
3.掌握遍歷二叉樹、線索二叉樹及其他基本操作。
4.掌握樹、森林與二叉樹的相互轉換;理解樹的遍歷;掌握哈夫曼樹及其應用。
五、圖
1.掌握圖的定義和術語。
2.掌握圖的存貯結構;理解圖的基本操作。
3.掌握圖的遍歷算法;了解利用圖的遍歷解決圖的應用問題。
4.理解圖的有關應用：求最小生成樹、求最短路徑、拓撲排序及關鍵路徑等算法的基本思想。
六、查找
1.掌握靜態(tài)查找表。
2.掌握二叉排序樹和平衡二叉樹。
3.理解B-樹;了解B+樹。
4.掌握哈希表。
5.掌握各種查找方法的時間性能分析。
七、內部排序
1.掌握直接插入排序、希爾排序、冒泡排序、快速排序、簡單選擇排序、堆排序、歸并排序;理解基數排序。
2.學會各種內部排序方法的比較(時間復雜度、空間復雜度、穩(wěn)定性)。
參考書目：
1. 《數據結構》(C語言版)，嚴蔚敏 吳偉民編著，清華大學出版社，2006.3
2. 《數據結構實用教程》(C++版)，萬健主編，電子工業(yè)出版社，2011.1
(二)計算機組成原理部分
一、計算機系統(tǒng)概述
1.計算機系統(tǒng)的發(fā)展與分類。
2.計算機系統(tǒng)的組成與層次結構。
3.馮·諾伊曼體系結構計算機的主要特點。
4.計算機硬件系統(tǒng)的組成部件及其功能。
5.計算機的主要性能指標。
6.計算機中的三種語言：機器語言、匯編語言、高級語言。
二、信息編碼與數據表示
1.計算機信息編碼
(1)進位計數制及其相互轉換。
(2)BCD碼。
(3)真值、機器數與數據格式。
(4)非數值數據的表示：字符、漢字。
(5)校驗碼校驗方法及其校驗能力。
2.定點機器數的表示
(1)無符號數的表示。
(2)有符號數的表示：原碼、反碼、補碼、移碼。
3.浮點機器數的表示
(1)浮點數的格式與特點。
(2)浮點數的規(guī)格化表示。
(3)IEEE754浮點數標準。
三、運算方法與運算器
1.定點機器數的運算方法
(1)補碼定點機器數的加/減運算。
(2)定點機器數的乘/除運算。
(3)機器數的移位運算。
(4)運算溢出概念和判別方法。
2.浮點機器數的運算方法
(1)浮點機器數的加/減運算。
(2)浮點機器數的乘/除運算方法。
3.運算器的組成與功能
(1)加法器：串行進位加法器與并行進位加法器。
(2)補碼加/減運算器。
(3)算術邏輯單元ALU：功能與結構。
(4)定點運算器的結構與數據通路。
(5)浮點運算器。
(6)標志寄存器。
四、存儲體系
1.存儲器的分類。
2.存儲器的技術指標與層次結構。
3.主存儲器
(1)主存儲器的訪問操作與構成。
(2)半導體隨機存取存儲器：SRAM與DRAM的構成及工作原理。
(3)只讀存儲器ROM。
4.主存儲器與CPU的連接
(1)存儲容量的擴展與地址譯碼。
(2)主存儲器與CPU的連接方法。
5.提高存儲器訪問速度的方法與高速存儲器
(1)雙端口存儲器
(2)多體交叉存儲器
(3)相聯存儲器
6.高速緩沖存儲器(Cache)
(1)Cache的特點。
(2)設置Cache的目的和理論基礎。
(3)Cache的構成與基本工作原理。
(4)Cache的地址映射方法。
(5)Cache的替換策略與寫策略。
7.虛擬存儲器
(1)虛擬存儲器的基本概念。
(2)虛擬存儲器的實現方式。
8.外存儲器
(1)磁盤存儲器。
(2)光盤存儲器。
五、指令系統(tǒng)
1.機器指令與指令系統(tǒng)的基本概念。
2.指令格式
(1)機器指令的基本格式。
(2)指令操作碼擴展技術。
3.尋址方式
(1)尋址方式的基本概念：定義、設置的目的與意義。
(2)數據尋址與指令尋址。
(3)常見的數據尋址方式和指令尋址方式。
4.指令類型。
5.CISC和RISC的特點。
6.機器語言程序的編寫與閱讀。
六、控制器
1.控制器的組成與功能。
2.兩種控制器的特點和區(qū)別：硬布線控制器、微程序控制器。
3.系統(tǒng)結構與數據通路。
4.指令執(zhí)行過程。
5.指令周期、機器周期與時鐘周期。
6.硬布線控制器
(1)硬布線控制器的組成。
(2)硬布線控制器的設計。
7.微程序控制器
(1)基本概念：微命令、微指令、微程序、微地址、控制存儲器。
(2)微指令格式與微指令編碼。
(3)微程序控制器的組成。
8.指令流水線的基本概念。
七、輸入輸出系統(tǒng)
1.I/O系統(tǒng)與接口的基本概念。
2.4種I/O傳送方式：原理與特點。
3.中斷系統(tǒng)基本概念。
參考書目：《計算機組成原理與系統(tǒng)結構》，包健等，高等教育出版社，2009.9
公眾號
事業(yè)單位
當前位置：
公考類
招聘類
各類考試
