專(zhuān)升本《數(shù)據(jù)結(jié)構(gòu)》一、（共75題，共150分）數(shù)據(jù)的基本單位是（）。（2分）數(shù)據(jù)元素 B.記錄 C.數(shù)據(jù)對(duì)象 D.數(shù)據(jù)項(xiàng).標(biāo)準(zhǔn)答案：A（）是數(shù)據(jù)的不可分割的最小單位。（2分）A.數(shù)據(jù)對(duì)象.標(biāo)準(zhǔn)答案：DB.數(shù)據(jù)元素C.數(shù)據(jù)類(lèi)型D.數(shù)據(jù)項(xiàng)3.算法的空間復(fù)雜度是對(duì)算法（）的度量。 （2分）A.時(shí)間效率B.空間效率C.可讀性D.健壯性.標(biāo)準(zhǔn)答案：B4.（）是限制了數(shù)據(jù)元素的內(nèi)部結(jié)構(gòu)僅為一個(gè)字符的線性表。（2分）A.棧.標(biāo)準(zhǔn)答案：BB.隊(duì)列C.串D.數(shù)組5.串的長(zhǎng)度是指串中所含（）的個(gè)數(shù)。 （2分）A.不同字符B.不同字母C.相同字符D.所有字符.標(biāo)準(zhǔn)答案：D6.采用帶頭結(jié)點(diǎn)雙向鏈表存儲(chǔ)的線性表,在刪除一個(gè)元素時(shí),需要修改指針（）次。（2分）A.1B.2C.3D.4.標(biāo)準(zhǔn)答案：B7.線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（）的存儲(chǔ)結(jié)構(gòu)。（2分）A.順序存取B.隨機(jī)存取C.索引存取存取.標(biāo)準(zhǔn)答案：B

數(shù)組a[1]采用順序存儲(chǔ)，a[1]和a[m]地址分別為1024和1150,每個(gè)元素占2字節(jié)，則m是（）。 （2分）TOC\o"1-5"\h\z\o"CurrentDocument"64 B.32 C.16 D.8.標(biāo)準(zhǔn)答案：A深度為h的二叉樹(shù),第h層最多有（）個(gè)結(jié)點(diǎn)。（2分）2121 D.2h.標(biāo)準(zhǔn)答案：Cm個(gè)結(jié)點(diǎn)的二叉樹(shù)，其對(duì)應(yīng)的二叉鏈表共有（）個(gè)非空鏈域。 （2分）\o"CurrentDocument"1 C.2m 1.標(biāo)準(zhǔn)答案：B下面敘述錯(cuò)誤的是（）。 （2分）順序表是借助物理單元相鄰表示數(shù)據(jù)元素之間的邏輯關(guān)系對(duì)于空隊(duì)列進(jìn)行出隊(duì)操作過(guò)程中發(fā)生下溢現(xiàn)象有向圖的鄰接矩陣一定是對(duì)稱(chēng)的具有相同的葉子個(gè)數(shù)和具有相同的葉子權(quán)值的赫夫曼樹(shù)不是唯一的.標(biāo)準(zhǔn)答案：C以下與數(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在一個(gè)長(zhǎng)度為n的鏈?zhǔn)綏Ｖ谐鰲?shí)現(xiàn)算法的時(shí)間復(fù)雜度為（）。（2分）TOC\o"1-5"\h\z\o"CurrentDocument"（1） （n）（n） （n2）.標(biāo)準(zhǔn)答案：A在具有k個(gè)度數(shù)為2的二叉樹(shù)中,必有（）個(gè)葉子結(jié)點(diǎn)。 （2分）\o"CurrentDocument"-1 C.2k 1.標(biāo)準(zhǔn)答案：D15.在關(guān)鍵字序列(10,20,30,40,50)中，采用折半法查找20,關(guān)鍵字之間比較需要()次。(2分)1 B.2 C.3 D.4.標(biāo)準(zhǔn)答案：C16某二叉樹(shù)的后序遍歷序列和和中序遍歷序列均為，該二叉樹(shù)的前序遍歷序列是()o(2分).標(biāo)準(zhǔn)答案：Bn個(gè)頂點(diǎn)的無(wú)向連通圖的生成樹(shù)，至少有()個(gè)邊。(2分)(1) (1)/2C.2n1.標(biāo)準(zhǔn)答案：D可以采用()這種數(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[01]存放循環(huán)隊(duì)列的元素，其頭指針指向隊(duì)頭元素、尾指旨向隊(duì)尾元素一個(gè)，則在少用一個(gè)元素空間的前提下，隊(duì)列空的判定條件為()o(2分)⑴％1= D.⑴％.標(biāo)準(zhǔn)答案：A經(jīng)冒泡須E序法由到大須E序，第一趟B.(19,21,5,2,37)D.經(jīng)冒泡須E序法由到大須E序，第一趟B.(19,21,5,2,37)D.(19,21,2,5,37)(19,21,37,5,2)(19,21,5,37,2).標(biāo)準(zhǔn)答案：B21.二叉鏈表適合作為()的存儲(chǔ)結(jié)構(gòu)。(2分)D.森林A.隊(duì)列 B.二叉樹(shù) C.D.森林.標(biāo)準(zhǔn)答案:22.設(shè)哈希（）函數(shù)為H（k）二k%17,其中k為關(guān)鍵字，關(guān)鍵字（）是同義詞。（2分）A.44,5,15 B.2&45,62C.6,57,125D.201,31,48.標(biāo)準(zhǔn)答案:TOC\o"1-5"\h\z23.下列各項(xiàng)鍵值（）序列不是堆的。 （2分）A.{94,68,23,16,5 B.{94,23,68,5,16C.{94,23,16,68,5 D.{94,16,68,23,5.標(biāo)準(zhǔn)答案:24.在下列排序方法中，（）的空間復(fù)雜度為O（n）。其中，n為參加須E序的元素個(gè)數(shù)。 （2分）A.選擇須E序 B.快速須E序 C.歸并須E序 D.冒泡須E序.標(biāo)準(zhǔn)答案:25.十字鏈表適合于（）選作存儲(chǔ)結(jié)構(gòu)。 （2分）A.隊(duì)列C.邊或弧數(shù)較少的圖.標(biāo)準(zhǔn)答案:B.稀疏矩陣D.二叉樹(shù)26.基于數(shù)據(jù)的邏輯關(guān)系，數(shù)據(jù)的邏輯結(jié)構(gòu)劃分為（）基本結(jié)構(gòu)。（2分）A.6類(lèi) B5類(lèi)C.4類(lèi)D.3類(lèi).標(biāo)準(zhǔn)答案：CTOC\o"1-5"\h\z（）不是算法具有的5個(gè)特性之一。 （2分）A.有窮性 B.確定性 C.可行性 D.正確性.標(biāo)準(zhǔn)答案：D（2分）（2分）D.健壯性時(shí)間效率 B.空間效率 C.可讀"生線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求結(jié)點(diǎn)的存儲(chǔ)單元地址（）。（2分）必須是連續(xù)的 B.部分地址必須是連續(xù)的C.必須是不連續(xù)的 D.連續(xù)或不連續(xù)都可以.標(biāo)準(zhǔn)答案：D二維數(shù)組通常采用順序存儲(chǔ)，其優(yōu)點(diǎn)是（）。（2分）便于增加存儲(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分）11.標(biāo)準(zhǔn)答案：C若已知一個(gè)棧的入棧序列是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.標(biāo)準(zhǔn)答案：B數(shù)組a[1..256]采用順序存儲(chǔ)，a的首地址為10,每個(gè)元素占2字TOC\o"1-5"\h\z節(jié)，貝Ua[21]的地址是（）。 （2分）A.10 B.30 C.50 D.70.標(biāo)準(zhǔn)答案：C深度為h的完全二叉樹(shù)至少有（）個(gè)葉子結(jié)點(diǎn)。 （2分）A.2（1）+1 B.2（2）+1C.21 D.22.標(biāo)準(zhǔn)答案：D若二叉樹(shù)對(duì)應(yīng)的二叉鏈表共有m個(gè)非空鏈域，則該二叉樹(shù)有（）個(gè)結(jié)點(diǎn)的二叉樹(shù)。（2分）-1 C1 D.2m.標(biāo)準(zhǔn)答案：B下面敘述錯(cuò)誤的是（）。（2分）A.單鏈表是借助指針表示數(shù)據(jù)元素之間的邏輯關(guān)系在順序棧的入棧操作過(guò)程中可能發(fā)生上溢現(xiàn)象具有相同的葉子個(gè)數(shù)和具有相同的葉子權(quán)值的赫夫曼樹(shù)是唯一的無(wú)向圖的鄰接矩陣一定是對(duì)稱(chēng)的.標(biāo)準(zhǔn)答案：C以下（）術(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ù)雜度為T(mén)OC\o"1-5"\h\z（）。 （2分）（1） （n）（n） （n2）.標(biāo)準(zhǔn)答案：A隊(duì)列的出隊(duì)操作是指（）操作。 （2分）A.隊(duì)尾刪除 B.隊(duì)頭刪除 C.隊(duì)尾插入 D.隊(duì)頭插入.標(biāo)準(zhǔn)答案：B在關(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)答案：B16某二叉樹(shù)的前序遍歷序列和和中序遍歷序列分別為和,該二叉樹(shù)的后序遍歷序列是（）。（2分）.標(biāo)準(zhǔn)答案：A所占用的存儲(chǔ)空間大小僅與圖的頂點(diǎn)個(gè)數(shù)相關(guān)的存儲(chǔ)結(jié)構(gòu)是（）。 （2分）A.鄰接表 B.逆鄰接表C.十字鏈表 D.鄰接矩陣.標(biāo)準(zhǔn)答案：D可以采用（）這種數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)圖的深度優(yōu)先遍歷運(yùn)算。 （2分）A.隊(duì)列 B樹(shù) C.棧 D.集合.標(biāo)準(zhǔn)答案：C為扌旨針，則判斷表空的條*線性表采用帶頭結(jié)點(diǎn)單鏈表實(shí)現(xiàn),為（）O（2分）為扌旨針，則判斷表空的條*.標(biāo)準(zhǔn)答案:C45.在關(guān)鍵字序列45.在關(guān)鍵字序列（35,10,15,20,25）中采用最低位優(yōu)先排序（）基數(shù)須E序，第一趟之后所得結(jié)果為（）o（2分）A.10,20,15,25,35A.10,20,15,25,35C.20,10,35,25,1510,20,35,15,2520,10,35,15,2546.下列邏輯結(jié)構(gòu)中，（）46.下列邏輯結(jié)構(gòu)中，（）為線性結(jié)構(gòu)。 （2分）A.棧B.隊(duì)列C.串.標(biāo)準(zhǔn)答案:D.二叉樹(shù)47.深度為3的二二叉樹(shù)可能的結(jié)點(diǎn)個(gè)數(shù)是（）。（2分）A.1B.2C.3D.4.標(biāo)準(zhǔn)答案:TOC\o"1-5"\h\z下列各項(xiàng)鍵值（）序列是大頂堆的。 （2分）\o"CurrentDocument"A.{23, 68,94,16, 5 B.{94, 68,23,16, 5\o"CurrentDocument"{94, 23,68,16, 5 D.{94, 16,68,23, 5.標(biāo)準(zhǔn)答案:下列（）是限制了插入和刪除操作的特殊線性表。 （2分）A.棧 A.棧 B.隊(duì)列 C.串D.數(shù)組.標(biāo)準(zhǔn)答案:對(duì)一棵二叉須E序樹(shù)，用（）方法進(jìn)行遍歷，不_定得到各結(jié)點(diǎn)鍵值的有序序列。 （2分）A.先根遍歷.標(biāo)準(zhǔn)答案:B.中根遍歷C.后根遍歷D.層次遍歷51.數(shù)據(jù)的最小單位是（）o（2分）D.數(shù)據(jù)項(xiàng)A.數(shù)據(jù)元素 B.記錄 C.D.數(shù)據(jù)項(xiàng).標(biāo)準(zhǔn)答案：D52.算法是對(duì)某一類(lèi)問(wèn)題求解步驟的有限序列。其中,有的5個(gè)特性之,一。（2分）A.有窮性B.正確性C.可讀性.標(biāo)準(zhǔn)答案：A（）是算法具D.健壯性TOC\o"1-5"\h\z（）是數(shù)據(jù)的邏輯結(jié)構(gòu)。 （2分）D.十字鏈表A.順序表 B.鏈表 C.D.十字鏈表（）是限制了插入和刪除操作在一端進(jìn)行的線性表。 （2分）A.棧 B.隊(duì)列 C.串 D.數(shù)組.標(biāo)準(zhǔn)答案：A（）是限制了插入和刪除操作分別在兩端進(jìn)行的線性表。 （2分）A.棧 B.隊(duì)列 C.串 D.數(shù)組.標(biāo)準(zhǔn)答案：B用鏈表表示線性表的優(yōu)點(diǎn)是（）。 （2分）便于插入和刪除便于隨機(jī)存取花費(fèi)的存儲(chǔ)空間較川頁(yè)序存儲(chǔ)少數(shù)據(jù)元素的物理川頁(yè)序與邏輯川頁(yè)序相同.標(biāo)準(zhǔn)答案：A若已知一個(gè)棧的入棧序列是1、2、3、4,其出棧序列不可能為0o（2分）A.1、4、3、2 B2、3、4、1C.4、3、2、1D.3、4、1、2.標(biāo)準(zhǔn)答案：D串下列關(guān)于串的敘述中，正確的是（）。 （2分）2個(gè)串的長(zhǎng)度相等，則2個(gè)串相等空串至少包一個(gè)空格替換操作可以實(shí)現(xiàn)字苻的刪除_個(gè)串的長(zhǎng)度至少是1.標(biāo)準(zhǔn)答案：C深度為h的二叉樹(shù)，第h層至少有（）個(gè)結(jié)點(diǎn)。 （2分）A.0 B.1 C.8 D.16.標(biāo)準(zhǔn)答案：B假設(shè)n>0,在程序段{0（（1）^（1）B.:]2.標(biāo)準(zhǔn)答案：C下面敘述錯(cuò)誤的是（）。 （2分）在集合{1,2,3,4,5中元素1是2的直接前驅(qū)二叉須E序樹(shù)的中序遍歷序列一定是有序的有3個(gè)結(jié)點(diǎn)的不同形態(tài)二叉樹(shù)的數(shù)目為5哈夫曼樹(shù)中所有結(jié)點(diǎn)的孩子數(shù)目只可能為2或者為0.標(biāo)準(zhǔn)答案：ATOC\o"1-5"\h\z以下數(shù)據(jù)結(jié)構(gòu)中，（）是線性結(jié)構(gòu)。 （2分）A.廣義表 B.二叉樹(shù) C.稀疏矩陣 D.串.標(biāo)準(zhǔn)答案：D在一個(gè)長(zhǎng)度為n的川頁(yè)序表中刪除一個(gè)元素的算法的時(shí)間復(fù)雜度為0o（2分）⑴ （n）(n2)如果一個(gè)樹(shù)含有n個(gè)葉子，則該樹(shù)必有（）的結(jié)點(diǎn)。 （2分）1 B.21 C.2n21.標(biāo)準(zhǔn)答案：D在關(guān)鍵字序列（10,15,20,25,30）中，采用折半法查找25,關(guān)鍵字之間比較需要（）次。（2分）A.1 B.2 C.34.標(biāo)準(zhǔn)答案：B16某二叉樹(shù)的前序遍歷序列和和中序遍歷序列均為，該二叉樹(shù)的后序遍歷序列是（）o（2分）.標(biāo)準(zhǔn)答案：Bm個(gè)頂點(diǎn)的有向完全圖有（）個(gè)弧。（2分）（1）/21（1）.標(biāo)準(zhǔn)答案：D下列各項(xiàng)鍵值（）序列不是堆的。 （2分）A.{94,68,16C.{94,23,5.標(biāo)準(zhǔn)答案:23, 16, 5 B.{94,23, 68, 5,68, 16, 5 D.{94,16, 68, 23,D69.設(shè)單鏈表中指針p指向結(jié)點(diǎn)A,q指向新元素結(jié)點(diǎn)，若要A之后插>一個(gè)新元素，則所需修改指針的操作為（）o（2分）>,??,>?,>>,?.標(biāo)準(zhǔn)答案：B70.在關(guān)鍵字序列70.在關(guān)鍵字序列(149,138,165,197,176,113,低位優(yōu)先須E序（）基數(shù)須E序，第一趟之后所得結(jié)果為（）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)答案:B127）中采用最□ （2分）71.下列術(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)答案