專(zhuān)升本《數(shù)據(jù)結(jié)構(gòu)》模擬題試卷

1、 專(zhuān)升本數(shù)據(jù)結(jié)構(gòu)模擬題試卷 一. （共 75 題,共 150 分） 1.數(shù)據(jù)的基本單位是（）。 （2分） A. 數(shù)據(jù)元素 B. 記錄 C. 數(shù)據(jù)對(duì)象 D. 數(shù)據(jù)項(xiàng) 檢查答案標(biāo)準(zhǔn)答案：A 2.（）是數(shù)據(jù)的不可分割的最小單位。 （2 分） A.數(shù)據(jù)對(duì)象 B. 數(shù)據(jù)元素 C. 數(shù)據(jù)類(lèi)型 D. 數(shù)據(jù)項(xiàng) 檢查答案標(biāo)準(zhǔn)答案：D 3.算法的空間復(fù)雜度是對(duì)算法（）的度量。 A. 時(shí)間效率 B. 空間效率 C. 可讀性 D. 健壯性 檢查答案標(biāo)準(zhǔn)答案：B （2 分） 4.（）是限制了數(shù)據(jù)元素的內(nèi)部結(jié)構(gòu)僅為一個(gè)字符的線性表。 A. 棧 B. 隊(duì)列 C. 串 D. 數(shù)組 檢查答案標(biāo)準(zhǔn)答案：B （2 分） 5.串的長(zhǎng)

2、度是指串中所含（）的個(gè)數(shù)。 （2分） A. 不同字符 B. 不同字母 C. 相同字符 D. 所有字符 檢查答案標(biāo)準(zhǔn)答案：D 6.采用帶頭結(jié)點(diǎn)雙向鏈表存儲(chǔ)的線性表，在刪除一個(gè)元素時(shí)，需要修改指針（）次。 （2 分） A. 1 B. 2 C. 3 D. 4 檢查答案標(biāo)準(zhǔn)答案：B 7. 線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（）的存儲(chǔ)結(jié)構(gòu)。 （2 分） A. 順序存取 B. 隨機(jī)存取 C. 索引存取 D. Hash存取 檢查答案標(biāo)準(zhǔn)答案：B 8. 數(shù)組 a1.m采用順序存儲(chǔ)， a1和 am地址分別為 1024 和 1150， 每個(gè)元素占 2 字節(jié), 則 m 是 （） 。（2 分） A. 64 B. 32 C.

3、16 D. 8 檢查答案標(biāo)準(zhǔn)答案：A 9. 深度為 h的二叉樹(shù)，第 h層最多有（）個(gè)結(jié)點(diǎn)。 （2 分） A. h B. 2h-1 C. 2h-1 D. 2h 檢查答案標(biāo)準(zhǔn)答案：C 10. m 個(gè)結(jié)點(diǎn)的二叉樹(shù)，其對(duì)應(yīng)的二叉鏈表共有（）個(gè)非空鏈域。 （2 分） A. m B. m+1 C. 2m D. m-1 檢查答案標(biāo)準(zhǔn)答案：B 11. 下面敘述錯(cuò)誤的是（）。（2 分） A. 順序表是借助物理單元相鄰表示數(shù)據(jù)元素之間的邏輯關(guān)系 B. 對(duì)于空隊(duì)列進(jìn)行出隊(duì)操作過(guò)程中發(fā)生下溢現(xiàn)象 C. 有向圖的鄰接矩陣一定是對(duì)稱(chēng)的 D. 具有相同的葉子個(gè)數(shù)和具有相同的葉子權(quán)值的赫夫曼樹(shù)不是唯一的 檢查答案標(biāo)準(zhǔn)答案：C

4、 12. 以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)的術(shù)語(yǔ)是（） 。（2 分） A. 循環(huán)隊(duì)列 B. 雙向鏈表 C. 哈希表 D. 數(shù)組 檢查答案標(biāo)準(zhǔn)答案：D 13. 在一個(gè)長(zhǎng)度為 n的鏈?zhǔn)綏Ｖ谐鰲?shí)現(xiàn)算法的時(shí)間復(fù)雜度為（） 。（2 分） A. 0（1） B. O（log n） C. 0（ n） D. 0（ n2） 檢查答案標(biāo)準(zhǔn)答案：A 14. 在具有 k 個(gè)度數(shù)為 2 的二叉樹(shù)中，必有（）個(gè)葉子結(jié)點(diǎn)。 （2 分） A. k B. k-1 C. 2k D. k+1 檢查答案標(biāo)準(zhǔn)答案：D 15. 在關(guān)鍵字序列（10,20,30,40,50 ）中，采用折半法查找 20，關(guān)鍵字之間比較需要（） 次。（2 分） A.

5、1 B. 2 C. 3 D. 4 檢查答案標(biāo)準(zhǔn)答案：C 16. 16 某二叉樹(shù)的后序遍歷序列和和中序遍歷序列均為 abed，該二叉樹(shù)的前序遍歷序列是 （）。（2 分） A. abed B. deba C. aebd D. dbea 檢查答案標(biāo)準(zhǔn)答案：B 17. n個(gè)頂點(diǎn)的無(wú)向連通圖的生成樹(shù)，至少有（）個(gè)邊。 （2 分） A. n（n-1） B. n（n-1）/2 C. 2 n D. n-1 檢查答案標(biāo)準(zhǔn)答案：D 18. 可以采用（）這種數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)二叉樹(shù)的層次遍歷運(yùn)算。 （2 分） A. 隊(duì)列 B. 樹(shù) C. 棧 D. 集合 檢查答案標(biāo)準(zhǔn)答案：A 19. 假設(shè)以數(shù)組 A0.n-1 存放循環(huán)隊(duì)

6、列的元素，其頭指針 front 指向隊(duì)頭元素、尾指針 rear 指向隊(duì)尾元素一個(gè)，則在少用一個(gè)元素空間的前提下，隊(duì)列空的判定條件為（） 。（2 分） A. rear= =front B. （front+1） % n= =rear C. rear+1= =front D. （rear+1） % n= =front 檢查答案標(biāo)準(zhǔn)答案：A 20. 序列(21, 19, 37, 5, 2)經(jīng)冒泡排序法由小到大排序，第一趟后所得結(jié)果為() 分) A. (19 , 21, 37, 5, 2) B. (19 , 21, 5, 2, 37) C. (19 , 21, 5, 37, 2) D. (19 , 21

7、, 2, 5, 37) 檢查答案標(biāo)準(zhǔn)答案：B A. 隊(duì)列 B. 二叉樹(shù) C. 樹(shù) D. 森林 檢查答案標(biāo)準(zhǔn)答案：B,C,D(2 21.二叉鏈表適合作為（）的存儲(chǔ)結(jié)構(gòu)。 (2 分) 27.（）不是算法具有的 5 個(gè)特性之一。 （2 分） 22. 設(shè)哈希（Hash）函數(shù)為 H（k）= k % 17,其中 k 為關(guān)鍵字，關(guān)鍵字（）是同義詞。 （2 分） A. 44,5,15 B. 28,45,62 C. 6,57,125 D. 201,31,48 檢查答案標(biāo)準(zhǔn)答案：B,C,D 23. 下列各項(xiàng)鍵值（）序列不是堆的。 （2 分） A. 94 ，68，23，16，5 B. 94 ，23，68，5，16

8、C. 94 ，23，16，68，5 D. 94，16，68，23，5 檢查答案標(biāo)準(zhǔn)答案： C,D 24. 在下列排序方法中，（）的空間復(fù)雜度為 0（n）。其中，n 為參加排序的元素個(gè)數(shù)。 （2 分） A. 選擇排序 B. 快速排序 C. 歸并排序 D. 冒泡排序 檢查答案標(biāo)準(zhǔn)答案：B,C 25. 十字鏈表適合于（）選作存儲(chǔ)結(jié)構(gòu)。 A. 隊(duì)列 B. 稀疏矩陣 C. 邊或弧數(shù)較少的圖 D. 二叉樹(shù) 檢查答案標(biāo)準(zhǔn)答案：B,C 26. 基于數(shù)據(jù)的邏輯關(guān)系，數(shù)據(jù)的邏輯結(jié)構(gòu)劃分為（）基本結(jié)構(gòu)。 （2 分） A. 6 類(lèi) B. 5 類(lèi) C. 4 類(lèi) D. 3 類(lèi) 檢查答案標(biāo)準(zhǔn)答案：C（2 分） A. 有窮性

9、 B. 確定性 C. 可行性 D. 正確性 檢查答案標(biāo)準(zhǔn)答案：D 28. 算法的時(shí)間復(fù)雜度是對(duì)算法（）的度量。 （2分） A. 時(shí)間效率 B. 空間效率 C. 可讀性 D. 健壯性 檢查答案標(biāo)準(zhǔn)答案：A 29. 線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求結(jié)點(diǎn)的存儲(chǔ)單元地址（） 。（2 分） A. 必須是連續(xù)的 B. 部分地址必須是連續(xù)的 C. 必須是不連續(xù)的 D. 連續(xù)或不連續(xù)都可以 檢查答案標(biāo)準(zhǔn)答案：D 30. 二維數(shù)組通常采用順序存儲(chǔ)，其優(yōu)點(diǎn)是（） 。（2分） A. 便于增加存儲(chǔ)空間 B. 防止下標(biāo)溢出 C. 避免數(shù)據(jù)元素的移動(dòng) D. 便于依據(jù)下標(biāo)進(jìn)行隨機(jī)存取 檢查答案標(biāo)準(zhǔn)答案：D 31. 采用順序

10、存儲(chǔ)的線性表， 若表長(zhǎng)為 n，在第 i 號(hào)元素之后插入一個(gè)元素時(shí), 個(gè)元素。 （2 分） A. i+1 B. i C. n-i D. n-i+1 需要移動(dòng)（） （2 分） 檢查答案標(biāo)準(zhǔn)答案：C 32. 若已知一個(gè)棧的入棧序列是 1、2、3、4,其出棧序列不可能為 A. 1 、4、3、2 B. 3 、 4、 1、 2 C. 4、3、2、1 D. 2、3、4、1 檢查答案標(biāo)準(zhǔn)答案：B 33. 數(shù)組 a1.256采用順序存儲(chǔ)，a 的首地址為 10,每個(gè)元素占 2 字節(jié)，則 a21的地址 是（）。（2分） A. 10 B. 30 C. 50 D. 70 檢查答案標(biāo)準(zhǔn)答案：C 34. 深度為 h的完全二

11、叉樹(shù)至少有（）個(gè)葉子結(jié)點(diǎn)。 （2 分） A. 2（h-1）+1 B. 2（h-2）+1 C. 2h-1 D. 2h-2 檢查答案標(biāo)準(zhǔn)答案：D 35. 若二叉樹(shù)對(duì)應(yīng)的二叉鏈表共有 m個(gè)非空鏈域，則該二叉樹(shù)有（）個(gè)結(jié)點(diǎn)的二叉樹(shù)。 （2 分） A. m B. m-1 C. m+1 D. 2m 檢查答案標(biāo)準(zhǔn)答案：B 36. 下面敘述錯(cuò)誤的是（）。（2 分） A. 單鏈表是借助指針表示數(shù)據(jù)元素之間的邏輯關(guān)系 B. 在順序棧的入棧操作過(guò)程中可能發(fā)生上溢現(xiàn)象 C. 具有相同的葉子個(gè)數(shù)和具有相同的葉子權(quán)值的赫夫曼樹(shù)是唯一的 D. 無(wú)向圖的鄰接矩陣一定是對(duì)稱(chēng)的 檢查答案標(biāo)準(zhǔn)答案：C 37. 以下（）術(shù)語(yǔ)與數(shù)據(jù)的

12、存儲(chǔ)結(jié)構(gòu)無(wú)關(guān) （2 分） A. 棧 B. 哈希表 C. 線索樹(shù) D. 雙向鏈表 檢查答案標(biāo)準(zhǔn)答案：A 38. 在一個(gè)長(zhǎng)度為 n的鏈?zhǔn)疥?duì)列中入隊(duì)實(shí)現(xiàn)算法的時(shí)間復(fù)雜度為（） 。（2 分） A. 0（1） B. O（log n） C. 0（ n） D. 0（ n2） 檢查答案標(biāo)準(zhǔn)答案：A 39. 隊(duì)列的出隊(duì)操作是指（）操作。 （2 分） A. 隊(duì)尾刪除 B. 隊(duì)頭刪除 C. 隊(duì)尾插入 D. 隊(duì)頭插入 檢查答案標(biāo)準(zhǔn)答案：B 40. 在關(guān)鍵字序列（10,15,20,25,30 ）中采用折半法查找 25,依次與（）關(guān)鍵字進(jìn)行了比 較。（2 分） A. 30,25 B. 20,25 C. 20，30，25

13、D. 25 檢查答案標(biāo)準(zhǔn)答案：B 41. 16 某二叉樹(shù)的前序遍歷序列和和中序遍歷序列分別為 abed 和 bead，該二叉樹(shù)的后序遍 歷序列是（）。（2 分） A. ebda B. deba C. abed D. deba 檢查答案標(biāo)準(zhǔn)答案：A 42. 所占用的存儲(chǔ)空間大小僅與圖的頂點(diǎn)個(gè)數(shù)相關(guān)的存儲(chǔ)結(jié)構(gòu)是（） 。（2 分） A. 鄰接表 B. 逆鄰接表 C. 十字鏈表 D. 鄰接矩陣 檢查答案標(biāo)準(zhǔn)答案：D 43. 可以采用（）這種數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)圖的深度優(yōu)先遍歷運(yùn)算。 （2 分） A. 隊(duì)列 B. 樹(shù) C. 棧 D. 集合 檢查答案標(biāo)準(zhǔn)答案：C 44. 線性表采用帶頭結(jié)點(diǎn)單鏈表實(shí)現(xiàn), A. h

14、ead= NULL B. head!=NULL C. head- next=NULL D. head-next !=NULL 檢查答案標(biāo)準(zhǔn)答案：C 之后所得結(jié)果為（） 1 。 （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)答案：BA. 棧 B. 隊(duì)列 C. 串 47. 深度為 3 的二叉樹(shù)可能的結(jié)點(diǎn)個(gè)數(shù)是（）。（2 分） A. 1 B. 2 C. 3 D. 4 檢查答案標(biāo)準(zhǔn)答案：A,B head為頭指45.在關(guān)鍵字序列（35, 10，15，20， 2

15、5）中采用最低位優(yōu)先排序 （LSD）基數(shù)排序，第一趟 46.下列邏輯結(jié)構(gòu)中, （） 為線性結(jié)構(gòu)。 （2 D.二叉樹(shù) 檢查答案標(biāo)準(zhǔn)答案: A,B,C 48. 下列各項(xiàng)鍵值（）序列是大頂堆的。 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,C 49. 下列（）是限制了插入和刪除操作的特殊線性表。 （2 分） A. 棧 B. 隊(duì)列 C. 串 D. 數(shù)組 檢查答案標(biāo)準(zhǔn)答案：A,B 50. 對(duì)一棵二叉排序樹(shù)，用（）方法進(jìn)行遍歷，不一定得到各結(jié)點(diǎn)鍵值的有序序列。 分） A

16、. 先根遍歷 B. 中根遍歷 C. 后根遍歷 D. 層次遍歷 檢查答案標(biāo)準(zhǔn)答案：A,C,D 51. 數(shù)據(jù)的最小單位是（）。（2 分） A. 數(shù)據(jù)元素 B. 記錄 C. 數(shù)據(jù)對(duì)象 D. 數(shù)據(jù)項(xiàng) 檢查答案標(biāo)準(zhǔn)答案：D 52. 算法是對(duì)某一類(lèi)問(wèn)題求解步驟的有限序列。 其中，（）是算法具有的 5 個(gè)特性之一。（2 分） A. 有窮性 B. 正確性 C. 可讀性 D. 健壯性 檢查答案標(biāo)準(zhǔn)答案：A 53. （）是數(shù)據(jù)的邏輯結(jié)構(gòu)。 （2 分） （2 (2 A. 順序表 B. 鏈表 C. 線性表 D. 十字鏈表 檢查答案標(biāo)準(zhǔn)答案：C 54. （） 是限制了插入和刪除操作在一端進(jìn)行的線性表。 （2 分） A.

17、 棧 B. 隊(duì)列 C. 串 D. 數(shù)組 檢查答案標(biāo)準(zhǔn)答案：A 55. （）是限制了插入和刪除操作分別在兩端進(jìn)行的線性表。 （2分） A. 棧 B. 隊(duì)列 C. 串 D. 數(shù)組 檢查答案標(biāo)準(zhǔn)答案：B 56. 用鏈表表示線性表的優(yōu)點(diǎn)是（）。（2 分） A. 便于插入和刪除 B. 便于隨機(jī)存取 C. 花費(fèi)的存儲(chǔ)空間較順序存儲(chǔ)少 D. 數(shù)據(jù)元素的物理順序與邏輯順序相同 檢查答案標(biāo)準(zhǔn)答案：A 57. 若已知一個(gè)棧的入棧序列是 1、2、3、4,其出棧序列不可能為（） A. 1、4、3、2 B. 2、3、4、1 C. 4、3、2、1 D. 3、4、1、2 檢查答案標(biāo)準(zhǔn)答案：D 58. 串下列關(guān)于串的敘述中，

18、正確的是（） 。（2 分） A. 2 個(gè)串的長(zhǎng)度相等，則 2 個(gè)串相等 B. 空串至少包一個(gè)空格 C. 替換操作可以實(shí)現(xiàn)字符的刪除 （2 D. 一個(gè)串的長(zhǎng)度至少是 1 檢查答案標(biāo)準(zhǔn)答案：C 59.深度為 h的二叉樹(shù)，第 h層至少有（）個(gè)結(jié)點(diǎn)。 （2 分） A. O B.1 C.8 D.16 檢查答案標(biāo)準(zhǔn)答案：B 60.假設(shè) n0,在程序段 y=0;while（y+1）*（y+1）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-next 檢查答案標(biāo)準(zhǔn)答案：B 70. 在關(guān)鍵字序列（149, 138, 165, 197, 176, 113, 127 ）中采用最低位優(yōu)先排序 基數(shù)排序，第一趟之后所得結(jié)果為（） 。