算法設(shè)計(jì)與分析章節(jié)練習(xí)(2020.02.09)

來(lái)源：考試資料網(wǎng)

1.問(wèn)答題設(shè)計(jì)算法，在數(shù)組r[n]中刪除重復(fù)的元素，要求移動(dòng)元素的次數(shù)較少并使剩余元素間的相對(duì)次序保持不變。

2.問(wèn)答題一個(gè)旅行者要駕車從A地到B地，A、B兩地間距離為s。A、B兩地之間有n個(gè)加油站，已知第i個(gè)加油站離起點(diǎn)A的距離為d_i公里，0=d1n≤s，車加滿油后可行駛m公里，出發(fā)之前汽車油箱為空。應(yīng)如何加油使得從A地到B地沿途加油次數(shù)最少？給出用貪心法求解該最優(yōu)化問(wèn)題的貪心選擇策略，寫出求該最優(yōu)化問(wèn)題的最優(yōu)值和最優(yōu)解的貪心算法，并分析算法的時(shí)間復(fù)雜性。

參考答案：貪心選擇策略：從起點(diǎn)的加油站起每次加滿油后不加油行駛盡可能遠(yuǎn)，直至油箱中的油耗盡前所能到達(dá)的最遠(yuǎn)的油站為止，在該油站再加...

點(diǎn)擊查看完整答案

進(jìn)入題庫(kù)練習(xí)

3.問(wèn)答題請(qǐng)寫出用回溯法解裝載問(wèn)題的函數(shù)。裝載問(wèn)題：有一批共n個(gè)集裝箱要裝上2艘載重量分別為c1和c2的輪船，其中集裝箱i的重量為wi。裝載問(wèn)題要求確定是否有一個(gè)合理的裝載方案可將這n個(gè)集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。

參考答案：

進(jìn)入題庫(kù)練習(xí)

4.問(wèn)答題 數(shù)塔問(wèn)題。有形如下圖所示的數(shù)塔，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向左走或是向右走，一起走到底層，要求找出一條路徑。算法如下，空白處應(yīng)填？

參考答案：

1.c<=r
2.t[r][c]+=t[r+1][c]
3.t[r][c]+=t[r+1][c+1]

進(jìn)入題庫(kù)練習(xí)

5.判斷題好的算法在很大程度上取決于問(wèn)題中數(shù)據(jù)所采用的數(shù)據(jù)結(jié)構(gòu)。

參考答案：錯(cuò)誤

進(jìn)入題庫(kù)練習(xí)

6.問(wèn)答題證明等式gcd（m，n）=gcd（n，m mod n）對(duì)每一對(duì)正整數(shù)m，n都成立.

參考答案：

進(jìn)入題庫(kù)練習(xí)

7.問(wèn)答題用回溯法解布線問(wèn)題時(shí)，求最優(yōu)解的主要程序段如下：如果布線區(qū)域劃分為n×m的方格陣列，擴(kuò)展每個(gè)結(jié)點(diǎn)需O（1）的時(shí)間，L為最短布線路徑的長(zhǎng)度，則算法共耗時(shí)（O（mn）），構(gòu)造相應(yīng)的最短距離需要（O（L））時(shí)間。

參考答案：

進(jìn)入題庫(kù)練習(xí)

8 回溯法搜索狀態(tài)空間樹是按照（）的順序。

點(diǎn)擊查看答案

9.問(wèn)答題分式化簡(jiǎn)。設(shè)計(jì)算法，將一個(gè)給定的真分?jǐn)?shù)化簡(jiǎn)為最簡(jiǎn)分?jǐn)?shù)形式。例如，將6/8化簡(jiǎn)為3/4。

參考答案：

進(jìn)入題庫(kù)練習(xí)

10 以下字符串中，是回文字符串的是（）。

點(diǎn)擊查看答案