數(shù)據(jù)結構復習題及答案

1、數(shù)據(jù)結構習題一、 名詞解釋1. 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)結構、數(shù)據(jù)的邏輯結構、數(shù)據(jù)物理結構、順序存儲、鏈式存儲、算法、時間復雜度、空間復雜度 。2. 線性表、順序表、單鏈表 、雙向鏈表 、循環(huán)鏈表 、雙向循環(huán)鏈表 、三個概念的區(qū)別：頭指針、頭結點、首元結點(第1個元素結點 )。3. 棧（順序棧、鏈棧）、隊列（順序隊、鏈隊）、循環(huán)隊列、遞歸、稀疏矩陣、三元組。4. 樹、葉子結點、結點的度、樹的度、樹的高(深)度、二叉樹、遍歷、滿二叉樹、完全二叉樹 、哈夫曼樹、WPL、哈夫曼編碼。5. 圖（有向、無向）、網、邊、弧、度、入度

2、、出度、完全圖（有向、無向）、（強）連通圖（分量）、（最?。┥蓸?、鄰接矩陣、鄰接表、DFS、BFS。6. 查找表、關鍵字、靜態(tài)查找、動態(tài)查找、 ASL、順序查找、折半查找、分塊查找、二叉排序樹。7、排序、內（外）排序、穩(wěn)定性、插入（直接、希爾）， 交換（起泡、快速），選擇（直接、堆），2路歸并。一、 填空題1. 數(shù)據(jù)結構是研究數(shù)據(jù)的_邏輯結構_和_物理結構_，并在這種結構上定義相關的運算，設計實現(xiàn)這些運算的算法，分析算法的效率。算法的效率包括時間和空間兩個方面，分別稱為_時間復雜度_和_空間復雜度_。學號2. 數(shù)據(jù)的基本單位是_數(shù)據(jù)元素_ ，數(shù)據(jù)的最小單位是_數(shù)據(jù)項_ 。3. 算法

3、是對特定問題求解_步驟_的一種描述，是指令的有限序列。4. 一個算法的時間復雜度為(3n3+2n7)，其數(shù)量級表示為 O（n3） _。5. 一個算法具有5個特性： 確定性 、 可行性 、 有窮性 、輸入和輸出。6. 算法性能的分析和度量，可以從算法的 時間復雜度 和 空間復雜度 來評價算法的優(yōu)劣。學號7. 數(shù)據(jù)的邏輯結構包括集合結構、 線性結構 、 樹形結構 和 圖型結構 四種類型。8. 數(shù)據(jù)結構在計算機中的表示稱為數(shù)據(jù)的 物理結構 ，它可以采用_順序存儲_或_鏈式存儲_兩種存儲方法。9. 線性表有兩種存儲結構，分別為 順序存儲 和 鏈式存儲 。10. 鏈式存儲的特點是利用 指針 來表示數(shù)據(jù)元

4、素之間的邏輯關系。姓名11. 若頻繁地對線性表進行插入和刪除操作，該線性表宜采用_鏈式存儲_存儲結構。12. 線性表中的數(shù)據(jù)元素之間具有 一對一 的線性關系，除第一個和最后一個元素外，其他數(shù)據(jù)元素有且只有 一個 直接后繼和直接前趨。13. 在一個單鏈表中p所指結點之后插入一個s所指結點時，應執(zhí)行s->next=_p->next_和p->next=_s_的操作。14. 在一個單鏈表中刪除p的后繼結點q時，應執(zhí)行以下操作p->next= q->next 。15. 對帶頭結點head的單鏈表，則判斷其為空的條件為 head->next=NULL 。16. 對帶頭結

5、點head的循環(huán)單鏈表尾結點(由p所指向)判非空的條件為 p->next=head 。17. 在棧結構中，允許插入的一端稱為 棧頂 ；在隊列結構中，允許插入的一端稱為 隊尾 。18. 隊列中元素的入隊和出隊應遵循_先進先出 _原則，數(shù)據(jù)元素1，2，3，4，5按照次序入隊后，第一個出隊的是_1 _。19. 在循環(huán)隊列中，存儲空間為0n-1。設隊頭指針front指向隊頭元素前一個空閑元素，隊尾指針指向隊尾元素，那么其隊空標志為rear=front，隊滿標志為 (rear+1)% n=front 。20. 設順序表有19個元素，第一個元素的地址為200，且每個元素占3個字節(jié)，則第14個元素的存

6、儲地址為 239 。21. 在一個長度為n的順序表中刪除第i個元素（1in），需向前移動 n-i 個元素。22. 在一個長度為n的順序表中第i個元素前（1in），插入一個元素，需向后移動 n-i+1 個元素。23. 在順序存儲的線性表中插入或刪除一個元素平均約移動表中_50%_（或一半）_的元素。24. 在順序表中訪問任意一結點的時間復雜度均為 O(1) ，因此，順序表也稱為 隨機存取 的數(shù)據(jù)結構。25. 在n個結點的單鏈表中要刪除已知結點*p，需找到它的前驅結點的地址，其時間復雜度為O（n）。26. 一個廣義表為(a,(a,b),d,e,(i,j),k)，則該廣義表的長度為_5_，深度為_3

7、_。27. 已知廣義表A=(a,b,c),(d,e,f)，則運算tail (head (tail(A)=(e,f)_。28. 已知廣義表Ls=(a,(b,c,d),e)，運用head和tail函數(shù)取出Ls中的原子b的運算是_head(head(tail(LS)_。29. 廣義表(a,b),c,d)的表頭是 (a,b) 表尾是 (c,d) 。30. 廣義表(a,b,c,d)的表頭是 a 表尾是 (b,c,d)_。31. 兩個串相等的充分必要條件是:_ 串長相等_ 且 _對應的字符相等_。32. 不含任何字符的串稱為 空串 其長度為 0 。33. 對于稀疏矩陣的壓縮存儲，通常用一個三元組表示非零元

8、素的信息，其中包括非零元素所在的 行 、 列 以及它的值。34. 若二叉樹中有20個葉子結點，則該二叉樹有 19 個度為2的結點。35. 若二叉樹中度為2的結點有15個，則該二叉樹有_16_個葉子結點。36. 深度為h且有_2h-1_個結點的二叉樹稱為滿二叉樹。37. 深度為k的二叉樹最多有 _2k-1 個結點，最少有 k 個結點，第i 層上最多有_2(i-1)_個結點。38. 深度為5的滿二叉樹共有 31 個結點，其中有_16_個葉子節(jié)點。39. 若深度為6的完全二叉樹的第6層有3個葉結點，則該二叉樹一共有 34 個結點。40. 深度為15的滿二叉樹上，第11層有 _2(11-1)=1024

9、 個結點。41. 一棵具有100個結點的完全二叉樹，它的深度為 7 ，其中度為1的結點有 1 個。42. 某二叉樹的后根遍歷序列為abd，中根遍歷序列為adb，則它的先根遍歷序列為 dab 。43. 哈夫曼樹是指對于一組帶有確定權值的葉子結點構造的具有最小帶權路徑長度 的二叉樹。44. 具有m個葉子結點的哈夫曼樹共有 2m-1 個結點。45. 已知一棵哈夫曼樹含有60個葉子結點，則該樹中共有 59 個非葉子結點。46. 在一個具有n個頂點無向完全圖中，含有 n(n-1)/2 邊；在一個具有n個頂點有向完全圖中，含有 n(n-1) 邊。一個具有4個頂點的無向完全圖有 6 條邊。47. 具有n個頂

10、點的連通圖至少需有 n-1 條邊。48. 一個連通圖的生成樹是該圖的 極小 連通子圖。若這個連通圖有n個頂點，則它的生成樹有 n-1 條邊。49. 在有向圖的鄰接矩陣中，第i行中非零元素的個數(shù)正好是第i個頂點的 出度 ；第i列中非零元素的個數(shù)正好是第i個頂點的 入度 。50. 在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的 2 倍。51. 在無向圖G的鄰接矩陣A中，若Aij等于1，則Aji等于 1 。52. 對二叉排序樹進行 中序 遍歷，可以得到按關鍵字從小到大排列的結點序列。53. 一個有序表為1，3，9，12，32，41，45，62，75，77，82，95，100，當折半查找值為82的結點時

11、，經過 4 次比較后查找成功。54. 在線性表中采用折半查找法查找一個數(shù)據(jù)元素，線性表中元素應該按值有序，并且采用_順序存儲_存儲方法。55. 在簡單選擇排序、堆排序、快速排列、歸并排序四種排序方法中，排序方法穩(wěn)定的是_歸并排序。56. 冒泡排序是一種穩(wěn)定的排序方法，對n個元素的序列進行冒泡排序時，最多需進行 n-1 趟。該排序方法的時間復雜度為 O(n2) 。57. 給定序列100，86，48，73，35，39，42，57，66，21，按堆的定義，則它一定 大根 堆。58. 數(shù)據(jù)結構是指數(shù)據(jù)及其相互之間的_一種或多種關系_。當結點之間存在M對N（M：N）的聯(lián)系時，稱這種結構為_圖狀結構_。5

12、9. 隊列的插入操作是在隊列的_隊尾_進行，刪除操作是在隊列的_隊頭_進行。60. 每次從無序表中順序取出一個元素，把它插入到有序表中的適當位置，此種排序方法叫做_直接插入_排序；每次從無序表中挑選出一個最小或最大元素，把它交換到有序表的一端，此種排序方法叫做_簡單選擇(或直接選擇)_排序。61. 二叉樹的前序遍歷序列為A，B，C，E，F(xiàn)，D，G，H，中序遍歷序列為A，E，C，F(xiàn)，B，G，H，其后序遍歷序列為_ E,F,C,G,H,D,B,A_。62. 對于一棵具有n個結點的二叉樹，若一個結點的編號為i(0in-1），則它的左孩子結點的編號為 2i ，右孩子結點的編號為 2i+1 ，雙親結點的

13、編號為 i/2 。 63. 在一個具有6個頂點的無向完全圖中，包含有 15 條邊，在一個具有6個頂點的有向完全圖中，包含有 30 條弧。64. 快速排序在平均情況下的時間復雜度為_O(nlog2n)_，在最壞情況下的時間復雜度為_ O(n2)_。65. 從一棵二叉排序樹中查找一個元素時，若元素的值等于根結點的值，則表明_查找成功_，若元素的值小于根結點的值，則繼續(xù)向_左子樹_查找，若元素的大于根結點的值，則繼續(xù)向_右子樹_查找。66. 在循環(huán)單鏈表中，最后一個結點的指針域指向_首_結點。67. 假定一棵樹的廣義表表示為A（C，D（E，F(xiàn)，G），H（I，J），則樹中所含的結點數(shù)為_9_個，樹的深

14、度為_3_，樹的度為_3_。68. 通常從四個方面評價算法的質量：_正確性_、_可讀性_、_健壯性_和_效率與低存儲量需求_。69. 假設一棵完全二叉樹含1000個結點,則其中度為2的結點數(shù)為_499_。70. 一個算法的時間復雜度為(3n3+2n7)(5n)，其數(shù)量級表示為 O(n2) 。71. 在快速排序、堆排序和歸并排序中，最壞時間復雜度為O(n2)的排序算法有_快速排序_。72. 數(shù)據(jù)結構被形式地定義為（D, R），其中D是 數(shù)據(jù)元素 的有限集合，R是D上的 關系 有限集合。 73. 在歸并排序中，進行每趟歸并的時間復雜度為_O(n)_，整個排序過程的時間復雜度為_O(nlog2n)_

15、，空間復雜度為_ O(n)_。74. 若一棵二叉樹有10個葉結點，則該二叉樹中度為2的結的點個數(shù)為_9_。 75. 對用鄰接矩陣表示的具有n個定點和e條邊的圖進行任一種遍歷時，其時間復雜度為 O(n2) ，對用鄰接表表示的圖進行任一種遍歷時，其時間復雜度為_ O(n+e) _。76. 從有序表（12，18，30，43，56，78，82，95）中依次二分查找43和56元素時，其查找長度分別為_1_和_3_。77. 對于一棵具有n個結點的二叉樹，用二叉鏈表存儲時，其指針總數(shù)為_2n_個，其中_ n-1_個用于指向孩子， n+1_個指針是空閑的。78. 從邏輯結構看，線性表是典型的_線性結構_，樹是

16、典型的_非線性結構_。79. 設二叉樹中結點的兩個指針域分別為lchild和rchild，則判斷指針變量p所指向的結點為葉子結點的條件是_p->lchild=NULL && p->rchild=NULL 。80. 棧是一種_先進后出_表。隊列又稱為_先進先出_表。81. 若對序列(49，38，65，97，76，13，27，50)采用直接選擇排序法排序，則第三趟結束后序列的狀態(tài)是_(13,27,38),97,76,49,65,50_。82. 利用關鍵碼分別為10， 20， 30， 40的四個結點，能構造出_14_種不同的二叉排序樹.83.

17、 設表中元素的初始狀態(tài)是按鍵值遞增的，分別用堆排序、快速排序、冒泡排序和歸并排序方法對其進行（按遞增排序），_冒泡排序_最省時間， _快速排序_最費時間。84. 空串的長度是_0_；空格串的長度是_空格的個數(shù)_。串中所含字符個數(shù)稱為該串的_長度_.85. 在n個結點的單鏈表中，在P指向的結點之后插入一個結點的時間復雜度為_ O(n)_。86. 設SQ為循環(huán)隊列，存儲在數(shù)組dm中，則SQ出隊操作對其隊頭指針front的修改是_ front=（front+1）% m_。87. 樹的度是指_樹內各結點的度_的最大值。88. 已知鏈棧的結點結構為棧頂指針為top，則實現(xiàn)將指針p所指結點插入棧頂?shù)恼Z句依

18、次為_ _p->next=top_和_top=p_。89. 堆排序的空間復雜度_ O(1)_。90. 深度為n(n>0)的二叉樹最多有_2n-1_個結點。91. 設關鍵字序列為(Kl，K2，Kn)，則用篩選法建初始堆必須從第_ n/2_個元素開始進行篩選。92. 圖有_鄰接矩陣_ 、_鄰接表_等存儲結構，遍歷圖有 _深度優(yōu)先搜索_ 、 _廣度優(yōu)先搜索_等方法。93. 在一個有向圖的鄰接表中，一個頂點的鏈表中結點的個數(shù)等于這個頂點的_出度_ ，在逆鄰接表中，一個頂點的鏈表中結點的個數(shù)等于這個頂點的_入度_ 。94. 對于有10個元素的有序表采用二分查找，需要比較3次方可找到其對應的鍵

19、值，則該元素在有序表中的位置可能是_1，3，6，9_。95. 折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它將依次與表中元素_比較大小。96. 在對一組記錄關鍵字（54，38，96，23，15，72，60，45，83）進行冒泡排序時，整個冒泡排序過程中需進行_8_趟才能完成。97. 對關鍵字序列(52，80，63，44，48，91)進行一趟快速排序之后得到的結果為_48，44，52，63，80，91_。98. 在堆排序和快速排序中，若初始記錄接近正序或反序，則選用_堆排序_；若初始記錄基本無序，則最好選用_快速排序_。99. 在對一組記錄（5

20、4，38，96，23，15，72，60，45，83）進行直接插入排序時，當把第7個記錄60插入到有序表時，為尋找插入位置至少需比較 _3_次。100. 設一組記錄關鍵字序列為(80，70，33，65，24，56，48)，則用篩選法建成的初始堆為_（80，70，56，65，24，33，48）或_(24，65，33，80，70，56，48)。二、單選題1. 在數(shù)據(jù)結構中，數(shù)據(jù)的基本單位是( )A. 數(shù)據(jù)項 B. 數(shù)據(jù)元素C. 數(shù)據(jù)對象 D. 數(shù)據(jù)文件2. 數(shù)據(jù)結構是（）A一種數(shù)據(jù)類型 B數(shù)據(jù)的存儲結構C一組性質相同的數(shù)據(jù)元素的集合D相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合3. 在數(shù)據(jù)結構的討

21、論中把數(shù)據(jù)結構從邏輯上分為（  ）. A. 內部結構與外部結構              B. 靜態(tài)結構與動態(tài)結構 C. 線性結構與非線性結構            D. 緊湊結構與非緊湊結構。4. 算法指的是（   ）。A計算機程序    

22、0;         B解決問題的計算方法   C排序算法                D解決問題的有限運算序列5. 算法分析的目的是（）A辨別數(shù)據(jù)結構的合理性 B評價算法的效率C研究算法中輸入與輸出的關系 D鑒別算法的可讀性6. 某程序的時間復雜度為（3n+nlog2n+n2+8）, 其數(shù)量級表示為（ ）。AO（n） BO（nlog2n） CO

23、（n2） DO（log2n）7. for（i=0；i<n；i+） for（j=0；j<n；j+） Aij=i*j； 上述程序段的時間復雜度為( )A.O（n2） B.O（n） C.O（2n） D.O（1）8. 以下數(shù)據(jù)結構中哪一個是非線性結構？( )A. 隊列 B. 棧 C. 線性表 D. 二叉樹9. 設順序表有9個元素，則在第3個元素前插入一個元素所需移動元素的個數(shù)為( )A.5 B.6 C.7 D.910. 線性表采用鏈式存儲結構時，要求內存中可用存儲單元的地址( )A. 必須是連續(xù)的 B. 必須是部分連續(xù)的 C. 一定是不連續(xù)的 D. 連續(xù)和不連續(xù)都可以11. 線性表是具有相

24、同數(shù)據(jù)類型的n個_的有限序列。A.數(shù)據(jù)項 B.數(shù)據(jù)元素 C.表元素 D.字符 12. 在一個具有n 個結點的有序單鏈表中插入一個新結點并仍然保持有序的時間復雜度是_。A. O(1) B. O(n) C. O(n2) D. O(nlog2n)13. 用鏈接方式存儲的隊列，在進行插入運算時（）A. 僅修改頭指針 B. 頭、尾指針都要修改 C. 僅修改尾指針 D.頭、尾指針可能都要修改14. 在長度為n的順序表中刪除第i個元素(1in)時，元素移動的次數(shù)為( )A. n-i+1 B. i C. i+1 D. n-i15. 若帶頭結點的單鏈表的頭指針為head，則該鏈表為空的判定條件是( )A. he

25、ad=NULL B. head->next=NULLC. head!=NULL D. head->next=head16. 已知棧的最大容量為4。若進棧序列為1，2，3，4，5，6，且進棧和出?？梢源┎暹M行,則可能出現(xiàn)的出棧序列為（）A.5，4，3，2，1，6 B.2，3，5，6，1，4C.3，2，5，4，1，6 D.1，4，6，5，2，317. 若某線性表中最常用的操作是取第i 個元素和找第i個元素的前趨元素，則采用（      ）存儲方式最節(jié)省時間。A單鏈表     B.雙鏈表  

26、;     C.單向循環(huán)       D.順序表18.  對一個算法的評價，不包括如下（   ）方面的內容。 A健壯性和可讀性     B并行性      C正確性     D時空復雜度19. 隊列的刪除操作是在（ ）進行。A隊首 B隊尾 C隊前 D對后20. 計算機識別、存儲和加工處理的對象被統(tǒng)稱為( )A.數(shù)據(jù) B.數(shù)據(jù)元素C.數(shù)據(jù)結

27、構 D.數(shù)據(jù)類型21. 串是任意有限個（       ）符號構成的序列        符號構成的集合字符構成的序列        字符構成的集合22. 如果以鏈表作為棧的存儲結構，則退棧操作時（      ） 必須判別棧是否滿     對棧不作任何判別 必須判別棧是否空 

28、0;   判別棧元素的類型 23. 二分查找要求被查找的表是（      ）  鍵值有序的鏈接表     鏈接表但鍵值不一定有序 鍵值有序的順序表     順序表但鍵值不一定有序24. 當初始序列已經按鍵值有序，用直接插入算法對其進行排序，需要循環(huán)的次數(shù)為（      ）n2       nlog2n

29、60;     log2n          n-125. 堆是一個鍵值序列k1,k2, kn,對i=1,2,|_n/2_|,滿足(      )kik2ik2i+1                ki<k2i+1<k2ikik2i且kik2i+1(2i+1

30、n)   kik2i 或kik2i+1(2i+1n)26. 隊列的插入操作是在（ ）進行。A隊首 B隊尾 C隊前 D對后27. 一棵具有層滿二叉樹中節(jié)點總數(shù)為（）。A、 B、 C、 D、28. 快速排序在最壞情況下的時間復雜度為（  ）。 AO(log2n)      BO(nlog2n)       C0(n)         D0(n2)29. 廣義表是線性表的推廣，它們之

31、間的區(qū)別在于( )。A能否使用子表 B能否使用原子項 C表的長度 D是否能為空30. 如果某圖的鄰接矩陣是對角線元素均為零的上三角矩陣，則此圖是( )。 A.有向完全圖 B.連通圖C.強連通圖 D.有向無環(huán)圖31. 對n個關鍵字的序列進行快速排序，平均情況下的空間復雜度為( ) A.O(1) B.O(log2n) C.O(n) D.O(n log2n)32. 與線性表相比，串的插入和刪除操作的特點是（） A.通常以串整體作為操作對象 B.需要更多的輔助空間 C.算法的時間復雜度較高 D.涉及移動的元素更多33. 假設帶頭結點的單向循環(huán)鏈表的頭指針為head,則該鏈表為空的判定條件是（）。A.h

32、ead= =NULL B.head>next= =NULLC.head!=NULL D.head>next= =head34. 在單鏈表中，指針p指向值為x的結點，能實現(xiàn)“刪除x的后繼”的語句是_。A. p=p->next ; B. p=p->next->next ;C. p->next=p ; D. p->next=p->next->next ;35. 一個棧的入棧序列是a，b，c，d，e，則棧的輸出序列不可能是( )A. dceab B. decba C. edcba D. abcde36. 若進棧序列為a，b，c，進棧過程中允許出棧，

33、則以下_是不可能得到的出棧序列。A. a,b,c B. b,a,c C. c,a,b D. c,b,a37. 若進棧序列為，進棧過程中允許出棧，則可能的出棧序列是_。A. ， B. ， C. ， D. ，38. 設有一個棧，按A、B、C、D的順序進棧，則可能為出棧序列的是( )A.DCBA B.CDAB C.DBAC D.DCAB39. 一個隊列的入隊序列是1，2，3，4，則隊列的輸出序列是( )A. 4,3,2,1 B. 1,2,3,4 C. 1,4,3,2 D. 3,2,4,140. 一個最多能容納m個元素的順序存儲循環(huán)隊列Q，其頭尾指針分別為front和rear，則判定該隊列為滿的條件是

34、_A. (Q.rear+1)%m= =Q.front B. Q.front= =Q.rearC. Q.rear+1= =Q.front D. (Q.front+1)%m= =Q.rear41. 設數(shù)組Datam作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作的語句為（       ）.A.front=front+1         B.front=(front+1)% m C.rear=(rear+1)%m &

35、#160;     D.front=(front+1)%(m+1)42. 假設以數(shù)組An存放循環(huán)隊列的元素，其頭、尾指針分別為front和rear。若設定尾指針指向隊列中的隊尾元素，頭指針指向隊列中隊頭元素的前一個位置，則當前存于隊列中的元素個數(shù)為( )A.(rear-front-1)n B.(rear-front)nC.(front-rear+1)n D.(rear-front+n)n43. 若用一個大小為6的一維數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3。當從隊里中刪除一個元素，再加入兩個元素后，rear和front的值分別是（）

36、A. 1和5 B. 5和1 C. 2和4 D. 4和244. 兩個字符串相等的條件是（ ）A. 串的長度相等 B. 含有相同的字符集C. 都是非空串 D. 串的長度相等且對應的字符相同45. 如下陳述中正確的是_。A串是一種特殊的線性表    B串的長度必須大于零C串中元素只能是字母     D空串就是空格串46. 一棵含18個結點的二叉樹的高度至少為_。A. 3 B. 4 C. 5 D. 647. 將一棵有40個結點的完全二叉樹從上到下，從左到右依次對結點進行編號，根結點的編號為1，則編號為15的結點的左孩子的編號為_。

37、A. 16    B. 30 C. 31    D.3248. 在程序的執(zhí)行過程中，對實現(xiàn)函數(shù)的遞歸調用應該借助于_結構。A. 線性表 B. 棧 C . 隊列 D. 樹49. 具有100個結點的完全二叉樹的深度為_。A.6 B. 7 C. 8 D. 950. 已知二叉樹的先序遍歷序列為ABDECF，中序遍歷序列為DBEAFC，則后序遍歷序列為_。ADEBAFCBDEFBCA CDEBCFA DDEBFCA51. 如果在數(shù)據(jù)結構中每個數(shù)據(jù)元素只可能有一個直接前驅，但可以有多個直接后繼，則該結構是( )A. 棧 B. 隊列 C. 樹 D. 圖52.

38、 已知一棵含50個結點的二叉樹中只有一個葉子結點，則該樹中度為1的結點個數(shù)為（ ）A. 0 B. 1 C. 48D. 4953. 具有100個結點的完全二叉樹，其中含有_個度為1的結點。A.1 B. 0 C. 2 D. 不確定54. 已知二叉樹的先序遍歷序列為ABCD，中序遍歷序列為BCDA，則后序遍歷序列為_。AABCD BBCDA CCDBA DDCBA55. 對一棵有100個結點的完全二叉樹按層序編號，則編號為49的結點，它的左孩子的編號為（ ）A.99 B.98 C.97 D.5056. 有m個葉子結點的哈夫曼樹，其結點總數(shù)是（ ）A.2m-1 B.2m C.2m+1 D.2(m+1)

39、57. 無向圖的鄰接矩陣是一個_。A.對稱矩陣  B.零矩陣  C.上三角矩陣   D.對角矩陣58. 廣義表中元素分為( )A原子元素 B表元素 C原子元素和表元素 D任意元素59. 廣義表A=( )，(a)，(b，(c，d)的長度為( ) .A2 B3 C4 D560. 廣義表A：( )，(a)，(b，(c，d)的深度為( ) .A2 B3 C4 D561. 若用鄰接矩陣表示一個有向圖，則其中每一列包含的1的個數(shù)為（）A圖中每個頂點的入度B圖中每個頂點的出度C圖中弧的條數(shù) D圖中連通分量的數(shù)目62. 鄰接矩陣為對稱矩陣的圖是( )A. 有向

40、圖 B. 帶權有向圖 C. 有向圖或無向圖 D. 無向圖63. 在一個具有n個頂點的無向圖中，要連通全部頂點至少需要的邊數(shù)為( )A. n/2 B. n C. n-1 D. n+164. 下面的序列中_是大根堆。A.1,2,8,5,3,9,10,4 B.1,5,10,6,7,8,9,2C.9,8,7,6,4,8,2,1 D.9,8,7,6,5,4,3,165. 一組記錄的關鍵碼為(46，79，56，38，40，84)，則利用快速排序方法，以第一個記錄為基準得到的一次劃分結果為_。A.38，40，46，56，79，84     B.40，38，46，79，

41、56，84C.40，38，46，56，79，84  D.40，38，46，84，56，7966. 對關鍵字序列（5，1，4，3，7，2，8，6）進行快速排序時，以第一個元素5為基準的一次劃分的結果為（）A（1，2，3，4，5，6，7，8） B（1，4，3，2，5，7，8，6）C（2，1，4，3，5，7，8，6） D（8，7，6，5，4，3，2，1）67. 使用折半查找，線性表必須_。.以順序方式存儲.以順序方式存儲，且元素已按值排好序.以鏈式方式存儲.以鏈式方式存儲，且元素已按值排好序68. 已知8個元素（34，76，45，18，26，54，92，65），按照依次插入結點的方法生成一

42、棵二叉排序樹，則該樹的深度為（ ）A.4 B.5 C.6 D.769. 若有序表的關鍵字序列為（b,c,d,e,f,g,q,r,s,t），則在折半查找關鍵字b的過程中，先后進行比較的關鍵字依次為（）Af,c,b Bf,d,b Cg,c,b Dg,d,b70. 在對查找表的查找過程中，若被查找的數(shù)據(jù)元素不存在，則把該數(shù)據(jù)元素插入到集合中。這種方式主要適合于( )A.靜態(tài)查找表B.動態(tài)查找表C.靜態(tài)查找表與動態(tài)查找表D.靜態(tài)查找表或動態(tài)查找表71. 有一個有序表為：(2,5,8,11,15,16,22,24,27,35,50)當折半查找值為24的結點時，經過_次比較后查找成功。A. 1 B. 2

43、C. 3 D. 472. 有一個有序表為：(21,32,41,45,62,75,77,82,95),當折半查找值為82的結點時，經過_次比較后查找成功。A. 1 B. 2 C. 4 D. 373. 下面排序算法的時間復雜度最小的是_。A直接插入排序 B簡單選擇排序 C冒泡排序 D快速排序74. 以下排序方法中，穩(wěn)定的排序方法是_。A. 直接插入排序和冒泡排序 B. 簡單選擇排序和歸并排序 C. 冒泡排序和快速排序 D. 堆排序和基數(shù)排序75. 按排序過程中依據(jù)的原則分類，快速排序屬于( )A.插入類的排序方法B.選擇類的排序方法C.交換類的排序方法 D.歸并類的排序方法76. 在一棵二叉排序樹

44、中，若左子樹不空，左子樹上所有結點的值均（ ）根結點的值。A大于 B小于 C不小于 D大于等于75. 用鄰接表表示圖進行深度優(yōu)先遍歷時，通常是采用（）來實現(xiàn)算法的。A棧 B. 隊列 C. 樹 D. 圖 76. 用鄰接表表示圖進行廣度優(yōu)先遍歷時，通常是采用（）來實現(xiàn)算法的。A棧 B. 隊列 C. 樹 D. 圖 77.從一個順序隊列刪除元素時，首先要（）。A前移一位隊首指針 B.后移一位隊首指針C.取出隊首指針所指位置上的元素 D.取出隊尾指針所指位置上的元素78.在一個具有n個頂點的無向圖中，要連通所有頂點則至少需要（ ）條邊。An B2n Cn-1 Dn+1 79.在有向圖的鄰接表存儲表示中，

45、頂點V在鏈表結點中出現(xiàn)的次數(shù)是（    ）。A.頂點V的入度    B.頂點V的出度C.頂點V的度      D.依附于頂點V的邊的數(shù)目80.由權值分別為3,6,7,2,5的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為（ ）。A74 B23 C51 D5381.設串sl=Data Structures with ，s2=it，則子串定位函數(shù)index的值為（）。A15 B16 C17 D1882.一棵深度為6的二叉樹至多有（      ）個結點。 

46、0; A64       B32      C31       D6383. 將含100個結點的完全二叉樹從根這一層開始，每層上從左到右依次對結點編號，根結點的編號為1，編號為49的結點X的雙親編號為（     ）。A24      B25       C23 

47、60;    D無法確定84. 樹的后根遍歷與其轉換的相應二叉樹的（    ）遍歷的結果序列相同。A.先序    B.中序    C.后序    D.層次遍歷85. 鏈表適用于（    ）查找A順序 B二分法 C順序，也能二分法 D隨機86. 折半查找有序表6,15,30,37,65,70,72,89,99,若要查找元素37，需要依次與表中元素_進行比較。A. 65，15，37 B. 68，30，37 C. 65，15，30 D. 65，15，30，378

48、7下列排序方法中，穩(wěn)定的排序方法為（）。A.希爾排序 B.堆排序 C.快速排序 D.直接插入排序88當利用大小為N 的數(shù)組順序存儲一個棧時，假定用top = = N表示?？?，則退棧時，用（ ）語句修改top指針。Atop+; Btop=0; Ctop-; Dtop=N;89在順序表中，只要知道_，就可在相同時間內求出任一結點的存儲地址。A基地址 B結點大小 C向量大小 D基地址和結點大小90在一棵二叉樹中，第4層上的結點數(shù)最多為（ ）。A31 B8 C15 D1691線性表的順序存儲結構是一種_的存儲結構。A隨機存取 B順序存取 C索引存取D散列存取92.數(shù)據(jù)結構在計算機內存儲器中的表示是指（

49、    ）A.數(shù)據(jù)結構    B.數(shù)據(jù)元素之間的關系C.數(shù)據(jù)的邏輯結構 D.數(shù)據(jù)的物理存儲結構93. 下述幾種排序方法中，要求內存最大的是（    ）. 插入排序 .快速排序 . 歸并排序 . 選擇排序94.若長度為n的線性表采用順序存儲結構，則在表中第i個位置（1<=i<=n+1）插入一個新元素的算法的時間復雜度為（    ）A.O(0)    B.O(1)    C.O(n)    D.O(n2)95.一個棧的輸入序列為ABCDE，則不可能

50、出現(xiàn)的輸出序列是（    ）A.ABCDE    B.EDCBA    C.CABED    D.BADCE96. 對序列（22，86，19，49，12，30，65，35，18）進行一趟排序后得到的結果如下：（18，12，19，22，49，30，65，35，86），則可以認為使用的排序方法是（）A選擇排序B冒泡排序 C快速排序D插入排序97.對二叉樹的結點從1開始編號，要求每個結點的編號大于其左孩子（如果有的話）的編號，而小于其右(孩子如果有的話）的編號，則可以采用（    ）次序的遍歷實現(xiàn)二叉

51、樹的結點編號A.先序    B.中序    C.后序    D.層次遍歷98. _是一棵滿二叉樹。A二叉排序樹 B深度為5有31個結點的二叉樹C有15個結點的完全二叉樹D哈夫曼（Huffman）樹99.某二叉樹結點的中序序列為BDAECF,后序序列為DBEFCA,則該二叉樹對應的森林包括（    ）棵樹A.1    B.2    C.3    D.4100. 下面關于圖的存儲的敘述中正確的是（ ）A.用鄰接矩陣法存儲圖，占用的存儲空間大小與圖中結點個數(shù)和邊

52、數(shù)都有關B.用鄰接矩陣法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關，而與結點個數(shù)無關C.用鄰接表法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關，而與結點個數(shù)無關D.用鄰接表法存儲圖，占用的存儲空間大小與圖中邊數(shù)和結點個數(shù)都有關三、判斷題：（對的打P，錯的打O）（ O ） 1.數(shù)據(jù)元素是數(shù)據(jù)處理的最小單位。（ P ） 2.數(shù)據(jù)項是數(shù)據(jù)處理的最小單位。（ O ） 3.線性表的順序存儲結構優(yōu)于鏈式存儲結構。（ P ） 4.順序存儲的線性表可以隨機訪問,鏈式存儲的線性表只能順序訪問。（ O ） 5.在線性表的順序存儲結構中,邏輯上相鄰的兩個元素在物理位置上不一定相鄰。（ O ） 6.線性表的順序存儲和鏈

53、式存儲都必須占用內存中的連續(xù)存儲單元。（ P ） 7.棧和隊列的存儲方式,既可以順序存儲也可以鏈式存儲。（ P ） 8.棧和隊列都是操作受限制的線性表。（ P ） 9.棧的特點是先進后出,隊列的特點是先進先出。（ P ） 10.空串是任意串的子串。（ O ） 11.串中任意個字符組成的子序列稱為該串的子串。（ O ） 12.樹型結構中每個結點都有一個直接前趨。（ O ） 13.二叉樹中每個結點的度最大為2,因此二叉樹是一種特殊的樹。（ O ） 14.滿二叉樹中存在度為1的結點。（ O ） 15.完全二叉樹中每個結點或者沒有孩子或者有2個孩子。（ P ） 16.在任意一棵二叉樹中,葉子結點的個數(shù)

54、等于度為2結點的個數(shù)加1。（ P ） 17.由樹轉化為二叉樹,其根結點的右子樹總是空的。（ O ） 18.最小生成樹是指邊數(shù)最少的生成樹。（ P ） 19. 一棵哈夫曼樹有m 個葉子結點,則其結點總數(shù)為2m-1。（ O ） 20.樹的先根遍歷序列等同于該樹對應的二叉樹中序遍歷序列。（ O ） 21. “順序查找法”是指在順序表上進行查找的方法。（ O ） 22.快速排序在任何情況下圴可得到最塊的排序效果。（ P ） 23.在有向圖中每個頂點的度等于各頂點的入度與出度之和。（ O ） 24.二叉排序樹是用來進行排序的。（ P ） 25.衡量排序算法的兩個主要性能指標是執(zhí)行排序算法所需要的時間和執(zhí)

55、行排序算法所需要的附加空間。（  P  ） 26.哈夫曼樹是帶權值的樹,且權值較大的結點離樹較近。1雙鏈表中至多只有一個結點的后繼指針為空。（ P   ）2在循環(huán)隊列中，front指向隊列中第一個元素的前一位置，rear指向實際的隊尾元素，隊列為滿的條件是front=rear。（ O    ）3對鏈表進行插入和刪除操作時，不必移動結點。（ P      ）4?？梢宰鳛閷崿F(xiàn)程序設計語言過程調用時的一種數(shù)據(jù)結構。（  P   ）5線性表的邏輯順序與物理順序總是一致的。（ O）6對有向圖G，如果從任一頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先搜索就能訪問每個頂點，則該圖一定是完全圖。( &#