算法設計與分析學習通超星期末考試答案章節(jié)答案2024年

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

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

設一組初始記錄關鍵字的長度為

8，則最多經過（

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

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

和度數(shù)為2

的結點且度數(shù)為0

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

）個結點。

答案:

2n-1設有n

個關鍵字具有相同的Hash

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

個關鍵字映射到HASH表中需要做（

）次線性探測。

答案:

n(n-1)/2設一組權值集合W=(15，3，14，2，6，9，16，17)，要求根據這些權值集合構造一棵哈夫曼樹，則這棵哈夫曼樹的帶權路徑長度為（

）。

答案:229二叉排序樹中左子樹上所有結點的值均（

）根結點的值。

答案:<設有一個

10

階的下三角矩陣

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

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

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

）。

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

）。

答案:

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

）存儲方式最節(jié)省運算時間。

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

答案:4設順序線性表的長度為30，分成5

塊，每塊6

個元素，如果采用分塊查找，則其平均查找長度為（）。

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

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

）。

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

個頂點，則該完全無向圖中有（

）條邊。

答案:n(n-1)/2

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

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

的結點數(shù)有2

個，度數(shù)為2

的結點數(shù)有1

個，度數(shù)為1的結點數(shù)有2個，那么度數(shù)為0的結點數(shù)有（）個。

答案:6設

F

是由

T1、T2

和

T3

三棵樹組成的森林，與

F

對應的二叉樹為

B，T1、T2

和

T3

的結點數(shù)分別為

N1、N2

和N3，則二叉樹

B

的根結點的左子樹的結點數(shù)為（）。

答案:

N1-1設順序線性表中有n

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

個元素需要移動（

）個元素。

答案:n-i隊列是一種（

）的線性表。

答案:先進先出設無向圖G

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

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

答案:aedfcb設一棵完全二叉樹中有

65

個結點，則該完全二叉樹的深度為（

）。

答案:7設一個順序有序表A[1:14]中有14

個元素，則采用二分法查找元素A[4]的過程中比較元素的順序為()。

答案:

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

）。

答案:同時具備(A)和(B)兩個條件字符串的長度是指（）。

答案:串中所含字符的個設某棵二叉樹的高度為10，該二叉樹上葉子結點最多有（

）。

答案:512（

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

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

的存儲結構，則有向圖G

中頂點i

的入度為（

）。

答案:第

i

列非

0

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

）。

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

）。

答案:

任一結點無右孩子設一組初始記錄關鍵字序列為(45，80，55，40，42，85)，則以第一個記錄關鍵字45為基準而得到一趟快速排序的結果是（

）。

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

）。

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

）的空間復雜度最大。

答案:快速排序設用鏈表作為棧的存儲結構則退棧操作（

）。

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

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

答案:3設某無向圖中有n

個頂點e

條邊，則該無向圖中所有頂點的入度之和為（

）。

答案:2e設有5000

個待排序的記錄關鍵字，如果需要用最快的方法選出其中最小的10

個記錄關鍵字，則用下列（

）方法可以達到此目的。

答案:堆排序設某強連通圖中有

n

個頂點，則該強連通圖中至少有（

）條邊。

答案:n設無向圖G

中有n

個頂點e

條邊，則其對應的鄰接表中的表頭結點和表結點的個數(shù)分別為（

）。

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

為

基準記錄的一趟快速排序結束后的結果為()。

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

設一組初始記錄關鍵字序列(5，2，6，3，8)，以第一個記錄關鍵字5

為基準進行一趟快速排序的結果為（

）。

答案:3，2，5，6，8設某有向圖中有

n

個頂點，該有向圖對應的鄰接表中有（

）個表頭結點。

答案:n設某棵二叉樹中有

2000

個結點，則該二叉樹的最小高度（

）。

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

ABCD，前序遍歷序列為

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

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

答案:2m下面關于線性表的敘述錯誤的是（）。

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

答案:二叉樹用鏈接方式存儲的隊列，在進行插入運算時(

)。

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

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

）。

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

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

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

答案:錯根樹中頂點個數(shù)肯定大于1。

答案:錯如果一個圖是連通無向圖，那圖中任兩個頂點間肯定有至少一條路徑存在。

答案:對隊列在進行進隊與出隊操作時遵循先進先出的原則，棧也一樣。

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

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

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

答案:錯遞歸方程可以沒有遞歸出口條件。

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

答案:對O符號用來表示算法分析時兩個函數(shù)低階及下界的概念。

答案:錯算法分析中漸進分析分析的是算法而不是程序。

答案:對算法是行為設計，描述對于給定問題，應該怎么做。

答案:對下面選項不是好的算法必須滿足的

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

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

答案:錯任意兩個矩陣都能進行乘法運算。

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

答案:對矩陣連乘問題中，當計算4個矩陣連乘時計算次序個數(shù)為（）。

答案:5下面關于動態(tài)規(guī)劃法和分治法的說法錯誤的是：

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

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

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

答案:對貪心法本著局部最優(yōu)方式構造最優(yōu)解對于背包問題來說一定是全局最優(yōu)解。

答案:對在兩點間的最短路徑問題中，如果（v1，v2，。。。vn）是v1到vn的最短路徑，則v2到vn的最短路徑一定是（v2,v3,。。。vn）。

答案:對關于貪心法說法正確的是：

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

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

答案:對合并排序和選擇排序時間復雜度相同。

答案:錯分治法求解時劃分成的子問題各自獨立，性質相