2018年中國農(nóng)業(yè)大學(xué)821數(shù)據(jù)結(jié)構(gòu)考試大綱

1、 PAGE PAGE 5一、考查目標(biāo)821 數(shù)據(jù)結(jié)構(gòu)考試大綱本操作的實(shí)現(xiàn)。掌握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠?qū)λ惴ㄟM(jìn)行設(shè)計(jì)與分析。能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進(jìn)行問題求解。二、考試形式和試卷結(jié)構(gòu)試卷滿分及考試時(shí)間試卷滿分 150 分，考試時(shí)間 180 分鐘。答題方式答題方式為筆試、閉卷。試卷內(nèi)容與題型結(jié)構(gòu)單選題10 題每小題2 分共 20 分填空題10 題每小題2 分共 20 分簡(jiǎn)答題5 題每小題5 分共 25 分綜合題3 題每小題15 分共 45 分算法題三、考查內(nèi)容4 題每小題10 分共 40 分概念基本概念和術(shù)語數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)抽象數(shù)據(jù)類型算法的描述和分析算法、算法的時(shí)間復(fù)雜度和空間

2、復(fù)雜度概念算法描述和算法分析的方法，對(duì)于一般算法能分析出時(shí)間復(fù)雜度線性表線性表的概念線性表的邏輯結(jié)構(gòu)線性表的存儲(chǔ)結(jié)構(gòu)：順序表，單鏈表，雙鏈表，循環(huán)鏈表線性表的實(shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu)：查找、插入、刪除等主要操作及其平均時(shí)間性能分析鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：查找、插入、刪除等主要操作及其平均時(shí)間性能分析棧、隊(duì)列棧和隊(duì)列的概念棧和隊(duì)列的邏輯結(jié)構(gòu)棧和隊(duì)列的存儲(chǔ)結(jié)構(gòu)：順序棧，循環(huán)隊(duì)列，鏈?zhǔn)綏?，鏈?zhǔn)疥?duì)列棧和隊(duì)列的實(shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu)：入棧、出棧、入隊(duì)、出隊(duì)等主要操作及其平均時(shí)間性能分析鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：入棧、出棧、入隊(duì)、出隊(duì)等主要操作及其平均時(shí)間性能分析數(shù)組和廣義表數(shù)組和廣義表的概念數(shù)組和廣義表的邏輯結(jié)構(gòu)數(shù)組的存儲(chǔ)結(jié)構(gòu)：特殊矩陣壓

3、縮存儲(chǔ)、稀疏矩陣壓縮存儲(chǔ)（三元組表）廣義表的存儲(chǔ)結(jié)構(gòu)：鏈?zhǔn)酱鎯?chǔ)數(shù)組和廣義表的實(shí)現(xiàn)數(shù)組順序存儲(chǔ)結(jié)構(gòu)：一般數(shù)組順序存儲(chǔ)的地址計(jì)算方法廣義表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：非空廣義表的求表頭和表尾運(yùn)算樹和二叉樹樹和二叉樹的概念樹和二叉樹的邏輯結(jié)構(gòu)樹和二叉樹的存儲(chǔ)結(jié)構(gòu)：樹的孩子兄弟二叉鏈表、二叉樹的二叉鏈表樹和二叉樹的遍歷：樹的三種遍歷、二叉樹的三種遍歷樹和二叉樹的轉(zhuǎn)換樹和二叉樹的實(shí)現(xiàn)二叉樹的遞歸遍歷Huffman樹Huffman編碼圖圖的概念圖的邏輯結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)：鄰接矩陣、鄰接表圖的遍歷：深度優(yōu)先搜索、廣度優(yōu)先搜索圖的實(shí)現(xiàn)最?。ù鷥r(jià)） Kruskal方法最短路徑：Dijkstra 方法拓?fù)渑判蜿P(guān)鍵路徑查找查找的概

4、念查找表、查找分類、查找結(jié)構(gòu)查找算法效率的評(píng)判標(biāo)準(zhǔn)：平均查找長(zhǎng)度靜態(tài)表及其查找順序查找折半查找動(dòng)態(tài)表及其查找二叉排序樹平衡二叉樹哈希表及其查找哈希函數(shù)處理沖突方法哈希查找各種查找算法的分析排序排序的概念排序方法穩(wěn)定性、排序分類排序算法效率的評(píng)判標(biāo)準(zhǔn)插入排序簡(jiǎn)單插入排序希爾排序交換排序冒泡排序快速排序選擇排序簡(jiǎn)單選擇排序堆排序歸并排序二路歸并排序分治歸并排序各種排序算法的比較四、題型舉例選擇題在單鏈表中成功查找一個(gè)元素的等概率下的平均搜索長(zhǎng)度是。A. n 2填空題B.n/2C.(n+1)/2D. n+1深度為5 的二叉樹至多有個(gè)結(jié)點(diǎn)。簡(jiǎn)答題請(qǐng)比較順序表和單鏈表在存儲(chǔ)空間和數(shù)據(jù)訪問方面的特點(diǎn)。綜合

5、題已知一棵二叉樹的先序遍歷的結(jié)果是ABDECF，中序遍歷的結(jié)果是DEBAFC，請(qǐng)畫出這棵二叉樹，并寫出該二叉樹的后序遍歷結(jié)果。算法題分析下面算法功能，以及時(shí)間復(fù)雜度。#define List_Size typedef structElemType elemList_Size; intlength; SqList;void ex(SqList la, SqList lb,SqList&lc)i=0;j=0;k=0;while(ila.length & jlb.length) if(la.elemi=lb.elemj)elselc.elemk+=lb.elemj+;while(ila.length)while(jlb.length) / ex的類型定義，并分別編寫隊(duì)列初始化、入隊(duì)、出隊(duì)算法。五、參考教材數(shù)據(jù)結(jié)構(gòu)，嚴(yán)蔚敏編著，清華大學(xué)出版社數(shù)據(jù)結(jié)構(gòu)，彭 波主編，北京郵電大學(xué)出版社QQ 552325756 821 數(shù)據(jù)結(jié)構(gòu)初試