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

專升本《數(shù)據(jù)結(jié)構(gòu)》一、（共75題洪150分）.數(shù)據(jù)的基本單位是O。（2分）A.數(shù)據(jù)元素B.記錄 C.數(shù)據(jù)對(duì)象D.數(shù)據(jù)項(xiàng).標(biāo)準(zhǔn)答案：A.O是數(shù)據(jù)的不可分割的最小單位。（2分）A.數(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.可讀性 D.健壯性.標(biāo)準(zhǔn)答案：B.O是限制了數(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)雙向鏈表存儲(chǔ)的線性表，在刪除一個(gè)元素時(shí)，需要修改指針（）次。（2分）A.lB.2 C.3 D.4.標(biāo)準(zhǔn)答案：B7,線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（）的存儲(chǔ)結(jié)構(gòu)。（2分）A.順序存取 B.隨機(jī)存取 C.索引存取D.Hash存取.標(biāo)準(zhǔn)答案：B.數(shù)組采用順序存儲(chǔ)，a⑴和a[m]地址分別為1024和1150,每個(gè)元素占2字節(jié)，則m是O。 （2分）A.64 B.32 C.16 D.8.標(biāo)準(zhǔn)答案：A.深度為h的二叉樹(shù)，第h層最多有（）個(gè)結(jié)點(diǎn)。（2分）A.h B.2h-1C.2h-iD.2h.標(biāo)準(zhǔn)答案：C.m個(gè)結(jié)點(diǎn)的二叉樹(shù)，其對(duì)應(yīng)的二叉鏈表共有（）個(gè)非空鏈域。（2分）A.mB.m+1C.2mD.m-1.標(biāo)準(zhǔn)答案：B.下面敘述錯(cuò)誤的是O。 （2分）A.順序表是借助物理單元相鄰表示數(shù)據(jù)元素之間的邏輯關(guān)系對(duì)于空隊(duì)列進(jìn)行出隊(duì)操作過(guò)程中發(fā)生下溢現(xiàn)象C.有向圖的鄰接矩陣一定是對(duì)稱的D.具有相同的葉子個(gè)數(shù)和具有相同的葉子權(quán)值的赫夫曼樹(shù)不是唯一的.標(biāo)準(zhǔn)答案：C.以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)的術(shù)語(yǔ)是O。（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ù)雜度為O。(2分)A.O(l) B.O(logn)C.O(n) D.O(n2).標(biāo)準(zhǔn)答案：A.在具有k個(gè)度數(shù)為2的二叉樹(shù)中，必有()個(gè)葉子結(jié)點(diǎn)。(2分)A.kB.k-1C.2kD.k+1.標(biāo)準(zhǔn)答案：D.在關(guān)鍵字序列(10,20,30,40,50)中，采用折半法查找20,關(guān)鍵字之間比較需要()次。(2分)A.lB.2 C.3 D.4.標(biāo)準(zhǔn)答案：C.16某二叉樹(shù)的后序遍歷序列和和中序遍歷序列均為abed,該二叉樹(shù)的前序遍歷序列是()o(2分)A.abcdB.dcbaC.acbdD.dbca.標(biāo)準(zhǔn)答案：B.n個(gè)頂點(diǎn)的無(wú)向連通圖的生成樹(shù)，至少有()個(gè)邊。(2分)A.n(n-l)B.n(n-l)/2C.2nD.n-1.標(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[O..n-1]存放循環(huán)隊(duì)列的元素，其頭指針front指向隊(duì)頭元素、尾指針rear指向隊(duì)尾元素一個(gè)，則在少用一個(gè)元素空間的前提下，隊(duì)列空的判定條件為()o(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é)果為()o(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,C,D.設(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.下列各項(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)答案：C,D.在下列排序方法中，（）的空間復(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.二叉樹(shù).標(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)答案：C.（）不是算法具有的5個(gè)特性之一。（2分）A.有窮性 B.確定性 C.可行性 D.正確性.標(biāo)準(zhǔn)答案：D.算法的時(shí)間復(fù)雜度是對(duì)算法（）的度量。（2分）A.時(shí)間效率B.空間效率C.可讀性 D.健壯性.標(biāo)準(zhǔn)答案：A.線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求結(jié)點(diǎn)的存儲(chǔ)單元地址（）o（2分）A.必須是連續(xù)的 B.部分地址必須是連續(xù)的C.必須是不連續(xù)的D.連續(xù)或不連續(xù)都可以.標(biāo)準(zhǔn)答案：D.二維數(shù)組通常采用順序存儲(chǔ)，其優(yōu)點(diǎn)是（）o（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,其出棧序列不可能為 o(2分)A.1、4、3、2B.3、4、1、2C.4、3、2、1D.2、3、4、1.標(biāo)準(zhǔn)答案：B.數(shù)組a[1..256]采用順序存儲(chǔ)，a的首地址為10,每個(gè)元素占2字節(jié)，則a[21]的地址是O。 (2分)A.10 B.30 C.50 D.70.標(biāo)準(zhǔn)答案：C.深度為h的完全二叉樹(shù)至少有()個(gè)葉子結(jié)點(diǎn)。(2分)A.2(h-1)+1 B.2(h-2)+lC.2h-1 D.2h-2.標(biāo)準(zhǔn)答案：D.若二叉樹(shù)對(duì)應(yīng)的二叉鏈表共有m個(gè)非空鏈域，則該二叉樹(shù)有()個(gè)結(jié)點(diǎn)的二叉樹(shù)。(2分)A.mB.m-1 C.m+1D.2m.標(biāo)準(zhǔn)答案：B.下面敘述錯(cuò)誤的是()o(2分)A.單鏈表是借助指針表示數(shù)據(jù)元素之間的邏輯關(guān)系在順序棧的入棧操作過(guò)程中可能發(fā)生上溢現(xiàn)象C.具有相同的葉子個(gè)數(shù)和具有相同的葉子權(quán)值的赫夫曼樹(shù)是唯一的D.無(wú)向圖的鄰接矩陣一定是對(duì)稱的.標(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ù)雜度為()o分)A.O(l) B.O(logn)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,依次與(進(jìn)行了比較。(2分)A.30,25 B.20,25 C.20,30,25D.25.標(biāo)準(zhǔn)答案：B41.16某二叉樹(shù)的前序遍歷序列和和中序遍歷序列分別為abed和bead,該二叉樹(shù)的后序遍歷序列是OO（2分）A.cbdaB.dcbaC.abcdD.dcba.標(biāo)準(zhǔn)答案：A.所占用的存儲(chǔ)空間大小僅與圖的頂點(diǎn)個(gè)數(shù)相關(guān)的存儲(chǔ)結(jié)構(gòu)是O。（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)，head為頭指針，則判斷表空的條件為（）o（2分）A.head==NULL B.head!=NULLC.head->next==NULLD.head->next!=NULL.標(biāo)準(zhǔn)答案：C）關(guān)鍵字.在關(guān)鍵字序列（35,10,15,20,25）中采用最低位優(yōu)先排序（LSD）基數(shù)排序，第一趟之后所得結(jié)果為（）o（2分））關(guān)鍵字A.10,20,15,25,35 B.10,20,35,15,25C.20,10,35,25,15 D.20,10,35,15,25.標(biāo)準(zhǔn)答案：B.下列邏輯結(jié)構(gòu)中，（）為線性結(jié)構(gòu)。（2分）A.棧 A.棧 B.隊(duì)列 C.串.標(biāo)準(zhǔn)答案：A,B,CD.二叉樹(shù).深度為3的二叉樹(shù)可能的結(jié)點(diǎn)個(gè)數(shù)是（）o（2分）A.lB.2 C.3 D.4.標(biāo)準(zhǔn)答案：A,B.下列各項(xiàng)鍵值（）序列是大頂堆的。（2分）A.{23,68,94,16,5 B.{94,68,23,16,5C.{94,23,68,16,5 D.{94,16,68,23,5.標(biāo)準(zhǔn)答案：B,C.下列（）是限制了插入和刪除操作的特殊線性表。（2分）A.棧 B.隊(duì)列C.串 D.數(shù)組.標(biāo)準(zhǔn)答案：A,B.對(duì)一棵二叉排序樹(shù)，用（）方法進(jìn)行遍歷，不一定得到各結(jié)點(diǎn)鍵值的有序序列。（2分）A.先根遍歷 B.中根遍歷 C.后根遍歷 D.層次遍歷.標(biāo)準(zhǔn)答案：A,C,D.數(shù)據(jù)的最小單位是O。 （2分）A.數(shù)據(jù)元素 B.記錄 C.數(shù)據(jù)對(duì)象 D.數(shù)據(jù)項(xiàng).標(biāo)準(zhǔn)答案：D.算法是對(duì)某一類問(wèn)題求解步驟的有限序列。其中，（）是算法具有的5個(gè)特性之一。（2分）A.有窮性 B.正確性C.可讀性D.健壯性.標(biāo)準(zhǔn)答案：A.（）是數(shù)據(jù)的邏輯結(jié)構(gòu)。（2分）A.順序表 B.鏈表 C.線性表 D.十字鏈表.標(biāo)準(zhǔn)答案：C.O是限制了插入和刪除操作在一端進(jìn)行的線性表。（2分）A.棧 B.隊(duì)列 C.串 D.數(shù)組.標(biāo)準(zhǔn)答案：A.O是限制了插入和刪除操作分別在兩端進(jìn)行的線性表。（2分）A.棧 B.隊(duì)列 C.串 D.數(shù)組.標(biāo)準(zhǔn)答案：B.用鏈表表示線性表的優(yōu)點(diǎn)是O。（2分）A.便于插入和刪除B.便于隨機(jī)存取C.花費(fèi)的存儲(chǔ)空間較順序存儲(chǔ)少D.數(shù)據(jù)元素的物理順序與邏輯順序相同.標(biāo)準(zhǔn)答案：A.若已知一個(gè)棧的入棧序列是1、2、3、4,其出棧序列不可能為（）o（2分）A.1、4、3、2B.2、3、4、1C.4、3、2、1D.3、4、1、2.標(biāo)準(zhǔn)答案：D.串下列關(guān)于串的敘述中，正確的是（）o（2分）A.2個(gè)串的長(zhǎng)度相等，則2個(gè)串相等B.空串至少包一個(gè)空格C.替換操作可以實(shí)現(xiàn)字符的刪除D.一個(gè)串的長(zhǎng)度至少是1.標(biāo)準(zhǔn)答案：C.深度為h的二叉樹(shù)，第h層至少有()個(gè)結(jié)點(diǎn)。(2分)A.OB.lC.8 D.16.標(biāo)準(zhǔn)答案：B.假設(shè)在程序段｛y=O;while((y+l)*(y+l)A.n B.口C.FI2.標(biāo)準(zhǔn)答案：C.下面敘述錯(cuò)誤的是()o(2分)A.在集合｛1,2,3,4,5中元素1是2的直接前驅(qū)二叉排序樹(shù)的中序遍歷序列一定是有序的C.有3個(gè)結(jié)點(diǎn)的不同形態(tài)二叉樹(shù)的數(shù)目為5D.哈夫曼樹(shù)中所有結(jié)點(diǎn)的孩子數(shù)目只可能為2或者為0.標(biāo)準(zhǔn)答案：A.以下數(shù)據(jù)結(jié)構(gòu)中，()是線性結(jié)構(gòu)。(2分)A.廣義表 B.二叉樹(shù) C.稀疏矩陣D.串.標(biāo)準(zhǔn)答案：D.在一個(gè)長(zhǎng)度為n的順序表中刪除一個(gè)元素的算法的時(shí)間復(fù)雜度為()o(2分)A.O(l)C.O(n)A.O(l)C.O(n)D.O(n2).標(biāo)準(zhǔn)答案：C.如果一個(gè)huffman樹(shù)含有n個(gè)葉子，則該樹(shù)必有()的結(jié)點(diǎn)。(2分)A.n+1 B.2n+1C.2nD.2n-1.標(biāo)準(zhǔn)答案：D.在關(guān)鍵字序列(10,15,20,25,30)中，采用折半法查找25,關(guān)鍵字之間比較需要()次。(2分)A.lB.2 C.3 D.4.標(biāo)準(zhǔn)答案：B.16某二叉樹(shù)的前序遍歷序列和和中序遍歷序列均為abed,該二叉樹(shù)的后序遍歷序列是OO(2分)A.abcdB.dcbaC.acbdD.dbca.標(biāo)準(zhǔn)答案：B.m個(gè)頂點(diǎn)的有向完全圖有()個(gè)弧。(2分)A.m(m-l)/2 B.m+1C.mD.m(m-l).標(biāo)準(zhǔn)答案：D.下列各項(xiàng)鍵值()序列不是堆的。(2分)A.{94,68,23,16,5 B.{94,23,68,5,16C.{94,23,68,16,5 D.{94,16,68,23,5.標(biāo)準(zhǔn)答案：D.設(shè)單鏈表中指針p指向結(jié)點(diǎn)A,q指向新元素結(jié)點(diǎn)，若要A之后插入一個(gè)新元素，則所需修改指針的操作為()o(2分)A.p->next=q,q->next=p->nextB.q->next=p->next,p->next=qC.p->next=q->next,q->next=pD.p->next=p,q->next=p->next.標(biāo)準(zhǔn)答案：BTOC\o"1-5"\h\z.在關(guān)鍵字序列（149,138,165,197,176,113,127）中采用最低位優(yōu)先排序（LSD）基數(shù)排序，第一趟之后所得結(jié)果為O。 （2分）A.149, 138, 165, 197, 176, 113, 127128, 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ù)語(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,C.對(duì)于采用鏈?zhǔn)浇Y(jié)構(gòu)