【正文】 ? A． O(lgn) B． O(nlgn) C． O(n) D． O(n2) ? T(n)=2T(n/2)+n =4T(n/4)+n+n =…… =2kT(1)+kn (n=2k) =+nlog2n 2022年 11月試題 57 ? 求單源點最短路徑的迪杰斯特拉（Dijkstra）算法是按 （ 57） 的順序求源點到各頂點的最短路徑的。 ? A. 路徑長度遞減 B. 路徑長度遞增 C. 頂點編號遞減 D. 頂點編號遞增 ? 答案： B 2022年 11月試題 58 ? _____算法策略與遞歸技術(shù)的聯(lián)系最弱。 ? A．動態(tài)規(guī)劃 B．貪心 C．回溯 D．分治 ? B 2022年 11月試題 59,60 ? 對于有 n個元素的一個數(shù)據(jù)序列，若只需得到其中第 k個元素之前的部分序列，最好采用 __(59)__，使用分治 (Divide and Conquer)策略的是 __(60)__算法。 ? (59)A. 希爾排序 B. 直接插入排序 C. 快速排序 D. 堆排序 ? (60)A. 冒泡排序 B. 插入排序 C. 快速排序 D. 堆排序 ? D C 2022年 11月下午試題四 ? 閱讀以下說明和圖，填補(bǔ)流程圖中的空缺，將解答填入答題紙的對應(yīng)欄內(nèi)。 [說明 ]某汽車制造工廠有兩條裝配線。汽車裝配過程如圖 41所示，即汽車底盤進(jìn)入裝配線，零件在多個工位裝配，結(jié)束時汽車自動完成下線工作。 2022年 11月下午試題四 ? (1) e0 和 e1 表示底盤分別進(jìn)入裝配線 0 和裝配線 1 所需要的時間。 ? (2) 每條裝配線有 n 個工位，第一條裝配線的工位為 S0,0, S0,1, … , S0,n1, 第二條裝 配線的工位為 S1,0, S1,1, … , S1,n1。其中 S0,k 和 S1,k（0≤k≤n 1）完成相同的任務(wù)，但所需時間可能不同。 ? (3) ai,j 表示在工位 Si,j 處的裝配時間，其中 i 表示裝配線（ i=0 或 i=1） ,j 表示工位號 (0≤j≤n 1)。 ? (4) ti,j 表示從 Si,j 處裝配完成后轉(zhuǎn)移到另一條裝配線下一個工位的時間。 ? (5) x0 和 x1 表示裝配結(jié)束后，汽車分別從裝配線 0 和裝配線 1 下線所需要的時間。 ? (6) 在同一條裝配線上，底盤從一個工位轉(zhuǎn)移到其下一個工位的時間可以忽略不計。 2022年 11月下午試題四 ? 圖 42 所示的流程圖描述了求最短裝配時間的算法，該算法的輸入為： n: 表示裝配線上的工位數(shù)； e[i]: 表示 e1 和 e2， i 取值為 0 或 1； a[i][j]:表示 ai,j， i 的取值為 0 或 1， j 的取值范圍為 0～ n1； t[i][j]:表示 ti,j, i 的取值為 0 或 1， j 的取值范圍為 0～ n1； x[i]: 表示 x0 和 x1， i 取值為 0 或 1。 ? 算法的輸出為： fi:最短的裝配時間； li:獲得最短裝配時間的下線裝配線號 (0 或者 1)。 算法中使用的 f[i][j]表示從開始點到 Si,j 處的最短裝配時間。 2022年 11月下午試題四 (1) f[0][0] = e[0] + a[0][0] f[1][0] = e[1] + a[1][0] (2) f[0][j1]+a[0][j] (3) f[1][j1]+a[1][j] f[0][j1]+t[0][j1]+a[1][j] (4) fi = f[0][n1]+x[0] li = 0 (5) fi = f[1][n1]+x[1] li = 1 2022年 5月試題 62 ? 設(shè)商店有 10 元、 5 元、 2 元和 1 元的零幣，每種零幣的數(shù)量充足。售貨員給顧客找零錢時，零幣的數(shù)量越少越好。例如給顧客找零 29 元：先選 2 張 10 元幣，然后選擇 1張 5 元幣，再選擇兩張 2 元幣。以上的找零錢方法采用了 （ 62）策略。 ? A. 分治 B. 貪心 C. 動態(tài)規(guī)劃 D. 回溯 ? B 2022年 5月試題 6465 2022年 5月下午試題四 ? [說明 ]在一條農(nóng)村公路的一邊稀疏地分布著房子，其分布如圖 41所示。某電信公司需要在某些位置放置蜂窩電話基站，由于基站的覆蓋范圍是 6公里，因此必須使得每棟房子到某個基站的直線距離不超過 6公里。為簡化問題，假設(shè)所有房子在同一直線上，并且基站沿該直線放置?，F(xiàn)采用貪心策略實現(xiàn)用盡可能少的基站覆蓋所有的房子。 2022年 5月下午試題四 ? 實現(xiàn)貪心算法的流程如圖 42所示，請?zhí)羁詹⒂嬎阍撍惴ǖ臅r間復(fù)雜度，其中： ? 1． d[i](1≤i≤N) 表示第 i個房子到公路 A端的距離， N表示房子的總數(shù)，按房子到公路 A端的距離從小到大進(jìn)行房子編號。 ? 2． s[k]表示第 k（ k≥1 ）個基站到公路 A端的距離，算法結(jié)束后 k的值為基站的總數(shù)。 分析：問題解的模型 該算法的時間復(fù)雜度為 (5) k=0 j=N k++ d[i]+6 O(n) 2022年 11月試題 63 ? 迪杰斯特拉（ Dijkstra)算法按照路徑長度遞增的方式求解單源點最短路徑問題，該算法運(yùn)用了 （ 63） 算法策略。 ? A. 貪心 B. 分而治之 C. 動態(tài)規(guī)劃 D. 試探＋回溯 ? A 2022年 11月試題 64 ? 關(guān)于算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系， （ 64） 是正確的。 ? A. 算法的實現(xiàn)依賴于數(shù)據(jù)結(jié)構(gòu)的設(shè)計 B. 算法的效率與數(shù)據(jù)結(jié)構(gòu)無關(guān) C. 數(shù)據(jù)結(jié)構(gòu)越復(fù)雜，算法的效率越高 D. 數(shù)據(jù)結(jié)構(gòu)越簡單，算法的效率越高 ? A 2022年 11月試題 65 ? 若一個問題既可以用迭代方式也可以用遞歸方式求解，則 （ 65） 方法具有更高的時空效率。 ? A. 迭代 B. 遞歸 C. 先遞歸后迭代 D. 先迭代后遞歸 ? A 2022年 11月下午試題四 ? 說明：某機(jī)器上需要處理 n個作業(yè) job1, job2, … , jobn，其中： 1. 每個作業(yè) jobi(1≤i≤n) 的編號為 i， jobi有一個 收益值 p[i]和 最后期限值 d[i]； 2. 機(jī)器在一個時刻只能處理一個作業(yè)， 而且每個作業(yè)需要一個單位時間進(jìn)行處理 ，一旦作業(yè)開始就不可中斷，每個作業(yè)的最后期限值為單位時間的正整數(shù)倍； 3. job1～ jobn的 收益值呈非遞增順序排列 ，即p[1]≥p[2]≥ … ≥p[n] ； 4. 如果作業(yè) jobi在其期限之內(nèi)完成，則獲得收益p[i]；如果在其期限之后完成，則沒有收益。 2022年 11月下午試題四 ? 為獲得較高的收益，采用貪心策略求解在期限之內(nèi)完成的作業(yè)序列。圖 41是基于貪心策略求解該問題的流程圖。 1. 整型數(shù)組 J[]有 n個存儲單元，變量 k表示在期限之內(nèi)完成的作業(yè)數(shù)， J[1..k]存儲所有能夠在期限內(nèi)完成的 作業(yè)編號 ，數(shù)組J[1..k]里的作業(yè) 按其最后期限非遞減排 序，即 d[J[1]]≤ … ≤d[J[k]] 。 2. 為了方便于在數(shù)組 J中加入作業(yè)，增加一個虛擬作業(yè) job0，并令 d[0] = 0， J[0] = 0。 2022年 11月下午試題四 3. 算法大致思想：先將作業(yè) job1的編號 1放入 J[1]，然后，依次對每個作業(yè) jobi(2≤i≤n) 進(jìn)行判定，看其能否插入到數(shù)組 J中，若能，則將其編號插入到數(shù)組 J的適當(dāng)位置，并保證 J中作業(yè)按其最后期限非遞減排列，否則不插入。 jobi能插入數(shù)組 J的 充要條件 是： jobi和數(shù)組 J中已有作業(yè)均能在其期限之內(nèi)完成。 4. 流程圖中的主要變量說明如下： i：循環(huán)控制變量，表示作業(yè)的編號； k：表示在期限內(nèi)完成的作業(yè)數(shù)； r：若 jobi能插入數(shù)組 J，則其在數(shù)組 J中的位置為 r+1； q：循環(huán)控制變量，用于移動數(shù)組 J中的元素。 開始d [ 0 ] = J [ 0 ] = 0 。J [ 1 ] = 1 。 k = 1i = 2( 1 ) r = k ( 2 ) amp。amp。d [ J [ r ]] r ?r = r 1d [ J [ r ]] = d [ i ] amp。amp。 d [ i ] r ?q = kq = r + 1 ?J [ q + 1 ] = J [ q ] 。輸入作業(yè)數(shù) n和期限數(shù)組 d結(jié)束輸出可完成的作業(yè)序列YNYNYNYN處理 a處理 a 開始處理 a 結(jié)束i ++q = q 1( 3 )k ++?(1) i=n (2) d[i]d[J[r]] (3) J[r+1]=i 2022年 11月下午試題四 ? 【 問題 1】 （ 9分）請?zhí)畛鋱D 41中的空缺 (1)、(2)和 (3)處。 2022年 11月下午試題四 ? 【 問題 2】 (4分 )假設(shè)有 6個作業(yè) job1, job2, … , job6；完成作業(yè)的收益數(shù)組p=(p[1],p[2],p[3],p[4],p[5],p[6]) = (90,80,50,30,20,10)； 每個作業(yè)的處理期限數(shù)組d=(d[1],d[2],d[3],d[4],d[5],d[6]) = (1,2,1,3,4,3)。 請應(yīng)用試題中描述的貪心策略算法，給出在期限之內(nèi)處理的作業(yè)編號序列 (4) （按作業(yè)處理的順序給出），得到的總收益為 (5) 。 5 220 2022年 11月下午試題四 2022年 11月下午試題四 ? 【 問題 3】 (2分 ) 對于本題的作業(yè)處理問題，用圖 41的貪心算法策略，能否求得最高收益？ (6) 。 用貪心算法求解任意給定問題時，是否一定能得到最優(yōu)解？ (7) 。 能 不能 2022年 5月試題 62 ? 一個算法本是對某類給定問題求解過程的精確描述，算法中描述的操作都可以通過將已經(jīng)實現(xiàn)的基本操作執(zhí)行有限次來實現(xiàn)，這句話說明算法具有 （ 62） 特性。 ? ? B 2022年 5月試題 6364 ? 斐波那契 (Fibonacci)數(shù)列可以遞歸地定義為： 用遞歸算法求解 F(5)時需要執(zhí)行 （ 63） 次 “ +”運(yùn)算，該方法采用的算法策略是 （ 64） 。 ? （ 63） A. 5 B. 6 C. 7 D. 8 ? （ 64） ? C B 2022年 5月試題下午試題四 ? 說明：快速排序是一種典型的分治算法。采用快速排序?qū)?shù)組 A[p..r]排序的三個步驟如下： 1. 分解：選擇一個樞軸（ pivot）元素劃分?jǐn)?shù)組。將數(shù)組 A[p..r]劃分為兩個子數(shù)組（可能為空）A[p..q1]和 A[q+1..r]，使得 A[q]大于等于A[p..q1]中的每個元素，小于 A[q+1..r]中的每個元素。 q的值在劃分過程中計算。 2. 遞歸求解：通過遞歸的調(diào)用快速排序，對子數(shù)組 A[p..q1]和 A[q+1..r]分別排序。 3. 合并：快速排序在原地排序，故不需合并操作。 2022年 5月試題下午試題四 ? 【 問題 1】 （ 6分）下面是快速排序的偽代碼，請?zhí)羁?。主要變量說明如下： A：待排序數(shù)組 p, r：數(shù)組元素下標(biāo)，從 p到 r q：劃分的位置 x：樞軸元素 i：整型變量，用于描述數(shù)組下標(biāo)。下標(biāo)小于或等于 i的元素的值小于或等于樞軸元素的值 j：循環(huán)控制變量，表示數(shù)組元素下標(biāo) 2022年 5月試題下午試題四 ? QUICKSORT(A, p, r){ if (p r){ q = PARTITION(A,p,r) 。 QUICKSORT(A, p, q1)。 QUICKSORT(A, q+1, r)。 } } ? PARTITION(A, p, r){ x = A[r]。 i = p – 1。 for (j = p 。 j=r – 1。 j++){ if (A[j]x){ i = i + 1 。 交換 A[i]和 A[j] } } 交換 （ 1） 和 （ 2） //（ 1）和（ 2）答案可互換，但兩空全部答對方可得