算法設(shè)計(jì)與分析課程期末試卷

華南農(nóng)業(yè)大學(xué)期末考試試卷〔A卷)2０04學(xué)年其次學(xué)期〔２005.6) 考試科目：算法設(shè)計(jì)與分析考試類型:(開卷〕考試時(shí)間1２０分鐘學(xué)號題號一姓名二 三四年級專業(yè)總分得分評閱人一、選擇題〔３０分,每題2分)1、一個(gè)算法應(yīng)當(dāng)包含如下幾條性質(zhì),除了A 。〔A〕二義性??(B〕有限性?〔Ｃ)??(D〕可終止性2、解決一個(gè)問題通常有多種方法。假設(shè)說一個(gè)算法“有效”是指 D 。(Ａ)這個(gè)算法能在肯定的時(shí)間和空間資源限制內(nèi)將問題解決(B)這個(gè)算法能在人的反響時(shí)間內(nèi)將問題解決(C)這個(gè)算法比其他算法都更快地將問題解決(D〕AC3、當(dāng)輸入規(guī)模為n時(shí)，算法增長率最小的是 B 。2 〔A〕5n??〔Ｂ〕2０l(fā)ｏgn??(Ｃ)2n2 〔Ｄ)3nｌog2 4、漸進(jìn)算法分析是指 B 。〔A〕算法在最正確狀況、最差狀況和平均狀況下的代價(jià)(Ｂ)當(dāng)規(guī)模逐步往極限方向增大時(shí),對算法資源開銷“增長率”上的簡化分析(Ｃ〕數(shù)據(jù)構(gòu)造所占用的空間(Ｄ)在最小輸入規(guī)模下算法的資源代價(jià)５、當(dāng)上下限表達(dá)式相等時(shí),我們使用以下哪種表示法來描述算法代價(jià)？C(A)大O表示法? (B)大Ω表示法〔C)Θ表示法? 〔D)?。锉硎痉ǎ?、承受“挨次搜尋法”從一個(gè)長度為N的隨機(jī)分布數(shù)組中搜尋值為Ｋ的元素。以下對挨次搜尋法分析正確的選項(xiàng)是 B 。(A)最正確狀況、最差狀況和平均狀況下，挨次搜尋法的漸進(jìn)代價(jià)都一樣(B〕最正確狀況的漸進(jìn)代價(jià)要好于最差狀況和平均狀況的漸進(jìn)代價(jià)最正確狀況和平均狀況的漸進(jìn)代價(jià)要好于最差狀況的漸進(jìn)代價(jià)最正確狀況的漸進(jìn)代價(jià)要好于平均狀況的漸進(jìn)代價(jià),而平均狀況的漸進(jìn)代價(jià)要好于最差狀況的漸進(jìn)代價(jià)7、遞歸通常用 C 來實(shí)現(xiàn)。〔Ａ〕有序的線性表?〔B〕隊(duì)列? 〔C)棧??〔D)數(shù)組8、分治法的設(shè)計(jì)思想是將一個(gè)難以直接解決的大問題分割成規(guī)模較小的子問題,分別解決子問題,最終將子問題的解組合起來形成原問題的解。這要求原問題和子問題 。Ｃ(A〕問題規(guī)模一樣，問題性質(zhì)一樣(Ｂ)問題規(guī)模一樣,問題性質(zhì)不同〔C)問題規(guī)模不同，問題性質(zhì)一樣〔D)問題規(guī)模不同，問題性質(zhì)不同9、在查找n個(gè)元素中第k小元素問題中,如快速排序算法思想,運(yùn)用分治算法對n個(gè)元素進(jìn)展劃分,如何選擇劃分基準(zhǔn)？下面 D 答案解釋最合理?！玻痢畴S機(jī)選擇一個(gè)元素作為劃分基準(zhǔn)(B)取子序列的第一個(gè)元素作為劃分基準(zhǔn)〔C〕用中位數(shù)的中位數(shù)方法查找劃分基準(zhǔn)(D)以上皆可行。但不同方法,算法簡單度上界可能不同１0、對于０－1背包問題和背包問題的解法，下面 C 答案解釋正確?！睞〕0－1背包問題和背包問題都可用貪心算法求解〔B)0-1背包問題可用貪心算法求解，但背包問題則不能用貪心算法求解(C〕0-1背包問題不能用貪心算法求解,但可以使用動(dòng)態(tài)規(guī)劃或搜尋算法求解，而背包問題則可以用貪心算法求解〔D)0－1背包問題不具有最優(yōu)子構(gòu)造性質(zhì)，所以不能用貪心算法求解11、關(guān)于回溯搜尋法的介紹,下面 D是不正確描述。(A〕回溯法有“通用解題法”之稱，它可以系統(tǒng)地搜尋一個(gè)問題的全部解或任意解(B)回溯法是一種既帶系統(tǒng)性又帶有跳動(dòng)性的搜尋算法〔C)回溯算法在生成解空間的任一結(jié)點(diǎn)時(shí),先推斷該結(jié)點(diǎn)是否可能包含問題的解,假設(shè)確定不包含,則跳過對該結(jié)點(diǎn)為根的子樹的搜尋，逐層向祖先結(jié)點(diǎn)回溯〔Ｄ〕回溯算法需要借助隊(duì)列這種構(gòu)造來保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑改:樹構(gòu)造回溯法，又被稱為通用解題法，用它可以系統(tǒng)地搜尋問題的全部解?；厮莘ㄊ且粋€(gè)既從根結(jié)點(diǎn),首先推斷該結(jié)點(diǎn)是否包含問題;否則進(jìn)入這棵子樹連續(xù)按深度優(yōu)先搜尋。如收費(fèi)大路重建問題。12、關(guān)于回溯算法和分支限界法,以下 A是不正確描述。(A)回溯法中，每個(gè)活結(jié)點(diǎn)只有一次時(shí)機(jī)成為擴(kuò)展結(jié)點(diǎn)〔B)分支限界法中,活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn),就一次性產(chǎn)生其全部兒子結(jié)點(diǎn)，在這些兒子結(jié)點(diǎn)中,那些導(dǎo)致不行行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄,其余兒子參加活結(jié)點(diǎn)表中回溯法承受深度優(yōu)先的結(jié)點(diǎn)生成策略(D〕分支限界法承受廣度優(yōu)先或最小消耗優(yōu)先(最大效益優(yōu)先)的結(jié)點(diǎn)生成策略1３、優(yōu)先隊(duì)列通常用以下 B數(shù)據(jù)構(gòu)造來實(shí)現(xiàn)。(A〕?！玻隆扯选玻?隊(duì)列二叉查找樹１4、在分支限界算法中，依據(jù)從活結(jié)點(diǎn)表中選擇下一擴(kuò)展結(jié)點(diǎn)的不同方式可有幾種常用分類,以下 Ｄ 描述最為準(zhǔn)確(A)承受FIFＯ隊(duì)列的隊(duì)列式分支限界法(B〕承受最小值堆的優(yōu)先隊(duì)列式分支限界法(C)承受最大值堆的優(yōu)先隊(duì)列式分支限界法〔D〕以上都常用，針對具體問題可以選擇承受其中某種更為適宜的方式1５、對布線問題，以下 C 是不正確描述(A〕布線問題的解空間是一個(gè)圖〔B),使得算法簡化對邊界的判定〔C〕承受廣度優(yōu)先的標(biāo)號法找到從起點(diǎn)到終點(diǎn)的布線方案〔這個(gè)方案假設(shè)存在的話〕不肯定是最短的(D)b為擴(kuò)展結(jié)點(diǎn)或活結(jié)點(diǎn)隊(duì)列為空作為算法完畢條件二、填空題(20分，每空２分)1、一個(gè)算法簡單性的凹凸表達(dá)在計(jì)算機(jī)運(yùn)行該算法所需的時(shí)間和存儲器資源上，因此算法的簡單性有 時(shí)間 簡單性和 空間 簡單性之分。2、一個(gè)直接或間接調(diào)用自身的算法稱為遞歸 算法。出自于“平衡子問題”的思想，通常分治法在分割原問題，形成假設(shè)干子問題時(shí),這些子問題的規(guī)模都大致 相等 。3、使用二分搜尋算法在ｎ個(gè)有序元素表中搜尋一個(gè)特定元素，在最正確狀況下，搜尋的時(shí)間簡單性為O〔 1),在最壞狀況下，搜尋的時(shí)間簡單性為O〔ｌｏgn?(或log2n) )。4、動(dòng)態(tài)規(guī)劃算法的根本要素是 最優(yōu)子構(gòu)造性質(zhì)?和?子問題重疊性質(zhì) 。５、動(dòng)態(tài)規(guī)劃算法有一個(gè)變形方法 備忘錄方法 。這種方法不同于動(dòng)態(tài)規(guī)劃算法“自底向上”的填充方,而是“自頂向下”的遞歸方向，為每個(gè)解過的子問題建立了備忘錄以備需要時(shí)查看，同樣也可避開一樣子問題的重復(fù)求解。6、貪心算法的根本要素是 貪心選擇性質(zhì)和最優(yōu)子構(gòu)造性質(zhì)。三、簡答題(３２分，五題任選四題,8分)1、有4 個(gè)矩陣{A,A1 2

,,A4

連乘積為AAA1 2

。其中Ai

Ai1

是可乘A1，A2，A3，A4A1A2，A2A3，A3A4A1A2A3，A2A3A4A1A2A3A4n個(gè)C(n,2)個(gè)的i1,A1，A2，A3，A4A1A2，A2A3，A3A4A1A2A3，A2A3A4A1A2A3A4n個(gè)C(n,2)個(gè)2、最大子段和問題：n〔其中可能有負(fù)數(shù))組成的序列aa,a,求該序列1 2 n形如jakki

的子段和的最大值。當(dāng)全部整數(shù)均為負(fù)整數(shù)時(shí)定義其最大子段和為0。依此定義，所求的最優(yōu)值為:max, maxja}1ijn ki記[j]maj1ijkimaxb[j]即為所求。1jn

a},k

1ijn,則對于n個(gè)整數(shù)序列的max{0,a[1]}bjmax{bj1aj],aj]}

j1問：對于實(shí)例〔a,a, ,a=(－2１１，，１3,-，２)依據(jù)前述動(dòng)態(tài)規(guī)1 2 6a劃遞歸式填充ｂ數(shù)組，算法運(yùn)行完畢后,請寫出。aa1a2a3a4a5a6－211－413－5－2bb1b2b3b4b5b60117201513最大子段和值maxb[j]201jn,請計(jì)算最終裝入背包的．。背包涵量：C=５0千克。320100元;2重２０千克,12０元;物品３重３090元。物品１的單位重量價(jià)值為５02的單位重量價(jià)值為６0元／千克；330元/千克。承受貪心算法解此背包問題。此時(shí)，貪心的策略是：每次選擇單位重量價(jià)值最大的物品。因此，首先選擇物品２,13，直至將背包裝滿。2全部裝入背包，當(dāng)前背包中價(jià)值１２０元,背包占用２0千克,30千克;物品1,當(dāng)前背包中價(jià)值220元(120+100元，背包占用千克,剩余１0千克；31/325０元(１20元+100元＋90元×1/3)50千克(裝滿)。因此,最終裝入背包的最大價(jià)值為２50元,物品1和物品２都全部裝入,分別是20千克和２03裝入１/310千克。++＋－---+－+4、對于符號三角問題,n“+”或“-”，以下每++＋－---+－+請畫出訪用回溯法求解第一行有4個(gè)符號〔即n=4)時(shí),的外形。－－＋－＋－＋－＋－＋－＋－＋－＋－＋－＋－＋－＋－＋－＋－＋5、在最接近點(diǎn)對問題中,用一條垂直線L：x=m將平面點(diǎn)集分為大致相等的兩個(gè)子集S1和Ｓ2。設(shè)Ｐ1和P2分別表示直線L的左邊和右邊的寬為d的兩個(gè)垂直長條區(qū)域,dd2分別是Ｓ1S2中最小距離，且設(shè)d＝mｉｎ｛d1,ｄ2}。對于P1中任意一個(gè)點(diǎn)pP２中點(diǎn)q構(gòu)成全平面點(diǎn)集的最接近點(diǎn)對的候選點(diǎn)對，請證明:6對這樣的候選點(diǎn)對。證明:依據(jù)鴿籠原理ｎ+1只鴿子飛入n只或兩只以上的鴿子。將矩形R2ｄ3等分,將它的長為d2等分,6〔d／２〕×(2d/3)的矩形〔如以下圖a所示R6S中的點(diǎn)，則由鴿籠原理易知至少有一個(gè)(d／2)×(２d/3)2個(gè)以上Ｓ中的點(diǎn)。設(shè)u，v是位于同一小2個(gè)點(diǎn),則：(x(u)x(v))2(y(u)y(v))2(d/2)2(2d/3)225d236disｔance(ｕ,v〕≤5d/6＜d。這與d的意義相沖突。即，矩形R中最多只有6個(gè)S中的bR6個(gè)Ｓ中的點(diǎn)的極端情形。四、算法設(shè)計(jì)題〔1８分，五題任選三題,6分〕(6分〕Oｌay教授正在為一家石油公司詢問，該公司正在打算建筑一條由東向西的石油主管道,該管道要穿過一片有n管道直接相連〔噴油管道為南北方向。給定各個(gè)井的X坐標(biāo)和Y坐標(biāo),Olay〔即:使各噴油管長度之和最小〕？噴油管噴油管主油管參考解答:如在X軸上有ｎ個(gè)點(diǎn),由左到右依次排列為X1，X2,…，Xn。XXX1X2…Xn-1 Xn我們期望在x軸上查找一點(diǎn)XpXp與各點(diǎn)距離之和ni1

d(Xi

X 最小。p這個(gè)問題可以歸結(jié)為中位數(shù)問題。即:當(dāng)n為奇數(shù)時(shí)，Ｘp為X ，否則，Xｐ為(X X )/2。(n1)/2 n/2 n/21從這個(gè)例子動(dòng)身,此題求主油管道的問題也是類似的。由于主管道由東向西,因此,要使連接油井和主油管道的噴井管道最短,噴井管道必需南北走向，與主管道垂直,即主管道的最優(yōu)位置應(yīng)為一條Y=Yk的水平線，問題是Yk如何確定。為了使ＹkYY1,Y2,…,Yn間的距離和最短,Y1，…,Yｎ由小到大排序,選擇最中間的那個(gè)點(diǎn)作為Yk,(假設(shè)油井為奇數(shù)，則取第〔n+１)/２小的Y坐標(biāo)作為Ｙk，假設(shè)油井為偶數(shù),n/2Y坐標(biāo)值與第(n／2+１〕小的Y坐標(biāo)值的平均數(shù)作為Yk的值。明顯，確定主油管道的最正確位置,n個(gè)油井的Y坐標(biāo)的中位數(shù)。評分準(zhǔn)則：答到求n個(gè)油井Ｙ坐標(biāo)的中位數(shù)，此題即可得總分值；僅說明求中位數(shù),但未提到是對Y坐標(biāo)求取，扣２分；其它狀況酌情考慮。0-1〔6分)0-1背包問題中，假設(shè)各物品依重量遞增序排列時(shí)，其價(jià)值恰好依遞減序排列，對這個(gè)特別的0-1背包問題,設(shè)計(jì)一個(gè)有效的算法找出最優(yōu)解〔描述你的算法即可，算法的正確性)對于０－１背包問題原來是無法用貪心算法得到最優(yōu)解的,但對于這類特別的０-1背包問題，則可以用貪心算法去解。貪心策略如下:首先將各物品依重量遞增序(即也是價(jià)值遞減序)排列,然后依照價(jià)值遞減挨次選擇物品裝入背包,直到背包裝不下下一件物品為止?！餐瑫r(shí)重量也最小)的物品,然后檢查是否可以裝入背包。評分準(zhǔn)則：答到使用貪心算法，并且貪心策略描述清楚,此題即可得總分值;僅說明使用貪心算法,但貪心策略描述模糊,1~2分;其它狀況酌情考慮。3raｙ〔6分)問題描述:2n次方的序列,滿足：(a)每個(gè)元素都是長度為n比特的串〔ｂ)序列中無一樣元素(ｃ)1個(gè)比特不同例如:ｎ=2時(shí)，格雷碼為｛００,01,11,10}。Grａy碼是一種編碼,這種編碼可以避開在讀取時(shí)，因各數(shù)據(jù)位時(shí)序上的差異造成,輸入長度序列n，輸出格雷碼〔只要做出一種構(gòu)造方案即可,格雷碼并不唯一〕。參考解答:此題也可用分治法解決。當(dāng)n＝1時(shí)，輸出格雷碼{0, 1}n>1時(shí)，格雷碼的長度為2n,即共有2n個(gè)碼序列。此時(shí),將問題一分為二，即上半局部和下半局部。上半局部最高位設(shè)為0,下半局部最高位設(shè)為1。剩下ｎ-１位的格雷碼的構(gòu)造承受遞歸的思路。評分準(zhǔn)則：(即當(dāng)僅輸出１位的格雷碼如何處理，此題即可得總分值；說明使用分治算法，但漏邊界條件,1分；其它狀況酌情考慮。4(6分)問題描述：羽毛球隊(duì)有男女運(yùn)發(fā)動(dòng)各ｎ人。給定兩個(gè)n×ｎ的矩陣Ｐ和Q。P[i］[ｊ]是男運(yùn)發(fā)動(dòng)i和女運(yùn)發(fā)動(dòng)j協(xié)作組成混合雙打的競賽優(yōu)勢,Q[i][j]是女運(yùn)發(fā)動(dòng)ｉ和男運(yùn)發(fā)動(dòng)j協(xié)作的競賽優(yōu)勢。由于技術(shù)協(xié)作或心理狀況等各種因素的影響，P［i][j]并不肯定等于Q［j］[ｉ]。承受回溯法設(shè)計(jì)一個(gè)算法,計(jì)算男女運(yùn)發(fā)動(dòng)最正確搭配的配對法,使得各組男女雙方競賽優(yōu)勢乘積的總和到達(dá)最大。對于這個(gè)問題，解空間如下:男男1男n女1女…女n男…女1女…女n女1女…女n,反之也同理,因此，對于搜尋的第一步選定某男和某女,那么其次個(gè)男隊(duì)員就不能和第一個(gè)男隊(duì)員的女伙伴組合,因此,剪去改女隊(duì)員的分枝。將男女隊(duì)員的競賽優(yōu)勢乘積計(jì)算出來，然后將各組男女的優(yōu)勢乘積進(jìn)展相加。找出最大值。評分準(zhǔn)則:答到使用回溯算法，并且大致寫出回溯的解空間樹及回溯的方法，此題即可得總分值;說明使用回溯算法，但解空間模糊，扣2~3分;其它狀況酌情考慮。5〔6分)2 問題描述:考慮在一臺打印機(jī)上美麗地打印一段文章的問題。輸入的文章正文是由長L1,L，…,Ｌ的n個(gè)英文單詞構(gòu)成的序列。我們期望將這段文章分假設(shè)干行打印出來，每行的最大長度為m,且“美麗度”的標(biāo)準(zhǔn)如下2 假設(shè)某一行包含從單詞i到單詞j，且每兩個(gè)單詞間留一空格，行首無空格，則在行末多余的空格數(shù)為：mjij Lkki〔解釋：這個(gè)公式如何得到呢？由于某一行包含單詞i到單詞j，且每兩個(gè)單詞間留一空格，因此單詞間的空格數(shù)為ｊ－ii個(gè)單詞到第j個(gè)單詞的長度和為j Lkki

,因此行末多余的空格為mjij L ?！砶ki不同的斷行(即切斷從單詞i到單詞ｊ形成一行〕的方式，將可能產(chǎn)生不同的“美麗度”〔即除最終一行的全部行的行末多余空格總和〕。我們期望除最終一行的全部行中，行末多余空格的總和最小。請用動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)出一個(gè)美麗的打印出一段有n個(gè)單詞的文章的方案。參考解答:此題的題目已經(jīng)指定了動(dòng)態(tài)規(guī)劃算法,而且算法思路也已較為清楚，所需要做的只是寫出狀態(tài)轉(zhuǎn)移方程和邊界設(shè)定。ijnj1](mjijn0

ji

L)}k

(1in)n1)解題思路提示：由于必需打印完n個(gè)單詞且每行打印的單詞是連續(xù)的，因此，我們從第n個(gè)單詞開頭，依次考慮填一個(gè)單詞〔單詞n〕，填兩個(gè)單詞〔單詞n-１,單詞n),……,填ｎ個(gè)單詞〔單詞１,2，…，單詞n〕的打印方案。由于單詞填入的方式是按單詞序號遞減的挨次進(jìn)展的，．．．設(shè)ｒ［i]—— 填入單詞ｉ到單詞n后,全部被填行的行末空格數(shù)總和的最小值。明顯,r[ｉ]的動(dòng)態(tài)規(guī)劃遞歸式可以由以上思路得到。另外，我們特地設(shè)置了一張記憶表k[i]〔1≤i≤ ｎ+１),登記使得r[i]最小的j值，表示填單詞i到單詞n的最正確方案中,第一行應(yīng)填單詞i到單詞j(ｊ即是k[ｉ])。ｒ的遞歸的邊界可定義為：r［n+１]＝0;k［n+1]=ｎ+1;表示不填任何單詞時(shí)的行0。我們從ｒ[ｎ+1]動(dòng)身,依次求ｒ[n］,r[n－1],…，ｒ[1]。由r[i]的遞歸式的由來可以看出，求r[i］最小值的子問題,包含了求r[ｉ+l]，…,r[n＋ｌ]這些子問題。要使r[ｉ]最小，必需使這些子問題的值最小,因此符合動(dòng)態(tài)規(guī)劃程序設(shè)計(jì)要求的“最優(yōu)子構(gòu)造”,充分利用了重疊子問題。最終求出的r［１]即為最優(yōu)“美麗打印方案”中行末空格數(shù)的總和；從單詞１動(dòng)身,順著記憶表K的指示,可挨次打印出文章的各行。問題和任務(wù):依據(jù)以上的算法提示，請寫出r[i]的動(dòng)態(tài)規(guī)劃遞歸式，并定義遞歸的邊界。２00４學(xué)年第一學(xué)期考試科目:算法設(shè)計(jì)與分析〔開卷〕120分鐘學(xué)號姓名年級專業(yè)題號 一 二三四 總分得分評閱人５Ｃ１０Ｃ一、選擇題(30分，每題５Ｃ１０Ｃ１A２D3B4Ｂ6B７C８C9D1111Ｄ１2Ａ13B14D15C二、填空題(２0分，每空2分〕1、時(shí)間?空間2、遞歸?相等3、１ logｎ?〔或log2n〕4、最優(yōu)子構(gòu)造性質(zhì)5、備忘錄方法６、貪心選擇性質(zhì)

?子問題重疊性質(zhì)三、簡答題(32分,五題任選四題,每題8分)1、子問題如下所列:A1A1，A2，A3，A4A1A2，A2A3，A3A4A1A2A3，A2A3A4A1A2A3A4n個(gè)C(n,2)個(gè)２、aa1a2a3a4a5a6－211－413－5－2bb1b2b3b4b5b60117201513最大子段和值maxb[j]201jn3、15０元/千克;260元/千克;3的單位重量價(jià)值為３０元/千克。承受貪心算法解此背包問題。此時(shí),,1,最終是物品３,直至將背包裝滿。物品2120千克，剩余30千克；1全部裝入背包,220〔１2０元+１0０元)，背包占用401０千克；31/32５0元〔120元＋100元＋９０元×１/３〕,50千克〔裝滿。因此,2501和物品２都全部裝入,2020千克,31／310千克。4、4個(gè)符號〔即n=4)時(shí)，解空間樹是一棵完全二叉樹。－－＋－＋－＋－＋－＋－＋－＋－＋－＋－＋－＋－＋－＋－＋－＋5、證明：依據(jù)鴿籠原理：假設(shè)n+1只鴿子飛入n個(gè)籠子中，那么至少有一個(gè)籠子里包含兩只或兩只以上的鴿子。2d的邊３等分,將它的長為d的邊２等分,由此導(dǎo)出６個(gè)(ｄ/2〕×(2d/3)的矩形〔如以下圖a所示6S中的點(diǎn)，則由鴿籠原理易知至少有一個(gè)(d/2)×〔2d/3)的小矩形中有２個(gè)以上Su,v是位于同一小矩形2個(gè)點(diǎn),則：(x(u)x(v))2(y(u)y(v))2(d/2)2(2d/3)225d236。這與ｄR中最多只有６個(gè)Ｓ中的bRS中的點(diǎn)的極端情形。四、算法設(shè)計(jì)題(18分,五題任選三題,每題６分〕1(6分)參考解答:這是中位數(shù)的應(yīng)用問題。在挨次統(tǒng)計(jì)的問題中,中位數(shù)的應(yīng)用最廣,例如在X軸上有n個(gè)點(diǎn),由左到右依次排列為X1,Ｘ２,…,Ｘｎ。XX1 X2 … Xn-1 Xn我們期望在x軸上查找一點(diǎn)ＸｐXp與各點(diǎn)距離之和ni1

d(Xi

X 最小。p這個(gè)問題可以歸結(jié)為中位數(shù)問題。即：當(dāng)ｎ為奇數(shù)時(shí),Xp為X(n1)/2，否則，Xｐ為(Xn/2Xn/21/2。從這個(gè)例子動(dòng)身,此題求主油管道的問題也是類似的。由于主管道由東向西,因此，要使連接油井和主油管道的噴井管道最短,噴井管道必需南北走向,Y＝Y(jié)ｋ的水平線,問題是Yk如何確定。為了使Yk與各油井的Ｙ坐標(biāo)Y1，Y２,…,Ｙｎ間的距離和最短,我們將Ｙ１,…，Yｎ由小到大排序,選擇最中間的那個(gè)點(diǎn)作為Yk,(假設(shè)油井為奇數(shù)，則取第〔n+1〕／2小Y坐標(biāo)作為Yk，假設(shè)油井為偶數(shù)，則取第ｎ/2小的Ｙ坐標(biāo)值與第(ｎ／2+1)小的Ｙ坐標(biāo)值的平均數(shù)作為Yk的值。明顯,確定主油管道的最正確位置，實(shí)際上就是求ｎ個(gè)油井的Ｙ坐標(biāo)的中位數(shù)。評分準(zhǔn)則:答到求n個(gè)油井Y坐標(biāo)的中位數(shù),此題即可得總分值；僅說明求中位數(shù)，但未提到是對Y坐標(biāo)求取,扣