專升本《數(shù)據(jù)結(jié)構(gòu)》-試卷-答案

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 專升本數(shù)據(jù)結(jié)構(gòu)一、 （共75題,共150分）1. 數(shù)據(jù)的基本單位是（）。 （2分）A.數(shù)據(jù)元素 B.記錄 C.數(shù)據(jù)對象 D.數(shù)據(jù)項(xiàng) .標(biāo)準(zhǔn)答案：A2. （）是數(shù)據(jù)的不可分割的最小單位。 （2分）A.數(shù)據(jù)對象 B.數(shù)據(jù)元素 C.數(shù)據(jù)類型 D.數(shù)據(jù)項(xiàng) .標(biāo)準(zhǔn)答案：D3. 算法的空間復(fù)雜度是對算法（）的度量。 （2分）A.時(shí)間效率 B.空間效率 C.可讀性 D.健壯性 .標(biāo)準(zhǔn)答案：B4. （）是限制了數(shù)據(jù)元素的內(nèi)部結(jié)構(gòu)僅為一個字符的線性表。 （2分）A.棧 B.隊(duì)列 C.串 D.數(shù)組 .標(biāo)準(zhǔn)答案：B5. 串的長度是指串中所含（）的個數(shù)。 （2分）A.不同字符 B.不同字母

2、 C.相同字符 D.所有字符 .標(biāo)準(zhǔn)答案：D6. 采用帶頭結(jié)點(diǎn)雙向鏈表存儲的線性表，在刪除一個元素時(shí)，需要修改指針（）次。 （2分） .標(biāo)準(zhǔn)答案：B7. 線性表的順序存儲結(jié)構(gòu)是一種（）的存儲結(jié)構(gòu)。 （2分）A.順序存取 B.隨機(jī)存取 C.索引存取 存取 .標(biāo)準(zhǔn)答案：B8. 數(shù)組a1.m采用順序存儲，a1和am地址分別為1024和1150，每個元素占2字節(jié)，則m是（）。 （2分） .標(biāo)準(zhǔn)答案：A9. 深度為h的二叉樹，第h層最多有（）個結(jié)點(diǎn)。 （2分） .標(biāo)準(zhǔn)答案：C10. m個結(jié)點(diǎn)的二叉樹，其對應(yīng)的二叉鏈表共有（）個非空鏈域。 （2分） +1 .標(biāo)準(zhǔn)答案：B11. 下面敘述錯誤的是（）。 （2

3、分）A.順序表是借助物理單元相鄰表示數(shù)據(jù)元素之間的邏輯關(guān)系B.對于空隊(duì)列進(jìn)行出隊(duì)操作過程中發(fā)生下溢現(xiàn)象C.有向圖的鄰接矩陣一定是對稱的D.具有相同的葉子個數(shù)和具有相同的葉子權(quán)值的赫夫曼樹不是唯一的.標(biāo)準(zhǔn)答案：C12. 以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是（）。 （2分）A.循環(huán)隊(duì)列 B.雙向鏈表 C.哈希表 D.數(shù)組 .標(biāo)準(zhǔn)答案：D13. 在一個長度為n的鏈?zhǔn)綏Ｖ谐鰲?shí)現(xiàn)算法的時(shí)間復(fù)雜度為（）。 （2分）(1) (log n) (n) (n2) .標(biāo)準(zhǔn)答案：A14. 在具有k個度數(shù)為2的二叉樹中，必有（）個葉子結(jié)點(diǎn)。 （2分） +1 .標(biāo)準(zhǔn)答案：D15. 在關(guān)鍵字序列（10,20,30,40,50

4、）中，采用折半法查找20，關(guān)鍵字之間比較需要（）次。 （2分） .標(biāo)準(zhǔn)答案：C16. 16某二叉樹的后序遍歷序列和和中序遍歷序列均為abcd，該二叉樹的前序遍歷序列是（）。 （2分） .標(biāo)準(zhǔn)答案：B17. n個頂點(diǎn)的無向連通圖的生成樹，至少有（）個邊。 （2分）(n-1) (n-1)/2 .標(biāo)準(zhǔn)答案：D18. 可以采用（）這種數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)二叉樹的層次遍歷運(yùn)算。 （2分）A.隊(duì)列 B.樹 C.棧 D.集合 .標(biāo)準(zhǔn)答案：A19. 假設(shè)以數(shù)組A0.n-1存放循環(huán)隊(duì)列的元素，其頭指針front指向隊(duì)頭元素、尾指針rear指向隊(duì)尾元素一個，則在少用一個元素空間的前提下，隊(duì)列空的判定條件為（）。 （2分

5、）= =front B.(front+1)n= =rear +1= =front D.(rear+1)n= =front .標(biāo)準(zhǔn)答案：A20. 序列（21，19，37，5，2）經(jīng)冒泡排序法由小到大排序，第一趟后所得結(jié)果為（）。 （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) .標(biāo)準(zhǔn)答案：B21. 二叉鏈表適合作為（）的存儲結(jié)構(gòu)。 （2分）A.隊(duì)列 B.二叉樹 C.樹 D.森林 .標(biāo)準(zhǔn)答案：B,C,D22. 設(shè)哈希(Hash)函數(shù)為H(k)= k % 17,其中k為關(guān)鍵字，關(guān)鍵字()是同義詞。 （2分

6、）,5,15 ,45,62 ,57,125 ,31,48 .標(biāo)準(zhǔn)答案：B,C,D23. 下列各項(xiàng)鍵值（）序列不是堆的。 （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 .標(biāo)準(zhǔn)答案：C,D24. 在下列排序方法中，（）的空間復(fù)雜度為O(n)。其中，n為參加排序的元素個數(shù)。 （2分）A.選擇排序 B.快速排序 C.歸并排序 D.冒泡排序 .標(biāo)準(zhǔn)答案：B,C25. 十字鏈表適合于（）選作存儲結(jié)構(gòu)。 （2分）A.隊(duì)列 B.稀疏矩陣 C.邊或弧數(shù)較少的圖 D.二叉樹 .標(biāo)準(zhǔn)答案：B,C26. 基于數(shù)據(jù)的邏輯關(guān)系，數(shù)據(jù)

7、的邏輯結(jié)構(gòu)劃分為（）基本結(jié)構(gòu)。 （2分）類 類 類 類 .標(biāo)準(zhǔn)答案：C27. （）不是算法具有的5個特性之一。 （2分）A.有窮性 B.確定性 C.可行性 D.正確性 .標(biāo)準(zhǔn)答案：D28. 算法的時(shí)間復(fù)雜度是對算法（）的度量。 （2分）A.時(shí)間效率 B.空間效率 C.可讀性 D.健壯性 .標(biāo)準(zhǔn)答案：A29. 線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時(shí)，要求結(jié)點(diǎn)的存儲單元地址（）。 （2分）A.必須是連續(xù)的 B.部分地址必須是連續(xù)的 C.必須是不連續(xù)的 D.連續(xù)或不連續(xù)都可以 .標(biāo)準(zhǔn)答案：D30. 二維數(shù)組通常采用順序存儲，其優(yōu)點(diǎn)是（）。 （2分）A.便于增加存儲空間 B.防止下標(biāo)溢出 C.避免數(shù)據(jù)元素的移動

8、D.便于依據(jù)下標(biāo)進(jìn)行隨機(jī)存取 .標(biāo)準(zhǔn)答案：D31. 采用順序存儲的線性表，若表長為n，在第i號元素之后插入一個元素時(shí)，需要移動（）個元素。 （2分）+1 +1 .標(biāo)準(zhǔn)答案：C32. 若已知一個棧的入棧序列是1、2、3、4，其出棧序列不可能為_。 （2分）、4、3、2 、4、1、2 、3、2、1 、3、4、1 .標(biāo)準(zhǔn)答案：B33. 數(shù)組a1.256采用順序存儲，a的首地址為10，每個元素占2字節(jié)，則a21的地址是（）。 （2分） .標(biāo)準(zhǔn)答案：C34. 深度為h的完全二叉樹至少有（）個葉子結(jié)點(diǎn)。 （2分）(h-1)+1 (h-2)+1 .標(biāo)準(zhǔn)答案：D35. 若二叉樹對應(yīng)的二叉鏈表共有m個非空鏈域，

9、則該二叉樹有（）個結(jié)點(diǎn)的二叉樹。 （2分） +1 .標(biāo)準(zhǔn)答案：B36. 下面敘述錯誤的是（）。 （2分）A.單鏈表是借助指針表示數(shù)據(jù)元素之間的邏輯關(guān)系B.在順序棧的入棧操作過程中可能發(fā)生上溢現(xiàn)象C.具有相同的葉子個數(shù)和具有相同的葉子權(quán)值的赫夫曼樹是唯一的D.無向圖的鄰接矩陣一定是對稱的.標(biāo)準(zhǔn)答案：C37. 以下（）術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān) （2分）A.棧 B.哈希表 C.線索樹 D.雙向鏈表 .標(biāo)準(zhǔn)答案：A38. 在一個長度為n的鏈?zhǔn)疥?duì)列中入隊(duì)實(shí)現(xiàn)算法的時(shí)間復(fù)雜度為（）。 （2分）(1) (log n) (n) (n2) .標(biāo)準(zhǔn)答案：A39. 隊(duì)列的出隊(duì)操作是指（）操作。 （2分）A.隊(duì)尾刪除

10、 B.隊(duì)頭刪除 C.隊(duì)尾插入 D.隊(duì)頭插入 .標(biāo)準(zhǔn)答案：B40. 在關(guān)鍵字序列（10,15,20,25,30）中采用折半法查找25，依次與（）關(guān)鍵字進(jìn)行了比較。 （2分）,25 ,25 ，30，25 .標(biāo)準(zhǔn)答案：B41. 16某二叉樹的前序遍歷序列和和中序遍歷序列分別為abcd和bcad，該二叉樹的后序遍歷序列是（）。 （2分） .標(biāo)準(zhǔn)答案：A42. 所占用的存儲空間大小僅與圖的頂點(diǎn)個數(shù)相關(guān)的存儲結(jié)構(gòu)是（）。 （2分）A.鄰接表 B.逆鄰接表 C.十字鏈表 D.鄰接矩陣.標(biāo)準(zhǔn)答案：D43. 可以采用（）這種數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)圖的深度優(yōu)先遍歷運(yùn)算。 （2分）A.隊(duì)列 B.樹 C.棧 D.集合 .標(biāo)準(zhǔn)

11、答案：C44. 線性表采用帶頭結(jié)點(diǎn)單鏈表實(shí)現(xiàn)，head為頭指針，則判斷表空的條件為（）。 （2分）= NULL !=NULL >next=NULL >next !=NULL .標(biāo)準(zhǔn)答案：C45. 在關(guān)鍵字序列（35，10，15，20，25）中采用最低位優(yōu)先排序(LSD)基數(shù)排序，第一趟之后所得結(jié)果為（）。 （2分），20，15，25，35 ，20，35，15，25 ，10，35，25，15 ，10，35，15，25 .標(biāo)準(zhǔn)答案：B46. 下列邏輯結(jié)構(gòu)中，（）為線性結(jié)構(gòu)。 （2分）A.棧 B.隊(duì)列 C.串 D.二叉樹 .標(biāo)準(zhǔn)答案：A,B,C47. 深度為3的二叉樹可能的結(jié)點(diǎn)個數(shù)是（）

12、。 （2分） .標(biāo)準(zhǔn)答案：A,B48. 下列各項(xiàng)鍵值（）序列是大頂堆的。 （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 .標(biāo)準(zhǔn)答案：B,C49. 下列（）是限制了插入和刪除操作的特殊線性表。 （2分）A.棧 B.隊(duì)列 C.串 D.數(shù)組 .標(biāo)準(zhǔn)答案：A,B50. 對一棵二叉排序樹，用（）方法進(jìn)行遍歷，不一定得到各結(jié)點(diǎn)鍵值的有序序列。 （2分）A.先根遍歷 B.中根遍歷 C.后根遍歷 D.層次遍歷 .標(biāo)準(zhǔn)答案：A,C,D51. 數(shù)據(jù)的最小單位是（）。 （2分）A.數(shù)據(jù)元素 B.記錄 C.數(shù)據(jù)對象 D.數(shù)據(jù)項(xiàng)

13、.標(biāo)準(zhǔn)答案：D52. 算法是對某一類問題求解步驟的有限序列。其中，（）是算法具有的5個特性之一。 （2分）A.有窮性 B.正確性 C.可讀性 D.健壯性 .標(biāo)準(zhǔn)答案：A53. （）是數(shù)據(jù)的邏輯結(jié)構(gòu)。 （2分）A.順序表 B.鏈表 C.線性表 D.十字鏈表 .標(biāo)準(zhǔn)答案：C54. （）是限制了插入和刪除操作在一端進(jìn)行的線性表。 （2分）A.棧 B.隊(duì)列 C.串 D.數(shù)組 .標(biāo)準(zhǔn)答案：A55. （）是限制了插入和刪除操作分別在兩端進(jìn)行的線性表。 （2分）A.棧 B.隊(duì)列 C.串 D.數(shù)組 .標(biāo)準(zhǔn)答案：B56. 用鏈表表示線性表的優(yōu)點(diǎn)是（）。 （2分）A.便于插入和刪除B.便于隨機(jī)存取C.花費(fèi)的存儲空

14、間較順序存儲少D.數(shù)據(jù)元素的物理順序與邏輯順序相同.標(biāo)準(zhǔn)答案：A57. 若已知一個棧的入棧序列是1、2、3、4，其出棧序列不可能為（）。 （2分）、4、3、2 、3、4、1 、3、2、1 、4、1、2 .標(biāo)準(zhǔn)答案：D58. 串下列關(guān)于串的敘述中，正確的是（）。 （2分）個串的長度相等，則2個串相等B.空串至少包一個空格C.替換操作可以實(shí)現(xiàn)字符的刪除D.一個串的長度至少是1.標(biāo)準(zhǔn)答案：C59. 深度為h的二叉樹，第h層至少有（）個結(jié)點(diǎn)。 （2分） .標(biāo)準(zhǔn)答案：B60. 假設(shè)n0，在程序段y=0;while(y+1)*(y+1)      

15、;                     B.標(biāo)準(zhǔn)答案：C61. 下面敘述錯誤的是（）。 （2分）A.在集合1，2，3，4，5中元素1是2的直接前驅(qū)B.二叉排序樹的中序遍歷序列一定是有序的C.有3個結(jié)點(diǎn)的不同形態(tài)二叉樹的數(shù)目為5D.哈夫曼樹中所有結(jié)點(diǎn)的孩子數(shù)目只可能為2或者為0.標(biāo)準(zhǔn)答案：A62. 以下數(shù)據(jù)結(jié)構(gòu)中，（）是線性結(jié)構(gòu)。 （2分）A.廣義表   

16、     B.二叉樹        C.稀疏矩陣      D.串            .標(biāo)準(zhǔn)答案：D63. 在一個長度為n的順序表中刪除一個元素的算法的時(shí)間復(fù)雜度為（）。 （2分）(1)        &#

17、160;               (log n)                    (n)            

18、0;           (n2)            .標(biāo)準(zhǔn)答案：C64. 如果一個huffman樹含有n個葉子，則該樹必有（）的結(jié)點(diǎn)。 （2分）+1           +1      

19、0;                         .標(biāo)準(zhǔn)答案：D65. 在關(guān)鍵字序列（10,15,20,25,30）中，采用折半法查找25，關(guān)鍵字之間比較需要（）次。 （2分）              &

20、#160;                                     .標(biāo)準(zhǔn)答案：B66. 16某二叉樹的前序遍歷序列和和中序遍歷序列均為abcd，該二叉樹的后序遍歷序列是（）。 （2分）  &#

21、160;                                     .標(biāo)準(zhǔn)答案：B67. m個頂點(diǎn)的有向完全圖有（）個弧。 （2分）(m-1)/2      

22、;+1                        (m-1)        .標(biāo)準(zhǔn)答案：D68. 下列各項(xiàng)鍵值（）序列不是堆的。 （2分）A.94，68，23，16，5         

23、 B.94，23，68，5，16          C.94，23，68，16，5          D.94，16，68，23，5          .標(biāo)準(zhǔn)答案：D69. 設(shè)單鏈表中指針p指向結(jié)點(diǎn)A，q指向新元素結(jié)點(diǎn)，若要A之后插入一個新元素，則所需修改指針的操作為（）。 （2分）>

24、;next=q，q->next=p->next>next=p->next，p->next=q>next=q->next，q->next=p>next=p，q->next=p->next.標(biāo)準(zhǔn)答案：B70. 在關(guān)鍵字序列（149，138，165，197，176，113，127）中采用最低位優(yōu)先排序(LSD)基數(shù)排序，第一趟之后所得結(jié)果為（）。 （2分），138，165，197，176，113，127，149，165，197，113，176，127，149，165，197，113，127，176，127，138，149，165，17

25、6，197.標(biāo)準(zhǔn)答案：B71. 下列術(shù)語表示的數(shù)據(jù)中，（）是同義語。 （2分）A.結(jié)點(diǎn)          B.數(shù)據(jù)元素      C.頂點(diǎn)          D.數(shù)據(jù)項(xiàng)        .標(biāo)準(zhǔn)答案：A,B,C72. 對于采用鏈?zhǔn)浇Y(jié)構(gòu)的隊(duì)列，（）運(yùn)算的實(shí)現(xiàn)算法的時(shí)

26、間復(fù)雜度為O(1)。 （2分）A.入隊(duì)          B.出隊(duì)          C.求隊(duì)長        D.隊(duì)清空        .標(biāo)準(zhǔn)答案：A,B73. 在n個數(shù)據(jù)元素中進(jìn)行查找，（）方法的最壞時(shí)間復(fù)雜度為O(n)。 （2分）A.順序查找