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

...wd......wd......wd...第1章緒論習(xí)題1．簡(jiǎn)述以下概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對(duì)象、數(shù)據(jù)構(gòu)造、邏輯構(gòu)造、存儲(chǔ)構(gòu)造、抽象數(shù)據(jù)類(lèi)型。2．試舉一個(gè)數(shù)據(jù)構(gòu)造的例子，表達(dá)其邏輯構(gòu)造和存儲(chǔ)構(gòu)造兩方面的含義和相互關(guān)系。3．簡(jiǎn)述邏輯構(gòu)造的四種基本關(guān)系并畫(huà)出它們的關(guān)系圖。4．存儲(chǔ)構(gòu)造由哪兩種基本的存儲(chǔ)方法實(shí)現(xiàn)5．選擇題〔1〕在數(shù)據(jù)構(gòu)造中，從邏輯上可以把數(shù)據(jù)構(gòu)造分成〔〕。A．動(dòng)態(tài)構(gòu)造和靜態(tài)構(gòu)造B．緊湊構(gòu)造和非緊湊構(gòu)造C．線(xiàn)性構(gòu)造和非線(xiàn)性構(gòu)造D．內(nèi)部構(gòu)造和外部構(gòu)造〔2〕與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、個(gè)數(shù)無(wú)關(guān)的是數(shù)據(jù)的〔〕。A．存儲(chǔ)構(gòu)造B．存儲(chǔ)實(shí)現(xiàn)C．邏輯構(gòu)造D．運(yùn)算實(shí)現(xiàn)〔3〕通常要求同一邏輯構(gòu)造中的所有數(shù)據(jù)元素具有一樣的特性，這意味著〔〕。A．?dāng)?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．?dāng)?shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等〔4〕以下說(shuō)法正確的選項(xiàng)是〔〕。A．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位B．?dāng)?shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位C．?dāng)?shù)據(jù)構(gòu)造是帶有構(gòu)造的各數(shù)據(jù)項(xiàng)的集合D．一些外表上很不一樣的數(shù)據(jù)可以有一樣的邏輯構(gòu)造〔5〕以下與數(shù)據(jù)的存儲(chǔ)構(gòu)造無(wú)關(guān)的術(shù)語(yǔ)是〔〕。A．順序隊(duì)列B.鏈表C.有序表D.鏈?！?〕以下數(shù)據(jù)構(gòu)造中，〔〕是非線(xiàn)性數(shù)據(jù)構(gòu)造A．樹(shù)B．字符串C．隊(duì)D．棧6．試分析下面各程序段的時(shí)間復(fù)雜度?！?〕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〔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〔4〕鏈接存儲(chǔ)的存儲(chǔ)構(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)性表假設(shè)采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址〔〕。A．必須是連續(xù)的B．局部地址必須是連續(xù)的C．一定是不連續(xù)的D．連續(xù)或不連續(xù)都可以〔6〕線(xiàn)性表Ｌ在〔〕情況下適用于使用鏈?zhǔn)綐?gòu)造實(shí)現(xiàn)。A．需經(jīng)常修改Ｌ中的結(jié)點(diǎn)值Ｂ．需不斷對(duì)Ｌ進(jìn)展刪除插入C．Ｌ中含有大量的結(jié)點(diǎn)Ｄ．Ｌ中結(jié)點(diǎn)構(gòu)造復(fù)雜〔7〕單鏈表的存儲(chǔ)密度〔〕。A．大于1B．等于1C．小于1D．〔8〕將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是〔〕。A．nB．2n-1C．2nD〔9〕在一個(gè)長(zhǎng)度為n的順序表中，在第i個(gè)元素〔1≤i≤n+1〕之前插入一個(gè)新元素時(shí)須向后移動(dòng)〔〕個(gè)元素。A．n-iB．n-i+1C．n-i-1(10)線(xiàn)性表L=(a1，a2,……an)，以下說(shuō)法正確的選項(xiàng)是〔〕。A．每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼B．線(xiàn)性表中至少有一個(gè)元素C．表中諸元素的排列必須是由小到大或由大到小D．除第一個(gè)和最后一個(gè)元素外，其余每個(gè)元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和直接后繼。(11)假設(shè)指定有n個(gè)元素的向量，那么建設(shè)一個(gè)有序單鏈表的時(shí)間復(fù)雜性的量級(jí)是〔〕。A．O(1)B．O(n)C．O(n2)D．O(nlog2n)(12)以下說(shuō)法錯(cuò)誤的選項(xiàng)是〔〕。A．求表長(zhǎng)、定位這兩種運(yùn)算在采用順序存儲(chǔ)構(gòu)造時(shí)實(shí)現(xiàn)的效率不比采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造時(shí)實(shí)現(xiàn)的效率低B．順序存儲(chǔ)的線(xiàn)性表可以隨機(jī)存取C．由于順序存儲(chǔ)要求連續(xù)的存儲(chǔ)區(qū)域，所以在存儲(chǔ)管理上不夠靈活D．線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造優(yōu)于順序存儲(chǔ)構(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ǔ)構(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(yíng)鏈表中。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(yíng)中出現(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è)具有一樣構(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)〕?！?〕設(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)構(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完畢?！?0〕長(zhǎng)度為n的線(xiàn)性表A采用順序存儲(chǔ)構(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++；∥假設(shè)值不為item，左移指針。if〔i<j〕while〔i<j&&A[j]==item〕j--；∥假設(shè)右端元素值為item，指針左移if〔i<j〕A[i++]=A[j--]；}[算法討論]因元素只掃描一趟，算法時(shí)間復(fù)雜度為O〔n〕。刪除元素未使用其它輔助空間，最后線(xiàn)性表中的元素個(gè)數(shù)是j。第3章棧和隊(duì)列習(xí)題1．選擇題〔1〕假設(shè)讓元素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〕假設(shè)一個(gè)棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，假設(shè)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指向棧頂.假設(shè)想摘除棧頂結(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大于等于0if(n<=0)return1;elsereturnn*fact(n-1);}那么計(jì)算fact(n)需要調(diào)用該函數(shù)的次數(shù)為〔〕。A．n+1B．n-1C．nD．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ū)的邏輯構(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，假設(shè)6個(gè)元素出隊(duì)的序列是e2、e4、e3、e6、e5和e1，那么棧S的容量至少應(yīng)該是〔〕。A．2B．3C．4D〔9〕在一個(gè)具有n個(gè)單元的順序棧中，假設(shè)以地址高端作為棧底，以top作為棧頂指針，那么當(dāng)作進(jìn)棧處理時(shí)，top的變化為〔〕。A．top不變B．top=0C．top--D．〔10〕設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號(hào)是否配對(duì)出現(xiàn)的算法，采用〔〕數(shù)據(jù)構(gòu)造最正確。A．線(xiàn)性表的順序存儲(chǔ)構(gòu)造B．隊(duì)列C.線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造D.?！?1〕用鏈接方式存儲(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ǔ)構(gòu)造定義

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

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

typedefstruct{

DataTypedata[StackSize];

inttop;

}SeqStack;

intIsHuiwen(char*t)

{//判斷t字符向量是否為回文，假設(shè)是，返回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)：用棧構(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棧空間容量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--])；}}}//算法完畢?！?〕從鍵盤(pán)上輸入一個(gè)后綴表達(dá)式，試編寫(xiě)算法計(jì)算表達(dá)式的值。規(guī)定：逆波蘭表達(dá)式的長(zhǎng)度不超過(guò)一行，以$符作為輸入完畢，操作數(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á)式完畢符$，這時(shí)OPND棧中只有一個(gè)數(shù)，就是結(jié)果。floatexpr()//從鍵盤(pán)輸入逆波蘭表達(dá)式，以‘$’表示輸入完畢，本算法求逆波蘭式表達(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)不作處理。}//完畢switchscanf(“%c〞,&x);//讀入表達(dá)式中下一個(gè)字符。}//完畢while〔x！=‘$’〕printf(“后綴表達(dá)式的值為%f〞,pop(OPND));}//算法完畢。[算法討論]假設(shè)輸入的后綴表達(dá)式是正確的，未作錯(cuò)誤檢查。算法中拼數(shù)局部是核心。假設(shè)遇到大于等于‘0’且小于等于‘9’的字符，認(rèn)為是數(shù)。這種字符的序號(hào)減去字符‘0’的序號(hào)得出數(shù)。對(duì)于整數(shù)，每讀入一個(gè)數(shù)字字符，前面得到的局部數(shù)要乘上10再加新讀入的數(shù)得到新的局部數(shù)。當(dāng)讀到小數(shù)點(diǎn)，認(rèn)為數(shù)的整數(shù)局部已完，要接著處理小數(shù)局部。小數(shù)局部的數(shù)要除以10〔或10的冪數(shù)〕變成十分位，百分位，千分位數(shù)等等，與前面局部數(shù)相加。在拼數(shù)過(guò)程中，假設(shè)遇非數(shù)字字符，表示數(shù)已拼完，將數(shù)壓入棧中，并且將變量num恢復(fù)為0，準(zhǔn)備下一個(gè)數(shù)。這時(shí)對(duì)新讀入的字符進(jìn)入‘+’、‘-’、‘*’、‘/’及空格的判斷，因此在完畢處理數(shù)字字符的case〔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è)算法，判定所給的操作序列是否合法。假設(shè)合法，返回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);}}//算法完畢。[算法討論]在入棧出棧序列〔即由‘I’和‘O’組成的字符串〕的任一位置，入棧次數(shù)〔‘I’的個(gè)數(shù)〕都必須大于等于出棧次數(shù)〔即‘O’的個(gè)數(shù)〕，否那么視作非法序列，立即給出信息，退出算法。整個(gè)序列〔即讀到字符數(shù)組中字符串的完畢標(biāo)記‘\0’(6〕假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾元素站點(diǎn)(注意不設(shè)頭指針)，試編寫(xiě)相應(yīng)的置空隊(duì)、判隊(duì)空、入隊(duì)和出隊(duì)等算法。

算法如下：

//先定義鏈隊(duì)構(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ě)與此構(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){ //建設(shè)一個(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)小的方向開(kāi)展，隊(duì)尾端入隊(duì)向下標(biāo)大的方向開(kāi)展?！?〕#defineM隊(duì)列可能到達(dá)的最大長(zhǎng)度typedefstruct{elemtpdata[M];intfront,rear;}cycqueue;〔2〕elemtpdelqueue(cycqueueQ)//Q是如上定義的循環(huán)隊(duì)列，本算法實(shí)現(xiàn)從隊(duì)尾刪除，假設(shè)刪除成功，返回被刪除元素，否那么給出出錯(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ì)尾刪除算法完畢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ì)頭指針。}//完畢從隊(duì)頭插入算法?！?〕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));}//算法完畢〔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]);}//算法完畢〔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),其值為itemvoidNewList(constintretvalue); //建設(shè)鏈表,以輸入retvalue完畢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){ //建設(shè)鏈表,以輸入retvalue完畢f(xié)irst=NULL;intvalue;ListNode*q;cout<<"Inputyourdata:\n"; //提示cin>>value; //輸入while(value!=retvalue){//輸入有效q=NewNode(value); //建設(shè)包含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; //遞歸完畢條件 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; //空表,返回0return1+Num(f->link); //否那么,返回后繼鏈表結(jié)點(diǎn)個(gè)數(shù)加1}floatList::Avg(ListNode*f,int&n){//遞歸算法:求鏈表中所有元素的平均值if(f->link==NULL) //鏈表中只有一個(gè)結(jié)點(diǎn),遞歸完畢條件{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<<“輸入建表完畢標(biāo)志數(shù)據(jù)：〞;cin>>finished; //輸入建表完畢標(biāo)志數(shù)據(jù)test.NewList(finished); //建設(shè)鏈表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)性表，其特殊性表達(dá)在〔〕。A．可以順序存儲(chǔ)B．?dāng)?shù)據(jù)元素是一個(gè)字符C．可以鏈?zhǔn)酱鎯?chǔ)D．?dāng)?shù)據(jù)元素可以是多個(gè)字符假設(shè)〔2〕串下面關(guān)于串的的表達(dá)中，〔〕是不正確的A．串是字符的有限序列B．空串是由空格構(gòu)成的串C．模式匹配是串的一種重要運(yùn)算D．串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)〔3〕串“ababaaababaa〞的next數(shù)組為〔〕。A．012345678999B．012121111212C．011234223456D．0123012322345〔4〕串“ababaabab〞的nextval為〔〕。A．010104101B．010102101C．〔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．〔7〕設(shè)有數(shù)組A[i,j]，數(shù)組的每個(gè)元素長(zhǎng)度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內(nèi)存首地址BA開(kāi)場(chǎng)順序存放，當(dāng)用以列為主存放時(shí)，元素A[5,8]的存儲(chǔ)首地址為〔〕。A．BA+141B．BA+180C．BA+222D〔8〕設(shè)有一個(gè)10階的對(duì)稱(chēng)矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間，那么a85的地址為〔〕。A．13B．33C．18D．〔9〕假設(shè)對(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〔12〕數(shù)組A[0..4,-1..-3,5..7]中含有元素的個(gè)數(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．a(chǎn)B．()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和〔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ù)值為0110132?！瞤的next函數(shù)值為0111232〕。=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)場(chǎng)連續(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〔〕〕!=‘#’〕//‘#’表示輸入字符串完畢。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]〕；｝//算法完畢?！?〕寫(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ī)定'.'是字符串輸入完畢標(biāo)志 {InvertStore(A); A[i++]=ch;//字符串逆序存儲(chǔ) }A[i]='\0';//字符串結(jié)尾標(biāo)記}//完畢算法InvertStore?！?〕編寫(xiě)算法，實(shí)現(xiàn)下面函數(shù)的功能。函數(shù)voidinsert(char*s,char*t,intpos)將字符串t插入到字符串s中，插入位置為pos。假設(shè)分配給字符串s的空間足夠讓字符串t插入?！舱f(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位置//假設(shè)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也指向‘\0while(*q!='\0'){q++;x++;}//查找字符串t的長(zhǎng)度x，循環(huán)完畢時(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的完畢標(biāo)記('\0')也后移了，而串t的結(jié)尾標(biāo)記不應(yīng)插入到s中?！?〕字符串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)=='')//假設(shè)最后一個(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字符串完畢標(biāo)記 } *q=s3;p++;//將s1串其余局部送字符串s3。while(*p!='\0'){*q=*p;q++;p++;} *q='\0';//置串s3完畢標(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完畢〔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)比較一次,所以在元素互不相等時(shí)總的比較次數(shù)為(m*n-1)+(m*n-2)+…+2+1=〔m*n〕(m*n-1)/2。在有一樣元素時(shí),可能第一次比較就一樣,也可能最后一次比較時(shí)一樣,設(shè)在(m*n-1)個(gè)位置上均可能一樣,這時(shí)的平均比較次數(shù)約為〔m*n〕(m*n-1)/4，總的時(shí)間復(fù)雜度是O(n4)。(10)設(shè)任意n個(gè)整數(shù)存放于數(shù)組A(1:n)中，試編寫(xiě)算法，將所有正數(shù)排在所有負(fù)數(shù)前面〔要求算法復(fù)雜性為0(n)〕。[題目分析]此題屬于排序問(wèn)題，只是排出正負(fù)，不排出大小?？稍跀?shù)組首尾設(shè)兩個(gè)指針i和j，i自小至大搜索到負(fù)數(shù)停頓，j自大至小搜索到正數(shù)停頓。然后i和j所指數(shù)據(jù)交換，繼續(xù)以上過(guò)程，直到i=j為止。voidArrange(intA[],intn)//n個(gè)整數(shù)存于數(shù)組A中，本算法將數(shù)組中所有正數(shù)排在所有負(fù)數(shù)的前面{inti=0,j=n-1,x;//用類(lèi)C編寫(xiě)，數(shù)組下標(biāo)從0開(kāi)場(chǎng)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完畢.[算法討論]對(duì)數(shù)組中元素各比較一次，比較次數(shù)為n。最正確情況(已排好,正數(shù)在前,負(fù)數(shù)在后)不發(fā)生交換，最差情況(負(fù)數(shù)均在正數(shù)前面)發(fā)生n/2次交換。用類(lèi)c編寫(xiě)，數(shù)組界偶是0..n-1?？臻g復(fù)雜度為O(1).第5章樹(shù)和二叉樹(shù)A．Ｂ．C．有多種，但根結(jié)點(diǎn)都沒(méi)有左孩子Ｄ．有多種，但根結(jié)點(diǎn)都沒(méi)有右孩子由3個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹(shù)〔〕A．2B．3C．4一棵完全二叉樹(shù)上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是〔〕A．250B．500C．254D．一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹(shù)的高h(yuǎn)為〔〕A．11B．10C．11至1025之間D深度為h的滿(mǎn)m叉樹(shù)的第k層有〔〕個(gè)結(jié)點(diǎn)。(1=<k=<h)A．mk-1B．mk-1C．mh-1D．m利用二叉鏈表存儲(chǔ)樹(shù)，那么根結(jié)點(diǎn)的右指針是〔〕A．指向最左孩子B．指向最右孩子C．空D．非空對(duì)二叉樹(shù)的結(jié)點(diǎn)從1開(kāi)場(chǎng)進(jìn)展連續(xù)編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左、右孩子的編號(hào)，同一結(jié)點(diǎn)的左右孩子中，其左孩子的編號(hào)小于其右孩子的編號(hào)，可采用〔〕遍歷實(shí)現(xiàn)編號(hào)。A．先序B.中序C.后序D.從根開(kāi)場(chǎng)按層次遍歷假設(shè)二叉樹(shù)采用二叉鏈表存儲(chǔ)構(gòu)造，要交換其所有分支結(jié)點(diǎn)左、右子樹(shù)的位置，利用〔〕遍歷方法最適宜。A．前序B．中序C．后序D．按層次在以下存儲(chǔ)形式中，〔〕不是樹(shù)的存儲(chǔ)形式A．雙親表示法B．孩子鏈表表示法C．孩子兄弟表示法D．順序存儲(chǔ)表示法一棵非空的二叉樹(shù)的先序遍歷序列與后序遍歷序列正好相反，那么該二叉樹(shù)一定滿(mǎn)足〔〕A．所有的結(jié)點(diǎn)均無(wú)左孩子B．所有的結(jié)點(diǎn)均無(wú)右孩子C．只有一個(gè)葉子結(jié)點(diǎn)D．是任意一棵二叉樹(shù)某二叉樹(shù)的前序序列和后序序列正好相反，那么該二叉樹(shù)一定是〔〕的二叉樹(shù)。A．空或只有一個(gè)結(jié)點(diǎn)B．任一結(jié)點(diǎn)無(wú)左子樹(shù)C．高度等于其結(jié)點(diǎn)數(shù)D．任一結(jié)點(diǎn)無(wú)右子樹(shù)假設(shè)X是二叉中序線(xiàn)索樹(shù)中一個(gè)有左孩子的結(jié)點(diǎn)，且X