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

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

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