2017年考試內(nèi)容范圍說(shuō)明

1、2017年考試內(nèi)容范圍說(shuō)明考試科目代碼：847 考試科目名稱：計(jì)算機(jī)學(xué)科專業(yè)綜合數(shù)據(jù)結(jié)構(gòu)部分一、緒論 1、理解數(shù)據(jù)結(jié)構(gòu)的基本概念；了解數(shù)據(jù)類型和抽象數(shù)據(jù)類型的概念；2、理解算法的設(shè)計(jì)目標(biāo)；掌握算法的時(shí)間、空間復(fù)雜度概念以及時(shí)間、空間復(fù)雜度的分析方法。 二、線性表 1、理解線性表的邏輯結(jié)構(gòu)和基本操作；2、熟練掌握線性表的順序存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)方法；3、熟練掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和實(shí)現(xiàn)方法；4、理解單循環(huán)鏈表和雙向鏈表的概念和基本設(shè)計(jì)方法。 三、棧和隊(duì)列 1、熟練掌握棧的概念、順序棧和鏈?zhǔn)綏５脑O(shè)計(jì)方法及應(yīng)用方法; 2、熟練掌握隊(duì)列的概念、順序循環(huán)隊(duì)列和鏈?zhǔn)疥?duì)列的設(shè)計(jì)方法及應(yīng)用方法3、理解遞歸算法的思

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

3、概念和術(shù)語(yǔ)；熟練掌握?qǐng)D的鄰接矩陣和鄰接表存儲(chǔ)結(jié)構(gòu)以及圖基本操作的實(shí)現(xiàn)方法；2、熟練掌握?qǐng)D的深度和廣度遍歷方法和算法設(shè)計(jì)方法；3、理解最小生成樹(shù)的概念，熟練掌握普里姆算法和克魯斯卡爾算法并掌握其生成方法；4、掌握單源點(diǎn)最短路徑的算法，拓?fù)渑判蚍椒ǎ斫怅P(guān)鍵路徑的概念。 七、查找 1、掌握查找的基本概念和查找方法的評(píng)判標(biāo)準(zhǔn)；2、熟練掌握順序查找和有序查找的算法設(shè)計(jì)方法，理解索引查找的基本結(jié)構(gòu)；3、理解二叉排序樹(shù)的特點(diǎn)；掌握二叉排序樹(shù)的構(gòu)造和查找方法4、熟練掌握哈希函數(shù)、哈希表的構(gòu)造方法，解決哈希沖突的方法，哈希表的查找及其分析 八、排序 1、掌握排序的基本概念，理解排序“穩(wěn)定”和“不穩(wěn)定”的含義，

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

5、。2.掌握主存儲(chǔ)器的設(shè)計(jì)及與CPU的連接方法。3.掌握Cache的基本工作原理、Cach和主存之間的映射方式；理解Cache替換算法。四、輸入輸出系統(tǒng) 1.掌握輸入輸出系統(tǒng)的基本結(jié)構(gòu)和功能、I/O端口及其編址方式。2.掌握三種I/O方式：程序查詢方式、程序中斷方式（中斷的基本概念、中斷響應(yīng)過(guò)程、中斷處理過(guò)程、多重中斷和中斷屏蔽的概念）、DMA方式（DMA傳送過(guò)程）。五、計(jì)算機(jī)中數(shù)的表示和運(yùn)算方法 1.掌握數(shù)的表示方法：包括無(wú)符號(hào)數(shù)、有符號(hào)數(shù)（原碼、反碼、補(bǔ)碼、移碼）、定點(diǎn)數(shù)和浮點(diǎn)數(shù)的表示。2.掌握數(shù)的運(yùn)算方法：包括移位運(yùn)算、定點(diǎn)加減運(yùn)算、浮點(diǎn)加減運(yùn)算。3.理解算術(shù)邏輯單元ALU的功能和結(jié)構(gòu)。六

6、、計(jì)算機(jī)指令系統(tǒng) 1.了解指令的基本格式，掌握定長(zhǎng)操作碼指令格式。 2.掌握有效地址的概念、掌握指令尋址和數(shù)據(jù)尋址及常見(jiàn)數(shù)據(jù)尋址方式。3.了解CISC和RISC的基本概念。 七、CPU結(jié)構(gòu)和功能 1.理解CPU的功能和基本結(jié)構(gòu)。2.掌握指令執(zhí)行流程（按取指周期、間址周期、執(zhí)行周期分析指令的微操作及相關(guān)控制號(hào)）。3.掌握微程序控制器（微程序、微指令和微命令，微指令的編碼方式，微地址的形式方式）；了解硬布線控制器?？荚嚳偡郑?50分（數(shù)據(jù)結(jié)構(gòu)75分 組成原理75分） 考試時(shí)間：3小時(shí) 考試形式：筆試考試題型：數(shù)據(jù)結(jié)構(gòu)：選擇題、填空題、判斷題、計(jì)算題、算法題組成原理：選擇題（30分） 計(jì)算題、綜合題（45分）參考教材：1、嚴(yán)蔚敏，數(shù)據(jù)結(jié)構(gòu)，