數(shù)據(jù)結(jié)構(gòu)判斷題

1、一、判斷題（每題1分,共131分）1. 線性表的邏輯順序總是與其物理順序一致。（）【答案】錯2. 線性表的順序存儲優(yōu)于鏈?zhǔn)酱鎯?。（）【答案】錯3. 在長度為n的順序表中，求第i個元素的直接前驅(qū)算 法的時間復(fù)雜度為0（ 1 ）。（）【答案】對4. 若一棵二叉樹中的結(jié)點均無右孩子，則該二叉樹的中根遍歷和后根遍歷序列正好相反。（）【答案】錯5順序表和一維數(shù)組一樣，都可以按下標(biāo)隨機（或直接）訪問。（）【答案】對6. 內(nèi)部排序是指排序過程在內(nèi)存中進(jìn)行的排序。（）【答案】對7. 當(dāng)待排序序列初始有序時，簡單選擇排序的時間復(fù)雜性為0（n）。（）【答案】錯8. 用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情 況

2、下，所占用的存儲空間大小只與圖中的頂點個數(shù)有關(guān)， 而與圖的邊數(shù)無關(guān)。（）【答案】對9. 任何一棵二叉樹的葉結(jié)點在三種遍歷中的相對次序是不變的。（）【答案】對10. 若將一批雜亂無章的數(shù)據(jù)按堆結(jié)構(gòu)組織起來 , 則堆中數(shù)據(jù)必然按從小到大的順序線性排列。 （）【答案】錯11. 如果采用如下方法定義一維字符數(shù)組：int maxSize = 30;char * a = new charmaxSize;則這種數(shù)組在程序執(zhí)行過程中不能擴充。（）【答案】錯12. 使用三元組表示稀疏矩陣中的非零元素能 節(jié)省存儲空間。（）【答案】對13. 對稀疏矩陣進(jìn)行壓縮存儲是為了節(jié)省存儲空間。（）【答案】對14. 當(dāng)向一個最

3、小堆插入一個具有最小值的元素時，該 元素需要逐層向上調(diào)整，直到被調(diào)整到堆頂位置為止。（）【答案】對15. 哈希查找法中解決沖突問題的常用方法是除留余數(shù)法。（）【答案】錯16. 對具有n個結(jié)點的堆進(jìn)行插入一個元素運算的 時間復(fù)雜度為0（n）。（）【答案】錯17. 堆排序是一種穩(wěn)定的排序算法。（）【答案】錯18. 如果有向圖中各個頂點的度都大于 2,則該圖 中必有回路。（）【答案】錯19. 在一個順序存儲的循環(huán)隊列中，隊頭指針指向隊頭元素的后一個位置。（）【答案】錯20. 對平衡二叉樹進(jìn)行中根遍歷，可得到結(jié)點的有序排列。（）【答案】對21. 在一棵二叉樹中，假定每個結(jié)點只有左子女，沒有 右子女，對

4、它分別進(jìn)行前序遍歷和中根遍歷，則具有相 同的結(jié)果。（）【答案】錯22. 拓?fù)渑判蚴侵附Y(jié)點的值是有序排序的。（）【答案】錯23. 在散列法中采取開散列（鏈地址）法來解決沖 突時，其裝載因子的取值一定在（0,1）之間。（）【答案】錯24. 在一棵具有n個結(jié)點的線索二叉樹中，每個結(jié)點的 指針域可能指向子女結(jié)點，也可能作為線索，使之指向 某一種遍歷次序的前驅(qū)或后繼結(jié)點，所有結(jié)點中作為線索使用的指針域共有n個（）【答案】錯25. 圖的深度優(yōu)先搜索是一種典型的回溯搜索的例子，可以通過遞歸算法求解。（）【答案】對26. 對二叉排序樹進(jìn)行中根遍歷，可得到結(jié)點的有序排列。（）【答案】對27. 任何一棵二叉樹的葉

5、結(jié)點在三種遍歷中的相對 次序是不變的。（）【答案】對28. 邊數(shù)很少的稀疏圖，適宜用鄰接矩陣表示。（） 【答案】錯29. 二叉樹是一棵無序樹。（）【答案】錯30. 對于一棵具有n個結(jié)點，其高度為h的二叉樹，進(jìn)行任一種次序遍歷的時間復(fù)雜度為0（n）。（）【答案】對31. 當(dāng)待排序序列初始有序時，快速排序的時間復(fù)雜性為 0（n）。（）【答案】錯32. 順序表的空間利用率高于鏈表。（）【答案】對33. 采用不同的遍歷方法， 所得到的無向圖的生成樹 是不同的。（）【答案】對34. 有回路的有向圖不能完成拓?fù)渑判?。（）【答案】?5. 存在這樣的二叉樹，對它采用任何次序的遍歷， 結(jié)果相同。（）【答案】對

6、36. 裝載因子是散列表的一個重要參數(shù)，它反映了 散列表的裝滿程度。（）【答案】對37. 算法分析的目的是找出數(shù)據(jù)結(jié)構(gòu)的合理性。（）【答案】錯38. 單鏈表可以實現(xiàn)隨機存取。（）【答案】錯39. 邊數(shù)很多的稠密圖，適宜用鄰接矩陣表示。（）【答案】對40. 理想情況下哈希查找的等概率查找成功的平 均查找長度是0（ 1）。（）【答案】對41. 邊數(shù)很少的稀疏圖，適宜用鄰接表表示。（）【答案】對42. 對于同一組關(guān)鍵碼互不相同的記錄，若生成 二叉搜索樹時插入記錄的次序不同則得到不同形 態(tài)的二叉搜索樹。（）【答案】對43. 強連通分量是有向圖中的極大強連通子圖。（）【答案】對44. 哈希查找法中解決沖

7、突問題的常用方法是除留余數(shù)法。（）【答案】錯45. 順序查找法適用于存儲結(jié)構(gòu)為順序或鏈接存儲的線性表。（）【答案】對46. 若讓元素1,2,3依次進(jìn)棧，則出棧次序1,3,2是不可能出現(xiàn)的情況。（）【答案】錯47. 在線性鏈表中刪除中間的結(jié)點時，只需將 被刪結(jié)點釋放。（）【答案】錯48. 線性表若采用鏈?zhǔn)酱鎯Ρ硎?，在刪除時不 需要移動元素。（）【答案】對49. 對任何用頂點表示活動的網(wǎng)絡(luò)（A0V網(wǎng)）進(jìn)行 拓?fù)渑判虻慕Y(jié)果都是唯一的。（）【答案】錯50. 鄰接矩陣適用于稠密圖（邊數(shù)接近于頂點數(shù)的 平方），鄰接表適用于稀疏圖（邊數(shù)遠(yuǎn)小于頂點數(shù) 的平方）。（）【答案】對51. 算法和程序原則上沒有區(qū)別，

8、在討論數(shù)據(jù) 結(jié)構(gòu)時二者是通用的。（）【答案】錯52. 在一棵B樹中，所有葉結(jié)點都處在同一層上， 所有葉結(jié)點中空指針數(shù)等于所有關(guān)鍵碼的總數(shù)加1。（）【答案】對53. 循環(huán)鏈表的結(jié)點與單鏈表的結(jié)點結(jié)構(gòu)完全相同，只是結(jié)點間的連接方式不同。（）【答案】對54. 能夠在鏈接存儲的有序表上進(jìn)行折半查找，其 時間復(fù)雜度與在順序存儲的有序表上相同。 （）【答案】錯55. 在一棵二叉樹中，假定每個結(jié)點只有左子女，沒有 右子女，對它分別進(jìn)行中序遍歷和后序遍歷，則具有相 同的結(jié)果。（）【答案】對56. 一個無向連通圖的生成樹是圖的極小的連通子 圖。（）【答案】對57. 對稀疏矩陣進(jìn)行壓縮存儲是為了節(jié)省存儲空間。（）

9、【答案】對58. 快速排序的時間復(fù)雜性不受數(shù)據(jù)初始狀態(tài)影響， 恒為 O（nlog2n）。（【答案】錯59. 兩個棧共享一片連續(xù)內(nèi)存空間時，為提高內(nèi)存利用率，減少溢出機會，應(yīng)把兩個棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。（）【答案】對60. 只有用面向?qū)ο蟮挠嬎銠C語言才能描述數(shù) 據(jù)結(jié)構(gòu)算法。（）【答案】錯61. 如果無向圖中每個頂點的度都大于等于2,則該圖中必有回路。（）【答案】對62. 順序存儲方式只適用于存儲線性表。（）【答案】錯63. 若一棵二叉樹中的結(jié)點均無右孩子，則該二叉樹的中根遍歷和后根遍歷序列正好相同。（）【答案】對64. 鄰接表只能用于有向圖的存儲，鄰接矩陣對于有向圖和無向圖的存儲都

10、適用。（）【答案】錯65. 完全二叉樹的某結(jié)點若無左孩子，則它必是葉結(jié)點。（）【答案】對66. 在一棵二叉樹中，假定每個結(jié)點只有左子 女，沒有右子女，對它分別進(jìn)行前序遍歷和后 序遍歷，則具有相同的結(jié)果。（）【答案】錯67. 折半查找所對應(yīng)的判定樹，既是一棵二叉查找樹，又是一棵理想平衡二叉樹。（）【答案】對68. 存儲無向圖的鄰接矩陣是對稱的，因此可以只存儲鄰接矩陣的下（上）三角部分。（）【答案】對69. 在對雙向循環(huán)鏈表做刪除一個結(jié)點操作 時，應(yīng)先將被刪除結(jié)點的前驅(qū)結(jié)點和后繼結(jié)點 鏈接好再執(zhí)行刪除結(jié)點操作。（）【答案】對70. 在用單鏈表表示的鏈?zhǔn)疥犃蠶中，隊頭指針 為Q->front

11、，隊尾指針為Q->rear，則隊空條件 為 Q->front =Q->rear 。（）【答案】錯71. 對稀疏矩陣進(jìn)行壓縮存儲是為了便于進(jìn)行矩陣 運算。（）【答案】錯72. 理想情況下哈希查找的等概率查找成功的平均查找長度是0（ 1）。（【答案】對73. 在任意一棵二叉樹的前序序列和后序序列中，各葉子之間的相對次序關(guān)系都相同。（【答案】對74. 遞歸調(diào)用算法與相同功能的非遞歸算法相 比，主要問題在于重復(fù)計算太多，而且調(diào)用本 身需要分配額外的空間和傳遞數(shù)據(jù)和控制，所以時間與空間開銷 通常都比較大。（【答案】對75. 采用不同的遍歷方法， 所得到的無向圖的生成樹總是相同的。（）【

12、答案】錯76. 對于同一組記錄，生成二叉搜索樹的形態(tài)與插 入記錄的次序無關(guān)。（）【答案】錯77. 對一個有向圖進(jìn)行拓?fù)渑判?，一定可以將圖的 所有頂點按其關(guān)鍵碼大小排列到一個拓?fù)溆行虻?序列中。（）【答案】錯78. 鏈?zhǔn)綏Ｅc順序棧相比，一個明顯的優(yōu)點是 通常不會出現(xiàn)棧滿的情況。（）【答案】對79. 對于兩棵具有相同記錄集合而具有不同形態(tài)的二叉搜索樹，按中序遍歷得到的結(jié)點序列是相同 的。（）【答案】對80. 在用散列表存儲關(guān)鍵碼集合時，可以用雙散列 法尋找下一個空位置。在設(shè)計再散列函數(shù)時，要求 計算出的值與表的大小m互質(zhì)。（）【答案】對81. 邊數(shù)很少的稀疏圖，適宜用鄰接矩陣表示。（）【答案】錯8

13、2. 遞歸的算法簡單、易懂、容易編寫，而且執(zhí)行效率 也高。（）【答案】錯83. 如果采用如下方式定義一維字符數(shù)組：const int maxSize = 30;char amaxSize;則這種數(shù)組在程序執(zhí)行過程中不能擴充。（）【答案】對84. 鏈隊列的出隊操作總是需要修改尾指針。（）【答案】錯85. 棧和隊列都是順序存取的線性表，但它們 對存取位置的限制不同。（）【答案】對86. 數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏 輯關(guān)系，是用戶根據(jù)應(yīng)用需要建立的?！敬鸢浮繉?7. 直接選擇排序是一種穩(wěn)定的排序方法。（）【答案】錯88. 當(dāng)從一個最小堆中刪除一個元素時，需要把堆 尾元素填補到堆頂位置，然后

14、再按條件把它逐層向 下調(diào)整，直到調(diào)整到合適位置為止。（）【答案】對89. 線性表的邏輯順序總是與其物理順序一致。（ ）【答案】錯90. 將f = 1 + 1/2 + 1/3+ 1/n 轉(zhuǎn)化為遞歸函數(shù)時，遞歸部分為f （n） = f （n-1） + 1/n， 遞歸結(jié)束條件為f=1。（）【答案】對91. 對平衡二叉樹進(jìn)行中根遍歷，可得到結(jié)點的有序序列。（【答案】對92. 雙向循環(huán)鏈表的結(jié)點與單鏈表的結(jié)點結(jié)構(gòu)相同，只是結(jié)點間的連接方式不同。（）【答案】錯93. 在順序表中，邏輯上相鄰的元素在物理位置上不 一定相鄰。（）【答案】錯94.數(shù)組是一種靜態(tài)的存儲空間分配，就是說, 在程序設(shè)計時必須預(yù)先定義數(shù)

15、組的數(shù)據(jù)類型和 存儲空間大小，由編譯程序在編譯時進(jìn)行分配。（）【答案】錯95. 線索二叉樹中的每個結(jié)點通常包含有5個數(shù)據(jù)成員。（）【答案】對96. 對于一棵具有n個結(jié)點，其高度為h的任何二叉樹，進(jìn)行任一種次序遍歷的時間復(fù)雜度均為0（h）。（）【答案】錯97. 當(dāng)輸入序列已經(jīng)基本有序時，起泡排序需要比較關(guān)鍵碼的次數(shù)，比快速排序還要少。（）【答案】對98. 順序查找法適用于存儲結(jié)構(gòu)為順序或鏈接存儲的 線性表。（）【答案】對99. 插入與刪除操作是數(shù)據(jù)結(jié)構(gòu)中最基本的兩 種操作，因此這兩種操作在數(shù)組中也經(jīng)常被使 用。（【答案】錯100. 哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán) 值較大的結(jié)點離根較近。

16、（）【答案】對101. 在一個有向圖中，所有頂點的入度之和等于所 有頂點的出度之和。（）【答案】對102. 在用循環(huán)單鏈表表示的鏈?zhǔn)疥犃兄校?可以 不設(shè)隊頭指針，僅在鏈尾設(shè)置隊尾指針。（）【答案】對103. 向一棵B樹插入關(guān)鍵碼的過程中， 若最終引起樹根結(jié)點的分裂，則新樹比原樹的高度減少1。（） 【答案】錯104. 多維數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)， 數(shù)組元 素之間的關(guān)系既不是線性的也不是樹形的。（）【答案】對105. 在二叉排序樹中插入新結(jié)點時，新結(jié)點總是作為葉子結(jié)點插入。（）【答案】對106. 邊數(shù)很少的稀疏圖，適宜用鄰接表表示。（）【答案】對107. 鏈隊列的出隊操作總是需要修改尾指針?！敬?/p>

17、案】錯108. 在一棵二叉樹中，假定每個結(jié)點只有左子女，沒 有右子女，對它分別進(jìn)行前序遍歷和按層遍歷，則具有 相同的結(jié)果。（）【答案】對109. 二叉樹中每個結(jié)點的兩棵子樹的高度差等于1。（）【答案】錯110. 二叉樹中不存在度大于 2的結(jié)點，當(dāng)某個結(jié)點只有一棵子樹時無所謂左、右子樹。（）【答案】錯111. 鏈隊列的出隊操作是不需要修改尾指針的。（）【答案】錯112. 圖的廣度優(yōu)先搜索算法通常采用非遞歸算法 求解。（）【答案】對113. 拓?fù)渑判蚴侵附Y(jié)點的值是有序排序的。（）【答案】錯114. 數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容 和形式無關(guān)?！敬鸢浮繉?15. 在樹的存儲中，若使每個結(jié)點帶有指

18、向雙親結(jié)點的指針，這為在算法中尋找雙親結(jié)點帶來方便。（）【答案】對116. 二叉樹中每個結(jié)點的關(guān)鍵字值大于其左非空子樹（若存在的話）所有結(jié)點的關(guān)鍵字值，且小于其右 非空子樹（若存在的話）所有結(jié)點的關(guān)鍵字值。（）【答案】錯117. 邊數(shù)很多的稠密圖，適宜用鄰接表表示。（）【答案】錯118. 從一棵B樹刪除關(guān)鍵碼的過程中， 若最終引起 樹根結(jié)點的合并，則新樹比原樹的高度增加1。（）【答案】錯119. 在索引順序結(jié)構(gòu)的搜索中，對索引表既可以采取順序搜索，也可以采用折半搜索。（）【答案】對120. 算法和程序都應(yīng)具有下面一些特征： 有輸 入，有輸出，確定性，有窮性，有效性。（）【答案】錯121. 對一個連通圖進(jìn)行一次深度優(yōu)先搜索可以遍 訪圖中的所有頂點。（）【答案】對122. 對于一棵具有n個結(jié)點的任何二叉樹，進(jìn)行前序、 中序或后序的任一種次序遍歷的空間復(fù)雜度為O（log2n）。（）【答案】錯123. 用字符數(shù)組存儲長度為n的字符串，數(shù)組 長度至少為n+1。（）【答案】對124. 線性表若采用鏈?zhǔn)酱鎯Ρ硎緯r，其存儲結(jié)點的地址可連續(xù)也可不連續(xù)。（）【答案】對125. 在二叉排序樹中插入新結(jié)點時，新結(jié)點