1、 PAGE PAGE 5一、考查目標821 數據結構考試大綱本操作的實現。掌握基本的數據處理原理和方法的基礎上，能夠對算法進行設計與分析。能夠選擇合適的數據結構和方法進行問題求解。二、考試形式和試卷結構試卷滿分及考試時間試卷滿分 150 分，考試時間 180 分鐘。答題方式答題方式為筆試、閉卷。試卷內容與題型結構單選題10 題每小題2 分共 20 分填空題10 題每小題2 分共 20 分簡答題5 題每小題5 分共 25 分綜合題3 題每小題15 分共 45 分算法題三、考查內容4 題每小題10 分共 40 分概念基本概念和術語數據數據結構抽象數據類型算法的描述和分析算法、算法的時間復雜度和空間

2、復雜度概念算法描述和算法分析的方法，對于一般算法能分析出時間復雜度線性表線性表的概念線性表的邏輯結構線性表的存儲結構：順序表，單鏈表，雙鏈表，循環鏈表線性表的實現順序存儲結構：查找、插入、刪除等主要操作及其平均時間性能分析鏈式存儲結構：查找、插入、刪除等主要操作及其平均時間性能分析棧、隊列棧和隊列的概念棧和隊列的邏輯結構棧和隊列的存儲結構：順序棧，循環隊列，鏈式棧，鏈式隊列棧和隊列的實現順序存儲結構：入棧、出棧、入隊、出隊等主要操作及其平均時間性能分析鏈式存儲結構：入棧、出棧、入隊、出隊等主要操作及其平均時間性能分析數組和廣義表數組和廣義表的概念數組和廣義表的邏輯結構數組的存儲結構：特殊矩陣壓

3、縮存儲、稀疏矩陣壓縮存儲（三元組表）廣義表的存儲結構：鏈式存儲數組和廣義表的實現數組順序存儲結構：一般數組順序存儲的地址計算方法廣義表鏈式存儲結構：非空廣義表的求表頭和表尾運算樹和二叉樹樹和二叉樹的概念樹和二叉樹的邏輯結構樹和二叉樹的存儲結構：樹的孩子兄弟二叉鏈表、二叉樹的二叉鏈表樹和二叉樹的遍歷：樹的三種遍歷、二叉樹的三種遍歷樹和二叉樹的轉換樹和二叉樹的實現二叉樹的遞歸遍歷Huffman樹Huffman編碼圖圖的概念圖的邏輯結構圖的存儲結構：鄰接矩陣、鄰接表圖的遍歷：深度優先搜索、廣度優先搜索圖的實現最小（代價） Kruskal方法最短路徑：Dijkstra 方法拓撲排序關鍵路徑查找查找的概

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

5、題已知一棵二叉樹的先序遍歷的結果是ABDECF，中序遍歷的結果是DEBAFC，請畫出這棵二叉樹，并寫出該二叉樹的后序遍歷結果。算法題分析下面算法功能，以及時間復雜度。#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的類型定義，并分別編寫隊列初始化、入隊、出隊算法。五、參考教材數據結構，嚴蔚敏編著，清華大學出版社數據結構，彭 波主編，北京郵電大學出版社QQ 552325756 821 數據結構初試