算法大視界知到智慧樹章節(jié)測(cè)試課后答案2024年秋中國(guó)海洋大學(xué)

算法大視界知到智慧樹章節(jié)測(cè)試課后答案2024年秋中國(guó)海洋大學(xué)緒論單元測(cè)試

本課程是面向非計(jì)算機(jī)專業(yè)學(xué)生開放，要求學(xué)生了解計(jì)算機(jī)解決現(xiàn)實(shí)問題的方式和策略，學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的基本知識(shí)，著重培養(yǎng)學(xué)生的計(jì)算思維能力

A:錯(cuò)B:對(duì)

答案:對(duì)

第一章單元測(cè)試

以下那個(gè)數(shù)據(jù)結(jié)構(gòu)是適用于"數(shù)據(jù)必須以相反的順序存儲(chǔ)然后檢索"?

A:ListB:QueueC:

LiinkListD:Stack

答案:Stack判斷下列說法是否正確：數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。

A:錯(cuò)B:對(duì)

答案:對(duì)關(guān)系數(shù)據(jù)模型的基本數(shù)據(jù)結(jié)構(gòu)是：

A:樹B:圖C:索引D:關(guān)系

答案:圖數(shù)據(jù)挖掘算法主要有聚類算法、關(guān)聯(lián)算法、決策樹算法和回歸分析等，各種算法用于解決不同的實(shí)際問題，某分行擬通過對(duì)縣域機(jī)構(gòu)數(shù)量與存款市場(chǎng)競(jìng)爭(zhēng)力的相關(guān)性分析，進(jìn)而建立兩者之間的函數(shù)表達(dá)式，用新思維拓展縣域市場(chǎng)，提升縣域存款的市場(chǎng)競(jìng)爭(zhēng)力。則可以采用的是（）

A:聚類分析B:關(guān)聯(lián)算法C:回歸分析D:決策樹算法

答案:回歸分析算法一般用類C語言之類的偽碼來描述，如果用C語言等高級(jí)語言來描述，則算法實(shí)際上就是程序了。

A:錯(cuò)B:對(duì)

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

A:隊(duì)列B:二叉樹C:線性表D:棧

答案:二叉樹樹最適合用來表示

A:元素之間具有分支層次關(guān)系的數(shù)據(jù)B:有序數(shù)據(jù)元素C:元素之間無聯(lián)系的數(shù)據(jù)D:無序數(shù)據(jù)元素

答案:元素之間具有分支層次關(guān)系的數(shù)據(jù)在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ)

A:數(shù)據(jù)元素之間的關(guān)系B:數(shù)據(jù)的存儲(chǔ)方法C:數(shù)據(jù)的處理方法D:數(shù)據(jù)元素的類型

答案:數(shù)據(jù)元素之間的關(guān)系計(jì)算機(jī)算法指的是：

A:解決問題的有限運(yùn)算序列B:排序方法C:計(jì)算方法D:調(diào)度方法

答案:解決問題的有限運(yùn)算序列研究數(shù)據(jù)結(jié)構(gòu)就是研究

A:數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)B:數(shù)據(jù)的邏輯結(jié)構(gòu)C:數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其基本操作D:數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

答案:數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其基本操作

第二章單元測(cè)試

下面關(guān)于線性表的敘述錯(cuò)誤的是（

）。

A:線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間B:線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間C:線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)D:線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)

答案:線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)鏈表不具備的特點(diǎn)是

A:可隨機(jī)訪問任一結(jié)點(diǎn)B:插入刪除不需要移動(dòng)元素C:所需空間與其長(zhǎng)度成正比D:不必事先估計(jì)存儲(chǔ)空間

答案:可隨機(jī)訪問任一結(jié)點(diǎn)線性表是具有n個(gè)（）的有限序列

A:數(shù)據(jù)項(xiàng)B:數(shù)據(jù)元素C:字符D:表元素

答案:數(shù)據(jù)元素在一個(gè)長(zhǎng)度為n的順序表中，在第i個(gè)元素之前插入一個(gè)新元素時(shí)，需向后移動(dòng)（

）個(gè)元素。

A:n-i+1B:iC:n-i-1D:n-i

答案:n-i+1對(duì)線性表進(jìn)行二分查找時(shí),要求線性表必須

A:以鏈接方式存儲(chǔ),且結(jié)點(diǎn)按關(guān)鍵字有序排序B:以順序方式存儲(chǔ),且結(jié)點(diǎn)按關(guān)鍵字有序排序C:以鏈接方式存儲(chǔ)D:以順序方式存儲(chǔ)

答案:以順序方式存儲(chǔ),且結(jié)點(diǎn)按關(guān)鍵字有序排序下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？

A:可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示B:存儲(chǔ)密度大C:插入運(yùn)算方便D:刪除運(yùn)算方便

答案:存儲(chǔ)密度大若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（

）存儲(chǔ)方式最節(jié)省時(shí)間。

A:帶頭結(jié)點(diǎn)的雙循環(huán)鏈表B:單循環(huán)鏈表C:雙鏈表D:順序表

答案:順序表靜態(tài)鏈表中指針表示的是（

）

A:下一元素地址B:數(shù)組下標(biāo)C:左、右孩子地址D:內(nèi)存地址

答案:下一元素地址指針的全部作用就是（

）

A:指向某常量B:存儲(chǔ)某數(shù)據(jù)C:指向某變量D:指向某結(jié)點(diǎn)

答案:指向某結(jié)點(diǎn)單鏈表的一個(gè)存儲(chǔ)結(jié)點(diǎn)包含（）

A:數(shù)據(jù)域和鏈域B:指針域或鏈域C:指針域和鏈域D:數(shù)據(jù)域或指針域

答案:數(shù)據(jù)域和鏈域

第三章單元測(cè)試

設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個(gè)記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為

A:3，2，5，6，8

B:2，3，6，5，8C:2，3，5，8，6D:3，2，5，8，6

答案:3，2，5，6，8

排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法稱為

A:起泡排序B:插入排序C:希爾排序D:選擇排序

答案:插入排序快速排序方法在（

）情況下最不利于發(fā)揮其長(zhǎng)處

A:要排序的數(shù)據(jù)中含有多個(gè)相同值B:要排序的數(shù)據(jù)量太大C:要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù)D:要排序的數(shù)據(jù)已基本有序

答案:要排序的數(shù)據(jù)已基本有序?qū)個(gè)不同的數(shù)據(jù)進(jìn)行冒泡排序，實(shí)現(xiàn)從小到大排序，在下列哪種情況下比較的次數(shù)最多（）

A:數(shù)據(jù)基本有序B:從大到小排列好的C:數(shù)據(jù)無序D:從小到大排列好的

答案:從大到小排列好的在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是

A:直接插入排序B:直接選擇排序C:希爾排序D:冒泡排序

答案:直接選擇排序關(guān)于排序算法，下列說法錯(cuò)誤的是:

A:歸并排序的最壞時(shí)間復(fù)雜度是O(n*log(n))B:堆排序的平均時(shí)間復(fù)雜度是O(n*log(n))C:快速排序的最壞時(shí)間復(fù)雜度是O(n*log(n))D:插入排序的最壞時(shí)間復(fù)雜度是O(n2)

答案:快速排序的最壞時(shí)間復(fù)雜度是O(n*log(n))下列排序算法中存儲(chǔ)消耗最大的是？（）

A:歸并排序B:插入排序C:快速排序D:堆排序

答案:歸并排序以下哪種排序算法在最壞情況下的時(shí)間復(fù)雜度最??？

A:歸并排序B:冒泡排序C:插入排序D:選擇排序

答案:歸并排序待排序元素規(guī)模較小時(shí)，宜選取哪種排序算法效率最高（）

A:堆排序B:冒泡排序C:歸并排序D:希爾排序

答案:冒泡排序若用冒泡排序?qū)﹃P(guān)鍵字序列{10,8,6,4,2},進(jìn)行從小到大的排序，所需進(jìn)行的關(guān)鍵字比較總次數(shù)是

A:10B:20C:25D:15

答案:10

第四章單元測(cè)試

一個(gè)棧的進(jìn)棧序列是a，b，c，d，e，則棧的不可能的輸出序列是

A:edcbaB:dceabC:abcdeD:decba

答案:dceab設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否配對(duì)出現(xiàn)的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳

A:線性表的順序存儲(chǔ)結(jié)構(gòu)B:線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C:隊(duì)列D:棧

答案:棧和順序棧相比，鏈棧有一個(gè)比較明顯的優(yōu)勢(shì)是

A:通常不會(huì)出現(xiàn)棧滿的情況B:刪除操作更容易實(shí)現(xiàn)C:通常不會(huì)出現(xiàn)?？盏那闆rD:插入操作更容易實(shí)現(xiàn)

答案:通常不會(huì)出現(xiàn)棧滿的情況棧的插入和刪除操作在

A:指定位置B:棧底C:棧頂D:任意位置

答案:棧頂若以S和X分別表示進(jìn)棧和退棧操作，則對(duì)初始狀態(tài)為空的?？梢赃M(jìn)行的棧操作系列合法的是

A:SXSSXXXXB:SXXSXSSXC:SXSXXSSX

D:SSSXXSXX

答案:SSSXXSXX對(duì)于棧操作數(shù)據(jù)的原則是（

）

A:不分順序B:后進(jìn)先出C:后進(jìn)后出D:先進(jìn)先出

答案:后進(jìn)先出若一個(gè)棧的輸入序列為1,2,3,…,n，輸出序列的第一個(gè)元素是i，則第j個(gè)輸出元素是

A:i-jB:j-i+1C:不確定的D:i-j-1

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

A:23145B:15432C:23415D:54132

答案:54132輸入序列為ABC，可以變?yōu)镃BA時(shí)，經(jīng)過的棧操作為

A:push,push,push,pop,pop,popB:push,pop,push,pop,push,popC:push,pop,push,push,pop,popD:push,push,pop,pop,push,pop

答案:push,push,push,pop,pop,pop棧在（

）中應(yīng)用

A:其他都是B:子程序調(diào)用C:遞歸調(diào)用D:表達(dá)式求值

答案:其他都是；子程序調(diào)用；遞歸調(diào)用；表達(dá)式求值

第五章單元測(cè)試

將遞歸算法轉(zhuǎn)換成對(duì)應(yīng)的非遞歸算法時(shí)，通常需要使用（

）來保存中間結(jié)果

A:鏈表B:樹C:棧D:隊(duì)列

答案:棧一個(gè)對(duì)象如果（

）由它自身來定義（或描述），則稱其為遞歸。

A:完全B:全部的C:部分的D:不能

答案:部分的下面哪種情況不能用遞歸來實(shí)現(xiàn)

A:漢諾塔B:直接插入排序

C:階乘函數(shù)D:八皇后

答案:直接插入排序

一個(gè)遞歸函數(shù)能夠正確運(yùn)行的必要條件是

A:有分支結(jié)構(gòu)B:有輸入C:有循環(huán)結(jié)構(gòu)D:有遞歸出口

答案:有遞歸出口在遞歸函數(shù)的遞歸調(diào)用過程中問題的規(guī)模是

A:逐漸變大的B:有時(shí)大有時(shí)小C:逐漸變小的D:不變的

答案:逐漸變小的一個(gè)遞歸算法必須包括

A:終止條件和迭代部分B:迭代部分C:遞歸部分D:終止條件和遞歸部分

答案:終止條件和遞歸部分在將一個(gè)函數(shù)的實(shí)現(xiàn)從遞歸實(shí)現(xiàn)改為非遞歸實(shí)現(xiàn)時(shí)，一般需要用到下列哪個(gè)數(shù)據(jù)結(jié)構(gòu)？

A:雙向鏈表B:二叉樹C:隊(duì)列D:棧

答案:棧若實(shí)現(xiàn)一個(gè)未加入任何優(yōu)化的遞歸版本的斐波那契序列實(shí)現(xiàn)，該遞歸版本實(shí)現(xiàn)的時(shí)間復(fù)雜度和空間復(fù)雜度是怎樣的?(不考慮整數(shù)溢出和機(jī)器的內(nèi)存限制）

A:時(shí)間復(fù)雜度O(2^n),空間復(fù)雜度O(n)B:時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(2^n)C:時(shí)間復(fù)雜度O(n),空間復(fù)雜度O(n)D:時(shí)間復(fù)雜度O(2^n),空間復(fù)雜度O(2^n)

答案:時(shí)間復(fù)雜度O(2^n),空間復(fù)雜度O(n)某遞歸算法的遞歸關(guān)系式為T(n)=2*T(n/2)+O(n)，那么它所對(duì)應(yīng)的時(shí)間復(fù)雜度為

A:O(n^2)B:O(n)C:O(n*logn)D:O(logn)

答案:O(n*logn)采用遞歸方式對(duì)順序表進(jìn)行快速排序。下列關(guān)于遞歸次數(shù)的敘述中，正確的是（）

A:遞歸次數(shù)與每次劃分后得到的分區(qū)的處理順序無關(guān)B:遞歸次數(shù)與初始數(shù)據(jù)的排列次序無關(guān)C:每次劃分后，先處理較長(zhǎng)的分區(qū)可以減少遞歸次數(shù)D:每次劃分后，先處理較短的分區(qū)可以減少遞歸次數(shù)

答案:遞歸次數(shù)與每次劃分后得到的分區(qū)的處理順序無關(guān)

第六章單元測(cè)試

隊(duì)列是一種（

）的線性表

A:只能插入B:只能刪除C:先進(jìn)后出D:先進(jìn)先出

答案:先進(jìn)先出對(duì)于循環(huán)隊(duì)列

A:無法判斷隊(duì)列是否為空B:無法判斷隊(duì)列是否為滿C:其他說法都不對(duì)D:隊(duì)列不可能滿

答案:其他說法都不對(duì)一個(gè)隊(duì)列的入隊(duì)序列是1，2，3，4，則隊(duì)列的輸出序列是

A:4，3，2，1B:1，2，3，4C:1，4，3，2D:3，2，4，1

答案:1，2，3，4允許對(duì)隊(duì)列進(jìn)行的操作有

A:在隊(duì)頭元素之前插入元素B:取出最近進(jìn)隊(duì)的元素C:對(duì)隊(duì)列中的元素排序D:刪除隊(duì)頭元素

答案:刪除隊(duì)頭元素隊(duì)列的“先進(jìn)先出”特性是指

A:每次從隊(duì)列中刪除的總是最早插入的元素B:當(dāng)同時(shí)進(jìn)行插入、刪除操作時(shí)，總是插入操作優(yōu)先C:最早插入隊(duì)列中的元素總是最后被刪除D:每當(dāng)有刪除操作時(shí)，總是要先做一次插入操作

答案:每次從隊(duì)列中刪除的總是最早插入的元素隊(duì)列的結(jié)構(gòu)屬于

A:鏈?zhǔn)酱鎯?chǔ)的非線性結(jié)構(gòu)B:限制存取點(diǎn)的線性結(jié)構(gòu)C:順序存儲(chǔ)的線性結(jié)構(gòu)D:限制存取點(diǎn)的非線性結(jié)構(gòu)

答案:限制存取點(diǎn)的線性結(jié)構(gòu)用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)

A:僅修改尾指針B:僅修改頭指針C:頭、尾指針都要修改D:頭、尾指針可能都要修改

答案:頭、尾指針可能都要修改循環(huán)隊(duì)列的隊(duì)滿條件為

A:(sq.rear+1)%mazsize==(sq.front+1)%maxsize;B:sq.rear==sq.frontC:sq.(rear+1)%maxsize==sq.frontD:(sq.rear+1%maxsize==sq.front+1

答案:sq.(rear+1)%maxsize==sq.front若以1234作為雙端隊(duì)列的輸入序列，則既不能由輸入受限的雙端隊(duì)列得到，也不能由輸出受限的雙端隊(duì)列得到的輸出序列是

A:4132B:4231C:4213D:1234

答案:4231循環(huán)隊(duì)列A[0..m-1]存放其元素值，用front和rear分別表示隊(duì)頭和隊(duì)尾，則當(dāng)前隊(duì)列中的元素?cái)?shù)是

A:rear-front+1B:rear-frontC:

(rear-front+m)%mD:rear-front-1

答案:

(rear-front+m)%m

第七章單元測(cè)試

在二叉樹的第i層上至多有(

)結(jié)點(diǎn)

A:

B:C:D:

答案:設(shè)某哈夫曼樹中有199個(gè)結(jié)點(diǎn)，則該哈夫曼樹中有（

）個(gè)葉子結(jié)點(diǎn)

A:102B:

99C:100D:101

答案:100下述二叉樹中，（

）滿足性質(zhì)：從任一結(jié)點(diǎn)出發(fā)到根的路徑上所經(jīng)過的結(jié)點(diǎn)序列按其關(guān)鍵字有序

A:哈夫曼樹B:AVL樹C:二叉排序樹D:堆

答案:哈夫曼樹下列陳述中正確的是(

)

A:二叉樹是度為2的有序樹B:二叉樹中最多只有兩棵子樹，并且有左右之分C:二叉樹中必有度為2的結(jié)點(diǎn)D:二叉樹中結(jié)點(diǎn)只有一個(gè)孩子時(shí)無左右之分

答案:二叉樹中最多只有兩棵子樹，并且有左右之分深度為5的二叉樹至多有

個(gè)結(jié)點(diǎn)

A:31B:16C:10D:32

答案:31如果初始時(shí)B-樹為空樹，通過逐個(gè)向3階B-樹中插入新結(jié)點(diǎn)(8,28,40,80,50,90,85,150,120,200)，以下說法正確的是

A:刪除90時(shí),需要將150放入其雙親結(jié)點(diǎn)中B:樹中插入80時(shí),結(jié)點(diǎn)需要分裂C:樹中插入85時(shí),結(jié)點(diǎn)需要分裂D:刪除200時(shí),需要將150放入其雙親結(jié)點(diǎn)中

答案:刪除90時(shí),需要將150放入其雙親結(jié)點(diǎn)中；樹中插入85時(shí),結(jié)點(diǎn)需要分裂在下列表述中,（）是錯(cuò)誤的

A:含有一個(gè)或多個(gè)空格字符的串稱為空串B:對(duì)n(n>0)個(gè)頂點(diǎn)的網(wǎng),求出權(quán)最小的n-1條邊便可構(gòu)成其最小生成樹C:選擇排序算法是不穩(wěn)定的D:平衡二叉樹的左右子樹的結(jié)點(diǎn)數(shù)之差的絕對(duì)值不超過1

答案:含有一個(gè)或多個(gè)空格字符的串稱為空串；對(duì)n(n>0)個(gè)頂點(diǎn)的網(wǎng),求出權(quán)最小的n-1條邊便可構(gòu)成其最小生成樹；平衡二叉樹的左右子樹的結(jié)點(diǎn)數(shù)之差的絕對(duì)值不超過1以下不是平衡二叉查找樹的是

A:AVL樹B:

B+/B-樹C:紅黑樹D:哈夫曼樹

答案:

B+/B-樹；哈夫曼樹數(shù)據(jù)庫(kù)索引經(jīng)常使用B+樹。以下關(guān)于B+樹的描述，錯(cuò)誤的是哪一項(xiàng)？

A:與二叉樹相比，B+樹更利于降低高度B:B+樹空間復(fù)雜度低于B樹C:B+樹的插入、刪除可以保證其平衡性D:B+樹能夠支持順序查找

答案:B+樹空間復(fù)雜度低于B樹二叉樹是每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu),假設(shè)一棵二叉樹的高度為m，所有結(jié)點(diǎn)的度為0，或?yàn)?，則關(guān)于此樹擁有的最少節(jié)點(diǎn)個(gè)數(shù)，下列選項(xiàng)正確的是

A:2m-2B:2m+1C:m+1D:

2m-1

答案:

2m-1

第八章單元測(cè)試

二叉排序樹中左子樹上所有結(jié)點(diǎn)的值均（

）根結(jié)點(diǎn)的值。

A:

!=B:=C:>D:

<

答案:

<下列描述中不符合二叉排序樹特點(diǎn)的是

A:關(guān)鍵字插入的順序影響二叉排序樹的形態(tài)B:左子樹中所有結(jié)點(diǎn)的關(guān)鍵字小于根結(jié)點(diǎn)的關(guān)鍵字C:根結(jié)點(diǎn)的關(guān)鍵字大于左、右子樹中所有結(jié)點(diǎn)的關(guān)鍵字D:右子樹中所有結(jié)點(diǎn)的關(guān)鍵字大于根節(jié)點(diǎn)的關(guān)鍵字

答案:根結(jié)點(diǎn)的關(guān)鍵字大于左、右子樹中所有結(jié)點(diǎn)的關(guān)鍵字一棵二叉排序樹是由關(guān)鍵字集合{18，43，27，44，36，39}構(gòu)建的，其中序遍歷序列是

A:44，43，39，36，27，18B:18，43，27，44，36，39C:18，27，36，39，43，44D:樹形未定，無法確定

答案:18，27，36，39，43，44二叉查找樹的查找效率與二叉樹的()有關(guān)

A:結(jié)點(diǎn)的多少B:結(jié)點(diǎn)的位置C:樹型D:高度

答案:樹型二叉查找樹在（

）時(shí)其查找效率最低

A:結(jié)點(diǎn)太復(fù)雜B:呈單枝樹C:完全二叉樹D:結(jié)點(diǎn)太多

答案:呈單枝樹一棵二叉樹的前序遍歷序列為ABCDEFG，它的中序遍歷序列可能是

A:ADCFEGB:CABDEFGC:ABCDEFGD:DACEFBG

答案:ABCDEFG已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,

它的前序遍歷是

A:decabB:acbedC:deabcD:cedba

答案:cedba將{32,2,15,65,28,10}依次插入初始為空的二叉排序樹。則該樹的前序遍歷結(jié)果是

A:32,2,10,15,28,6B:10,28,15,2,65,32C:32,2,15,10,28,65D:2,10,15,28,32,65

答案:32,2,15,10,28,65下列敘述正確的是

A:二叉樹中除葉結(jié)點(diǎn)外,任一結(jié)點(diǎn)X，其左子樹根結(jié)點(diǎn)的值小于該結(jié)點(diǎn)（X）的值；其右子樹根結(jié)點(diǎn)的值≥該結(jié)點(diǎn)（X）的值，則此二叉樹一定是二叉排序樹B:雖然給出關(guān)鍵字序列的順序不一樣，但依次生成的二叉排序樹卻是一樣的C:在任意一棵非空二叉排序樹，刪除某結(jié)點(diǎn)后又將其插入，則所得二叉排序樹與刪除前原二叉排序樹相同D:在二叉排序樹中插入一個(gè)新結(jié)點(diǎn)，總是插入到最下層，作為新的葉子結(jié)點(diǎn)

答案:在二叉排序樹中插入一個(gè)新結(jié)點(diǎn)，總是插入到最下層，作為新的葉子結(jié)點(diǎn)二叉樹的先序遍歷和中序遍歷如下：先序遍歷：EFHIGJK；中序遍歷:HFIEJKG。該二叉樹根的右子樹的根是

A:EB:G

C:FD:H

答案:G

下面關(guān)于m階B-樹說法正確的是(

)①每個(gè)結(jié)點(diǎn)至少有兩棵非空子樹②樹中每個(gè)結(jié)點(diǎn)至多有m-1個(gè)關(guān)鍵字③所有葉子在同一層上④當(dāng)插入一個(gè)數(shù)據(jù)項(xiàng)引起B(yǎng)-樹結(jié)點(diǎn)分裂后,樹長(zhǎng)高一層

A:①②③B:③C:②③④D:②③

答案:②③

第九章單元測(cè)試

普里姆算法是用來解決

A:最短路徑B:關(guān)鍵路徑C:最小生成樹D:拓?fù)浣Y(jié)構(gòu)

答案:最小生成樹設(shè)某有向圖中有n個(gè)頂點(diǎn)，則該有向圖對(duì)應(yīng)的鄰接表中有（

）個(gè)表頭結(jié)點(diǎn)

A:n-1B:

2n-1C:

nD:

n+1

答案:

n設(shè)某無向圖中有n個(gè)頂點(diǎn)e條邊，則該無向圖中所有頂點(diǎn)的入度之和為

A:2eB:nC:2nD:e

答案:2e具有6個(gè)頂點(diǎn)的無向圖至少應(yīng)該有（

）條邊才能確保是一個(gè)連通圖

A:6B:8C:5D:7

答案:5對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無向圖,若采用鄰接矩陣表示,則該矩陣的大小為

A:(n-1)×(n-1)B:n×nC:(n-1)×nD:n×(n+1)

答案:n×n在對(duì)圖進(jìn)行深度優(yōu)先搜索時(shí)，一般需要用到下列哪個(gè)數(shù)據(jù)結(jié)構(gòu)？

A:單向鏈表B:二叉樹C:隊(duì)列D:棧

答案:棧下列關(guān)于最小生成樹的說法中，正確的是(

)。(1)最小生成樹的代價(jià)唯一(2)權(quán)值最小的邊一定會(huì)出現(xiàn)在所有的最小生成樹中(3)用Prim算法從不同頂點(diǎn)開始得到的最小生成樹的形態(tài)一定相同(4)Prim算法和Kruskal算法得到的最小生成樹的形態(tài)總不相同

A:僅(1)B:僅(2)C:僅(2)

(4)D:僅(1)

(3)

答案:僅(1)求圖的最小生成樹有兩種算法，Kruskal算法適合于求稀疏圖的最小生成樹

A:錯(cuò)B:對(duì)

答案:對(duì)6個(gè)頂點(diǎn)的連通圖的最小生成樹，其邊數(shù)為（）

A:7B:6C:4D:5

答案:5設(shè)完全無向圖中有n個(gè)頂點(diǎn)，則該完全無向圖中有多少條邊

A:n(n-1)B:(n-1)/2C:n(n-1)/2D:n(n+1)/2

答案:n(n-1)/2

第十章單元測(cè)試

在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的

A:1/2B:4倍C:2倍D:1倍

答案:1倍下列哪一種圖的鄰接矩陣是對(duì)稱矩陣？

A:無向圖B:有向圖C:AOE網(wǎng)D:AOV網(wǎng)

答案:無向圖設(shè)某強(qiáng)連通圖中有n個(gè)頂點(diǎn)，則該強(qiáng)連通圖中至少有（

）條邊

A:nB:n+1C:n(n+1)D:n(n-1)

答案:n求解最短路徑的Floyd算法的時(shí)間復(fù)雜度為