?？啤稊?shù)據(jù)結(jié)構(gòu)》_試卷_答案.doc

專科數(shù)據(jù)結(jié)構(gòu)一、 （共75題,共150分）1. 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)內(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) .標(biāo)準(zhǔn)答案：C2. （）是數(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.時間效率 B.空間效率 C.可讀性 D.健壯性 .標(biāo)準(zhǔn)答案：A4. （）是限制了插入和刪除操作在一端進(jìn)行的線性表。 （2分）A.棧 B.隊(duì)列 C.串 D.數(shù)組 .標(biāo)準(zhǔn)答案：A5. 數(shù)組通常采用順序存儲的優(yōu)點(diǎn)是（）。 （2分）A.便于增加存儲空間 B.便于依據(jù)下標(biāo)進(jìn)行隨機(jī)存取 C.避免數(shù)據(jù)元素的移動 D.防止下標(biāo)溢出 .標(biāo)準(zhǔn)答案：B6. 采用帶頭結(jié)點(diǎn)雙向鏈表存儲的線性表，在插入一個元素時，需要修改指針（）次。 （2分）A.1 B.2 C.3 D.4 .標(biāo)準(zhǔn)答案：D7. 線性表的順序存儲結(jié)構(gòu)是一種（）的存儲結(jié)構(gòu)。 （2分）A.順序存取 B.隨機(jī)存取 C.索引存取 D.Hash存取 .標(biāo)準(zhǔn)答案：B8. 數(shù)組a1.256采用順序存儲，a的首地址為10，每個元素占2字節(jié)，則a21的地址是（）。 （2分）A.10 B.30 C.50 D.70 .標(biāo)準(zhǔn)答案：C9. 深度為4的二叉樹，第4層至少有（）個結(jié)點(diǎn)。 （2分）A.0 B.1 C.8 D.15 .標(biāo)準(zhǔn)答案：B10. 若二叉樹對應(yīng)的二叉鏈表共有11個非空鏈域，則該二叉樹有（）個結(jié)點(diǎn)的二叉樹。 （2分）A.10 B.11 C.20 D.21 .標(biāo)準(zhǔn)答案：A11. 下面敘述錯誤的是（）。 （2分）A.借助于隊(duì)列可以實(shí)現(xiàn)對二叉樹的層遍歷B.棧的特點(diǎn)是先進(jìn)后出C.對于單鏈表進(jìn)行插入操作過程中不會發(fā)生上溢現(xiàn)象D.在無向圖的鄰接矩陣中每行1的個數(shù)等于對應(yīng)的頂點(diǎ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)疥?duì)列中入隊(duì)實(shí)現(xiàn)算法的時間復(fù)雜度為（）。 （2分）A.O(1) B.O(log n) C.O(n) D.O(n2) .標(biāo)準(zhǔn)答案：A14. 在具有2個葉子的二叉樹中，必有（）個度數(shù)為2的結(jié)點(diǎn)。 （2分）A.4 B.3 C.2 D.1 .標(biāo)準(zhǔn)答案：D15. 在關(guān)鍵字序列（10,15,20,25,30）中采用折半法查找20，依次與（）關(guān)鍵字進(jìn)行了比較。 （2分）A.30,20 B.30,10,20 C.40,20 D.20 .標(biāo)準(zhǔn)答案：B16. 16某二叉樹的后序遍歷序列和和中序遍歷序列分別為cbda和bcad，該二叉樹的前序遍歷序列是（）。 （2分）A.cbda B.dcba C.abcd D.dcba .標(biāo)準(zhǔn)答案：C17. 4個頂點(diǎn)的無向連通圖的生成樹，至少有（）個邊。 （2分）A.0 B.1 C.2 D.3.標(biāo)準(zhǔn)答案：D18. 可以采用（）這種數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)圖的深度優(yōu)先遍歷運(yùn)算。 （2分）A.隊(duì)列 B.樹 C.棧 D.集合 .標(biāo)準(zhǔn)答案：C19. 設(shè)單鏈表中指針p指向結(jié)點(diǎn)A，q指向新元素結(jié)點(diǎn)，若要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.標(biāo)準(zhǔn)答案：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) .標(biāo)準(zhǔn)答案：C21. 單鏈表可作為（）的存儲結(jié)構(gòu)。 （2分）A.線性表 B.棧 C.隊(duì)列 D.廣義表 .標(biāo)準(zhǔn)答案：A,B,C22. 在下列排序方法中，（）的平均時間復(fù)雜度為O(n2)。其中，n為參加排序的元素個數(shù)。 （2分）A.選擇排序 B.快速排序 C.直接插入排序 D.冒泡排序 .標(biāo)準(zhǔn)答案：A,C,D23. 下列各項(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,C24. 下列是二叉樹4種常見的遍歷方法。其中，（）屬于深度優(yōu)先遍歷。 （2分）A.前序遍歷 B.中序遍歷 C.后序遍歷 D.層序遍歷 .標(biāo)準(zhǔn)答案：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) .標(biāo)準(zhǔn)答案：C,D26. 物理結(jié)構(gòu)的在計(jì)算機(jī)內(nèi)部的基本存儲表示方法有（）種。 （2分）A.2 B.3 C.4 D.5 .標(biāo)準(zhǔn)答案：A27. 數(shù)據(jù)元素的存儲結(jié)構(gòu)，通常采用（）。 （2分）A.順序結(jié)構(gòu) B.鏈?zhǔn)浇Y(jié)構(gòu) C.順序和鏈?zhǔn)浇M合結(jié)構(gòu) D.散列結(jié)構(gòu) .標(biāo)準(zhǔn)答案：A28. 算法的空間復(fù)雜度是對算法（）的度量。 （2分）A.時間效率 B.空間效率 C.可讀性 D.健壯性 .標(biāo)準(zhǔn)答案：B29. 線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，要求結(jié)點(diǎn)的存儲單元地址（）。 （2分）A.必須是連續(xù)的 B.部分地址必須是連續(xù)的 C.必須是不連續(xù)的 D.連續(xù)或不連續(xù)都可以 .標(biāo)準(zhǔn)答案：D30. （）是限制了插入和刪除操作分別在兩端進(jìn)行的線性表。 （2分）A.棧 B.隊(duì)列 C.串 D.數(shù)組 .標(biāo)準(zhǔn)答案：B31. 串通常采用塊鏈存儲的優(yōu)點(diǎn)是（）。 （2分）A.防止聯(lián)接操作溢出 B.提高運(yùn)算效率 C.避免數(shù)據(jù)元素的移動 D.提高存儲效率 .標(biāo)準(zhǔn)答案：D32. 采用順序存儲的線性表，若表長為9，在刪除第4號元素時，需要移動（）個元素。 （2分）A.0 B.4 C.5 D.9 .標(biāo)準(zhǔn)答案：C33. 數(shù)組采用順序存儲，a的首地址為1024，每個元素占2字節(jié)，則a1的地址是（）。 （2分）A.1024 B.1026 C.1028 D.1030 .標(biāo)準(zhǔn)答案：A34. 深度為4的二叉樹最多有（）個結(jié)點(diǎn)。 （2分）A.1 B.3 C.7 D.15 .標(biāo)準(zhǔn)答案：D35. 3個結(jié)點(diǎn)的二叉樹，其對應(yīng)的二叉鏈表共有（）個非空鏈域。 （2分）A.2 B.3 C.4 D.5 .標(biāo)準(zhǔn)答案：C36. 下面敘述錯誤的是（）。 （2分）A.借助于?？梢詫?shí)現(xiàn)對圖的深度優(yōu)先遍歷B.對矩陣進(jìn)行壓縮存儲后無法實(shí)現(xiàn)對其元素進(jìn)行隨機(jī)訪問C.樹的結(jié)點(diǎn)度是指結(jié)點(diǎn)的分支數(shù)D.空串的長度為零.標(biāo)準(zhǔn)答案：B37. 以下數(shù)據(jù)結(jié)構(gòu)中，（）是線性結(jié)構(gòu)。 （2分）A.二維數(shù)組 B.二叉樹 C.特殊矩陣 D.棧 .標(biāo)準(zhǔn)答案：D38. 在一個長度為n的鏈?zhǔn)綏Ｖ谐鰲?shí)現(xiàn)算法的時間復(fù)雜度為（）。 （2分）A.O(1)B.O(log n)C.O(n)D.標(biāo)準(zhǔn)答案：A39. 在具有4個葉子的二叉樹中，必有（）個度數(shù)為2的結(jié)點(diǎn)。 （2分）A.4 B.3 C.2 D.1 .標(biāo)準(zhǔn)答案：B40. 在關(guān)鍵字序列（10,15,20,25,30）中，采用折半法查找25，關(guān)鍵字之間比較需要（）次。 （2分）A.1 B.2 C.3 D.4 .標(biāo)準(zhǔn)答案：B41. 某二叉樹的后序遍歷序列和和中序遍歷序列分別為cba和bca，該二叉樹的前序遍歷序列是（）。 （2分）A.cba B.bca C.abc D.acb .標(biāo)準(zhǔn)答案：C42. 4個頂點(diǎn)的無向連通網(wǎng)的最小成本樹，至少有（）個邊。 （2分）A.0 B.1 C.2 D.3.標(biāo)準(zhǔn)答案：D43. 可以采用（）這種數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)二叉樹的層次遍歷運(yùn)算。 （2分）A.隊(duì)列 B.樹 C.棧 D.集合 .標(biāo)準(zhǔn)答案：A44. 線性表采用帶頭結(jié)點(diǎn)單鏈表實(shí)現(xiàn)，head為頭指針，則判斷表空的條件為（）。 （2分）A.B.C.D.標(biāo)準(zhǔn)答案：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.標(biāo)準(zhǔn)答案：B46. 算法分析的內(nèi)容是對算法的（）分析。 （2分）A.時間效率 B.空間效率 C.可行性 D.正確性 .標(biāo)準(zhǔn)答案：A,B47. 在n個數(shù)據(jù)元素中進(jìn)行查找，（）方法的平均時間復(fù)雜度為O(n)。 （2分）A.順序查找 B.折半查找 C.二叉排序樹查找 D.分塊查找 .標(biāo)準(zhǔn)答案：B,C48. 下列各項(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,D49. 下列（）是限制了插入和刪除操作的特殊線性表。 （2分）A.棧 B.隊(duì)列 C.串 D.數(shù)組 .標(biāo)準(zhǔn)答案：A,B50. 下列（）哈希函數(shù)構(gòu)造方法所得的哈希函數(shù)，使得查找時間復(fù)雜度通常不能到達(dá)O(1)。 （2分）A.直接定地法 B.數(shù)字分析法 C.平方取中法 D.折疊法 .標(biāo)準(zhǔn)答案：B,C,D51. 數(shù)據(jù)的邏輯結(jié)構(gòu)是由（）部分組成的。 （2分）A.2 B.3 C.4 D.5 .標(biāo)準(zhǔn)答案：A52. 下列時間復(fù)雜度中，（）表示的復(fù)雜度是最高的。 （2分）A.B.O(n2)C.D.O(n).標(biāo)準(zhǔn)答案：B53. 棧和隊(duì)列的共同點(diǎn)是（）。 （2分）A.進(jìn)出原則都是先進(jìn)先出B.進(jìn)出原則都是后進(jìn)先出C.都是插入刪除操作受限的線性表D.不允許在任意端點(diǎn)處插入和刪除元素.標(biāo)準(zhǔn)答案：C54. （）是限制了數(shù)據(jù)元素的內(nèi)部結(jié)構(gòu)僅為一個字符的線性表。 （2分）A.棧 B.隊(duì)列 C.串 D.數(shù)組 .標(biāo)準(zhǔn)答案：B55. 二維數(shù)組通常采用順序存儲，其優(yōu)點(diǎn)是（）。 （2分）A.便于增加存儲空間 B.防止下標(biāo)溢出 C.避免數(shù)據(jù)元素的移動 D.便于依據(jù)下標(biāo)進(jìn)行隨機(jī)存取 .標(biāo)準(zhǔn)答案：D56. 下列給出的操作中，（）是允許對隊(duì)列進(jìn)行的操作。 （2分）A.刪除隊(duì)首元素 B.取出最近進(jìn)隊(duì)的元素 C.按元素大小排序 D.中間插入元素 .標(biāo)準(zhǔn)答案：A57. 采用帶頭結(jié)點(diǎn)的單鏈表存儲的線性表，若表長為9，在第4號元素之前插入一個元素時，需要移動指針（）次。 （2分）A.1 B.2 C.3 D.4 .標(biāo)準(zhǔn)答案：C58. 數(shù)組采用順序存儲，a的首地址為1024，每個元素占4字節(jié)，則a17的地址是（）。 （2分）A.1040 B.1056 C.1072 D.1088 .標(biāo)準(zhǔn)答案：D59. 深度為4的二叉樹，第4層最多有（）個結(jié)點(diǎn)。 （2分）A.0 B.1 C.8 D.15 .標(biāo)準(zhǔn)答案：C60. 若二叉樹對應(yīng)的二叉鏈表共有4個非空鏈域，則該二叉樹有（）個結(jié)點(diǎn)的二叉樹。 （2分）A.2 B.3 C.4 D.5 .標(biāo)準(zhǔn)答案：B61. 下面敘述錯誤的是（）。 （2分）A.借助于隊(duì)列可以實(shí)現(xiàn)對圖的廣度優(yōu)先遍歷B.二叉樹中序遍歷的序列是有序C.只有一個結(jié)點(diǎn)的二叉樹的度為0D.空格串是指由1個或以上的空格符號組成的串.標(biāo)準(zhǔn)答案：B62. 以下（）術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān) （2分）A.串 B.哈希表 C.線索樹 D.單鏈表 .標(biāo)準(zhǔn)答案：A63. 在一個長度為n的鏈?zhǔn)疥?duì)列中出隊(duì)實(shí)現(xiàn)算法的時間復(fù)雜度為（）。 （2分）A.O(1) B.O(log n) C.O(n) D.O(n2) .標(biāo)準(zhǔn)答案：A64. 在具有4個度數(shù)為2的二叉樹中，必有（）個葉子結(jié)點(diǎn)。 （2分）A.2 B.3 C.4 D.5 .標(biāo)準(zhǔn)答案：D65. 在關(guān)鍵字序列（10,15,20,25,30）中采用折半法查找25，依次與（）關(guān)鍵字進(jìn)行了比較。 （2分）A.30,25 B.20,25 C.20，30，25 D.25 .標(biāo)準(zhǔn)答案：B66. 某二叉樹的前序遍歷序列和和中序遍歷序列分別為abc和bca，該二叉樹的后序遍歷序列是（）。 （2分）A.cba B.bca C.abc D.acb .標(biāo)準(zhǔn)答案：A67. 4個頂點(diǎn)的無向圖，最多有（）個邊。 （2分）A.3 B.4 C.5 D.6 .標(biāo)準(zhǔn)答案：D68. 可以采用（）這種數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)表達(dá)式中左右括號是否配對出現(xiàn)判別的運(yùn)算。 （2分）A.隊(duì)列 B.樹 C.棧 D.集合 .標(biāo)準(zhǔn)答案：C69. 假設(shè)以數(shù)組A0.n-1存放循環(huán)隊(duì)列的元素，其頭指針front指向隊(duì)頭元素、尾指針rear指向隊(duì)尾元素一個，則在少用一個元素空間的前提下，隊(duì)列空的判定條件為（）。 （2分）A.B.C.D.標(biāo)準(zhǔn)答案：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 .標(biāo)準(zhǔn)答案：B71. 算法具有的5個特性，（）均為算法的特性之一。 （2分）A.有窮性 B.確定性 C.可行性 D.正確性 .標(biāo)準(zhǔn)答案：A,B,C72. 在下列數(shù)據(jù)結(jié)構(gòu)中，（）屬于非線性結(jié)構(gòu)。 （2分）A.串 B.棧 C