數(shù)據(jù)結(jié)構(gòu)與算法復(fù)習(xí)題與答案

..第1章緒論習(xí)題1．簡述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、抽象數(shù)據(jù)類型。2．試舉一個數(shù)據(jù)結(jié)構(gòu)的例子,敘述其邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)兩方面的含義和相互關(guān)系。3．簡述邏輯結(jié)構(gòu)的四種基本關(guān)系并畫出它們的關(guān)系圖。4．存儲結(jié)構(gòu)由哪兩種基本的存儲方法實現(xiàn)？5．選擇題〔1在數(shù)據(jù)結(jié)構(gòu)中,從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成〔。A．動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B．緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C．線性結(jié)構(gòu)和非線性結(jié)構(gòu)D．內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)〔2與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的〔。A．存儲結(jié)構(gòu)B．存儲實現(xiàn)C．邏輯結(jié)構(gòu)D．運(yùn)算實現(xiàn)〔3通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性,這意味著〔。A．?dāng)?shù)據(jù)具有同一特點B．不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同,而且對應(yīng)數(shù)據(jù)項的類型要一致C．每個數(shù)據(jù)元素都一樣D．?dāng)?shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等〔4以下說法正確的是〔。A．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位B．?dāng)?shù)據(jù)項是數(shù)據(jù)的基本單位C．?dāng)?shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項的集合D．一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)〔5以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是〔。A．順序隊列B.鏈表C.有序表D.鏈?！?以下數(shù)據(jù)結(jié)構(gòu)中,〔是非線性數(shù)據(jù)結(jié)構(gòu)A．樹B．字符串C．隊D．棧6．試分析下面各程序段的時間復(fù)雜度。〔1x=90;y=100;?while<y>0>if<x>100>{x=x-10;y--;}elsex++;〔2for<i=0;i<n;i++>for<j=0;j<m;j++>a[i][j]=0;〔3s=0;fori=0;i<n;i++>for<j=0;j<n;j++>s+=B[i][j];sum=s;〔4i=1;while<i<=n>i=i*3;〔5x=0;for<i=1;i<n;i++>for<j=1;j<=n-i;j++>x++;〔6x=n;//n>1y=0;while<x≥<y+1>*<y+1>>y++;〔1O〔1〔2O〔m*n〔3O〔n2〔4O〔log3n〔5因為x++共執(zhí)行了n-1+n-2+……＋1=n<n-1>/2,所以執(zhí)行時間為O〔n2〔6O<>第2章線性表1．選擇題〔1一個向量第一個元素的存儲地址是100,每個元素的長度為2,則第5個元素的地址是〔。A．110B．108C．100D．〔2在n個結(jié)點的順序表中,算法的時間復(fù)雜度是O<1>的操作是〔。A．訪問第i個結(jié)點〔1≤i≤n和求第i個結(jié)點的直接前驅(qū)〔2≤i≤nB．在第i個結(jié)點后插入一個新結(jié)點〔1≤i≤nC．刪除第i個結(jié)點〔1≤i≤nD．將n個結(jié)點從小到大排序〔3向一個有127個元素的順序表中插入一個新元素并保持原來順序不變,平均要移動的元素個數(shù)為〔。A．8B．63.5C．63D．〔4鏈接存儲的存儲結(jié)構(gòu)所占存儲空間〔。A．分兩部分,一部分存放結(jié)點值,另一部分存放表示結(jié)點間關(guān)系的指針B．只有一部分,存放結(jié)點值C．只有一部分,存儲表示結(jié)點間關(guān)系的指針D．分兩部分,一部分存放結(jié)點值,另一部分存放結(jié)點所占單元數(shù)〔5線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時,要求內(nèi)存中可用存儲單元的地址〔。A．必須是連續(xù)的B．部分地址必須是連續(xù)的C．一定是不連續(xù)的D．連續(xù)或不連續(xù)都可以〔6線性表Ｌ在〔情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實現(xiàn)。A．需經(jīng)常修改Ｌ中的結(jié)點值Ｂ．需不斷對Ｌ進(jìn)行刪除插入C．Ｌ中含有大量的結(jié)點Ｄ．Ｌ中結(jié)點結(jié)構(gòu)復(fù)雜〔7單鏈表的存儲密度〔。A．大于1B．等于1C．小于1D．〔8將兩個各有n個元素的有序表歸并成一個有序表,其最少的比較次數(shù)是〔。A．nB．2n-1C．2nD．n〔9在一個長度為n的順序表中,在第i個元素〔1≤i≤n+1之前插入一個新元素時須向后移動〔個元素。A．n-iB．n-i+1C．n-i-1D．<10>線性表L=<a1,a2,……an>,下列說法正確的是〔。A．每個元素都有一個直接前驅(qū)和一個直接后繼B．線性表中至少有一個元素C．表中諸元素的排列必須是由小到大或由大到小D．除第一個和最后一個元素外,其余每個元素都有一個且僅有一個直接前驅(qū)和直接后繼。<11>若指定有n個元素的向量,則建立一個有序單鏈表的時間復(fù)雜性的量級是〔。A．O<1>B．O<n>C．O<n2>D．O<nlog2n><12>以下說法錯誤的是〔。A．求表長、定位這兩種運(yùn)算在采用順序存儲結(jié)構(gòu)時實現(xiàn)的效率不比采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時實現(xiàn)的效率低B．順序存儲的線性表可以隨機(jī)存取C．由于順序存儲要求連續(xù)的存儲區(qū)域,所以在存儲管理上不夠靈活D．線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)<13>在單鏈表中,要將s所指結(jié)點插入到p所指結(jié)點之后,其語句應(yīng)為〔。A．s->next=p+1;p->next=s;B．<*p>.next=s;<*s>.next=<*p>.next;C．s->next=p->next;p->next=s->next;D．s->next=p->next;p->next=s;<14>在雙向鏈表存儲結(jié)構(gòu)中,刪除p所指的結(jié)點時須修改指針〔。A．p->next->prior=p->prior;p->prior->next=p->next;B．p->next=p->next->next;p->next->prior=p;C．p->prior->next=p;p->prior=p->prior->prior;D．p->prior=p->next->next;p->next=p->prior->prior;<15>在雙向循環(huán)鏈表中,在p指針?biāo)傅慕Y(jié)點后插入q所指向的新結(jié)點,其修改指針的操作是〔。A．p->next=q;q->prior=p;p->next->prior=q;q->next=q;B．p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;C．q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;D．q->prior=p;q->next=p->next;p->next=q;p->next->prior=q;2．算法設(shè)計題〔1將兩個遞增的有序鏈表合并為一個遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間,不另外占用其它的存儲空間。表中不允許有重復(fù)的數(shù)據(jù)。voidMergeList_L<LinkList&La,LinkList&Lb,LinkList&Lc>{pa=La->next;pb=Lb->next;Lc=pc=La;//用La的頭結(jié)點作為Lc的頭結(jié)點while<pa&&pb>{if<pa->data<pb->data>{pc->next=pa;pc=pa;pa=pa->next;}elseif<pa->data>pb->data>{pc->next=pb;pc=pb;pb=pb->next;}else{//相等時取La的元素,刪除Lb的元素pc->next=pa;pc=pa;pa=pa->next;q=pb->next;deletepb;pb=q;}}pc->next=pa?pa:pb;//插入剩余段deleteLb;//釋放Lb的頭結(jié)點}〔2將兩個非遞減的有序鏈表合并為一個非遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間,不另外占用其它的存儲空間。表中允許有重復(fù)的數(shù)據(jù)。voidunion<LinkList&La,LinkList&Lb,LinkList&Lc,>{pa=La->next;pb=Lb->next;//初始化Lc=pc=La;//用La的頭結(jié)點作為Lc的頭結(jié)點Lc->next=NULL;while<pa||pb>{if<!pa>{q=pb;pb=pb->next;}elseif<!pb>{q=pa;pa=pa->next;}elseif<pa->data<=pb->data>{q=pa;pa=pa->next;}else{q=pb;pb=pb->next;}q->next=Lc->next;Lc->next=q;//插入}deleteLb;//釋放Lb的頭結(jié)點}〔3已知兩個鏈表A和B分別表示兩個集合,其元素遞增排列。請設(shè)計算法求出A與B的交集,并存放于A鏈表中。voidMix<LinkList&La,LinkList&Lb,LinkList&Lc,>{pa=la->next;pb=lb->next;∥設(shè)工作指針pa和pb；Lc=pc=La;//用La的頭結(jié)點作為Lc的頭結(jié)點while<pa&&pb>if<pa->data==pb->data>∥交集并入結(jié)果表中。{pc->next=pa;pc=pa;pa=pa->next;u=pb;pb=pb->next;deleteu;}elseif<pa->data<pb->data>{u=pa;pa=pa->next;deleteu;}else{u=pb;pb=pb->next;deleteu;}while<pa>{u=pa;pa=pa->next;deleteu;}∥釋放結(jié)點空間while<pb>{u=pb;pb=pb->next;deleteu;}∥釋放結(jié)點空間pc->next=null;∥置鏈表尾標(biāo)記。deleteLb;∥注：本算法中也可對B表不作釋放空間的處理〔4已知兩個鏈表A和B分別表示兩個集合,其元素遞增排列。請設(shè)計算法求出兩個集合A和B的差集〔即僅由在A中出現(xiàn)而不在B中出現(xiàn)的元素所構(gòu)成的集合,并以同樣的形式存儲,同時返回該集合的元素個數(shù)。voidDifference〔LinkedListA,B,*n∥A和B均是帶頭結(jié)點的遞增有序的單鏈表,分別存儲了一個集合,本算法求兩集合的差集,存儲于單鏈表A中,*n是結(jié)果集合中元素個數(shù),調(diào)用時為0{p=A->next；∥p和q分別是鏈表A和B的工作指針。q=B->next；pre=A；∥pre為A中p所指結(jié)點的前驅(qū)結(jié)點的指針。while〔p!=null&&q!=nullif〔p->data<q->data{pre=p；p=p->next；*n++；}∥A鏈表中當(dāng)前結(jié)點指針后移。elseif〔p->data>q->dataq=q->next；∥B鏈表中當(dāng)前結(jié)點指針后移。else{pre->next=p->next；∥處理A,B中元素值相同的結(jié)點,應(yīng)刪除。u=p；p=p->next；deleteu；}∥刪除結(jié)點〔5設(shè)計算法將一個帶頭結(jié)點的單鏈表A分解為兩個具有相同結(jié)構(gòu)的鏈表B、C,其中B表的結(jié)點為A表中值小于零的結(jié)點,而C表的結(jié)點為A表中值大于零的結(jié)點〔鏈表A的元素類型為整型,要求B、C表利用A表的結(jié)點。〔6設(shè)計一個算法,通過一趟遍歷在單鏈表中確定值最大的結(jié)點。ElemTypeMax<LinkListL>{ if<L->next==NULL>returnNULL; pmax=L->next;//假定第一個結(jié)點中數(shù)據(jù)具有最大值 p=L->next->next; while<p!=NULL>{//如果下一個結(jié)點存在 if<p->data>pmax->data>pmax=p; p=p->next; } returnpmax->data;〔7設(shè)計一個算法,通過遍歷一趟,將鏈表中所有結(jié)點的鏈接方向逆轉(zhuǎn),仍利用原表的存儲空間。voidinverse<LinkList&L>{//逆置帶頭結(jié)點的單鏈表Lp=L->next;L->next=NULL;while<p>{q=p->next;//q指向*p的后繼p->next=L->next;L->next=p;//*p插入在頭結(jié)點之后p=q;}}〔8設(shè)計一個算法,刪除遞增有序鏈表中值大于mink且小于maxk的所有元素〔mink和maxk是給定的兩個參數(shù),其值可以和表中的元素相同,也可以不同。voiddelete<LinkList&L,intmink,intmaxk>{p=L->next;//首元結(jié)點while<p&&p->data<=mink>{pre=p;p=p->next;}//查找第一個值>mink的結(jié)點if<p>{while<p&&p->data<maxk>p=p->next;//查找第一個值≥maxk的結(jié)點q=pre->next;pre->next=p;//修改指針while<q!=p>{s=q->next;deleteq;q=s;}//釋放結(jié)點空間}//if}〔9已知p指向雙向循環(huán)鏈表中的一個結(jié)點,其結(jié)點結(jié)構(gòu)為data、prior、next三個域,寫出算法change<p>,交換p所指向的結(jié)點和它的前綴結(jié)點的順序。知道雙向循環(huán)鏈表中的一個結(jié)點,與前驅(qū)交換涉及到四個結(jié)點〔p結(jié)點,前驅(qū)結(jié)點,前驅(qū)的前驅(qū)結(jié)點,后繼結(jié)點六條鏈。voidExchange〔LinkedListp∥p是雙向循環(huán)鏈表中的一個結(jié)點,本算法將p所指結(jié)點與其前驅(qū)結(jié)點交換。{q=p->llink；q->llink->rlink=p；∥p的前驅(qū)的前驅(qū)之后繼為pp->llink=q->llink；∥p的前驅(qū)指向其前驅(qū)的前驅(qū)。q->rlink=p->rlink；∥p的前驅(qū)的后繼為p的后繼。q->llink=p；∥p與其前驅(qū)交換p->rlink->llink=q；∥p的后繼的前驅(qū)指向原p的前驅(qū)p->rlink=q；∥p的后繼指向其原來的前驅(qū)}∥算法exchange結(jié)束。〔10已知長度為n的線性表A采用順序存儲結(jié)構(gòu),請寫一時間復(fù)雜度為O<n>、空間復(fù)雜度為O<1>的算法,該算法刪除線性表中所有值為item的數(shù)據(jù)元素。[題目分析]在順序存儲的線性表上刪除元素,通常要涉及到一系列元素的移動〔刪第i個元素,第i+1至第n個元素要依次前移。本題要求刪除線性表中所有值為item的數(shù)據(jù)元素,并未要求元素間的相對位置不變。因此可以考慮設(shè)頭尾兩個指針〔i=1,j=n,從兩端向中間移動,凡遇到值item的數(shù)據(jù)元素時,直接將右端元素左移至值為item的數(shù)據(jù)元素位置。voidDelete〔ElemTypeA[],intn∥A是有n個元素的一維數(shù)組,本算法刪除A中所有值為item的元素。{i=1；j=n；∥設(shè)置數(shù)組低、高端指針〔下標(biāo)。while〔i<j{while〔i<j&&A[i]!=itemi++；∥若值不為item,左移指針。if〔i<jwhile〔i<j&&A[j]==itemj--；∥若右端元素值為item,指針左移if〔i<jA[i++]=A[j--]；}[算法討論]因元素只掃描一趟,算法時間復(fù)雜度為O〔n。刪除元素未使用其它輔助空間,最后線性表中的元素個數(shù)是j。第3章棧和隊列習(xí)題1．選擇題〔1若讓元素1,2,3,4,5依次進(jìn)棧,則出棧次序不可能出現(xiàn)在〔種情況。A．5,4,3,2,1B．2,1,5,4,3C．4,3,1,2,5D．2,3,5,4,1〔2若已知一個棧的入棧序列是1,2,3,…,n,其輸出序列為p1,p2,p3,…,pn,若p1=n,則pi為〔。A．iB．n-iC．n-i+1D．不確定〔3數(shù)組Ｑ［ｎ］用來表示一個循環(huán)隊列,ｆ為當(dāng)前隊列頭元素的前一位置,ｒ為隊尾元素的位置,假定隊列中元素的個數(shù)小于ｎ,計算隊列中元素個數(shù)的公式為〔。A．r-fB．<n+f-r>%nC．n+r-fD．〔n+r-f>%n〔4鏈?zhǔn)綏＝Y(jié)點為：<data,link>,top指向棧頂.若想摘除棧頂結(jié)點,并將刪除結(jié)點的值保存到x中,則應(yīng)執(zhí)行操作〔。A．x=top->data;top=top->link； B．top=top->link;x=top->link；C．x=top;top=top->link； D．x=top->link；〔5設(shè)有一個遞歸算法如下??????intfact<intn>{?//n大于等于0???????????if<n<=0>return1;???????????elsereturnn*fact<n-1>;??????}則計算fact<n>需要調(diào)用該函數(shù)的次數(shù)為〔。?A．?n+1?????B．?n-1?????C．n?????D．n+2〔6棧在?〔中有所應(yīng)用。A．遞歸調(diào)用B．函數(shù)調(diào)用C．表達(dá)式求值D．前三個選項都有〔7為解決計算機(jī)主機(jī)與打印機(jī)間速度不匹配問題,通常設(shè)一個打印數(shù)據(jù)緩沖區(qū)。主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū),而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是〔。A．隊列B．棧C．線性表D．有序表〔8設(shè)棧S和隊列Q的初始狀態(tài)為空,元素e1、e2、e3、e4、e5和e6依次進(jìn)入棧S,一個元素出棧后即進(jìn)入Q,若6個元素出隊的序列是e2、e4、e3、e6、e5和e1,則棧S的容量至少應(yīng)該是〔。A．2B．3C．4D．〔9在一個具有n個單元的順序棧中,假設(shè)以地址高端作為棧底,以top作為棧頂指針,則當(dāng)作進(jìn)棧處理時,top的變化為〔。A．top不變B．top=0C．top--D．〔10設(shè)計一個判別表達(dá)式中左,右括號是否配對出現(xiàn)的算法,采用〔數(shù)據(jù)結(jié)構(gòu)最佳。A．線性表的順序存儲結(jié)構(gòu)B．隊列C.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)D.棧〔11用鏈接方式存儲的隊列,在進(jìn)行刪除運(yùn)算時〔。A.僅修改頭指針B.僅修改尾指針C.頭、尾指針都要修改D.頭、尾指針可能都要修改〔12循環(huán)隊列存儲在數(shù)組A[0..m]中,則入隊時的操作為〔。A.rear=rear+1B.rear=<rear+1>%<m-1>C.rear=<rear+1>%mD.rear=<rear+1>%<m+1>〔13最大容量為n的循環(huán)隊列,隊尾指針是rear,隊頭是front,則隊空的條件是〔。A.<rear+1>%n==frontB.rear==frontC．rear+1==frontD.<rear-l>%n==front〔14棧和隊列的共同點是〔。A.都是先進(jìn)先出B.都是先進(jìn)后出C.只允許在端點處插入和刪除元素D.沒有共同點〔15一個遞歸算法必須包括〔。A.遞歸部分B.終止條件和遞歸部分C.迭代部分D.終止條件和迭代部分〔2回文是指正讀反讀均相同的字符序列,如"abba"和"abdba"均是回文,但"good"不是回文。試寫一個算法判定給定的字符向量是否為回文。<提示：將一半字符入棧>?根據(jù)提示,算法可設(shè)計為：

//以下為順序棧的存儲結(jié)構(gòu)定義

#defineStackSize100//假定預(yù)分配的?？臻g最多為100個元素

typedefcharDataType;//假定棧元素的數(shù)據(jù)類型為字符

typedefstruct{

DataTypedata[StackSize];

inttop;

}SeqStack;?

intIsHuiwen<char*t>

{//判斷t字符向量是否為回文,若是,返回1,否則返回0

SeqStacks;

inti,len;

chartemp;

InitStack<&s>;

len=strlen<t>;//求向量長度

for<i=0;i<len/2;i++>//將一半字符入棧

Push<&s,t[i]>;

while<!EmptyStack<&s>>

{//每彈出一個字符與相應(yīng)字符比較

temp=Pop<&s>;

if<temp!=S[i]>?return0;//不等則返回0

elsei++;

}?

return1;//比較完畢均相等則返回1

}〔3設(shè)從鍵盤輸入一整數(shù)的序列：a1,a2,a3,…,an,試編寫算法實現(xiàn)：用棧結(jié)構(gòu)存儲輸入的整數(shù),當(dāng)ai≠-1時,將ai進(jìn)棧；當(dāng)ai=-1時,輸出棧頂整數(shù)并出棧。算法應(yīng)對異常情況〔入棧滿等給出相應(yīng)的信息。#definemaxsize?？臻g容量voidInOutS<ints[maxsize]>//s是元素為整數(shù)的棧,本算法進(jìn)行入棧和退棧操作。{inttop=0;//top為棧頂指針,定義top=0時為棧空。for<i=1;i<=n;i++>//n個整數(shù)序列作處理。{scanf<"%d",&x>;//從鍵盤讀入整數(shù)序列。if<x!=-1>//讀入的整數(shù)不等于-1時入棧。if<top==maxsize-1>{printf<"棧滿\n">;exit<0>;}elses[++top]=x;//x入棧。else//讀入的整數(shù)等于-1時退棧。{if<top==0>{printf<"?？誠n">;exit<0>;}elseprintf<"出棧元素是%d\n",s[top--]>；}}}//算法結(jié)束?！?從鍵盤上輸入一個后綴表達(dá)式,試編寫算法計算表達(dá)式的值。規(guī)定：逆波蘭表達(dá)式的長度不超過一行,以$符作為輸入結(jié)束,操作數(shù)之間用空格分隔,操作符只可能有+、-、*、/四種運(yùn)算。例如：23434+2*$。[題目分析]逆波蘭表達(dá)式<即后綴表達(dá)式>求值規(guī)則如下：設(shè)立運(yùn)算數(shù)棧OPND,對表達(dá)式從左到右掃描<讀入>,當(dāng)表達(dá)式中掃描到數(shù)時,壓入OPND棧。當(dāng)掃描到運(yùn)算符時,從OPND退出兩個數(shù),進(jìn)行相應(yīng)運(yùn)算,結(jié)果再壓入OPND棧。這個過程一直進(jìn)行到讀出表達(dá)式結(jié)束符$,這時OPND棧中只有一個數(shù),就是結(jié)果。floatexpr<>//從鍵盤輸入逆波蘭表達(dá)式,以‘$’表示輸入結(jié)束,本算法求逆波蘭式表達(dá)式的值。｛floatOPND[30];//OPND是操作數(shù)棧。init<OPND>;//兩棧初始化。floatnum=0.0;//數(shù)字初始化。scanf<"%c",&x>;//x是字符型變量。while<x!=’$’>{switch{case‘0’<=x<=’9’:while<<x>=’0’&&x<=’9’>||x==’.’>//拼數(shù)if<x!=’.’>//處理整數(shù){num=num*10+〔ord<x>-ord<‘0’>;scanf<"%c",&x>;}else//處理小數(shù)部分。{scale=10.0;scanf<"%c",&x>;while<x>=’0’&&x<=’9’>{num=num+<ord<x>-ord<‘0’>/scale;scale=scale*10;scanf<"%c",&x>;}}//elsepush<OPND,num>;num=0.0;//數(shù)壓入棧,下個數(shù)初始化casex=‘’:break;//遇空格,繼續(xù)讀下一個字符。casex=‘+’:push<OPND,pop<OPND>+pop<OPND>>;break;casex=‘-’:x1=pop<OPND>;x2=pop<OPND>;push<OPND,x2-x1>;break;casex=‘*’:push<OPND,pop<OPND>*pop<OPND>>;break;casex=‘/’:x1=pop<OPND>;x2=pop<OPND>;push<OPND,x2/x1>;break;default://其它符號不作處理。}//結(jié)束switchscanf<"%c",&x>;//讀入表達(dá)式中下一個字符。}//結(jié)束while〔x！=‘$’printf<"后綴表達(dá)式的值為%f",pop<OPND>>;}//算法結(jié)束。[算法討論]假設(shè)輸入的后綴表達(dá)式是正確的,未作錯誤檢查。算法中拼數(shù)部分是核心。若遇到大于等于‘0’且小于等于‘9’的字符,認(rèn)為是數(shù)。這種字符的序號減去字符‘0’的序號得出數(shù)。對于整數(shù),每讀入一個數(shù)字字符,前面得到的部分?jǐn)?shù)要乘上10再加新讀入的數(shù)得到新的部分?jǐn)?shù)。當(dāng)讀到小數(shù)點,認(rèn)為數(shù)的整數(shù)部分已完,要接著處理小數(shù)部分。小數(shù)部分的數(shù)要除以10〔或10的冪數(shù)變成十分位,百分位,千分位數(shù)等等,與前面部分?jǐn)?shù)相加。在拼數(shù)過程中,若遇非數(shù)字字符,表示數(shù)已拼完,將數(shù)壓入棧中,并且將變量num恢復(fù)為0,準(zhǔn)備下一個數(shù)。這時對新讀入的字符進(jìn)入‘+’、‘-’、‘*’、‘/’及空格的判斷,因此在結(jié)束處理數(shù)字字符的case〔5假設(shè)以I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空,入棧和出棧的操作序列可表示為僅由I和O組成的序列,稱可以操作的序列為合法序列,否則稱為非法序列。=1\*GB3①下面所示的序列中哪些是合法的？=2\*GB3②通過對=1\*GB3①的分析,寫出一個算法,判定所給的操作序列是否合法。若合法,返回true,否則返回false〔假定被判定的操作序列已存入一維數(shù)組中。=1\*GB3①A和D是合法序列,B和C是非法序列。=2\*GB3②設(shè)被判定的操作序列已存入一維數(shù)組A中。intJudge<charA[]>//判斷字符數(shù)組A中的輸入輸出序列是否是合法序列。如是,返回true,否則返回false。{i=0;//i為下標(biāo)。j=k=0;//j和k分別為I和字母O的的個數(shù)。while<A[i]!=‘\0’>//當(dāng)未到字符數(shù)組尾就作。{switch<A[i]>{case‘I’:j++;break;//入棧次數(shù)增1。case‘O’:k++;if<k>j>{printf<"序列非法\n">；exit<0>;}}i++;//不論A[i]是‘I’或‘O’,指針i均后移。}if<j!=k>{printf<"序列非法\n">；return<false>;}else{printf<"序列合法\n">；return<true>;}}//算法結(jié)束。[算法討論]在入棧出棧序列〔即由‘I’和‘O’組成的字符串的任一位置,入棧次數(shù)〔‘I’的個數(shù)都必須大于等于出棧次數(shù)〔即‘O’的個數(shù),否則視作非法序列,立即給出信息,退出算法。整個序列〔即讀到字符數(shù)組中字符串的結(jié)束標(biāo)記‘\0’<6假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列,并且只設(shè)一個指針指向隊尾元素站點<注意不設(shè)頭指針>,試編寫相應(yīng)的置空隊、判隊空、入隊和出隊等算法。?算法如下：

//先定義鏈隊結(jié)構(gòu):

typedefstructqueuenode{

Datatypedata;

structqueuenode*next;

}QueueNode;//以上是結(jié)點類型的定義

typedefstruct{

queuenode*rear;

}LinkQueue;//只設(shè)一個指向隊尾元素的指針

<1>置空隊

voidInitQueue<LinkQueue*Q>

{//置空隊：就是使頭結(jié)點成為隊尾元素

QueueNode*s;

Q->rear=Q->rear->next;//將隊尾指針指向頭結(jié)點

while<Q->rear!=Q->rear->next>//當(dāng)隊列非空,將隊中元素逐個出隊

{s=Q->rear->next;

Q->rear->next=s->next;

free<s>;

}//回收結(jié)點空間

}

<2>判隊空?

intEmptyQueue<LinkQueue*Q>

{//判隊空

//當(dāng)頭結(jié)點的next指針指向自己時為空隊

returnQ->rear->next->next==Q->rear->next;

}

<3>入隊

voidEnQueue<LinkQueue*Q,Datatypex>

{//入隊

//也就是在尾結(jié)點處插入元素

QueueNode*p=<QueueNode*>malloc<sizeof<QueueNode>>;//申請新結(jié)點

p->data=x;p->next=Q->rear->next;//初始化新結(jié)點并鏈入

Q-rear->next=p;?

Q->rear=p;//將尾指針移至新結(jié)點

}

<4>出隊

DatatypeDeQueue<LinkQueue*Q>

{//出隊,把頭結(jié)點之后的元素摘下

Datatypet;

QueueNode*p;

if<EmptyQueue<Q>>

Error<"Queueunderflow">;

p=Q->rear->next->next;//p指向?qū)⒁碌慕Y(jié)點

x=p->data;//保存結(jié)點中數(shù)據(jù)

if<p==Q->rear>

{//當(dāng)隊列中只有一個結(jié)點時,p結(jié)點出隊后,要將隊尾指針指向頭結(jié)點

Q->rear=Q->rear->next;Q->rear->next=p->next;}

else?

Q->rear->next->next=p->next;//摘下結(jié)點p

free<p>;//釋放被刪結(jié)點

returnx;

}〔7假設(shè)以數(shù)組Q[m]存放循環(huán)隊列中的元素,同時設(shè)置一個標(biāo)志tag,以tag==0和tag==1來區(qū)別在隊頭指針<front>和隊尾指針<rear>相等時,隊列狀態(tài)為"空"還是"滿"。試編寫與此結(jié)構(gòu)相應(yīng)的插入<enqueue>和刪除<dlqueue>算法。[解答]循環(huán)隊列類定義 #include<assert.h> template<classType>classQueue{ //循環(huán)隊列的類定義 public:Queue<int=10>; ~Queue<>{delete[]Q;}voidEnQueue<Type&item>;TypeDeQueue<>;TypeGetFront<>;voidMakeEmpty<>{front=rear=tag=0;} //置空隊列intIsEmpty<>const{returnfront==rear&&tag==0;} //判隊列空否intIsFull<>const{returnfront==rear&&tag==1;} //判隊列滿否 private:intrear,front,tag; //隊尾指針、隊頭指針和隊滿標(biāo)志Type*Q; //存放隊列元素的數(shù)組intm; //隊列最大可容納元素個數(shù) }構(gòu)造函數(shù) template<classType>Queue<Type>::Queue<intsz>:rear<0>,front<0>,tag<0>,m<sz>{ //建立一個最大具有m個元素的空隊列。Q=newType[m]; //創(chuàng)建隊列空間assert<Q!=0>; //斷言:動態(tài)存儲分配成功與否 }插入函數(shù)template<classType>voidQueue<Type>::EnQueue<Type&item>{ assert<!IsFull<>>;//判隊列是否不滿,滿則出錯處理rear=<rear+1>%m;//隊尾位置進(jìn)1,隊尾指針指示實際隊尾位置Q[rear]=item; //進(jìn)隊列tag=1; //標(biāo)志改1,表示隊列不空 }刪除函數(shù)template<classType>TypeQueue<Type>::DeQueue<>{ assert<!IsEmpty<>>;//判斷隊列是否不空,空則出錯處理front=<front+1>%m; //隊頭位置進(jìn)1,隊頭指針指示實際隊頭的前一位置tag=0; //標(biāo)志改0,表示棧不滿returnQ[front]; //返回原隊頭元素的值}讀取隊頭元素函數(shù)template<classType>TypeQueue<Type>::GetFront<>{ assert<!IsEmpty<>>;//判斷隊列是否不空,空則出錯處理returnQ[<front+1>%m]; //返回隊頭元素的值}<8如果允許在循環(huán)隊列的兩端都可以進(jìn)行插入和刪除操作。要求：=1\*GB3①寫出循環(huán)隊列的類型定義；=2\*GB3②寫出"從隊尾刪除"和"從隊頭插入"的算法。[題目分析]用一維數(shù)組v[0..M-1]實現(xiàn)循環(huán)隊列,其中M是隊列長度。設(shè)隊頭指針front和隊尾指針rear,約定front指向隊頭元素的前一位置,rear指向隊尾元素。定義front=rear時為隊空,<rear+1>%m=front為隊滿。約定隊頭端入隊向下標(biāo)小的方向發(fā)展,隊尾端入隊向下標(biāo)大的方向發(fā)展?！?#defineM隊列可能達(dá)到的最大長度typedefstruct{elemtpdata[M];intfront,rear;}cycqueue;〔2elemtpdelqueue<cycqueueQ>//Q是如上定義的循環(huán)隊列,本算法實現(xiàn)從隊尾刪除,若刪除成功,返回被刪除元素,否則給出出錯信息。 {if<Q.front==Q.rear>{printf<"隊列空">;exit<0>;} Q.rear=<Q.rear-1+M>%M;//修改隊尾指針。return<Q.data[<Q.rear+1+M>%M]>;//返回出隊元素。}//從隊尾刪除算法結(jié)束voidenqueue<cycqueueQ,elemtpx>//Q是順序存儲的循環(huán)隊列,本算法實現(xiàn)"從隊頭插入"元素x。{if<Q.rear==<Q.front-1+M>%M>{printf<"隊滿";exit<0>;>Q.data[Q.front]=x;//x入隊列Q.front=<Q.front-1+M>%M;//修改隊頭指針。}//結(jié)束從隊頭插入算法?！?已知Ackermann函數(shù)定義如下:=1\*GB3①寫出計算Ack<m,n>的遞歸算法,并根據(jù)此算法給出出Ack<2,1>的計算過程。=2\*GB3②寫出計算Ack<m,n>的非遞歸算法。intAck<intm,n>{if<m==0>return<n+1>;elseif<m!=0&&n==0>return<Ack<m-1,1>>;elsereturn<Ack<m-1,Ack<m,m-1>>;}//算法結(jié)束〔1Ack<2,1>的計算過程Ack<2,1>=Ack<1,Ack<2,0>>//因m<>0,n<>0而得=Ack<1,Ack<1,1>>//因m<>0,n=0而得=Ack<1,Ack<0,Ack<1,0>>>//因m<>0,n<>0而得=Ack<1,Ack<0,Ack<0,1>>>//因m<>0,n=0而得=Ack<1,Ack<0,2>>//因m=0而得=Ack<1,3>//因m=0而得=Ack<0,Ack<1,2>>//因m<>0,n<>0而得=Ack<0,Ack<0,Ack<1,1>>>//因m<>0,n<>0而得=Ack<0,Ack<0,Ack<0,Ack<1,0>>>>//因m<>0,n<>0而得=Ack<0,Ack<0,Ack<0,Ack<0,1>>>>//因m<>0,n=0而得=Ack<0,Ack<0,Ack<0,2>>>//因m=0而得=Ack<0,Ack<0,3>>//因m=0而得=Ack<0,4>//因n=0而得=5//因n=0而得〔2intAckerman<intm,intn>{intakm[M][N];inti,j;for<j=0;j<N;j++>akm[0][j];=j+1;for<i=1;i<m;i++>{akm[i][0]=akm[i-1][1];for<j=1;j<N;j++>akm[i][j]=akm[i-1][akm[i][j-1]];}return<akm[m][n]>;}//算法結(jié)束〔10已知f為單鏈表的表頭指針,鏈表中存儲的都是整型數(shù)據(jù),試寫出實現(xiàn)下列運(yùn)算的遞歸算法：=1\*GB3①求鏈表中的最大整數(shù)；=2\*GB3②求鏈表的結(jié)點個數(shù)；=3\*GB3③求所有整數(shù)的平均值。#include<iostream.h>//定義在頭文件"RecurveList.h"中classList; classListNode{ //鏈表結(jié)點類friendclassList;private:intdata; //結(jié)點數(shù)據(jù)ListNode*link; //結(jié)點指針ListNode<constintitem>:data<item>,link<NULL>{} //構(gòu)造函數(shù)};classList{ //鏈表類private:ListNode*first,current;intMax<ListNode*f>;intNum<ListNode*f>;floatAvg<ListNode*f,int&n>;public:List<>:first<NULL>,current<NULL>{} //構(gòu)造函數(shù) ~List<>{} //析構(gòu)函數(shù)ListNode*NewNode<constintitem>; //創(chuàng)建鏈表結(jié)點,其值為itemvoidNewList<constintretvalue>; //建立鏈表,以輸入retvalue結(jié)束voidPrintList<>; //輸出鏈表所有結(jié)點數(shù)據(jù)intGetMax<>{returnMax<first>;} //求鏈表所有數(shù)據(jù)的最大值intGetNum<>{returnNum<first>;} //求鏈表中數(shù)據(jù)個數(shù)floatGetAvg<>{returnAvg<first>;} //求鏈表所有數(shù)據(jù)的平均值}; ListNode*List::NewNode<constintitem>{ //創(chuàng)建新鏈表結(jié)點ListNode*newnode=newListNode<item>;returnnewnode;}voidList::NewList<constintretvalue>{ //建立鏈表,以輸入retvalue結(jié)束first=NULL;intvalue;ListNode*q;cout<<"Inputyourdata:\n"; //提示cin>>value; //輸入while<value!=retvalue>{//輸入有效q=NewNode<value>; //建立包含value的新結(jié)點if<first==NULL>first=current=q; //空表時,新結(jié)點成為鏈表第一個結(jié)點else{current->link=q;current=q;} //非空表時,新結(jié)點鏈入鏈尾cin>>value; //再輸入}current->link=NULL; //鏈尾封閉}voidList::PrintList<>{ //輸出鏈表cout<<"\nTheListis:\n";ListNode*p=first;while<p!=NULL>{ cout<<p->data<<'';p=p->link;} cout<<‘\n’;}intList::Max<ListNode*f>{ //遞歸算法:求鏈表中的最大值if<f->link==NULL>returnf->data; //遞歸結(jié)束條件 inttemp=Max<f->link>; //在當(dāng)前結(jié)點的后繼鏈表中求最大值if<f->data>temp>returnf->data; //如果當(dāng)前結(jié)點的值還要大,返回當(dāng)前檢點值 elsereturntemp; //否則返回后繼鏈表中的最大值}intList::Num<ListNode*f>{ //遞歸算法:求鏈表中結(jié)點個數(shù) if<f==NULL>return0; //空表,返回0return1+Num<f->link>; //否則,返回后繼鏈表結(jié)點個數(shù)加1}floatList::Avg<ListNode*f,int&n>{//遞歸算法:求鏈表中所有元素的平均值if<f->link==NULL> //鏈表中只有一個結(jié)點,遞歸結(jié)束條件{n=1;return<float><f->data>;}else{floatSum=Avg<f->link,n>*n;n++;return<f->data+Sum>/n;}}#include"RecurveList.h" //定義在主文件中intmain<intargc,char*argv[]>{Listtest;intfinished;cout<<"輸入建表結(jié)束標(biāo)志數(shù)據(jù)：";cin>>finished; //輸入建表結(jié)束標(biāo)志數(shù)據(jù)test.NewList<finished>; //建立鏈表test.PrintList<>; //打印鏈表cout<<"\nTheMaxis:"<<test.GetMax<>;cout<<"\nTheNumis:"<<test.GetNum<>;cout<<"\nTheAveis:"<<test.GetAve<><<'\n'; printf<"HelloWorld!\n">;return0;}第4章串、數(shù)組和廣義表習(xí)題1．選擇題〔1串是一種特殊的線性表,其特殊性體現(xiàn)在〔。A．可以順序存儲B．?dāng)?shù)據(jù)元素是一個字符C．可以鏈?zhǔn)酱鎯．?dāng)?shù)據(jù)元素可以是多個字符若〔2串下面關(guān)于串的的敘述中,〔是不正確的？A．串是字符的有限序列B．空串是由空格構(gòu)成的串C．模式匹配是串的一種重要運(yùn)算D．串既可以采用順序存儲,也可以采用鏈?zhǔn)酱鎯Α?串"ababaaababaa"的next數(shù)組為〔。A．．．0456D．〔4串"ababaabab"的nextval為〔。A．B．C．．010101011〔5串的長度是指〔。A．串中所含不同字母的個數(shù)B．串中所含字符的個數(shù)C．串中所含不同字符的個數(shù)D．串中所含非空格字符的個數(shù)〔6假設(shè)以行序為主序存儲二維數(shù)組A=array[1..100,1..100],設(shè)每個數(shù)據(jù)元素占2個存儲單元,基地址為10,則LOC[5,5]=〔。A．808B．818C．1010D．〔7設(shè)有數(shù)組A[i,j],數(shù)組的每個元素長度為3字節(jié),i的值為1到8,j的值為1到10,數(shù)組從內(nèi)存首地址BA開始順序存放,當(dāng)用以列為主存放時,元素A[5,8]的存儲首地址為〔。A．BA+141B．BA+180C．BA+222D．〔8設(shè)有一個10階的對稱矩陣A,采用壓縮存儲方式,以行序為主存儲,a11為第一元素,其存儲地址為1,每個元素占一個地址空間,則a85的地址為〔。A．13B．33C．18D．〔9若對n階對稱矩陣A以行序為主序方式將其下三角形的元素<包括主對角線上所有元素>依次存放于一維數(shù)組B[1..<n<n+1>>/2]中,則在B中確定aij〔i<j的位置k的關(guān)系為〔。A．i*<i-1>/2+jB．j*<j-1>/2+iC．i*<i+1>/2+jD．j*<j+1>/2+i〔10A[N,N]是對稱矩陣,將下面三角〔包括對角線以行序存儲到一維數(shù)組T[N<N+1>/2]中,則對任一上三角元素a[i][j]對應(yīng)T[k]的下標(biāo)k是〔。A．i<i-1>/2+jB．j<j-1>/2+iC．i<j-i>/2+1D．j<i-1>/2+1〔11設(shè)二維數(shù)組A[1..m,1..n]〔即m行n列按行存儲在數(shù)組B[1..m*n]中,則二維數(shù)組元素A[i,j]在一維數(shù)組B中的下標(biāo)為〔。A．<i-1>*n+jB．<i-1>*n+j-1C．i*<j-1>D．j*m+i-1〔12數(shù)組A[0..4,-1..-3,5..7]中含有元素的個數(shù)〔。A．55B．45C．36D．〔13廣義表A=<a,b,<c,d>,<e,<f,g>>>,則Head<Tail<Head<Tail<Tail<A>>>>>的值為〔。A．<g>B．<d>C．cD．d〔14廣義表<<a,b,c,d>>的表頭是〔,表尾是〔。A．a(chǎn)B．<>C．<a,b,c,d>D．<b,c,d>〔15設(shè)廣義表L=<<a,b,c>>,則L的長度和深度分別為〔。A．1和1B．1和3C．1和2D．2和〔1已知模式串t=‘a(chǎn)bcaabbabcab’寫出用KMP法求得的每個字符對應(yīng)的next和nextval函數(shù)值。模式串t的next和nextval值如下：jt串a(chǎn)bcaabbabcabnext[j]nextval[j]〔2設(shè)目標(biāo)為t="abcaabbabcabaacbacba",模式為p="abcabaa"=1\*GB3①計算模式p的naxtval函數(shù)值；=2\*GB3②不寫出算法,只畫出利用KMP算法進(jìn)行模式匹配時每一趟的匹配過程。=1\*GB3①p的nextval函數(shù)值為0110132?！瞤的next函數(shù)值為0111232。=2\*GB3②利用KMP<改進(jìn)的nextval>算法,每趟匹配過程如下：第一趟匹配：abcaabbabcabaacbacbaabcab<i=5,j=5>第二趟匹配：abcaabbabcabaacbacbaabc<i=7,j=3>第三趟匹配：abcaabbabcabaacbacbaa<i=7,j=1>第四趟匹配：abcaabbabcabaacbacba<成功>abcabaa<i=15,j=8>〔3數(shù)組A中,每個元素A[i,j]的長度均為32個二進(jìn)位,行下標(biāo)從-1到9,列下標(biāo)從1到11,從首地址S開始連續(xù)存放主存儲器中,主存儲器字長為16位。求：=1\*GB3①存放該數(shù)組所需多少單元？=2\*GB3②存放數(shù)組第4列所有元素至少需多少單元？=3\*GB3③數(shù)組按行存放時,元素A[7,4]的起始地址是多少？=4\*GB3④數(shù)組按列存放時,元素A[4,7]的起始地址是多少？每個元素32個二進(jìn)制位,主存字長16位,故每個元素占2個字長,行下標(biāo)可平移至1到11。〔1242〔222〔3s+182〔4s+142<4>請將香蕉banana用工具H<>—Head<>,T<>—Tail<>從L中取出。L=<apple,<orange,<strawberry,<banana>>,peach>,pear>H〔H〔T〔H〔T〔H〔T〔L〔5寫一個算法統(tǒng)計在輸入字符串中各個不同字符出現(xiàn)的頻度并將結(jié)果存入文件〔字符串中的合法字符為A-Z這26個字母和0-9這10個數(shù)字。voidCount〔//統(tǒng)計輸入字符串中數(shù)字字符和字母字符的個數(shù)。｛inti,num[36]；charch；for〔i＝0；i<36；i++num[i]＝０；//初始化while〔〔ch＝getchar〔!=‘#’//‘#’表示輸入字符串結(jié)束。if〔‘0’<=ch<=‘9’｛i=ch－48;num[i]++；｝//數(shù)字字符elseif〔‘A’<=ch<=‘Z’｛i=ch-65+10;num[i]++；｝//字母字符for〔i=0；i<10；i++//輸出數(shù)字字符的個數(shù)printf〔"數(shù)字％d的個數(shù)＝％d\n",i,num[i]；for〔i＝10；i<36；i++//求出字母字符的個數(shù)printf〔"字母字符％c的個數(shù)＝％d\n",i＋55,num[i]；｝//算法結(jié)束?！?寫一個遞歸算法來實現(xiàn)字符串逆序存儲,要求不另設(shè)串存儲空間。[題目分析]實現(xiàn)字符串的逆置并不難,但本題"要求不另設(shè)串存儲空間"來實現(xiàn)字符串逆序存儲,即第一個輸入的字符最后存儲,最后輸入的字符先存儲,使用遞歸可容易做到。voidInvertStore<charA[]>//字符串逆序存儲的遞歸算法。{charch;staticinti=0;//需要使用靜態(tài)變量scanf<"%c",&ch>;if<ch!='.'>//規(guī)定'.'是字符串輸入結(jié)束標(biāo)志 {InvertStore<A>; A[i++]=ch;//字符串逆序存儲 }A[i]='\0';//字符串結(jié)尾標(biāo)記}//結(jié)束算法InvertStore。〔7編寫算法,實現(xiàn)下面函數(shù)的功能。函數(shù)voidinsert<char*s,char*t,intpos>將字符串t插入到字符串s中,插入位置為pos。假設(shè)分配給字符串s的空間足夠讓字符串t插入。〔說明：不得使用任何庫函數(shù)[題目分析]本題是字符串的插入問題,要求在字符串s的pos位置,插入字符串t。首先應(yīng)查找字符串s的pos位置,將第pos個字符到字符串s尾的子串向后移動字符串t的長度,然后將字符串t復(fù)制到字符串s的第pos位置后。對插入位置pos要驗證其合法性,小于1或大于串s的長度均為非法,因題目假設(shè)給字符串s的空間足夠大,故對插入不必判溢出。voidinsert<char*s,char*t,intpos>//將字符串t插入字符串s的第pos個位置。{inti=1,x=0;char*p=s,*q=t;//p,q分別為字符串s和t的工作指針if<pos<1>{printf<"pos參數(shù)位置非法\n">;exit<0>;}while<*p!=’\0’&&i<pos>{p++;i++;}//查pos位置//若pos小于串s長度,則查到pos位置時,i=pos。if<*p=='/0'>{printf<"%d位置大于字符串s的長度",pos>;exit<0>;}else//查找字符串的尾while<*p!='/0'>{p++;i++;}//查到尾時,i為字符‘\0’的下標(biāo),p也指向‘\0while<*q!='\0'>{q++;x++;}//查找字符串t的長度x,循環(huán)結(jié)束時q指向'\0'。for<j=i;j>=pos;j-->{*<p+x>=*p;p--;}//串s的pos后的子串右移,空出串t的位置。q--;//指針q回退到串t的最后一個字符for<j=1;j<=x;j++>*p--=*q--;//將t串插入到s的pos位置上[算法討論]串s的結(jié)束標(biāo)記<'\0'>也后移了,而串t的結(jié)尾標(biāo)記不應(yīng)插入到s中?！?已知字符串S1中存放一段英文,寫出算法format<s1,s2,s3,n>,將其按給定的長度n格式化成兩端對齊的字符串S2,其多余的字符送S3。[題目分析]本題要求字符串s1拆分成字符串s2和字符串s3,要求字符串s2"按給定長度n格式化成兩端對齊的字符串",即長度為n且首尾字符不得為空格字符。算法從左到右掃描字符串s1,找到第一個非空格字符,計數(shù)到n,第n個拷入字符串s2的字符不得為空格,然后將余下字符復(fù)制到字符串s3中。voidformat<char*s1,*s2,*s3>//將字符串s1拆分成字符串s2和字符串s3,要求字符串s2是長n且兩端對齊{char*p=s1,*q=s2;inti=0;while<*p!='\0'&&*p==''>p++;//濾掉s1左端空格if<*p=='\0'>{printf<"字符串s1為空串或空格串\n">;exit<0>; }while<*p!='\0'&&i<n>{*q=*p;q++;p++;i++;}//字符串s1向字符串s2中復(fù)制if<*p=='\0'>{printf<"字符串s1沒有%d個有效字符\n",n>;exit<0>;}if<*<--q>==''>//若最后一個字符為空格,則需向后找到第一個非空格字符 {p--;//p指針也后退while<*p==''&&*p!='\0'>p++;//往后查找一個非空格字符作串s2的尾字符if<*p=='\0'>{printf<"s1串沒有%d個兩端對齊的字符串\n",n>;exit<0>; } *q=*p;//字符串s2最后一個非空字符 *<++q>='\0';//置s2字符串結(jié)束標(biāo)記 } *q=s3;p++;//將s1串其余部分送字符串s3。while<*p!='\0'>{*q=*p;q++;p++;} *q='\0';//置串s3結(jié)束標(biāo)記}<9>設(shè)二維數(shù)組a[1..m,1..n]含有m*n個整數(shù)。=1\*GB3①寫一個算法判斷a中所有元素是否互不相同?輸出相關(guān)信息<yes/no>；=2\*GB3②試分析算法的時間復(fù)雜度。[題目分析]判斷二維數(shù)組中元素是否互不相同,只有逐個比較,找到一對相等的元素,就可結(jié)論為不是互不相同。如何達(dá)到每個元素同其它元素比較一次且只一次？在當(dāng)前行,每個元素要同本行后面的元素比較一次〔下面第一個循環(huán)控制變量p的for循環(huán),然后同第i+1行及以后各行元素比較一次,這就是循環(huán)控制變量k和p的二層for循環(huán)。intJudgEqual<inga[m][n],intm,n>//判斷二維數(shù)組中所有元素是否互不相同,如是,返回1；否則,返回0。{for<i=0;i<m;i++>for<j=0;j<n-1;j++>{for<p=j+1;p<n;p++>//和同行其它元素比較if<a[i][j]==a[i][p]>{printf<"no">;return<0>;}//只要有一個相同的,就結(jié)論不是互不相同for<k=i+1;k<m;k++>//和第i+1行及以后元素比較for<p=0;p<n;p++>if<a[i][j]==a[k][p]>{printf<"no">;return<0>;}}//for<j=0;j<n-1;j++>printf<yes">;return<1>;//元素互不相同}//算法JudgEqual結(jié)束〔2二維數(shù)組中的每一個元素同其它元素都比較一次,數(shù)組中共m*n個元素,第1個元素同其它m*n-1個元素比較,第2個元素同其它m*n-2個元素比較,……,第m*n-1個元素同最后一個元素<m*n>比較一次,所以在元素互不相等時總的比較次數(shù)為<m*n-1>+<m*n-2>+…+2+1=〔m*n<m*n-1>/2。在有相同元素時,可能第一次比較就相同,也可能最后一次比較時相同,設(shè)在<m*n-1>個位置上均可能相同,這時的平均比較次數(shù)約為〔m*n<m*n-1>/4,總的時間復(fù)雜度是O<n4>。<10>設(shè)任意n個整數(shù)存放于數(shù)組A<1:n>中,試編寫算法,將所有正數(shù)排在所有負(fù)數(shù)前面〔要求算法復(fù)雜性為0<n>。[題目分析]本題屬于排序問題,只是排出正負(fù),不排出大小?？稍跀?shù)組首尾設(shè)兩個指針i和j,i自小至大搜索到負(fù)數(shù)停止,j自大至小搜索到正數(shù)停止。然后i和j所指數(shù)據(jù)交換,繼續(xù)以上過程,直到i=j為止。voidArrange<intA[],intn>//n個整數(shù)存于數(shù)組A中,本算法將數(shù)組中所有正數(shù)排在所有負(fù)數(shù)的前面{inti=0,j=n-1,x;//用類C編寫,數(shù)組下標(biāo)從0開始while<i<j>{while<i<j&&A[i]>0>i++;while<i<j&&A[j]<0>j--;if<i<j>{x=A[i];A[i++]=A[j];A[j--]=x;}//交換A[i]與A[j]}}//算法Arrange結(jié)束.[算法討論]對數(shù)組中元素各比較一次,比較次數(shù)為n。最佳情況<已排好,正數(shù)在前,負(fù)數(shù)在后>不發(fā)生交換,最差情況<負(fù)數(shù)均在正數(shù)前面>發(fā)生n/2次交換。用類c編寫,數(shù)組界偶是0..n-1。空間復(fù)雜度為O<1>.第5章樹和二叉樹A．Ｂ．C．有多種,但根結(jié)點都沒有左孩子Ｄ．有多種,但根結(jié)點都沒有右孩子由3個結(jié)點可以構(gòu)造出多少種不同的二叉樹？〔A．2B．3C．4D．一棵完全二叉樹上有1001個結(jié)點,其中葉子結(jié)點的個數(shù)是〔A．250B．500C．254D．501一個具有1025個結(jié)點的二叉樹的高h(yuǎn)為〔A．11B．10C．11至1025之間D．10至1024深度為h的滿m叉樹的第k層有〔個結(jié)點。<1=<k=<h>A．mk-1B．mk-1C．mh-1D．mh-1利用二叉鏈表存儲樹,則根結(jié)點的右指針是〔A．指向最左孩子B．指向最右孩子C．空D．非空對二叉樹的結(jié)點從1開始進(jìn)行連續(xù)編號,要求每個結(jié)點的編號大于其左、右孩子的編號,同一結(jié)點的左右孩子中,其左孩子的編號小于其右孩子的編號,可采用〔遍歷實現(xiàn)編號。A．先序B.中序C.后序D.從根開始按層次遍歷若二叉樹采用二叉鏈表存儲結(jié)構(gòu),要交換其所有分支結(jié)點左、右子樹的位置,利用〔遍歷方法最合適。A．前序B．中序C．后序D．按層次在下列存儲形式中,〔不是樹的存儲形式？A．雙親表示法B．孩子鏈表表示法C．孩子兄弟表示法D．順序存儲表示法一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反,則該二叉樹一定滿足〔A．所有的結(jié)點均無左孩子B．所有的結(jié)點均無右孩子C．只有一個葉子結(jié)點D．是任意一棵二叉樹某二叉樹的前序序列和后序序列正好相反,則該二叉樹一定是〔的二叉樹。A．空或只有一個結(jié)點B．任一結(jié)點無左子樹C．高度等于其結(jié)點數(shù)D．任一結(jié)點無右子樹若X是二叉中序線索樹中一個有左孩子的結(jié)點,且X不為根,則X的前驅(qū)為〔A．X的雙親B．X的右子樹中最左的結(jié)點C．X的左子樹中最右結(jié)點D．X的左子樹中最右葉結(jié)點引入二叉線索樹的目的是〔A．加快查找結(jié)點的前驅(qū)或后繼的速度B．為了能在二叉樹中方便的進(jìn)行插入與刪除C．為了能方便的找到雙親D．使二叉樹的遍歷結(jié)果唯一線索二叉樹是一種〔結(jié)構(gòu)。A．邏輯B．邏輯和存儲C．物理D．線性設(shè)F是一個森林,B是由F變換得的二叉樹。若F中有n個非終端結(jié)點,則B中右指針域為空的結(jié)點有〔個。A．n-1B．nC．n+1D．n+22．應(yīng)用題1試找出滿足下列條件的二叉樹=1\*GB3①先序序列與后序序列相同=2\*GB3②中序序列與后序序列相同=3\*GB3③先序序列與中序序列相同=4\*GB3④中序序列與層次遍歷序列相同先序遍歷二叉樹的順序是"根—左子樹—右子樹",中序遍歷"左子樹—根—右子樹",后序遍歷順序是："左子樹—右子樹―根＂,根據(jù)以上原則,本題解答如下：〔１?若先序序列與后序序列相同,則或為空樹,或為只有根結(jié)點的二叉樹〔２?若中序序列與后序序列相同,則或為空樹,或為任一結(jié)點至多只有左子樹的二叉樹．〔３?若先序序列與中序序列相同,則或為空樹,或為任一結(jié)點至多只有右子樹的二叉樹．〔４?若中序序列與層次遍歷序列相同,則或為空樹,或為任一結(jié)點至多只有右子樹的二叉樹2設(shè)一棵二叉樹的先序序列：ABDFCEGH,中序序列：BFDAGEHC=1\*GB3①畫出這棵二叉樹。=2\*GB3②畫出這棵二叉樹的后序線索樹。=3\*GB3③將這棵二叉樹轉(zhuǎn)換成對應(yīng)的樹〔或森林。ABMABMFD<3>CEMHG<1><2>3假設(shè)用于通信的電文僅由8個字母組成,字母在電文中出現(xiàn)的頻率分別為0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。=1\*GB3①試為這8個字母設(shè)計赫夫曼編碼。=2\*GB3②試設(shè)計另一種由二進(jìn)制表示的等長編碼方案。=3\*GB3③對于上述實例,比較兩種方案的優(yōu)缺點。解：方案1；哈夫曼編碼先將概率放大100倍,以方便構(gòu)造哈夫曼樹。w={7,19,2,6,32,3,21,10},按哈夫曼規(guī)則：[[〔2,3,6],<7,10>],……19,21,3201010121321010101213210101106123〔40〔60192132〔28〔117106〔523方案比較：字母編號對應(yīng)編碼字母編號對應(yīng)編碼出現(xiàn)頻率111000.072000.193111100.02411100.065100.326111110.037010.21811010.10字母編號對應(yīng)編碼出現(xiàn)頻率10000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10方案1的WPL＝2<0.19+0.32+0.21>+4<0.07+0.06+0.10>+5<0.02+0.03>=1.44+0.92+0.25=2.61方案2的WPL＝3<0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03>=3結(jié)論：哈夫曼編碼優(yōu)于等長二進(jìn)制編碼?4已知下列字符A、B、C、D、E、F、G的權(quán)值分別為3、12、7、4、2、8,11,試填寫出其對應(yīng)哈夫曼樹HT的存儲結(jié)構(gòu)的初態(tài)和終態(tài)。初態(tài):weightparentlchildrchild13000212000370004400052000680007110008000900010000110001200013000weightparentlchildrchild13800212120037100044900528006810007111100859519911481015123611201397122713210134701112終態(tài)3．算法設(shè)計題編寫以下算法：1統(tǒng)計二叉樹的葉結(jié)點個數(shù)。intLeafNodeCount<BiTreeT>{ if<T==NULL> return0;//如果是空樹,則葉子結(jié)點個數(shù)為0 elseif<T->lchild==NULL&&T->rchild==NULL> return1;//判斷該結(jié)點是否是葉子結(jié)點〔左孩子右孩子都為空,若是則返回1 else returnLeafNodeCount<T->lchild>+LeafNodeCount<T->rchild>;}2判別兩棵樹是否相等。3交換二叉樹每個結(jié)點的左孩子和右孩子。voidChangeLR<BiTree&T>{ BiTreetemp; if<T->lchild==NULL&&T->rchild==NULL> return;else { temp=T->lchild; T->lchild=T->rchild; T->rchild=temp; } ChangeLR<T->lchild>;ChangeLR<T->rchild>;}4設(shè)計二叉樹的雙序遍歷算法〔雙序遍歷是指對于二叉樹的每一個結(jié)點來說,先訪問這個結(jié)點,再按雙序遍歷它的左子樹,然后再一次訪問這個結(jié)點,接下來按雙序遍歷它的右子樹。voidDoubleTraverse<BiTreeT>{ if<T==NULL> return; elseif<T->lchild==NULL&&T->rchild==NULL> cout<<T->data; else { cout<<T->data; DoubleTraverse<T->lchild>; cout<<T->data; DoubleTraverse<T->rchild>; }}5計算二叉樹最大的寬度〔二叉樹的最大寬度是指二叉樹所有層中結(jié)點個數(shù)的最大值。[題目分析]求二叉樹高度的算法見上題。求最大寬度可采用層次遍歷的方法,記下各層結(jié)點數(shù),每層遍歷完畢,若結(jié)點數(shù)大于原先最大寬度,則修改最大寬度。intWidth<BiTreebt>//求二叉樹bt的最大寬度{if<bt==null>return<0>;//空二叉樹寬度為0else{BiTreeQ[];//Q是隊列,元素為二叉樹結(jié)點指針,容量足夠大 front=1;rear=1;last=1;//front隊頭指針,rear隊尾指針,last同層最右結(jié)點在隊列中的位置 temp=0;maxw=0;//temp記局部寬度,maxw記最大寬度 Q[rear]=bt;//根結(jié)點入隊列while<front<=last> {p=Q[front++];temp++;//同層元素數(shù)加1if<p->lchild!=null>Q[++rear]=p->lchild;//左子女入隊if<p->rchild!=null>Q[++rear]=p->rchild;//右子女入隊if<front>last>//一層結(jié)束, {last=rear;if<temp>maxw>maxw=temp;//last指向下層最右元素,更新當(dāng)前最大寬度 temp=0;}//if}//whilereturn<maxw>;}//結(jié)束width6用按層次順序遍歷二叉樹的方法,統(tǒng)計樹中具有度為1的結(jié)點數(shù)目。intLevel<BiTreebt>//層次遍歷二叉樹,并統(tǒng)計度為1的結(jié)點的個數(shù){intnum=0;//num統(tǒng)計度為1的結(jié)點的個數(shù)if<bt>{QueueInit<Q>;QueueIn<Q,bt>；//Q是以二叉樹結(jié)點指針為元素的隊列while<!QueueEmpty<Q>>{p=QueueOut<Q>;printf<p->data>;//出隊,訪問結(jié)點if<p->lchild&&!p->rchild||!p->lchild&&p->rchild>num++;//度為1的結(jié)點if<p->lchild>QueueIn<Q,p->lchild>;//非空左子女入隊if<p->rchild>QueueIn<Q,p->rchild>;//非空右子女入隊}}//if<bt>return<num>;}//返回度為1的結(jié)點的個數(shù)7求任意二叉樹中第一條最長的路徑長度,并輸出此路徑上各結(jié)點的值。[題目分析]因為后序遍歷棧中保留當(dāng)前結(jié)點的祖先的信息,用一變量保存棧的最高棧頂指針,每當(dāng)退棧時,棧頂指針高于保存最高棧頂指針的值時,則將該棧倒入輔助棧中,輔助棧始終保存最長路徑長度上的結(jié)點,直至后序遍歷完畢,則輔助棧中內(nèi)容即為所求。voidLongestPath<BiTreebt>//求二叉樹中的第一條最長路徑長度{BiTreep=bt,l[],s[];//l,s是棧,元素是二叉樹結(jié)點指針,l中保留當(dāng)前最長路徑中的結(jié)點inti,top=0,tag[],longest=0;while<p||top>0>{while<p>{s[++top]=p；tag[top]=0;p=p->Lc;}//沿左分枝向下if<tag[top]==1>//當(dāng)前結(jié)點的右分枝已遍歷{if<!s[top]->Lc&&!s[top]->Rc>//只有到葉子結(jié)點時,才查看路徑長度if<top>longest>{for<i=1;i<=top;i++>l[i]=s[i];longest=top;top--;}//保留當(dāng)前最長路徑到l棧,記住最高棧頂指針,退棧}elseif<top>0>{tag[top]=1;p=s[top].Rc;}//沿右子分枝向下}//while<p!=null||top>0>}//結(jié)束LongestPath8輸出二叉樹中從每個葉子結(jié)點到根結(jié)點的路徑。[題目分析]采用先序遍歷的遞歸方法,當(dāng)找到葉子結(jié)點*b時,由于*b葉子結(jié)點尚未添加到path中