西安交通大學(xué)數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料-wenkub
2023-05-02 12:21:46 本頁面
【正文】 儲單元，這種存儲單元稱為存儲結(jié)點，簡稱結(jié)點。v 所有數(shù)據(jù)元素ai在同一個線性表中必須是相同的數(shù)據(jù)類型。了解時間復(fù)雜度的概念、時間復(fù)雜度的度量、時間復(fù)雜度的類型，能對實際的程序分析它的時間復(fù)雜度。這個取值函數(shù)也稱為散列函數(shù)。為了區(qū)別于線性結(jié)構(gòu)，時常把樹結(jié)構(gòu)和圖結(jié)構(gòu)稱為非線性結(jié)構(gòu)。第一章 緒 論數(shù)據(jù)結(jié)構(gòu)的主要研究內(nèi)容①數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)關(guān)系之間的邏輯關(guān)系 ②數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的表示 數(shù)據(jù)邏輯結(jié)構(gòu)的種類：集合、線性表、樹和圖的性質(zhì)和特點。數(shù)據(jù)結(jié)構(gòu)的二元組定義，能根據(jù)給出的二元組來判斷數(shù)據(jù)的邏輯結(jié)構(gòu)類型。 數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和總的數(shù)據(jù)結(jié)構(gòu)之間的關(guān)系v 邏輯結(jié)構(gòu)相同，但存儲結(jié)構(gòu)不同，則認(rèn)為是不同的數(shù)據(jù)結(jié)構(gòu)。算法的時間復(fù)雜度是一個算法運行時間的相對量度。熟悉順序線性表（順序存儲的線性表）的存儲方式及其表單元（簡單數(shù)據(jù)類型和記錄數(shù)據(jù)類型）的定位和計算。v 在鏈?zhǔn)酱鎯Ψ绞街?，要求每個結(jié)點由兩部分組成：一部分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域（或稱為信息域）；另一部分用于存放指針，稱為指針域。如果這一鏈表中每個結(jié)點只有一個指針域，則稱該鏈表為線性鏈表或單鏈表，否則則稱為雙向鏈表。循環(huán)鏈表的特點：只要知道表中任何一個結(jié)點的地址，就能查詢到表中的任何一個結(jié)點。頭結(jié)點數(shù)據(jù)域可以不存儲任何信息，也可以存儲如線性表的長度等類的附加信息；頭結(jié)點指針域存儲指向第一個結(jié)點的指針(即第一個元素的存儲位置)。 了解線性表的順序與鏈?zhǔn)酱鎯υ诓煌僮鲌龊舷碌臅r間復(fù)雜度指標(biāo)順序表是隨機(jī)存儲結(jié)構(gòu)，表中任一數(shù)據(jù)元素都可以通過計算直接得到地址進(jìn)行存取，時間復(fù)雜度為O(1)。第四章 棧和隊列了解棧的定義及性質(zhì)棧（stack）又稱堆棧，它是一種運算受限的線性表，其限制是僅允許在表的一端進(jìn)行插入和刪除運算。v 由于隊列的插入和刪除操作分別是在各自的一端進(jìn)行的，每個元素必然按照進(jìn)入的次序離隊，所以又把隊列稱為先進(jìn)先出表（first in first out, 簡稱FIFO）。 v 葉子結(jié)點：度為零的結(jié)點稱葉子結(jié)點或終端結(jié)點。v 兄弟結(jié)點(sibling)：同一個雙親的孩子之間互為兄弟。也即樹T中各子樹T1，T2，…，Tn的相對次序是有意義的。 證明：根據(jù)定義：除根結(jié)點外，每個結(jié)點有一個分支指向。 對于第i層，最多結(jié)點數(shù)為：= ki1 命題得證。logk(n(k1)+1)249。因此得到具有n個結(jié)點的一般k叉樹的最小深度為： 233。 表示對x進(jìn)行向上取整熟悉二叉樹的定義及基本性質(zhì)，并能根據(jù)這些性質(zhì)進(jìn)行相關(guān)推理和計算。v 性質(zhì)1：在二叉樹第i 層上最多有2i1個結(jié)點( i≥1)。 由于在二叉樹中，任一結(jié)點的度數(shù)小于或等于2，所以其結(jié)點總數(shù)n為: n = n0 + n1 + n2 (n0 :終端結(jié)點。表達(dá)式235。 (3) 若編號為i的結(jié)點有左孩子，則左孩子結(jié)點的編號為2i；若編號為i的結(jié)點有右孩子，則右孩子結(jié)點的編號為2i+1，即遵循對一般二叉樹的編號規(guī)則。此點也適合于一般二叉樹。log2nlog2(n+1)249。 第i層有2i1個結(jié)點；全部分支結(jié)點度為2。v 顯然，理想平衡樹包含滿二叉樹和完全二叉樹。lchilddataparentrchild熟悉二叉樹的4種遍歷方法，能按任何一種遍歷方法來寫出給定樹的遍歷序列(1) 先序遍歷：若二叉樹為空，則空操作；否則① 訪問根結(jié)點； ② 先序遍歷左子樹； { 先訪問左子樹根節(jié)點；再遍歷左子樹根節(jié)點的左子樹，再遍歷左子樹根節(jié)點的右子樹；……直至遍歷完所有左子樹的節(jié)點}③ 先序遍歷右子樹。熟悉樹的遍歷序列與樹結(jié)構(gòu)之間的關(guān)系，并能由特定的遍歷序列來恢復(fù)樹結(jié)構(gòu)和寫出另外的遍歷序列熟悉樹與二叉樹的共性和差異之處熟悉樹的幾種遍歷算法能根據(jù)樹的定義（包括結(jié)點類型的定義）編程實現(xiàn)樹的一些基本運算第六章 二叉樹的應(yīng)用了解二叉搜索樹的定義，性質(zhì)并能根據(jù)定義由給定序列構(gòu)造二叉搜索樹v 二叉搜索樹(Binany Searching Tree)又稱做二叉排序樹(Binary Sorting Tree)，它或者是一棵空樹，或者是一棵具有如下特性的非空二叉樹。了解二叉搜索樹應(yīng)用于查找時的特性及指標(biāo)v 在二叉搜索樹上進(jìn)行查找的過程中，給定值item同樹中結(jié)點比較的次數(shù)最少為一次（即樹根結(jié)點就是待查的結(jié)點)，最多為樹的深度，所以平均查找次數(shù)要小于等于樹的深度。了解堆的定義和性質(zhì)堆(Heap)分為小根堆和大根堆兩種，對于一個小根堆，它是具有如下特性的一棵完全二叉樹。v 堆頂結(jié)點具有最小值(——對應(yīng)于小根堆）或最大值（—— 對應(yīng)于大根堆)。從k1到kj所經(jīng)過的分支數(shù)稱為這兩點之間的路徑長度，它等于路徑上的結(jié)點數(shù)減1。v 哈夫曼(Huffman)樹又稱作最優(yōu)二叉樹。針對圖G，頂點集和邊集可分別記為V(G)和E(G)。 236。E(G) 238。v 在有向圖中, 統(tǒng)計第 i 行 中1的個數(shù)可得頂點 i 的出度，統(tǒng)計第 j 列中 1 的個數(shù)可得頂點 j 的入度。v 圖的鄰接矩陣表示，需要使用一個二維數(shù)組存儲頂點之間相鄰的關(guān)系，為了存儲圖中n個頂點元素的信息，通常還需要使用一個一維數(shù)組，用數(shù)組中下標(biāo)為
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1