數(shù)據(jù)結構習題答案

第1章緒論習題1．簡述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對象、數(shù)據(jù)構造、邏輯構造、存儲構造、抽象數(shù)據(jù)類型。2．試舉一種數(shù)據(jù)構造的例子，論述其邏輯構造和存儲構造兩方面的含義和互相關系。3．簡述邏輯構造的四種基本關系并畫出它們的關系圖。4．存儲構造由哪兩種基本的存儲措施實現(xiàn)？5．選擇題（1）在數(shù)據(jù)構造中，從邏輯上可以把數(shù)據(jù)構造提成（）。A．動態(tài)構造和靜態(tài)構造B．緊湊構造和非緊湊構造C．線性構造和非線性構造D．內部構造和外部構造（2）與數(shù)據(jù)元素自身的形式、內容、相對位置、個數(shù)無關的是數(shù)據(jù)的（）。A．存儲構造B．存儲實現(xiàn)C．邏輯構造D．運算實現(xiàn)（3）一般規(guī)定同一邏輯構造中的所有數(shù)據(jù)元素具有相似的特性，這意味著（）。A．數(shù)據(jù)具有同一特點B．不僅數(shù)據(jù)元素所包括的數(shù)據(jù)項的個數(shù)要相似，并且對應數(shù)據(jù)項的類型要一致C．每個數(shù)據(jù)元素都同樣D．數(shù)據(jù)元素所包括的數(shù)據(jù)項的個數(shù)要相等（4）如下說法對的的是（）。A．數(shù)據(jù)元素是數(shù)據(jù)的最小單位B．數(shù)據(jù)項是數(shù)據(jù)的基本單位C．數(shù)據(jù)構造是帶有構造的各數(shù)據(jù)項的集合D．某些表面上很不相似的數(shù)據(jù)可以有相似的邏輯構造（5）如下與數(shù)據(jù)的存儲構造無關的術語是（）。A．次序隊列B.鏈表C.有序表D.鏈棧（6）如下數(shù)據(jù)構造中，（）是非線性數(shù)據(jù)構造A．樹B．字符串C．隊D．棧6．試分析下面各程序段的時間復雜度。（1）x=90;y=100;

while(y>0)if(x>100){x=x-10;y--;}elsex++;（2）for(i=0;i<n;i++)for(j=0;j<m;j++)a[i][j]=0;（3）s=0;fori=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;（4）i=1;while(i<=n)i=i*3;（5）x=0;for(i=1;i<n;i++)for(j=1;j<=n-i;j++)x++;（6）x=n;//n>1y=0;while(x≥(y+1)*(y+1))y++;（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）（5）由于x++共執(zhí)行了n-1+n-2+……＋1=n(n-1)/2，因此執(zhí)行時間為O（n2）（6）O()

第2章線性表1．選擇題（1）一種向量第一種元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（）。A．110B．108C．100D（2）在n個結點的次序表中，算法的時間復雜度是O(1)的操作是（）。A．訪問第i個結點（1≤i≤n）和求第i個結點的直接前驅（2≤i≤n）B．在第i個結點后插入一種新結點（1≤i≤n）C．刪除第i個結點（1≤i≤n）D．將n個結點從小到大排序（3）向一種有127個元素的次序表中插入一種新元素并保持本來次序不變，平均要移動的元素個數(shù)為（）。A．8B．63.5C．63D（4）鏈接存儲的存儲構造所占存儲空間（）。A．分兩部分，一部分寄存結點值，另一部分寄存表達結點間關系的指針B．只有一部分，寄存結點值C．只有一部分，存儲表達結點間關系的指針D．分兩部分，一部分寄存結點值，另一部分寄存結點所占單元數(shù)（5）線性表若采用鏈式存儲構造時，規(guī)定內存中可用存儲單元的地址（）。A．必須是持續(xù)的B．部分地址必須是持續(xù)的C．一定是不持續(xù)的D．持續(xù)或不持續(xù)都可以（6）線性表Ｌ在（）狀況下合用于使用鏈式構造實現(xiàn)。A．需常常修改Ｌ中的結點值Ｂ．需不停對Ｌ進行刪除插入C．Ｌ中具有大量的結點Ｄ．Ｌ中結點構造復雜（7）單鏈表的存儲密度（）。A．不小于1B．等于1C．不不小于1D．（8）將兩個各有n個元素的有序表歸并成一種有序表，其至少的比較次數(shù)是（）。A．nB．2n-1C．2nD（9）在一種長度為n的次序表中，在第i個元素（1≤i≤n+1）之前插入一種新元素時須向后移動（）個元素。A．n-iB．n-i+1C．n-i-1(10)線性表L=(a1，a2,……an)，下列說法對的的是（）。A．每個元素均有一種直接前驅和一種直接后繼B．線性表中至少有一種元素C．表中諸元素的排列必須是由小到大或由大到小D．除第一種和最終一種元素外，其他每個元素均有一種且僅有一種直接前驅和直接后繼。(11)若指定有n個元素的向量，則建立一種有序單鏈表的時間復雜性的量級是（）。A．O(1)B．O(n)C．O(n2)D．O(nlog2n)(12)如下說法錯誤的是（）。A．求表長、定位這兩種運算在采用次序存儲構造時實現(xiàn)的效率不比采用鏈式存儲構造時實現(xiàn)的效率低B．次序存儲的線性表可以隨機存取C．由于次序存儲規(guī)定持續(xù)的存儲區(qū)域，因此在存儲管理上不夠靈活D．線性表的鏈式存儲構造優(yōu)于次序存儲構造(13)在單鏈表中，要將s所指結點插入到p所指結點之后，其語句應為（）。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)在雙向鏈表存儲構造中，刪除p所指的結點時須修改指針（）。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指針所指的結點后插入q所指向的新結點，其修改指針的操作是（）。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．算法設計題（1）將兩個遞增的有序鏈表合并為一種遞增的有序鏈表。規(guī)定成果鏈表仍使用本來兩個鏈表的存儲空間,不此外占用其他的存儲空間。表中不容許有反復的數(shù)據(jù)。voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){pa=La->next;pb=Lb->next;Lc=pc=La;//用La的頭結點作為Lc的頭結點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的頭結點}（2）將兩個非遞減的有序鏈表合并為一種非遞增的有序鏈表。規(guī)定成果鏈表仍使用本來兩個鏈表的存儲空間,不此外占用其他的存儲空間。表中容許有反復的數(shù)據(jù)。voidunion(LinkList&La,LinkList&Lb,LinkList&Lc,){pa=La->next;pb=Lb->next;//初始化Lc=pc=La;//用La的頭結點作為Lc的頭結點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的頭結點}（3）已知兩個鏈表A和B分別表達兩個集合，其元素遞增排列。請設計算法求出A與B的交集，并寄存于A鏈表中。voidMix(LinkList&La,LinkList&Lb,LinkList&Lc,){pa=la->next;pb=lb->next;∥設工作指針pa和pb；Lc=pc=La;//用La的頭結點作為Lc的頭結點while(pa&&pb)if(pa->data==pb->data)∥交集并入成果表中。{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;}∥釋放結點空間while(pb){u=pb;pb=pb->next;deleteu;}∥釋放結點空間pc->next=null;∥置鏈表尾標識。deleteLb;∥注：本算法中也可對B表不作釋放空間的處理（4）已知兩個鏈表A和B分別表達兩個集合，其元素遞增排列。請設計算法求出兩個集合A和B的差集（即僅由在A中出現(xiàn)而不在B中出現(xiàn)的元素所構成的集合），并以同樣的形式存儲，同步返回該集合的元素個數(shù)。voidDifference（LinkedListA，B，*n）∥A和B均是帶頭結點的遞增有序的單鏈表，分別存儲了一種集合，本算法求兩集合的差集，存儲于單鏈表A中，*n是成果集合中元素個數(shù)，調用時為0{p=A->next；∥p和q分別是鏈表A和B的工作指針。q=B->next；pre=A；∥pre為A中p所指結點的前驅結點的指針。while（p!=null&&q!=null）if（p->data<q->data）{pre=p；p=p->next；*n++；}∥A鏈表中目前結點指針后移。elseif（p->data>q->data）q=q->next；∥B鏈表中目前結點指針后移。else{pre->next=p->next；∥處理A，B中元素值相似的結點，應刪除。u=p；p=p->next；deleteu；}∥刪除結點（5）設計算法將一種帶頭結點的單鏈表A分解為兩個具有相似構造的鏈表B、C，其中B表的結點為A表中值不不小于零的結點，而C表的結點為A表中值不小于零的結點（鏈表A的元素類型為整型，規(guī)定B、C表運用A表的結點）。（6）設計一種算法，通過一趟遍歷在單鏈表中確定值最大的結點。ElemTypeMax(LinkListL){ if(L->next==NULL)returnNULL; pmax=L->next;//假定第一種結點中數(shù)據(jù)具有最大值 p=L->next->next; while(p!=NULL){//假如下一種結點存在 if(p->data>pmax->data)pmax=p; p=p->next; } returnpmax->data;（7）設計一種算法，通過遍歷一趟，將鏈表中所有結點的鏈接方向逆轉，仍運用原表的存儲空間。voidinverse(LinkList&L){//逆置帶頭結點的單鏈表Lp=L->next;L->next=NULL;while(p){q=p->next;//q指向*p的后繼p->next=L->next;L->next=p;//*p插入在頭結點之后p=q;}}（8）設計一種算法，刪除遞增有序鏈表中值不小于mink且不不小于maxk的所有元素（mink和maxk是給定的兩個參數(shù)，其值可以和表中的元素相似，也可以不一樣）。voiddelete(LinkList&L,intmink,intmaxk){p=L->next;//首元結點while(p&&p->data<=mink){pre=p;p=p->next;}//查找第一種值>mink的結點if(p){while(p&&p->data<maxk)p=p->next;//查找第一種值≥maxk的結點q=pre->next;pre->next=p;//修改指針while(q!=p){s=q->next;deleteq;q=s;}//釋放結點空間}//if}（9）已知p指向雙向循環(huán)鏈表中的一種結點，其結點構造為data、prior、next三個域，寫出算法change(p),互換p所指向的結點和它的前綴結點的次序。懂得雙向循環(huán)鏈表中的一種結點，與前驅互換波及到四個結點（p結點，前驅結點，前驅的前驅結點，后繼結點）六條鏈。voidExchange（LinkedListp）∥p是雙向循環(huán)鏈表中的一種結點，本算法將p所指結點與其前驅結點互換。{q=p->llink；q->llink->rlink=p；∥p的前驅的前驅之后繼為pp->llink=q->llink；∥p的前驅指向其前驅的前驅。q->rlink=p->rlink；∥p的前驅的后繼為p的后繼。q->llink=p；∥p與其前驅互換p->rlink->llink=q；∥p的后繼的前驅指向原p的前驅p->rlink=q；∥p的后繼指向其本來的前驅}∥算法exchange結束。（10）已知長度為n的線性表A采用次序存儲構造，請寫一時間復雜度為O(n)、空間復雜度為O(1)的算法，該算法刪除線性表中所有值為item的數(shù)據(jù)元素。[題目分析]在次序存儲的線性表上刪除元素，一般要波及到一系列元素的移動（刪第i個元素，第i+1至第n個元素要依次前移）。本題規(guī)定刪除線性表中所有值為item的數(shù)據(jù)元素，并未規(guī)定元素間的相對位置不變。因此可以考慮設頭尾兩個指針（i=1，j=n），從兩端向中間移動，凡碰到值item的數(shù)據(jù)元素時，直接將右端元素左移至值為item的數(shù)據(jù)元素位置。voidDelete（ElemTypeA[]，intn）∥A是有n個元素的一維數(shù)組，本算法刪除A中所有值為item的元素。{i=1；j=n；∥設置數(shù)組低、高端指針（下標）。while（i<j）{while（i<j&&A[i]!=item）i++；∥若值不為item，左移指針。if（i<j）while（i<j&&A[j]==item）j--；∥若右端元素值為item，指針左移if（i<j）A[i++]=A[j--]；}[算法討論]因元素只掃描一趟，算法時間復雜度為O（n）。刪除元素未使用其他輔助空間，最終線性表中的元素個數(shù)是j。

第3章棧和隊列習題1．選擇題（1）若讓元素1，2，3，4，5依次進棧，則出棧次序不也許出目前（）種狀況。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)隊列，ｆ為目前隊列頭元素的前一位置，ｒ為隊尾元素的位置，假定隊列中元素的個數(shù)不不小于ｎ，計算隊列中元素個數(shù)的公式為（）。A．r-fB．(n+f-r)%nC．n+r-fD．（n+r-f)%n（4）鏈式棧結點為：(data,link)，top指向棧頂.若想摘除棧頂結點，并將刪除結點的值保留到x中,則應執(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）設有一種遞歸算法如下

intfact(intn){

//n不小于等于0

if(n<=0)return1;

elsereturnn*fact(n-1);

}則計算fact(n)需要調用該函數(shù)的次數(shù)為（）。

A．

n+1

B．

n-1

C．n

D．n+2（6）棧在

（）中有所應用。A．遞歸調用B．函數(shù)調用C．體現(xiàn)式求值D．前三個選項均有（7）為處理計算機主機與打印機間速度不匹配問題，一般設一種打印數(shù)據(jù)緩沖區(qū)。主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯構造應當是（）。A．隊列B．棧C．線性表D．有序表（8）設棧S和隊列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次進入棧S，一種元素出棧后即進入Q，若6個元素出隊的序列是e2、e4、e3、e6、e5和e1，則棧S的容量至少應當是（）。A．2B．3C．4D（9）在一種具有n個單元的次序棧中，假設以地址高端作為棧底，以top作為棧頂指針，則當作進棧處理時，top的變化為（）。A．top不變B．top=0C．top--D．（10）設計一種鑒別體現(xiàn)式中左，右括號與否配對出現(xiàn)的算法，采用（）數(shù)據(jù)構造最佳。A．線性表的次序存儲構造B．隊列C.線性表的鏈式存儲構造D.棧（11）用鏈接方式存儲的隊列，在進行刪除運算時（）。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.都是先進先出B.都是先進后出C.只容許在端點處插入和刪除元素D.沒有共同點（15）一種遞歸算法必須包括（）。A.遞歸部分B.終止條件和遞歸部分C.迭代部分D.終止條件和迭代部分（2）回文是指正讀反讀均相似的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。試寫一種算法鑒定給定的字符向量與否為回文。(提醒：將二分之一字符入棧)

根據(jù)提醒，算法可設計為：

//如下為次序棧的存儲構造定義

#defineStackSize100//假定預分派的?？臻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))

{//每彈出一種字符與對應字符比較

temp=Pop(&s);

if(temp!=S[i])

return0;//不等則返回0

elsei++;

}

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

}（3）設從鍵盤輸入一整數(shù)的序列：a1,a2,a3，…，an，試編寫算法實現(xiàn)：用棧構造存儲輸入的整數(shù)，當ai≠-1時，將ai進棧；當ai=-1時，輸出棧頂整數(shù)并出棧。算法應對異常狀況（入棧滿等）給出對應的信息。#definemaxsize?？臻g容量voidInOutS(ints[maxsize])//s是元素為整數(shù)的棧，本算法進行入棧和退棧操作。{inttop=0;//top為棧頂指針，定義top=0時為?？铡or(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--])；}}}//算法結束。（4）從鍵盤上輸入一種后綴體現(xiàn)式，試編寫算法計算體現(xiàn)式的值。規(guī)定：逆波蘭體現(xiàn)式的長度不超過一行，以$符作為輸入結束，操作數(shù)之間用空格分隔,操作符只也許有+、-、*、/四種運算。例如：23434+2*$。[題目分析]逆波蘭體現(xiàn)式(即后綴體現(xiàn)式)求值規(guī)則如下：設置運算數(shù)棧OPND,對體現(xiàn)式從左到右掃描(讀入)，當體現(xiàn)式中掃描到數(shù)時，壓入OPND棧。當掃描到運算符時，從OPND退出兩個數(shù)，進行對應運算，成果再壓入OPND棧。這個過程一直進行到讀出體現(xiàn)式結束符$，這時OPND棧中只有一種數(shù)，就是成果。floatexpr()//從鍵盤輸入逆波蘭體現(xiàn)式，以‘$’表達輸入結束，本算法求逆波蘭式體現(xiàn)式的值。｛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://其他符號不作處理。}//結束switchscanf(“%c”,&x);//讀入體現(xiàn)式中下一種字符。}//結束while（x！=‘$’）printf(“后綴體現(xiàn)式的值為%f”,pop(OPND));}//算法結束。[算法討論]假設輸入的后綴體現(xiàn)式是對的的，未作錯誤檢查。算法中拼數(shù)部分是關鍵。若碰到不小于等于‘0’且不不小于等于‘9’的字符，認為是數(shù)。這種字符的序號減去字符‘0’的序號得出數(shù)。對于整數(shù)，每讀入一種數(shù)字字符，前面得到的部分數(shù)要乘上10再加新讀入的數(shù)得到新的部分數(shù)。當讀到小數(shù)點，認為數(shù)的整數(shù)部分已完，要接著處理小數(shù)部分。小數(shù)部分的數(shù)要除以10（或10的冪數(shù)）變成十分位，百分位，千分位數(shù)等等，與前面部分數(shù)相加。在拼數(shù)過程中，若遇非數(shù)字字符，表達數(shù)已拼完，將數(shù)壓入棧中，并且將變量num恢復為0，準備下一種數(shù)。這時對新讀入的字符進入‘+’、‘-’、‘*’、‘/’及空格的判斷，因此在結束處理數(shù)字字符的case（5）假設以I和O分別表達入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表達為僅由I和O構成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。=1\*GB3①下面所示的序列中哪些是合法的？A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO=2\*GB3②通過對=1\*GB3①的分析，寫出一種算法，鑒定所給的操作序列與否合法。若合法，返回true，否則返回false（假定被鑒定的操作序列已存入一維數(shù)組中）。=1\*GB3①A和D是合法序列，B和C是非法序列。=2\*GB3②設被鑒定的操作序列已存入一維數(shù)組A中。intJudge(charA[])//判斷字符數(shù)組A中的輸入輸出序列與否是合法序列。如是，返回true，否則返回false。{i=0;//i為下標。j=k=0;//j和k分別為I和字母O的的個數(shù)。while(A[i]!=‘\0’)//當未到字符數(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);}}//算法結束。[算法討論]在入棧出棧序列（即由‘I’和‘O’構成的字符串）的任一位置，入棧次數(shù)（‘I’的個數(shù)）都必須不小于等于出棧次數(shù)（即‘O’的個數(shù)），否則視作非法序列，立即給出信息，退出算法。整個序列（即讀到字符數(shù)組中字符串的結束標識‘\0’(6）假設以帶頭結點的循環(huán)鏈表表達隊列，并且只設一種指針指向隊尾元素站點(注意不設頭指針)，試編寫對應的置空隊、判隊空、入隊和出隊等算法。

算法如下：

//先定義鏈隊構造:

typedefstructqueuenode{

Datatypedata;

structqueuenode*next;

}QueueNode;//以上是結點類型的定義

typedefstruct{

queuenode*rear;

}LinkQueue;//只設一種指向隊尾元素的指針

(1)置空隊

voidInitQueue(LinkQueue*Q)

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

QueueNode*s;

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

while(Q->rear!=Q->rear->next)//當隊列非空，將隊中元素逐一出隊

{s=Q->rear->next;

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

free(s);

}//回收結點空間

}

(2)判隊空

intEmptyQueue(LinkQueue*Q)

{//判隊空

//當頭結點的next指針指向自己時為空隊

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

}

(3)入隊

voidEnQueue(LinkQueue*Q,Datatypex)

{//入隊

//也就是在尾結點處插入元素

QueueNode*p=(QueueNode*)malloc(sizeof(QueueNode));//申請新結點

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

Q-rear->next=p;

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

}

(4)出隊

DatatypeDeQueue(LinkQueue*Q)

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

Datatypet;

QueueNode*p;

if(EmptyQueue(Q))

Error("Queueunderflow");

p=Q->rear->next->next;//p指向將要摘下的結點

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

if(p==Q->rear)

{//當隊列中只有一種結點時，p結點出隊后，要將隊尾指針指向頭結點

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

else

Q->rear->next->next=p->next;//摘下結點p

free(p);//釋放被刪結點

returnx;

}（7）假設以數(shù)組Q[m]寄存循環(huán)隊列中的元素,同步設置一種標志tag，以tag==0和tag==1來區(qū)別在隊頭指針(front)和隊尾指針(rear)相等時，隊列狀態(tài)為“空”還是“滿”。試編寫與此構造對應的插入(enqueue)和刪除(dlqueue)算法?！窘獯稹垦h(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; //隊尾指針、隊頭指針和隊滿標志 Type*Q; //寄存隊列元素的數(shù)組 intm; //隊列最大可容納元素個數(shù) } 構造函數(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; //隊尾位置進1,隊尾指針指示實際隊尾位置 Q[rear]=item; //進隊列 tag=1; //標志改1，表達隊列不空 } 刪除函數(shù) template<classType>TypeQueue<Type>::DeQueue(){ assert(!IsEmpty()); //判斷隊列與否不空，空則出錯處理 front=(front+1)%m; //隊頭位置進1,隊頭指針指示實際隊頭的前一位置tag=0; //標志改0,表達棧不滿returnQ[front]; //返回原隊頭元素的值 } 讀取隊頭元素函數(shù) template<classType>TypeQueue<Type>::GetFront(){ assert(!IsEmpty()); //判斷隊列與否不空，空則出錯處理returnQ[(front+1)%m]; //返回隊頭元素的值 }(8）假如容許在循環(huán)隊列的兩端都可以進行插入和刪除操作。規(guī)定：=1\*GB3①寫出循環(huán)隊列的類型定義；=2\*GB3②寫出“從隊尾刪除”和“從隊頭插入”的算法。[題目分析]用一維數(shù)組v[0..M-1]實現(xiàn)循環(huán)隊列，其中M是隊列長度。設隊頭指針front和隊尾指針rear，約定front指向隊頭元素的前一位置，rear指向隊尾元素。定義front=rear時為隊空，(rear+1)%m=front為隊滿。約定隊頭端入隊向下標小的方向發(fā)展，隊尾端入隊向下標大的方向發(fā)展。（1）#defineM隊列也許到達的最大長度typedefstruct{elemtpdata[M];intfront,rear;}cycqueue;（2）elemtpdelqueue(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]);//返回出隊元素。}//從隊尾刪除算法結束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;//修改隊頭指針。}//結束從隊頭插入算法。（9）已知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));}//算法結束（1）Ack(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而得（2）intAckerman(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]);}//算法結束（10）已知f為單鏈表的表頭指針,鏈表中存儲的都是整型數(shù)據(jù)，試寫出實現(xiàn)下列運算的遞歸算法： =1\*GB3①求鏈表中的最大整數(shù)；=2\*GB3②求鏈表的結點個數(shù)；=3\*GB3③求所有整數(shù)的平均值。#include<iostream.h> //定義在頭文獻"RecurveList.h"中classList; classListNode{ //鏈表結點類friendclassList;private: intdata; //結點數(shù)據(jù) ListNode*link; //結點指針 ListNode(constintitem):data(item),link(NULL){} //構造函數(shù)};classList{ //鏈表類private: ListNode*first,current; intMax(ListNode*f); intNum(ListNode*f); floatAvg(ListNode*f,int&n);public: List():first(NULL),current(NULL){} //構造函數(shù) ~List(){} //析構函數(shù) ListNode*NewNode(constintitem); //創(chuàng)立鏈表結點,其值為item voidNewList(constintretvalue); //建立鏈表,以輸入retvalue結束 voidPrintList(); //輸出鏈表所有結點數(shù)據(jù) intGetMax(){returnMax(first);} //求鏈表所有數(shù)據(jù)的最大值 intGetNum(){returnNum(first);} //求鏈表中數(shù)據(jù)個數(shù) floatGetAvg(){returnAvg(first);} //求鏈表所有數(shù)據(jù)的平均值}; ListNode*List::NewNode(constintitem){ //創(chuàng)立新鏈表結點 ListNode*newnode=newListNode(item); returnnewnode;}voidList::NewList(constintretvalue){ //建立鏈表,以輸入retvalue結束 first=NULL;intvalue;ListNode*q; cout<<"Inputyourdata:\n"; //提醒 cin>>value; //輸入while(value!=retvalue){ //輸入有效 q=NewNode(value); //建立包括value的新結點 if(first==NULL)first=current=q; //空表時,新結點成為鏈表第一種結點else{current->link=q;current=q;} //非空表時,新結點鏈入鏈尾 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; //遞歸結束條件 inttemp=Max(f->link); //在目前結點的后繼鏈表中求最大值 if(f->data>temp)returnf->data; //假如目前結點的值還要大,返回目前檢點值 elsereturntemp; //否則返回后繼鏈表中的最大值}intList::Num(ListNode*f){ //遞歸算法:求鏈表中結點個數(shù) if(f==NULL)return0; //空表,返回0 return1+Num(f->link); //否則,返回后繼鏈表結點個數(shù)加1}floatList::Avg(ListNode*f,int&n){ //遞歸算法:求鏈表中所有元素的平均值 if(f->link==NULL) //鏈表中只有一種結點,遞歸結束條件{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<<“輸入建表結束標志數(shù)據(jù)：”;cin>>finished; //輸入建表結束標志數(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ù)組和廣義表習題1．選擇題（1）串是一種特殊的線性表，其特殊性體目前（）。A．可以次序存儲B．數(shù)據(jù)元素是一種字符C．可以鏈式存儲D．數(shù)據(jù)元素可以是多種字符若（2）串下面有關串的的論述中，（）是不對的的？A．串是字符的有限序列B．空串是由空格構成的串C．模式匹配是串的一種重要運算D．串既可以采用次序存儲，也可以采用鏈式存儲（3）串“ababaaababaa”的next數(shù)組為（）。A．B．C．D．5（4）串“ababaabab”的nextval為（）。A．B．C．D（5）串的長度是指（）。A．串中所含不一樣字母的個數(shù)B．串中所含字符的個數(shù)C．串中所含不一樣字符的個數(shù)D．串中所含非空格字符的個數(shù)（6）假設以行序為主序存儲二維數(shù)組A=array[1..100,1..100]，設每個數(shù)據(jù)元素占2個存儲單元，基地址為10，則LOC[5,5]=（）。A．808B．818C．1010D．（7）設有數(shù)組A[i,j]，數(shù)組的每個元素長度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內存首地址BA開始次序寄存，當用以列為主寄存時，元素A[5,8]的存儲首地址為（）。A．BA+141B．BA+180C．BA+222D（8）設有一種10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一元素，其存儲地址為1，每個元素占一種地址空間，則a85的地址為（）。A．13B．33C．18D．（9）若對n階對稱矩陣A以行序為主序方式將其下三角形的元素(包括主對角線上所有元素)依次寄存于一維數(shù)組B[1..(n(n+1))/2]中，則在B中確定aij（i<j）的位置k的關系為（）。A．i*(i-1)/2+jB．j*(j-1)/2+iC．i*(i+1)/2+jD．j*(j+1)/2+i（10）A[N，N]是對稱矩陣，將下面三角（包括對角線）以行序存儲到一維數(shù)組T[N(N+1)/2]中，則對任一上三角元素a[i][j]對應T[k]的下標k是（）。A．i(i-1)/2+jB．j(j-1)/2+iC．i(j-i)/2+1D．j(i-1)/2+1（11）設二維數(shù)組A[1..m，1..n]（即m行n列）按行存儲在數(shù)組B[1..m*n]中，則二維數(shù)組元素A[i,j]在一維數(shù)組B中的下標為（）。A．(i-1)*n+jB．(i-1)*n+j-1C．i*(j-1)D（12）數(shù)組A[0..4,-1..-3,5..7]中具有元素的個數(shù)（）。A．55B．45C．36（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．aB．()C．(a,b,c,d)D．(b,c,d)（15）設廣義表L=((a,b,c))，則L的長度和深度分別為（）。A．1和1B．1和3C．1和2D．2和3（1）已知模式串t=‘abcaabbabcab’寫出用KMP法求得的每個字符對應的next和nextval函數(shù)值。模式串t的next和nextval值如下：j123456789101112t串abcaabbabcabnext[j]011122312345nextval[j]011021301105（2）設目的為t=“abcaabbabcabaacbacba”,模式為p=“abcabaa”=1\*GB3①計算模式p的naxtval函數(shù)值；=2\*GB3②不寫出算法,只畫出運用KMP算法進行模式匹配時每一趟的匹配過程。=1\*GB3①p的nextval函數(shù)值為0110132。（p的next函數(shù)值為0111232）。=2\*GB3②運用KMP(改善的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個二進位,行下標從-1到9，列下標從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個二進制位，主存字長16位，故每個元素占2個字長，行下標可平移至1到11。（1）242（2）22（3）s+182（4）s+142(4)請將香蕉banana用工具H()—Head()，T()—Tail()從L中取出。L=(apple,(orange,(strawberry,(banana)),peach),pear)H（H（T（H（T（H（T（L）））））））（5）寫一種算法記錄在輸入字符串中各個不一樣字符出現(xiàn)的頻度并將成果存入文獻（字符串中的合法字符為A-Z這26個字母和0-9這10個數(shù)字）。voidCount（）//記錄輸入字符串中數(shù)字字符和字母字符的個數(shù)。｛inti，num[36]；charch；for（i＝0；i<36；i++）num[i]＝０；//初始化while（（ch＝getchar（））!=‘#’）//‘#’表達輸入字符串結束。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]）；｝//算法結束。（6）寫一種遞歸算法來實現(xiàn)字符串逆序存儲，規(guī)定不另設串存儲空間。[題目分析]實現(xiàn)字符串的逆置并不難，但本題“規(guī)定不另設串存儲空間”來實現(xiàn)字符串逆序存儲，即第一種輸入的字符最終存儲，最終輸入的字符先存儲，使用遞歸可輕易做到。voidInvertStore(charA[])//字符串逆序存儲的遞歸算法。{charch;staticinti=0;//需要使用靜態(tài)變量scanf("%c",&ch);if(ch!='.')//規(guī)定'.'是字符串輸入結束標志 {InvertStore(A); A[i++]=ch;//字符串逆序存儲 }A[i]='\0';//字符串結尾標識}//結束算法InvertStore。（7）編寫算法，實現(xiàn)下面函數(shù)的功能。函數(shù)voidinsert(char*s,char*t,intpos)將字符串t插入到字符串s中，插入位置為pos。假設分派給字符串s的空間足夠讓字符串t插入。（闡明：不得使用任何庫函數(shù)）[題目分析]本題是字符串的插入問題，規(guī)定在字符串s的pos位置，插入字符串t。首先應查找字符串s的pos位置，將第pos個字符到字符串s尾的子串向后移動字符串t的長度，然后將字符串t復制到字符串s的第pos位置后。對插入位置pos要驗證其合法性，不不小于1或不小于串s的長度均為非法，因題目假設給字符串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’的下標，p也指向‘\0while(*q!='\0'){q++;x++;}//查找字符串t的長度x，循環(huán)結束時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的結束標識('\0')也后移了，而串t的結尾標識不應插入到s中。（8）已知字符串S1中寄存一段英文，寫出算法format(s1,s2,s3,n),將其按給定的長度n格式化成兩端對齊的字符串S2,其多出的字符送S3。[題目分析]本題規(guī)定字符串s1拆提成字符串s2和字符串s3，規(guī)定字符串s2“按給定長度n格式化成兩端對齊的字符串”，即長度為n且首尾字符不得為空格字符。算法從左到右掃描字符串s1，找到第一種非空格字符，計數(shù)到n，第n個拷入字符串s2的字符不得為空格，然后將余下字符復制到字符串s3中。voidformat(char*s1,*s2,*s3)//將字符串s1拆提成字符串s2和字符串s3，規(guī)定字符串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中復制 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字符串結束標識 } *q=s3;p++;//將s1串其他部分送字符串s3。 while(*p!='\0'){*q=*p;q++;p++;} *q='\0';//置串s3結束標識}(9)設二維數(shù)組a[1..m,1..n]具有m*n個整數(shù)。=1\*GB3①寫一種算法判斷a中所有元素與否互不相似?輸出有關信息(yes/no)；=2\*GB3②試分析算法的時間復雜度。[題目分析]判斷二維數(shù)組中元素與否互不相似，只有逐一比較,找到一對相等的元素，就可結論為不是互不相似。怎樣到達每個元素同其他元素比較一次且只一次？在目前行，每個元素要同本行背面的元素比較一次（下面第一種循環(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);}//只要有一種相似的，就結論不是互不相似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結束（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。在有相似元素時,也許第一次比較就相似,也也許最終一次比較時相似,設在(m*n-1)個位置上均也許相似,這時的平均比較次數(shù)約為（m*n）(m*n-1)/4，總的時間復雜度是O(n4)。(10)設任意n個整數(shù)寄存于數(shù)組A(1:n)中，試編寫算法，將所有正數(shù)排在所有負數(shù)前面（規(guī)定算法復雜性為0(n