數據結構習題答案

第1章緒論習題1．簡述下列概念：數據、數據元素、數據項、數據對象、數據結構、邏輯結構、存儲結構、抽象數據類型。2．試舉一個數據結構的例子，敘述其邏輯結構和存儲結構兩方面的含義和相互關系。3．簡述邏輯結構的四種基本關系并畫出它們的關系圖。4．存儲結構由哪兩種基本的存儲方法實現？5．選擇題（1）在數據結構中，從邏輯上可以把數據結構分成（）。A．動態(tài)結構和靜態(tài)結構B．緊湊結構和非緊湊結構C．線性結構和非線性結構D．內部結構和外部結構（2）與數據元素本身的形式、內容、相對位置、個數無關的是數據的（）。A．存儲結構B．存儲實現C．邏輯結構D．運算實現（3）通常要求同一邏輯結構中的所有數據元素具有相同的特性，這意味著（）。A．數據具有同一特點B．不僅數據元素所包含的數據項的個數要相同，而且對應數據項的類型要一致C．每個數據元素都一樣D．數據元素所包含的數據項的個數要相等（4）以下說法正確的是（）。A．數據元素是數據的最小單位B．數據項是數據的基本單位C．數據結構是帶有結構的各數據項的集合D．一些表面上很不相同的數據可以有相同的邏輯結構（5）以下與數據的存儲結構無關的術語是（）。A．順序隊列B.鏈表C.有序表D.鏈棧（6）以下數據結構中，（）是非線性數據結構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個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動的元素個數為（）。A．8B．63.5C．63D（4）鏈接存儲的存儲結構所占存儲空間（）。A．分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針B．只有一部分，存放結點值C．只有一部分，存儲表示結點間關系的指針D．分兩部分，一部分存放結點值，另一部分存放結點所占單元數（5）線性表若采用鏈式存儲結構時，要求內存中可用存儲單元的地址（）。A．必須是連續(xù)的B．部分地址必須是連續(xù)的C．一定是不連續(xù)的D．連續(xù)或不連續(xù)都可以（6）線性表Ｌ在（）情況下適用于使用鏈式結構實現。A．需經常修改Ｌ中的結點值Ｂ．需不斷對Ｌ進行刪除插入C．Ｌ中含有大量的結點Ｄ．Ｌ中結點結構復雜（7）單鏈表的存儲密度（）。A．大于1B．等于1C．小于1D．（8）將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數是（）。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．求表長、定位這兩種運算在采用順序存儲結構時實現的效率不比采用鏈式存儲結構時實現的效率低B．順序存儲的線性表可以隨機存取C．由于順序存儲要求連續(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）將兩個遞增的有序鏈表合并為一個遞增的有序鏈表。要求結果鏈表仍使用原來兩個鏈表的存儲空間,不另外占用其它的存儲空間。表中不允許有重復的數據。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）將兩個非遞減的有序鏈表合并為一個非遞增的有序鏈表。要求結果鏈表仍使用原來兩個鏈表的存儲空間,不另外占用其它的存儲空間。表中允許有重復的數據。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中出現而不在B中出現的元素所構成的集合），并以同樣的形式存儲，同時返回該集合的元素個數。voidDifference（LinkedListA，B，*n）∥A和B均是帶頭結點的遞增有序的單鏈表，分別存儲了一個集合，本算法求兩集合的差集，存儲于單鏈表A中，*n是結果集合中元素個數，調用時為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的元素類型為整型，要求B、C表利用A表的結點）。（6）設計一個算法，通過一趟遍歷在單鏈表中確定值最大的結點。ElemTypeMax(LinkListL){ if(L->next==NULL)returnNULL; pmax=L->next;//假定第一個結點中數據具有最大值 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是給定的兩個參數，其值可以和表中的元素相同，也可以不同）。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的數據元素。[題目分析]在順序存儲的線性表上刪除元素，通常要涉及到一系列元素的移動（刪第i個元素，第i+1至第n個元素要依次前移）。本題要求刪除線性表中所有值為item的數據元素，并未要求元素間的相對位置不變。因此可以考慮設頭尾兩個指針（i=1，j=n），從兩端向中間移動，凡遇到值item的數據元素時，直接將右端元素左移至值為item的數據元素位置。voidDelete（ElemTypeA[]，intn）∥A是有n個元素的一維數組，本算法刪除A中所有值為item的元素。{i=1；j=n；∥設置數組低、高端指針（下標）。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）。刪除元素未使用其它輔助空間，最后線性表中的元素個數是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）數組Ｑ［ｎ］用來表示一個循環(huán)隊列，ｆ為當前隊列頭元素的前一位置，ｒ為隊尾元素的位置，假定隊列中元素的個數小于ｎ，計算隊列中元素個數的公式為（）。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)需要調用該函數的次數為（）。

A．

n+1

B．

n-1

C．n

D．n+2（6）棧在

（）中有所應用。A．遞歸調用B．函數調用C．表達式求值D．前三個選項都有（7）為解決計算機主機與打印機間速度不匹配問題，通常設一個打印數據緩沖區(qū)。主機將要輸出的數據依次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數據。該緩沖區(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）設計一個判別表達式中左，右括號是否配對出現的算法，采用（）數據結構最佳。A．線性表的順序存儲結構B．隊列C.線性表的鏈式存儲結構D.棧（11）用鏈接方式存儲的隊列，在進行刪除運算時（）。A.僅修改頭指針B.僅修改尾指針C.頭、尾指針都要修改D.頭、尾指針可能都要修改（12）循環(huán)隊列存儲在數組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”不是回文。試寫一個算法判定給定的字符向量是否為回文。(提示：將一半字符入棧)

根據提示，算法可設計為：

//以下為順序棧的存儲結構定義

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

typedefcharDataType;//假定棧元素的數據類型為字符

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

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）假設以數組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; //存放隊列元素的數組 intm; //隊列最大可容納元素個數 } 構造函數 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)存儲分配成功與否 } 插入函數 template<classType>voidQueue<Type>::EnQueue(Type&item){ assert(!IsFull()); //判隊列是否不滿，滿則出錯處理 rear=(rear+1)%m; //隊尾位置進1,隊尾指針指示實際隊尾位置 Q[rear]=item; //進隊列 tag=1; //標志改1，表示隊列不空 } 刪除函數 template<classType>TypeQueue<Type>::DeQueue(){ assert(!IsEmpty()); //判斷隊列是否不空，空則出錯處理 front=(front+1)%m; //隊頭位置進1,隊頭指針指示實際隊頭的前一位置tag=0; //標志改0,表示棧不滿returnQ[front]; //返回原隊頭元素的值 } 讀取隊頭元素函數 template<classType>TypeQueue<Type>::GetFront(){ assert(!IsEmpty()); //判斷隊列是否不空，空則出錯處理returnQ[(front+1)%m]; //返回隊頭元素的值 }(8）如果允許在循環(huán)隊列的兩端都可以進行插入和刪除操作。要求：=1\*GB3①寫出循環(huán)隊列的類型定義；=2\*GB3②寫出“從隊尾刪除”和“從隊頭插入”的算法。[題目分析]用一維數組v[0..M-1]實現循環(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)隊列，本算法實現從隊尾刪除，若刪除成功，返回被刪除元素，否則給出出錯信息。 {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)隊列，本算法實現“從隊頭插入”元素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函數定義如下:=1\*GB3①寫出計算Ack(m,n)的遞歸算法，并根據此算法給出出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為單鏈表的表頭指針,鏈表中存儲的都是整型數據，試寫出實現下列運算的遞歸算法： =1\*GB3①求鏈表中的最大整數；=2\*GB3②求鏈表的結點個數；=3\*GB3③求所有整數的平均值。#include<iostream.h> //定義在頭文件"RecurveList.h"中classList; classListNode{ //鏈表結點類friendclassList;private: intdata; //結點數據 ListNode*link; //結點指針 ListNode(constintitem):data(item),link(NULL){} //構造函數};classList{ //鏈表類private: ListNode*first,current; intMax(ListNode*f); intNum(ListNode*f); floatAvg(ListNode*f,int&n);public: List():first(NULL),current(NULL){} //構造函數 ~List(){} //析構函數 ListNode*NewNode(constintitem); //創(chuàng)建鏈表結點,其值為item voidNewList(constintretvalue); //建立鏈表,以輸入retvalue結束 voidPrintList(); //輸出鏈表所有結點數據 intGetMax(){returnMax(first);} //求鏈表所有數據的最大值 intGetNum(){returnNum(first);} //求鏈表中數據個數 floatGetAvg(){returnAvg(first);} //求鏈表所有數據的平均值}; 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){ //遞歸算法:求鏈表中結點個數 if(f==NULL)return0; //空表,返回0 return1+Num(f->link); //否則,返回后繼鏈表結點個數加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<<“輸入建表結束標志數據：”;cin>>finished; //輸入建表結束標志數據 test.NewList(finished); //建立鏈表 test.PrintList(); //打印鏈表cout<<"\nTheMaxis:"<<test.GetMax(); cout<<"\nTheNumis:"<<test.GetNum(); cout<<"\nTheAveis:"<<test.GetAve()<<'\n'; printf("HelloWorld!\n"); return0;}

第4章串、數組和廣義表習題1．選擇題（1）串是一種特殊的線性表，其特殊性體現在（）。A．可以順序存儲B．數據元素是一個字符C．可以鏈式存儲D．數據元素可以是多個字符若（2）串下面關于串的的敘述中，（）是不正確的？A．串是字符的有限序列B．空串是由空格構成的串C．模式匹配是串的一種重要運算D．串既可以采用順序存儲，也可以采用鏈式存儲（3）串“ababaaababaa”的next數組為（）。A．012345678999B．012121111212C．011234223456D．0123012322345（4）串“ababaabab”的nextval為（）。A．010104101B．010102101C．（5）串的長度是指（）。A．串中所含不同字母的個數B．串中所含字符的個數C．串中所含不同字符的個數D．串中所含非空格字符的個數（6）假設以行序為主序存儲二維數組A=array[1..100,1..100]，設每個數據元素占2個存儲單元，基地址為10，則LOC[5,5]=（）。A．808B．818C．1010D．（7）設有數組A[i,j]，數組的每個元素長度為3字節(jié)，i的值為1到8，j的值為1到10，數組從內存首地址BA開始順序存放，當用以列為主存放時，元素A[5,8]的存儲首地址為（）。A．BA+141B．BA+180C．BA+222D（8）設有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一元素，其存儲地址為1，每個元素占一個地址空間，則a85的地址為（）。A．13B．33C．18D．（9）若對n階對稱矩陣A以行序為主序方式將其下三角形的元素(包括主對角線上所有元素)依次存放于一維數組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]是對稱矩陣，將下面三角（包括對角線）以行序存儲到一維數組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）設二維數組A[1..m，1..n]（即m行n列）按行存儲在數組B[1..m*n]中，則二維數組元素A[i,j]在一維數組B中的下標為（）。A．(i-1)*n+jB．(i-1)*n+j-1C．i*(j-1)D（12）數組A[0..4,-1..-3,5..7]中含有元素的個數（）。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函數值。模式串t的next和nextval值如下：j123456789101112t串abcaabbabcabnext[j]011122312345nextval[j]011021301105（2）設目標為t=“abcaabbabcabaacbacba”,模式為p=“abcabaa”=1\*GB3①計算模式p的naxtval函數值；=2\*GB3②不寫出算法,只畫出利用KMP算法進行模式匹配時每一趟的匹配過程。=1\*GB3①p的nextval函數值為0110132。（p的next函數值為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）數組A中，每個元素A[i,j]的長度均為32個二進位,行下標從-1到9，列下標從1到11，從首地址S開始連續(xù)存放主存儲器中，主存儲器字長為16位。求：=1\*GB3①存放該數組所需多少單元？=2\*GB3②存放數組第4列所有元素至少需多少單元？=3\*GB3③數組按行存放時，元素A[7,4]的起始地址是多少？=4\*GB3④數組按列存放時，元素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）寫一個算法統(tǒng)計在輸入字符串中各個不同字符出現的頻度并將結果存入文件（字符串中的合法字符為A-Z這26個字母和0-9這10個數字）。voidCount（）//統(tǒng)計輸入字符串中數字字符和字母字符的個數。｛inti，num[36]；charch；for（i＝0；i<36；i++）num[i]＝０；//初始化while（（ch＝getchar（））!=‘#’）//‘#’表示輸入字符串結束。if（‘0’<=ch<=‘9’）｛i=ch－48;num[i]++；｝//數字字符elseif（‘A’<=ch<=‘Z’）｛i=ch-65+10;num[i]++；｝//字母字符for（i=0；i<10；i++）//輸出數字字符的個數printf（“數字％d的個數＝％d\n”，i，num[i]）；for（i＝10；i<36；i++）//求出字母字符的個數printf（“字母字符％c的個數＝％d\n”，i＋55，num[i]）；｝//算法結束。（6）寫一個遞歸算法來實現字符串逆序存儲，要求不另設串存儲空間。[題目分析]實現字符串的逆置并不難，但本題“要求不另設串存儲空間”來實現字符串逆序存儲，即第一個輸入的字符最后存儲，最后輸入的字符先存儲，使用遞歸可容易做到。voidInvertStore(charA[])//字符串逆序存儲的遞歸算法。{charch;staticinti=0;//需要使用靜態(tài)變量scanf("%c",&ch);if(ch!='.')//規(guī)定'.'是字符串輸入結束標志 {InvertStore(A); A[i++]=ch;//字符串逆序存儲 }A[i]='\0';//字符串結尾標記}//結束算法InvertStore。（7）編寫算法，實現下面函數的功能。函數voidinsert(char*s,char*t,intpos)將字符串t插入到字符串s中，插入位置為pos。假設分配給字符串s的空間足夠讓字符串t插入。（說明：不得使用任何庫函數）[題目分析]本題是字符串的插入問題，要求在字符串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參數位置非法\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。[題目分析]本題要求字符串s1拆分成字符串s2和字符串s3，要求字符串s2“按給定長度n格式化成兩端對齊的字符串”，即長度為n且首尾字符不得為空格字符。算法從左到右掃描字符串s1，找到第一個非空格字符，計數到n，第n個拷入字符串s2的字符不得為空格，然后將余下字符復制到字符串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中復制 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)設二維數組a[1..m,1..n]含有m*n個整數。=1\*GB3①寫一個算法判斷a中所有元素是否互不相同?輸出相關信息(yes/no)；=2\*GB3②試分析算法的時間復雜度。[題目分析]判斷二維數組中元素是否互不相同，只有逐個比較,找到一對相等的元素，就可結論為不是互不相同。如何達到每個元素同其它元素比較一次且只一次？在當前行，每個元素要同本行后面的元素比較一次（下面第一個循環(huán)控制變量p的for循環(huán)），然后同第i+1行及以后各行元素比較一次，這就是循環(huán)控制變量k和p的二層for循環(huán)。intJudgEqual(inga[m][n],intm,n)//判斷二維數組中所有元素是否互不相同，如是，返回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）二維數組中的每一個元素同其它元素都比較一次，數組中共m*n個元素，第1個元素同其它m*n-1個元素比較，第2個元素同其它m*n-2個元素比較，……，第m*n-1個元素同最后一個元素(m*n)比較一次,所以在元素互不相等時總的比較次數為(m*n-1)+(m*n-2)+…+2+1=（m*n）(m*n-1)/2。在有相同元素時,可能第一次比較就相同,也可能最后一次比較時相同,設在(m*n-1)個位置上均可能相同,這時的平均比較次數約為（m*n）(m*n-1)/4，總的時間復雜度是O(n4)。(10)設任意n個整數存放于數組A(1:n)中，試編寫