蘇仕華版自考數(shù)據(jù)結(jié)構(gòu)筆記總結(jié)

第一章概論1、 若結(jié)點(diǎn)的存儲(chǔ)地址與其關(guān)鍵字之間存在某種映射關(guān)系則稱為：散列存儲(chǔ)結(jié)構(gòu)。2、 數(shù)據(jù)類型通常稱為原子型和結(jié)構(gòu)型。索引存儲(chǔ)：附加索引表。關(guān)鍵字是能唯一標(biāo)識(shí)一個(gè)元素的一個(gè)數(shù)據(jù)項(xiàng)或多個(gè)數(shù)據(jù)項(xiàng)的組合。3、 抽象數(shù)據(jù)類型是指數(shù)據(jù)邏輯結(jié)構(gòu)及與之相關(guān)的操作第二章線性表4、 順序表便于按號(hào)查找結(jié)點(diǎn)5、 順序表中插入一個(gè)元素平均需要移動(dòng)n/2刪除一個(gè)元素平均需要移動(dòng)(4)/26、 最節(jié)省時(shí)間的存儲(chǔ)結(jié)構(gòu)式：僅有尾指針的單循環(huán)鏈表，帶頭結(jié)點(diǎn)的雙循環(huán)鏈表。7、 將線性表的數(shù)據(jù)元素按其邏輯次序依次存入一組地址連續(xù)的存儲(chǔ)單元里，用這種方法存儲(chǔ)的線性表稱為順庠表。8、 在第i個(gè)元素之前插入一個(gè)新元素需要進(jìn)n?i+1次移動(dòng)，在第i個(gè)元素之后插入一個(gè)新元素需要后移nt個(gè)元素。9、 單鏈表中每個(gè)結(jié)點(diǎn)的存儲(chǔ)地址是存放在其直接前驅(qū)結(jié)點(diǎn)的指針域中10、 在雙鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p，其時(shí)間復(fù)雜度為O⑴第三章棧和隊(duì)列11、 循環(huán)隊(duì)列出隊(duì)列：(front+1)%m入隊(duì)列：(rear+1)%m循環(huán)隊(duì)列元素個(gè)數(shù)：(rear-front+m)%m12、 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：不需要判斷棧滿單需要判斷?？铡ｍ樞虼鎯?chǔ)結(jié)構(gòu)：既需要判斷?？找残枰袛鄺M且需要置空棧。13、 遞歸實(shí)現(xiàn)和函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，應(yīng)采用的數(shù)據(jù)結(jié)構(gòu)是堆棧。14、 初始top為n+1，則X入棧操作：top=top-1;V[top]=X;第四章多維數(shù)組和廣義表15、 二維數(shù)組Am*n按行優(yōu)先順序存儲(chǔ)公式：LOC(aij)=LOC(a00)+(i*n+j)*d16、 三位數(shù)組Am*n*p按行優(yōu)先順序存儲(chǔ)公式：LOC(aijk)=LOC(a000)+(i*n*p+j*p+k)*d17、 應(yīng)許結(jié)點(diǎn)共享的表稱為再入表。廣義表的深度：展開后所含括號(hào)的層數(shù)。18、 稀疏矩陣的三元組表是順序存儲(chǔ)結(jié)構(gòu)19、 廣義表表頭和表尾深度相同，則廣義表深度+1，不同則為深度最深。20、 假設(shè)以行優(yōu)先順序?qū)⒁粋€(gè)n階的5對角矩陣壓縮存儲(chǔ)到一維數(shù)組Q中，則數(shù)組Q的大小至少為5n-6(n>5)。第五章：樹和二叉樹1、二叉樹的性質(zhì)21、 一個(gè)結(jié)點(diǎn)擁有的子樹稱為該樹的度，一棵樹中結(jié)點(diǎn)的最大度稱為該樹的度。22、 度為零的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)或終端結(jié)點(diǎn)，樹中的最大層次稱為該樹的深度或高度23、 在二叉樹的第i層上至多有2i-i個(gè)節(jié)點(diǎn)，深度為K的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)。24、 對任何一棵二叉樹T,若其終端結(jié)點(diǎn)數(shù)為％，度數(shù)為2的節(jié)點(diǎn)數(shù)為n2,則n0=n2+125、 滿二叉樹：一顆深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹成為滿二叉樹.26、 完全二叉樹：若一棵深度為K的二叉樹，其前k-1層是一個(gè)滿二叉樹，而下一層(即第k層)上的結(jié)點(diǎn)都集中在該層最左邊的若干位置上，則稱為完全二叉樹27、 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為logn+1或者log(n+1)。28、 已知一棵度為3的樹中，度為2的結(jié)點(diǎn)數(shù)為4，度為3的結(jié)點(diǎn)數(shù)為3，則該樹中葉子結(jié)點(diǎn)為1129、 含有3個(gè)結(jié)點(diǎn)a,b,c的二叉樹，前序序列a,b,c且后序序列為cba的二叉樹共有4棵。30、 哈夫曼樹：帶權(quán)路徑長度最短的樹。哈夫曼樹一個(gè)有2n-1個(gè)結(jié)點(diǎn)。31、 若一棵具有n(n>0)個(gè)結(jié)點(diǎn)的二叉樹的先序序列與后序序列正好相反，則二叉樹的高度一定為n.32、 一棵左子樹為空的二叉樹的前序線索化后，其空指針為2。33、 在左右子樹均不空的先序線索二叉樹中，空鏈域的數(shù)冃是1。34、 一棵樹的后序遍歷等價(jià)于該二叉樹的中序遍歷。35、 森林：m棵互不相交樹的集合。若將一棵樹的根結(jié)點(diǎn)刪除，就得到該樹構(gòu)成的森林。36、N個(gè)頂點(diǎn)的生成樹有條邊。一個(gè)帶權(quán)的無向連通圖的最小生成樹有一顆或多棵。37、 已知二叉樹的中序序列和后序序列均為ABCDEF，則先序序列為FEDCBA。38、 已知一顆含有50個(gè)節(jié)點(diǎn)的二叉樹中只有一個(gè)葉子結(jié)點(diǎn)，則該二叉樹中度為1的結(jié)點(diǎn)個(gè)數(shù)為49。39、 一顆完全二叉樹中含有1000個(gè)結(jié)點(diǎn)，則其中度為2的結(jié)點(diǎn)個(gè)數(shù)為499.40、 用二叉鏈表保存有n個(gè)結(jié)點(diǎn)的二叉樹，則結(jié)點(diǎn)中有n+1個(gè)空指針域。41、 在含100個(gè)結(jié)點(diǎn)的完全二叉樹中，葉子結(jié)點(diǎn)的個(gè)數(shù)為50。42、 已知完全二叉樹的第4層有4個(gè)結(jié)點(diǎn)，則其葉子結(jié)點(diǎn)數(shù)是6。43、 已知完全二叉樹的第7層有8個(gè)結(jié)點(diǎn)，則葉子結(jié)點(diǎn)數(shù)是32。2、最優(yōu)二叉樹（哈夫曼樹）在兩個(gè)節(jié)點(diǎn)構(gòu)成的路徑上的分支（邊）數(shù)目稱為路勁長度，而樹根到樹中每個(gè)結(jié)點(diǎn)的路徑長度之和稱為路徑長度。完全二叉樹就是這種路徑長度最短的二叉樹。從樹根結(jié)點(diǎn)到某結(jié)點(diǎn)之間的路徑長度與該節(jié)點(diǎn)上權(quán)的乘積稱為該結(jié)點(diǎn)的帶權(quán)路徑長度，樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和稱為該樹的帶全路徑長度，通常記為：WPL=wj]+w2l2+…+wJi利用哈夫曼樹求得的用于通信的二進(jìn)制編碼稱為哈夫曼編碼。樹中從根到每個(gè)結(jié)點(diǎn)都有一條路徑，對路徑上的各分支約定指向左子樹的分支表示“0”碼，指向右子樹的分子表示“1”碼，取每條路徑上的“0”或“1”的序列作為每個(gè)葉子結(jié)點(diǎn)對應(yīng)的字符編碼，這就是哈夫曼編碼。第六章圖44、 無向圖邊或弧e的取值范圍0~n（n-]）/2有向圖邊或弧的取值范圍0?n（n-1）45、 深度優(yōu)先算法（DFS）遍歷類似于樹的前序遍歷。廣度優(yōu)先遍歷（BFS）類似于樹的按層遍歷時(shí)間復(fù)雜度空間復(fù)雜度深度優(yōu)先算法（DFS）遍歷類似于樹的前序遍歷，從頂點(diǎn)v出發(fā)，依次訪問鄰接點(diǎn)鄰接矩陣：O（n2）鄰接表：O（n+e）廣度優(yōu)先算法（BFS）遍歷類似于樹的按層次遍歷，按層帶有大小順序依次訪問鄰接矩陣：O（n2）鄰接表：O（n+e）O(n)最小生成樹：普利姆算法和克魯斯卡爾算法46、 最短路徑：迪杰斯特拉算法：按路徑長度遞增的順序產(chǎn)生諸頂點(diǎn)的最短路徑算法，圖中某頂點(diǎn)到其他頂點(diǎn)的最短路徑。O（n+e）47、 帶權(quán)圖的最短路徑問題，路徑長度指：路徑上各邊的權(quán)值之和。48、 我們把這種頂點(diǎn)表示活動(dòng)，邊表示活動(dòng)間先后關(guān)系的有向無環(huán)圖（DAG）稱為頂點(diǎn)活動(dòng)網(wǎng)，簡稱AOV網(wǎng)。在AOV網(wǎng)中，若不存在回路（即環(huán)），所有活動(dòng)可排成一個(gè)線性序列，使得每個(gè)活動(dòng)的所有前驅(qū)活動(dòng)都排在該活動(dòng)的前面，此序列就是拓?fù)湫蛄?。由AOV網(wǎng)構(gòu)造拓?fù)湫蛄械倪^程稱為拓?fù)渑判颉?9、 對于一個(gè)具有n個(gè)頂點(diǎn)和e跳變的無向圖，若采用鄰接表表示，則表頭向量的大小為n，所有鄰接表中的節(jié)點(diǎn)數(shù)2e.50、 若無向圖有n個(gè)頂點(diǎn)和e條邊，則它的鄰接表共用n個(gè)頭結(jié)點(diǎn)和2e個(gè)表頭結(jié)點(diǎn)。51、 在無向圖中，如果對任意兩個(gè)頂點(diǎn)Vi和Vj都連通，即從Vi到Vj和Vj到Vi都存在路徑，則稱圖G是連通圖52、 無向圖的極大連通子圖稱為連通分量，顯然，任何連通圖的連通分量只有一個(gè)，就是其本身。而非連通圖的無向圖有多個(gè)連通分量。53、 在有向圖中，如果對任意兩個(gè)頂點(diǎn)Vi和Vj都連通，即從Vi到Vj和Vj到Vi都存在路徑，則稱圖G是強(qiáng)連通圖54、 有向圖的極大連通子圖稱作有向圖的強(qiáng)連通分量55、 在每條邊上標(biāo)上某種值，帶權(quán)圖的連通圖稱為網(wǎng)絡(luò)。若圖G中任意兩個(gè)不同的頂點(diǎn)間都有路徑，則稱該圖為連通圖。56、 一個(gè)無向連通圖的生成樹是含有該連通圖的全部頂點(diǎn)的極小連通子圖。57、 若用鄰接矩陣表示有向圖，則頂點(diǎn)i的入度等于鄰接矩陣中第i列非零元素個(gè)數(shù)。58、 N個(gè)頂點(diǎn)且含有回路的無向連同圖中，至少含有n條邊。59、 若要建立網(wǎng)絡(luò)的鄰接表，則需要在邊表的每個(gè)結(jié)點(diǎn)中增加一個(gè)存儲(chǔ)邊上權(quán)值的數(shù)據(jù)域。第七章：排序1、排序過程中需要進(jìn)行兩種基本操作：比較兩個(gè)關(guān)鍵字的大小、改變指向記錄的指針或移動(dòng)記錄本身。而待排序記錄的存儲(chǔ)方式一般有三種：順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)和輔助表結(jié)構(gòu)。評價(jià)排序算法的標(biāo)準(zhǔn)主要有兩條：執(zhí)行算法需要的時(shí)間，以及算法所需要的附加空間。2、內(nèi)排序：插入、選擇、交換、歸并和分配排序。3、插入排序的基本思想：每次將一個(gè)待排序的記錄按其關(guān)鍵字的大小插入到前面已排好序的文件中的適當(dāng)位置，知道全部記錄插入完為止。包括：直接插入排序和希爾排序。3.1直接插入排序是一個(gè)就地排序（若排序算法所需要的額外空間相對于輸入數(shù)據(jù)量來說是一個(gè)常數(shù)，則成該類排序算法為就地排序）。最好情況最壞情況時(shí)間復(fù)雜度空間復(fù)雜度排序算法直接插入正序0（n）逆序O（n2）O(n2)0(1)穩(wěn)定希爾排序O(nlog2n)或O(ni.25)0(1)不穩(wěn)定4、交換排序的基本思想：兩兩比較待排序記錄的關(guān)鍵字，如果發(fā)現(xiàn)兩個(gè)記錄的次序相反時(shí)即進(jìn)行交換，知道所有記錄都沒有反序時(shí)為止。包括：冒泡排序和快速排序4.1冒泡排序是相鄰元素之間的比較和交換，快速排序記錄關(guān)鍵字的比較和記錄的交換是從兩端向中間進(jìn)行的，即該元素將比它大的和小的區(qū)分在兩邊，例如：231635673670最好情況最壞情況時(shí)間復(fù)雜度空間復(fù)雜度排序算法冒泡排序0(n2)0(1)穩(wěn)定快速排序（劃分交換排序）O(nlog2n)O(log2n)不穩(wěn)定5、選擇排序的基本思想：每一趟在待排序的記錄中選出關(guān)鍵字最小的記錄，一次存放在已排序號(hào)的記錄序列的最后，知道全部記錄排序完為止。包括：直接選擇排序和堆排序5.1堆排序：完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在聯(lián)系，在當(dāng)前無序區(qū)中選擇關(guān)鍵字最大（或最?。┯涗洝６雅判蛘抢么蟾眩ㄐ「眩﹣磉x取當(dāng)前無序區(qū)中關(guān)鍵字最大（最?。┑挠涗泴?shí)現(xiàn)排序的。每一趟排序的操作是：將當(dāng)前無序區(qū)調(diào)整成一個(gè)大根堆，選取關(guān)鍵字最大的堆頂記錄，將它和無序區(qū)中最后一個(gè)記錄交換，這正好與選擇排序相反。堆排序就是一個(gè)不斷建堆的過程。最好情況最壞情況時(shí)間復(fù)雜度空間復(fù)雜度排序算法直接選擇排序0(n2)0(1)不穩(wěn)定堆排序O(log2n)0(1)不穩(wěn)定6、歸并排序的基本思想：首先將待排序文件看成n個(gè)長度為1的有序子文件，把這些子文件兩兩歸并，得到n/2個(gè)長度為2的有序子文件然后再把這n/2個(gè)有序的子文件兩兩歸并，如此反復(fù)，知道最后得到一個(gè)長度為n的有序文件位置，這種排序方法稱為二路歸并排序。最好情況最壞情況時(shí)間復(fù)雜度空間復(fù)雜度排序算法歸并排序0(nlog尹)0(n)穩(wěn)定7、分配排序：箱（桶）排序和基數(shù)排序最好情況最壞情況時(shí)間復(fù)雜度空間復(fù)雜度排序算法基數(shù)排序0(d*(rd+n))0(n+rd)穩(wěn)定其中rd為基數(shù)，d是關(guān)鍵字的位數(shù)，n是元素個(gè)數(shù)9、排序方法的選?。?、 若待排序的一組記錄數(shù)目n較?。╪v=50）時(shí)，可采用插入排序和選擇排序2、 若n比較大時(shí)，則應(yīng)采用快速排序、堆排序或歸并排序3、 若待排序記錄按關(guān)鍵字基本有序時(shí)，則適合選用直接插入排序或冒泡排序4、 當(dāng)n很大時(shí)，而且關(guān)鍵字位數(shù)較少時(shí)，采用鏈?zhǔn)交鶖?shù)排序較好5、 關(guān)鍵字比較次數(shù)與記錄的初始排列順序無關(guān)的排序方法時(shí)選擇直接選擇排序第八章：查找1、順序查找：順序查找成功時(shí)的平均查找長度約為表長的一半：ASL=（n+1）/2，查找最多需要n+1次。如果查找成功和不成功機(jī)會(huì)相等，那么順序查找的平均查找長度：34*（n+1）優(yōu)點(diǎn)：簡單，且對表的結(jié)構(gòu)無任何要求，無論是順序存儲(chǔ)還是鏈?zhǔn)酱鎯?chǔ)，無論是否有序，都適用。缺點(diǎn)：效率低。時(shí)間復(fù)雜度：O(n)2、 二分查找：又稱折半查找，效率較高。二分查找要求查找對象的線性表必須是順序存儲(chǔ)結(jié)構(gòu)的有序表。查詢成功時(shí)平均長度：ASL=((n+1)/n)*log2(n+1)-1,二分查找的最壞性能和平均性能相當(dāng)接近。二分查找速度快快，效率高，適用于表不易改動(dòng)且又經(jīng)常查找的情況。時(shí)間復(fù)雜度：O(log2n)3、 索引順序查找(分塊查找)：是一種介于順序查找和二分查找之間的查找方法。在表中插入或刪除一個(gè)記錄時(shí)，只要找到該記錄所屬的塊，就可以在該塊內(nèi)進(jìn)行插入或刪除運(yùn)算。插入或刪除記錄時(shí)無需移動(dòng)大量記錄。缺點(diǎn)：需要一個(gè)輔助數(shù)組的存儲(chǔ)空間，不適宜用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。時(shí)間復(fù)雜度：O(n的開根號(hào))4、 散列表查找：1散列存儲(chǔ)中使用的函數(shù)H(key)稱為散列函數(shù)或哈希函數(shù)。它實(shí)現(xiàn)關(guān)鍵字到存儲(chǔ)地址的映射。H(key)的值稱為散列地址或哈希地址，使用的數(shù)組空間是線性表進(jìn)行散列存儲(chǔ)的地址空間，被稱為散列表或哈希表2處理沖突的方法：a、開放定址法b、拉鏈法開放定址法分為線性探查法、二次探查法和雙重散列法，開放定址法解決重復(fù)的基本思想是：使用某種方法在散列表中形成一個(gè)探查序列，沿著此序列逐個(gè)單元進(jìn)行查找，直到找到一個(gè)空閑的單元時(shí)將新節(jié)點(diǎn)插入其中。(1)、線性探查法：一種運(yùn)算時(shí)插入，若當(dāng)前探查單元為空，則將關(guān)鍵字key寫入空單元，若不為空，則繼續(xù)后續(xù)地址探查，知道遇到控單元插入關(guān)鍵字。、二分探査法：d=H(key)，探查從地址d開始，先探查T[d]，然后依次探查T[d+12]，T[d-12]T[d+22]，T[d-22]....、雙重散列法：探查序列為d=H(key)，(d+1*H1(key))%m，(d+2*H2(key))%m，...5、 B樹：一棵m(m>=3)階的B樹，或?yàn)榭諛?，或?yàn)闈M足下列性質(zhì)的m叉樹：、每個(gè)結(jié)點(diǎn)至少包含下列信息域：(n,p0,k1,p1,k2,…，kn,pn)、樹中每個(gè)結(jié)點(diǎn)至多有m棵子樹、若樹為非空，則根結(jié)點(diǎn)至少有—個(gè)是關(guān)鍵字，至多有 ■個(gè)關(guān)鍵字，因此若根節(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則它至少與兩棵子樹。、所有的葉子結(jié)點(diǎn)都在同一層上，并且不帶信息，葉子的層數(shù)為樹的高度