2010年作業(yè)題(第1、2章)

1、作業(yè)題講解,作業(yè)15: 試用ADL語(yǔ)言編寫一個(gè)算法，判斷任一整數(shù) n 是否為素?cái)?shù),算法 S (n. flag) /*判斷整數(shù)n是否為素?cái)?shù)，將結(jié)果保存到變量flag*/ S1n1？ IF (n1) THEN (flagfalse. RETURN.) S2初始化 i2. flagtrue. S3求余判斷 WHILE (in-1) DO (IF (n MOD i)=0 THEN (flagfalse. RETURN.) ii+1.) 該算法的時(shí)間復(fù)雜性最好為：O(1) 最壞情況為：O(n),算法 S (n. flag) /*判斷整數(shù)n是否為素?cái)?shù)，將結(jié)果保存到變量flag*/ S1n1？ IF (n1

2、) THEN (flagfalse. RETURN.) S2初始化 i2. flagtrue. S3求余判斷 WHILE (i n/2 ) DO (IF (n MOD i)=0 THEN (flagfalse. RETURN.) ii+1.) 該算法的時(shí)間復(fù)雜性最好為：O(1) 最壞情況為：O(n),算法 S (n. flag) /*判斷整數(shù)n是否為素?cái)?shù)，將結(jié)果保存到變量flag*/ S1n1？ IF (n1) THEN (flagfalse. RETURN.) S2初始化 i2. flagtrue. S3求余判斷 WHILE (i n 1/2 ) DO (IF (n MOD i)=0 THE

3、N (flagfalse. RETURN.) ii+1.) 該算法的時(shí)間復(fù)雜性最好為：O(1) 最壞情況為：O(n1/2),作業(yè)111,證明對(duì)正整數(shù)n3，算法BS的元素比較次數(shù)T（n）5n/3-2。 已知信息 T（n）= 0 n=1 1 n=2 T( n/2)+T(n/2 )+2 n2 數(shù)學(xué)歸納法證明 證明 n=3 時(shí)成立 假設(shè) n k 時(shí)都成立,證明 n= k時(shí)也成立,作業(yè)111,n=3 時(shí)， T(3)=T(1)+T(2)+2=3，5*3/3-2=3，命題成立。 假設(shè)n ，即k-1 所以有T( )5*( )/3-2, T( )5*( )/3-2 成立, .(2) 又知 k= + , (3)

4、由(1)(2)(3)，有 T(k) = T( )+T( )+2 5*( )/3-25*( )/3-2+2 = 5*( + )/3-2 = 5*k/3-2 綜上，命題得證。,2-1,編寫算法Reverse ( A , n)，將順序存儲(chǔ)的線性表A=( a1, a2, , an )轉(zhuǎn)換為A=( an, a2, a1)，要求轉(zhuǎn)換過程中用盡可能少的輔助空間。,2-1,只需從線性表的第一個(gè)數(shù)據(jù)元素開始，將第i個(gè)數(shù)據(jù)元素與第n-i+1個(gè)數(shù)據(jù)元素相交換即可。在這個(gè)過程中，i的變化范圍是1到 。這里只需要一個(gè)輔助空間temp.,2-1,算法Reverse（A，n . A） Reverse1.元素互換 FOR i

5、=1 TO DO ( temp Ai. Ai An-i+1. An-i+1 temp. ). ,2-8,設(shè)計(jì)一個(gè)算法，將鏈表的鏈接完全顛倒。,算法1：類似于習(xí)題2-1，將第i個(gè)與第n-i+1個(gè)結(jié)點(diǎn)的數(shù)據(jù)域互換。 算法2：遍歷鏈表的同時(shí)修改指針。 算法3：使用堆棧，實(shí)現(xiàn)單鏈表求逆。,2-8,算法 reverse ( head. head) /*將指針 head 所指向的鏈表倒置*/ RV1指針初始化 /q,p,r 分別指向三個(gè)連續(xù)的結(jié)點(diǎn) q NULL. p next(head). r next(p). RV2反轉(zhuǎn)鏈表 WHILE( rNULL ) DO ( next(p) q. /反轉(zhuǎn)結(jié)點(diǎn)p qp. /移動(dòng)3個(gè)指針 pr. r next(r). ) RV3最后一個(gè)結(jié)點(diǎn)的處理 next(p)q. next(head)p.,2-17,對(duì)于順序堆棧和鏈?zhǔn)蕉褩，分別編寫函數(shù)SelectItem（ Stack flag = true; while(!te