數(shù)據(jù)結(jié)構(gòu)總復(fù)習(xí)

第一章緒論

1、數(shù)據(jù)結(jié)構(gòu)主要包括哪三方面內(nèi)容？

2、數(shù)據(jù)結(jié)構(gòu)是一個二元組（D,R）,其中D、R分別代表什么？

3、什么是邏輯結(jié)構(gòu)？什么是存儲結(jié)構(gòu)？兩者有何關(guān)系？

4、邏輯結(jié)構(gòu)主要分哪兩個類型？

5、存儲結(jié)構(gòu)主要有那些方式？

6、順序存儲方式是如何表示數(shù)據(jù)元素之間的關(guān)系？其存儲地址一定連續(xù)嗎？

7、鏈式存儲方式是如何表示數(shù)據(jù)元素之間的關(guān)系？其存儲地址一定連續(xù)嗎？

8、邏輯結(jié)構(gòu)與具體計算機有關(guān)嗎？存儲結(jié)構(gòu)呢？

9、什么是算法？算法有哪五個基本性質(zhì)？

10、算法與具體的計算機及計算機語言有關(guān)嗎？

11、算法與程序有何異同與聯(lián)系？

12、算法分析主要從哪三方面考慮？

第二章線性表

1、線性結(jié)構(gòu)的邏輯關(guān)系是什么？

2、順序表是如何表示數(shù)據(jù)元素的邏輯關(guān)系的？

3、單鏈表的特點是什么？

4、如何在單鏈表指定結(jié)點之后插入一個新結(jié)點？如何將指定結(jié)點之后的結(jié)點刪除?

5、循環(huán)鏈表的特點是什么？

6、雙向鏈表的特點是什么？

7、如何在雙向鏈表指定結(jié)點之前或之后插入一個新結(jié)點？如何將指定結(jié)點刪除？

8、順序表與鏈表比較各自的優(yōu)缺點是什么？

9、算法要求：（分別在順序表和鏈表實現(xiàn)下面算法）（特別是會修改指針）

（1）建立。（鏈表的頭插法和尾插法）

（2）查找指定元素。查找第i個元素。

（3）插入在第i個位置、插入在指定元素前或后、有序表的插入。

（4）刪除第i元素、刪除指定元素。

（5）線性表逆置。

（6）兩個線性表的有條件合并。

第三章棧、隊列復(fù)習(xí)題

1.棧的操作原則是什么？

2.棧有哪些基本運算？

3.算法要求：在順序表和鏈棧實現(xiàn)基本運算。

注意：?？盏臈l件和棧滿的條件及棧頂指針的移動。

4.兩個棧共享空間時基本運算如何實現(xiàn)？

5遞歸與棧有何關(guān)系？

6.隊列的操作原則是什么？

7.隊列有哪些基本運算？

8.順序隊列操作中的“假溢出”是什么？

9.循環(huán)隊列是存儲在循環(huán)鏈表中嗎？

10.循環(huán)隊列空的條件、滿的條件及求長度公式各是什么？

11.算法要求：在循環(huán)隊列和鏈式隊列實現(xiàn)基本運算。

注意：隊列空的條件和隊列滿的條件及隊頭、隊尾指針的移動。

10.棧和隊列的共同點和不同點是什么？

第四章串復(fù)習(xí)題

1、串的邏輯結(jié)構(gòu)是什么？

2、空串與空格串的區(qū)別是什么？

3、兩個串相等的充分必要條件是什么？

4、空串是任意串的子串嗎？串自身呢？

5、什么是結(jié)點大??？

6、了解串的基本運算的含義。

7、什么是模式匹配？如何實現(xiàn)？

8、算法要求（順序串和鏈串）：串的插入、刪除、置換、模式匹配等。

第五章數(shù)組的復(fù)習(xí)題

1、數(shù)組的邏輯結(jié)構(gòu)是什么？

2、數(shù)組的特點是什么？數(shù)組可以進行插入刪除操作嗎？

3、數(shù)組通常以什么方式存儲？

4、存儲二維數(shù)組有哪兩種排列方式？（要求會計算存儲地址）

5、特殊矩陣的壓縮存儲基本思想是什么？

6、對稱矩陣、三角矩陣和對三角矩陣如何壓縮存儲？

7、稀疏矩陣只需存儲非零元素的值嗎？

8、操作要求：會畫出稀疏矩陣的三元組表和十字鏈表的表示。

9、算法要求：在稀疏矩陣的三元組表和十字鏈表中，給定一組下標求出中元素值及矩陣簡單

操作。

第七章樹的復(fù)習(xí)題

1、樹的遞歸定義是什么？樹的邏輯結(jié)構(gòu)是什么？

2、什么是樹的度？什么是樹的深度？

3、樹有那些存儲方式？要求會畫出各種存儲方式。

4、操作要求：給定樹或森林寫出先根遍歷序列和后根遍歷序列兩種遍歷序列。

5、二叉樹與度為2的樹有何區(qū)別？

6、操作要求：會畫出二叉樹的5種基本形態(tài)。

7、三個結(jié)點能組成幾種不同的二叉樹？

8、二叉樹的五個性質(zhì)是什么？

9、滿二叉樹的特點是什么？完全二叉樹的特點是什么？

10、會畫出二叉樹按順序方式存儲和鏈式方式存儲的表示。

11、什么是（二叉樹或樹）遍歷？

（1）給出一棵二叉樹要求會寫出其前序遍歷序列、中序遍歷序列及后序遍歷序列。

（2）給出一棵二叉樹的先根遍歷序列和中根遍歷序列要求能畫出其二叉樹。

給出一棵二叉樹的中根遍歷序列和后根遍歷序列要求能畫出其二叉樹。

12、算法要求：二叉樹的遍歷算法。（遞歸遍歷、非遞歸遍歷及按層次遍歷的算法）

遍歷算法的應(yīng)用。

13、N個結(jié)點的線索二叉樹按二叉鏈表方式存，共有多少指針域？其中多少指針域為線索。

14、操作要求：會畫線索二叉樹。

15、操作要求：給定二叉樹能轉(zhuǎn)換為樹或樹林，給定樹或樹林能轉(zhuǎn)換為二叉樹。

第八章廣義表的復(fù)習(xí)題

1、什么是廣義表？其邏輯結(jié)構(gòu)是什么？

2、廣義表主要有哪些基本運算？

3、求表頭運算結(jié)果一定是原子元素嗎？求表尾一定是個子表嗎？

4、操作要求：給定廣義表能畫出其單鏈表示，并能進行求表頭、求表尾、求長度及深度運算。

第九章圖復(fù)習(xí)題

1、圖的邏輯結(jié)構(gòu)是什么？

2、一個具有N個頂點的完全無向圖有多少條邊？完全有向圖呢？

3、什么是圖中頂點的度？

4、任意圖是其自身的子圖嗎？

5、什么是連通圖及連通分量？

6、什么是生成樹？生成樹的三個特點是什么？

7、操作要求：給出圖要求能畫出其鄰接矩陣、鄰接表、十字鏈表和多重鄰接表。

8、鄰接矩陣占的存儲空間大小與圖中頂點個數(shù)有何關(guān)系？與邊（或?。┑膫€數(shù)有何關(guān)系？

9、鄰接表中無向圖中每條邊要占多少結(jié)點？有向圖呢？

10、什么是圖的遍歷？兩種基本方法是什么？

11、操作要求：給定圖（或給定其存儲結(jié)構(gòu)示意圖）要求能寫出其兩種遍歷序列。

并畫出對應(yīng)的生成樹或森林。

12、圖的應(yīng)用：最小生成樹和最短路徑

13、算法要求：兩種不同存儲方式下實現(xiàn)插入邊、刪除邊及求頂點的度。

兩種遍歷的通用算法及具體存儲方式的遍歷算法。

第十章查找復(fù)習(xí)題

1、ASL是什么？其有何用？

2、順序查找ASL為多少？

3、可用于二分查找（折半查找）的查找有什么要求？

4、二分查找（折半查找）若加入插入其效率如何？要求會計算折半查找的比較次數(shù)。

6、算法要求：二分查找（折半查找）的算法。

7、操作要求：會畫有n個記錄的二叉判定樹，并求出ASL（成功與不成功）。

8、什么是二叉排序樹？

9、中序遍歷二叉排序樹將得到什么結(jié)果？

10、操作要求：給出一個序列能構(gòu)造二叉排序樹，并求出相應(yīng)的ASL（成功與不成功）。

11、算法要求：二叉排序樹的插入（及建立）、二叉排序樹的查找。

12、什么是AVL樹？其特點是什么？

13、操作要求：會構(gòu)造AVL樹，并求出ASL。如何進行IX、RR、LR、RL調(diào)整。

14、AVL樹與二叉排序樹有何同異？

15、什么是哈希函數(shù)？常用的是什么？什么是同義詞？什么是沖突？什么是裝填因子？

17、操作要求：給出一個序列及哈希函數(shù)，并求出相應(yīng)的ASL（成功與不成功）。

（1）能畫出開放定址法的哈希表，并求出相應(yīng)的ASL（成功與不成功）。

（2）能畫出拉鏈法的哈希表，并求出相應(yīng)的ASL（成功與不成功）。

18、哈希表的查找效率與n有關(guān)嗎？

第十一章內(nèi)排序復(fù)習(xí)題

1、什么是排序？什么是排序的穩(wěn)定性？

2、內(nèi)部排序與外部排序的主要區(qū)別是什么？

3、連續(xù)順序文件排序與鏈表排序的區(qū)別是什么？

4、如何進行直接插入排序？什么情況下效率最高？最少比較多少次？移動多少次?

5、如何進行起泡排序？什么情況下效率最高？最少比較多少次？移動多少次