1、專升本數據結構模擬題試卷 一. 共75題,共150分 1. 數據的基本單位是。 2分 A.數據元素 B.記錄 C.數據對象 D.數據項 檢查答案標準答案：A 2. 是數據的不可分割的最小單位。 2分 A.數據對象 B.數據元素 C.數據類型 D.數據項 檢查答案標準答案：D 3. 算法的空間復雜度是對算法的度量。 2分 A.時間效率 B.空間效率 C.可讀性 D.健壯性 檢查答案標準答案：B 4. 是限制了數據元素的內部結構僅為一個字符的線性表。 2分 A.棧 B.隊列 C.串 D.數組 檢查答案標準答案：B 5. 串的長度是指串中所含的個數。 2分 A.不同字符 B.不同字母 C.相同字符

2、D.所有字符 檢查答案標準答案：D 6. 采用帶頭結點雙向鏈表存儲的線性表，在刪除一個元素時，需要修改指針次。 2分 A.1 B.2 C.3 D.4 檢查答案標準答案：B 7. 線性表的順序存儲結構是一種的存儲結構。 2分 A.順序存取 B.隨機存取 C.索引存取 D.Hash存取 檢查答案標準答案：B 8. 數組a1.m采用順序存儲，a1和am地址分別為1024和1150，每個元素占2字節，則m是。 2分 A.64 B.32 C.16 D.8 檢查答案標準答案：A 9. 深度為h的二叉樹，第h層最多有個結點。 2分 A.h B.2h-1 C.2h-1 D.2h 檢查答案標準答案：C 10.

3、m個結點的二叉樹，其對應的二叉鏈表共有個非空鏈域。 2分 A.m B.m+1 C.2m D.m-1 檢查答案標準答案：B 11. 下面表達錯誤的選項是。 2分 A.順序表是借助物理單元相鄰表示數據元素之間的邏輯關系 B.對于空隊列進行出隊操作過程中發生下溢現象 C.有向圖的鄰接矩陣一定是對稱的 D.具有相同的葉子個數和具有相同的葉子權值的赫夫曼樹不是唯一的 檢查答案標準答案：C 12. 以下與數據的存儲結構無關的術語是。 2分 A.循環隊列 B.雙向鏈表 C.哈希表 D.數組 檢查答案標準答案：D 13. 在一個長度為n的鏈式棧中出棧實現算法的時間復雜度為。 2分 A.O(1) B.O(log

4、 n) C.O(n) D.O(n2) 檢查答案標準答案：A 14. 在具有k個度數為2的二叉樹中，必有個葉子結點。 2分 A.k B.k-1 C.2k D.k+1 檢查答案標準答案：D 15. 在關鍵字序列10,20,30,40,50中，采用折半法查找20，關鍵字之間比較需要次。 2分 A.1 B.2 C.3 D.4 檢查答案標準答案：C 16. 16某二叉樹的后序遍歷序列和和中序遍歷序列均為abcd，該二叉樹的前序遍歷序列是。 2分 A.abcd B.dcba C.acbd D.dbca 檢查答案標準答案：B 17. n個頂點的無向連通圖的生成樹，至少有個邊。 2分 A.n(n-1) B.n

5、(n-1)/2 C.2n D.n-1 檢查答案標準答案：D 18. 可以采用這種數據結構，實現二叉樹的層次遍歷運算。 2分 A.隊列 B.樹 C.棧 D.集合 檢查答案標準答案：A 19. 假設以數組A0.n-1存放循環隊列的元素，其頭指針front指向隊頭元素、尾指針rear指向隊尾元素一個，則在少用一個元素空間的前提下，隊列空的判定條件為。 2分 A.rear= =front B.(front+1)n= =rear C.rear+1= =front D.(rear+1)n= =front 檢查答案標準答案：A 20. 序列21，19，37，5，2經冒泡排序法由小到大排序，第一趟后所得結果為

6、。 2分 A.(19，21，37，5，2) B.(19，21，5，2，37) C.(19，21，5，37，2) D.(19，21，2，5，37) 檢查答案標準答案：B 21. 二叉鏈表適合作為的存儲結構。 2分 A.隊列 B.二叉樹 C.樹 D.森林 檢查答案標準答案：B,C,D 22. 設哈希(Hash)函數為H(k)= k % 17,其中k為關鍵字，關鍵字()是同義詞。 2分 A.44,5,15 B.28,45,62 C.6,57,125 D.201,31,48 檢查答案標準答案：B,C,D 23. 以下各項鍵值序列不是堆的。 2分 A.94，68，23，16，5 B.94，23，68，5

7、，16 C.94，23，16，68，5 D.94，16，68，23，5 檢查答案標準答案：C,D 24. 在以下排序方法中，的空間復雜度為O(n)。其中，n為參加排序的元素個數。 2分 A.選擇排序 B.快速排序 C.歸并排序 D.冒泡排序 檢查答案標準答案：B,C 25. 十字鏈表適合于選作存儲結構。 2分 A.隊列 B.稀疏矩陣 C.邊或弧數較少的圖 D.二叉樹 檢查答案標準答案：B,C 26. 基于數據的邏輯關系，數據的邏輯結構劃分為基本結構。 2分 A.6類 B.5類 C.4類 D.3類 檢查答案標準答案：C 27. 不是算法具有的5個特性之一。 2分 A.有窮性 B.確定性 C.可行

8、性 D.正確性 檢查答案標準答案：D 28. 算法的時間復雜度是對算法的度量。 2分 A.時間效率 B.空間效率 C.可讀性 D.健壯性 檢查答案標準答案：A 29. 線性表假設采用鏈式存儲結構時，要求結點的存儲單元地址。 2分 A.必須是連續的 B.部分地址必須是連續的 C.必須是不連續的 D.連續或不連續都可以 檢查答案標準答案：D 30. 二維數組通常采用順序存儲，其優點是。 2分 A.便于增加存儲空間 B.防止下標溢出 C.防止數據元素的移動 D.便于依據下標進行隨機存取 檢查答案標準答案：D 31. 采用順序存儲的線性表，假設表長為n，在第i號元素之后插入一個元素時，需要移動個元素。

9、 2分 A.i+1 B.i C.n-i D.n-i+1 檢查答案標準答案：C 32. 假設已知一個棧的入棧序列是1、2、3、4，其出棧序列不可能為_。 2分 A.1、4、3、2 B.3、4、1、2 C.4、3、2、1 D.2、3、4、1 檢查答案標準答案：B 33. 數組a1.256采用順序存儲，a的首地址為10，每個元素占2字節，則a21的地址是。 2分 A.10 B.30 C.50 D.70 檢查答案標準答案：C 34. 深度為h的完全二叉樹至少有個葉子結點。 2分 A.2(h-1)+1 B.2(h-2)+1 C.2h-1 D.2h-2 檢查答案標準答案：D 35. 假設二叉樹對應的二叉鏈

10、表共有m個非空鏈域，則該二叉樹有個結點的二叉樹。 2分 A.m B.m-1 C.m+1 D.2m 檢查答案標準答案：B 36. 下面表達錯誤的選項是。 2分 A.單鏈表是借助指針表示數據元素之間的邏輯關系 B.在順序棧的入棧操作過程中可能發生上溢現象 C.具有相同的葉子個數和具有相同的葉子權值的赫夫曼樹是唯一的 D.無向圖的鄰接矩陣一定是對稱的 檢查答案標準答案：C 37. 以下術語與數據的存儲結構無關 2分 A.棧 B.哈希表 C.線索樹 D.雙向鏈表 檢查答案標準答案：A 38. 在一個長度為n的鏈式隊列中入隊實現算法的時間復雜度為。 2分 A.O(1) B.O(log n) C.O(n)

11、 D.O(n2) 檢查答案標準答案：A 39. 隊列的出隊操作是指操作。 2分 A.隊尾刪除 B.隊頭刪除 C.隊尾插入 D.隊頭插入 檢查答案標準答案：B 40. 在關鍵字序列10,15,20,25,30中采用折半法查找25，依次與關鍵字進行了比較。 2分 A.30,25 B.20,25 C.20，30，25 D.25 檢查答案標準答案：B 41. 16某二叉樹的前序遍歷序列和和中序遍歷序列分別為abcd和bcad，該二叉樹的后序遍歷序列是。 2分 A.cbda B.dcba C.abcd D.dcba 檢查答案標準答案：A 42. 所占用的存儲空間大小僅與圖的頂點個數相關的存儲結構是。 2

12、分 A.鄰接表 B.逆鄰接表 C.十字鏈表 D.鄰接矩陣 檢查答案標準答案：D 43. 可以采用這種數據結構，實現圖的深度優先遍歷運算。 2分 A.隊列 B.樹 C.棧 D.集合 檢查答案標準答案：C 44. 線性表采用帶頭結點單鏈表實現，head為頭指針，則判斷表空的條件為。 2分 A.head= NULL B.head!=NULL C.head->next=NULL D.head->next !=NULL 檢查答案標準答案：C 45. 在關鍵字序列35，10，15，20，25中采用最低位優先排序(LSD)基數排序，第一趟之后所得結果為。 2分 A.10，20，15，25，35

13、B.10，20，35，15，25 C.20，10，35，25，15 D.20，10，35，15，25 檢查答案標準答案：B 46. 以下邏輯結構中，為線性結構。 2分 A.棧 B.隊列 C.串 D.二叉樹 檢查答案標準答案：A,B,C 47. 深度為3的二叉樹可能的結點個數是。 2分 A.1 B.2 C.3 D.4 檢查答案標準答案：A,B 48. 以下各項鍵值序列是大頂堆的。 2分 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,C 49. 以下是限制了插入和刪除操作的特殊線性表。 2分 A

14、.棧 B.隊列 C.串 D.數組 檢查答案標準答案：A,B 50. 對一棵二叉排序樹，用方法進行遍歷，不一定得到各結點鍵值的有序序列。 2分 A.先根遍歷 B.中根遍歷 C.后根遍歷 D.層次遍歷 檢查答案標準答案：A,C,D 51. 數據的最小單位是。 2分 A.數據元素 B.記錄 C.數據對象 D.數據項 檢查答案標準答案：D 52. 算法是對某一類問題求解步驟的有限序列。其中，是算法具有的5個特性之一。 2分 A.有窮性 B.正確性 C.可讀性 D.健壯性 檢查答案標準答案：A 53. 是數據的邏輯結構。 2分 A.順序表 B.鏈表 C.線性表 D.十字鏈表 檢查答案標準答案：C 54.

15、 是限制了插入和刪除操作在一端進行的線性表。 2分 A.棧 B.隊列 C.串 D.數組 檢查答案標準答案：A 55. 是限制了插入和刪除操作分別在兩端進行的線性表。 2分 A.棧 B.隊列 C.串 D.數組 檢查答案標準答案：B 56. 用鏈表表示線性表的優點是。 2分 A.便于插入和刪除 B.便于隨機存取 C.花費的存儲空間較順序存儲少 D.數據元素的物理順序與邏輯順序相同 檢查答案標準答案：A 57. 假設已知一個棧的入棧序列是1、2、3、4，其出棧序列不可能為。 2分 A.1、4、3、2 B.2、3、4、1 C.4、3、2、1 D.3、4、1、2 檢查答案標準答案：D 58. 串以下關于

16、串的表達中，正確的選項是。 2分 A.2個串的長度相等，則2個串相等 B.空串至少包一個空格 C.替換操作可以實現字符的刪除 D.一個串的長度至少是1 檢查答案標準答案：C 59. 深度為h的二叉樹，第h層至少有個結點。 2分 A.0 B.1 C.8 D.16 檢查答案標準答案：B 60. 假設n0，在程序段y=0;while(y+1)*(y+1)<=n) y+;中，標記的語句實際執行的次數是。其中，x表示對x取整運算。 2分 A.n B. C.n2 檢查答案標準答案：C 61. 下面表達錯誤的選項是。 2分 A.在集合1，2，3，4，5中元素1是2的直接前驅 B.二叉排序樹的中序遍歷序

17、列一定是有序的 C.有3個結點的不同形態二叉樹的數目為5 D.哈夫曼樹中所有結點的孩子數目只可能為2或者為0 檢查答案標準答案：A 62. 以下數據結構中，是線性結構。 2分 A.廣義表 B.二叉樹 C.稀疏矩陣 D.串 檢查答案標準答案：D 63. 在一個長度為n的順序表中刪除一個元素的算法的時間復雜度為。 2分 A.O(1) B.O(log n) C.O(n) D.O(n2) 檢查答案標準答案：C 64. 如果一個huffman樹含有n個葉子，則該樹必有的結點。 2分 A.n+1 B.2n+1 C.2n D.2n-1 檢查答案標準答案：D 65. 在關鍵字序列10,15,20,25,30中

18、，采用折半法查找25，關鍵字之間比較需要次。 2分 A.1 B.2 C.3 D.4 檢查答案標準答案：B 66. 16某二叉樹的前序遍歷序列和和中序遍歷序列均為abcd，該二叉樹的后序遍歷序列是。 2分 A.abcd B.dcba C.acbd D.dbca 檢查答案標準答案：B 67. m個頂點的有向完全圖有個弧。 2分 A.m(m-1)/2 B.m+1 C.m D.m(m-1) 檢查答案標準答案：D 68. 以下各項鍵值序列不是堆的。 2分 A.94，68，23，16，5 B.94，23，68，5，16 C.94，23，68，16，5 D.94，16，68，23，5 檢查答案標準答案：D 69. 設單鏈表中指針p指向結點A，q指向新元素結點，假設要A之后插入一個新元素，則所需修改指針的操作為。 2分 A.p->next=q，q->next=p->next B.q->next=p->next，p->next=q C.p->next=q->next，q->next=p D.p->next=p，q->next=p-