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

專升本《數(shù)據(jù)結(jié)構(gòu)》模擬題試卷一.（共75題,共150分）數(shù)據(jù)的基本單位是（）。（2分）數(shù)據(jù)元素記錄數(shù)據(jù)對(duì)象數(shù)據(jù)項(xiàng)★檢查答案標(biāo)準(zhǔn)答案：A（）是數(shù)據(jù)的不可分割的最小單位。（2分）數(shù)據(jù)對(duì)象數(shù)據(jù)元素?cái)?shù)據(jù)類型數(shù)據(jù)項(xiàng)★檢查答案標(biāo)準(zhǔn)答案：D算法的空間復(fù)雜度是對(duì)算法（）的度量。（2分）時(shí)間效率空間效率可讀性健壯性★檢查答案標(biāo)準(zhǔn)答案：B（）是限制了數(shù)據(jù)元素的內(nèi)部結(jié)構(gòu)僅為一個(gè)字符的線性表。（2分）棧隊(duì)列串?dāng)?shù)組★檢查答案標(biāo)準(zhǔn)答案：B串的長(zhǎng)度是指串中所含（）的個(gè)數(shù)。（2分）不同字符不同字母相同字符所有字符★檢查答案標(biāo)準(zhǔn)答案：D采用帶頭結(jié)點(diǎn)雙向鏈表存儲(chǔ)的線性表，在刪除一個(gè)元素時(shí)，需要修改指針（）次。（2分）1234★檢查答案標(biāo)準(zhǔn)答案：B線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（）的存儲(chǔ)結(jié)構(gòu)。（2分）順序存取隨機(jī)存取索引存取Hash存取★檢查答案標(biāo)準(zhǔn)答案：B8.數(shù)組a[l..m]采用順序存儲(chǔ)，a⑴和a[m]地址分別為1024和1150,每個(gè)元素占2字節(jié)，則m是（）。（2分）TOC\o"1-5"\h\z6432168★檢查答案標(biāo)準(zhǔn)答案：A深度為h的二叉樹(shù)，第h層最多有（）個(gè)結(jié)點(diǎn)。（2分）h2h-12h-12h★檢查答案標(biāo)準(zhǔn)答案：Cm個(gè)結(jié)點(diǎn)的二叉樹(shù)，其對(duì)應(yīng)的二叉鏈表共有（）個(gè)非空鏈域。（2分）mm+12mm-1★檢查答案標(biāo)準(zhǔn)答案：B下面敘述錯(cuò)誤的是（）。（2分）順序表是借助物理單元相鄰表示數(shù)據(jù)元素之間的邏輯關(guān)系對(duì)于空隊(duì)列進(jìn)行出隊(duì)操作過(guò)程中發(fā)生下溢現(xiàn)象有向圖的鄰接矩陣一定是對(duì)稱的具有相同的葉子個(gè)數(shù)和具有相同的葉子權(quán)值的赫夫曼樹(shù)不是唯一的★檢查答案標(biāo)準(zhǔn)答案：C以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)的術(shù)語(yǔ)是（）。（2分）循環(huán)隊(duì)列雙向鏈表哈希表數(shù)組★檢查答案標(biāo)準(zhǔn)答案：D在一個(gè)長(zhǎng)度為n的鏈?zhǔn)綏Ｖ谐鰲?shí)現(xiàn)算法的時(shí)間復(fù)雜度為（）。（2分）TOC\o"1-5"\h\zO（1）O（logn）\o"CurrentDocument"O（n）O（n2）★檢查答案標(biāo)準(zhǔn)答案：A在具有k個(gè)度數(shù)為2的二叉樹(shù)中，必有（）個(gè)葉子結(jié)點(diǎn)。（2分）kk-12kk+1★檢查答案標(biāo)準(zhǔn)答案：D15.在關(guān)鍵字序列（10,20,30,40,50）中，采用折半法查找20，關(guān)鍵字之間比較需要（）次。（2分）1234★檢查答案標(biāo)準(zhǔn)答案：C16某二叉樹(shù)的后序遍歷序列和和中序遍歷序列均為abed，該二叉樹(shù)的前序遍歷序列是（）。 （2分）abeddebaaebddbea★檢查答案標(biāo)準(zhǔn)答案：Bn個(gè)頂點(diǎn)的無(wú)向連通圖的生成樹(shù)，至少有（）個(gè)邊。（2分）n（n-1）n（n-1）/2TOC\o"1-5"\h\z2nn-1★檢查答案標(biāo)準(zhǔn)答案：D可以采用（）這種數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)二叉樹(shù)的層次遍歷運(yùn)算。（2分）隊(duì)列樹(shù)棧集合★檢查答案標(biāo)準(zhǔn)答案：A假設(shè)以數(shù)組A[O..n-1]存放循環(huán)隊(duì)列的元素，其頭指針front指向隊(duì)頭元素、尾指針rear指向隊(duì)尾元素一個(gè)，則在少用一個(gè)元素空間的前提下，隊(duì)列空的判定條件為（）。（2分）rear==front（front+1）％n==rearrear+1==front（rear+1）％n==front★檢查答案標(biāo)準(zhǔn)答案：A序列（21，19，37，5，2）經(jīng)冒泡排序法由小到大排序，第一趟后所得結(jié)果為（）。 （2分）（19，21，37，5，2）（19，21，5，2，37）（19，21，5，37，2）（19，21，2，5，37）★檢查答案標(biāo)準(zhǔn)答案：B二叉鏈表適合作為（）的存儲(chǔ)結(jié)構(gòu)。 （2分）隊(duì)列二叉樹(shù)樹(shù)森林★檢查答案標(biāo)準(zhǔn)答案：B,C,D22.設(shè)哈希(Hash)函數(shù)為H(k)=k%17,其中k為關(guān)鍵字，關(guān)鍵字()是同義詞。(2分)44,5,1528,45,626,57,125201,31,48★檢查答案標(biāo)準(zhǔn)答案：B,C,D下列各項(xiàng)鍵值()序列不是堆的。(2分)A.{94，68，23，16，5B.{94，23，68，5，16C.{94，23，16，68，5D.{94，16，68，23，5★檢查答案標(biāo)準(zhǔn)答案：C,D在下列排序方法中，()的空間復(fù)雜度為O(n)。其中，n為參加排序的元素個(gè)數(shù)。(2分)選擇排序快速排序歸并排序冒泡排序★檢查答案標(biāo)準(zhǔn)答案：B,C十字鏈表適合于()選作存儲(chǔ)結(jié)構(gòu)。(2分)隊(duì)列稀疏矩陣邊或弧數(shù)較少的圖二叉樹(shù)★檢查答案標(biāo)準(zhǔn)答案：B,C基于數(shù)據(jù)的邏輯關(guān)系，數(shù)據(jù)的邏輯結(jié)構(gòu)劃分為()基本結(jié)構(gòu)。(2分)TOC\o"1-5"\h\z6類5類4類3類★檢查答案標(biāo)準(zhǔn)答案：C()不是算法具有的5個(gè)特性之一。 (2分)A.有窮性

確定性可行性正確性★檢查答案標(biāo)準(zhǔn)答案：D算法的時(shí)間復(fù)雜度是對(duì)算法（）的度量。（2分）時(shí)間效率空間效率可讀性健壯性★檢查答案標(biāo)準(zhǔn)答案：A線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求結(jié)點(diǎn)的存儲(chǔ)單元地址（）。（2分）必須是連續(xù)的部分地址必須是連續(xù)的必須是不連續(xù)的連續(xù)或不連續(xù)都可以★檢查答案標(biāo)準(zhǔn)答案：D二維數(shù)組通常采用順序存儲(chǔ)，其優(yōu)點(diǎn)是（）。（2分）便于增加存儲(chǔ)空間防止下標(biāo)溢出避免數(shù)據(jù)元素的移動(dòng)便于依據(jù)下標(biāo)進(jìn)行隨機(jī)存取★檢查答案標(biāo)準(zhǔn)答案：D需要移動(dòng)（）2分）采用順序存儲(chǔ)的線性表，若表長(zhǎng)為n在第i號(hào)元素之后插入一個(gè)元素時(shí),個(gè)元素。（2需要移動(dòng)（）2分）TOC\o"1-5"\h\zi+1in-in-i+1★檢查答案標(biāo)準(zhǔn)答案：C若已知一個(gè)棧的入棧序列是1、2、3、4，其出棧序列不可能為 1、4、3、23、4、1、24、3、2、12、3、4、1★檢查答案標(biāo)準(zhǔn)答案：B33.數(shù)組a[1..256]采用順序存儲(chǔ)，a的首地址為10,每個(gè)元素占2字節(jié)，則a[21啲地址是（）。（2分）10TOC\o"1-5"\h\z305070★檢查答案標(biāo)準(zhǔn)答案：C深度為h的完全二叉樹(shù)至少有（）個(gè)葉子結(jié)點(diǎn)。（2分）2（h-1）+12（h-2）+1TOC\o"1-5"\h\z2h-12h-2★檢查答案標(biāo)準(zhǔn)答案：D若二叉樹(shù)對(duì)應(yīng)的二叉鏈表共有m個(gè)非空鏈域，則該二叉樹(shù)有（）個(gè)結(jié)點(diǎn)的二叉樹(shù)。（2分）mm-1m+12m★檢查答案標(biāo)準(zhǔn)答案：B下面敘述錯(cuò)誤的是（）。 （2分）單鏈表是借助指針表示數(shù)據(jù)元素之間的邏輯關(guān)系在順序棧的入棧操作過(guò)程中可能發(fā)生上溢現(xiàn)象具有相同的葉子個(gè)數(shù)和具有相同的葉子權(quán)值的赫夫曼樹(shù)是唯一的無(wú)向圖的鄰接矩陣一定是對(duì)稱的★檢查答案標(biāo)準(zhǔn)答案：C以下（）術(shù)語(yǔ)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)（2分）棧哈希表線索樹(shù)雙向鏈表在一個(gè)長(zhǎng)度為n的鏈?zhǔn)疥?duì)列中入隊(duì)實(shí)現(xiàn)算法的時(shí)間復(fù)雜度為()。(2分)O(1)O(logn)O(n)O(n2)★檢查答案標(biāo)準(zhǔn)答案：A隊(duì)列的出隊(duì)操作是指()操作。(2分)隊(duì)尾刪除隊(duì)頭刪除隊(duì)尾插入隊(duì)頭插入★檢查答案標(biāo)準(zhǔn)答案：B40.在關(guān)鍵字序列(10,15,20,25,30)中采用折半法查找25，依次與()關(guān)鍵字進(jìn)行了比較。(2分)TOC\o"1-5"\h\z30,2520,2520，30，25\o"CurrentDocument"25★檢查答案標(biāo)準(zhǔn)答案：B16某二叉樹(shù)的前序遍歷序列和和中序遍歷序列分別為abed和bead，該二叉樹(shù)的后序遍歷序列是()。(2分)ebdadebaabeddeba★檢查答案標(biāo)準(zhǔn)答案：A所占用的存儲(chǔ)空間大小僅與圖的頂點(diǎn)個(gè)數(shù)相關(guān)的存儲(chǔ)結(jié)構(gòu)是()。 (2分)鄰接表逆鄰接表十字鏈表鄰接矩陣★檢查答案標(biāo)準(zhǔn)答案：D可以采用()這種數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)圖的深度優(yōu)先遍歷運(yùn)算。(2分)隊(duì)列樹(shù)棧集合★檢查答案標(biāo)準(zhǔn)答案：C線性表采用帶頭結(jié)點(diǎn)單鏈表實(shí)現(xiàn)，head為頭指針，則判斷表空的條件為（）。（2分）head==NULLhead!=NULLhead->next==NULLhead->next!=NULL★檢查答案標(biāo)準(zhǔn)答案：C45.在關(guān)鍵字序列（35,10,15,20，25）中采用最低位優(yōu)先排序（LSD）基數(shù)排序，第一趟之后所得結(jié)果為()。25，(2分)35A.10，20，15，B.10，20，35，15，25C.20，10，35，25，15D.20，10，35，15，25★檢查答案標(biāo)準(zhǔn)答案：BTOC\o"1-5"\h\z下列邏輯結(jié)構(gòu)中，（）為線性結(jié)構(gòu)。 （2分）棧隊(duì)列串二叉樹(shù)★檢查答案標(biāo)準(zhǔn)答案：A,B,C深度為3的二叉樹(shù)可能的結(jié)點(diǎn)個(gè)數(shù)是（）。 （2分）1234★檢查答案標(biāo)準(zhǔn)答案：A,B下列各項(xiàng)鍵值（）序列是大頂堆的。（2分）{23，68，94，16，5{94，68，23，16，5{94，23，68，16，5D.{94，16，68，23，5★檢查答案標(biāo)準(zhǔn)答案：B,C下列（）是限制了插入和刪除操作的特殊線性表。（2分）棧隊(duì)列串?dāng)?shù)組★檢查答案標(biāo)準(zhǔn)答案：A,B對(duì)一棵二叉排序樹(shù)，用（）方法進(jìn)行遍歷，不一定得到各結(jié)點(diǎn)鍵值的有序序列。（2分）先根遍歷中根遍歷后根遍歷層次遍歷★檢查答案標(biāo)準(zhǔn)答案：A,C,D數(shù)據(jù)的最小單位是（）。（2分）數(shù)據(jù)元素記錄數(shù)據(jù)對(duì)象數(shù)據(jù)項(xiàng)★檢查答案標(biāo)準(zhǔn)答案：D算法是對(duì)某一類問(wèn)題求解步驟的有限序列。其中，（）是算法具有的5個(gè)特性之一。（2分）有窮性正確性可讀性健壯性★檢查答案標(biāo)準(zhǔn)答案：A（）是數(shù)據(jù)的邏輯結(jié)構(gòu)。（2分）順序表鏈表線性表十字鏈表（）是限制了插入和刪除操作在一端進(jìn)行的線性表。（2分）TOC\o"1-5"\h\z棧隊(duì)列串?dāng)?shù)組★檢查答案標(biāo)準(zhǔn)答案：A（）是限制了插入和刪除操作分別在兩端進(jìn)行的線性表。（2分）棧隊(duì)列串?dāng)?shù)組★檢查答案標(biāo)準(zhǔn)答案：B用鏈表表示線性表的優(yōu)點(diǎn)是（）。（2分）便于插入和刪除便于隨機(jī)存取花費(fèi)的存儲(chǔ)空間較順序存儲(chǔ)少數(shù)據(jù)元素的物理順序與邏輯順序相同★檢查答案標(biāo)準(zhǔn)答案：A2分）若已知一個(gè)棧的入棧序列是1、2、3、42分）1、4、3、22、3、4、14、3、2、13、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分）01816★檢查答案標(biāo)準(zhǔn)答案：B60.假設(shè)n三0,在程序段｛y=O;while（（y+l）*（y+l）v=n）@y++;中，標(biāo)記@的語(yǔ)句實(shí)際執(zhí)行的次數(shù)是（）。其中，[x]表示對(duì)x取整運(yùn)算。（2分）n[]n2★檢查答案標(biāo)準(zhǔn)答案：C6l. 下面敘述錯(cuò)誤的是（）。（2分）在集合｛1，2，3，4，5中元素1是2的直接前驅(qū)二叉排序樹(shù)的中序遍歷序列一定是有序的有3個(gè)結(jié)點(diǎn)的不同形態(tài)二叉樹(shù)的數(shù)目為5哈夫曼樹(shù)中所有結(jié)點(diǎn)的孩子數(shù)目只可能為2或者為0★檢查答案標(biāo)準(zhǔn)答案：A以下數(shù)據(jù)結(jié)構(gòu)中，（）是線性結(jié)構(gòu)。（2分）廣義表二叉樹(shù)稀疏矩陣TOC\o"1-5"\h\z串★檢查答案標(biāo)準(zhǔn)答案：D在一個(gè)長(zhǎng)度為n的順序表中刪除一個(gè)元素的算法的時(shí)間復(fù)雜度為（）。（2分）O（1）O（logn）\o"CurrentDocument"O（n）O（n2）★檢查答案標(biāo)準(zhǔn)答案：C如果一個(gè)huffman樹(shù)含有n個(gè)葉子，則該樹(shù)必有（）的結(jié)點(diǎn)。（2分）n+12n+12n2n-165.在關(guān)鍵字序列（10,15,20,25,30）中，采用折半法查找25，關(guān)鍵字之間比較需要（）次。（2分）1234★檢查答案標(biāo)準(zhǔn)答案：B16某二叉樹(shù)的前序遍歷序列和和中序遍歷序列均為abed，該二叉樹(shù)的后序遍歷序列是（）。（2分）abeddebaaebddbea★檢查答案標(biāo)準(zhǔn)答案：Bm個(gè)頂點(diǎn)的有向完全圖有（）個(gè)弧。（2分）m（m-1）/2m+1mm（m-1）★檢查答案標(biāo)準(zhǔn)答案：D下列各項(xiàng)鍵值（）序列不是堆的。（2分）A.{94，68，23，16，5{94，23，68，5，16{94，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分）p->next=q，q->next=p->nextq->next=p->next，p->next=qp->next=q->next，q->next=pp->next=p，q->next=p->next70.在關(guān)鍵字序列（149，138，165，197，176，113，127）中采用最低位優(yōu)先排序（LSD）基數(shù)排序，第一趟之后所得結(jié)果為（）。（2分）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)答案：B下列術(shù)語(yǔ)表示的數(shù)據(jù)中，（）是同義語(yǔ)。（2分）結(jié)點(diǎn)數(shù)據(jù)元素頂點(diǎn)數(shù)據(jù)項(xiàng)★檢查答案標(biāo)準(zhǔn)