山東科技大學(xué)算法復(fù)習(xí)題.pdf

一、簡(jiǎn)答題（1 題 4 分，2 題 4 分，3 題 6 分，共 14 分） 1. 什么是算法？什么是程序？。 2. 算法的特點(diǎn)是什么？ 3. 給出算法復(fù)雜度計(jì)量符號(hào) O 和的定義。 二、算法復(fù)雜度計(jì)算（10分） 已知某算法耗時(shí)為 T（n） ，且滿足如下遞歸方程 (1)1 ( ) 2 ( / 2)( )1 On T n T nO nn 試計(jì)算該算法的時(shí)間復(fù)雜度 T（n） 。 三、對(duì)于分治法，試解答： （1、2題各5分，3題8分,共18分） 1. 分治法的基本思想什么？ 2. 試給出分治法的一般算法設(shè)計(jì)模式，用偽代碼描述或詳述解題步驟。 3. 設(shè) n 個(gè)不同的整數(shù)排好序后存于 T0n-1中。若存在一個(gè)下標(biāo) i，0i int Search(Type a,int n) Int l=0; int r=n-1; while (r = l) int m = (l+r)/2; if (m = = am) return m; if (m int BinarySearch(Type a, const Type if (x = am) return m; if (x c) break; xi=1; c-=wi; if (in) output(x); else for (int i=0;in) output(x); else for (int i=t;i int Search(Type a,int n) Int l=0; int r=n-1; while (r = l) int m = (l+r)/2; if (m = = am) return m; if (mn) output(x); else for (int i=0;in) output(x); else for (int i=t;i0，存在正數(shù)和 n0 0 使得對(duì)所有 n n0 有：0 f(n) int BinarySearch(Type a, const Type if (x = am) return m; if (x n) output(x); else for (int i=f(n,t);i0) if (f(n,t)=g(n,t) for (int i=f(n,t);i=g(n,t);i+) xt=h(i); if (constraint(t) else t+; else t-; 2. 常見的兩種分支限界法：隊(duì)列式(FIFO)分支限界法-將活結(jié)點(diǎn)表組織成一個(gè)隊(duì)列，按照 先進(jìn)先出（FIFO）原則選取下一個(gè)結(jié)點(diǎn)為擴(kuò)展結(jié)點(diǎn)；優(yōu)先隊(duì)列式分支限界法-將活結(jié)點(diǎn)表組 織成一個(gè)優(yōu)先隊(duì)列，按照規(guī)定的優(yōu)先級(jí)選取優(yōu)先級(jí)最高的結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。 3. 解：按照單位效益從大到小依次排列這 7 個(gè)物品為：FBGDECA。將它們的序號(hào)分別記 為 17。則可生產(chǎn)如下的狀態(tài)空間搜索樹。其中各個(gè)節(jié)點(diǎn)處的限界函數(shù)值通過如下方式求 得： a 150 115 4040305035190.625 40 7 (1,1,1,1,0,0) 8 b. 150 115 4040305030177.5 60 7 (1,1,1,1,0,0) 12 c40403050 10170 (1,1,1,1,0,0,1) d. 150 105 4040303530167.5 60 3 (1,1,1,0,1,0) 4 e. 150 130 4040503530175 60 1 (1,1,0,1,1,0) 3 f. 150130 4040503510170.71 35 4 (1,1,0,1,1,0, ) 7 g.40405030160 (1,1,0,1,0,1,0) h. 150 140 40403530 10146.85 35 2 (1,1,0,0,1,1, ) 7 i. 150 125 4030503530167.5 60 5 (1,0,1,1,1,0) 12 j. 150 145 4030503530157.5 60 1 (0,1,1,1,1,0) 12 在 Q1處獲得該問題的最優(yōu)解為(1,1,1,1,0,0,1)，背包效益為 170。即在背包中裝入物品 F、 B、G、D、A 時(shí)達(dá)到最大效益，為 170，重量為 150。 a a a b a a c Q1 1 1x