電子科技大學(xué)《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)提要_電子科大考研網(wǎng)

1、 電子科技大學(xué)數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)提要一、總體要求數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)程序設(shè)計(jì)的重要理論技術(shù)基礎(chǔ),是計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科的核心課程。要求:1.理解數(shù)據(jù)結(jié)構(gòu)的基本概念;掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其差異,以及各種基本操作的實(shí)現(xiàn)。2.掌握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上,能夠分析算法的時(shí)間復(fù)雜度與空間復(fù)雜度。3.能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和算法策略進(jìn)行問題求解,具備采用C 或C+或JAVA 語言設(shè)計(jì)與實(shí)現(xiàn)算法的能力。二、內(nèi)容1. 數(shù)據(jù)結(jié)構(gòu)及算法的相關(guān)概念和術(shù)語(1數(shù)據(jù)結(jié)構(gòu)及算法的概念;(2數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu);(3算法的定義及特性;(4算法時(shí)間復(fù)雜度和空間復(fù)雜度的分析方法。2.線性表(1線性表的定義(2線性

2、表的基本操作及在順序存儲(chǔ)及鏈?zhǔn)酱鎯?chǔ)上的實(shí)現(xiàn);(3各種變形鏈表(循環(huán)鏈表、雙向鏈表、帶頭結(jié)點(diǎn)的鏈表等的表示和基本操作的實(shí)現(xiàn);(4遞歸過程的特點(diǎn)及實(shí)現(xiàn)方法;(5棧和隊(duì)列的基本概念;棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)絻?chǔ)存結(jié)構(gòu)及其存儲(chǔ)特點(diǎn);(6棧和隊(duì)列的應(yīng)用(7循環(huán)隊(duì)列的判滿、判空方法;(8特殊矩陣的壓縮儲(chǔ)存;3.廣義表的基本概念、存儲(chǔ)結(jié)構(gòu)和基本操作4.樹和二叉樹(1樹與森林的基本概念(2樹與森林的存儲(chǔ)結(jié)構(gòu)及遍歷(3二叉樹的定義及6大性質(zhì)(4二叉樹的順序儲(chǔ)存與鏈?zhǔn)絻?chǔ)存結(jié)構(gòu)(5二叉樹的先序、中序、后序三種遍歷方式的關(guān)系以及實(shí)現(xiàn);層序遍歷的實(shí)現(xiàn)(6線索二叉樹的基本概念與構(gòu)造方法(7樹與二叉樹的應(yīng)用:二叉排序樹;

3、二叉平衡樹;哈夫曼樹與哈夫曼編碼5.圖 (1圖的基本概念和術(shù)語;(2圖的存儲(chǔ)結(jié)構(gòu):鄰接矩陣、鄰接表、逆鄰接表;(3遍歷算法:深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法;(4應(yīng)用:最小生成樹;最短路徑,拓?fù)渑判蚝完P(guān)鍵路徑。6.查找(1查找的基本概念;靜態(tài)查找與動(dòng)態(tài)查找;(2順序查找、折半查找、索引查找(3哈希查找哈希函數(shù)的基本構(gòu)造方法,解決地址沖突的基本策略;(4各種查找算法的時(shí)間復(fù)雜度和空間復(fù)雜度。7.排序(1排序的基本概念(2插入排序(3簡(jiǎn)單選擇排序(4希爾排序(5快速排序(6堆排序(7歸并排序(8基數(shù)排序(9排序算法的比較。三、題型及分值比例1. 填空題(10分2. 單選題(20分3. 簡(jiǎn)答題(30分4. 算法題(15分其中算法題分為閱讀、修改和編寫算法三類:(1閱讀算法:閱讀指定算法,回答使用的數(shù)據(jù)結(jié)構(gòu)、算法實(shí)現(xiàn)的功能或執(zhí)行的結(jié)果;(2修改算法:閱讀指定算法,指出算法的錯(cuò)誤并修正;指出算法的不足并改進(jìn);按給定功能填寫算法空缺部分;(3編寫算法:根據(jù)算法功能要求,選擇或者設(shè)計(jì)合適的數(shù)據(jù)結(jié)構(gòu),用程序設(shè)計(jì)語言編寫算法,實(shí)現(xiàn)指定功能