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

1、專升本數(shù)據(jù)結(jié)構(gòu)-試卷-答案hC2h-iD.2hB2hD.2hB2h-1專升本數(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)答案：A2（）是數(shù)據(jù)的不可分割的最小單位。（2分）A數(shù)據(jù)對(duì)象B數(shù)據(jù)元素C數(shù)據(jù)類型D數(shù)據(jù)項(xiàng)標(biāo)準(zhǔn)答案：D3算法的空間復(fù)雜度是對(duì)算法（）的度量。（2分）A時(shí)間效率B空間效率C可讀性D健壯性標(biāo)準(zhǔn)答案：B4（）是限制了數(shù)據(jù)元素的內(nèi)部結(jié)構(gòu)僅為一個(gè)字符的線性表。（2分）A棧B.隊(duì)列C串D數(shù)組標(biāo)準(zhǔn)答案：B5串的長(zhǎng)度是指串中所含（）的個(gè)數(shù)。（2分）A不同字符B不同字母C相同字符D所有字符標(biāo)準(zhǔn)答案：D6采用帶頭結(jié)點(diǎn)雙向鏈表存儲(chǔ)的線性表

2、，在刪除一個(gè)元素時(shí)，需要修改指針（）次。 （2分）A1B2C3D4標(biāo)準(zhǔn)答案：B7線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（）的存儲(chǔ)結(jié)構(gòu)。（2分）A順序存取B隨機(jī)存取C索引存取DHash存取標(biāo)準(zhǔn)答案：B8數(shù)組a1m采用順序存儲(chǔ)，a1和am地址分別為1024和1150,每個(gè)元素占2字節(jié)，則m是（）。（2分）A64B32C16D.8標(biāo)準(zhǔn)答案：A9深度為h的二叉樹(shù)，第h層最多有（）個(gè)結(jié)點(diǎn)。（2分）10m個(gè)結(jié)點(diǎn)的二叉樹(shù)，其對(duì)應(yīng)的二叉鏈表共有（）個(gè)非空鏈域。（2分）AmBm+1C2mDm-1標(biāo)準(zhǔn)答案：B11下面敘述錯(cuò)誤的是（）。（2分）A順序表是借助物理單元相鄰表示數(shù)據(jù)元素之間的邏輯關(guān)系B.對(duì)于空隊(duì)列進(jìn)行出隊(duì)操作過(guò)程中

3、發(fā)生下溢現(xiàn)象C有向圖的鄰接矩陣一定是對(duì)稱的D具有相同的葉子個(gè)數(shù)和具有相同的葉子權(quán)值的赫夫曼樹(shù)不是唯一的標(biāo)準(zhǔn)答案：C12以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)的術(shù)語(yǔ)是（）。（2分）A循環(huán)隊(duì)列B雙向鏈表C哈希表D數(shù)組標(biāo)準(zhǔn)答案：D13在一個(gè)長(zhǎng)度為n的鏈?zhǔn)綏Ｖ谐鰲?shí)現(xiàn)算法的時(shí)間復(fù)雜度為（）。（2分）AO（1）BO（log n）CO（n）DO（n2）標(biāo)準(zhǔn)答案：A14在具有k個(gè)度數(shù)為2的二叉樹(shù)中，必有（）個(gè)葉子結(jié)點(diǎn)。（2分）AkBk-1C2kDk+1標(biāo)準(zhǔn)答案：D15在關(guān)鍵字序列（10200,40,50）中，采用折半法查找20,關(guān)鍵字之間比較需要 （）次。（2分）A1B2C3D4標(biāo)準(zhǔn)答案：C1616某二叉樹(shù)的后序遍歷序列

4、和和中序遍歷序列均為abed，該二叉樹(shù)的前序遍歷 序列是（）。（2分）AabcdBdcbaCacbdDdbea標(biāo)準(zhǔn)答案：B17n個(gè)頂點(diǎn)的無(wú)向連通圖的生成樹(shù)，至少有（）個(gè)邊。（2分）An（n-1）Bn（n-1）/2 C2n Dn-1標(biāo)準(zhǔn)答案：D18.可以采用（）這種數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)二叉樹(shù)的層次遍歷運(yùn)算。（2分）A.隊(duì)列B樹(shù)C棧D集合標(biāo)準(zhǔn)答案：A假設(shè)以數(shù)組A 0n-1存放循環(huán)隊(duì)列的元素，其頭指針front指向隊(duì)頭元素、 尾指針rear指向隊(duì)尾元素一個(gè)，則在少用一個(gè)元素空間的前提下，隊(duì)列空的判定條 件為（）。（2分）A.rear= =frontB.（front+1） % n= =rearC.rear+

5、1= fontD.（rear+1） % n= =front標(biāo)準(zhǔn)答案：A序列（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)答案：B二叉鏈表適合作為（）的存儲(chǔ)結(jié)構(gòu)。（2分）A隊(duì)列B二叉樹(shù)C樹(shù)D森林標(biāo)準(zhǔn)答案：B,CD設(shè)哈希（Hash）函數(shù)為H（k）= k % 17,其中k為關(guān)鍵字，關(guān)鍵字（）是同義詞。（2 分）A.44,5,15B.28,45,62C.6,57,125D.201,31,48標(biāo)準(zhǔn)答案：B,CD下列各項(xiàng)鍵值

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

7、度是對(duì)算法（）的度量。（2分）A.時(shí)間效率B空間效率C可讀性D健壯性標(biāo)準(zhǔn)答案：A線性表若采用鏈?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二維數(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采用順序存儲(chǔ)的線性表，若表長(zhǎng)為n,在第i號(hào)元素之后插入一個(gè)元素時(shí)，需要 移動(dòng)（）個(gè)元素。（2分）A.i+1B.iC.n-iD.n-i+1標(biāo)準(zhǔn)答案：C若已知一個(gè)棧的入棧序列是1、2、3、4,其出棧序列不可能為。 （2分）A.1、4、3

8、、2B3、4、1、2C4、3、2、1D2、3、4、1標(biāo)準(zhǔn)答案：B數(shù)組a1256采用順序存儲(chǔ)，a的首地址為10,每個(gè)元素占2字節(jié)，則a21啲地址是（）。（2分）A.10B.30C.50D.70標(biāo)準(zhǔn)答案：C深度為h的完全二叉樹(shù)至少有（）個(gè)葉子結(jié)點(diǎn)。（2分）A.2（h-1）+1B.2（h-2）+14545在關(guān)鍵字序列（35，10, 第一趟之后所得結(jié)果為（）。A 10, 20，15, 25, 35C20， 10, 35, 25, 15標(biāo)準(zhǔn)答案：BC2h-1D2h-2標(biāo)準(zhǔn)答案：D若二叉樹(shù)對(duì)應(yīng)的二叉鏈表共有m個(gè)非空鏈域，則該二叉樹(shù)有（）個(gè)結(jié)點(diǎn)的二叉 樹(shù)。（2分）A.mB.m-1C.m+1D.2m標(biāo)準(zhǔn)答案：

9、B下面敘述錯(cuò)誤的是（）。（2分）A單鏈表是借助指針表示數(shù)據(jù)元素之間的邏輯關(guān)系B在順序棧的入棧操作過(guò)程中可能發(fā)生上溢現(xiàn)象C.具有相同的葉子個(gè)數(shù)和具有相同的葉子權(quán)值的赫夫曼樹(shù)是唯一的D無(wú)向圖的鄰接矩陣一定是對(duì)稱的標(biāo)準(zhǔn)答案：C37以下（）術(shù)語(yǔ)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)（2分）A棧B哈希表C線索樹(shù)D雙向鏈表標(biāo)準(zhǔn)答案：A在一個(gè)長(zhǎng)度為n的鏈?zhǔn)疥?duì)列中入隊(duì)實(shí)現(xiàn)算法的時(shí)間復(fù)雜度為（）。（2分）AO（1）B.OQog n）CO（n）D. O（n2）標(biāo)準(zhǔn)答案：A隊(duì)列的出隊(duì)操作是指（）操作。（2分）A隊(duì)尾刪除B隊(duì)頭刪除C隊(duì)尾插入D隊(duì)頭插入標(biāo)準(zhǔn)答案：B40在關(guān)鍵字序列（10,15,20,25,30）中采用折半法査找25,依次

10、與（）關(guān)鍵字進(jìn)行 了比較。（2分）A.3025B.2025C.20, 30，25D.25標(biāo)準(zhǔn)答案：B4116某二叉樹(shù)的前序遍歷序列和和中序遍歷序列分別為abed和bead,該二叉樹(shù) 的后序遍歷序列是（）。（2分）AcbdaBdebaCabcdDdeba標(biāo)準(zhǔn)答案：A42所占用的存儲(chǔ)空間大小僅與圖的頂點(diǎn)個(gè)數(shù)相關(guān)的存儲(chǔ)結(jié)構(gòu)是（）。（2分）A鄰接表B逆鄰接表C十字鏈表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)答案：C44線性表采用帶頭結(jié)點(diǎn)單鏈表實(shí)現(xiàn)，head為頭指針，則判斷表空的條件為（）。 （2分）Ahead= NULLBhead!=NULLC

11、head-next=NULLDhead-next !=NULL標(biāo)準(zhǔn)答案：C15, 20, 25）中采用最低位優(yōu)先排序（LSD）基數(shù)排序, （2分）B10, 20, 35, 15, 25D20, 10, 35, 15, 2546下列邏輯結(jié)構(gòu)中，（）為線性結(jié)構(gòu)。（2分）A棧B隊(duì)列C串D二叉樹(shù)標(biāo)準(zhǔn)答案：AQC 47深度為3的二叉樹(shù)可能的結(jié)點(diǎn)個(gè)數(shù)是（）。（2分） TOC o 1-5 h z A1B2C3D4標(biāo)準(zhǔn)答案：A,B 48下列各項(xiàng)鍵值（）序列是大頂堆的。（2分） HYPERLINK l bookmark0 o Current Document A23, 68,94,16,5B94,68,23,1

12、6, 5 HYPERLINK l bookmark2 o Current Document C94, 23,68,16,5D94,16,68,23, 5標(biāo)準(zhǔn)答案：B,C 49下列（）是限制了插入和刪除操作的特殊線性表。（2分）A棧B隊(duì)列C串D數(shù)組標(biāo)準(zhǔn)答案：AB50對(duì)一棵二叉排序樹(shù)，用（）方法進(jìn)行遍歷，不一定得到各結(jié)點(diǎn)鍵值的有序序列。（2分）A先根遍歷B中根遍歷C后根遍歷D層次遍歷標(biāo)準(zhǔn)答案：A,C,D 51數(shù)據(jù)的最小單位是（）。（2分）（）是算法具有的5（）是算法具有的5個(gè)特性D健壯性D十字鏈表A數(shù)據(jù)元素B記錄標(biāo)準(zhǔn)答案：D 52算法是對(duì)某一類問(wèn)題求解步驟的有限序列。其中, 之一。（2分）A有窮性

13、B正確性C可讀性標(biāo)準(zhǔn)答案：A 53（）是數(shù)據(jù)的邏輯結(jié)構(gòu)。（2分）A順序表B鏈表C線性表標(biāo)準(zhǔn)答案：C 54（）是限制了插入和刪除操作在一端進(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)答案：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,其出棧序列不可能為（）。（2分）A.1、4、3、2B.2、3、4、1C.4、3、2、1D.3、4、1、2標(biāo)準(zhǔn)答案：D 58

14、串下列關(guān)于串的敘述中，正確的是（）。（2分） A.2個(gè)串的長(zhǎng)度相等，則2個(gè)串相等B空串至少包一個(gè)空格C替換操作可以實(shí)現(xiàn)字符的刪除D一個(gè)串的長(zhǎng)度至少是1標(biāo)準(zhǔn)答案：C 59深度為h的二叉樹(shù)，第h層至少有（）個(gè)結(jié)點(diǎn)。（2分）A0B1C8D1660假設(shè) n0 在程序段y=0;while（y+1）*（y+1）AnBCna標(biāo)準(zhǔn)答案：C61下面敘述錯(cuò)誤的是（）。（2分）A在集合1, 2, 3, 4, 5中元素1是2的直接前驅(qū)B二叉排序樹(shù)的中序遍歷序列一定是有序的C有 3個(gè)結(jié)點(diǎn)的不同形態(tài)二叉樹(shù)的數(shù)目為5D哈夫曼樹(shù)中所有結(jié)點(diǎn)的孩子數(shù)目只可能為2或者為0標(biāo)準(zhǔn)答案：A62以下數(shù)據(jù)結(jié)構(gòu)中，（）是線性結(jié)構(gòu)。（2分）A廣

15、義表B二叉樹(shù)C稀疏矩陣 D.串標(biāo)準(zhǔn)答案：D63在一個(gè)長(zhǎng)度為n的順序表中刪除一個(gè)元素的算法的時(shí)間復(fù)雜度為（）。（2分）AO（1）BO（log n）CO（n）DO（n2）標(biāo)準(zhǔn)答案：C64如果一個(gè)huffman樹(shù)含有n個(gè)葉子，則該樹(shù)必有（）的結(jié)點(diǎn)。（2分）An+1B2n+1 C2n D2n-1標(biāo)準(zhǔn)答案：D65在關(guān)鍵字序列（10,15,20,25,30）中，采用折半法査找25,關(guān)鍵字之間比較需要 （）次。（2分）A1B2C3D4標(biāo)準(zhǔn)答案：B6616某二叉樹(shù)的前序遍歷序列和和中序遍歷序列均為abed,該二叉樹(shù)的后序遍歷 序列是（）。（2分）Aabcd Bdcba Caebd Ddbea標(biāo)準(zhǔn)答案：B67m

16、個(gè)頂點(diǎn)的有向完全圖有（）個(gè)弧。（2分）Am（m-1）/2Bm+1 Cm Dm（m-1）標(biāo)準(zhǔn)答案：D68下列各項(xiàng)鍵值（）序列不是堆的。（2分）A94,68,23,16,5B94,23,68,5, 16C94,23,68,16,5D.94,16,68,23, 5標(biāo)準(zhǔn)答案：D設(shè)單鏈表中指針p指向結(jié)點(diǎn)A, q指向新元素結(jié)點(diǎn)，若要A之后插入一個(gè)新元 素，則所需修改指針的操作為（）。（2分）Ap-next=q, q-next=p-nextq-next=p-next, p-next=qp-next=q-next, q-next=pp-next=p, q-next=p-next標(biāo)準(zhǔn)答案：B在關(guān)鍵字序列（149, 138, 165, 197, 176, 113, 127）中采用最低位優(yōu)先排序（LSD）基數(shù)排序，第一趟之后所得結(jié)果為（）。（2分）149, 138, 165, 197, 176, 113, 127128, 149, 1砧，197, 113, 176, 127128, 149, 165, 197, 113, 127, 176113, 127, 138, 149, 165, 176, 197標(biāo)準(zhǔn)答案：B下列術(shù)語(yǔ)表示的數(shù)據(jù)中，（）是同義語(yǔ)。（2分）A結(jié)點(diǎn)B數(shù)據(jù)元素C頂點(diǎn)D數(shù)據(jù)項(xiàng)標(biāo)準(zhǔn)答案