算法設(shè)計(jì)與分析學(xué)習(xí)通超星期末考試答案章節(jié)答案2024年

算法設(shè)計(jì)與分析學(xué)習(xí)通超星期末考試章節(jié)答案2024年設(shè)一組初始記錄關(guān)鍵字序列為(Q，H，C，Y，P，A，M，S，R，D，F(xiàn)，X)，則按字母升序的第一趟冒泡排序結(jié)束后的結(jié)果是（）。

答案:H，C，Q，P，A，M，S，R，D，F(xiàn)，X，Y

設(shè)一組初始記錄關(guān)鍵字的長(zhǎng)度為

8，則最多經(jīng)過(guò)（

）趟插入排序可以得到有序序列。

答案:7設(shè)某棵二叉樹中只有度數(shù)為0

和度數(shù)為2

的結(jié)點(diǎn)且度數(shù)為0

的結(jié)點(diǎn)數(shù)為n，則這棵二叉中共有（

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

答案:

2n-1設(shè)有n

個(gè)關(guān)鍵字具有相同的Hash

函數(shù)值，則用線性探測(cè)法把這n

個(gè)關(guān)鍵字映射到HASH表中需要做（

）次線性探測(cè)。

答案:

n(n-1)/2設(shè)一組權(quán)值集合W=(15，3，14，2，6，9，16，17)，要求根據(jù)這些權(quán)值集合構(gòu)造一棵哈夫曼樹，則這棵哈夫曼樹的帶權(quán)路徑長(zhǎng)度為（

）。

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

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

答案:<設(shè)有一個(gè)

10

階的下三角矩陣

A（包括對(duì)角線），按照從上到下、從左到右的順序存儲(chǔ)到連續(xù)的55

個(gè)存儲(chǔ)單元中，每個(gè)數(shù)組元素占1

個(gè)字節(jié)的存儲(chǔ)空間，則A[5][4]地址與A[0][0]的地址之差為（

）。

答案:19設(shè)輸入序列為1、2、3、4、5、6，則通過(guò)棧的作用后可以得到的輸出序列為（

）。

答案:

3，2，5，6，4，1設(shè)某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列（

）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。

答案:雙向循環(huán)鏈表設(shè)有一組初始記錄關(guān)鍵字序列為(34，76，45，18，26，54，92)，則由這組記錄關(guān)鍵字生成的二叉排序樹的深度為（）。

答案:4設(shè)順序線性表的長(zhǎng)度為30，分成5

塊，每塊6

個(gè)元素，如果采用分塊查找，則其平均查找長(zhǎng)度為（）。

答案:6.5設(shè)有序表中的元素為(13，18，24，35，47，50，62)，則在其中利用二分法查找值為24的元素需要經(jīng)過(guò)（）次比較。

答案:3設(shè)順序表的長(zhǎng)度為n，則順序查找的平均比較次數(shù)為（

）。

答案:(n+1)/2設(shè)完全無(wú)向圖中有n

個(gè)頂點(diǎn)，則該完全無(wú)向圖中有（

）條邊。

答案:n(n-1)/2

設(shè)在一棵度數(shù)為3

的樹中，度數(shù)為3

的結(jié)點(diǎn)數(shù)有2

個(gè)，度數(shù)為2

的結(jié)點(diǎn)數(shù)有1

個(gè)，度數(shù)為1的結(jié)點(diǎn)數(shù)有2個(gè)，那么度數(shù)為0的結(jié)點(diǎn)數(shù)有（）個(gè)。

答案:6設(shè)

F

是由

T1、T2

和

T3

三棵樹組成的森林，與

F

對(duì)應(yīng)的二叉樹為

B，T1、T2

和

T3

的結(jié)點(diǎn)數(shù)分別為

N1、N2

和N3，則二叉樹

B

的根結(jié)點(diǎn)的左子樹的結(jié)點(diǎn)數(shù)為（）。

答案:

N1-1設(shè)順序線性表中有n

個(gè)數(shù)據(jù)元素，刪除表中第i

個(gè)元素需要移動(dòng)（

）個(gè)元素。

答案:n-i隊(duì)列是一種（

）的線性表。

答案:先進(jìn)先出設(shè)無(wú)向圖G

中的邊的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點(diǎn)a

出發(fā)進(jìn)行深度優(yōu)先遍歷可以得到的一種頂點(diǎn)序列為（）。

答案:aedfcb設(shè)一棵完全二叉樹中有

65

個(gè)結(jié)點(diǎn)，則該完全二叉樹的深度為（

）。

答案:7設(shè)一個(gè)順序有序表A[1:14]中有14

個(gè)元素，則采用二分法查找元素A[4]的過(guò)程中比較元素的順序?yàn)?)。

答案:

A[7]，A[3]，A[5]，A[4]兩個(gè)字符串相等的充要條件是（

）。

答案:同時(shí)具備(A)和(B)兩個(gè)條件字符串的長(zhǎng)度是指（）。

答案:串中所含字符的個(gè)設(shè)某棵二叉樹的高度為10，該二叉樹上葉子結(jié)點(diǎn)最多有（

）。

答案:512（

）二叉排序樹可以得到一個(gè)從小到大的有序序列。

答案:中序遍歷設(shè)用鄰接矩陣A表示有向圖G

的存儲(chǔ)結(jié)構(gòu)，則有向圖G

中頂點(diǎn)i

的入度為（

）。

答案:第

i

列非

0

元素的個(gè)數(shù)之和一趟排序結(jié)束后不一定能夠選出一個(gè)元素放在其最終位置上的是（

）。

答案:希爾排序設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（

）。

答案:

任一結(jié)點(diǎn)無(wú)右孩子設(shè)一組初始記錄關(guān)鍵字序列為(45，80，55，40，42，85)，則以第一個(gè)記錄關(guān)鍵字45為基準(zhǔn)而得到一趟快速排序的結(jié)果是（

）。

答案:42，40，45，55，80，85數(shù)據(jù)的最小單位（

）。

答案:數(shù)據(jù)項(xiàng)下列四種排序中（

）的空間復(fù)雜度最大。

答案:快速排序設(shè)用鏈表作為棧的存儲(chǔ)結(jié)構(gòu)則退棧操作（

）。

答案:必須判別棧是否為空設(shè)一組初始記錄關(guān)鍵字序列為(345，253，674，924，627)，則用基數(shù)排序需要進(jìn)行（

）趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。

答案:3設(shè)某無(wú)向圖中有n

個(gè)頂點(diǎn)e

條邊，則該無(wú)向圖中所有頂點(diǎn)的入度之和為（

）。

答案:2e設(shè)有5000

個(gè)待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的10

個(gè)記錄關(guān)鍵字，則用下列（

）方法可以達(dá)到此目的。

答案:堆排序設(shè)某強(qiáng)連通圖中有

n

個(gè)頂點(diǎn)，則該強(qiáng)連通圖中至少有（

）條邊。

答案:n設(shè)無(wú)向圖G

中有n

個(gè)頂點(diǎn)e

條邊，則其對(duì)應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個(gè)數(shù)分別為（

）。

答案:n，2e設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20，15，14，18，21，36，40，10)，則以20

為

基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為()。

答案:10，15，14，18，20，36，40，21

設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個(gè)記錄關(guān)鍵字5

為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為（

）。

答案:3，2，5，6，8設(shè)某有向圖中有

n

個(gè)頂點(diǎn)，該有向圖對(duì)應(yīng)的鄰接表中有（

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

答案:n設(shè)某棵二叉樹中有

2000

個(gè)結(jié)點(diǎn)，則該二叉樹的最小高度（

）。

答案:11設(shè)某棵二叉樹的中序遍歷序列為

ABCD，前序遍歷序列為

CABD，則后序遍歷該二叉樹得到序列為（）。

答案:BADC設(shè)哈夫曼樹中的葉子結(jié)點(diǎn)總數(shù)為m，若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該哈夫曼樹中總共有（）個(gè)空指針域。

答案:2m下面關(guān)于線性表的敘述錯(cuò)誤的是（）。

答案:線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？()

答案:二叉樹用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)(

)。

答案:頭、尾指針可能都要修改棧和隊(duì)列的共同特點(diǎn)是()。

答案:只允許在端點(diǎn)處插入和刪除元素T(n)表示當(dāng)輸入規(guī)模為n時(shí)的算法效率，以下算法中效率最優(yōu)的是（

）。

答案:T(n)=T(n/2)+1,T(1)=1下列關(guān)于算法的論述中，正確的有（

）個(gè)。Ⅰ.求解某一類問(wèn)題的算法是唯一的Ⅱ.算法必須在有限步操作之后停止Ⅲ.算法的每一步操作必須是明確的，不能有歧義或含義模糊Ⅳ.算法執(zhí)行后一定產(chǎn)生確定的結(jié)果

答案:3二叉樹與根樹均可以為空樹。

答案:錯(cuò)根樹中頂點(diǎn)個(gè)數(shù)肯定大于1。

答案:錯(cuò)如果一個(gè)圖是連通無(wú)向圖，那圖中任兩個(gè)頂點(diǎn)間肯定有至少一條路徑存在。

答案:對(duì)隊(duì)列在進(jìn)行進(jìn)隊(duì)與出隊(duì)操作時(shí)遵循先進(jìn)先出的原則，棧也一樣。

答案:錯(cuò)樹T中如果有n個(gè)頂點(diǎn)，那么T的邊數(shù)一定是n-1。

答案:對(duì)齊次常系數(shù)遞歸方程對(duì)應(yīng)得特征方程如果有r重根，則重根前面的系數(shù)是關(guān)于n的r-1次多項(xiàng)式。

答案:對(duì)t(n)=t(n-1)+n(n>=2);t(1)=0上述遞歸方程是齊次常系數(shù)遞歸方程。

答案:錯(cuò)遞歸方程可以沒(méi)有遞歸出口條件。

答案:錯(cuò)算法要滿足有限性，程序不需要滿足此特性。

答案:對(duì)O符號(hào)用來(lái)表示算法分析時(shí)兩個(gè)函數(shù)低階及下界的概念。

答案:錯(cuò)算法分析中漸進(jìn)分析分析的是算法而不是程序。

答案:對(duì)算法是行為設(shè)計(jì)，描述對(duì)于給定問(wèn)題，應(yīng)該怎么做。

答案:對(duì)下面選項(xiàng)不是好的算法必須滿足的

答案:有限性/star3/origin/17efdd36b7278817bcb7ab7a593fd9be.jpg

答案:1;2;4;50-1背包問(wèn)題用貪心法和用動(dòng)態(tài)規(guī)劃法都能求出最優(yōu)解和最大價(jià)值。

答案:錯(cuò)任意兩個(gè)矩陣都能進(jìn)行乘法運(yùn)算。

答案:錯(cuò)動(dòng)態(tài)規(guī)劃法求解的問(wèn)題具有最優(yōu)子結(jié)構(gòu)和子問(wèn)題重疊性兩個(gè)基本要素。

答案:對(duì)矩陣連乘問(wèn)題中，當(dāng)計(jì)算4個(gè)矩陣連乘時(shí)計(jì)算次序個(gè)數(shù)為（）。

答案:5下面關(guān)于動(dòng)態(tài)規(guī)劃法和分治法的說(shuō)法錯(cuò)誤的是：

答案:兩者分成的子問(wèn)題都是各自獨(dú)立的。采用貪心策略建立哈夫曼樹時(shí)，采用極大堆組織優(yōu)先隊(duì)列。

答案:錯(cuò)采用貪心法求解問(wèn)題的最優(yōu)解首先必須是可行解，并且符合全局最優(yōu)原則選擇。

答案:錯(cuò)貪心法求0-1背包問(wèn)題不一定得到全局最優(yōu)解。

答案:對(duì)貪心法本著局部最優(yōu)方式構(gòu)造最優(yōu)解對(duì)于背包問(wèn)題來(lái)說(shuō)一定是全局最優(yōu)解。

答案:對(duì)在兩點(diǎn)間的最短路徑問(wèn)題中，如果（v1，v2，。。。vn）是v1到vn的最短路徑，則v2到vn的最短路徑一定是（v2,v3,。。。vn）。

答案:對(duì)關(guān)于貪心法說(shuō)法正確的是：

答案:貪心法是本著局部最優(yōu)策略構(gòu)建最優(yōu)解。采用改進(jìn)的斯特拉森算法進(jìn)行矩陣乘法問(wèn)題求解比傳統(tǒng)數(shù)學(xué)運(yùn)算時(shí)間耗費(fèi)更低，效率更高。

答案:對(duì)利用分治法求k小元素時(shí)，假如劃分成A1，A2，A3，元素個(gè)數(shù)分別為5，2，7，則可以斷定，如果要求第6小元和第7小元不需要第二輪查找。

答案:對(duì)合并排序和選擇排序時(shí)間復(fù)雜度相同。

答案:錯(cuò)分治法求解時(shí)劃分成的子問(wèn)題各自獨(dú)立，性質(zhì)相