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

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

一、 排序和查找是經(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à)值如下表所示。若這些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包問(wèn)題。請(qǐng)寫出狀態(tài)空間搜索樹（20分）。 物品 A B C D E F G 重量 35 30 60 50 40 10 25 價(jià)值 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的最佳求積順序。（要求：給出計(jì)算步驟）（20分） 五、回答如下問(wèn)題：（20分） （1） 什么是算法？算法的特征有哪些？ （2） 什么是P類問(wèn)題？什么是NP類問(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à)值如下表所示。若這些物品均可以被分割，且背包容量M＝150，如果使用貪心方法求解此背包問(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)的？ 物品 A B C D E F G 重量 35 30 60 50 40 10 25 價(jià)值 10 40 30 50 35 40 30 三、 多段圖問(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類問(wèn)題？什么是NP類問(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的方格的棋盤上，將數(shù)字1到15代表的15個(gè)棋子以任意的順序置入各方格中，空出一格。要求通過(guò)有限次的移動(dòng)，把一個(gè)給定的初始狀態(tài)變成目標(biāo)狀態(tài)。移動(dòng)的規(guī)則是：每次只能把空格周圍的四格數(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)的搜索樹。 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) 目標(biāo)狀態(tài) 五、設(shè)x1、x2、x3是一個(gè)三角形的三條邊，而且x1+x2+x3=14。請(qǐng)問(wèn)有多少種不同的三角形？給出解答過(guò)程。（20分） 第 4 頁(yè) 共 4 頁(yè)