計(jì)算機(jī)軟件技術(shù)基礎(chǔ)-習(xí)題一解答

計(jì)算機(jī)軟件技術(shù)基礎(chǔ)-習(xí)題一解第第2頁(yè)共16頁(yè)n為正整數(shù),分析下列各程序段中加下劃for(ini=1i<=nfor(inj=1j<=nj++{c[i][j]=0.0for(ink=1k<=nk++)c[i][j]=c[i][j]+a[i][k*}x= y=for(ini=1i<=nfor(inj=1j<=i;j++for(ink=1k<=j;x=x+ini=1 j=1whil(i<=&&j<=n{i=i+ j=j+}*ini=1for(inj=1j<=ni=i+}while(i<10+【解 答1ni1j1

i(i1)

1 11j

2

2i

j1

i1

1n(n1)(2n1)1n(n1)n(n1)(n (3)=1時(shí)，i=2，=j+=1+2=2+i=2時(shí)，i=3，=+i=(2+1)+3=3+1+i=3時(shí)，i=4，=+i=(3+1+2)+4=4+1+2+i=4時(shí)，i=5，=+i=(4+1+2+3)+5=5+1+2+3+kkjk1ik

k23k1 1 i=k時(shí)，i=k+1，=j+i=(k+)+(1+2+3+4+…+k解出滿足上述不等式的k值，即為語(yǔ)句i=i+1的 for語(yǔ)句每執(zhí)行一次，語(yǔ)句i=i+將執(zhí)行ni的值會(huì)增加n(n2fork，i1kn(n2fork1kn(n1)1002的最小整數(shù)k語(yǔ)句i=i+j的程序步數(shù)為n*kA[arraySize]n0≤n≤arraySize。若設(shè)計(jì)算機(jī)中允許的整數(shù)的最大值為，則當(dāng)n>arraySiz或者對(duì)于某一k0knk!*2kmaxIn時(shí)，應(yīng)按用print顯示錯(cuò)誤信息及exit(1)語(yǔ)句01在函數(shù)的參數(shù)表設(shè)置一個(gè)引用型的整型#includconstinarraySize=100constinMaxIn=0x7fffffffincalc(inT[],inn){ini,valu=1;T[0]=1if(n!0){inedge=MaxIn/n/2for(i=1i<ni+){valu*=i*2T[i=if(valu>edge)return}valu*=n*}T[n]=printf("A%d]=%d\n”,n,T[n])return1}voimai()inintfor(i=0i<arraySize;i+)if(!calc(Ai)){printf("faileat%d.\n"i);}} 順序表結(jié)構(gòu)的定義.數(shù)據(jù)元素從data[0]處開(kāi)始存儲(chǔ)typedefstruct {in /*數(shù)據(jù)域in /*表長(zhǎng)設(shè)有一個(gè)線性表(a0a1…,an-2an-1)存放在一個(gè)一維數(shù)組A[arraySize]中的前n個(gè)數(shù)組置，即將數(shù)組的前n個(gè)原址內(nèi)容置換為(an-1an-2a1a0voiinvers(listtyp*A){intmpinn=A-for(ini=0i<=(n-1)/2i+){ A- A- A->data[n-i- A->data[n-i-1]=}}度為O(n)空間復(fù)雜度：使用一個(gè)整形輔助存儲(chǔ)單元tmp因此空間復(fù)雜度為O(1)。順序表的插入和刪除要求仍然保持各個(gè)元素127素的順序表進(jìn)行插入,平均需要移動(dòng)多少個(gè)元個(gè)插入位置(可以在表中最后一個(gè)表項(xiàng)后面追加)，每個(gè)元素位置插入的概率為1/(n+1)，但每個(gè)元素位置刪除的概率為1/n。插入時(shí)平均移動(dòng)元素個(gè)數(shù)AMN(AveragNumberAMN1

ni1(n(n1)

10) n(n1)nn1

n

n 刪除時(shí)平均移動(dòng)元素個(gè)數(shù)AMNAMN11(ni1)1((n1)(n2)

10)1(n1)nn1n

從順序表中刪除具有給定值x從順序表中刪除其值在給定值s與t（st）從有序順序表中刪除其值在給定值s與之間（st）將兩個(gè)有序順序表la,l合并成一個(gè)新的lc。第第10頁(yè)共16頁(yè)從順序表中刪除具有給定值xvoiDelValue(listtyp*L,inx){ini=0whil(i<L->lengt) /*循環(huán),尋找具有值x的元素并刪除它*/if(L->data[i==x){ x的元素,后續(xù)元素前移*/ L->data[j=L->data[j+1]L-length- /*}else}st（s小于t）voiDelValue_s_to_(listtyp*L,ins,int){intif(L->lengt==0||s>=t){printf(“Lisisemptyorparameterareillegal!\n”) exit(1)}i=0whil(i<L->length /*循環(huán),尋找具有值x的元素并刪除它*/if(L->data[i]>=&&L->data[i]</*刪除滿足條件的元素,后續(xù)元素前移for(j=i;j<L->length-1j+)L->data[j=L->data[j+1]L->length- /*}else}實(shí)現(xiàn)從有序順序表中刪除其值在給定值stvoiDelValue_s_to_t_(listtyp*L,insint){intif(L->lengt==0||s>=t){printf(“Lisisemptyorparameterare exit(1)for(i=0i<L->lengthi+ 循環(huán),尋找值≥s的第一個(gè)元素if(L->data[i>=s) 退出循環(huán)時(shí),i指向該元素*/if(i<L->lengt){forj1ijL->lengthj)/*尋找值>t的第一個(gè)元素if(L->data[i+j>t)break 出循環(huán)時(shí),i+指向該元素*/forki+jkL->lengthk*刪除滿足條件的元素,后續(xù)元素前移*/L->data[k-j]=L-L->length-= /*表長(zhǎng)減}}實(shí)現(xiàn)將兩個(gè)有序順序表合并成一個(gè)新的listtyp*Merge(listtyp*LA,listtyplisttypinvalue1,value2ini,j,kif(LA->lengt+LB->lengt>MAXSIZE{ }i=0j=0k=value=LA-value=LB-whil(i<LA->lengt&&j<LB->lengt{/*循環(huán),兩兩比較,小者存入結(jié)果表*/if(value<=value2LC- value1=LA-else }whilei<LA->length /*當(dāng)LA表未檢測(cè)完,繼續(xù)向結(jié)果表傳送*/ value=LA->data[i]}whilej<LB- /*當(dāng)LB未檢測(cè)完,繼續(xù)向結(jié)果表傳送 value=LB->data[j]}LC->lengt=kreturnLC}實(shí)現(xiàn)從表中刪除所有其值重復(fù)的元素的voiDelDouble(listtyp*L){ini,j,kinif(L->lengt==0printf(“表空 }whil(i<L->lengt){ /*循環(huán)檢ji+=L-whilej<L->lengt){ /*對(duì)于每i,重復(fù)檢測(cè)一遍后續(xù)元素*/if(tm==L->data[j{/*如果相for(k=j+1k<L->length)L->data[k-1]=L- 減1*/}else} /*檢測(cè)完L-檢測(cè)下一個(gè)}}順序存儲(chǔ)表示是將數(shù)據(jù)元素存放于一個(gè)連鏈接存儲(chǔ)表示的存儲(chǔ)空間一般在程序的運(yùn)行過(guò)如果有n空間中為這n間還可以在以后動(dòng)態(tài)分配給其他的存儲(chǔ)申請(qǐng)要求，非常靈活方便。對(duì)于n個(gè)表(包括表的總數(shù) 鏈表結(jié)構(gòu)的定義. typedefstructindata structmynode*next /*指針域*/}nodeinlengthsl(linklisttyp*L){linklisttyp*pinlenif(L==NULL){returp=L->next pLle=while(!NULL)p=p-}return}h表的表頭指針h指向原鏈表的最后一個(gè)結(jié)點(diǎn)。voiLinkListInverse(linklisttyp*L){linklisttyp*p*pre*nextif(L==NULL||L->next==NULL)p=L->nextpre=whilep!NULL){ next=p- /*后繼指針p->next=pre pre=p /*指針后移}L->next->next=NULL L->next=pre } L,linklisttyp*LA,linklisttyp*LB){點(diǎn)值均為正，LB中結(jié)點(diǎn)值均為負(fù)，并刪除結(jié)點(diǎn)值為零的結(jié)點(diǎn),最后釋放L的頭結(jié)點(diǎn)。linklisttyp*p,*pt,*pa*pbLA=initiatesl()pa=LA /*指向LA中的最后LB=pb=LB /*指向LB中的最后If(L==NULL||L->next==NUUL)/*LLp=L-第一個(gè)結(jié)點(diǎn)/*p指向鏈表Lwhile(!/*遍歷鏈表if(p->data>LA的pa后pa->next=pa=p=p-}elseif(p->dataLBpbpb->next=pb=p=p-} /*刪除值為0pt=p- /*的后繼，以便刪除當(dāng)前結(jié)點(diǎn)p=pt}pb->next=NULL}有序單鏈表的表頭指針,試設(shè)計(jì)一個(gè)算法,將這 *LA,linklisttyp*LB放LB的頭結(jié)點(diǎn)*/linklisttyp*pa*pb,*pre,*pnif(L==NULL||LB==NULL||)returnif(LA- /*LA為L(zhǎng)A->next=LB->next} /*LBpa=LA->nextpb=LB->next,pre=LAwhil(pa!NULL&&pb!NULL) 循環(huán),兩兩比較,小者存入結(jié)果表if(pa->data>pb /*將pre->next=pbpb->next=pb=} pa=pa->nextpre=pre->next}if(p!NULL) /*pb結(jié)點(diǎn)鏈入LA*/pre->next=pb}有序單鏈表的表頭指針,試設(shè)計(jì)一個(gè)算法,將這 *LA,linklisttyp*LBLA、LBLC*/linklisttyp*pa*pb,if(L==NULL||LB==NULL||)returnLC=initiatesl()pa=LA->nextpb=LB-whil(pa!NULL&&pb! 循環(huán),兩兩比較,大者存if(pa->data>pb /*將p=pa->nextpa->next=LC->nextLC->next=papa=} p=pb-pb->next=LC->nextLC->next=pbpb=}while(p! /*將剩余結(jié)點(diǎn)鏈入LC*/p=pa->nextpa->next=LC->nextLC->next=papa=}while(p! /*將剩余結(jié)點(diǎn)鏈入LC*/p=pb->nextpb->next=LC->nextLC->next=pbpb=}}xtypedefstructmynode inx){cyclelisttyp*p,*preif(C==NULL)returnp=CL->nextpre=CLwhile(!CL)if(p->data==x)p=p-}if(! /*查找成功per->next=p->next 除p*/p->next=CL- /*p插入到后CL->next=}鐵路進(jìn)行列車調(diào)度時(shí)常把站臺(tái)設(shè)計(jì)成棧式結(jié)構(gòu)的站臺(tái)，如右設(shè)有編號(hào)為1,2,3,4,5,的六輛列車,順序開(kāi)入棧式結(jié)構(gòu)的站臺(tái),則可能的出棧序列有若進(jìn)站的六輛列車順序如上所述,否能夠得435612325641154623的出站序列如果不能說(shuō)明為什么不能如果能,說(shuō)明如何得到(即寫出"進(jìn)棧"或"出棧"的序

1/(61)C

可能的不同出棧序列 種不能得到435612和154623列。因?yàn)槿粼?356之后再將12棧2應(yīng)壓在1上面不可能1先于2出棧也是這種情況出棧序列325641和13542632121154132121154141641411 1325424221325424226 試證明：若借助?？捎奢斎胄蛄?23np1p2p3pn(它是輸i<j<kppk<pi。(因?yàn)榻柚鷹Ｓ奢斎胄蛄?23n，可得到輸出序列p1p2p3…,pni,j,ki<j<k，那么在輸出序列中出現(xiàn)如下5種情況：①i進(jìn)棧，i出棧，j進(jìn)棧，j出棧，k進(jìn)棧，kp位置，具有中間值的排在其后p位置，具有最大值的pkpppkppk<p的情形；j出棧。此時(shí)具有最小值的排在最前面p位置，具有最大值的排在p位置，具有中間值的排在pkp<pkpppk<p的情形；③i進(jìn)棧，j進(jìn)棧，j出棧，i出棧，k進(jìn)棧，kp位置，具有最小值的排在其后p位置，有p<p<pk不可能出現(xiàn)p<pk<p的情形；④i進(jìn)棧，j進(jìn)棧，j出棧，k進(jìn)棧，k出棧，i出棧。此時(shí)具有中間值的排在最前面p位置，具有最大值的排在其后p位置，具有最小值的排在pk位置有pk<p<pj 也不可能出現(xiàn)p<pk<p的情形⑤i進(jìn)棧，j進(jìn)棧，k進(jìn)棧，k出棧，j出棧，i出棧。此時(shí)具有最大值的排在最前面p位置，具有中間值的排在其后p位置，具有最小值的排在pk位置有pk<p<pi 也不可能出現(xiàn)p<pk<p的情形01間V[m]中，棧底分別處于數(shù)組的兩端。當(dāng)?shù)?號(hào)棧的棧頂指針top[0]等于-1時(shí)該棧為空，當(dāng)?shù)?號(hào)棧的棧頂指針top[1]等于m時(shí)該棧為空。0號(hào)棧插入一個(gè)新元素時(shí)，使top[0]增1得到新的棧頂位1top[1]top[0top[1]-1能再向任一棧加入新的元素。試定義這種雙棧(DoublStack)結(jié)構(gòu)的類定義，并實(shí)現(xiàn)判?？?、 typedefstruct{intop0,top1elemtypinDoubleStackEmpty(DoubleStac*DS,in/*DS：指向雙棧的指針，或1，指定要判斷的是第0棧，還是第一棧return(DS->top0<0)retrun(DS->top1>=}inDoubleStackFull(DoubleStac*DS)} StackNo,elemtypx){if(StackNo==0){/*0*/DS-DS-}else{/*1*/DS-}} DS,inStackNo)if(StackNo==0){/*0*/return(DS->data[DS-}DS-return(DS->data[DS->top1-}}改寫順序棧的進(jìn)棧成員函數(shù)Push(x)，要求當(dāng)棧滿時(shí)執(zhí)行一個(gè)stackFull)操作進(jìn)行棧滿組中的元素占據(jù)新數(shù)組的前MaxSiz位置。voipush(stack*S,elemtypx){if(StackEmpty(S)S->top++S->data[S->top]= }voistackFull(stac*S){elemtyp*temp//for(ini=0i<=S->topi+temp[i=S->data[i]free(S- //MAXSIZ*=3 //數(shù)組最 }e有n(NS)6達(dá)式求值時(shí)所用到的運(yùn)算對(duì)象棧中最多可存入若設(shè)當(dāng)前掃描到的運(yùn)算符ch的優(yōu)先級(jí)為符;(^%-)017538086421步序描作動(dòng)化輸出進(jìn)棧,讀下一符;isp也叫做棧內(nèi)(ink)優(yōu)先數(shù)，ip也叫做棧外(incomingty)chicp(ch)isp()時(shí)，ch進(jìn)棧；當(dāng)剛掃描到的運(yùn)算符hicp(ch)isp()時(shí)，則位于棧頂?shù)倪\(yùn)算符退棧并ip(“(”)(棧后，步序描作動(dòng)化輸出進(jìn)棧,讀下一符;0號(hào) 操作直接輸出,讀下一;A數(shù) 操作isp(';')<icp(''),進(jìn)棧,;A符 操作直接輸出,讀下一;a數(shù) 操作isp('*')>icp(';ax符isp(';')<icp(''),進(jìn)棧,;ax 操作直接輸出,讀下一;ax*數(shù) 操作isp(' ')<進(jìn)棧,讀下一;-ax*符號(hào)操直接輸出,讀下一;ax* 作數(shù)-x操isp(' ')<;a* 作'^'),進(jìn)棧讀下一-x符號(hào)^操直接輸出,讀下一;a* 作-x數(shù)^操isp('↑')>icp(';;axb1;作),-x0符isp('/')>icp(';axbxisp('-')>icp(';;ax*),x2^/70（170，隊(duì)列中元素的個(gè)數(shù)為(MAXSIZE+rear-%MAXSIZ=(70+46-隊(duì)列中元素的個(gè)數(shù)為(MAXSIZE+rear-%MAXSIZ=(70+10-基于此結(jié)構(gòu)的隊(duì)列的插入(enqueue)和刪除front指向頭結(jié)點(diǎn)，rear=front location,elemtypx){/*Q