數(shù)據(jù)結(jié)構(gòu)智慧樹知到答案章節(jié)測試2023年內(nèi)蒙古民族大學(xué)

緒論單元測試數(shù)據(jù)在計算機(jī)存儲器內(nèi)表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱這為()。

A:順序存儲結(jié)構(gòu)

B:鏈?zhǔn)酱鎯Y(jié)構(gòu)

C:存儲結(jié)構(gòu)

D:邏輯結(jié)構(gòu)

答案:A算法的時間復(fù)雜度取決于（）。

A:問題的可解性

B:待處理數(shù)據(jù)的初態(tài)

C:問題的復(fù)雜度

D:問題的規(guī)模

答案:BD從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為()。

A:非線性結(jié)構(gòu)

B:物理結(jié)構(gòu)

C:線性結(jié)構(gòu)

D:靜態(tài)結(jié)構(gòu)

答案:AC除了考慮存儲數(shù)據(jù)結(jié)構(gòu)本身所占用的空間外,實現(xiàn)算法所用輔助空間的多少稱為算法的()。

A:空間效率

B:軟件效率

C:硬件效率

D:時間效率

答案:A鏈?zhǔn)酱鎯Φ拇鎯Y(jié)構(gòu)所占存儲空間()。

A:分兩部分,一部分存放結(jié)點值,另一部分存放表示結(jié)點間關(guān)系的指針

B:只有一部分,存儲表示結(jié)點間關(guān)系的指針

C:分兩部分,一部分存放結(jié)點值,另一部分存放指向下一結(jié)點的地址

D:只有一部分,存放結(jié)點值

答案:AC設(shè)語句X++的時間是單位時間,則語句。for(I=1;I＜=n;I++)x++;的時間復(fù)雜度為()

A:O(n3)

B:O(n2)

C:O(n)

D:O(1)

答案:C對一個算法的評價，不包括如下（）方面的內(nèi)容。

A:時空復(fù)雜度

B:健壯性和可讀性

C:計算性

D:并行性

答案:CD以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)()

A:二叉樹

B:隊列

C:線性表

D:棧

答案:A邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)（）

A:對

B:錯

答案:A基于某種邏輯結(jié)構(gòu)之上的基本操作，其實現(xiàn)是唯一的。（）

A:對

B:錯

答案:B第一章測試非空的循環(huán)單鏈表head的尾結(jié)點（由p指向）滿足（）。

A:p→next==head

B:p==NULL

C:p==head

D:p→next==NULL

答案:A帶頭結(jié)點head的單鏈表為空的判定條件是（）。

A:head-＞next==head

B:head-＞next==NULL

C:head!==NULL

D:head==NULL

答案:B在長度為n的順序表的第i個位置上插入一個元素（1≤i≤n+1），元素的移動次數(shù)為（）。

A:i–1

B:i

C:n–i+1

D:n–i

答案:C在一個單鏈表中，若刪除P所指結(jié)點的后續(xù)結(jié)點，則執(zhí)行（）。

A:P-＞next=P-＞next-＞next;

B:q=P-＞next;P-＞next=P-＞next-＞next;

C:P=P-＞next-＞next

D:P-＞next=P-＞next

答案:B在循環(huán)雙鏈表的p所指結(jié)點后插入s所指結(jié)點的操作是（）。

A:s-＞prior=p;s-＞next=p-＞next;p-＞next-＞prior=s;p-＞next=s;

B:p-＞next=s;p-＞next-＞prior=s;s-＞prior=p;s-＞next=p-＞next;

C:p-＞next=s;s-＞prior=p;p-＞next-＞prior=s;s-＞next=p-＞next;

D:s-＞prior=p;s-＞next=p-＞next;p-＞next=s;p-＞next-＞prior=s;

答案:A線性表的邏輯順序和存儲順序總是一致的。（）

A:對

B:錯

答案:B線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈接存儲結(jié)構(gòu)。（）

A:對

B:錯

答案:B用數(shù)組r存儲靜態(tài)鏈表，結(jié)點的next域指向后繼，工作指針j指向鏈中某結(jié)點，則j后移的操作語句為j=j+1。（）

A:對

B:錯

答案:B下列敘述正確的是（）。

A:在鏈表進(jìn)行刪除操作時，在給出指向鏈表中某個合適位置的指針后，刪除操作所需的時間僅為O（1）。

B:當(dāng)線性表中元素個數(shù)變化較大或者未知時，最好使用鏈表實現(xiàn)。

C:空表是長度等于0的線性表。

D:若線性表需頻繁進(jìn)行插入和刪除操作，則宜采用順序表作為存儲結(jié)構(gòu)。

E:順序表插入操作的時間復(fù)雜度為O（n）。

答案:ABCE靜態(tài)鏈表的指針表示的是（）。

A:下一元素在數(shù)組中的位置。

B:左鏈或右鏈指向的元素地址。

C:下一元素在數(shù)組的下標(biāo)。

D:下一元素的地址。

E:內(nèi)存儲器的地址。

答案:AC第二章測試一個隊列的入隊列順序是1，2，3，4，則隊列的輸出順序是（）

A:1432

B:4321

C:1234

D:不唯一

答案:C一個棧的輸入序列為12345，則下列序列中不可能是棧的輸出序列的是()

A:51432

B:23415

C:54132

D:23145

答案:AC設(shè)一個棧，元素abcdef，依次進(jìn)棧，不可能得到出棧序列是（）

A:fedcba

B:defabc

C:abcdef

D:fabced

答案:BD在棧中，出棧的時間復(fù)雜度為()

A:O（log2n）

B:O(n)

C:O(n2)

D:O（1）

答案:D循環(huán)隊列用數(shù)組A[maxsize]表示，下面哪個選項表示該循環(huán)隊列隊滿()

A:rear-front==maxsize-1

B:rear==maxsize-1

C:front==(rear+1)%maxsize

D:rear-front==maxsize

答案:C棧和隊列屬于非線性結(jié)構(gòu)（）

A:對

B:錯

答案:B讀隊頭元素和出隊操作是一樣的（）

A:對

B:錯

答案:B循環(huán)隊列的判空操作只需判斷front==rear是否成立（）

A:對

B:錯

答案:A循環(huán)隊列的基本操作的實現(xiàn)，算法的時間復(fù)雜度都是O(1)（）

A:對

B:錯

答案:A取棧頂元素不需要修改指針（）

A:錯

B:對

答案:B第三章測試100個結(jié)點的完全二叉樹采用順序存儲，從1開始按層次編號，則編號最小的葉子結(jié)點的編號應(yīng)該是（）。

A:49

B:50

C:51

D:100

答案:C以下屬于前綴編碼的是（）。

A:{00,01,10,11,101}

B:{0,1,01,010,110}

C:{0,1101,1110,1100,1111}

D:{01,00,10,001,110,101}

答案:C如果結(jié)點A有2個兄弟B是A的雙親，則結(jié)點B的度為（）。

A:2

B:4

C:1

D:3

答案:D在一棵滿二叉樹中，某結(jié)點的深度為4、高度為4，則可推知該滿二叉樹的高度為（）。

A:6

B:7

C:4

D:5

答案:B用n個權(quán)值構(gòu)造出來的哈夫曼樹共有（）個結(jié)點。

A:2n

B:2n-1

C:n+1

D:2n+1

答案:B一顆有n個結(jié)點的樹的所有結(jié)點的度數(shù)之和為（）。

A:n+1

B:n

C:n-1

D:2n

答案:C如果T2是由樹T轉(zhuǎn)換成的二叉樹，那么T中結(jié)點的先根遍歷序列對應(yīng)T2中結(jié)點的（）遍歷序列。

A:中序

B:后序

C:前序

D:層次序

答案:B設(shè)n和m為一棵二叉樹上的兩個結(jié)點，在該二叉樹的前序遍歷序列中，n在m前的條件是（）。

A:n是m的祖先

B:n是m的子孫

C:n在m右方

D:n在m左方

答案:AD對于一棵非空二叉樹，它的根結(jié)點作為第一層，則它的第i層上最多能有2i—1個結(jié)點。（）

A:對

B:錯

答案:B一棵哈夫曼樹中不存在度為1的結(jié)點。（）

A:錯

B:對

答案:B第四章測試最小生成樹指的是（）。

A:由連通網(wǎng)所得到的頂點數(shù)相對較少的生成樹

B:連通網(wǎng)的極小連通子圖

C:由連通網(wǎng)所得到的邊數(shù)最少的生成樹

D:連通網(wǎng)中所有生成樹中權(quán)值之和為最小的生成樹

答案:D有向完全圖中，頂點的入度、出度與頂點個數(shù)之間的關(guān)系正確說法是（）。

A:入度+出度=頂點個數(shù)

B:入度=出度=頂點個數(shù)-1

C:入度、出度與頂點個數(shù)之間沒有關(guān)系

D:入度+出度=2*頂點個數(shù)

答案:B含n個頂點的無向完全圖有（）條邊。

A:不確定

B:n(n-1)/2

C:n(n-1)

D:n-1

答案:B圖的存儲結(jié)構(gòu)主要有兩種，鄰接矩陣和（）。

A:雙親表示法

B:孩子兄弟表示法

C:孩子鏈表示法

D:鄰接表

答案:D圖的遍歷操作分兩種，分別為深度優(yōu)先遍歷和（）。。

A:中序遍歷

B:后序遍歷

C:廣度優(yōu)先遍歷

D:前序遍歷

答案:C無向圖的鄰接矩陣是對稱的。（）

A:對

B:錯

答案:A圖中頂點集和邊集均為空，則稱空圖。（）

A:錯

B:對

答案:A有向圖的鄰接矩陣一定不對稱。（）

A:錯

B:對

答案:A無向圖的頂點的度指依附于該頂點的邊數(shù)。（）

A:錯

B:對

答案:B有向圖的頂點入度指以該頂點為弧頭的弧的個數(shù)。（）

A:錯

B:對

答案:B第五章測試對二叉排序樹進(jìn)行（）遍歷能夠得到結(jié)點的有序序列。

A:層序

B:中序

C:前序

D:后序

答案:B在順序表(30,61,82,89,90,93,96,98)中，用折半法查找關(guān)鍵碼值60，所需的關(guān)鍵碼比較次數(shù)為（）

A:2

B:4

C:5

D:3

答案:D對有序表{-1,0,1,3,4,6,8,10,12}進(jìn)行折半查找，則查找12需要比較的次數(shù)為（）。

A:5

B:3

C:4

D:6

答案:C散列技術(shù)中的沖突指的是（）。

A:不同鍵值的元素對應(yīng)于相同的存儲地址

B:兩個元素具有相同的序號

C:數(shù)據(jù)元素過多

D:兩個元素的鍵值不同，而其他屬性相同

答案:A采用折半查找法查找長度為n的有序表時，每個元素的平均查找長度為（）。

A:n

B:nlogn

C:logn

D:n

答案:C一個有序表為（1，3，9，12，32，41，62，75，77，82，95，100），當(dāng)二分查找給定值82時，（）次比較后查找成功。

A:2

B:1

C:8

D:4

答案:D靜態(tài)查找與動態(tài)查找的根本區(qū)別在于（）。

A:它們的邏輯結(jié)構(gòu)不一樣

B:所包含的數(shù)據(jù)元素的類型不一樣

C:施加在其上的操作不同

D:存儲實現(xiàn)不一樣

答案:C散列文件的優(yōu)點是（）

A:存取速度快

B:插入.刪除操作方便

C:文件可隨機(jī)存放，記錄無需排序

D:能夠進(jìn)行順序存取

E:無需索引區(qū)，節(jié)省存儲空間

答案:ABCE關(guān)鍵字序列的順序不一樣，依次生成的二叉排序樹是一樣的。（）

A:對

B:錯

答案:B二叉樹中除葉子結(jié)點外，對于任結(jié)點x，其左子樹根結(jié)點的值小于該結(jié)點（x）其右子樹結(jié)點的值不小于該結(jié)點（x）的值，則此二叉樹一定是二叉排序樹。（）

A:對

B:錯

答案:B第六章測試希爾排序的增量序列必須是（）

A:遞減的

B:非遞減的

C:遞增的

D:隨機(jī)的

答案:A下列排序算法中，占用輔助存儲空間最多的是（）

A:希爾排序

B:堆排序

C:起泡排序

D:歸并排序

答案:D一組記錄的關(guān)鍵碼為（46，79，56，38，40，84），則利用快速排序的方法，以第一個紀(jì)律為軸值得到的一次劃分結(jié)果為（）

A:（38，40，46，56，79，84）

B:（40，38，46，84，56，79）

C:（40，38，46，56，79，84）

D:（40，38，46，79，56，84）

答案:C下面四個序列中，哪一個是堆（）

A:75，45，65，30，15，25，20，10

B:75，45，65，10，25，30，20，15

C:75，65，45，10，30，25，20，15

D:75，65，30，15，25，45，20，10

答案:A下面排序算法中，