2017年考試內容范圍說明

1、2017年考試內容范圍說明考試科目代碼：847 考試科目名稱：計算機學科專業(yè)綜合數據結構部分一、緒論 1、理解數據結構的基本概念；了解數據類型和抽象數據類型的概念；2、理解算法的設計目標；掌握算法的時間、空間復雜度概念以及時間、空間復雜度的分析方法。 二、線性表 1、理解線性表的邏輯結構和基本操作；2、熟練掌握線性表的順序存儲結構和實現方法；3、熟練掌握線性表的鏈式存儲結構和實現方法；4、理解單循環(huán)鏈表和雙向鏈表的概念和基本設計方法。 三、棧和隊列 1、熟練掌握棧的概念、順序棧和鏈式棧的設計方法及應用方法; 2、熟練掌握隊列的概念、順序循環(huán)隊列和鏈式隊列的設計方法及應用方法3、理解遞歸算法的思

2、想，遞歸算法執(zhí)行過程中工作棧的變化過程。 四、數組 1、理解多維數組的概念及存儲結構，掌握多維數組的地址計算方法；2、掌握特殊矩陣的壓縮存儲方法；3、掌握稀疏矩陣的壓縮存儲方法及應用，用三元組存儲稀疏矩陣時的基本矩陣運算方法。 五、樹和二叉樹 1、理解樹的定義、表示方法和樹的幾種典型存儲結構；2、熟練掌握二叉樹的定義、二叉樹的性質、二叉樹的存儲結構和二叉樹操作的實現方法；3、熟練掌握二叉樹的遍歷算法和二叉樹問題的遍歷算法設計分析和實現；4、理解哈夫曼樹的概念，掌握建立哈夫曼樹和哈夫曼樹編碼的方法；5、掌握樹與二叉樹的轉換方法；樹的遍歷；森林與二叉樹的轉換；森林的遍歷。 六、圖 1、理解圖的基本

3、概念和術語；熟練掌握圖的鄰接矩陣和鄰接表存儲結構以及圖基本操作的實現方法；2、熟練掌握圖的深度和廣度遍歷方法和算法設計方法；3、理解最小生成樹的概念，熟練掌握普里姆算法和克魯斯卡爾算法并掌握其生成方法；4、掌握單源點最短路徑的算法，拓撲排序方法，理解關鍵路徑的概念。 七、查找 1、掌握查找的基本概念和查找方法的評判標準；2、熟練掌握順序查找和有序查找的算法設計方法，理解索引查找的基本結構；3、理解二叉排序樹的特點；掌握二叉排序樹的構造和查找方法4、熟練掌握哈希函數、哈希表的構造方法，解決哈希沖突的方法，哈希表的查找及其分析 八、排序 1、掌握排序的基本概念，理解排序“穩(wěn)定”和“不穩(wěn)定”的含義，

4、理解排序算法的評判標準；2、熟練掌握直接插入排序、希爾排序、直接選擇排序、堆排序、快速排序、二路歸并排序、基數排序的算法思想和算法設計方法；理解各種排序方法的性能特點并能靈活應用。計算機組成原理部分考試內容范圍：一、計算機系統概論 1.理解計算機系統的層次結構。2.掌握馮.諾依曼機的組成及特點。3.掌握計算機硬件的主要技術指標，如機器字長、存儲容量、CPU時鐘周期、主頻、CPI、CPU執(zhí)行時間、MIPS、MFLOPS等。二、系統總線 1.掌握總線定義、總線組成及性能指標；了解常用總線標準。2.掌握總線集中仲裁方式。三、存儲器 1.理解存儲器分類及層次結構（Cache-主存結構、主存-輔存結構）

5、。2.掌握主存儲器的設計及與CPU的連接方法。3.掌握Cache的基本工作原理、Cach和主存之間的映射方式；理解Cache替換算法。四、輸入輸出系統 1.掌握輸入輸出系統的基本結構和功能、I/O端口及其編址方式。2.掌握三種I/O方式：程序查詢方式、程序中斷方式（中斷的基本概念、中斷響應過程、中斷處理過程、多重中斷和中斷屏蔽的概念）、DMA方式（DMA傳送過程）。五、計算機中數的表示和運算方法 1.掌握數的表示方法：包括無符號數、有符號數（原碼、反碼、補碼、移碼）、定點數和浮點數的表示。2.掌握數的運算方法：包括移位運算、定點加減運算、浮點加減運算。3.理解算術邏輯單元ALU的功能和結構。六

6、、計算機指令系統 1.了解指令的基本格式，掌握定長操作碼指令格式。 2.掌握有效地址的概念、掌握指令尋址和數據尋址及常見數據尋址方式。3.了解CISC和RISC的基本概念。 七、CPU結構和功能 1.理解CPU的功能和基本結構。2.掌握指令執(zhí)行流程（按取指周期、間址周期、執(zhí)行周期分析指令的微操作及相關控制號）。3.掌握微程序控制器（微程序、微指令和微命令，微指令的編碼方式，微地址的形式方式）；了解硬布線控制器。考試總分：150分（數據結構75分 組成原理75分） 考試時間：3小時 考試形式：筆試考試題型：數據結構：選擇題、填空題、判斷題、計算題、算法題組成原理：選擇題（30分） 計算題、綜合題（45分）參考教材：1、嚴蔚敏，數據結構，