【習(xí)題課】第1-3章課件

第1－3章習(xí)題.第1－3章習(xí)題.1作業(yè)1－5

試用ADL語言編寫一個算法，判斷任一整數(shù)n是否為素數(shù)。.作業(yè)1－5試用ADL語言編寫一個算法，判斷任一整數(shù)n2考察知識點判斷素數(shù)素數(shù)——大于1的自然數(shù)中，除了1和此整數(shù)自身外，不能被其他自然數(shù)整除的數(shù)。判斷：對于指定的n，如果[2,n-1]內(nèi)的整數(shù)都不能整除n，則n為素數(shù)。ADL語言寫算法算法證明很難，可以使用邊界條件和特殊數(shù)據(jù)，人工模擬算法執(zhí)行過程。.考察知識點判斷素數(shù).3完成情況思想——基本正確，對素數(shù)定義的理解：1？算法——特殊情況處理：n1？算法輸出；ADL語言的使用：運算符號：MOD(模)，DIV(除數(shù))，/(除)；

，（取整）；％？sqrt?fabs()?

輸入輸出參數(shù)：設(shè)置返回值；中間用“.”分隔；條件語句：ifthenelse；

fori＝1tonstep1(i=i+1?)

賦值語句：.完成情況思想——基本正確，對素數(shù)定義的理解：1？.4參考答案算法S(n.flag)/*判斷整數(shù)n是否為素數(shù)，將結(jié)果保存到變量flag*/S1[n≤1？]IF(n≤1)THEN(flag←false.RETURN.)S2[初始化]i←2.flag←true.S3[求余判斷]WHILE(i≤n-1)DO(IF(nMODi)=0THEN(flag←false.RETURN.)i←i+1.)▌.參考答案算法S(n.flag).5正確性驗證：假定n＝7，模擬執(zhí)行過程，對i＝2，3，4，5，6時，分別判斷(7modi)的取值是否為0。改進(jìn)：n-1？——n/2、n1/2n=ab,a≥2,b≤n/2,…a,…b,…n/2a≤n1/2,b≥n1/2,…a,…n1/2,…b…

.正確性驗證：.6參考答案2算法S(n.flag)/*判斷整數(shù)n是否為素數(shù)，將結(jié)果保存到變量flag*/S1[n≤1？]IF(n≤1)THEN(flag←false.RETURN.)S2[初始化]i←2.flag←true.S3[求余判斷]WHILE(i≤

n/2)DO(IF(nMODi)=0THEN(flag←false.RETURN.)i←i+1.)▌.參考答案2算法S(n.flag).7作業(yè)1-8若A(n)=amnm+…+a1n+a0是關(guān)于n的m次多項式，證明A(n)=O(nm)。設(shè)f(n)和g(n)是正整數(shù)集到正實數(shù)集的函數(shù)，稱f(n)是O(g(n))當(dāng)且僅當(dāng)存在正常數(shù)C和n0，使得對任意的nn0，有f(n)Cg(n)。完成情況：令n0＝1，C＝am+…+a1+a0，

amnm+…+a1n+a0Cnm

注意：當(dāng)ai0時，ainiainm不一定成立。.作業(yè)1-8若A(n)=amnm+…+a1n+a0是關(guān)于n的m8證明：對于所有的n≥1，有：

A(n)=i=0,…,maini≤i=0,…,m|ai|ni≤

nmi=0,…,m|ai|ni-m

≤

nmi=0,…,m|ai|

令C＝i=0,…,m|ai|，有A(n)≤

Cnm

所以，

A(n)=O(nm)。參考答案.證明：對于所有的n≥1，有：參考答案.9作業(yè)1－11

證明對正整數(shù)n≥3，算法BS的元素比較次數(shù)T(n)≤5n/3-2。已知：0n=1T(n)=1n=2T(n/2)+T(n/2)+2n>2.作業(yè)1－11證明對正整數(shù)n≥3，算法BS的元素比較次數(shù)T(10考察知識點：數(shù)學(xué)歸納法基礎(chǔ)歸納：n=c(初值)時，命題是正確的；歸納步驟：如果n＝k－1時，命題成立，則n＝k時，命題也成立。完成情況：利用結(jié)論T(n)＝3n/2－2，需要注意前提條件——當(dāng)n是2的冪時；由n=k反推n＝k-1時的情況。.考察知識點：數(shù)學(xué)歸納法.110n=1

T(n)=1n=2

T(n/2)+T(n/2)+2n>2n=3時，T(3)=T(1)+T(2)+2=3，53/3-2=3，命題成立。假設(shè)n<=k時命題成立，需證明n=k+1時成立。

當(dāng)k≥3時，有(k+1)>(k+1)/2≥(k+1)/2

，即k≥(k+1)/2≥(k+1)/2

所以：T((k+1)/2)≤5((k+1)/2)/3-2,

(1)

T((k+1)/2)≤5((k+1)/2)/3-2

(2)T(k+1)=T((k+1)/2)+T((k+1)/2)+2≤[5((k+1)/2)/3-2]＋[5((k+1)/2)/3-2]+2=5((k+1)/2+(k+1)/2)/3-2//k＋1=(k+1)/2+(k+1)/2

=5(k+1)/3-2綜上，命題得證。.012作業(yè)1－12給出算法BS的非遞歸算法，并說明算法最多需要多大的輔助空間。.作業(yè)1－12給出算法BS的非遞歸算法，并說明算法最多需要多大13算法SM(A,n.max,min)

SM1[初始化]max←min←A[1].

SM2[比較]

FORI=2TOnDO

//求最大和最小元素

(IFA[I]>maxTHENmax←A[I].IFA[I]<minTHENmin←A[I]).

▌.算法SM(A,n.max,min).14BS算法算法BS（A，i，j.fmax，fmin）//在數(shù)組A的第i個元素到第j個元素之間尋找最大和最//小元素，已知ij。BS1[遞歸出口]IFi=jTHEN（fmax←fmin←A[i].RETURN.）IFi=j1THEN

（IFA[i]<A[j]THEN（fmax←A[j].fmin←A[i]）. ELSE（fmax←A[i].fmin←A[j]）.RETURN）..BS算法算法BS（A，i，j.fmax，fmin）15BS2[取中值] mid←(i+j)/2BS3[遞歸調(diào)用]BS（A，i，mid.gmax，gmin）

BS（A，mid+1，j.hmax，hmin）.BS4[合并] fmax←max{gmax，hmax}. fmin←min{gmin，hmin}.■

.BS2[取中值].16完成情況做的很少SM方法；（沒有體現(xiàn)分治思想）依次對比鄰近的兩個元素，找到較大較小者，不斷更新全局最大最小值；依次對比，用數(shù)組存放每對的最大最小值；兩個棧分別存放當(dāng)前起始和終止元素下標(biāo)；一個棧存儲中間值，另一個存放最大最小值。（沒法確定起始和終止元素的下標(biāo)）.完成情況做的很少.17輔助空間：因為采用某種特殊結(jié)構(gòu)，而增加占用的空間；占用空間：算法運行所需要的空間；方法3：數(shù)組；方法4：棧.輔助空間：因為采用某種特殊結(jié)構(gòu)，而增加占用的空間；.18方法4基本思想：創(chuàng)建兩個棧，一個存放起始元素的下標(biāo)，一個存放終止元素的下標(biāo)。每次從棧中彈出一對下標(biāo)，若兩者相等或相差為1，則找到最大最小值，否則找到中間下標(biāo)，形成兩對新的下標(biāo)，壓入棧內(nèi)。.方法4基本思想：.19示例數(shù)組A=[3,9,21,15,8,19]16初始：壓入起始和結(jié)束下標(biāo)1和6；循環(huán)：彈出元素1和6；兩者不相等、相差不為1；取中值(1+6)/2=3；形成兩對新的下標(biāo)，(1,3)和(4,6);壓入棧；彈出4和6，兩者不相等、相差不為1；取中值(4+6)/2=5；形成兩對新的下標(biāo)，(4,5)和(6,6);壓入棧內(nèi)；1346134566.示例數(shù)組A=[3,9,21,15,8,19]16初始：壓入起20A=[3,9,21,15,8,19]134566彈出(6,6)，相等，元素值為19，則fmaxmax{fmax,19}=19，fminmin{fmin,19}=19；彈出(4,5)，相差為1，元素值為15和8，則fmaxmax{19,15,8}=19，fminmin{19,15,8}=8；13.A=[3,9,21,15,8,19]134566彈出(6,621參考答案算法f(A,i,j.fmax,fmin)f1.[初始化]fmaxfminA[i].Lstack<int>left;Lstack<int>right;//存儲起始和終止下標(biāo)left.push(i).right.push(j).f2.[求最大、最小值]While(!left.IsEmpty())DO(lleft.pop().rright.pop().

.參考答案算法f(A,i,j.fmax,fmin).22IFl=rTHEN//相等(fmaxmax{fmax,A[l]}.fminmin{fmin,A[l]}.)ELSE(IFr-l=1//相差為1THEN(fmaxmax{fmax,A[l],A[r]}.fminmin{fmin,A[l],A[r]}.)ELSE(mid=(i+j)/2.left.push(l).left.push(mid+1).right.push(mid).Right.push(r).))).IFl=rTHEN//23輔助空間：棧nn/2n/2n/4n/4…1log2n.輔助空間：棧nn/2n/2n/4n/4…1log2n.24作業(yè)2－1編寫算法Reverse(A[],n)，將順序存儲的線性表A=(a1,a2,…,an)轉(zhuǎn)換為A=(an,…,a2,a1)，要求轉(zhuǎn)換過程中使用盡可能少的輔助空間。關(guān)鍵點：限制輔助空間的使用如果沒有這個限制，則可以有多種方法：輔助數(shù)組；雙下標(biāo)同時向中間移動.作業(yè)2－1編寫算法Reverse(A[],n)，將順25分析只需從線性表的第一個數(shù)據(jù)元素開始，將第i個數(shù)據(jù)元素與第n-i+1個數(shù)據(jù)元素相交換即可。i的變化范圍是1到n/2。a1a2…an-1ananan-1…a2a11+n2+(n-1)…(n-1)+2n+1.分析只需從線性表的第一個數(shù)據(jù)元素開始，將第i個數(shù)據(jù)元素與第n26參考答案算法Reverse（A，n.A）Reverse1.[元素互換]FORi=1TOn/2DOA[i]←→A[n-i+1].▌.參考答案算法Reverse（A，n.A）.27作業(yè)2-8在單鏈表類SLIST中添加一個成員函數(shù)，將單鏈表中元素的次序完全顛倒。.作業(yè)2-8在單鏈表類SLIST中添加一個成員函數(shù)，將單鏈表中28利用堆棧；從表頭刪除，插入表尾；(不推薦)換數(shù)據(jù)域的取值，p1和p2向中間移動，更換數(shù)據(jù)域的取值?！環(huán)eadp1p2.利用堆棧；…h(huán)eadp1p2.29方法4思想：從左向右，依次更換鄰近結(jié)點的指針方向。初始設(shè)置，第一個元素需要被放到表尾，指向空指針，p1=null，p2=next(head)//第一個元素headp22p3345p1nullp11p26P3next(p2)next(P2)P1. //反轉(zhuǎn)P1P2.P2P3..方法4思想：從左向右，依次更換鄰近結(jié)點的指針方向。headp30參考答案算法Reverse(head.head)/*將指針head所指向的鏈表倒置*/RV1[空鏈表和1個節(jié)點鏈表]IF(next(head)=NULL)RETURN.RV2[指針初始化] //P1,P2分別指向兩個連續(xù)的節(jié)點

P1NULL. P2next(head)..參考答案算法Reverse(head.head).31RV3[反轉(zhuǎn)鏈表] WHILE(P2≠NULL)DO (P3next(p2) next(P2)P1. //反轉(zhuǎn)節(jié)點指針

P1P2.P2P3.//移動3個指針 ）RV4[head指向反轉(zhuǎn)鏈表]

next(head)P1.

▌p1p2.RV3[反轉(zhuǎn)鏈表]p1p2.32作業(yè)2－11已知線性表中的元素以data值遞增有序排列，并以單鏈表做存儲結(jié)構(gòu)。試寫一高效的算法，刪除表中所有值大于mink且小于maxk的元素，同時釋放被刪結(jié)點空間，并分析算法的時間復(fù)雜度。鏈表是有序的：找到區(qū)間特殊情況的處理：表為空，元素都大于maxk(第一個元素大于maxk)；元素都小于mink(最后一個元素小于mink)。.作業(yè)2－11已知線性表中的元素以data值遞增有序排列，并以33主要思想：找到大于mink的第一個元素，刪除操作，直至元素大于maxk。時間復(fù)雜度：比較為基本運算最好：空，元素都大于maxk（找不到）//O(1)最壞：元素都小于mink（找不到），

元素都小于maxk，O(n)；.主要思想：.34算法LD(L,mink,maxk)LD1.[特殊情況]IF

minkmaxkTHEN(RETURN.)LD2.[初始化]p←head.prev←p.p←next(p)LD3.[找]WHILE(pNULLANDdata(p)<maxk)DO(IF(data(p)mink)THEN(prev←p.p←next(p))//向后移動ELSE(next(prev)←next(p).q←p.p←next(p).AVAILq.))//刪除qRETURN.prevheadpPprevp.算法LD(L,mink,maxk)LD1.[特殊情況35作業(yè)2－17對于順序堆棧和鏈?zhǔn)蕉褩，分別編寫函數(shù)SelectItem(Stack&s,intn)，要求在堆棧中查找元素n在棧中第一次出現(xiàn)的位置，并將該位置元素移至棧頂，同時其他元素次序不變。（注意：用int匹配堆棧的模板）.作業(yè)2－17對于順序堆棧和鏈?zhǔn)蕉褩，分別編寫函數(shù)Selec36基本思想：取棧頂元素，若不匹配，則進(jìn)行彈棧操作；找到（或無法找到）后恢復(fù)原來的元素次序。關(guān)鍵點：記錄彈出的順序，后彈出的元素能夠先被壓回原來的棧，因此需要使用一個輔助堆棧。.基本思想：.37示例105112shelpStack5173n=515112105173751511210377351.示例105112shelpStack5173n=51511238參考答案intSelectItem(Stack<int>&s,intn){AStack<int>temp(100);//順序堆棧，輔助棧

//LStack<int>temp;//鏈?zhǔn)蕉褩?/p>

boolflag=false;//是否存在元素nintloc=0;//記錄n所在的位置

while(!s.isEmpty()&&s.Peek()!=n

){temp.Push(s.Pop());loc++;}棧非空且當(dāng)前元素不等于n.參考答案intSelectItem(Stack<int>39if(!s.isEmpty()){s.Pop();flag=true;}//彈出nwhile(!temp.isEmpty())//將輔助棧中元素壓入原棧

{s.Push(temp.Pop());}if(flag)thens.Push(n)；

elseloc=-1;returnloc;}因為找到元素而跳出循環(huán).if(!s.isEmpty())因為找到元素40作業(yè)2－25編寫并實現(xiàn)雙端隊列類，雙端隊列是可進(jìn)行如下操作的線性表。(1)push(item)－－item插入到隊列的前端；(2)pop(item)－－刪除前端元素且賦給item；(3)inject(item)－－item插入尾端；(4)eject(item)－－刪除尾端元素且賦給item.作業(yè)2－25編寫并實現(xiàn)雙端隊列類，雙端隊列是可進(jìn)行如下操作的41結(jié)點結(jié)構(gòu)SLNode：數(shù)據(jù)域和指針域；類成員：隊首和隊尾的SLNode類型指針、指示元素個數(shù)的整型變量；Push(item插入隊列前端)

若空，則加入一個以item為數(shù)據(jù)域的結(jié)點，元素個數(shù)為1；否則，temp記錄原隊首指針front；

創(chuàng)建以item為數(shù)據(jù)域的新結(jié)點，作為新的隊首，賦值給front；front的指針域指向temp，元素個數(shù)加1。.結(jié)點結(jié)構(gòu)SLNode：數(shù)據(jù)域和指針域；.42Pop(刪除前端元素，并賦值item)若空，則錯誤；否則，temp記錄原隊首指針front；

隊首后移，即frontnext(front)；

返回temp的數(shù)據(jù)域；

刪除temp結(jié)點，元素個數(shù)減1；

若大小為零，則隊尾指針rear賦值為NULL。.Pop(刪除前端元素，并賦值item).43Inject(item插入隊尾)若空，則加入一個以item為數(shù)據(jù)域的結(jié)點，元素個數(shù)為1；否則，創(chuàng)建以item為數(shù)據(jù)域的新結(jié)點temp，作為新的隊尾，即next(rear)temp；隊尾指針后移，即rearnext(rear);元素個數(shù)加1。.Inject(item插入隊尾).44Eject(刪除隊尾元素并賦值給item)若空，則出錯；否則，

找到隊尾指針的前驅(qū)指針tempfront.IF(temprear)THEN(WHILE(next(temp)rear)DO(tempnext(temp))隊尾指針更新，即reartemp，

要刪除結(jié)點是next(temp)，返回數(shù)據(jù)域，刪除結(jié)點，元素個數(shù)減1。

若大小為零，front和rear賦值為NULL。.Eject(刪除隊尾元素并賦值給item).45作業(yè)3－10設(shè)稀疏矩陣Mmn中有t個非零元素，用三元組表的方式存儲.請設(shè)計一個算法，計算矩陣M的轉(zhuǎn)置矩陣N，且算法的時間復(fù)雜性為O(n+t).注意，書中給出的算法的復(fù)雜性為O(nt)。.作業(yè)3－10設(shè)稀疏矩陣Mmn中有t個非零元素，用三元組表的46M=500001002000000-300-605N=50100-3000000200-6000050050a[0]1010a[1]1220a[2]30-30a[3]32-60a[4]335a[5]0050b[0]0110b[1]03-30b[2]2120b[3]23-60b[4]335b[5]算法的關(guān)鍵是求出a中元素在b中的位置.M=50000N=501047Bindex＝0；FORj=0TOn－1DO

FORk=0TOt－1DOIFcol(A[k])=jThen (row(B[Bindex])=j. col(B[Bindex])=row(A[k]). value(B[Bindex])=Value(A[k]).

Bindex++）a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-30j=0,k=0,a[0],列坐標(biāo)=0；存儲j=0;k=1;a[1],列坐標(biāo)=0；存儲j=0;k=2;a[2],列坐標(biāo)=2；j=0;k=3;a[3],列坐標(biāo)=0；存儲j=0;k=4;j=0;k=5;j=1;k=0005030-301010.Bindex＝0；a[0]0050212001103352348a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-30005030-301010j=1,k=0,a[0],列坐標(biāo)=0j；j=1,k=1;列坐標(biāo)1j=1,k=2;j=1,k=3;j=1,k=4;j=1,k=5;j=2,k=0；j=2,k=1；j=2,k=2，列坐標(biāo)=2=jFORj=0TOn－1DO

FORk=0TOt－1DOIFcol(A[k])=jThen2201.a[0]00502120011033523-6003-30049005030-30101033532-601220a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-30b[2]a[x]b[y]?y=列坐標(biāo)小于col(a[x])的元素個數(shù)+

列坐標(biāo)等于col(a[x])且在a[x]之前的元素個數(shù).005030-30101033532-601220a[0]050a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-30基本思想：

數(shù)組num存儲a中每列非零元素個數(shù)；數(shù)組pos存儲a中每列第一個非零元素在b的三元組表中的位置；

302101230123num0335pos.a[0]00502120011033523-6003-30基51算法:TRANSPOSE(A.B)TP1[初始化]

n←Rows(B)←Cols(A).//B的行數(shù)等于A的列數(shù)，B的列數(shù)等于A的行數(shù)

Cols(B)←Rows(A).

t←Count(B)←Count(A).//B中非0元素的個數(shù)等于A中非0元素的個數(shù)TP2[定義數(shù)組num]

FORi←0TOn-1DO

num[i]←0.

FORi←0TOt-1DO（

j←col(A

[i]). num[j]←num[j]+1.）//A中每列非零元素個數(shù)

pos[0]

←0//定義數(shù)組pos

FORi←1TOn-1DO(pos[i]←pos[i-1]+num[i-1]).算法:TRANSPOSE(A.B).52a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-3003102231num00132335pos005030-30101033532-601220b[0]b[1]b[2]b[3]b[4]b[5].a[0]00502120011033523-6003-30053TP3[處理三元組表]FORi←0TOt-1DO(p←col(A[i]).//列坐標(biāo)k←pos[p].//該列坐標(biāo)的元素在b中的位置col(B[k])←row(A[i]).row(B[k])←col(A[i]).val(B[k])←val(A[i]).

pos[p]←pos[p]+1).a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-300335pos0050.TP3[處理三元組表]a[0]00502120011033554TP3[處理三元組表]FORi←0TOt-1DO(p←col(A[i]).k←pos[p].col(B[k])←row(A[i]).row(B[k])←col(A[i]).val(B[k])←val(A[i]).pos[p]←pos[p]+1).a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-301335pos00501010.TP3[處理三元組表]a[0]00502120011033555TP3[處理三元組表]FORi←0TOt-1DO(p←col(A[i]).k←pos[p].col(B[k])←row(A[i]).row(B[k])←col(A[i]).val(B[k])←val(A[i]).pos[p]←pos[p]+1).a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-302335pos005010101220.TP3[處理三元組表]a[0]00502120011033556TP3[處理三元組表]FORi←0TOt-1DO(p←col(A[i]).k←pos[p].col(B[k])←row(A[i]).row(B[k])←col(A[i]).val(B[k])←val(A[i]).pos[p]←pos[p]+1).a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-302345pos005030-3010101220.TP3[處理三元組表]a[0]00502120011033557TP3[處理三元組表]FORi←0TOt-1DO(p←col(A[i]).k←pos[p].col(B[k])←row(A[i]).row(B[k])←col(A[i]).val(B[k])←val(A[i]).pos[p]←pos[p]+1).a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-303345pos005030-30101032-601220.TP3[處理三元組表]a[0]00502120011033558TP3[處理三元組表]FORi←0TOt-1DO(p←col(A[i]).k←pos[p].col(B[k])←row(A[i]).row(B[k])←col(A[i]).val(B[k])←val(A[i]).pos[p]←pos[p]+1).a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-303355pos005030-30101033532-601220.TP3[處理三元組表]a[0]00502120011033559TP3[處理三元組表]FORi←0TOt-1DO(p←col(A[i]).k←pos[p].col(B[k])←row(A[i]).row(B[k])←col(A[i]).val(B[k])←val(A[i]).pos[p]←pos[p]+1).a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-303356pos005030-30101033532-601220.TP3[處理三元組表]a[0]00502120011033560f(j)abcabcacabca-1-1-10123-10123作業(yè)2-15.f(j)abcabca61abcaabbabcab…..abcaabb62第1－3章習(xí)題.第1－3章習(xí)題.63作業(yè)1－5

試用ADL語言編寫一個算法，判斷任一整數(shù)n是否為素數(shù)。.作業(yè)1－5試用ADL語言編寫一個算法，判斷任一整數(shù)n64考察知識點判斷素數(shù)素數(shù)——大于1的自然數(shù)中，除了1和此整數(shù)自身外，不能被其他自然數(shù)整除的數(shù)。判斷：對于指定的n，如果[2,n-1]內(nèi)的整數(shù)都不能整除n，則n為素數(shù)。ADL語言寫算法算法證明很難，可以使用邊界條件和特殊數(shù)據(jù)，人工模擬算法執(zhí)行過程。.考察知識點判斷素數(shù).65完成情況思想——基本正確，對素數(shù)定義的理解：1？算法——特殊情況處理：n1？算法輸出；ADL語言的使用：運算符號：MOD(模)，DIV(除數(shù))，/(除)；

，（取整）；％？sqrt?fabs()?

輸入輸出參數(shù)：設(shè)置返回值；中間用“.”分隔；條件語句：ifthenelse；

fori＝1tonstep1(i=i+1?)

賦值語句：.完成情況思想——基本正確，對素數(shù)定義的理解：1？.66參考答案算法S(n.flag)/*判斷整數(shù)n是否為素數(shù)，將結(jié)果保存到變量flag*/S1[n≤1？]IF(n≤1)THEN(flag←false.RETURN.)S2[初始化]i←2.flag←true.S3[求余判斷]WHILE(i≤n-1)DO(IF(nMODi)=0THEN(flag←false.RETURN.)i←i+1.)▌.參考答案算法S(n.flag).67正確性驗證：假定n＝7，模擬執(zhí)行過程，對i＝2，3，4，5，6時，分別判斷(7modi)的取值是否為0。改進(jìn)：n-1？——n/2、n1/2n=ab,a≥2,b≤n/2,…a,…b,…n/2a≤n1/2,b≥n1/2,…a,…n1/2,…b…

.正確性驗證：.68參考答案2算法S(n.flag)/*判斷整數(shù)n是否為素數(shù)，將結(jié)果保存到變量flag*/S1[n≤1？]IF(n≤1)THEN(flag←false.RETURN.)S2[初始化]i←2.flag←true.S3[求余判斷]WHILE(i≤

n/2)DO(IF(nMODi)=0THEN(flag←false.RETURN.)i←i+1.)▌.參考答案2算法S(n.flag).69作業(yè)1-8若A(n)=amnm+…+a1n+a0是關(guān)于n的m次多項式，證明A(n)=O(nm)。設(shè)f(n)和g(n)是正整數(shù)集到正實數(shù)集的函數(shù)，稱f(n)是O(g(n))當(dāng)且僅當(dāng)存在正常數(shù)C和n0，使得對任意的nn0，有f(n)Cg(n)。完成情況：令n0＝1，C＝am+…+a1+a0，

amnm+…+a1n+a0Cnm

注意：當(dāng)ai0時，ainiainm不一定成立。.作業(yè)1-8若A(n)=amnm+…+a1n+a0是關(guān)于n的m70證明：對于所有的n≥1，有：

A(n)=i=0,…,maini≤i=0,…,m|ai|ni≤

nmi=0,…,m|ai|ni-m

≤

nmi=0,…,m|ai|

令C＝i=0,…,m|ai|，有A(n)≤

Cnm

所以，

A(n)=O(nm)。參考答案.證明：對于所有的n≥1，有：參考答案.71作業(yè)1－11

證明對正整數(shù)n≥3，算法BS的元素比較次數(shù)T(n)≤5n/3-2。已知：0n=1T(n)=1n=2T(n/2)+T(n/2)+2n>2.作業(yè)1－11證明對正整數(shù)n≥3，算法BS的元素比較次數(shù)T(72考察知識點：數(shù)學(xué)歸納法基礎(chǔ)歸納：n=c(初值)時，命題是正確的；歸納步驟：如果n＝k－1時，命題成立，則n＝k時，命題也成立。完成情況：利用結(jié)論T(n)＝3n/2－2，需要注意前提條件——當(dāng)n是2的冪時；由n=k反推n＝k-1時的情況。.考察知識點：數(shù)學(xué)歸納法.730n=1

T(n)=1n=2

T(n/2)+T(n/2)+2n>2n=3時，T(3)=T(1)+T(2)+2=3，53/3-2=3，命題成立。假設(shè)n<=k時命題成立，需證明n=k+1時成立。

當(dāng)k≥3時，有(k+1)>(k+1)/2≥(k+1)/2

，即k≥(k+1)/2≥(k+1)/2

所以：T((k+1)/2)≤5((k+1)/2)/3-2,

(1)

T((k+1)/2)≤5((k+1)/2)/3-2

(2)T(k+1)=T((k+1)/2)+T((k+1)/2)+2≤[5((k+1)/2)/3-2]＋[5((k+1)/2)/3-2]+2=5((k+1)/2+(k+1)/2)/3-2//k＋1=(k+1)/2+(k+1)/2

=5(k+1)/3-2綜上，命題得證。.074作業(yè)1－12給出算法BS的非遞歸算法，并說明算法最多需要多大的輔助空間。.作業(yè)1－12給出算法BS的非遞歸算法，并說明算法最多需要多大75算法SM(A,n.max,min)

SM1[初始化]max←min←A[1].

SM2[比較]

FORI=2TOnDO

//求最大和最小元素

(IFA[I]>maxTHENmax←A[I].IFA[I]<minTHENmin←A[I]).

▌.算法SM(A,n.max,min).76BS算法算法BS（A，i，j.fmax，fmin）//在數(shù)組A的第i個元素到第j個元素之間尋找最大和最//小元素，已知ij。BS1[遞歸出口]IFi=jTHEN（fmax←fmin←A[i].RETURN.）IFi=j1THEN

（IFA[i]<A[j]THEN（fmax←A[j].fmin←A[i]）. ELSE（fmax←A[i].fmin←A[j]）.RETURN）..BS算法算法BS（A，i，j.fmax，fmin）77BS2[取中值] mid←(i+j)/2BS3[遞歸調(diào)用]BS（A，i，mid.gmax，gmin）

BS（A，mid+1，j.hmax，hmin）.BS4[合并] fmax←max{gmax，hmax}. fmin←min{gmin，hmin}.■

.BS2[取中值].78完成情況做的很少SM方法；（沒有體現(xiàn)分治思想）依次對比鄰近的兩個元素，找到較大較小者，不斷更新全局最大最小值；依次對比，用數(shù)組存放每對的最大最小值；兩個棧分別存放當(dāng)前起始和終止元素下標(biāo)；一個棧存儲中間值，另一個存放最大最小值。（沒法確定起始和終止元素的下標(biāo)）.完成情況做的很少.79輔助空間：因為采用某種特殊結(jié)構(gòu)，而增加占用的空間；占用空間：算法運行所需要的空間；方法3：數(shù)組；方法4：棧.輔助空間：因為采用某種特殊結(jié)構(gòu)，而增加占用的空間；.80方法4基本思想：創(chuàng)建兩個棧，一個存放起始元素的下標(biāo)，一個存放終止元素的下標(biāo)。每次從棧中彈出一對下標(biāo)，若兩者相等或相差為1，則找到最大最小值，否則找到中間下標(biāo)，形成兩對新的下標(biāo)，壓入棧內(nèi)。.方法4基本思想：.81示例數(shù)組A=[3,9,21,15,8,19]16初始：壓入起始和結(jié)束下標(biāo)1和6；循環(huán)：彈出元素1和6；兩者不相等、相差不為1；取中值(1+6)/2=3；形成兩對新的下標(biāo)，(1,3)和(4,6);壓入棧；彈出4和6，兩者不相等、相差不為1；取中值(4+6)/2=5；形成兩對新的下標(biāo)，(4,5)和(6,6);壓入棧內(nèi)；1346134566.示例數(shù)組A=[3,9,21,15,8,19]16初始：壓入起82A=[3,9,21,15,8,19]134566彈出(6,6)，相等，元素值為19，則fmaxmax{fmax,19}=19，fminmin{fmin,19}=19；彈出(4,5)，相差為1，元素值為15和8，則fmaxmax{19,15,8}=19，fminmin{19,15,8}=8；13.A=[3,9,21,15,8,19]134566彈出(6,683參考答案算法f(A,i,j.fmax,fmin)f1.[初始化]fmaxfminA[i].Lstack<int>left;Lstack<int>right;//存儲起始和終止下標(biāo)left.push(i).right.push(j).f2.[求最大、最小值]While(!left.IsEmpty())DO(lleft.pop().rright.pop().

.參考答案算法f(A,i,j.fmax,fmin).84IFl=rTHEN//相等(fmaxmax{fmax,A[l]}.fminmin{fmin,A[l]}.)ELSE(IFr-l=1//相差為1THEN(fmaxmax{fmax,A[l],A[r]}.fminmin{fmin,A[l],A[r]}.)ELSE(mid=(i+j)/2.left.push(l).left.push(mid+1).right.push(mid).Right.push(r).))).IFl=rTHEN//85輔助空間：棧nn/2n/2n/4n/4…1log2n.輔助空間：棧nn/2n/2n/4n/4…1log2n.86作業(yè)2－1編寫算法Reverse(A[],n)，將順序存儲的線性表A=(a1,a2,…,an)轉(zhuǎn)換為A=(an,…,a2,a1)，要求轉(zhuǎn)換過程中使用盡可能少的輔助空間。關(guān)鍵點：限制輔助空間的使用如果沒有這個限制，則可以有多種方法：輔助數(shù)組；雙下標(biāo)同時向中間移動.作業(yè)2－1編寫算法Reverse(A[],n)，將順87分析只需從線性表的第一個數(shù)據(jù)元素開始，將第i個數(shù)據(jù)元素與第n-i+1個數(shù)據(jù)元素相交換即可。i的變化范圍是1到n/2。a1a2…an-1ananan-1…a2a11+n2+(n-1)…(n-1)+2n+1.分析只需從線性表的第一個數(shù)據(jù)元素開始，將第i個數(shù)據(jù)元素與第n88參考答案算法Reverse（A，n.A）Reverse1.[元素互換]FORi=1TOn/2DOA[i]←→A[n-i+1].▌.參考答案算法Reverse（A，n.A）.89作業(yè)2-8在單鏈表類SLIST中添加一個成員函數(shù)，將單鏈表中元素的次序完全顛倒。.作業(yè)2-8在單鏈表類SLIST中添加一個成員函數(shù)，將單鏈表中90利用堆棧；從表頭刪除，插入表尾；(不推薦)換數(shù)據(jù)域的取值，p1和p2向中間移動，更換數(shù)據(jù)域的取值?！環(huán)eadp1p2.利用堆棧；…h(huán)eadp1p2.91方法4思想：從左向右，依次更換鄰近結(jié)點的指針方向。初始設(shè)置，第一個元素需要被放到表尾，指向空指針，p1=null，p2=next(head)//第一個元素headp22p3345p1nullp11p26P3next(p2)next(P2)P1. //反轉(zhuǎn)P1P2.P2P3..方法4思想：從左向右，依次更換鄰近結(jié)點的指針方向。headp92參考答案算法Reverse(head.head)/*將指針head所指向的鏈表倒置*/RV1[空鏈表和1個節(jié)點鏈表]IF(next(head)=NULL)RETURN.RV2[指針初始化] //P1,P2分別指向兩個連續(xù)的節(jié)點

P1NULL. P2next(head)..參考答案算法Reverse(head.head).93RV3[反轉(zhuǎn)鏈表] WHILE(P2≠NULL)DO (P3next(p2) next(P2)P1. //反轉(zhuǎn)節(jié)點指針

P1P2.P2P3.//移動3個指針 ）RV4[head指向反轉(zhuǎn)鏈表]

next(head)P1.

▌p1p2.RV3[反轉(zhuǎn)鏈表]p1p2.94作業(yè)2－11已知線性表中的元素以data值遞增有序排列，并以單鏈表做存儲結(jié)構(gòu)。試寫一高效的算法，刪除表中所有值大于mink且小于maxk的元素，同時釋放被刪結(jié)點空間，并分析算法的時間復(fù)雜度。鏈表是有序的：找到區(qū)間特殊情況的處理：表為空，元素都大于maxk(第一個元素大于maxk)；元素都小于mink(最后一個元素小于mink)。.作業(yè)2－11已知線性表中的元素以data值遞增有序排列，并以95主要思想：找到大于mink的第一個元素，刪除操作，直至元素大于maxk。時間復(fù)雜度：比較為基本運算最好：空，元素都大于maxk（找不到）//O(1)最壞：元素都小于mink（找不到），

元素都小于maxk，O(n)；.主要思想：.96算法LD(L,mink,maxk)LD1.[特殊情況]IF

minkmaxkTHEN(RETURN.)LD2.[初始化]p←head.prev←p.p←next(p)LD3.[找]WHILE(pNULLANDdata(p)<maxk)DO(IF(data(p)mink)THEN(prev←p.p←next(p))//向后移動ELSE(next(prev)←next(p).q←p.p←next(p).AVAILq.))//刪除qRETURN.prevheadpPprevp.算法LD(L,mink,maxk)LD1.[特殊情況97作業(yè)2－17對于順序堆棧和鏈?zhǔn)蕉褩，分別編寫函數(shù)SelectItem(Stack&s,intn)，要求在堆棧中查找元素n在棧中第一次出現(xiàn)的位置，并將該位置元素移至棧頂，同時其他元素次序不變。（注意：用int匹配堆棧的模板）.作業(yè)2－17對于順序堆棧和鏈?zhǔn)蕉褩，分別編寫函數(shù)Selec98基本思想：取棧頂元素，若不匹配，則進(jìn)行彈棧操作；找到（或無法找到）后恢復(fù)原來的元素次序。關(guān)鍵點：記錄彈出的順序，后彈出的元素能夠先被壓回原來的棧，因此需要使用一個輔助堆棧。.基本思想：.99示例105112shelpStack5173n=515112105173751511210377351.示例105112shelpStack5173n=515112100參考答案intSelectItem(Stack<int>&s,intn){AStack<int>temp(100);//順序堆棧，輔助棧

//LStack<int>temp;//鏈?zhǔn)蕉褩?/p>

boolflag=false;//是否存在元素nintloc=0;//記錄n所在的位置

while(!s.isEmpty()&&s.Peek()!=n

){temp.Push(s.Pop());loc++;}棧非空且當(dāng)前元素不等于n.參考答案intSelectItem(Stack<int>101if(!s.isEmpty()){s.Pop();flag=true;}//彈出nwhile(!temp.isEmpty())//將輔助棧中元素壓入原棧

{s.Push(temp.Pop());}if(flag)thens.Push(n)；

elseloc=-1;returnloc;}因為找到元素而跳出循環(huán).if(!s.isEmpty())因為找到元素102作業(yè)2－25編寫并實現(xiàn)雙端隊列類，雙端隊列是可進(jìn)行如下操作的線性表。(1)push(item)－－item插入到隊列的前端；(2)pop(item)－－刪除前端元素且賦給item；(3)inject(item)－－item插入尾端；(4)eject(item)－－刪除尾端元素且賦給item.作業(yè)2－25編寫并實現(xiàn)雙端隊列類，雙端隊列是可進(jìn)行如下操作的103結(jié)點結(jié)構(gòu)SLNode：數(shù)據(jù)域和指針域；類成員：隊首和隊尾的SLNode類型指針、指示元素個數(shù)的整型變量；Push(item插入隊列前端)

若空，則加入一個以item為數(shù)據(jù)域的結(jié)點，元素個數(shù)為1；否則，temp記錄原隊首指針front；

創(chuàng)建以item為數(shù)據(jù)域的新結(jié)點，作為新的隊首，賦值給front；front的指針域指向temp，元素個數(shù)加1。.結(jié)點結(jié)構(gòu)SLNode：數(shù)據(jù)域和指針域；.104Pop(刪除前端元素，并賦值item)若空，則錯誤；否則，temp記錄原隊首指針front；

隊首后移，即frontnext(front)；

返回temp的數(shù)據(jù)域；

刪除temp結(jié)點，元素個數(shù)減1；

若大小為零，則隊尾指針rear賦值為NULL。.Pop(刪除前端元素，并賦值item).105Inject(item插入隊尾)若空，則加入一個以item為數(shù)據(jù)域的結(jié)點，元素個數(shù)為1；否則，創(chuàng)建以item為數(shù)據(jù)域的新結(jié)點temp，作為新的隊尾，即next(rear)temp；隊尾指針后移，即rearnext(rear);元素個數(shù)加1。.Inject(item插入隊尾).106Eject(刪除隊尾元素并賦值給item)若空，則出錯；否則，

找到隊尾指針的前驅(qū)指針tempfront.IF(temprear)THEN(WHILE(next(temp)rear)DO(tempnext(temp))隊尾指針更新，即reartemp，

要刪除結(jié)點是next(temp)，返回數(shù)據(jù)域，刪除結(jié)點，元素個數(shù)減1。

若大小為零，front和rear賦值為NULL。.Eject(刪除隊尾元素并賦值給item).107作業(yè)3－10設(shè)稀疏矩陣Mmn中有t個非零元素，用三元組表的方式存儲.請設(shè)計一個算法，計算矩陣M的轉(zhuǎn)置矩陣N，且算法的時間復(fù)雜性為O(n+t).注意，書中給出的算法的復(fù)雜性為O(nt)。.作業(yè)3－10設(shè)稀疏矩陣Mmn中有t個非零元素，用三元組表的108M=500001002000000-300-605N=50100-3000000200-6000050050a[0]1010a[1]1220a[2]30-30a[3]32-60a[4]335a[5]0050b[0]0110b[1]03-30b[2]2120b[3]23-60b[4]335b[5]算法的關(guān)鍵是求出a中元素在b中的位置.M=50000N=5010109Bindex＝0；FORj=0TOn－1DO

FORk=0TOt－1DOIFcol(A[k])=jThen (row(B[Bindex])=j. col(B[Bindex])=row(A[k]). value(B[Bindex])=Value(A[k]).

Bindex++）a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-30j=0,k=0,a[0],列坐標(biāo)=0；存儲j=0;k=1;a[1],列坐標(biāo)=0；存儲j=0;k=2;a[2],列坐標(biāo)=2；j=0;k=3;a[3],列坐標(biāo)=0；存儲j=0;k=4;j=0;k=5;j=1;k=0005030-301010.Bindex＝0；a[0]00502120011033523110a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-30005030-301010j=1,k=0,a[0],列坐標(biāo)=0j；j=1,k=1;列坐標(biāo)1j=1,k=2;j=1,k=3;j=1,k=4;j=1,k=5;j=2,k=0；j=2,k=1；j=2,k=2，列坐標(biāo)=2=jFORj=0TOn－1DO

FORk=0TOt－1DOIFcol(A[k])=jThen2201.a[0]00502120011033523-6003-300111005030-30101033532-601220a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-30b[2]a[x]b[y]?y=列坐標(biāo)小于col(a[x])的元素個數(shù)+

列坐標(biāo)等于col(a[x])且在a[x]之前的元素個數(shù).005030-30101033532-601220a[0]0112a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-30基本思想：

數(shù)組num存儲a中每列非零元素個數(shù)；數(shù)組pos存儲a中每列第一個非零元素在b的三元組表中的位置；

302101230123num0335pos.a[0]00502120011033523-6003-30基113算法:TRANSPOSE(A.B)TP