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

問(wèn)答題
設(shè)計(jì)算法，在數(shù)組r[n]中刪除重復(fù)的元素，要求移動(dòng)元素的次數(shù)較少并使剩余元素間的相對(duì)次序保持不變。
答案：
問(wèn)答題
一個(gè)旅行者要駕車從A地到B地，A、B兩地間距離為s。A、B兩地之間有n個(gè)加油站，已知第i個(gè)加油站離起點(diǎn)A的距離為di公里，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)的油站為止，在該油站再加...
問(wèn)答題
請(qǐng)寫出用回溯法解裝載問(wèn)題的函數(shù)。裝載問(wèn)題：有一批共n個(gè)集裝箱要裝上2艘載重量分別為c1和c2的輪船，其中集裝箱i的重量為wi。裝載問(wèn)題要求確定是否有一個(gè)合理的裝載方案可將這n個(gè)集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。
答案：
問(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]
判斷題
好的算法在很大程度上取決于問(wèn)題中數(shù)據(jù)所采用的數(shù)據(jù)結(jié)構(gòu)。
答案：錯(cuò)誤
問(wèn)答題
證明等式gcd（m，n）=gcd（n，m mod n）對(duì)每一對(duì)正整數(shù)m，n都成立.
答案：
問(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í)間。
答案：
單項(xiàng)選擇題
回溯法搜索狀態(tài)空間樹(shù)是按照（）的順序。
A.中序遍歷
B.廣度優(yōu)先遍歷
C.深度優(yōu)先遍歷
D.層次優(yōu)先遍歷
問(wèn)答題
分式化簡(jiǎn)。設(shè)計(jì)算法，將一個(gè)給定的真分?jǐn)?shù)化簡(jiǎn)為最簡(jiǎn)分?jǐn)?shù)形式。例如，將6/8化簡(jiǎn)為3/4。
答案：
多項(xiàng)選擇題
以下字符串中，是回文字符串的是（）。
A.abcba
B.12321
C.1221
D.abcdef

首頁(yè)

題庫(kù)

網(wǎng)課

在線?？?/h3>

桌面端

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

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

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

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

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

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

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

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

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

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

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

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

證明等式gcd（m，n）=gcd（n，m mod n）對(duì)每一對(duì)正整數(shù)m，n都成立.

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

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

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

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

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

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

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

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