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

1、 PAGE 5 PAGE 5第1頁共5頁。標(biāo)準(zhǔn)答案:C（75 題150 分）專升本數(shù)據(jù)結(jié)構(gòu)10。 m 個(gè)結(jié)點(diǎn)的二叉樹，其對應(yīng)的二叉鏈表共有（）個(gè)非空鏈域。 （2 分）A。mB.m+1C.2mD.m1.標(biāo)準(zhǔn)答案：B1. 數(shù)據(jù)的基本單位是（）. （2 分）A。數(shù)據(jù)元素B.記錄C.數(shù)據(jù)對象D.數(shù)據(jù)項(xiàng)。標(biāo)準(zhǔn)答案:A2。 （）是數(shù)據(jù)的不可分割的最小單位。 （2 分）A.數(shù)據(jù)對象。數(shù)據(jù)元素C.數(shù)據(jù)類型D。數(shù)據(jù)項(xiàng).標(biāo)準(zhǔn)答案：D3. 算法的空間復(fù)雜度是對算法（）的度量。 （2 分)A。時(shí)間效率B.空間效率C。可讀性D.健壯性.標(biāo)準(zhǔn)答案：B4。 （)是限制了數(shù)據(jù)元素的內(nèi)部結(jié)構(gòu)僅為一個(gè)字符的線性表。 （2 分）A

2、。棧B.隊(duì)列C。串D。數(shù)組。標(biāo)準(zhǔn)答案：B串的長度是指串中所含（）（2分）不同字符。不同字母C。相同字符D.所有字符.標(biāo)準(zhǔn)答案：D采用帶頭結(jié)點(diǎn)雙向鏈表存儲(chǔ)的線性表，在刪除一個(gè)元素時(shí)，需要修改指針(2分）。2C.3D。4。標(biāo)準(zhǔn)答案：B線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（）的存儲(chǔ)結(jié)構(gòu). (2分)順序存取。隨機(jī)存取C。索引存取D.Hash存取。標(biāo)準(zhǔn)答案：Ba1。m采用順序存儲(chǔ)，a1am1024 1150，每個(gè)2m是（). （2分）A。64。32C。16D。8。標(biāo)準(zhǔn)答案:A9。 深度為 h 的二叉樹，第 h 層最多有（）個(gè)結(jié)點(diǎn)。 （2 分）A。hB.2h1C.2h1D。2h下面敘述錯(cuò)誤的是（)(2分）A.順序表

3、是借助物理單元相鄰表示數(shù)據(jù)元素之間的邏輯關(guān)系B。對于空隊(duì)列進(jìn)行出隊(duì)操作過程中發(fā)生下溢現(xiàn)象C.有向圖的鄰接矩陣一定是對稱的D。具有相同的葉子個(gè)數(shù)和具有相同的葉子權(quán)值的赫夫曼樹不是唯一的.標(biāo)準(zhǔn)答案：C以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)的術(shù)語是（）。 (2 分) A。循環(huán)隊(duì)列。雙向鏈表C。哈希表D.數(shù)。標(biāo)準(zhǔn)答案：D13。 在一個(gè)長度為 n 的鏈?zhǔn)綏Ｖ谐鰲?shí)現(xiàn)算法的時(shí)間復(fù)雜度為（）。 （2 分）A.O(1)B.O（log n） C。O（n)。標(biāo)準(zhǔn)答案：Ak2的二叉樹中，必有(）（2分）A.kB.k1C。2kD。k+1。標(biāo)準(zhǔn)答案：D在關(guān)鍵字序列(10，20，30,40,50)20，關(guān)鍵字之間比較需要（）次。 (2

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

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

6、分） 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,D24。 在下列排序方法中,（）的空間復(fù)雜度為 O（n)。其中，n 為參加排序的元素個(gè)數(shù)。 （2 分）A.選擇排序B.快速排序C。歸并排序D.冒泡排序。標(biāo)準(zhǔn)答案：B，C十字鏈表適合于（）（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.有窮性。確定性C

7、.可行性D。正確性。標(biāo)準(zhǔn)答案：D28. 算法的時(shí)間復(fù)雜度是對算法（）（2 分）A.時(shí)間效率B.空間效率C?？勺x性健壯性.標(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)答案:D31ni 要移動(dòng)（）個(gè)元素. （2 分）A。i+1B.iC.n-iD.ni+1.標(biāo)準(zhǔn)答案：C32. 若已知一個(gè)棧的入棧序列是1、2、3、4，

8、其出棧序列不可能為。(2分)A.1、4、3、2B.3、4、1、2C.4、3、2、1D。2、3、4、1。標(biāo)準(zhǔn)答案:B33a1.。256采用順序存儲(chǔ)，a 102 字節(jié),a21的地址是（)（2 分)A。10。30C。50D。70.標(biāo)準(zhǔn)答案:C34。深度為h 的完全二叉樹至少有（）個(gè)葉子結(jié)點(diǎn)。(2 分A.h-1)+1。2(h-2)+1C。2h1D.2h-2。標(biāo)準(zhǔn)答案:D35。 若二叉樹對應(yīng)的二叉鏈表共有 m 個(gè)非空鏈域，則該二叉樹有（）個(gè)結(jié)點(diǎn)的二叉樹。 （2 分）A。mB。m-1C。m+1D.2m。標(biāo)準(zhǔn)答案：B下面敘述錯(cuò)誤的是（）. （2分）A.單鏈表是借助指針表示數(shù)據(jù)元素之間的邏輯關(guān)系B。在順序棧的

9、入棧操作過程中可能發(fā)生上溢現(xiàn)象C。具有相同的葉子個(gè)數(shù)和具有相同的葉子權(quán)值的赫夫曼樹是唯一的D.無向圖的鄰接矩陣一定是對稱的.標(biāo)準(zhǔn)答案：C以下（）（2分)A。棧B.哈希表C。線索樹D.雙向鏈表.標(biāo)準(zhǔn)答案：A38。 在一個(gè)長度為 n 的鏈?zhǔn)疥?duì)列中入隊(duì)實(shí)現(xiàn)算法的時(shí)間復(fù)雜度為（）。 （2 分）A。O（1）B.O(log C。O(n）D。.標(biāo)準(zhǔn)答案：A39。 隊(duì)列的出隊(duì)操作是指（)操作. （2 分）A。隊(duì)尾刪除B.隊(duì)頭刪除C.隊(duì)尾插入D.隊(duì)頭插入.標(biāo)準(zhǔn)答案：B在關(guān)鍵字序列（10,15，20,25，30）中采用折半法查找 25，依次與（)（2分)A.30，25。20，25C.20，30，25D。25。標(biāo)準(zhǔn)

10、答案：B16 abcd bcad的后序遍歷序列是（）(2分)A.cbdaB.dcbaC。abcd。dcba。標(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 為頭指針，則判斷表空的條件為(）。（2 分）A.head= NULLB.head！=NULLC.headnext=NULLD.head-next ！=NULL.標(biāo)準(zhǔn)答案：C45。 在關(guān)鍵

11、字序列（35，10，15，20，25)中采用最低位優(yōu)先排序(LSD）基數(shù)排序，第一趟之后所得結(jié)果為()。 (2 分）A.10，20，15,25,35B.10,20，35,15，25 C.20,10，35，25，15.標(biāo)準(zhǔn)答案:B下列邏輯結(jié)構(gòu)中，（）為線性結(jié)構(gòu)。(2 分A。棧B.隊(duì)列C.串D.二叉樹。標(biāo)準(zhǔn)答案:A，B,C深度為3 的二叉樹可能的結(jié)點(diǎn)個(gè)數(shù)是（）. （2 分A。1B.2C。3D.4。標(biāo)準(zhǔn)答案：A,B48。 下列各項(xiàng)鍵值（)序列是大頂堆的. （2 分)A。23,68，94，16，5B.94，68，23，16,5C。94，23，68,16，5D.94，16，68，23，5。標(biāo)準(zhǔn)答案：B,

12、C49。下列()是限制了插入和刪除操作的特殊線性表。(2 分A。棧。隊(duì)列C.串D。數(shù)組。標(biāo)準(zhǔn)答案:A,B50。 對一棵二叉排序樹，用()方法進(jìn)行遍歷,不一定得到各結(jié)點(diǎn)鍵值的有序序列。（2 分)A.先根遍歷。中根遍歷C.后根遍歷D。層次遍歷。標(biāo)準(zhǔn)答案：A，C，D51。 數(shù)據(jù)的最小單位是（）。 (2 分)A.數(shù)據(jù)元素B.記錄C.數(shù)據(jù)對象D。數(shù)據(jù)項(xiàng)。標(biāo)準(zhǔn)答案：D算法是對某一類問題求解步驟的有限序列。其中,（）5 一. (2分)A.有窮性B.正確性C?？勺x性D.健壯性。標(biāo)準(zhǔn)答案：A(）（2分)A。順序表B.鏈表C.線性表D。十字鏈表.標(biāo)準(zhǔn)答案：C54。 ()是限制了插入和刪除操作在一端進(jìn)行的線性表。

13、（2 分)A。棧。隊(duì)列C.串D.數(shù)組.標(biāo)準(zhǔn)答案：A55. （）是限制了插入和刪除操作分別在兩端進(jìn)行的線性表。（2 分A。棧。隊(duì)列C。串D.數(shù)組。標(biāo)準(zhǔn)答案：B56。 用鏈表表示線性表的優(yōu)點(diǎn)是(）. （2 分）A。便于插入和刪除B。便于隨機(jī)存取C?；ㄙM(fèi)的存儲(chǔ)空間較順序存儲(chǔ)少D.數(shù)據(jù)元素的物理順序與邏輯順序相同。標(biāo)準(zhǔn)答案：A571、2、3、4，其出棧序列不可能為（）分）A.1、4、3、2。2、3、4、1C。4、3、2、1D.3、4、1、2。標(biāo)準(zhǔn)答案：D58。 串下列關(guān)于串的敘述中，正確的是（)。 （2 分）A。2 個(gè)串的長度相等，則 2 個(gè)串相等B?？沾辽侔粋€(gè)空格C.替換操作可以實(shí)現(xiàn)字符的刪除D

14、。一個(gè)串的長度至少是 1.標(biāo)準(zhǔn)答案:C59。 深度為 h 的二叉樹，第 h 層至少有(）個(gè)結(jié)點(diǎn)。 （2 分）A.0B.1C.8D.16.標(biāo)準(zhǔn)答案：B60。假設(shè)n0,在程序段y=0；while（y+1)*（y+1）A.nB。C。n2.標(biāo)準(zhǔn)答案：C61. 下面敘述錯(cuò)誤的是（）. （2 分）A。在集合1，2，3,4,5 1 2 。二叉排序樹的中序遍歷序列一定是有序的C.有 3 個(gè)結(jié)點(diǎn)的不同形態(tài)二叉樹的數(shù)目為 5D.哈夫曼樹中所有結(jié)點(diǎn)的孩子數(shù)目只可能為 2 或者為 0。標(biāo)準(zhǔn)答案：A62。 以下數(shù)據(jù)結(jié)構(gòu)中,(）是線性結(jié)構(gòu)。 （2 分）廣義表。二叉樹C.稀疏矩陣D。串.標(biāo)準(zhǔn)答案：D63. 在一個(gè)長度為n

15、的順序表中刪除一個(gè)元素的算法的時(shí)間復(fù)雜度為（）. (2 分A。O(1)B。O(log n）C。O（n）D。O(n2）.標(biāo)準(zhǔn)答案：C64。 如果一個(gè) huffman 樹含有 n 個(gè)葉子，則該樹必有（）的結(jié)點(diǎn)。 （2 分）A。n+1。2n+1C.2nD。2n-1。標(biāo)準(zhǔn)答案：D65。 在關(guān)鍵字序列(10,15，20,25，30）中，采用折半法查找 25，關(guān)鍵字之間比較需要（）次. （2 分）。2C.3D.4。標(biāo)準(zhǔn)答案:B16 abcd,序列是（）（2分)A.abcdB.dcbaC。acbdD.dbca。標(biāo)準(zhǔn)答案：Bm個(gè)頂點(diǎn)的有向完全圖有（)個(gè)弧. （2分)A。m（m1）/2B。m+1C。mD。m(m

16、-1).標(biāo)準(zhǔn)答案：D68。下列各項(xiàng)鍵值（）序列不是堆的. (2分） A.94，68，23，16,5B。C。94，23，68,16，5D。94，16,68，23,5.標(biāo)準(zhǔn)答案：D69p A,q 指向新元素結(jié)點(diǎn),A 素，則所需修改指針的操作為（)（2 分）A。pnext=q，q-next=p-next。qnext=pnext，p-C。p-next=qnext，qnext=p D。pnext=p，q-next=pnext。標(biāo)準(zhǔn)答案：B70. 在關(guān)鍵字序列(149,138，165，197，176，113，127)中采用最低位優(yōu)先排序(LSD)基數(shù)排序，第一趟之后所得結(jié)果為（）。 （2 分） A 。 149，138,165，197,176,113,127 B.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)答案：B71. 下列術(shù)語表示的數(shù)據(jù)中，（）是同義語。(2 分A.結(jié)點(diǎn)。數(shù)據(jù)元素C.頂點(diǎn)D。數(shù)據(jù).標(biāo)準(zhǔn)答案：A,B,C72。對于采用鏈?zhǔn)浇Y(jié)構(gòu)的隊(duì)列,(）運(yùn)算的實(shí)現(xiàn)算法的時(shí)間復(fù)雜度為O（1）. (2 分A.入隊(duì)。出隊(duì)C。求隊(duì)長