理解和掌握20xx06fx(文件)
【正文】 循環(huán)鏈表 ? 雙向鏈表 ? 需要掌握的知識(shí)點(diǎn) ? 單鏈表的基本概念 ? 單鏈表是線性表的鏈接存儲(chǔ)表示。 ? 鏈表的插入與刪除僅改變指針值。只要知道任一結(jié)點(diǎn)地址就能遍歷其他所有結(jié)點(diǎn)。 ? 雙向鏈表 ?有兩個(gè)鏈接指針：前驅(qū)和后繼。 ? 在雙向鏈表中插入新結(jié)點(diǎn)的算法。 ? 棧是先進(jìn)后出 , 隊(duì)列是先進(jìn)先出。 ? 循環(huán)隊(duì)列的結(jié)構(gòu)與特點(diǎn) ? 其存儲(chǔ)表示是順序的環(huán)形結(jié)構(gòu)。 ? 循環(huán)隊(duì)列：將一個(gè)新元素進(jìn)隊(duì)的算法。 ? 遞歸數(shù)據(jù)結(jié)構(gòu)（鏈表、樹等）可用遞歸算法求解。 ? 遞歸算法的編制 ? 二叉樹前序遍歷的算法。 ? 完全二叉樹用前序遍歷實(shí)現(xiàn)順序存儲(chǔ)表示與二叉鏈表表示相互轉(zhuǎn)換的算法。 ? 完全二叉樹結(jié)點(diǎn) i的雙親 ?(i1)/2?、左子女 2i+右子女 2i+2。 ? 二叉樹的前序序列與中序序列唯一確定二叉樹的方法。 ? 樹的左子女 /右兄弟表示中根沒有右兄弟。 T1 T2 T3 A F H T1 T2 T3 A B C D G I J E K F B C D E G H I K J A B C E D H I K J F G 3 棵樹的森林 各棵樹的二叉樹表示 森林的二叉樹表示 ? 霍夫曼樹與霍夫曼編碼 ? 霍夫曼樹的構(gòu)造方法。 ? 根的權(quán)值相同時(shí)，新構(gòu)造出來的樹的根一般位于右邊。 ? 形成堆時(shí)用到的向下調(diào)整算法。 ? 等概率情形下，二叉搜索樹的搜索成功的平均搜索長度計(jì)算。 ? 二叉搜索樹的搜索算法。 ? 從插入位置向上回溯找發(fā)生不平衡結(jié)點(diǎn)，確定參加旋轉(zhuǎn)結(jié)點(diǎn)。 ? 無向圖頂點(diǎn) 度的和等于邊數(shù)的 2倍 。 ? 圖的存儲(chǔ)表示 ? 鄰接矩陣是圖的順序存儲(chǔ) , 適用于稠密圖， e條邊時(shí)有 e~2e個(gè)非零元素。 ? 無向圖的鄰接矩陣是對(duì)稱的 。 ? 圖的 DFS生成樹的高度通常比其 BFS 生成樹的高度要高。 ? 拓?fù)渑判虻慕Y(jié)果可能不唯一。滿足圖中所有前驅(qū)和后繼關(guān)系 , 對(duì)于本來沒有這種關(guān)系的頂點(diǎn) , 如 C4和 C2, 也排出先后次序。 ? 當(dāng)初始排列已有序時(shí)速度提高最快。 ? 對(duì)特定的待排序?qū)ο笮蛄?，可以?zhǔn)確地估算比較次數(shù)和移動(dòng)次數(shù)。 ? 快速排序是不穩(wěn)定的排序方法。 ? 直接選擇排序的實(shí)例。 ? 歸并排序 ? 歸并排序的實(shí)例（不要算法）。 ? 數(shù)據(jù)移動(dòng)次數(shù)不受初始排列影響 , O(nlog2n) 次（表之間傳送）。 ? m階 B樹 的非失敗結(jié)點(diǎn)最多包含 m1 個(gè)關(guān)鍵碼 , 最少 ?m/2? 1 個(gè)關(guān)鍵碼。 ? 除留余數(shù)法注意除數(shù)的選擇：質(zhì)數(shù)。 ? 閉散列法 ? 線性探查的探查序列 ? 搜索成功的平均探查次數(shù) ? 搜索不成功的平均探查次數(shù) ? 探查序列 H0 = Hash(key) Hi = (H0 + i) % m, i = 1,2,…, m 1 ? 搜索成功的平均探查次數(shù) = 每個(gè)已有表項(xiàng)找到它的比較次數(shù)的平均值 ? 搜索不成功的平均探查次數(shù) = 散列函數(shù)可能算出的散列地址上插入新表項(xiàng)時(shí)找到空位的比較次數(shù)的平均值 ? 線性探查法容易產(chǎn)生“堆積” ? 閉散列法 ? 1, 開散列法 ? 可大于 1 ? 平均搜索長度取決于裝填因子 ? ? 平均搜索長度與裝填因子之間關(guān)系 處理沖突 平均搜索長度 A S L 的方法 搜索成功 S n 搜索不成功 ( 登入新記錄 ) U n 線性探查法 ?????????????? ?????????????????)( 。 ? 開散列法優(yōu)于閉散列法。 ? 解決沖突的閉散列法（線性探查）。 ? m階 B樹 所有失敗結(jié)點(diǎn)在同一層。 ? 歸并趟數(shù) = ?log2(n+1)? , n 是待排序數(shù)據(jù)對(duì)象個(gè)數(shù)。 ? 數(shù)據(jù)比較次數(shù)不受初始排列影響 = n(n1)/2。 ? 當(dāng)初始排列已經(jīng)有序時(shí) , 速度最慢 ,數(shù)據(jù)比較達(dá) n(n1)/2 次。
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號(hào)-1