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