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

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

intfact(intn){

//n大于等于0

if(n<=0)return1;

elsereturnn*fact(n-1);

}則計(jì)算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.前三個(gè)選項(xiàng)都有(7)為解決計(jì)算機(jī)主機(jī)與打印機(jī)間速度不匹配問(wèn)題,通常設(shè)一個(gè)打印數(shù)據(jù)緩沖區(qū)。主機(jī)將要輸出得數(shù)據(jù)依次寫(xiě)入該緩沖區(qū),而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)得邏輯結(jié)構(gòu)應(yīng)該就是()。A.隊(duì)列B.棧C.線(xiàn)性表D.有序表(8)設(shè)棧S與隊(duì)列Q得初始狀態(tài)為空,元素e1、e2、e3、e4、e5與e6依次進(jìn)入棧S,一個(gè)元素出棧后即進(jìn)入Q,若6個(gè)元素出隊(duì)得序列就是e2、e4、e3、e6、e5與e1,則棧S得容量至少應(yīng)該就是()。A.2B.3C.4D.6(9)在一個(gè)具有n個(gè)單元得順序棧中,假設(shè)以地址高端作為棧底,以top作為棧頂指針,則當(dāng)作進(jìn)棧處理時(shí),top得變化為()。A.top不變B.top=0C.top--D.top++(10)設(shè)計(jì)一個(gè)判別表達(dá)式中左,右括號(hào)就是否配對(duì)出現(xiàn)得算法,采用()數(shù)據(jù)結(jié)構(gòu)最佳。A.線(xiàn)性表得順序存儲(chǔ)結(jié)構(gòu)B.隊(duì)列C、線(xiàn)性表得鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D、棧(11)用鏈接方式存儲(chǔ)得隊(duì)列,在進(jìn)行刪除運(yùn)算時(shí)()。A、僅修改頭指針B、僅修改尾指針C、頭、尾指針都要修改D、頭、尾指針可能都要修改(12)循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A[0、、m]中,則入隊(duì)時(shí)得操作為()。A、rear=rear+1B、rear=(rear+1)%(m-1)C、rear=(rear+1)%mD、rear=(rear+1)%(m+1)(13)最大容量為n得循環(huán)隊(duì)列,隊(duì)尾指針就是rear,隊(duì)頭就是front,則隊(duì)空得條件就是()。A、(rear+1)%n==frontB、rear==frontC.rear+1==frontD、(rear-l)%n==front(14)棧與隊(duì)列得共同點(diǎn)就是()。A、都就是先進(jìn)先出B、都就是先進(jìn)后出C、只允許在端點(diǎn)處插入與刪除元素D、沒(méi)有共同點(diǎn)(15)一個(gè)遞歸算法必須包括()。A、遞歸部分B、終止條件與遞歸部分C、迭代部分D、終止條件與迭代部分(2)回文就是指正讀反讀均相同得字符序列,如“abba”與“abdba”均就是回文,但“good”不就是回文。試寫(xiě)一個(gè)算法判定給定得字符向量就是否為回文。(提示:將一半字符入棧)

根據(jù)提示,算法可設(shè)計(jì)為:

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

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

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

typedefstruct{

DataTypedata[StackSize];

inttop;

}SeqStack;

intIsHuiwen(char*t)

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

SeqStacks;

inti,len;

chartemp;

InitStack(&s);

len=strlen(t);//求向量長(zhǎng)度

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

Push(&s,t[i]);

while(!EmptyStack(&s))

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

temp=Pop(&s);

if(temp!=S[i])

return0;//不等則返回0

elsei++;

}

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

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

算法如下:

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

typedefstructqueuenode{

Datatypedata;

structqueuenode*next;

}QueueNode;//以上就是結(jié)點(diǎn)類(lèi)型得定義

typedefstruct{

queuenode*rear;

}LinkQueue;//只設(shè)一個(gè)指向隊(duì)尾元素得指針

(1)置空隊(duì)

voidInitQueue(LinkQueue*Q)

{//置空隊(duì):就就是使頭結(jié)點(diǎn)成為隊(duì)尾元素

QueueNode*s;

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

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

{s=Q->rear->next;

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

free(s);

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

}

(2)判隊(duì)空

intEmptyQueue(LinkQueue*Q)

{//判隊(duì)空

//當(dāng)頭結(jié)點(diǎn)得next指針指向自己時(shí)為空隊(duì)

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

}

(3)入隊(duì)

voidEnQueue(LinkQueue*Q,Datatypex)

{//入隊(duì)

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

QueueNode*p=(QueueNode*)malloc(sizeof(QueueNode));//申請(qǐng)新結(jié)點(diǎn)

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

Q-rear->next=p;

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

}

(4)出隊(duì)

DatatypeDeQueue(LinkQueue*Q)

{//出隊(duì),把頭結(jié)點(diǎn)之后得元素摘下

Datatypet;

QueueNode*p;

if(EmptyQueue(Q))

Error("Queueunderflow");

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

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

if(p==Q->rear)

{//當(dāng)隊(duì)列中只有一個(gè)結(jié)點(diǎn)時(shí),p結(jié)點(diǎn)出隊(duì)后,要將隊(duì)尾指針指向頭結(jié)點(diǎn)

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

else

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

free(p);//釋放被刪結(jié)點(diǎn)

returnx;

}(7)假設(shè)以數(shù)組Q[m]存放循環(huán)隊(duì)列中得元素,同時(shí)設(shè)置一個(gè)標(biāo)志tag,以tag==0與tag==1來(lái)區(qū)別在隊(duì)頭指針(front)與隊(duì)尾指針(rear)相等時(shí),隊(duì)列狀態(tài)為“空”還就是“滿(mǎn)”。試編寫(xiě)與此結(jié)構(gòu)相應(yīng)得插入(enqueue)與刪除(dlqueue)算法?！窘獯稹垦h(huán)隊(duì)列類(lèi)定義 #include<assert、h> template<classType>classQueue{ //循環(huán)隊(duì)列得類(lèi)定義 public: Queue(int=10); ~Queue(){delete[]Q;} voidEnQueue(Type&item); TypeDeQueue(); TypeGetFront(); voidMakeEmpty(){front=rear=tag=0;} //置空隊(duì)列 intIsEmpty()const{returnfront==rear&&tag==0;} //判隊(duì)列空否 intIsFull()const{returnfront==rear&&tag==1;} //判隊(duì)列滿(mǎn)否 private: intrear,front,tag; //隊(duì)尾指針、隊(duì)頭指針與隊(duì)滿(mǎn)標(biāo)志 Type*Q; //存放隊(duì)列元素得數(shù)組 intm; //隊(duì)列最大可容納元素個(gè)數(shù) } 構(gòu)造函數(shù) template<classType>Queue<Type>::Queue(intsz):rear(0),front(0),tag(0),m(sz){ //建立一個(gè)最大具有m個(gè)元素得空隊(duì)列。 Q=newType[m]; //創(chuàng)建隊(duì)列空間 assert(Q!=0); //斷言:動(dòng)態(tài)存儲(chǔ)分配成功與否 } 插入函數(shù) template<classType>voidQueue<Type>::EnQueue(Type&item){ assert(!IsFull()); //判隊(duì)列就是否不滿(mǎn),滿(mǎn)則出錯(cuò)處理 rear=(rear+1)%m; //隊(duì)尾位置進(jìn)1,隊(duì)尾指針指示實(shí)際隊(duì)尾位置 Q[rear]=item; //進(jìn)隊(duì)列 tag=1; //標(biāo)志改1,表示隊(duì)列不空 } 刪除函數(shù) template<classType>TypeQueue<Type>::DeQueue(){ assert(!IsEmpty()); //判斷隊(duì)列就是否不空,空則出錯(cuò)處理 front=(front+1)%m; //隊(duì)頭位置進(jìn)1,隊(duì)頭指針指示實(shí)際隊(duì)頭得前一位置tag=0; //標(biāo)志改0,表示棧不滿(mǎn)returnQ[front]; //返回原隊(duì)頭元素得值 } 讀取隊(duì)頭元素函數(shù) template<classType>TypeQueue<Type>::GetFront(){ assert(!IsEmpty()); //判斷隊(duì)列就是否不空,空則出錯(cuò)處理returnQ[(front+1)%m]; //返回隊(duì)頭元素得值 }(8)如果允許在循環(huán)隊(duì)列得兩端都可以進(jìn)行插入與刪除操作。要求:=1\*GB3①寫(xiě)出循環(huán)隊(duì)列得類(lèi)型定義;=2\*GB3②寫(xiě)出“從隊(duì)尾刪除”與“從隊(duì)頭插入”得算法。[題目分析]用一維數(shù)組v[0、、M-1]實(shí)現(xiàn)循環(huán)隊(duì)列,其中M就是隊(duì)列長(zhǎng)度。設(shè)隊(duì)頭指針front與隊(duì)尾指針rear,約定front指向隊(duì)頭元素得前一位置,rear指向隊(duì)尾元素。定義front=rear時(shí)為隊(duì)空,(rear+1)%m=front為隊(duì)滿(mǎn)。約定隊(duì)頭端入隊(duì)向下標(biāo)小得方向發(fā)展,隊(duì)尾端入隊(duì)向下標(biāo)大得方向發(fā)展。(1)#defineM隊(duì)列可能達(dá)到得最大長(zhǎng)度typedefstruct{elemtpdata[M];intfront,rear;}cycqueue;(2)elemtpdelqueue(cycqueueQ)//Q就是如上定義得循環(huán)隊(duì)列,本算法實(shí)現(xiàn)從隊(duì)尾刪除,若刪除成功,返回被刪除元素,否則給出出錯(cuò)信息。 {if(Q、front==Q、rear){printf(“隊(duì)列空”);exit(0);} Q、rear=(Q、rear-1+M)%M;//修改隊(duì)尾指針。return(Q、data[(Q、rear+1+M)%M]);//返回出隊(duì)元素。}//從隊(duì)尾刪除算法結(jié)束voidenqueue(cycqueueQ,elemtpx)//Q就是順序存儲(chǔ)得循環(huán)隊(duì)列,本算法實(shí)現(xiàn)“從隊(duì)頭插入”元素x。{if(Q、rear==(Q、front-1+M)%M){printf(“隊(duì)滿(mǎn)”;exit(0);)Q、data[Q、front]=x;//x入隊(duì)列Q、front=(Q、front-1+M)%M;//修改隊(duì)頭指針。}//結(jié)束從隊(duì)頭插入算法。(9)已知Ackermann函數(shù)定義如下:=1\*GB3①寫(xiě)出計(jì)算Ack(m,n)得遞歸算法,并根據(jù)此算法給出出Ack(2,1)得計(jì)算過(guò)程。=2\*GB3②寫(xiě)出計(jì)算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é)束(1)Ack(2,1)得計(jì)算過(guò)程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]);}//算法結(jié)束(10)已知f為單鏈表得表頭指針,鏈表中存儲(chǔ)得都就是整型數(shù)據(jù),試寫(xiě)出實(shí)現(xiàn)下列運(yùn)算得遞歸算法: =1\*GB3①求鏈表中得最大整數(shù);=2\*GB3②求鏈表得結(jié)點(diǎn)個(gè)數(shù);=3\*GB3③求所有整數(shù)得平均值。#include<iostream、h> //定義在頭文件"RecurveList、h"中classList; classListNode{ //鏈表結(jié)點(diǎn)類(lèi)friendclassList;private: intdata; //結(jié)點(diǎn)數(shù)據(jù) ListNode*link; //結(jié)點(diǎn)指針 ListNode(constintitem):data(item),link(NULL){} //構(gòu)造函數(shù)};classList{ //鏈表類(lèi)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é)點(diǎn),其值為item voidNewList(constintretvalue); //建立鏈表,以輸入retvalue結(jié)束 voidPrintList(); //輸出鏈表所有結(jié)點(diǎn)數(shù)據(jù) intGetMax(){returnMax(first);} //求鏈表所有數(shù)據(jù)得最大值 intGetNum(){returnNum(first);} //求鏈表中數(shù)據(jù)個(gè)數(shù) floatGetAvg(){returnAvg(first);} //求鏈表所有數(shù)據(jù)得平均值}; ListNode*List::NewNode(constintitem){ //創(chuàng)建新鏈表結(jié)點(diǎn) 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é)點(diǎn) if(first==NULL)first=current=q; //空表時(shí),新結(jié)點(diǎn)成為鏈表第一個(gè)結(jié)點(diǎn)else{current->link=q;current=q;} //非空表時(shí),新結(jié)點(diǎn)鏈入鏈尾 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é)點(diǎn)得后繼鏈表中求最大值 if(f->data>temp)returnf->data; //如果當(dāng)前結(jié)點(diǎn)得值還要大,返回當(dāng)前檢點(diǎn)值 elsereturntemp; //否則返回后繼鏈表中得最大值}intList::Num(ListNode*f){ //遞歸算法:求鏈表中結(jié)點(diǎn)個(gè)數(shù) if(f==NULL)return0; //空表,返回0 return1+Num(f->link); //否則,返回后繼鏈表結(jié)點(diǎn)個(gè)數(shù)加1}floatList::Avg(ListNode*f,int&n){ //遞歸算法:求鏈表中所有元素得平均值 if(f->link==NULL) //鏈表中只有一個(gè)結(jié)點(diǎn),遞歸結(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)性表,其特殊性體現(xiàn)在()。A.可以順序存儲(chǔ)B.數(shù)據(jù)元素就是一個(gè)字符C.可以鏈?zhǔn)酱鎯?chǔ)D.數(shù)據(jù)元素可以就是多個(gè)字符若(2)串下面關(guān)于串得得敘述中,()就是不正確得？A.串就是字符得有限序列B.空串就是由空格構(gòu)成得串C.模式匹配就是串得一種重要運(yùn)算D.串既可以采用順序存儲(chǔ),也可以采用鏈?zhǔn)酱鎯?chǔ)(3)串“ababaaababaa”得next數(shù)組為()。A.9B.2C.0456D.45(4)串“ababaabab”得nextval為()。A.010104101B.010102101C.010100011D.010101011(5)串得長(zhǎng)度就是指()。A.串中所含不同字母得個(gè)數(shù)B.串中所含字符得個(gè)數(shù)C.串中所含不同字符得個(gè)數(shù)D.串中所含非空格字符得個(gè)數(shù)(6)假設(shè)以行序?yàn)橹餍虼鎯?chǔ)二維數(shù)組A=array[1、、100,1、、100],設(shè)每個(gè)數(shù)據(jù)元素占2個(gè)存儲(chǔ)單元,基地址為10,則LOC[5,5]=()。A.808B.818C.1010D.1020(7)設(shè)有數(shù)組A[i,j],數(shù)組得每個(gè)元素長(zhǎng)度為3字節(jié),i得值為1到8,j得值為1到10,數(shù)組從內(nèi)存首地址BA開(kāi)始順序存放,當(dāng)用以列為主存放時(shí),元素A[5,8]得存儲(chǔ)首地址為()。A.BA+141B.BA+180C.BA+222D.BA+225(8)設(shè)有一個(gè)10階得對(duì)稱(chēng)矩陣A,采用壓縮存儲(chǔ)方式,以行序?yàn)橹鞔鎯?chǔ),a11為第一元素,其存儲(chǔ)地址為1,每個(gè)元素占一個(gè)地址空間,則a85得地址為()。A.13B.33C.18D.40(9)若對(duì)n階對(duì)稱(chēng)矩陣A以行序?yàn)橹餍蚍绞綄⑵湎氯切蔚迷?包括主對(duì)角線(xiàn)上所有元素)依次存放于一維數(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(10)A[N,N]就是對(duì)稱(chēng)矩陣,將下面三角(包括對(duì)角線(xiàn))以行序存儲(chǔ)到一維數(shù)組T[N(N+1)/2]中,則對(duì)任一上三角元素a[i][j]對(duì)應(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列)按行存儲(chǔ)在數(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]中含有元素得個(gè)數(shù)()。A.55B.45C.36D.16(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)設(shè)廣義表L=((a,b,c)),則L得長(zhǎng)度與深度分別為()。A.1與1B.1與3C.1與2D.2與3(1)已知模式串t=‘a(chǎn)bcaabbabcab’寫(xiě)出用KMP法求得得每個(gè)字符對(duì)應(yīng)得next與nextval函數(shù)值。模式串t得next與nextval值如下:j123456789101112t串a(chǎn)bcaabbabcabnext[j]011122312345nextval[j]011021301105(2)設(shè)目標(biāo)為t=“abcaabbabcabaacbacba”,模式為p=“abcabaa”=1\*GB3①計(jì)算模式p得naxtval函數(shù)值;=2\*GB3②不寫(xiě)出算法,只畫(huà)出利用KMP算法進(jìn)行模式匹配時(shí)每一趟得匹配過(guò)程。=1\*GB3①p得nextval函數(shù)值為。(p得next函數(shù)值為)。=2\*GB3②利用KMP(改進(jìn)得nextval)算法,每趟匹配過(guò)程如下:第一趟匹配:abcaabbabcabaacbacbaabcab(i=5,j=5)第二趟匹配:abcaabbabcabaacbacbaabc(i=7,j=3)第三趟匹配:abcaabbabcabaacbacbaa(i=7,j=1)第四趟匹配:abcaabbabcabaacbacba(成功)abcabaa(i=15,j=8)(3)數(shù)組A中,每個(gè)元素A[i,j]得長(zhǎng)度均為32個(gè)二進(jìn)位,行下標(biāo)從-1到9,列下標(biāo)從1到11,從首地址S開(kāi)始連續(xù)存放主存儲(chǔ)器中,主存儲(chǔ)器字長(zhǎng)為16位。求:=1\*GB3①存放該數(shù)組所需多少單元？=2\*GB3②存放數(shù)組第4列所有元素至少需多少單元？=3\*GB3③數(shù)組按行存放時(shí),元素A[7,4]得起始地址就是多少？=4\*GB3④數(shù)組按列存放時(shí),元素A[4,7]得起始地址就是多少？每個(gè)元素32個(gè)二進(jìn)制位,主存字長(zhǎng)16位,故每個(gè)元素占2個(gè)字長(zhǎng),行下標(biāo)可平移至1到11。(1)242(2)22(3)s+182(4)s+142(4)請(qǐng)將香蕉banana用工具H()—Head(),T()—Tail()從L中取出。L=(apple,(orange,(strawberry,(banana)),peach),pear)H(H(T(H(T(H(T(L)))))))(5)寫(xiě)一個(gè)算法統(tǒng)計(jì)在輸入字符串中各個(gè)不同字符出現(xiàn)得頻度并將結(jié)果存入文件(字符串中得合法字符為A-Z這26個(gè)字母與0-9這10個(gè)數(shù)字)。voidCount()//統(tǒng)計(jì)輸入字符串中數(shù)字字符與字母字符得個(gè)數(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ù)字字符得個(gè)數(shù)printf(“數(shù)字％d得個(gè)數(shù)＝％d\n”,i,num[i]);for(i＝10;i<36;i++)//求出字母字符得個(gè)數(shù)printf(“字母字符％c得個(gè)數(shù)＝％d\n”,i＋55,num[i]);｝//算法結(jié)束。(6)寫(xiě)一個(gè)遞歸算法來(lái)實(shí)現(xiàn)字符串逆序存儲(chǔ),要求不另設(shè)串存儲(chǔ)空間。[題目分析]實(shí)現(xiàn)字符串得逆置并不難,但本題“要求不另設(shè)串存儲(chǔ)空間”來(lái)實(shí)現(xiàn)字符串逆序存儲(chǔ),即第一個(gè)輸入得字符最后存儲(chǔ),最后輸入得字符先存儲(chǔ),使用遞歸可容易做到。voidInvertStore(charA[])//字符串逆序存儲(chǔ)得遞歸算法。{charch;staticinti=0;//需要使用靜態(tài)變量scanf("%c",&ch);if(ch!='、')//規(guī)定'、'就是字符串輸入結(jié)束標(biāo)志 {InvertStore(A); A[i++]=ch;//字符串逆序存儲(chǔ) }A[i]='\0';//字符串結(jié)尾標(biāo)記}//結(jié)束算法InvertStore。(7)編寫(xiě)算法,實(shí)現(xiàn)下面函數(shù)得功能。函數(shù)voidinsert(char*s,char*t,intpos)將字符串t插入到字符串s中,插入位置為pos。假設(shè)分配給字符串s得空間足夠讓字符串t插入。(說(shuō)明:不得使用任何庫(kù)函數(shù))[題目分析]本題就是字符串得插入問(wèn)題,要求在字符串s得pos位置,插入字符串t。首先應(yīng)查找字符串s得pos位置,將第pos個(gè)字符到字符串s尾得子串向后移動(dòng)字符串t得長(zhǎng)度,然后將字符串t復(fù)制到字符串s得第pos位置后。對(duì)插入位置pos要驗(yàn)證其合法性,小于1或大于串s得長(zhǎng)度均為非法,因題目假設(shè)給字符串s得空間足夠大,故對(duì)插入不必判溢出。voidinsert(char*s,char*t,intpos)//將字符串t插入字符串s得第pos個(gè)位置。{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長(zhǎng)度,則查到pos位置時(shí),i=pos。if(*p=='/0'){printf("%d位置大于字符串s得長(zhǎng)度",pos);exit(0);}else//查找字符串得尾while(*p!='/0'){p++;i++;}//查到尾時(shí),i為字符‘\0’得下標(biāo),p也指向‘\0’。while(*q!='\0'){q++;x++;}//查找字符串t得長(zhǎng)度x,循環(huán)結(jié)束時(shí)q指向'\0'。for(j=i;j>=pos;j--){*(p+x)=*p;p--;}//串s得pos后得子串右移,空出串t得位置。q--;//指針q回退到串t得最后一個(gè)字符for(j=1;j<=x;j++)*p--=*q--;//將t串插入到s得pos位置上[算法討論]串s得結(jié)束標(biāo)記('\0')也后移了,而串t得結(jié)尾標(biāo)記不應(yīng)插入到s中。(8)已知字符串S1中存放一段英文,寫(xiě)出算法format(s1,s2,s3,n),將其按給定得長(zhǎng)度n格式化成兩端對(duì)齊得字符串S2,其多余得字符送S3。[題目分析]本題要求字符串s1拆分成字符串s2與字符串s3,要求字符串s2“按給定長(zhǎng)度n格式化成兩端對(duì)齊得字符串”,即長(zhǎng)度為n且首尾字符不得為空格字符。算法從左到右掃描字符串s1,找到第一個(gè)非空格字符,計(jì)數(shù)到n,第n個(gè)拷入字符串s2得字符不得為空格,然后將余下字符復(fù)制到字符串s3中。voidformat(char*s1,*s2,*s3)//將字符串s1拆分成字符串s2與字符串s3,要求字符串s2就是長(zhǎng)n且兩端對(duì)齊{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沒(méi)有%d個(gè)有效字符\n",n);exit(0);} if(*(--q)=='')//若最后一個(gè)字符為空格,則需向后找到第一個(gè)非空格字符 {p--;//p指針也后退 while(*p==''&&*p!='\0')p++;//往后查找一個(gè)非空格字符作串s2得尾字符 if(*p=='\0'){printf("s1串沒(méi)有%d個(gè)兩端對(duì)齊得字符串\n",n);exit(0); } *q=*p;//字符串s2最后一個(gè)非空字符 *(++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個(gè)整數(shù)。=1\*GB3①寫(xiě)一個(gè)算法判斷a中所有元素就是否互不相同?輸出相關(guān)信息(yes/no);=2\*GB3②試分析算法得時(shí)間復(fù)雜度。[題目分析]判斷二維數(shù)組中元素就是否互不相同,只有逐個(gè)比較,找到一對(duì)相等得元素,就可結(jié)論為不就是互不相同。如何達(dá)到每個(gè)元素同其它元素比較一次且只一次？在當(dāng)前行,每個(gè)元素要同本行后面得元素比較一次(下面第一個(gè)循環(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);}//只要有一個(gè)相同得,就結(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ù)組中得每一個(gè)元素同其它元素都比較一次,數(shù)組中共m*n個(gè)元素,第1個(gè)元素同其它m*n-1個(gè)元素比較,第2個(gè)元素同其它m*n-2個(gè)元素比較,……,第m*n-1個(gè)元素同最后一個(gè)元素(m*n)比較一次,所以在元