西安交通大學數(shù)據(jù)結(jié)構復習資料(參考版)
2025-04-20 12:21本頁面
【正文】 第九章 排序v 熟悉直接插入排序的方法以及描述其排序性能的指標v 熟悉直接選擇排序、堆排序和交換排序的方法、性質(zhì)以及描述排序性能的指標v 熟悉快速排序和歸并排序的方法、性質(zhì)及指標v 通過比較各排序方法性能（時間復雜度和空間復雜度等）熟悉如何選擇合適的排序方法。圖的邊集數(shù)組的定義v 能根據(jù)鄰接矩陣或鄰接表或邊集數(shù)組來得到圖的結(jié)構v 熟悉圖的深度和廣度優(yōu)先遍歷的方法，并能根據(jù)相應遍歷方法對給定的圖寫出其遍歷序列v 了解圖的生成樹和最小生成樹的定義和性質(zhì)v 熟悉普里姆算法和克魯斯卡爾算法，并能寫出根據(jù)給定的圖用這兩種算法之一來構成最小生成樹的過程。為了便于隨機訪問任一頂點的鄰接表，需要把這n個表頭指針用一個向量(即一維數(shù)組)存儲起來，其中第i個分量存儲vi鄰接表的表頭指針。在這三個域中，鄰接點域和鏈域是必不可少的，權域可根據(jù)情況取舍，若表示的是無權圖，則可省去此域。v vi鄰接表中的結(jié)點數(shù)，對于無向圖來說，等于vi的邊數(shù)，或鄰接點數(shù)或度數(shù)；對于有向圖來說，等于vi的出邊數(shù)、或出邊鄰接點數(shù)或出度數(shù)。v 為頂點vi建立的鄰接關系的單鏈表稱作vi鄰接表。v 圖的鄰接矩陣表示，需要使用一個二維數(shù)組存儲頂點之間相鄰的關系，為了存儲圖中n個頂點元素的信息，通常還需要使用一個一維數(shù)組，用數(shù)組中下標為i的元素存儲頂點vi的信息。v 圖的鄰接矩陣的存儲需要占用n n個整數(shù)存儲位置，所以其空間復雜度為O(n2)。v 在有向圖中, 統(tǒng)計第 i 行 中1的個數(shù)可得頂點 i 的出度，統(tǒng)計第 j 列中 1 的個數(shù)可得頂點 j 的入度。若其值大于1則為該通路的權值。E(G) 238。E(G)； A[i,j]= 237。 236。 了解圖的鄰接矩陣、鄰接表、逆鄰接表和十字鄰接表的定義及性質(zhì)鄰接矩陣(adjacency matrix)是表示圖形中頂點之間相鄰關系的矩陣。針對圖G，頂點集和邊集可分別記為V(G)和E(G)。 能根據(jù)給定的權值集合和結(jié)點集合構成具有n個結(jié)點的哈夫曼樹(1) 根據(jù)與n個權值{w1,w2,…,wn}對應的n個結(jié)點構成具有n棵二叉樹的森林F={T1,T2,…,Tn}，其中每棵二叉樹Ti(1≤i≤n)都只有一個權值為wi的根結(jié)點，其左、右子樹均為空； (2) 在森林F中選出兩棵根結(jié)點的權值最小的樹作為一棵新樹的左、右子樹，且置新樹的根結(jié)點的權值為其左、右子樹上根結(jié)點的權值之和； (3) 從F中刪除構成新樹的那兩棵樹，同時把新樹加入F中； (4) 重復(2)和(3)步，直到F中只含有一棵樹為止，此樹便是哈夫曼樹第七章 圖了解圖的定義以及基本性質(zhì)v 圖中的每個頂點，都允許有任意個前驅(qū)和后繼，即對每個頂點的前驅(qū)和后繼個數(shù)均不加以限制v 對于一個圖G，若E是有序?qū)Φ募希瑒t每個有序?qū)獔D形中的一條有向邊，若E是無序?qū)Φ募希瑒t每個無序?qū)獔D形中的一條無向邊，所以可把E看做為邊的集合。v 哈夫曼(Huffman)樹又稱作最優(yōu)二叉樹。結(jié)點的帶權路徑長度規(guī)定為從樹根結(jié)點到該結(jié)點之間的路徑長度與該結(jié)點上權的乘積。從k1到kj所經(jīng)過的分支數(shù)稱為這兩點之間的路徑長度，它等于路徑上的結(jié)點數(shù)減1。也就是說，在二叉樹中，一個結(jié)點到另一個結(jié)點之間的分支構成這兩個結(jié)點之間的路徑。v 堆頂結(jié)點具有最小值(——對應于小根堆）或最大值（—— 對應于大根堆)。 大根堆的定義與上述類似，只要把小于等于改為大于等于就得到了。了解堆的定義和性質(zhì)堆(Heap)分為小根堆和大根堆兩種，對于一個小根堆，它是具有如下特性的一棵完全二叉樹。 由此可知，在二叉搜索樹上查找比在集合或線性表上進行順序查找的時間復雜度O(n)要小得多，這正是構造二叉搜索樹的優(yōu)勢所在。了解二叉搜索樹應用于查找時的特性及指標v 在二叉搜索樹上進行查找的過程中，給定值item同樹中結(jié)點比較的次數(shù)最少為一次（即樹根結(jié)點就是待查的結(jié)點)，最多為樹的深度，所以平均查找次數(shù)要小于等于樹的深度。 在一個二叉搜索樹中，當每個結(jié)點的元素類型為簡單類型時，則結(jié)點的關鍵字就為該結(jié)點的值；當結(jié)點的元素類型為記錄類型時，則結(jié)點的關鍵字為該結(jié)點的某一個域的值。熟悉樹的遍歷序列與樹結(jié)構之間的關系，并能由特定的遍歷序列來恢復樹結(jié)構和寫出另外的遍歷序列熟悉樹與二叉樹的共性和差異之處熟悉樹的幾種遍歷算法能根據(jù)樹的定義（包括結(jié)點類型的定義）編程實現(xiàn)樹的一些基本運算第六章 二叉樹的應用了解二叉搜索樹的定義，性質(zhì)并能根據(jù)定義由給定序列構造二叉搜索樹v 二叉搜索樹(Binany Searching Tree)又稱做二叉排序樹(Binary Sorting Tree)，它或者是一棵空樹，或者是一棵具有如下特性的非空二叉樹。 （遍歷的過程與先根級的遞歸遍歷類似） ② 訪問根結(jié)點； ③ 中序遍歷右子樹 （遍歷過程與先根級的遞歸遍歷相同）(3) 后序遍歷：若二叉樹為空，則空操作；否則 ① 后序遍歷左子樹； ② 后序遍歷右子樹。lchilddataparentrchild熟悉二叉樹的4種遍歷方法，能按任何一種遍歷方法來寫出給定樹的遍歷序列(1) 先序遍歷：若二叉樹為空，則空操作；否則① 訪問根結(jié)點； ② 先序遍歷左子樹； { 先訪問左子樹根節(jié)點；再遍歷左子樹根節(jié)點的左子樹，再遍歷左子樹根節(jié)點的右子樹；……直至遍歷完所有左子樹的節(jié)點}③ 先序遍歷右子樹。其結(jié)點結(jié)構為：Leftdataright其中data表示值域，用于存儲
教學教案相關推薦
鄂ICP備17016276號-1