(完整word版)數(shù)據(jù)結(jié)構(gòu)練習題

1、第一章判斷題（一）1. 數(shù)據(jù)元素是數(shù)據(jù)最小單位。錯2. 數(shù)據(jù)對象就是一組數(shù)據(jù)元素的集合。錯3. 任何數(shù)據(jù)結(jié)構(gòu)都具備三個基本運算：插入、刪除和查找。錯4. 數(shù)據(jù)對象是由有限個類型相同的數(shù)據(jù)元素構(gòu)成的。對5. 數(shù)據(jù)的邏輯結(jié)構(gòu)與各數(shù)據(jù)元素在計算機中如何存儲有關(guān)。錯6. 如果數(shù)據(jù)元素值發(fā)生改變，則數(shù)據(jù)的邏輯結(jié)構(gòu)也隨之改變。錯7. 邏輯結(jié)構(gòu)相同的數(shù)據(jù)，可以采用多種不同的存儲方法。對8. 邏輯結(jié)構(gòu)不相同的數(shù)據(jù)，必須采用不同的存儲方法來儲存。錯9. 數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素的各數(shù)據(jù)項之間的邏輯關(guān)系。錯 判斷題（二）1. 順序存儲方式只能用于存儲線性結(jié)構(gòu)。錯2. 數(shù)據(jù)元素是數(shù)據(jù)最小的單位。錯3. 數(shù)據(jù)結(jié)構(gòu)是

2、帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。對4. 數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系。對節(jié)點和數(shù)5. 數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)元素、 數(shù)據(jù)項在計算機中的表示分別稱為存儲結(jié)構(gòu)、 據(jù)域。對6. 數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機內(nèi)的實際的存儲形式。對第二章判斷題一1. 分配給單鏈表的內(nèi)存單元地址必須是連續(xù)的。錯2. 與順序表相比，在鏈表中順序訪問所有節(jié)點，其算法的效率比較低。錯3. 從長度為n的順序表中刪除任何一個元素，時間復雜度都是O (n)。錯4. 向順序表中插入一個元素，平均要移動大約一半的元素。對5. 凡是為空的單鏈表都是不含任何節(jié)點的。錯6. 如果單鏈表帶有頭結(jié)點，則插入操作永遠不會改變頭節(jié)點指針的值。對7.

3、 在循環(huán)單鏈表中，任何一個節(jié)點的指針域都不可能為空。對 判斷題二1. 順序存儲方式的特點是存儲密度大且插入、刪除運算效率高。錯2. 線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈式存儲結(jié)構(gòu)。錯3. 順序存儲結(jié)構(gòu)屬于靜態(tài)結(jié)構(gòu)而鏈式存儲結(jié)構(gòu)屬于動態(tài)結(jié)構(gòu)。對4. 由于順序存儲結(jié)構(gòu)要求連續(xù)的存儲區(qū)域，所以再存儲管理上不夠靈活。對5. 對于單鏈表來說，只有從頭節(jié)點開始才能掃描表中全部節(jié)點。對6. 對于循環(huán)單鏈表來說，從表中任一節(jié)點出發(fā)都能掃描整個鏈表。對7. 雙鏈表的特點是很容易找任一節(jié)點的前驅(qū)和后繼。對第三章1. 棧底元素是不能刪除的元素。錯2. 順序棧中元素值的大小是有序的。錯3. 在 n 個元素連續(xù)進棧后，他們的出棧

4、順序和進棧順序一定正好相反。對4. 棧頂元素和棧底元素有可能是同一元素。對5. 若sm表示順序棧的存儲空間，則對棧的進棧、出棧操作最多只能進行 m次 錯6. 棧是一種對進棧、出棧操作總次數(shù)作了限制的線性表。錯7. 對順序棧進行進棧、出棧操作，不涉及元素的前、后移動問題。對8. 空棧沒有棧頂指針。錯9. 環(huán)形隊列中有多少元素，可以根據(jù)隊首指針和隊尾指針的值來計算。對10. 無論是順序隊列，還是鏈式隊列，插入、刪除運算的時間復雜度都是O(1)。對11. 隊列若用不帶頭節(jié)點的非循環(huán)單鏈表來表示鏈式隊列， 則可以用“隊首指針和 隊尾指針的值相等”作為空隊標志。錯12. 棧和隊列都是插入和刪除操作受限的

5、線性表。對13. 棧和隊列的存儲方式既可以是順序方式，也可以是鏈式方式。對14. 環(huán)形隊列也存在空間溢出的問題。對15. 消除遞歸不一定需要使用棧。對，也可用迭代第四、五、六章判斷題1. KMP 算法的最大特點是指示主串的指針不需回溯。對2. 任何遞歸算法都有遞歸出口。對3. 遞歸算法的執(zhí)行效率比功能相同的非遞歸算法的執(zhí)行效率高。錯4. 遞歸算法不能轉(zhuǎn)換成對應(yīng)的非遞歸算法。錯5. 稀疏矩陣的特點是矩陣中的元素較少。錯簡答題1. 兩個串相等的充分必要條件是什么？長度相同且對應(yīng)位置字符相等2. 二維數(shù)組A030引的元素起始地址是LOC(A 00)=100Q 個元素占用內(nèi)存單元為2,則LOC(A32)為多少。(分別計算按行、列存儲情況)按行存儲：1000+(3-0)X 4+(2-0) X 2=1028按列存儲：1000+(2-0)X 4+(3-0) X 2=1022上機操作題1順序表：已知線性表(a1,a2-an)按順序結(jié)構(gòu)存儲且每個元素為不相等的整 數(shù)。設(shè)計把所有奇數(shù)移到所有偶數(shù)前邊的算法。 (要求時間少，輔助空間少)2. 單鏈表 ：編寫算法將帶頭節(jié)點的單鏈表中值重復的節(jié)點刪除， 使所得的鏈表中 各節(jié)點值不同。3. 棧和隊列 ：編程實現(xiàn)用兩個棧模擬一個隊列的算法