數(shù)據(jù)結(jié)構(gòu)名詞解釋整理

1、v1.0可編輯可修改Data Structure2015hash table 散列表：存放記錄的數(shù)組topological sort拓?fù)渑判颍簩⒁粋€DAG中所有頂點在不違反前置依賴條件規(guī)定的基礎(chǔ)上排成線性序列的過程稱為拓?fù)渑判颍?4） worst case 最差情況：從一個n元一維數(shù)組中找出一個給定的 K, 如果數(shù)組的最后一個元素是 K,運行時間會相當(dāng)長，因為要檢查所有 n個元素，這是算法的最差情況（15）FIFO先進(jìn)先出：隊列元素只能從隊尾插入，從隊首刪除（20）（ P82）2014growth rate增長率：算法的增長率是指當(dāng)輸入的值增長時，算法代價的增長速率（14）priority q

2、ueue優(yōu)先隊列：一些按照重要性或優(yōu)先級來組織的對象成為優(yōu)先隊列（26）exter nal sorti ng外排序：考慮到有一組記錄因數(shù)量太大而無法存放到主存中的問題，由于記錄必須駐留在外存中，因此這些排序方法 稱為外排序（32）connected component 連通分量：無向圖的最大連通子圖稱為連通分量（40）2013stack棧：是限定僅在一端進(jìn)行插入或刪除操作的線性表（19） priority queue優(yōu)先隊列：一些按照重要性或優(yōu)先級來組織的對象成為優(yōu)先隊列(26)BFS廣度優(yōu)先搜索：在進(jìn)一步深入訪問其他頂點之前，檢查起點的所有相鄰頂點(42)collision (in hash

3、ing)沖突：對于一個散列函數(shù) h和兩個關(guān)鍵碼值也和k2，如果h(k1) = = h(k2)，其中 是表中的一個槽，那 么就說k1和k2對于 在散列函數(shù)h下有沖(35)Chapter 1 Data Structures and Algorithms1. type類型：是指一組值的集合2. data type數(shù)據(jù)類型：一個類型和定義在這個類型上的一組操作3. abstract data type (ADT)抽象數(shù)據(jù)類型：指數(shù)據(jù)結(jié)構(gòu)作為一個軟件構(gòu)件的實現(xiàn)4. data structure數(shù)據(jù)結(jié)構(gòu)：是 ADT的實現(xiàn)5. problem問題：一個需要完成的任務(wù)，即對應(yīng)一組輸入，就有一組相應(yīng)的輸出6.

4、function 函數(shù)：是輸入和輸出之間的一種映射關(guān)系7. algorithm 算法：是指解決問題的一種方法或者一個過程8. algorithm 算法是解決問題的步驟，它必須把每一次輸入轉(zhuǎn)化為 正確的輸出；一個算法應(yīng)該由一系列具體步驟組成，下一步應(yīng)執(zhí) 行的步驟必須明確；一個算法必須由有限步組成；算法必須可以 終止。9. computer program計算機(jī)程序：被認(rèn)為是使用某種程序設(shè)計語言 對一個算法的具體實現(xiàn)10. program程序：是算法在計算機(jī)程序設(shè)計語言中的實現(xiàn)Chapter 2 Mathematical Prelim in aries11. set集合：是由互不相同的成員 mem

5、bers或者元素 elements構(gòu)成的一個整體12. recursive遞歸：如果一個算法調(diào)用自己來完成它的部分工作， 就稱這個算法是遞歸的Chapter 3 Algorithm An alysis13. Asymptotic analysis 漸進(jìn)分析：可以估算出當(dāng)問題規(guī)模變大 時，一種算法及實現(xiàn)它的程序的效率和開銷14. growth rate 增長率：算法的增長率是指當(dāng)輸入的值增長時， 算法代價的增長速率15. best / worst / average case 最佳、最差、平均情況(P39)16. upper bound (p42) / lower bound (p43)上限：該

6、算法可能有的最高增長率下限：一種算法消耗某種資源的最大值17. big-Oh (p42) / big-Omega (p43) / Theta notation (p44)Chapter 4 List, Stacks, and Queues18. list線性表：是由稱為元素的數(shù)據(jù)項組成的一種有限且有序的序列19. stack棧：是限定僅在一端進(jìn)行插入或刪除操作的線性表20. queue隊列：也是一種受限制的線性表，隊列元素只能從隊尾 插入，從隊首刪除Chapter 5 Binary Trees21. BST二叉檢索樹：是滿足下面所給出條件的二叉樹， 該條件即二叉檢索樹性質(zhì)：對于二叉檢索樹的任何

7、一個結(jié)點，設(shè)其值為K,則該結(jié)點左子樹中任意一個結(jié)點的值都小于K;該結(jié)點右子樹中任意一個結(jié)點的值都大于或等于 K22. depth深度：結(jié)點M的深度就是從根節(jié)點到M的路徑長度23. height高度：樹的高度等于最深結(jié)點的深度加 124. full b in ary tree滿二叉樹：的每一個結(jié)點或者是一個分支結(jié)點，并恰好有兩個非空子結(jié)點；或者是葉結(jié)點25. complete bi nary tree完全二叉樹：有嚴(yán)格的形狀要求：從根結(jié)點起每一層從左到右填充26. priority queue優(yōu)先隊列：一些按照重要性或優(yōu)先級來組織的對象成為優(yōu)先隊列27. heap堆：堆由兩條性質(zhì)來定義。首先，它

8、是一棵完全二叉樹， 所有往往用數(shù)組來實現(xiàn)表示完全二叉樹。其次，堆中存儲的數(shù)據(jù) 是局部有序的。也就是說，結(jié)點存儲的值與其子結(jié)點存儲的值之 間存在某種關(guān)系。Chapter 8 File Processing and External Sorting28. Golden Rule of File Processing:文件處理的黃金法則使磁盤的訪問次數(shù)最少！29. track磁頭在一個盤片的某個位置上可以訪問的所有數(shù)據(jù)就構(gòu) 成了一個磁道，即這個盤片上與主軸具有相同距離的所有數(shù)據(jù)30. sectors扇區(qū)：每個磁道（track ）分為多個扇區(qū)31. Con tiguous sectors are of

9、te n grouped to form acluster簇：多個扇區(qū)通常集結(jié)成組，稱為一個簇。簇是文件分配的最小 單位，因此所有文件都是一個或幾個簇的大小32. external sorti ng外排序：考慮到有一組記錄因數(shù)量太大而無法存放到主存中的問題，由于記錄必須駐留在外存中，因此這 些排序方法稱為外排序33. run順串：被排序的子序列成為順串（p294）Chapter 9 Search ing34. hashing散列：可以通過一些計算，把關(guān)鍵碼值映射到數(shù)組中 的位置來訪問記錄，這個過程稱為散列35. collision沖突：對于一個散列函數(shù) h和兩個關(guān)鍵碼值也和k2，如果h（k1）

10、= = h（k2），其中 是表中的一個槽，那么就說 k1和k2對于在散列函數(shù)h下有沖突Chapter 10 In dex ing36. In dex ing索引：是把一個關(guān)鍵碼與它對應(yīng)的數(shù)據(jù)記錄的位置 相關(guān)聯(lián)的過程37. primary key主碼：數(shù)據(jù)庫中的每一條記錄通常都有一個唯一 標(biāo)識，稱為主碼38. secondary key輔碼：可能有多條記錄相同的關(guān)鍵碼值39. lin ear in dex線性索引：的索引文件中是一組關(guān)鍵碼/指針對，這個文件按照關(guān)鍵碼順序排序，指針可以(1)指向磁盤中的 完整記錄所在的位置，也可以(2)指向主索引中主碼的位置，或 者(3)指向主碼的實際值Chapter 11 Graphs40. connected components連通分量：無向圖的最大連通子圖 稱為連通分量41. directed acyclic graph(DAG)有向無環(huán)圖：不帶回路的有向圖42. BFS (breadth-first search) 廣度優(yōu)先搜索：在進(jìn)一步深入訪問其他頂點之前，檢查起點的所有相鄰頂點43. DFS (deep-first search)深度優(yōu)先搜索：把所有從頂點 V出去的邊存入棧中44. topological sort拓?fù)渑判颍簩?/p>