?？茢?shù)據(jù)結(jié)構(gòu)試卷答案

1、 ?？茢?shù)據(jù)結(jié)構(gòu)一、 （共75題,共150分）1. 數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機內(nèi)部存儲表示稱為為數(shù)據(jù)的（）。 （2分）A.數(shù)據(jù)結(jié)構(gòu) B.邏輯關(guān)系 C.物理結(jié)構(gòu) D.數(shù)據(jù)元素的內(nèi)部結(jié)構(gòu) .標準答案：C2. （）是數(shù)據(jù)的不可分割的最小單位。 （2分）A.數(shù)據(jù)對象 B.數(shù)據(jù)元素 C.數(shù)據(jù)類型 D.數(shù)據(jù)項 .標準答案：D3. 算法的時間復雜度是對算法（）的度量。 （2分）A.時間效率 B.空間效率 C.可讀性 D.健壯性 .標準答案：A4. （）是限制了插入和刪除操作在一端進行的線性表。 （2分）A.棧 B.隊列 C.串 D.數(shù)組 .標準答案：A5. 數(shù)組通常采用順序存儲的優(yōu)點是（）。 （2分）A.便于增加

2、存儲空間 B.便于依據(jù)下標進行隨機存取 C.避免數(shù)據(jù)元素的移動 D.防止下標溢出 .標準答案：B6. 采用帶頭結(jié)點雙向鏈表存儲的線性表，在插入一個元素時，需要修改指針（）次。 （2分）A.1 B.2 C.3 D.4 .標準答案：D7. 線性表的順序存儲結(jié)構(gòu)是一種（）的存儲結(jié)構(gòu)。 （2分）A.順序存取 B.隨機存取 C.索引存取 D.Hash存取 .標準答案：B8. 數(shù)組a1.256采用順序存儲，a的首地址為10，每個元素占2字節(jié)，則a21的地址是（）。 （2分）A.10 B.30 C.50 D.70 .標準答案：C9. 深度為4的二叉樹，第4層至少有（）個結(jié)點。 （2分）A.0 B.1 C.8

3、 D.15 .標準答案：B10. 若二叉樹對應的二叉鏈表共有11個非空鏈域，則該二叉樹有（）個結(jié)點的二叉樹。 （2分）A.10 B.11 C.20 D.21 .標準答案：A11. 下面敘述錯誤的是（）。 （2分）A.借助于隊列可以實現(xiàn)對二叉樹的層遍歷B.棧的特點是先進后出C.對于單鏈表進行插入操作過程中不會發(fā)生上溢現(xiàn)象D.在無向圖的鄰接矩陣中每行1的個數(shù)等于對應的頂點度.標準答案：C12. 以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是（）。 （2分）A.循環(huán)隊列 B.雙向鏈表 C.哈希表 D.數(shù)組 .標準答案：D13. 在一個長度為n的鏈式隊列中入隊實現(xiàn)算法的時間復雜度為（）。 （2分）A.O(1) B.

4、O(log n) C.O(n) D.O(n2) .標準答案：A14. 在具有2個葉子的二叉樹中，必有（）個度數(shù)為2的結(jié)點。 （2分）A.4 B.3 C.2 D.1 .標準答案：D15. 在關(guān)鍵字序列（10,15,20,25,30）中采用折半法查找20，依次與（）關(guān)鍵字進行了比較。 （2分）A.30,20 B.30,10,20 C.40,20 D.20 .標準答案：B16. 16某二叉樹的后序遍歷序列和和中序遍歷序列分別為cbda和bcad，該二叉樹的前序遍歷序列是（）。 （2分）A.cbda B.dcba C.abcd D.dcba .標準答案：C17. 4個頂點的無向連通圖的生成樹，至少有（

5、）個邊。 （2分）A.0 B.1 C.2 D.3.標準答案：D18. 可以采用（）這種數(shù)據(jù)結(jié)構(gòu)，實現(xiàn)圖的深度優(yōu)先遍歷運算。 （2分）A.隊列 B.樹 C.棧 D.集合 .標準答案：C19. 設單鏈表中指針p指向結(jié)點A，q指向新元素結(jié)點，若要A之后插入一個新元素，則所需修改指針的操作為（）。 （2分）A.p->next=q，q->next=p->nextB.q->next=p->next，p->next=qC.p->next=q->next，q->next=pD.p->next=p，q->next=p->next.標準答案：

6、B20. 序列（21,19,37,5,2）經(jīng)簡單選擇排序法由小到大排序，在第一趟后所得結(jié)果為（）。 （2分）A.(19，21，5，2，37) B.(21，19，5，37，2) C.(21，19，2，5，37) D.(37，21，19，5，2) .標準答案：C21. 單鏈表可作為（）的存儲結(jié)構(gòu)。 （2分）A.線性表 B.棧 C.隊列 D.廣義表 .標準答案：A,B,C22. 在下列排序方法中，（）的平均時間復雜度為O(n2)。其中，n為參加排序的元素個數(shù)。 （2分）A.選擇排序 B.快速排序 C.直接插入排序 D.冒泡排序 .標準答案：A,C,D23. 下列各項鍵值（）序列是大頂堆的。 （2分）

7、A.23，68，94，16，5 B.94，68，23，16，5 C.94，23，68，16，5 D.94，16，68，23，5 .標準答案：B,C24. 下列是二叉樹4種常見的遍歷方法。其中，（）屬于深度優(yōu)先遍歷。 （2分）A.前序遍歷 B.中序遍歷 C.后序遍歷 D.層序遍歷 .標準答案：A,B,C25. 若已知一個棧的入棧序列是(1，2，3，4)，其可能出棧序列為（）。 （2分）A.(1，4，2，3) B.(3，4，1，2) C.(4，3，2，1) D.(2，3，4，1) .標準答案：C,D26. 物理結(jié)構(gòu)的在計算機內(nèi)部的基本存儲表示方法有（）種。 （2分）A.2 B.3 C.4 D.5

8、.標準答案：A27. 數(shù)據(jù)元素的存儲結(jié)構(gòu)，通常采用（）。 （2分）A.順序結(jié)構(gòu) B.鏈式結(jié)構(gòu) C.順序和鏈式組合結(jié)構(gòu) D.散列結(jié)構(gòu) .標準答案：A28. 算法的空間復雜度是對算法（）的度量。 （2分）A.時間效率 B.空間效率 C.可讀性 D.健壯性 .標準答案：B29. 線性表若采用鏈式存儲結(jié)構(gòu)時，要求結(jié)點的存儲單元地址（）。 （2分）A.必須是連續(xù)的 B.部分地址必須是連續(xù)的 C.必須是不連續(xù)的 D.連續(xù)或不連續(xù)都可以 .標準答案：D30. （）是限制了插入和刪除操作分別在兩端進行的線性表。 （2分）A.棧 B.隊列 C.串 D.數(shù)組 .標準答案：B31. 串通常采用塊鏈存儲的優(yōu)點是（）。

9、 （2分）A.防止聯(lián)接操作溢出 B.提高運算效率 C.避免數(shù)據(jù)元素的移動 D.提高存儲效率 .標準答案：D32. 采用順序存儲的線性表，若表長為9，在刪除第4號元素時，需要移動（）個元素。 （2分）A.0 B.4 C.5 D.9 .標準答案：C33. 數(shù)組采用順序存儲，a的首地址為1024，每個元素占2字節(jié)，則a1的地址是（）。 （2分）A.1024 B.1026 C.1028 D.1030 .標準答案：A34. 深度為4的二叉樹最多有（）個結(jié)點。 （2分）A.1 B.3 C.7 D.15 .標準答案：D35. 3個結(jié)點的二叉樹，其對應的二叉鏈表共有（）個非空鏈域。 （2分）A.2 B.3 C

10、.4 D.5 .標準答案：C36. 下面敘述錯誤的是（）。 （2分）A.借助于?？梢詫崿F(xiàn)對圖的深度優(yōu)先遍歷B.對矩陣進行壓縮存儲后無法實現(xiàn)對其元素進行隨機訪問C.樹的結(jié)點度是指結(jié)點的分支數(shù)D.空串的長度為零.標準答案：B37. 以下數(shù)據(jù)結(jié)構(gòu)中，（）是線性結(jié)構(gòu)。 （2分）A.二維數(shù)組 B.二叉樹 C.特殊矩陣 D.棧 .標準答案：D38. 在一個長度為n的鏈式棧中出棧實現(xiàn)算法的時間復雜度為（）。 （2分）A.O(1)B.O(log n)C.O(n)D.標準答案：A39. 在具有4個葉子的二叉樹中，必有（）個度數(shù)為2的結(jié)點。 （2分）A.4 B.3 C.2 D.1 .標準答案：B40. 在關(guān)鍵字序

11、列（10,15,20,25,30）中，采用折半法查找25，關(guān)鍵字之間比較需要（）次。 （2分）A.1 B.2 C.3 D.4 .標準答案：B41. 某二叉樹的后序遍歷序列和和中序遍歷序列分別為cba和bca，該二叉樹的前序遍歷序列是（）。 （2分）A.cba B.bca C.abc D.acb .標準答案：C42. 4個頂點的無向連通網(wǎng)的最小成本樹，至少有（）個邊。 （2分）A.0 B.1 C.2 D.3.標準答案：D43. 可以采用（）這種數(shù)據(jù)結(jié)構(gòu)，實現(xiàn)二叉樹的層次遍歷運算。 （2分）A.隊列 B.樹 C.棧 D.集合 .標準答案：A44. 線性表采用帶頭結(jié)點單鏈表實現(xiàn)，head為頭指針，則

12、判斷表空的條件為（）。 （2分）A.B.C.D.標準答案：C45. 在關(guān)鍵字序列（149，138，165，197，176，113，127）中采用最低位優(yōu)先排序(LSD)基數(shù)排序，第一趟之后所得結(jié)果為（）。 （2分）A.149，138，165，197，176，113，127B.128，149，165，197，113，176，127C.128，149，165，197，113，127，176D.113，127，138，149，165，176，197.標準答案：B46. 算法分析的內(nèi)容是對算法的（）分析。 （2分）A.時間效率 B.空間效率 C.可行性 D.正確性 .標準答案：A,B47. 在n個數(shù)據(jù)

13、元素中進行查找，（）方法的平均時間復雜度為O(n)。 （2分）A.順序查找 B.折半查找 C.二叉排序樹查找 D.分塊查找 .標準答案：B,C48. 下列各項鍵值（）序列不是堆的。 （2分）A.94，68，23，16，5 B.94，23，68，5，16 C.94，23，16，68，5 D.94，16，68，23，5 .標準答案：C,D49. 下列（）是限制了插入和刪除操作的特殊線性表。 （2分）A.棧 B.隊列 C.串 D.數(shù)組 .標準答案：A,B50. 下列（）哈希函數(shù)構(gòu)造方法所得的哈希函數(shù)，使得查找時間復雜度通常不能到達O(1)。 （2分）A.直接定地法 B.數(shù)字分析法 C.平方取中法 D

14、.折疊法 .標準答案：B,C,D51. 數(shù)據(jù)的邏輯結(jié)構(gòu)是由（）部分組成的。 （2分）A.2 B.3 C.4 D.5 .標準答案：A52. 下列時間復雜度中，（）表示的復雜度是最高的。 （2分）A.B.O(n2)C.D.O(n).標準答案：B53. 棧和隊列的共同點是（）。 （2分）A.進出原則都是先進先出B.進出原則都是后進先出C.都是插入刪除操作受限的線性表D.不允許在任意端點處插入和刪除元素.標準答案：C54. （）是限制了數(shù)據(jù)元素的內(nèi)部結(jié)構(gòu)僅為一個字符的線性表。 （2分）A.棧 B.隊列 C.串 D.數(shù)組 .標準答案：B55. 二維數(shù)組通常采用順序存儲，其優(yōu)點是（）。 （2分）A.便于增

15、加存儲空間 B.防止下標溢出 C.避免數(shù)據(jù)元素的移動 D.便于依據(jù)下標進行隨機存取 .標準答案：D56. 下列給出的操作中，（）是允許對隊列進行的操作。 （2分）A.刪除隊首元素 B.取出最近進隊的元素 C.按元素大小排序 D.中間插入元素 .標準答案：A57. 采用帶頭結(jié)點的單鏈表存儲的線性表，若表長為9，在第4號元素之前插入一個元素時，需要移動指針（）次。 （2分）A.1 B.2 C.3 D.4 .標準答案：C58. 數(shù)組采用順序存儲，a的首地址為1024，每個元素占4字節(jié)，則a17的地址是（）。 （2分）A.1040 B.1056 C.1072 D.1088 .標準答案：D59. 深度為

16、4的二叉樹，第4層最多有（）個結(jié)點。 （2分）A.0 B.1 C.8 D.15 .標準答案：C60. 若二叉樹對應的二叉鏈表共有4個非空鏈域，則該二叉樹有（）個結(jié)點的二叉樹。 （2分）A.2 B.3 C.4 D.5 .標準答案：B61. 下面敘述錯誤的是（）。 （2分）A.借助于隊列可以實現(xiàn)對圖的廣度優(yōu)先遍歷B.二叉樹中序遍歷的序列是有序C.只有一個結(jié)點的二叉樹的度為0D.空格串是指由1個或以上的空格符號組成的串.標準答案：B62. 以下（）術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān) （2分）A.串 B.哈希表 C.線索樹 D.單鏈表 .標準答案：A63. 在一個長度為n的鏈式隊列中出隊實現(xiàn)算法的時間復雜度為（

17、）。 （2分）A.O(1) B.O(log n) C.O(n) D.O(n2) .標準答案：A64. 在具有4個度數(shù)為2的二叉樹中，必有（）個葉子結(jié)點。 （2分）A.2 B.3 C.4 D.5 .標準答案：D65. 在關(guān)鍵字序列（10,15,20,25,30）中采用折半法查找25，依次與（）關(guān)鍵字進行了比較。 （2分）A.30,25 B.20,25 C.20，30，25 D.25 .標準答案：B66. 某二叉樹的前序遍歷序列和和中序遍歷序列分別為abc和bca，該二叉樹的后序遍歷序列是（）。 （2分）A.cba B.bca C.abc D.acb .標準答案：A67. 4個頂點的無向圖，最多有

18、（）個邊。 （2分）A.3 B.4 C.5 D.6 .標準答案：D68. 可以采用（）這種數(shù)據(jù)結(jié)構(gòu)，實現(xiàn)表達式中左右括號是否配對出現(xiàn)判別的運算。 （2分）A.隊列 B.樹 C.棧 D.集合 .標準答案：C69. 假設以數(shù)組A0.n-1存放循環(huán)隊列的元素，其頭指針front指向隊頭元素、尾指針rear指向隊尾元素一個，則在少用一個元素空間的前提下，隊列空的判定條件為（）。 （2分）A.B.C.D.標準答案：A70. 在關(guān)鍵字序列（35，10，15，20，25）中采用最低位優(yōu)先排序(LSD)基數(shù)排序，第一趟之后所得結(jié)果為（）。 （2分）A.10，20，15，25，35 B.10，20，35，15，25 C.20，10，35，25，15 D.20，10，35，15，25 .標準答案：B71. 算法具有的5個特性，（）均為算法的特性之一。 （2分）A.有窮性 B.確定性 C.可行性 D.正確性 .標準答案：A,B,C72. 在下列數(shù)據(jù)結(jié)構(gòu)中，（）屬于非線性結(jié)構(gòu)。 （2分）