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

1、。標(biāo)準(zhǔn)答案:c專升本數(shù)據(jù)結(jié)構(gòu)一、（共 75題,共 150分）數(shù)據(jù)的基本單位是（）. （2分）A。數(shù)據(jù)元素B.記錄C.數(shù)據(jù)對(duì)象 D.數(shù)據(jù)項(xiàng)。標(biāo)準(zhǔn)答案:A（）是數(shù)據(jù)的不可分割的最小單位。 （2 分）數(shù)據(jù)對(duì)象 B。數(shù)據(jù)元素C.數(shù)據(jù)類型D。數(shù)據(jù)項(xiàng).標(biāo)準(zhǔn)答案：D算法的空間復(fù)雜度是對(duì)算法（）的度量。 （2 分）A。時(shí)間效率B.空間效率C?？勺x性D.健壯性.標(biāo)準(zhǔn)答案： B（）是限制了數(shù)據(jù)元素的內(nèi)部結(jié)構(gòu)僅為一個(gè)字符的線性表。 （2 分）A。棧B.隊(duì)列C。串D。數(shù)組。標(biāo)準(zhǔn)答案： B串的長(zhǎng)度是指串中所含（）的個(gè)數(shù)。 （2分）A.不同字符 B。不同字母 C。相同字符 D.所有字符 .標(biāo)準(zhǔn)答案： D采用帶頭結(jié)點(diǎn)雙向鏈

2、表存儲(chǔ)的線性表，在刪除一個(gè)元素時(shí)，需要修改指針（） 次。 （2 分）A.1 B。 2C.3 D。 4。標(biāo)準(zhǔn)答案： B線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（）的存儲(chǔ)結(jié)構(gòu). （2 分）A.順序存取 B。隨機(jī)存取 C。索引存取 D.Hash存取 。標(biāo)準(zhǔn)答案： B數(shù)組a 1。m采用順序存儲(chǔ)，a 1和a m地址分別為1024和1150，每個(gè) 元素占2字節(jié)，則m是（）.（2分）A。 64B。 32 C。 16 D。 8。標(biāo)準(zhǔn)答案:A深度為 h 的二叉樹，第 h 層最多有（）個(gè)結(jié)點(diǎn)。 （ 2 分）A。 hB.2h1C.2h1D。 2h10。m個(gè)結(jié)點(diǎn)的二叉樹，其對(duì)應(yīng)的二叉鏈表共有（）個(gè)非空鏈域。（2分）A。 mB.m+

3、1 C.2mD.m1.標(biāo)準(zhǔn)答案： B1 1 .下面敘述錯(cuò)誤的是（ ） 。 （2分）順序表是借助物理單元相鄰表示數(shù)據(jù)元素之間的邏輯關(guān)系B。對(duì)于空隊(duì)列進(jìn)行出隊(duì)操作過(guò)程中發(fā)生下溢現(xiàn)象有向圖的鄰接矩陣一定是對(duì)稱的D。具有相同的葉子個(gè)數(shù)和具有相同的葉子權(quán)值的赫夫曼樹不是唯一的 .標(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分） A.O（1）B.O（log n）C。 O（ n）D.O（ n2）。標(biāo)準(zhǔn)答案： A在具有k個(gè)度數(shù)為2的二叉樹中，必有（）個(gè)葉子結(jié)點(diǎn)。（2分）A.

4、kB.k1C。 2k D。 k+1。標(biāo)準(zhǔn)答案： D在關(guān)鍵字序列（10， 20， 30,40,50）中，采用折半法查找20，關(guān)鍵字之間比較需要 （）次。 （2 分）A。 1B。 2C。 3D.4.標(biāo)準(zhǔn)答案： C16某二叉樹的后序遍歷序列和和中序遍歷序列均為abed，該二叉樹的前序遍歷 序列是（） . （2分）A。 abed B。 debaC。 aebd D。 dbea。標(biāo)準(zhǔn)答案:Bn個(gè)頂點(diǎn)的無(wú)向連通圖的生成樹，至少有（）個(gè)邊.（2分）A。 n（n-1）B.n（n1） /2 C.2n D.n1.標(biāo)準(zhǔn)答案:D可以采用（）這種數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)二叉樹的層次遍歷運(yùn)算。 （2分）A.隊(duì)列 B。樹C.棧D。集合

5、.標(biāo)準(zhǔn)答案:A19。假設(shè)以數(shù)組A ：0.o n1存放循環(huán)隊(duì)列的元素，其頭指針front指向隊(duì)頭元 素、尾指針rear指向隊(duì)尾元素一個(gè)，貝V在少用一個(gè)元素空間的前提下，隊(duì)列空的判 定條件為（）。 （2 分）A.rear= =frontB（front+1）%n= =rearC。 rear+1= =frontD.（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,

6、5,37）.標(biāo)準(zhǔn)答案： B二叉鏈表適合作為（）的存儲(chǔ)結(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 分)A.44, 5, 15 B。 28, 45, 62C。 6, 57, 125D.201, 31,48.標(biāo)準(zhǔn)答案： B, C,D23。下列各項(xiàng)鍵值()序列不是堆的。 (2分)A. 94,68, 23, 16, 5B.94, 23,68, 5, 16C.94,23, 16, 68, 5 D。 94, 16,68, 23,5 。標(biāo)準(zhǔn)答案： C,D 24。在下列排序方法

7、中，（）的空間復(fù)雜度為0 （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。二叉樹 .標(biāo)準(zhǔn)答案： B, C基于數(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)答案： C27。（）不是算法具有的 5個(gè)特性之一。 （2分）A.有窮性 B。確定性 C.可行性 D。正確性 。標(biāo)準(zhǔn)答案： D28。算法的時(shí)間復(fù)雜度是對(duì)算法（）的度量。 （2分）A.時(shí)間效率B.空間效率C?？勺x性D.

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

9、1、 4、3、2 B.3、4、 1、 2C.4、3、 2、 1D。2、3、4、1。標(biāo)準(zhǔn)答案:B33。數(shù)組a 1.o 256采用順序存儲(chǔ)，a的首地址為10,每個(gè)元素占2字節(jié)，則 a21的地址是（）。（2分）A。 10 B。 30C。 50 D。 70.標(biāo)準(zhǔn)答案:C34。深度為h的完全二叉樹至少有（）個(gè)葉子結(jié)點(diǎn)。（2分）A.2（h-1）+1B。 2（h-2）+1C。 2h1D.2h-2。標(biāo)準(zhǔn)答案:D35。若二叉樹對(duì)應(yīng)的二叉鏈表共有m個(gè)非空鏈域，則該二叉樹有（）個(gè)結(jié)點(diǎn)的二 叉樹。 （ 2 分）A。 mB。 m-1 C。 m+1 D.2m。標(biāo)準(zhǔn)答案： B36。下面敘述錯(cuò)誤的是（） . （2分）單鏈表是

10、借助指針表示數(shù)據(jù)元素之間的邏輯關(guān)系B。在順序棧的入棧操作過(guò)程中可能發(fā)生上溢現(xiàn)象C。具有相同的葉子個(gè)數(shù)和具有相同的葉子權(quán)值的赫夫曼樹是唯一的無(wú)向圖的鄰接矩陣一定是對(duì)稱的.標(biāo)準(zhǔn)答案：C以下（）術(shù)語(yǔ)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)（2分）A。棧 B.哈希表 C。線索樹 D.雙向鏈表 .標(biāo)準(zhǔn)答案： A在一個(gè)長(zhǎng)度為n的鏈?zhǔn)疥?duì)列中入隊(duì)實(shí)現(xiàn)算法的時(shí)間復(fù)雜度為（）。（2分）A。 O（ 1）B.O（log n）C。 O（n）D。 O（ 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

11、，依次與（）關(guān)鍵字進(jìn) 行了比較。 （2分）A.30，25B。 20，25C.20，30，25 D。 25。標(biāo)準(zhǔn)答案： B16某二叉樹的前序遍歷序列和和中序遍歷序列分別為abed和bead，該二叉樹 的后序遍歷序列是（）。 （2 分）A.ebda B.debaC。 abed D。 deba。標(biāo)準(zhǔn)答案： A42。 所占用的存儲(chǔ)空間大小僅與圖的頂點(diǎn)個(gè)數(shù)相關(guān)的存儲(chǔ)結(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)答案： C44。線性表采用帶頭結(jié)點(diǎn)單鏈表實(shí)現(xiàn)，head

12、為頭指針，則判斷表空的條件為（）。 （ 2 分）A.head= NULLB.head！=NULLC.headnext=NULLD.head-next ！=NULL.標(biāo)準(zhǔn)答案： C45。在關(guān)鍵字序列（35, 10, 15, 20, 25）中采用最低位優(yōu)先排序（LSD）基數(shù)排 序,第一趟之后所得結(jié)果為（）。 （2分）A.10, 20, 15,25,35C.20,10, 35, 25, 15.標(biāo)準(zhǔn)答案:BB.10,20, 35,15, 25D.20,10, 35, 15, 2546. 下列邏輯結(jié)構(gòu)中,（）為線性結(jié)構(gòu)。 （2分）A。棧B.隊(duì)列C.串D.二叉樹。標(biāo)準(zhǔn)答案:A, B,C47。深度為3的二叉

13、樹可能的結(jié)點(diǎn)個(gè)數(shù)是（） .（2分）A。 1B.2C。 3D.4。標(biāo)準(zhǔn)答案： A,B48。下列各項(xiàng)鍵值（）序列是大頂堆的.（2分）A23,68, 94, 16, 5B.94, 68, 23, 16,5C94, 23, 68,16, 5D. 94, 16, 68, 23, 5。標(biāo)準(zhǔn)答案： B,C49。下列（）是限制了插入和刪除操作的特殊線性表。 （2分） A。棧 B。隊(duì)列 C.串 D。數(shù)組。標(biāo)準(zhǔn)答案:A,B50。 對(duì)一棵二叉排序樹,用（）方法進(jìn)行遍歷,不一定得到各結(jié)點(diǎn)鍵值的有序序列。（ 2 分）A.先根遍歷B。中根遍歷C.后根遍歷 D。層次遍歷。標(biāo)準(zhǔn)答案： A, C, D51。 數(shù)據(jù)的最小單位是（

14、）。 （2 分）A.數(shù)據(jù)兀素B.記錄C.數(shù)據(jù)對(duì)象D。數(shù)據(jù)項(xiàng)。標(biāo)準(zhǔn)答案： D52.算法是對(duì)某一類問(wèn)題求解步驟的有限序列。其中,（）是算法具有的5個(gè)特性之一. （2分）A.有窮性 B.正確性C?？勺x性D.健壯性。標(biāo)準(zhǔn)答案： A（）是數(shù)據(jù)的邏輯結(jié)構(gòu)。 （2分）A。順序表B.鏈表C.線性表D。十字鏈表.標(biāo)準(zhǔn)答案： C54。（）是限制了插入和刪除操作在一端進(jìn)行的線性表。 （2分）Ao棧 Bo隊(duì)列C.串.標(biāo)準(zhǔn)答案：AD.數(shù)組（）是限制了插入和刪除操作分別在兩端進(jìn)行的線性表。（2分）A。棧 E。隊(duì)列 C。串D.數(shù)組。標(biāo)準(zhǔn)答案：B56。用鏈表表示線性表的優(yōu)點(diǎn)是（）.（2分）Ao便于插入和刪除Bo便于隨機(jī)存取C

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

16、 A.nCo n2.標(biāo)準(zhǔn)答案：C61.下面敘述錯(cuò)誤的是（）.（2分）Ao在集合1, 2, 3,4,5中元素1是2的直接前驅(qū)Bo二叉排序樹的中序遍歷序列一定是有序的有3個(gè)結(jié)點(diǎn)的不同形態(tài)二叉樹的數(shù)目為5哈夫曼樹中所有結(jié)點(diǎn)的孩子數(shù)目只可能為2或者為0。標(biāo)準(zhǔn)答案：A62o以下數(shù)據(jù)結(jié)構(gòu)中,（）是線性結(jié)構(gòu)。（2分）A.廣義表 Bo二叉樹C.稀疏矩陣Do串.標(biāo)準(zhǔn)答案：D63.在一個(gè)長(zhǎng)度為n的順序表中刪除一個(gè)元素的算法的時(shí)間復(fù)雜度為（）.（2分） Ao 0（1）Bo O（logn）Co 0 （n）Do 0（n2）標(biāo)準(zhǔn)答案：C64o如果一個(gè)huffman樹含有n個(gè)葉子，則該樹必有（）的結(jié)點(diǎn)。（2分）Ao n+1

17、 Bo 2n+l C.2n D。2n-lo標(biāo)準(zhǔn)答案：D在關(guān)鍵字序列（10,15, 20,25, 30）中，采用折半法查找25,關(guān)鍵字之間比較 需要（）次.（2分）A.lBo 2C.3D.4（2。標(biāo)準(zhǔn)答案:E16某二叉樹的前序遍歷序列和和中序遍歷序列均為abed,該二叉樹的后序遍歷 序列是（）。（2分）A.abcd B.dcba C。aebd D.dbcao標(biāo)準(zhǔn)答案：Bm個(gè)頂點(diǎn)的有向完全圖有（）個(gè)弧.（2分）Ao m （m一1） /2 Bo m+1 C。mD。m（m-l）.標(biāo)準(zhǔn)答案：D68o下列各項(xiàng)鍵值（）序列不是堆的.（2分）94, 68, 23, 16,5 Bo 94,23, 68,5, 1

18、6Co 94, 23, 6&16, 5 D。94, 16,68, 23,5 .標(biāo)準(zhǔn)答案：DBo 69o設(shè)單鏈表中指針p指向結(jié)點(diǎn)A,q指向新元素結(jié)點(diǎn)，若要A之后插入一個(gè)新元素，則所需修改指針的操作為（）。（2分）Ao p一next=q, q-next=p-nextBo q一next=p一next, p-） next=qCo p-next=qnext, q一next=pDo pnext=p, q-next=pnexto標(biāo)準(zhǔn)答案：B70.在關(guān)鍵字序列（149,138, 165, 197, 176, 113, 127）中采用最低位優(yōu)先排序 （LSD）基數(shù)排序，第一趟之后所得結(jié)果為（）。（2分）Ao 149, 13&165, 197,176,113,127128, 149, 165, 197, 113, 176, 127Co 128, 149, 165, 197, 113, 127, 176D.113,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)答案： A,B,C72。對(duì)于采用鏈?zhǔn)浇Y(jié)構(gòu)的隊(duì)列,（）運(yùn)算的實(shí)