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

判斷題，在每小題前面打?qū)μ柋硎菊_或打叉號表示錯誤1. 數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。對2. 使用三元組表示稀疏矩陣中的非零元素能節(jié)省存儲空間。對3. 在一棵二叉樹中，假定每個結(jié)點(diǎn)只有左子女，沒有右子女，則對它分別進(jìn)行前序遍歷和按層遍歷時具有相同的結(jié)果。對4. 能夠在鏈接存儲的有序表上進(jìn)行折半搜索，其時間復(fù)雜度與在順序存儲的有序表上相同。錯5. 鄰接表表示只能用于有向圖的存儲，鄰接矩陣對于有向圖和無向圖的存儲都適用。錯6. 在索引順序結(jié)構(gòu)上實(shí)施分塊搜索，在等概率情況下，其平均搜索長度不僅與子表個數(shù)有關(guān)，而且與每一個子表中的對象個數(shù)有關(guān)。對7. 向一棵B樹插入關(guān)鍵碼的過程中，若最終引起樹根結(jié)點(diǎn)的分裂，則新樹比原樹的高度減少1。錯8. 算法和程序都應(yīng)具有下面一些特征：有輸入，有輸出，確定性，有窮性，有效性。錯9. 用字符數(shù)組存儲長度為n的字符串，數(shù)組長度至少為n+1。對10. 在用循環(huán)單鏈表表示的鏈?zhǔn)疥犃兄?，可以不設(shè)隊頭指針，僅在鏈尾設(shè)置隊尾指針。對11. 鄰接矩陣適用于稀疏圖的表示，鄰接表適用于稠密圖的表示。錯12. 對一個無向連通圖進(jìn)行一次深度優(yōu)先搜索遍歷時可以訪問到圖中的所有頂點(diǎn)。對13. 在索引順序結(jié)構(gòu)的搜索中，對索引表只可以采取順序搜索，不可以采用折半搜索。錯14. 圖中各個頂點(diǎn)的編號是人為的，不是它本身固有的，因此可以根據(jù)需要進(jìn)行改變。對15. 線性表若采用鏈?zhǔn)酱鎯Ρ硎緯r，其存儲結(jié)點(diǎn)的地址可連續(xù)也可不連續(xù)。對16. 在線性鏈表中刪除結(jié)點(diǎn)時，只需要將被刪結(jié)點(diǎn)釋放，不需要修改任何指針。錯17. 在用單鏈表表示的鏈?zhǔn)疥犃蠶中，假定隊頭指針為Q-front，隊尾指針為Q-rear，則鏈隊為空的條件為Q-front=Q-rear。錯18. 一棵AVL樹的所有葉結(jié)點(diǎn)不一定在同一層次上，同樣，平衡的m路搜索樹的葉結(jié)點(diǎn)也不一定在同一層次上。對19. 一個廣義表(a),(b),c),(d)的表尾是“(b),c),(d)”。錯20. 在一棵二叉樹中，假定每個結(jié)點(diǎn)只有左子女，沒有右子女，若對它分別進(jìn)行中序遍歷和后序遍歷，則具有相同的結(jié)果。對21. 折半搜索所對應(yīng)的判定樹，既是一棵二叉搜索樹，又是一棵理想平衡二叉樹。對22. 對任何用頂點(diǎn)表示活動的網(wǎng)絡(luò)（AOV網(wǎng)）進(jìn)行拓?fù)渑判虻慕Y(jié)果都是唯一的。錯23. 如果有向圖中各個頂點(diǎn)的度都大于2，則該圖中必有回路。錯24. 堆排序是一種穩(wěn)定的排序方法。錯25. 算法和程序的概念完全相同，在討論數(shù)據(jù)結(jié)構(gòu)時二者是通用的。錯26. 插入與刪除操作是數(shù)據(jù)結(jié)構(gòu)中最基本的兩種操作，因此這兩種操作在數(shù)組中也經(jīng)常被使用。錯27. 棧和隊列都是順序存取的線性表, 但它們對存取位置的限制不同。對28. 將f=1+1/2+1/3+1/n轉(zhuǎn)化為遞歸函數(shù)時，遞歸部分為f(n)=f(n-1)+1/n，遞歸結(jié)束條件為f(1)=1。對28. 在一棵二叉樹中，假定每個結(jié)點(diǎn)只有左子女，沒有右子女，對它分別進(jìn)行前序遍歷和中序遍歷時具有相同的結(jié)果。錯30. 進(jìn)行折半搜索的表必須是順序存儲的有序表。對31. 用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中的頂點(diǎn)個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。對32. 對于AOE網(wǎng)絡(luò)，任一關(guān)鍵活動延遲都將導(dǎo)致整個工程的延遲完成。對33. 將一批雜亂無章的數(shù)據(jù)按小根堆結(jié)構(gòu)組織起來并存儲到一維數(shù)組中, 則堆中的數(shù)據(jù)必然按從小到大的線性順序排列。錯34. 一棵m階B樹中每個結(jié)點(diǎn)都最多有m-1個關(guān)鍵碼，最少有m/2-1個關(guān)鍵碼。錯35. 二叉排序樹或是一棵空樹，或是具有下列性質(zhì)的二叉樹：（X）若它的左子樹非空，則根結(jié)點(diǎn)的值大于其左孩子的值，若它的右子樹非空，則根結(jié)點(diǎn)的值大于其右孩子的值。36. 索引順序表的特點(diǎn)是塊內(nèi)可無序，塊間要有序。（）37. 子串是主串中任意個連續(xù)字符組成的序列。（）38. 線性結(jié)構(gòu)只能用順序結(jié)構(gòu)存放，非線性結(jié)構(gòu)只能用鏈表存放。（X）39. 快速排序的樞軸元素可以任意選定。（）40. 在拓樸序列中，如果結(jié)點(diǎn)Vi排在結(jié)點(diǎn)Vj的前面，則一定存在從Vi到Vj的路徑。(r)41. 在采用線性探測法處理沖突的散列表中，所有同義詞在表中一定相鄰。(r)42. 在一個小根堆中，具有最大值的元素一定是葉結(jié)點(diǎn)。()43. 索引順序表的特點(diǎn)是塊間可無序，但塊內(nèi)一定要有序。(r)44. 哈夫曼樹中沒有度為1的結(jié)點(diǎn)，所以必為滿二叉樹。(r)45. 廣義表( a ), b), c ) 的表頭是( a ), b)，表尾是( c )。()46. 在哈夫曼樹中，權(quán)值最小的結(jié)點(diǎn)離根結(jié)點(diǎn)最近。()47. 基數(shù)排序是高位優(yōu)先排序法。()48. 在平衡二叉樹中，任意結(jié)點(diǎn)左右子樹的高度差（絕對值）不超過1。()49. 在單鏈表中，給定任一結(jié)點(diǎn)的地址p，則可用下述語句將新結(jié)點(diǎn)s插入結(jié)點(diǎn)p的后面 ：p-next = s; s-next = p-next; ()50. 抽象數(shù)據(jù)類型（ADT）包括定義和實(shí)現(xiàn)兩方面，其中定義是獨(dú)立于實(shí)現(xiàn)的，定義僅給出一個ADT的邏輯特性，不必考慮如何在計算機(jī)中實(shí)現(xiàn)。()51. 數(shù)組元素的下標(biāo)值越大，存取時間越長。()52. 用鄰接矩陣法存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中結(jié)點(diǎn)個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。()53. 拓?fù)渑判蚴前碅OE網(wǎng)中每個結(jié)點(diǎn)事件的最早發(fā)生時間對結(jié)點(diǎn)進(jìn)行排序。()54. 長度為1的串等價于一個字符型常量。()55. 棧和隊列都是非線性數(shù)據(jù)結(jié)構(gòu)。56. 完全二叉樹可以用順序存儲結(jié)構(gòu)進(jìn)行存儲。57. 數(shù)據(jù)元素是數(shù)據(jù)的最小單位。(基本單位) 58. 含尾指針的單鏈循環(huán)表可以被用于隊列操作。59. 數(shù)據(jù)結(jié)構(gòu)包含數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)以及數(shù)據(jù)集合上定義的運(yùn)算。60. 含尾指針的單鏈循環(huán)表可以被用于隊列操作。61. 棧和隊列都不是線性數(shù)據(jù)結(jié)構(gòu)。62. 數(shù)據(jù)項是數(shù)據(jù)的最小單位。（而數(shù)據(jù)元素是基本單位）63. 數(shù)據(jù)結(jié)構(gòu)包含數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)以及數(shù)據(jù)集合上定義的運(yùn)算。64. 完全二叉樹不可以用順序存儲結(jié)構(gòu)進(jìn)行存儲。（ F ）65. 線性結(jié)構(gòu)的基本特征是：每個結(jié)點(diǎn)有且僅有一個直接前驅(qū)和一個直接后繼。（ F ）66. 二叉樹是樹的特殊情形。（ T ）67. 存在這樣的二叉樹，其先序遍歷與中序遍歷得到的訪問序列相同。（ F ）68.用一維數(shù)組存儲二叉樹時，總是以先序遍歷的順序存儲結(jié)點(diǎn)。（ F ）69. 空串就是由空格組成的串。（ F ）70. 在AOE網(wǎng)中，一定只有一條關(guān)鍵路徑。（ T ）71 插入排序是穩(wěn)定的。（ T ）72. 順序存儲的線性表可以實(shí)現(xiàn)隨機(jī)存取。（ F ）73. 二叉樹按某種順序線索化后，任一結(jié)點(diǎn)均有指向其直接前驅(qū)和直接后繼的線索。（ F ）74. 在線性結(jié)構(gòu)的順序存儲結(jié)構(gòu)中，邏輯上相鄰的兩個元素在物理位置上不一定相鄰。（ F ）75. 二叉樹就是度為2的樹。（