熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

自學考試《數據結構》復習指導-2

2013-11-15 15:22:08  來源: 數據結構 

    第五章

  概念一個圖G由兩個集合V和E組成V是有限的非空頂點集E是用頂點對表示的邊集

  無向圖有向圖

  鄰接關聯鄰接到(於)關聯於孤立頂點

  頂點的度圖G中關聯於頂點V的邊的數目稱為V的度

  所有頂點的度等於邊的兩倍

  子圖

  完全圖每對頂點之間都有一條邊相連的圖在有向圖中每對頂點之間都有兩條有向邊相互關聯的圖

  在無向完全圖中邊的總數為Cn=n(n)/

  在有向完全圖中邊的總數為Pn=n(n

  路徑由邊組成

  回路

  連通圖對於無向圖如果圖中任何兩頂點都是可達的則稱此圖為連能圖

  對於有向圖如果圖中任何兩個頂點都是相互可達的則此有向圖是強連通的如果圖中任何兩頂點至少有一個頂點另一個頂點可達則稱此有向圖是單向連通的

  強連通分量有向圖的最大強連通子圖稱為它的強連通分量 樹圖其本質特征是連通性和無圈性把不含圈的無向連通圖稱為樹圖

  網絡是每條邊上帶有數量指標的連通圖

  鄰接矩陣鄰接表

  第六章 查找

  查找就是確定一個已給的數據是否出現在某個數據表中

  域(字段)組成記錄的每個數據項

  關鍵字通常記錄中總存在某個或某組數據項它們的值能唯一標識一個記錄這個(組)數據項稱為關鍵字

  方法順序

  二分

  線性插值

  分區

  二叉排序樹如果將記錄的鍵碼按二叉樹的結構來組織並且假定樹中任意非葉子結點的鍵碼大於其左子樹所有結點的鍵碼(若左子樹存在的話)而小於其右子樹所有結點的鍵碼(如右子樹存在的話)這樣的二叉樹叫二叉排序樹(二叉查找樹) 哈 希查找

  哈希函數能把關鍵字映射成記錄存貯地址的函數

  哈希表假定數組HT[··m]為存貯記錄的地址空間哈希函數H以每個記錄的關鍵字值K作為輸入產生一個落在[··m]內的整數H(K)並以它作為K所標識的記錄在表HT中的地址或索引號這樣產生的記錄表H(K)叫做 ··]

  構造哈希函數的方法

  直接定址法

  除留余數法

  平方取中法

  折疊法與移位法

  數字分析法

  沖突處理

  開放定址法 線性探測法 偽隨機探測法

  鏈地址法

  第七章排序

  內部排序

  外部排序

  內部冒泡 選擇 插入 歸並 堆排序 快速排序 基數

  堆每個非終端結點的關鍵字大於等於它的孩子結點的關鍵字

  第八章文件

  基本概念

[] []


From:http://tw.wingwit.com/Article/program/sjjg/201311/23303.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.