1、數(shù)據(jù)結(jié)構(gòu)梁春燕華電信息管理教研室主要內(nèi)容復(fù)習(xí)串講題目講解關(guān)于考試復(fù)習(xí)串講第一章 緒論數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ)：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型抽象數(shù)據(jù)結(jié)構(gòu)類型ADT的表示與實(shí)現(xiàn)算法和算法分析：特性、評(píng)價(jià)方法（時(shí)間空間復(fù)雜度）數(shù)據(jù)結(jié)構(gòu)是什么？其研究的主要內(nèi)容？類型？算法的評(píng)價(jià)？數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等的學(xué)科。數(shù)據(jù)結(jié)構(gòu)（Data Structure）：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。 數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等 線性結(jié)構(gòu) 非線性結(jié)構(gòu) 順序存儲(chǔ) 鏈?zhǔn)酱鎯?chǔ) 線性表?xiàng)ｊ?duì)列樹形

2、結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面：復(fù)習(xí)串講第二章 線性表線性表的邏輯結(jié)構(gòu) ：一對(duì)一線性表的順序存儲(chǔ)結(jié)構(gòu)（順序表）：存儲(chǔ)方式、特點(diǎn)、基本操作線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：存儲(chǔ)方式、特點(diǎn)、基本操作單鏈表（靜態(tài)鏈表）循環(huán)鏈表雙向鏈表線性表的應(yīng)用舉例一元多項(xiàng)式的表示及相加（單鏈表）約瑟夫問題（循環(huán)鏈表）順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的優(yōu)缺點(diǎn)？順序存儲(chǔ)結(jié)構(gòu)優(yōu)點(diǎn) 邏輯相鄰，物理相鄰 可隨機(jī)存取任一元素 存儲(chǔ)空間使用緊湊缺點(diǎn) 插入、刪除操作需要移動(dòng)大量的元素 預(yù)先分配空間需按最大空間分配，利用不充分 表容量難以擴(kuò)充鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)點(diǎn) 動(dòng)態(tài)結(jié)構(gòu)，整個(gè)存儲(chǔ)空間為多個(gè)鏈表共用，節(jié)省空間 不需預(yù)先分配空間，易擴(kuò)充 插入、刪除操作方便缺點(diǎn)

3、指針占用額外存儲(chǔ)空間 不能隨機(jī)存取，查找速度慢測(cè)試程序填空：1. 雙向鏈表結(jié)點(diǎn)的刪除void del_dulist(JD *p) p-prior-next=p-next; p-next-prior=p-prior; free(p);bcaPp-prior-next=p-next;p-next-prior=p-prior;復(fù)習(xí)串講第三章 棧和隊(duì)列棧的邏輯結(jié)構(gòu) 、順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本操作順序棧：?？铡M鏈?zhǔn)綏＃簵？贞?duì)列的邏輯結(jié)構(gòu) 、順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本操作循環(huán)隊(duì)列：隊(duì)空、隊(duì)滿鏈?zhǔn)疥?duì)列：隊(duì)空棧和隊(duì)列的應(yīng)用數(shù)制轉(zhuǎn)換、表達(dá)式計(jì)算、漢諾塔問題（棧）舞伴問題（隊(duì)列）棧和隊(duì)列的異

4、同？相同點(diǎn) 棧和隊(duì)列都是特殊的線性表，是操作受限的線性表，稱限定性DS不同點(diǎn) 棧 限定僅在表尾（棧頂）進(jìn)行插入或刪除操作的線性表 特點(diǎn)：先進(jìn)后出（FILO）或后進(jìn)先出（LIFO） 進(jìn)棧、退棧操作隊(duì) 列 限定只能在表的一端（隊(duì)尾）進(jìn)行插入，在表的另一端（隊(duì)頭）進(jìn)行刪除的線性表 特點(diǎn)：先進(jìn)先出(FIFO) 進(jìn)隊(duì)、出隊(duì)操作測(cè)試2. 循環(huán)隊(duì)列的出隊(duì)DataType deQueue(CirQueue *Q) DataType temp; if(queueEmpty(Q) Error(“隊(duì)空n”); temp = Q-dataQ-front; Q-count-; Q-front = (Q-front+1)

5、%QueueSize; return temp;J4J5J6012345rearfront復(fù)習(xí)串講第四章 串串及其運(yùn)算數(shù)據(jù)元素約束為字符集的線性表基本操作：以串的整體作為操作對(duì)象，“子串”的操作串的長(zhǎng)度 、串復(fù)制 、聯(lián)接、串比較、求子串 串的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)：定長(zhǎng)順序存儲(chǔ)、堆分配存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)：塊鏈存儲(chǔ)串的模式匹配算法簡(jiǎn)單匹配KMP算法串的存儲(chǔ)方式的比較？ 定長(zhǎng)順序存儲(chǔ) 順序存儲(chǔ)、串的長(zhǎng)度固定 串的插入、聯(lián)結(jié)：串的截?cái)?串的插入、刪除：移動(dòng)元素 串的查找、定位：方便 堆分配存儲(chǔ) 順序存儲(chǔ)、串的長(zhǎng)度可變 串的插入、刪除：移動(dòng)元素 串的聯(lián)結(jié)、查找、定位：方便 串的塊鏈存儲(chǔ) 鏈?zhǔn)酱鎯?chǔ)、串的長(zhǎng)度可變 占

6、用空間大、操作復(fù)雜復(fù)習(xí)串講第五章 數(shù)組和廣義表數(shù)組的定義和特點(diǎn)特殊的線性表，即線性表中數(shù)據(jù)元素本身也是一個(gè)線性表數(shù)組的順序存儲(chǔ)：行序、列序數(shù)組的壓縮存儲(chǔ)：對(duì)稱矩陣、三角矩陣、對(duì)角矩陣、稀疏矩陣數(shù)組的鏈?zhǔn)酱鎯?chǔ)：帶行指針向量的單鏈表、十字鏈表廣義表的概念和表示稀疏矩陣的存儲(chǔ)方式？稀疏矩陣（m行n列，t個(gè)非零元素，tm*n） 順序存儲(chǔ)方法：m*n 壓縮存儲(chǔ)方法 順序存儲(chǔ)結(jié)構(gòu) 三元組表：3(t+1) 帶輔助行向量的二元組表： 2(t+1)+m+1 偽地址表示法：2(t+1) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 帶行指針向量的單鏈表表示：3t+m 十字鏈表：5t+m+n復(fù)習(xí)串講第六章 樹和二叉樹二叉樹二叉樹的特點(diǎn)和性質(zhì)二叉樹

7、的存儲(chǔ)結(jié)構(gòu)：順序、鏈?zhǔn)剑ǘ?、三叉、線索）二叉樹的遍歷：先序、中序、后序、層次二叉樹的線索化樹樹的存儲(chǔ)結(jié)構(gòu)：雙親、孩子、孩子兄弟表示方法樹與二叉樹轉(zhuǎn)換森林與二叉樹轉(zhuǎn)換樹和森林的遍歷（與對(duì)應(yīng)二叉樹的遍歷的關(guān)系）Huffman樹Huffman樹的建立：Huffman算法Huffman樹的應(yīng)用：Huffman編碼樹和二叉樹的遍歷算法的應(yīng)用復(fù)習(xí)串講第七章 圖圖的定義和術(shù)語(yǔ)圖的存儲(chǔ)結(jié)構(gòu)：鄰接矩陣、鄰接表、有向圖的十字鏈表、無(wú)向圖的鄰接多重表圖的遍歷：深度優(yōu)先、寬度優(yōu)先生成樹和最小生成樹：普里姆Prim算法、克魯斯卡爾Kruskal算法圖的應(yīng)用：拓?fù)渑判颍ˋOV網(wǎng)）有向無(wú)環(huán)圖關(guān)鍵路徑（AOE網(wǎng)）帶權(quán)的有向

8、無(wú)環(huán)圖最短路徑：迪杰斯特拉Dijkstra算法、弗洛伊德Floyd算法帶權(quán)的有向圖復(fù)習(xí)串講第八章 查找靜態(tài)查找表順序查找折半查找分塊查找動(dòng)態(tài)查找表二叉排序樹和平衡二叉樹B-樹和B+樹哈希查找基本概念哈希函數(shù)的構(gòu)造：直接定址法、數(shù)字分析法、平方取中法、折疊法、除留余數(shù)法沖突處理方法：開放地址法（線性、二次、偽隨機(jī)）、再哈希法、鏈地址法哈希表的查找復(fù)習(xí)串講第九章 排序排序的基本概念：排序的分類和基本操作插入排序：直接插入、折半插入和希爾排序交換排序：冒泡、快速排序選擇排序：簡(jiǎn)單選擇、堆排序歸并排序： 2-路歸并排序基數(shù)排序：鏈?zhǔn)交鶖?shù)排序不同排序方法的比較？排序方法平均時(shí)間輔助空間穩(wěn)定性直接插入O(n2)O(1)穩(wěn)定冒泡O(n2)O(1)穩(wěn)定直接選擇O(n2)O(1)穩(wěn)定希爾O(n1.23)O(1)不穩(wěn)定快速O(nlog n)O(log n)不穩(wěn)定堆O(nlog n)O(1)不穩(wěn)定歸并O(nlog n)O(n)穩(wěn)定基數(shù)O(d*n+d*rd)O(n+rd)穩(wěn)定題目講解二叉樹的存儲(chǔ)、遍歷樹、森林和二叉樹的轉(zhuǎn)換及其遍歷圖的存儲(chǔ)結(jié)構(gòu)和遍歷Huffman樹的建立和Huffman編碼哈