數(shù)據(jù)結(jié)構(gòu)與C語言程序設計題目

1、練習：1. 棧和隊列的共同特點是（只允許在端點處插入和刪除元素）2. 如果進棧序列為 e1,e2,e3,e4 ，則可能的出棧序列是（ e2,e4,e3,e1 ）3. 棧底至棧頂依次存放元素A 、B 、C、D ，在第五個元素 E 入棧前，棧中元素可以出棧，則出棧序列可能是（ DCBEA ）4. 棧通常采用的兩種存儲結(jié)構(gòu)是（線性存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)）5. 下列關(guān)于棧的敘述正確的是（ D）A. 棧是非線性結(jié)構(gòu) B.棧是一種樹狀結(jié)構(gòu) C.棧具有先進先出的特征D.棧有后進先出的特征6. 鏈表不具有的特點是（B） A.不必事先估計存儲空間B.可隨機訪問任一元素C. 插入刪除不需要移動元素D. 所需空間與

2、線性表長度成正比7. 用鏈表表示線性表的優(yōu)點是（便于插入和刪除操作）8. 在單鏈表中，增加頭結(jié)點的目的是（方便運算的實現(xiàn)）9. 循環(huán)鏈表的主要優(yōu)點是（從表中任一結(jié)點出發(fā)都能訪問到整個鏈表）10. 線性表L =（ a1,a2,a3,ai,）麗列說法正確的是（D）A. 每個元素都有一個直接前件和直接后件B. 線性表中至少要有一個元素C. 表中諸元素的排列順序必須是由小到大或由大到小D. 除第一個和最后一個元素外， 其余每個元素都有一個且只有一個直接前件和直接后件11. 線性表若采用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址（D ）A. 必須是連續(xù)的 B. 部分地址必須是連續(xù)的 C. 一定是不連續(xù)

3、的 D. 連續(xù)不連續(xù)都可以12. 線性表的順序存儲結(jié)構(gòu)和線性表的鏈式存儲結(jié)構(gòu)分別是（隨機存取的存儲結(jié)構(gòu)、順序存 取的存儲結(jié)構(gòu)）13. 樹是結(jié)點的集合，它的根結(jié)點數(shù)目是（有且只有1）14. 在深度為 5 的滿二叉樹中，葉子結(jié)點的個數(shù)為（31 ）15. 具有 3 個結(jié)點的二叉樹有（ 5 種形態(tài)）16. 設一棵二叉樹中有 3 個葉子結(jié)點，有 8 個度為 1 的結(jié)點，則該二叉樹中總的結(jié)點數(shù)為（13 ）17. 已知二叉樹后序遍歷序列是 dabec ，中序遍歷序列是 debac ，它的前序遍歷序列是 （ cedba ）18. 已知一棵二叉樹前序遍歷和中序遍歷分別為 ABDEGCFH 和 DBGEACHF

4、，則該二叉樹 的后序遍歷為（ DGEBHFCA ）19. 若某二叉樹的前序遍歷訪問順序是 abdgcefh ，中序遍歷訪問順序是 dgbaechf ，則其 后序遍歷的結(jié)點訪問順序是（ gdbehfca ）20. 數(shù)據(jù)庫保護分為：安全性控制、 完整性控制 、并發(fā)性控制和數(shù)據(jù)的恢復。1. 在計算機中，算法是指（解題方案的準確而完整的描述）2. 在下列選項中，哪個不是一個算法一般應該具有的基本特征（無窮性） 說明：算法的四個基本特征是：可行性、確定性、有窮性和擁有足夠的情報。3. 算法一般都可以用哪幾種控制結(jié)構(gòu)組合而成（順序、選擇、循環(huán)）4. 算法的時間復雜度是指（算法執(zhí)行過程中所需要的基本運算次數(shù)

5、）5. 算法的空間復雜度是指（執(zhí)行過程中所需要的存儲空間）6. 算法分析的目的是（分析算法的效率以求改進）7. 下列敘述正確的是（ C）A 算法的執(zhí)行效率與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)B 算法的空間復雜度是指算法程序中指令（或語句）的條數(shù)C 算法的有窮性是指算法必須能在執(zhí)行有限個步驟之后終止D 算法的時間復雜度是指執(zhí)行算法程序所需要的時間8. 數(shù)據(jù)結(jié)構(gòu)作為計算機的一門學科， 主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、 對各種數(shù)據(jù)結(jié)構(gòu)進行的運算， 以及（數(shù)據(jù)的存儲結(jié)構(gòu)）9. 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的（ C）A 存儲結(jié)構(gòu)B 物理結(jié)構(gòu)C 邏輯結(jié)構(gòu)D 物理和存儲結(jié)構(gòu)10. 下列敘述中，錯誤的是（ B）A 數(shù)據(jù)的

6、存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率密切相關(guān)B 數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率無關(guān)C 數(shù)據(jù)的存儲結(jié)構(gòu)在計算機中所占的空間不一定是連續(xù)的D 一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)11. 數(shù)據(jù)的存儲結(jié)構(gòu)是指（數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示）12. 數(shù)據(jù)的邏輯結(jié)構(gòu)是指（反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)）13. 根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為（線性 結(jié)構(gòu)和非線性結(jié)構(gòu)）14. 下列數(shù)據(jù)結(jié)構(gòu)具有記憶功能的是（ C） A 隊列B 循環(huán)隊列C 棧D 順序表15. 下列數(shù)據(jù)結(jié)構(gòu)中，按先進后出原則組織數(shù)據(jù)的是（ B）A 線性鏈表B 棧C 循環(huán)鏈表D 順序表16. 遞歸算法一般需要利用（隊

7、列）實現(xiàn)。17. 下列關(guān)于棧的敘述中正確的是（D ） A .在棧中只能插入數(shù)據(jù)B .在棧中只能刪除數(shù)據(jù)C.棧是先進先出的線性表D .棧是先進后出的線性表18. 棧底至棧頂依次存放元素 A、B、C、D ，在第五個元素 E 入棧前，棧中元素可以出棧， 則出棧序列可能是（ DCBEA ）19. 如果進棧序列為 e1,e2,e3,e4 ，則可能的出棧序列是（ e2,e4,e3,e1）20. 由兩個棧共享一個存儲空間的好處是（節(jié)省存儲空間，降低上溢發(fā)生的機率）21. 應用程序在執(zhí)行過程中，需要通過打印機輸出數(shù)據(jù)時，一般先形成一個打印作業(yè)，將 其存放在硬盤中的一個指定 （隊列） 中，當打印機空閑時， 就會

8、按先來先服務的方式從中取 出待打印的作業(yè)進行打印。22. 下列關(guān)于隊列的敘述中正確的是（C） A .在隊列中只能插入數(shù)據(jù)B .在隊列中只能刪除數(shù)據(jù)C 隊列是先進先出的線性表D 隊列是先進后出的線性表23. 下列敘述中，正確的是（D） A .線性鏈表中的各元素在存儲空間中的位置必須是連續(xù) 的B. 線性鏈表中的表頭元素一定存儲在其他元素的前面C.線性鏈表中的各元素在存儲空間中的位置不一定是連續(xù)的，但表頭元素一定存儲在其他元素的前面D .線性鏈表中的各元素在存儲空間中的位置不一定是連續(xù)的，且各元素的存儲順序也是任意的24. 下列敘述中正確的是（A ） A .線性表是線性結(jié)構(gòu)B .棧與隊列是非線性結(jié)構(gòu)

9、C 線性鏈表是非線性結(jié)構(gòu)D 二叉樹是線性結(jié)構(gòu)25. 線性表L =（ a1,a2,a3,ai,），2下列說法正確的是（ D）A 每個元素都有一個直接前件和直接后件B 線性表中至少要有一個元素C. 表中諸元素的排列順序必須是由小到大或由大到小D .除第一個元素和最后一個元素外， 其余每個元素都有一個且只有一個直接前件和直接后件26. 線性表若采用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址（連續(xù)不連續(xù)都可以）27. 鏈表不具有的特點是（B） A 不必事先估計存儲空間B 可隨機訪問任一元素C 插入刪除不需要移動元素D 所需空間與線性表長度成正比28. 非空的循環(huán)單鏈表 head 的尾結(jié)點（由 p 所

10、指向），滿足（ p->next=head ）29. 與單向鏈表相比，雙向鏈表的優(yōu)點之一是（更容易訪問相鄰結(jié)點）30. 在（D ）中，只要指出表中任何一個結(jié)點的位置，就可以從它出發(fā)依次訪問到表中其他所有結(jié)點。A 線性單鏈表B 雙向鏈表C 線性鏈表D 循環(huán)鏈表31. 以下數(shù)據(jù)結(jié)構(gòu)屬于非線性數(shù)據(jù)結(jié)構(gòu)的是 （C）A 隊列B 線性表C 二叉樹D 棧32. 樹是結(jié)點的集合，它的根結(jié)點數(shù)目是（有且只有 1）33. 具有 3 個結(jié)點的二叉樹有（ 5 種形態(tài)）34.在一棵二叉樹上第 8 層的結(jié)點數(shù)最多是（ 128 ）注:2K-135.在深度為 5 的滿二叉樹中,葉子結(jié)點的個數(shù)為（16)注:2n-136.在

11、深度為 5 的滿二叉樹中,共有（ 31 ）個結(jié)點。注:2n 137.設一棵完全二叉樹共有 699 個結(jié)點,則在該二叉樹中的葉子結(jié)點數(shù)為（350)說明:完全二叉樹總結(jié)點數(shù)為 N，若N為奇數(shù)，則葉子結(jié)點數(shù)為( N+1) /2 ；若N 為偶數(shù)則葉子結(jié)點數(shù)為 N/2 。38.設有下列二叉樹,對此二叉樹中序遍歷的結(jié)果是（B)A ABCDEFB DBEAFCC ABDECFD DEBFCA39.已知二叉樹后序遍歷序列是 dabec ,中序遍歷序列debac ,它的前序遍歷序列是（ cedba ）40. 已知一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF，則該二叉樹的后序遍歷為（ DG

12、EBHFCA ）41. 若某二叉樹的前序遍歷訪問順序是 abdgcefh ，中序遍歷訪問順序是 dgbaechf ，則其 后序遍歷的結(jié)點訪問順序是（ gdbehfca ）42. 串的長度是（串中所含字符的個數(shù)）43. 設有兩個串p和q，求q在p中首次出現(xiàn)位置的運算稱做（模式匹配）44. N 個頂點的連通圖中邊的條數(shù)至少為（ N-1 ）45. N 個頂點的強連通圖的邊數(shù)至少有（ N）46. 對長度為 n 的線性表進行順序查找，在最壞情況下所需要的比較次數(shù)為（N）47. 最簡單的交換排序方法是（冒泡排序）48. 假設線性表的長度為 n,則在最壞情況下，冒泡排序需要的比較次數(shù)為（n（n-1）/2 ）

13、49. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是（冒泡排序）50. 在最壞情況下,下列順序方法中時間復雜度最小的是（堆排序）51. 希爾排序法屬于（插入類排序）52. 堆排序法屬于（選擇類排序）53. 在下列幾種排序方法中,要求內(nèi)存量最大的是（歸并排序）54. 已知數(shù)據(jù)表 A 中每個元素距其最終位置不遠,為節(jié)省時間,應采用（直接插入排序）55. 算法的基本特征是可行性、確定性、 有窮性 和擁有足夠的情報。1. 一個算法通常由兩種基本要素組成： 一是對數(shù)據(jù)對象的運算和操作, 二是算法的控制結(jié)構(gòu)。1. 算法的復雜度主要包括時間復雜度和 空間 復雜度。2. 實現(xiàn)算法所需的存儲單元多少

14、和算法的工作量大小分別稱為算法的空間復雜度和時間復 雜度 。3. 所謂數(shù)據(jù)處理是指對數(shù)據(jù)集合中的各元素以各種方式進行運算，包括插入、刪除、查找、 更改等運算，也包括對數(shù)據(jù)元素進行分析。4. 數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的 數(shù)據(jù)元素 的集合。5. 數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)，線性鏈表屬于 存儲結(jié)構(gòu) 。6. 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的 邏輯 結(jié)構(gòu)和數(shù)據(jù)的存儲結(jié)構(gòu)。7. 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的 存儲結(jié)構(gòu) 以及對數(shù)據(jù)的操作運算。8. 數(shù)據(jù)元素之間的任何關(guān)系都可以用 前趨和后繼 關(guān)系來描述。9. 數(shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。10. 常用的存儲結(jié)構(gòu)有順序、鏈接、 索引 等存儲結(jié)構(gòu)。11.

15、 順序存儲方法是把邏輯上相鄰的結(jié)點存儲在物理位置 相鄰 的存儲單元中。12. 棧的基本運算有三種：入棧、退棧與讀棧頂元素 。13. 隊列主要有兩種基本運算：入隊運算與 退隊運算 。14. 在實際應用中，帶鏈的?？梢杂脕硎占嬎銠C存儲空間中所有空閑的存儲結(jié)點，這種 帶鏈的棧稱為 可利用棧 。15. 棧和隊列通常采用的存儲結(jié)構(gòu)是 鏈式存儲和順序存儲 。16. 當線性表采用順序存儲結(jié)構(gòu)實現(xiàn)存儲時，其主要特點是 邏輯結(jié)構(gòu)中相鄰的結(jié)點在存儲 結(jié)構(gòu)中仍相鄰 。17. 循環(huán)隊列主要有兩種基本運算：入隊運算與退隊運算。每進行一次入隊運算，隊尾指 針就 進 1 。18. 當循環(huán)隊列非空且隊尾指針等于對頭指針時，

16、說明循環(huán)隊列已滿，不能進行入隊運算。 這種情況稱為 上溢 。19. 當循環(huán)隊列為空時，不能進行退隊運算，這種情況稱為 下溢 。20. 在一個容量為 25 的循環(huán)隊列中，若頭指針 front=16 ，尾指針 rear=9 ，則該循環(huán)隊 列中共有 18 個元素。注：當 rearvfront時，元素個數(shù)=總?cè)萘?front rear );當 rear>front 時，元素個數(shù)= rear front 。21. 在一個容量為 15 的循環(huán)隊列中，若頭指針 front=6 ，尾指針 rear=9 ，則該循環(huán)隊列 中共有 3 個元素。22. 順序查找一般是指在 線性表 中查找指定的元素。23. 在計

17、算機中存放線性表，一種最簡單的方法是 順序存儲 。24. 在程序設計語言中，通常定義一個 一維數(shù)組 來表示線性表的順序存儲空間。25. 在鏈式存儲方式中，要求每個結(jié)點由兩部分組成：一部分用于存放數(shù)據(jù)元素值，稱為數(shù) 據(jù)域， 另一部分用于存放指針， 稱為 指針域 。其中指針用于指向該結(jié)點的前一個或后一個 結(jié)點(即前件或后件)。26. 在 線性單鏈表中 ，每一個結(jié)點只有一個指針域，由這個指針只能找到后繼結(jié)點，但不 能找到前驅(qū)結(jié)點。27. 為了要在線性鏈表中插入一個新元素，首先要給該元素分配一個新結(jié)點 ，以便用于存儲該元素的值。28. 在線性鏈表中刪除一個元素后，只需要改變被刪除元素所在結(jié)點的前一個結(jié)

18、點的指針域 即可。29. 用鏈表表示線性表的突出優(yōu)點是便于插入和刪除操作。30. 在樹形結(jié)構(gòu)中，樹根結(jié)點沒有前件 。31. 在樹結(jié)構(gòu)中，一個結(jié)點所擁有的后件個數(shù)稱為該結(jié)點的度。葉子結(jié)點的度為0 。32. 設一棵二叉樹中有 3 個葉子結(jié)點， 8 個度為 1 的結(jié)點，則該二叉樹中總的結(jié)點數(shù)為 13 。33. 設一棵完全二叉樹共有 739 個結(jié)點，則在該二叉樹中有 370 個葉子結(jié)點。34. 設一棵完全二叉樹共有 700 個結(jié)點，則在該二叉樹中有 350 個葉子結(jié)點。35. 在先左后右的原則下，根據(jù)訪問根結(jié)點的次序，二叉樹的遍歷可以分為三種：前序遍 歷、 中序 遍歷和后序遍歷。36. 若串 S="Program" ，則其子串的數(shù)目是 29 。 注： n(n+1)/2+137. 若串 S= ” MathTypes ，”則其子串的數(shù)目是 46 。38. 對長度為 n 的線性表進行插入一個