數(shù)據(jù)結(jié)構(gòu)參與命題課件復(fù)習(xí)課

1、題型填空題 每題3分，共10題簡(jiǎn)答題 每題8分，共6題算法題 共22分，共2題第1章 緒論數(shù)據(jù)結(jié)構(gòu)的定義按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)（或稱帶結(jié)構(gòu)的數(shù)據(jù)元素的集合）應(yīng)用計(jì)算機(jī)語(yǔ)言并按一定的表示 方式把它們?cè)谟?jì)算機(jī)的存儲(chǔ)器中，并在其上定義了一個(gè)運(yùn)算的集合。具體來說，數(shù)據(jù)結(jié)構(gòu)包含三個(gè)方面的內(nèi)容，即數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存貯結(jié)構(gòu)和對(duì)數(shù)據(jù)所施加的運(yùn)算（操作）。數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面研究?jī)?nèi)容：?jiǎn)栴}數(shù)學(xué)模型實(shí)現(xiàn)建模求精線性表?xiàng)ｊ?duì)列串及數(shù)組樹形結(jié)構(gòu)圖形結(jié)構(gòu)線性結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)（面向應(yīng)用）非線性結(jié)構(gòu)順序鏈?zhǔn)剿饕⒘袛?shù)據(jù)的（面向結(jié)構(gòu)）數(shù)據(jù)的運(yùn)算（操作）：檢索、排序、刪除、修改等結(jié)構(gòu)實(shí)現(xiàn)邏輯結(jié)構(gòu)基本運(yùn)算機(jī)外表示處

2、理要求算法與數(shù)據(jù)結(jié)構(gòu)算法與數(shù)據(jù)結(jié)構(gòu)關(guān)系密切選擇的數(shù)據(jù)結(jié)構(gòu)是否恰當(dāng)直接影響算法的效 率；而數(shù)據(jù)結(jié)構(gòu)的優(yōu)劣由算法的執(zhí)行來體現(xiàn)。N.Wirth計(jì)算機(jī)科學(xué)家“算法+數(shù)據(jù)結(jié)構(gòu)=程序”算法程序算法是供人閱讀的程序是讓機(jī)器執(zhí)行的算法用計(jì)算機(jī)語(yǔ)言實(shí)現(xiàn)時(shí)就是程序程序不具有算法的有窮性算法效率的衡量方法和準(zhǔn)則一個(gè)算法的評(píng)價(jià)主要從時(shí)間復(fù)雜度和空間復(fù)雜度來考慮。時(shí)間復(fù)雜度T(n)為語(yǔ)句執(zhí)行的次數(shù)稱為頻度lim T(n) C(C 0)f (n)nO（f（n）稱為時(shí)間復(fù)雜度例如，若T(n)=n(n+1)/2,則有 1/4T(n)/n21，故它的時(shí)間復(fù)雜度為(n2), 即(n)與n2 數(shù)量級(jí)相同?？臻g復(fù)雜度第2章 線性表線

3、性結(jié)構(gòu)的特點(diǎn)：在數(shù)據(jù)元素的非空有限集中，有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)只有一個(gè)直接前趨和一個(gè)直接后繼。簡(jiǎn)言之，線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是 一對(duì)一。線性結(jié)構(gòu)包括線性表、堆棧、隊(duì)列、字符串、數(shù)組等等，其中，最簡(jiǎn) 單、最常用的是線性表。線性表的定義及特點(diǎn)線性表的順序鏈?zhǔn)椒椒ǎ哼壿嬌舷噜徫锢砩弦欢ㄏ噜彛哼壿嬌舷噜徫锢砩喜灰欢ㄏ噜忢樞虮眄樞虮砭€性表的順序表示用一組地址連續(xù)的順序單元依次線性表的元素，可通過數(shù)組來實(shí)現(xiàn)。（邏輯上相鄰物理上一定相鄰）LOC(ai ) = LOC(a1) + (i - 1) l （a1為首元素）順序的優(yōu)點(diǎn)可以隨機(jī)存取表中任一元素O(1)；空間使用緊湊順序的

4、缺點(diǎn)：元素時(shí)平均需要移動(dòng)n/2個(gè)元素，刪除某一元素在時(shí)，平均需要移動(dòng)n-1/2個(gè)元素。算法的平均時(shí)間復(fù)雜度為 O(n)預(yù)先分配空間需按最大空間分配，利用不充分;表容量難以擴(kuò)充鏈表線性表的鏈?zhǔn)芥準(zhǔn)浇Y(jié)構(gòu)特點(diǎn)用一組任意的單元線性表的數(shù)據(jù)元素單元存放邏輯上相鄰的元素利用指針實(shí)現(xiàn)了用不相鄰的每個(gè)數(shù)據(jù)元素ai，除信息本身信息外，還需其直接后繼的鏈?zhǔn)浇Y(jié)構(gòu)的優(yōu)點(diǎn)：結(jié)點(diǎn)空間可以動(dòng)態(tài)申請(qǐng)和；數(shù)據(jù)元素的邏輯次序靠結(jié)點(diǎn)的指針來指示，需要移動(dòng)數(shù)據(jù)元素。和刪除時(shí)不鏈?zhǔn)浇Y(jié)構(gòu)的缺點(diǎn)：每個(gè)結(jié)點(diǎn)的指針域需額外占用空間。當(dāng)數(shù)據(jù)域所占字節(jié)顯得很大。不多時(shí)，指針域所占空間的鏈表是非隨機(jī)存取結(jié)構(gòu)。對(duì)任一結(jié)點(diǎn)的操作都要從頭指針依鏈查找該結(jié)

5、點(diǎn)，這增加了算法的復(fù)雜度。不便于在表尾元素：需遍歷整個(gè)表才能找到位置。第3章 排序簡(jiǎn)單排序方法（O(n2)）排序（穩(wěn)定排序）直接選擇排序（不穩(wěn)定排序）冒泡排序（不穩(wěn)定排序）先進(jìn)排序方法（ O(nlogn)快速排序（不穩(wěn)定排序）歸并排序（穩(wěn)定排序）堆排序（不穩(wěn)定排序）已知一組關(guān)鍵字29, 18, 23, 1, 68, 41, 8,65，請(qǐng)分別寫出按排序、冒泡排序、直接選擇排序和快速排序方法排序過程，每一趟排序結(jié)束時(shí)的關(guān)鍵字的狀態(tài)。一、時(shí)間性能各種排序方法的綜合比較1.按平均時(shí)間性能來分，有三類排序方法：時(shí)間復(fù)雜度為 O(nlogn)：快速排序、堆排序和歸并排序，其中以快速排序?yàn)樽詈?。時(shí)間復(fù)雜度為

6、 O(n2)：直接排序、起泡排序和簡(jiǎn)單選擇排序，其中以直接為最好，特別是對(duì)那些對(duì)關(guān)鍵字基本有序的時(shí)間復(fù)雜度為 O(n*d)：基數(shù)排序。序列尤為如此。2. 當(dāng)待排序列按關(guān)鍵字順序有序時(shí)，改進(jìn)直接排序、冒泡排序以及簡(jiǎn)單選擇排序能達(dá)到 O(n) 的時(shí)間復(fù)雜度，快速排序的時(shí)間性能蛻化為 O(n2) 。3. 堆排序和歸并排序的時(shí)間性能不隨變。序列中關(guān)鍵字的分布而改二、空間性能指的是排序過所需的輔助空間大小。1.所有的簡(jiǎn)單排序方法(包括：直接堆排序的空間復(fù)雜度為 O(1)；、冒泡和簡(jiǎn)單選擇) 和2.快速排序?yàn)?O(logn)，為遞歸程序執(zhí)行過空間；歸并排序所需輔助空間最多，其空間復(fù)雜度為 O(n)；鏈?zhǔn)交?/p>

7、數(shù)排序需附設(shè)隊(duì)列首尾指針，則空間復(fù)雜度為 O(2*rd+n)，棧所需的輔助3.4.三、排序方法的穩(wěn)定性能1.對(duì)于不穩(wěn)定的排序方法，只要能舉出一個(gè)實(shí)例說明即可。2.快速排序、堆排序是不穩(wěn)定的排序方法。各種排序方法的比較排序方法平均時(shí)間情況最好情況輔助穩(wěn)定性排序O(n2)O(n2)O(n)O(1）穩(wěn)定選擇排序O(n2)O(n2)O(n)O(1）穩(wěn)定冒泡排序O(n2)O(n2)O(n)O(1）穩(wěn)定快速排序O(nlgn)O(n2)O(nlgn )O(lgn)不穩(wěn)定歸并排序O(nlgn )O(nlgn)O(nlgn )O(n）穩(wěn)定堆排序O(nlgn )O(nlgn)O(nlgn )O(1）不穩(wěn)定基數(shù)排序

8、O(d n)O(d n)O(d n)O(n)穩(wěn)定第4章 棧和隊(duì)列棧限定僅在表尾進(jìn)行和刪除的線性表，把這個(gè)表尾稱為棧頂。特點(diǎn)：后進(jìn)先出(LIFO表)棧的方法順序棧鏈棧棧的順序棧的鏈?zhǔn)嚼?：一個(gè)棧的輸入序列是12345，若在入棧的過允許出棧，則棧的輸出序列43512可能實(shí)現(xiàn)嗎？12345的輸出呢？43512不可能實(shí)現(xiàn)，主要是其中的12順序不能實(shí)現(xiàn)；12345的輸出可以實(shí)現(xiàn)，只需壓入一個(gè)立即彈出一個(gè)即可。答：例2：如果一個(gè)棧的輸入序列為123456，能否得到435612和135426的出棧序列？答：435612中到了12順序不能實(shí)現(xiàn)； 135426可以實(shí)現(xiàn)。例3一個(gè)棧的輸入序列為123，若在入棧的過

9、許出棧，則可能得到的出棧序列是什么？允答：可以通過窮舉所有可能性來求解： 1入1出， 2入2出，3入3出， 即123； 1入1出， 2、3入3、2出，即132； 1、2入，2出， 3入3出，即231； 1、2入，2、1出，3入3出， 即213； 1、2、3入，3、2、1出，即321；合計(jì)有5種可能性。4.34.3.1隊(duì)列 （排隊(duì)買票）隊(duì)列的結(jié)構(gòu)特點(diǎn)和操作隊(duì)尾隊(duì)頭隊(duì)列的定義限定在表的一端、另一端刪除。隊(duì)列：線性表(queue)特點(diǎn)：先進(jìn)先出 (FIFO結(jié)構(gòu))。下圖是隊(duì)列的示意圖：表尾稱為隊(duì)尾(rear)表頭稱為隊(duì)頭(front)a1a2an出隊(duì)入隊(duì)元素稱為入隊(duì)隊(duì)頭隊(duì)尾刪除元素稱為出隊(duì)當(dāng)隊(duì)列中沒有

10、元素時(shí)稱為空隊(duì)列。在順序隊(duì)列中，當(dāng)尾指針已經(jīng)指向了隊(duì)列的最后一個(gè)位置即數(shù)組上界時(shí)，若再有元素入隊(duì)，就會(huì)發(fā)生“溢出”?！凹僖绯觥标?duì)列的空間未滿，卻發(fā)生了溢出。解決“假溢出”有兩種可行的方法：(1)、平移元素：把元素平移到隊(duì)列的首部。效率低。(2)、將新元素到第一個(gè)位置上，循環(huán)隊(duì)列，入隊(duì)和出隊(duì)仍按“先進(jìn)先出”的原則進(jìn)行。操作效率、空間利用率高。rearrearrearfront rearfrontfrontfrontJ4J3J4J3J4J3J4J3J2J1選用空閑單元法：即front和rear之一指向?qū)嵲?，另一指向空閑元素。隊(duì)空條件 : front = rear(初始化時(shí)：front = rea

11、r )隊(duì)滿條件： front = (rear+1) % N(N=maxsize)隊(duì)列長(zhǎng)度：L=（Nrearfront）% N問1：左圖中隊(duì)列長(zhǎng)度L=？ 5J2J3問2： 在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有多少J1J4front個(gè)元素？n-1個(gè)J5rear例1： 一循環(huán)隊(duì)列如下圖所示，由圖可知，隊(duì)頭和隊(duì)尾指針的初態(tài)分別為front=1和rear=0。若先刪除4個(gè)元素，接著4個(gè)元素，請(qǐng)問隊(duì)頭和隊(duì)尾指針分別指向哪個(gè)位置?front再frontJ2J3J8J9frontrearJ7J1J4frontJ6J5J5frontfrontrear解：刪除4個(gè)元素后front=(1+4)%6=5；4個(gè)元素后

12、，rear=(0+4)%6=4再例2 ：數(shù)組n用來表示一個(gè)循環(huán)隊(duì)列，f 為當(dāng)前隊(duì)列頭元素的前一位置，r 為隊(duì)尾元素的位置。假定隊(duì)列中元素的個(gè)數(shù)小于n，計(jì)算隊(duì)列中元素的公式為:（） rf（）nrf（）（nfr）% n（）（nrf）% nfrontJ2J3J1J4J5分析 ：4種公式哪種合理？當(dāng) r f 時(shí)（A）合理；當(dāng) r n，則無左孩子；i的右孩子是2i + 1，如果2i + 1n則無右孩子。課堂練習(xí)：1.深度為k的二叉樹的結(jié)點(diǎn)總數(shù)，最多為個(gè)。)k-1)log2k)k)k2. 深度為9的二叉樹中至少有個(gè)結(jié)點(diǎn)。)9)8)913二叉樹有n個(gè)葉子，沒有度為1的結(jié)點(diǎn)，共有 2n-1個(gè)結(jié)點(diǎn)分析：度為2的

13、結(jié)點(diǎn)有n-1個(gè)，所以共2n-1個(gè)結(jié)點(diǎn)。 4。設(shè)一棵完全二叉樹具有1000個(gè)結(jié)點(diǎn)，則它有個(gè)葉子結(jié)點(diǎn)，有個(gè)度為2的結(jié)點(diǎn)，有個(gè)結(jié)點(diǎn)只有非樹，有個(gè)結(jié)點(diǎn)只有非空右。課堂練習(xí)：1完全二叉樹的第3層有2個(gè)葉子，則共有個(gè)結(jié)點(diǎn)5111232323456745674589 10 118910一棵深度為6的滿二叉樹有個(gè)分支結(jié)點(diǎn)和個(gè)葉子。n個(gè)節(jié)點(diǎn)的完全二叉樹高度為，n個(gè)葉子節(jié)點(diǎn)的完全二叉樹高度為。已知二叉樹有50個(gè)葉子結(jié)點(diǎn)，則該二叉樹的總結(jié)點(diǎn)數(shù)至少應(yīng)有個(gè)？二叉樹二叉樹二叉樹順序方法有順序結(jié)構(gòu)和鏈?zhǔn)酵耆鏄洌河靡唤M地址連續(xù)的單元依次自上為 i 的結(jié)而下、自左至右結(jié)點(diǎn)元素，即將在一維數(shù)組中下標(biāo)為 i 的分量中（不用點(diǎn)元

14、素下標(biāo)為0全二叉樹單元）。此順序結(jié)構(gòu)僅適用于完不是完全二叉樹怎么辦？一律轉(zhuǎn)為完全二叉樹！方法很簡(jiǎn)單，將各層空缺處統(tǒng)統(tǒng)補(bǔ)上“虛結(jié)點(diǎn)”，其內(nèi)容為空。缺點(diǎn)：浪費(fèi)空間；、刪除不便2、 鏈?zhǔn)浇Y(jié)構(gòu)parent二叉樹結(jié)點(diǎn)的特點(diǎn)二叉樹是非線性結(jié)構(gòu)，適合用鏈?zhǔn)浇Y(jié)構(gòu)方式datalchildrchild一般從根結(jié)點(diǎn)開始來表示。（相應(yīng)地，也只能從根開始），用二叉鏈表樹中結(jié)點(diǎn)時(shí)l結(jié)點(diǎn)結(jié)構(gòu)二叉樹結(jié)點(diǎn)數(shù)據(jù)類型定義：typedef struct BiTNode emType data;struct BTNode*lchild,*rchild; BiTNode,*BiTree;rchildlchilddatachilddata

15、rchildAABBCCDDFEG二叉鏈表注：如果需要倒查某結(jié)點(diǎn)的雙親，可以再增加一個(gè)雙親域（直接前趨）指針，將二叉鏈表變成三叉鏈表。GDFECDCBBAA012345678. 151.設(shè)二叉樹的順序結(jié)構(gòu)如下：（1）根據(jù)其結(jié)構(gòu)，畫出該二叉樹。（2）寫出前序，中序，后序遍歷該二叉樹所得的結(jié)點(diǎn)序列。2.已知一棵二叉樹的中序序列和后序序列分別是 BDCEAFHG 和 DECBHGFA，請(qǐng)畫出這棵二叉樹。ABCEDGF二叉樹遍歷若規(guī)定先左后右，則只有前三種情況：DLR 先（根）序遍歷，LDR 中（根）序遍歷，LRD 后（根）序遍歷結(jié)論已知二叉樹的先序序列和中序序列，可以唯一確定一棵二叉樹。已知二叉樹的

16、后序序列和中序序列，可以唯一確定一棵二叉樹。已知二叉樹的先序序列和后序序列，不能唯一確定一棵二叉樹。樹和森林樹和森林定義樹的遍歷方法Huffman樹的應(yīng)用帶權(quán)路徑計(jì)算WPL具有相同帶權(quán)結(jié)點(diǎn)的滿二叉樹不一定是樹不惟一樹樹的結(jié)點(diǎn)的度數(shù)為 0 或 2， 沒有度為 1 的結(jié)點(diǎn)。包含 n 個(gè)葉子結(jié)點(diǎn) 的點(diǎn)。有2n 1 個(gè)結(jié)樹本章小結(jié)雙親表示先序遍歷后序遍歷結(jié)構(gòu)遍歷孩子表示1、定義和性質(zhì)孩子兄弟樹順序結(jié)構(gòu)2、結(jié)構(gòu)二叉鏈表鏈?zhǔn)浇Y(jié)構(gòu)先序遍歷三叉鏈表二叉樹森林3、遍歷中序遍歷遍歷后序遍歷先序線索樹后序遍歷先序遍歷4、線索化：線索樹中序線索樹后序線索樹編碼樹第7章 圖圖的相關(guān)定義(無向完全圖、有向完全圖、網(wǎng)、連通

17、 圖、強(qiáng)連通圖、度、入度、出度、生成樹和生成森林)圖的方式鄰接矩陣無向圖鄰接矩陣有向圖鄰接矩陣網(wǎng)的鄰接矩陣每個(gè)結(jié)點(diǎn)的出度？入度？度？圖的邊數(shù)？鄰接表每個(gè)結(jié)點(diǎn)的出度？入度？度？圖的邊數(shù)？例已知某網(wǎng)的鄰接（出邊）表，請(qǐng)畫出該網(wǎng)絡(luò)。當(dāng)鄰接表的結(jié)構(gòu)形成后，圖便唯一確定！圖的遍歷廣度優(yōu)先搜索從圖的某一結(jié)點(diǎn)出發(fā)，首先依次Vi2, , Vin 再按這些頂點(diǎn)被該結(jié)點(diǎn)的所有鄰接頂點(diǎn) Vi1,的先后次序依次與它們相鄰接的所有未被的頂點(diǎn)，重復(fù)此過程，直至所有頂 點(diǎn)均被為止。深度優(yōu)先搜索1、指定的起始頂點(diǎn)；2、若當(dāng)前的頂點(diǎn)的鄰接頂點(diǎn)有未被的，則任選一個(gè)訪問之；反之，退回到最近過的頂點(diǎn)；直到與起始頂點(diǎn)相通的全部頂點(diǎn)都完

18、畢；3、若此時(shí)圖中尚有頂點(diǎn)未被，則再選其中一個(gè)頂點(diǎn)作為起之，轉(zhuǎn) 2； 反之，遍歷結(jié)束。始頂點(diǎn)并最小生成樹姆算法將頂點(diǎn)進(jìn)行歸并算法將邊進(jìn)行歸并例：Prim算法UV0V056111255 5V1V2V35V1V2V364432326V4V5V4V564最小代價(jià)生成樹的生成過程例： Kruscal 算法實(shí)例的執(zhí)行過程V05615 5V1V2V364326V4V5圖GV05155V1V2V3432算法實(shí)現(xiàn)要點(diǎn): 每個(gè)結(jié)點(diǎn)增加一個(gè)數(shù)據(jù)場(chǎng)，用于標(biāo)識(shí)該結(jié)點(diǎn)V4V5所屬的集合?？捎糜谂袛嘈碌倪吋尤牒笫欠窕芈?。最小代價(jià)生成樹1、初始連通分量： 0,1,2,3,4,52、反復(fù)執(zhí)行添加、放棄動(dòng)作。條件：邊數(shù)不等于

19、n-1時(shí)邊動(dòng)作連通分量(0,2)添加0,2,1,3,4,5(3,5)添加0,2,3, 5,1,4(1,4)添加0,2,3, 5,1,4(2,5)添加0,2,3,5,1,4(0,3) 放棄 因 回路 (2,3) 放棄 因 回路 (1,2) 添加 0,2,3,5,1,4單源最短路徑在帶權(quán)有向圖中A點(diǎn)（源點(diǎn)）到達(dá)B點(diǎn)（終點(diǎn)）的多條路徑中，尋找一條各邊權(quán)值之和最小的路徑，即最短路徑(Dijkstra) 算法：按路徑長(zhǎng)度遞增次序產(chǎn)生最短路徑1、把 V 分成兩組：S：已求出最短路徑的頂點(diǎn)的集合。V - S = T：尚未確定最短路徑的頂點(diǎn)集合。 2、將 T 中頂點(diǎn)按最短路徑遞增的次序加入到 S 中，保證： (1) 從源點(diǎn) v0 到 S 中各頂點(diǎn)的最短路徑長(zhǎng)度都不大于從 v0 到 T 中任何頂點(diǎn)的最短路徑長(zhǎng)度。(2) 每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離值：S 中頂點(diǎn)：從 v0 到此頂點(diǎn)的最短路徑長(zhǎng)度。T 中頂點(diǎn)：從 v0 到此頂點(diǎn)的只包括S 中頂點(diǎn)作中間頂點(diǎn)的最短路徑長(zhǎng)度。拓?fù)渑判駻OV網(wǎng)：在一個(gè)有向圖中，若用頂點(diǎn)表示活動(dòng)，有向邊表示活動(dòng)間先后關(guān)系，稱該有向圖叫做頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(Activity On Vertex network)簡(jiǎn)稱為AOV網(wǎng)。拓?fù)渑判虻姆椒ǎ涸谟邢驁D中選一個(gè)沒有前驅(qū)的頂點(diǎn)且輸出之。從圖中刪除該頂點(diǎn)