一、 排序和查找是經(jīng)常遇到的問(wèn)題。按照要求完成以下各題：（20分）（1） 對(duì)數(shù)組A=15，29，135，18，32，1，27，25，5，用快速排序方法將其排成遞減序。（2） 請(qǐng)描述遞減數(shù)組進(jìn)行二分搜索的基本思想，并給出非遞歸算法。（3） 給出上述算法的遞歸算法。（4） 使用上述算法對(duì)（1）所得到的結(jié)果搜索如下元素，并給出搜索過(guò)程：18，31，135。二、 對(duì)于下圖使用Dijkstra算法求由頂點(diǎn)a到頂點(diǎn)h的最短路徑。（20分）。三、 假設(shè)有7個(gè)物品，它們的重量和價(jià)值如下表所示。若這些物品均不能被分割，且背包容量M150，使用回溯方法求解此背包問(wèn)題。請(qǐng)寫(xiě)出狀態(tài)空間搜索樹(shù)（20分）。物品ABCDEFG重量35306050401025價(jià)值10403050354030四、 已知，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，r6=50，r7=6，求矩陣鏈積A1×A2×A3×A4×A5×A6的最佳求積順序。（要求：給出計(jì)算步驟）（20分）五、回答如下問(wèn)題：（20分）（1） 什么是算法？算法的特征有哪些？（2） 什么是P類(lèi)問(wèn)題？什么是NP類(lèi)問(wèn)題？請(qǐng)描述集合覆蓋問(wèn)題的近似算法的基本思想。一、 排序和查找是常用的計(jì)算機(jī)算法。按照要求完成以下各題：（20分）（1） 對(duì)數(shù)組A=15，9，115，118，3，90，27，25，5，使用合并排序方法將其排成遞減序。（2） 若改變二分搜索法為三分搜索法，即從一個(gè)遞減序列A中尋找元素Z，先與元素比較，若，則在前面?zhèn)€元素中尋找Z；否則與比較，總之使余下的序列為個(gè)元素。給出該方法的偽代碼描述。（3） 使用上述算法對(duì)（1）所得到的結(jié)果搜索如下元素，并給出搜索過(guò)程：118，31，25。二、 假設(shè)有7個(gè)物品，它們的重量和價(jià)值如下表所示。若這些物品均可以被分割，且背包容量M150，如果使用貪心方法求解此背包問(wèn)題，請(qǐng)回答：（20分）。（1） 對(duì)各個(gè)物品進(jìn)行排序時(shí)，依據(jù)的標(biāo)準(zhǔn)都有哪些？（2） 使用上述標(biāo)準(zhǔn)分別對(duì)7個(gè)物品進(jìn)行排序，并給出利用各個(gè)順序進(jìn)行貪心求解時(shí)獲得解。（3） 上述解中哪個(gè)是最優(yōu)的？ 物品ABCDEFG重量35306050401025價(jià)值10403050354030三、 多段圖問(wèn)題：設(shè)G(V，E)是一個(gè)賦權(quán)有向圖，其頂點(diǎn)集V被劃分成k>2個(gè)不相交的子集Vi：，其中，V1和Vk分別只有一個(gè)頂點(diǎn)s（稱為源）和一個(gè)頂點(diǎn)t（稱為匯），圖中所有的邊（u,v），。求由s到t的最小成本路徑。（25分）（1） 給出使用動(dòng)態(tài)規(guī)劃算法求解多段圖問(wèn)題的基本思想。（2） 使用上述方法求解如下多段圖問(wèn)題。四、回答如下問(wèn)題：（15分）（3） 什么是算法？算法的特征有哪些？（4） 什么是P類(lèi)問(wèn)題？什么是NP類(lèi)問(wèn)題？請(qǐng)描述集合覆蓋問(wèn)題的近似算法的基本思想。五、設(shè)x1、x2、x3是一個(gè)三角形的三條邊，而且x1+x2+x3=14。請(qǐng)問(wèn)有多少種不同的三角形？給出解答過(guò)程。（20分）一、 設(shè)數(shù)組A有n個(gè)元素，需要找出其中的最大最小值。（20分）（1） 請(qǐng)給出一個(gè)解決方法，并分析其復(fù)雜性。（2） 把n個(gè)元素等分為兩組A1和A2，分別求這兩組的最大值和最小值，然后分別將這兩組的最大值和最小值相比較，求出全部元素的最大值和最小值。如果A1和A2中的元素多于兩個(gè)，則再用上述方法各分為兩個(gè)子集。直至子集中元素至多兩個(gè)元素為止。這是什么方法的思想？請(qǐng)給出該方法的算法描述，并分析其復(fù)雜性。二、 已知，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，r6=50，r7=6，求矩陣鏈積A1×A2×A3×A4×A5×A6的最佳求積順序。（20分）三、 對(duì)于下圖使用Dijkstra算法求由頂點(diǎn)a到其他各個(gè)頂點(diǎn)的最短路徑。并給出求各個(gè)頂點(diǎn)對(duì)之間的最短路徑的算法思想。（20分）。四、 15謎問(wèn)題：在一個(gè)4×4的方格的棋盤(pán)上，將數(shù)字1到15代表的15個(gè)棋子以任意的順序置入各方格中，空出一格。要求通過(guò)有限次的移動(dòng)，把一個(gè)給定的初始狀態(tài)變成目標(biāo)狀態(tài)。移動(dòng)的規(guī)則是：每次只能把空格周?chē)乃母駭?shù)字（棋子）中的任意一個(gè)移入空格，從而形成一個(gè)新的狀態(tài)。為了有效的移動(dòng)，設(shè)計(jì)了估值函數(shù)C1(x)，表示在結(jié)點(diǎn)x的狀態(tài)下，沒(méi)有到達(dá)目標(biāo)狀態(tài)下的正確位置的棋子的個(gè)數(shù)。（20分）請(qǐng)使用該估計(jì)函數(shù)，對(duì)圖示的初始狀態(tài)，給出使用分支限界方法轉(zhuǎn)換到目標(biāo)狀態(tài)的搜索樹(shù)。124563791012813141115123456789101112131415 初始狀態(tài) 目標(biāo)狀態(tài)五、設(shè)x1、x2、x3是一個(gè)三角形的三條邊，而且x1+x2+x3=14。請(qǐng)問(wèn)有多少種不同的三角形？給出解答過(guò)程。（20分）第 4 頁(yè) 共 4 頁(yè)