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

一、簡答題（1 題 4 分，2 題 4 分，3 題 6 分，共 14 分） 1. 什么是算法？什么是程序？。 2. 算法的特點是什么？ 3. 給出算法復(fù)雜度計量符號 O 和的定義。 二、算法復(fù)雜度計算（10分） 已知某算法耗時為 T（n） ，且滿足如下遞歸方程 (1)1 ( ) 2 ( / 2)( )1 On T n T nO nn 試計算該算法的時間復(fù)雜度 T（n） 。 三、對于分治法，試解答： （1、2題各5分，3題8分,共18分） 1. 分治法的基本思想什么？ 2. 試給出分治法的一般算法設(shè)計模式，用偽代碼描述或詳述解題步驟。 3. 設(shè) n 個不同的整數(shù)排好序后存于 T0n-1中。若存在一個下標 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 使得對所有 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. 常見的兩種分支限界法：隊列式(FIFO)分支限界法-將活結(jié)點表組織成一個隊列，按照 先進先出（FIFO）原則選取下一個結(jié)點為擴展結(jié)點；優(yōu)先隊列式分支限界法-將活結(jié)點表組 織成一個優(yōu)先隊列，按照規(guī)定的優(yōu)先級選取優(yōu)先級最高的結(jié)點成為當(dāng)前擴展結(jié)點。 3. 解：按照單位效益從大到小依次排列這 7 個物品為：FBGDECA。將它們的序號分別記 為 17。則可生產(chǎn)如下的狀態(tài)空間搜索樹。其中各個節(jié)點處的限界函數(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 時達到最大效益，為 170，重量為 150。 a a a b a a c Q1 1 1x