大二上學(xué)期學(xué)習(xí)2014年習(xí)題課

作業(yè)題講解12第一章課后作業(yè)1.求下述計(jì)算f=1！+2！+3！+…+n！的算法的時(shí)間復(fù)雜性。voidfactorsum(intn){inti,j；

intf,w；

f=0；

for(i=1;i<=n;i++)

{w=1；

for(j=1;j<=i;j++)

w=w*j;f=f+w;}return；}以乘法運(yùn)算為基本運(yùn)算;基本運(yùn)算次數(shù)為1+2+3+…+n=O(n2)作業(yè)1-5:試用ADL語言編寫一個(gè)算法，判斷任一整數(shù)n是否為素?cái)?shù)算法S(n.flag)/*判斷整數(shù)n是否為素?cái)?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.)▌該算法的時(shí)間復(fù)雜性最好為：O(1)最壞情況為：O(n)3算法S(n.flag)/*判斷整數(shù)n是否為素?cái)?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.)▌該算法的時(shí)間復(fù)雜性最好為：O(1)最壞情況為：O(n)4算法S(n.flag)/*判斷整數(shù)n是否為素?cái)?shù)，將結(jié)果保存到變量flag*/S1[n≤1？]IF(n≤1)THEN(flag←false.RETURN.)S2[初始化]i←2.flag←true.S3[求余判斷]WHILE(i≤

「n1/2)DO(IF(nMODi)=0THEN(flag←false.RETURN.)i←i+1.)▌該算法的時(shí)間復(fù)雜性最好為：O(1)最壞情況為：O(n1/2)5作業(yè)1-11證明對(duì)正整數(shù)n≥3，算法BS的元素比較次數(shù)T(n)≤5n/3-2

.已知信息

數(shù)學(xué)歸納法證明證明n=3時(shí)成立假設(shè)n<k時(shí)都成立,證明n=k時(shí)也成立6作業(yè)1-11n=3時(shí)，T(3)=T(1)+T(2)+2=3，5*3/3-2=3，命題成立。假設(shè)n<k時(shí)，命題成立。則n=k時(shí),T(k)=T()+()+2,...(1)

當(dāng)k≥3時(shí)，有k>≥

所以有T()≤5*()/3-2,

T()≤5*(

)/3-2成立,...(2)由(1)(2)，有T(k)=T(

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

綜上，命題得證。7第2章作業(yè)2-1已知長(zhǎng)度為n的線性表A＝(a1,a2,…,an)采用順序存儲(chǔ)結(jié)構(gòu)，請(qǐng)寫一算法，將線性表轉(zhuǎn)換為A＝(an,…,a2，a1)，要求轉(zhuǎn)換過程中用盡可能少的存儲(chǔ)空間。

82-1只需從線性表的第一個(gè)數(shù)據(jù)元素開始，將第i個(gè)數(shù)據(jù)元素與第n-i+1個(gè)數(shù)據(jù)元素相交換即可。在這個(gè)過程中，i的變化范圍是1到。這里只需要一個(gè)輔助空間temp.92-1算法Reverse（A，n.A）Reverse1.[元素互換]FORi=1TODO(temp←A[i].A[i]←A[n-i+1].A[n-i+1]←temp.).▌102-8設(shè)計(jì)一個(gè)算法，將鏈表的鏈接完全顛倒。11算法1：類似于習(xí)題2-1，將第i個(gè)與第n-i+1個(gè)結(jié)點(diǎn)的數(shù)據(jù)域互換。算法2：遍歷鏈表的同時(shí)修改指針。算法3：使用堆棧，實(shí)現(xiàn)單鏈表求逆。2-812

算法2

RV(head.head)/*將指針head所指向的鏈表倒置*/RV1[指針初始化] pNULL.qnext(head). rnext(q).//p,q,r分別指向三個(gè)連續(xù)的結(jié)點(diǎn)RV2[反轉(zhuǎn)鏈表] WHILE(r≠NULL)DO (next(q)p.//反轉(zhuǎn)結(jié)點(diǎn)q pq.//移動(dòng)3個(gè)指針

qr.rnext(r). )RV3[最后一個(gè)結(jié)點(diǎn)的處理]next(q)p.next(head)q.▌132-17對(duì)于順序堆棧和鏈?zhǔn)蕉褩，分別編寫函數(shù)SelectItem（Stack&s，intn），要求在堆棧中查找元素n在棧中第一次出現(xiàn)的位置，并將該位置元素移至棧頂，同時(shí)其他元素次序不變。（注意：用int匹配堆棧的模板）

142-17算法思想示例：n=34103412stemp3472103412stemp3472103412stemp3472從使用的角度來講，鏈?zhǔn)蕉褩Ｅc順序堆棧沒有區(qū)別。152-17intSelectItem(Stack<int>&s,intn){AStack<int>temp(100);//順序堆棧LStack<int>temp;//鏈?zhǔn)蕉褩?/p>

booleanflag=false;intloc=0;while(!s.isEmpty()&&s.Peek()!=n

){temp.Push(s.Pop());loc++;}162-17if(s.peek()==n)then{s.Pop();flag=true;}while(!temp.isEmpty())s.Push(temp.Pop());if(flag)thens.Push(n)elseloc=-1;returnloc;}17前二章練習(xí)題18與單鏈表相比，雙向鏈表添加和刪除數(shù)據(jù)元素的能力更高．循環(huán)鏈表可以實(shí)現(xiàn)環(huán)狀隊(duì)列。多維數(shù)組元素之間的關(guān)系是線性的．(正確）（正確）（正確）一、判斷題19二、選擇題：

已知一個(gè)順序存儲(chǔ)的線性表，設(shè)每個(gè)結(jié)點(diǎn)需占m個(gè)存儲(chǔ)單元，若第一個(gè)結(jié)點(diǎn)的地址為da,則第i個(gè)結(jié)點(diǎn)的地址為()。

A.da+(i-1)*mB.da+i*mC.da-i*mD.da+(i+1)*m20

若某線性表中最常用的操作是取第i個(gè)元素和刪除最后一個(gè)元素，則采用（）存儲(chǔ)方式最節(jié)省時(shí)間。

A.順序表

B.單鏈表

C.雙鏈表

D.單循環(huán)鏈表

A.順序表A

21

棧和隊(duì)列都是（）

A.順序存儲(chǔ)的線性表

B.鏈?zhǔn)酱鎯?chǔ)的線性表

C.限制存取點(diǎn)的線性結(jié)構(gòu)

D.限制存取點(diǎn)的非線性結(jié)構(gòu)CC.限制存取點(diǎn)的線性結(jié)構(gòu)22第3章課后作業(yè)73頁3-2二維數(shù)組A中，每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)從0到9，列下標(biāo)從0到11，則連續(xù)存放該數(shù)組至少需要多少個(gè)字節(jié)？10*12*3=360字節(jié)23

假定每個(gè)元素占據(jù)1個(gè)存儲(chǔ)單元，把該下三角型矩陣存儲(chǔ)在(n+1)(n+2)/2個(gè)連續(xù)的存儲(chǔ)單元中。請(qǐng)給出相應(yīng)的尋址公式。設(shè)元素A[i,j]前面有k個(gè)元素，可以計(jì)算出

k=1+2+…+i+j=i(i+1)/2+jLoc(A[i,j])=Loc(A[0,0])+i(i+1)/2+j24

73頁3-3

二維數(shù)組A有4行8列，下標(biāo)從0開始，存儲(chǔ)A的起始地址為2000，每個(gè)元素用相鄰的4個(gè)字節(jié)存儲(chǔ)，試計(jì)算：存儲(chǔ)整個(gè)數(shù)組一共需要多少個(gè)字節(jié)。數(shù)組A的最后一個(gè)元素的起始地址。按行優(yōu)先存儲(chǔ)時(shí)，A[2][4]的起始地址。按列優(yōu)先存儲(chǔ)時(shí)，A[3][2]的起始地址。(1)4*8*4=128字節(jié);(2)2124；(3)2000+(2*8+4)*4=2080;(4)2000+(2*4+3)*4=2044;25

73頁3-4

26

73頁3-8

3-10

設(shè)稀疏矩陣Mm*n中有t個(gè)非零元素，用三元組表的方式存儲(chǔ).請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，計(jì)算矩陣M的轉(zhuǎn)置矩陣N，且算法的時(shí)間復(fù)雜性為O(n+t).

注意，書中給出的算法的復(fù)雜性為O(n*t).

27A=500001002000000-300-605A’=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中的位置283-10算法TRANSPOSE(A.B)TP1[初始化]

/*聲明A的轉(zhuǎn)置矩陣B，使得B的行數(shù)等于A的列數(shù)，B的列數(shù)等于A的行數(shù)，B中非0元素的個(gè)數(shù)等于A中非0元素的個(gè)數(shù)*/

n←Rows(B)←Cols(A).

Cols(B)←Rows(A).

t←Count(B)←Count(A). 29TP2[計(jì)算存儲(chǔ)位置]//定義數(shù)組num存儲(chǔ)A中每列非零元素個(gè)數(shù)

FORi=0TOn-1DO

num[i]←0.

FORi=0TOt-1DO

（j←col(A[i]). num[j]←num[j]+1.）//數(shù)組pos存儲(chǔ)A中每列第一個(gè)非零元素在B中的位置

pos[0]←