數據結構習題課1

1、2021/8/21數據結構習題數據結構習題 第第 1 章章吉林大學計算機科學與技術學院谷方明2021/8/22l感謝二班、三班的學委把作業(yè)按學號排序。這是一種積極的習慣。2021/8/23課堂練習課堂練習求下述計算f=1！+2！+3！+n！的算法的時間復雜性void factorsum(int n)2021/8/24參考答案參考答案l以乘法為基本運算l最壞時間復雜度為T(n)=n(n+1)/2，l漸近表示法O(n2) （或算法是n2 階的）2021/8/251-21-2l設數據的邏輯結構為L=(N,R)，其中，lN=a,b,c,d,elR=r,lr=,l請畫出對應的邏輯結構，說明是何種結構20

2、21/8/26l圖型結構：a有多個后繼，e有多個前驅參考答案參考答案aedbc2021/8/27作業(yè)情況作業(yè)情況l正確率：超過80%l用圓圈表示結點，用直線箭頭表示邊l結點名一般寫在圓圈內l有問題的畫法l無向邊l邊共用線l交叉：盡量避免2021/8/28作業(yè)作業(yè)1 14 4l題目描述：【3】【10分鐘】用反證法證明 是無理數。22021/8/29參考答案參考答案l假設 不是無理數，那么 一定是有理數，即存在p、q，使得 =p/q，p、q互質。整理得p2=2*q2 ，因此p是偶數。設p=2*k，則有q2=2*k2 ，因此q也是偶數。這與p、q互質矛盾。l因此 是無理數。22222021/8/21

3、0其它做法其它做法l有一種證法：p、q互質得到p2 、 q2互質。 由p2=2*q2 ，可得p2 、 q2有公約數q2 。（需要說明q不是1）l唯一分解定理：2班李百林l三種證法的同學：3班徐文峰（幾何法）。2021/8/211作業(yè)情況作業(yè)情況l正確率70%左右l有問題的說法l因為 不是有理數或找不到分數、循環(huán)小數表示l因為 是無理數？l（p,q）=2：改成p、q有公約數2l表示成p/q，p、q互為質數，q1或q0等等2212021/8/212作業(yè)作業(yè)1 15 5l題目描述 試用ADL語言編寫一個算法，判斷任一整數 n 是否為素數2021/8/213考察知識點考察知識點l用ADL描述算法l特殊

4、情況判斷l(xiāng)初始化l核心處理步驟l后處理l算法的正確性l證明很難，但驗證較容易。用邊界條件和特殊數據驗證，人工模擬算法執(zhí)行。l分析算法的效率2021/8/214參考答案參考答案1 1算法算法 S (n. flag) /*判斷整數判斷整數n是否為素數，將結果保存到變量是否為素數，將結果保存到變量flag*/S1n1 1？ IF (n1 1) THEN (flagfalse. RETURN.)S2初始化初始化 i2. flagtrue. S3求余判斷求余判斷 WHILE (in-1) DO (IF (n MOD i)=0 THEN (flagfalse. RETURN.) ii+1.) 2021/8

5、/215參考答案參考答案2 2算法算法 S (n. flag) /*判斷整數判斷整數n是否為素數，將結果保存到變量是否為素數，將結果保存到變量flag*/S1n1 1？ IF (n1 1) THEN (flagfalse. RETURN.)S2初始化初始化 i2. flagtrue. S3求余判斷求余判斷 WHILE (i n DIV 2 ) DO (IF (n MOD i)=0 THEN (flagfalse. RETURN.) ii+1.) 2021/8/216參考答案參考答案3 3算法算法 S (n. flag) /*判斷整數判斷整數n是否為素數，將結果保存到變量是否為素數，將結果保存到

6、變量flag*/S1n1 1？ IF (n1 1) THEN (flagfalse. RETURN.)S2初始化初始化 i2. flagtruetrue. S3求余判斷求余判斷 WHILE (i n 1/2 ) DO (IF (n MOD i)=0 THEN (flagfalse. RETURN.) ii+1.) 2021/8/217作業(yè)情況作業(yè)情況l正確率不到50%l有問題的做法l特殊情況沒有處理：1和2.l不理解程序語句？lFor處理：IF(n%i=0) THEN flag 0. ELSE 0. ELSE flag 1.1.l無返回值: RETURN.lFOR TO i DOlIF DO2

7、021/8/218用用ADLADL描述算法描述算法l輸入輸出參數的確定：臨時變量不是參數l符號“.”的應用l分隔輸入輸出參數l一條語句的結束；能判斷語句結束的問題可略去l符號“ ”的應用：標志算法結束l混雜C+語言lFOR i=2 TO n-1 STEP i+ DO l步驟說明有且精2021/8/2191-61-6l分析下面程序段的時間復雜性int s=0,i,j,k;for(i=0;i=n;i+)for(j=0;j=i;j+)for(k=0;kj;k+)s+;2021/8/220參考答案參考答案l以s+為基本運算l對每個i，分析(j,k)兩重循環(huán)的次數lj=0 循環(huán)次數為 0lj=1 循環(huán)次

8、數為 1llj=i 循環(huán)次數為 il因此對每個i，(j,k)二重循環(huán)的次數為i*(i+1)/2l總循環(huán)次數為sigma(i*(i+1)/2) i=0.nlT(n)=n*(n+1)*(n+2)/6，算法的階為O(n3)2021/8/221作業(yè)情況作業(yè)情況l正確率約60%l有分析步驟l直接給結果l有問題的做法l三重循環(huán)，所以O(n3)l推導出錯2021/8/2221-91-9l將下列算法時間復雜性O(n),O(2n),O(log2n),O(nlog2n),O(n5), O(n2+1),O(n3-n2) 按由低到高的順序排列。其中，n是輸入數據的規(guī)模。2021/8/223參考答案參考答案lO(log

9、2n) O(n) O(nlog2n) lO(n2+1) O(n3-n2) O(n5) 22021/8/2262021/8/227考察知識點考察知識點l數學歸納法證明l歸納基礎 n = ? 時，*，命題成立。l歸納假設步驟 假設n=k是，有*， 當n=k+1時，推出命題也成立l用數學歸納法證明l第一數學歸納法 (假設n=k，往推n=k+1)l第二數學歸納法(假設n=k，往推n=k+1，強數學歸納法)l兩者等價2021/8/228l本題的數學歸納法證明思路l證明 n=3 時成立l假設 n =k 時都成立,證明 n= k+1時也成立l思路可以不寫出來2021/8/229參考答案參考答案ln=3 時，

10、時， T(3)=T(1)+T(2)+2=3，5*3/3-2=3，命題成立。，命題成立。l假設假設n ， 即即k 所以有所以有T( )55* *( )/3-2,( )/3-2, T( )55* *( ( )/3-2 )/3-2 成立成立, .(2) 又知又知 k+1= +k+1= + , (3) 由由(1)(2)(3)， T(k+1)=T( )+T( )+2, 5 5* * /3-2 /3-255* * /3-2+2 /3-2+2 = 5 = 5* *( + )/3-2( + )/3-2 = 5 = 5* *(k+1)/3-2 (k+1)/3-2 綜上，命題得證。綜上，命題得證。(k+1)/2(

11、k+1)/2(k+1)/2(k+1)/2 (k+1)/2(k+1)/2(k+1)/2(k+1)/2(k+1)/2(k+1)/2(k+1)/2(k+1)/2(k+1)/2(k+1)/2 (k+1)/2(k+1)/2(k+1)/2(k+1)/22021/8/230作業(yè)情況作業(yè)情況l正確率約50%l由3=n=k，往推n=2*k，n=2*k+1也正確l分n=2*k，n=2*k+1討論 k+1 = l有問題的做法l弱假設：設n=k時成立l設n=k時成立，即 T(k)=5*k/3-2l利用(3*n/2 -2 )結論l由(1)、(2)、(3)直接得到，不用數學歸納法l經分析得，T(n)=lognl往年：通過

12、觀察可知 T(n+1)=T(n)+1 ?2021/8/2311-121-12l給出算法BS的非遞歸算法，并說明算法最多需要多大的輔助空間。2021/8/232算法算法 BS (A,s,e. fmax,fmin ) /*求數組求數組A的的s到到e中的元素的最大最小值，用棧去遞歸，確保中的元素的最大最小值，用棧去遞歸，確保s=e*/B1初始化，創(chuàng)建輔助分解棧初始化，創(chuàng)建輔助分解棧 p 和合并棧和合并棧 t CREATS(p). CREATS(t). p p (s,e,e).(s,e,e).B2迭代迭代 WHILE (NOT StackEmpty(s) DO ( (L, R ,B)(L, R ,B)

13、 p .p . IF (L = R) THEN ( max minmin AL .AL . WHILE(NOT StackEmpty(t) AND R (StackTop(t) ) + 1 =L AND B (StackTop(t) ) =B ) ( (left,right,bound,fm,fn)(left,right,bound,fm,fn) t t . . L left. IF (mafn) THEN mi fm.fm. ) t t (l,r,ma,mi(l,r,ma,mi) . )2021/8/233ELSE( mid (L+R) div 2.(L+R) div 2. p p (mid

14、+1,R,(mid+1,R,B B). ). p p (L,mid,(L,mid,R R).). ) B3結果結果 (s,e,e,fmax,fmin) (s,e,e,fmax,fmin) t t . .2021/8/234參考答案參考答案l輔助空間l問題分解棧P: ( log2n + 1) *2l問題合并棧T: 2*42021/8/235lvoid bs(int a,int s,int e,int& fmin,int& fmax)l/* 使用倍增法，求最大最小*/llint len=1;llwhile(s+len=e)l l for(i=s;i+2*len-1ai+len) swap(ai,ai+len);l if(ai+len-1ai+2*len-1) swap(ai+l