山東科技大學(xué)算法設(shè)計與分析試題

《山東科技大學(xué)算法設(shè)計與分析試題》由會員分享，可在線閱讀，更多相關(guān)《山東科技大學(xué)算法設(shè)計與分析試題（4頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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