909數(shù)據(jù)結(jié)構(gòu)考試大綱

832-計算機綜合計算機綜合包括數(shù)據(jù)結(jié)構(gòu)、計算機組成原理兩部分內(nèi)容，每部分內(nèi)容各占1/2。I數(shù)據(jù)結(jié)構(gòu)考試基本要求要求考生系統(tǒng)地理解線性結(jié)構(gòu)（線性表、數(shù)組和矩陣、棧、隊列、跳表和散列表）、樹型結(jié)構(gòu)（森林（樹）、二叉樹、優(yōu)先隊列、搜索樹）、圖結(jié)構(gòu)等各種主要數(shù)據(jù)結(jié)構(gòu)的基本概念，掌握各種數(shù)據(jù)結(jié)構(gòu)的定義、實現(xiàn)算法和應(yīng)用；掌握基本算法設(shè)計方法（遞歸、貪婪算法、分而治之、動態(tài)規(guī)劃）及應(yīng)用；掌握程序性能分析方法。要求考生具有抽象思維能力，邏輯推理能力，和綜合運用所學(xué)的知識分析問題和解決問題的能力?？荚嚪秶A(yù)備知識1.C++基本語法結(jié)構(gòu)和應(yīng)用2.遞歸思想和方法程序性能分析1.復(fù)雜性（時間復(fù)雜性和空間復(fù)雜性）的表示和計算方法2.插入排序、選擇排序、冒泡排序、按名次排序方法3.順序搜索、折半搜索方法線性表1.線性表的數(shù)組描述、鏈表描述等存儲方法2.線性表的插入、刪除、合并等基本操作實現(xiàn)方法3.遍歷器的作用、實現(xiàn)方法和應(yīng)用4.線性表結(jié)構(gòu)應(yīng)用：箱子排序、基數(shù)排序、并查集（在線等價類）等數(shù)組和矩陣1.一般矩陣存儲方法和基本運算實現(xiàn)2.特殊矩陣的特征、存儲方法和基本運算實現(xiàn)3.稀疏矩陣的存儲方法和基本運算實現(xiàn)棧1.棧的基本概念、基本操作和實現(xiàn)方法2.棧結(jié)構(gòu)應(yīng)用：括號匹配、列車車廂重排、迷宮老鼠、離線等價類等隊列1.隊列的基本概念、基本操作和實現(xiàn)方法2.隊列結(jié)構(gòu)應(yīng)用：列車車廂重排、電路布線、圖元識別等跳表和散列1.字典結(jié)構(gòu)基本概念和表示結(jié)構(gòu)2.跳表的基本概念、基本操作和實現(xiàn)方法3.散列表的基本概念、基本操作和實現(xiàn)方法4.LZW壓縮思想二叉樹和其他樹1.樹（以及森林）和二叉樹的基本概念、存儲方法、常用操作和特性2.二叉樹的前序、中序、后序、層次遍歷方法及應(yīng)用3.樹（以及森林）的存儲方法4.樹和二叉樹結(jié)構(gòu)的應(yīng)用：基于樹存儲的并查集（在線等價類）等優(yōu)先隊列1.優(yōu)先隊列基本概念和表示結(jié)構(gòu)2.堆結(jié)構(gòu)基本概念，堆的插入、刪除和初始化等操作實現(xiàn)方法3.堆結(jié)構(gòu)應(yīng)用：堆排序、霍夫曼樹、霍夫曼編碼4.左高樹基本概念和插入、刪除、合并、初始化等操作的實現(xiàn)思想搜索樹1.二叉搜索樹(排序樹)基本概念和插入、刪除、搜索等操作的實現(xiàn)方法2.二叉平衡樹（AVL樹）基本概念和插入、刪除、搜索等操作的實現(xiàn)方法3.m叉搜索樹和B-樹基本概念以及插入、刪除、搜索等操作的實現(xiàn)方法圖1.圖基本概念和特性2.圖的鄰接矩陣和鄰接鏈表存儲方法及各種基本操作和實現(xiàn)方法3.圖的深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）算法4.DFS/BFS應(yīng)用：尋找路徑、連通圖及連通構(gòu)件、生成樹等貪婪算法1.貪婪算法基本思想2.AOV網(wǎng)的拓撲排序算法3.單源最短路徑Dijkstra算法4.最小成本生成樹的概念、Prim算法和Kruskal算法5.AOE網(wǎng)的關(guān)鍵路徑算法分而治之1.分而治之思想2.歸并排序、快速排序方法3.選擇問題實現(xiàn)方法動態(tài)規(guī)劃1.動態(tài)規(guī)劃思想2.所有頂點對之間的最短路徑算法參考文獻《數(shù)據(jù)結(jié)構(gòu)，算法與應(yīng)用----C++語言描述》（原書第2版），SartajSahni著王立柱，劉志紅譯，機械工業(yè)出版社2015年出版《數(shù)據(jù)結(jié)構(gòu)》（用面向?qū)ο蠓椒ㄅcC++語言描述第二版）

殷人昆著清華大學(xué)出版社II計算機組成原理課程基本要求理解單處理器計算機系統(tǒng)中各部件的內(nèi)部工作原理、組成結(jié)構(gòu)以及相互連接方式，具有完整的計算機系統(tǒng)的整機概念；理解計算機系統(tǒng)層次化結(jié)構(gòu)概念，熟悉硬件與軟件之間的界面，掌握指令集體系結(jié)構(gòu)的基本知識和基本實現(xiàn)方法；能夠綜合運用計算機組成的基本原理和基本方法，對有關(guān)計算機硬件系統(tǒng)中的理論和實際問題進行計算、分析，對一些基本部件進行簡單設(shè)計，并能對高級程序設(shè)計語言(如C語言)中的相關(guān)問題進行分析。考試范圍計算機系統(tǒng)概述計算機發(fā)展歷程計算機系統(tǒng)層次結(jié)構(gòu)計算機系統(tǒng)的基本組成計算機硬件的基本組成計算機軟件的分類計算機的工作過程計算機性能指標CPU時鐘周期、主頻、CPI、CPU執(zhí)行時間、MIPS、MFLOPS字長容量總線寬度數(shù)據(jù)的表示和運算數(shù)制與編碼進位計數(shù)制及其相互轉(zhuǎn)換真值和機器數(shù)BCD碼字符與字符串校驗碼定點數(shù)的表示和運算定點數(shù)的表示無符號數(shù)的表示及范圍；有符號數(shù)的表示及其相互轉(zhuǎn)換。定點數(shù)的運算定點數(shù)的移位運算；補碼定點數(shù)的加/減運算；定點數(shù)的乘/除運算；溢出概念和判別方法。浮點數(shù)的表示和運算浮點數(shù)的表示浮點數(shù)的表示范圍；浮點機器數(shù)與真值間的相互轉(zhuǎn)換。浮點數(shù)的加/減運算算術(shù)邏輯單元ALU并行加法器算術(shù)邏輯單元ALU的功能和結(jié)構(gòu)快速進位鏈設(shè)計原理存儲器層次機構(gòu)存儲器的分類存儲器的層次化結(jié)構(gòu)半導(dǎo)體隨機存取存儲器SRAM存儲器的工作原理DRAM存儲器的工作原理；刷新方式。只讀存儲器、Flash存儲器主存儲器的基本組成、存儲單元的屬性、數(shù)據(jù)的存放模式存儲器的技術(shù)指標存儲器的擴展方式及存儲器與CPU的連接多體并行存儲器系統(tǒng)高速緩沖存儲器（Cache）Cache的基本工作原理Cache和主存之間的映射方式及其地址轉(zhuǎn)換Cache中主存塊的替換算法Cache讀、寫策略指令系統(tǒng)指令格式指令的基本格式定長操作碼指令格式擴展操作碼指令格式指令的尋址方式有效地址的概念數(shù)據(jù)尋址和指令尋址常見尋址方式CISC和RISC的基本概念中央處理器（CPU）CPU的功能和基本結(jié)構(gòu)指令執(zhí)行過程數(shù)據(jù)通路的功能和基本結(jié)構(gòu)基于數(shù)據(jù)通路，指令周期流程及取指、間址、執(zhí)行和中斷周期的數(shù)據(jù)流?？刂破鞯墓δ芎凸ぷ髟砦⒉僮髅畹姆治鋈≈钢芷凇㈤g址周期、執(zhí)行周期和中斷周期的微操作命令及其節(jié)拍安排。組合邏輯（硬布線）控制器組合邏輯控制器的組成結(jié)構(gòu)、設(shè)計步驟。微程序控制器微程序、微指令、微命令、微操作、控制存儲器的基本概念；微程序控制器的設(shè)計思想、組成結(jié)構(gòu)、工作原理；微指令的編碼方式；微地址的形式方式。指令流水線指令流水線的基本概念指令流水線的基本實現(xiàn)影響指令流水線性能的因素：結(jié)構(gòu)相關(guān)、數(shù)據(jù)相關(guān)、控制相關(guān)；流水線的主要性能：吞吐率、加速比、效率。流水線的多發(fā)技術(shù)超標量處理機、超流水線處理機、超長指令字處理機的基本概念?？偩€總線概述總線的基本概念總線的分類總線的組成及性能指標總線仲裁集中仲裁方式分布仲裁方式總線操作和定時同步定時方式異步定時方式總線標準輸入輸出（I/O）系統(tǒng)I/O系統(tǒng)基本概念I(lǐng)/O接口（I/O控制器）I/O接口的功能和基本結(jié)構(gòu)I/O端口及其編址I/O方式程序查詢方式程序中斷方式中斷的基本概念；中斷響應(yīng)過程；中斷處理過程；多重中斷和中斷屏蔽的概念；中斷處理順序