習(xí)題集第一章習(xí)題一、填空題1.數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D，R），其中D是_________的有限集合，R是_________的有限集合。2.3.線(xiàn)性結(jié)構(gòu)中元素之間存在_________關(guān)系，樹(shù)形結(jié)構(gòu)中元素之間存在_________關(guān)系，圖形結(jié)構(gòu)中元素之間存在_________關(guān)系。4.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用4種基本的存儲(chǔ)方法表示，分別是_____、_____、_____、_____。5.數(shù)據(jù)常用的運(yùn)算有5種，分別是_____、_____、_____、_____、_____。6.數(shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是和。7.一個(gè)算法具有5個(gè)特性：_____、_____、_____、有零個(gè)或多個(gè)輸入、有一個(gè)或多個(gè)輸出。8.下面程序段的時(shí)間復(fù)雜度為_(kāi)____。sum=1;for(i=0;sum<n;i++)sum+=1；9.下面程序段的時(shí)間復(fù)雜度為_(kāi)____。i=1;while(i<=n)i=i*3;10.鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)是利用_____來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。二、選擇題1.數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容不涉及（）A．?dāng)?shù)據(jù)如何組織B.數(shù)據(jù)如何存儲(chǔ)C．?dāng)?shù)據(jù)的運(yùn)算如何實(shí)現(xiàn)D.算法用什么語(yǔ)言來(lái)描述2.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的什么結(jié)構(gòu)（）。A.存儲(chǔ)B.物理C.邏輯D.物理和存儲(chǔ)3.算法分析的目的是（）。A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中的輸入和輸出的關(guān)系C.分析算法的效率以求改進(jìn)D.分析算法的易懂性和文檔性4.計(jì)算機(jī)算法指的是（）。A.計(jì)算方法B.排序方法C.解決問(wèn)題的有限運(yùn)算序列D.調(diào)度方法5.計(jì)算算法的時(shí)間復(fù)雜度是屬于一種（）A．事前統(tǒng)計(jì)的方法B.事前分析估算的方法C．事后統(tǒng)計(jì)的方法D.事后分析估算的方法。6.數(shù)據(jù)元素之間的關(guān)系稱(chēng)為（）A．操作B.結(jié)構(gòu)C.數(shù)據(jù)對(duì)象D.數(shù)據(jù)集合7.當(dāng)輸入非法錯(cuò)誤時(shí)，一個(gè)“好”的算法會(huì)進(jìn)行適當(dāng)處理，而不會(huì)產(chǎn)生難以理解的輸出結(jié)果。這稱(chēng)為算法的（）A．可讀性B.健壯性C.無(wú)二義性D.可讀性好的8.下列函數(shù)中漸進(jìn)時(shí)間復(fù)雜度最小的是（）A．Tn=logC.Tn=n9.下面程序的時(shí)間復(fù)雜度是（）for(inti=0;i<m;i++)for(intj=0;j<n;j++)a[i][j]=i*j;A.O(n2)B.O(m*n)C.O(10.某算法的時(shí)間復(fù)雜度為O(n2A．問(wèn)題規(guī)模是n2B.執(zhí)行時(shí)間等于C．執(zhí)行時(shí)間與n2成正比D.問(wèn)題規(guī)模與n三、分析題閱讀下列算法：Voidsuan-fa(intn){inti，j，k，s，x；for(s=0,i=0;i<n;i++)for(j=i;j<n;j++)s++;i=1;j=n;x=0;while(i<j){i++；j--；x+=2；}Printf(s=“%d”,x=“%d”，s，x)；}分析算法中語(yǔ)句“s++”的執(zhí)行次數(shù)；分析算法中語(yǔ)句“x+=2”的執(zhí)行次數(shù)；分析算法的時(shí)間復(fù)雜度；假定n=5;試寫(xiě)出執(zhí)行該算法的輸出結(jié)果。四、簡(jiǎn)答題1.簡(jiǎn)述將一個(gè)現(xiàn)實(shí)問(wèn)題轉(zhuǎn)化為可用計(jì)算機(jī)解決的問(wèn)題的過(guò)程。2.簡(jiǎn)述構(gòu)建或使用函數(shù)應(yīng)關(guān)注哪些屬性。3.當(dāng)你為解決某一問(wèn)題而選擇數(shù)據(jù)結(jié)構(gòu)時(shí)，應(yīng)從哪些方面考慮？答：通?？紤]算法運(yùn)行所需要的存儲(chǔ)空間量和時(shí)間量。后者又涉及三方面：程序運(yùn)行時(shí)所需輸入的數(shù)據(jù)總量，計(jì)算機(jī)執(zhí)行每條指令所需時(shí)間和程序中指令重復(fù)執(zhí)行的次數(shù)。4.設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)S=（D，R），試按各小題所給條件畫(huà)出這些邏輯結(jié)構(gòu)的圖示，并確定相對(duì)應(yīng)關(guān)系R，哪些結(jié)點(diǎn)是開(kāi)始結(jié)點(diǎn)，哪些結(jié)點(diǎn)是終端結(jié)點(diǎn)。（1）D={d1，d2，d3，d4}R={（d1，d2）,（d2，d3）,（d3，d4）}（2）D={d1，d2，，d9}

R={（d1，d2），（d1，d3），（d3，d4），（d3，d6），（d6，d8），（d4，d5），（d6，d7），（d8，d9）}（3）D={d1，d2，，d9}R={（d1，d3），（d1，d8），（d2，d3），（d2，d4），（d2，d5），（d3，d9），（d5，d6），（d8，d9），（d9，d7），（d4，d7），（d4，d6）}第二章習(xí)題一、判斷題（）1.線(xiàn)性表中每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼。（）2.線(xiàn)性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類(lèi)型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類(lèi)型。（）3.線(xiàn)性表的物理存儲(chǔ)空間中也一定是連續(xù)的。（）4.順序表結(jié)構(gòu)適合于進(jìn)行順序存取，而鏈表適合于進(jìn)行隨機(jī)存取。（）5.順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。（）6.鏈表的物理存儲(chǔ)結(jié)構(gòu)具有與鏈表表達(dá)的邏輯結(jié)構(gòu)一樣的順序。（）7.鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針。（）8.帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，任一結(jié)點(diǎn)的后繼結(jié)點(diǎn)的指針域均不為空。（）9.在單鏈表中，要訪(fǎng)問(wèn)某個(gè)結(jié)點(diǎn)，只要知道該結(jié)點(diǎn)的指針即可，因此，單鏈表是一種隨機(jī)存取結(jié)構(gòu)。（）10.在具有頭結(jié)點(diǎn)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，頭指針指向鏈表中的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)。二、選擇題A.存儲(chǔ)結(jié)構(gòu)B.邏輯結(jié)構(gòu)C.順序存儲(chǔ)結(jié)構(gòu)D.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2.一個(gè)向量的第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的地址是（）。A.110

B.108C.100

D.1203.在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)從小到大排序4.向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變，平均要移動(dòng)（）個(gè)元素。A.8

B.63.5C.63

D.75.鏈接存儲(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ù)6.線(xiàn)性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（）。A.必須是連續(xù)的B.部分地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)或不連續(xù)都可以7.線(xiàn)性表L在（）情況下適合使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。A.需經(jīng)常修改L中的結(jié)點(diǎn)值

B.需不斷對(duì)L進(jìn)行刪除插入C.L中含有大量的結(jié)點(diǎn)D.L中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜8.在非空雙向循環(huán)鏈表（結(jié)點(diǎn)指針域分別為pre和next）中q所指的結(jié)點(diǎn)前插入一個(gè)由p所指的鏈結(jié)點(diǎn)的過(guò)程依次為（）。A.q?>pre=p;p->next=q;B.t=q?>pre;t->next=p;p->next=q;C.t=q?>pre;t->next=p;p->pre=t;p->next=q;D.t=q?>pre;t->next=p;p->next=q;q->pre=p;p->pre=t;9.帶頭結(jié)點(diǎn)的單鏈表L為空的判定條件是（）。A.L==NULL

B.L?>next==NULLC.L?>next==L

D.L!=NULL10.設(shè)單循環(huán)鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為(data,next),且rear是指向非空的帶頭結(jié)點(diǎn)的單循環(huán)鏈表的尾結(jié)點(diǎn)的指針。若要?jiǎng)h除鏈表的第一個(gè)結(jié)點(diǎn)，正確的操作是（）A．s=rear;rear=rear->next;free(s);B.rear=rear->next;free(s);C.rear=rear->next->next;free(s);D.s=rear->next->next;rear-next->next=s->next;free(s);三、填空題1.在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)__________個(gè)元素，具體移動(dòng)的元素個(gè)數(shù)與__________有關(guān)。2.在順序表中訪(fǎng)問(wèn)任意一結(jié)點(diǎn)的時(shí)間復(fù)雜度均為_(kāi)_________，因此，順序表也稱(chēng)為_(kāi)_________的數(shù)據(jù)結(jié)構(gòu)。3.順序表中邏輯上相鄰的元素在物理位置上__________相鄰，單鏈表中邏輯上相鄰的元素在物理位置上__________相鄰。4.5.在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p，須找到它的__________，其時(shí)間復(fù)雜度為_(kāi)_________。6.當(dāng)線(xiàn)性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線(xiàn)性表中的元素時(shí)，應(yīng)采用存儲(chǔ)結(jié)構(gòu)。7.有一個(gè)無(wú)頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)有數(shù)據(jù)域data,指針域next,表頭指針為h,通過(guò)遍歷鏈表，將鏈表中所有的鏈接方向逆轉(zhuǎn)。要求逆轉(zhuǎn)后的鏈表的表頭指針h指向原鏈表的最后一個(gè)結(jié)點(diǎn)。算法如下所示，請(qǐng)?jiān)诳崭裉幪钊胝_的語(yǔ)句。VoidInverse(&h){Ifreturn;p=h->next;pr=NULL;while{h->next=pr;pr=h;h=p;;}h->next=pr;}8.對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)*p后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為，在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為。四、簡(jiǎn)答題1.試比較順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。在什么情況下用順序表比鏈表好？2.描述以下三個(gè)概念的區(qū)別：頭指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn)（第一個(gè)元素結(jié)點(diǎn)）。在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是什么？3.閱讀下面的算法，說(shuō)明算法實(shí)現(xiàn)的功能。Node*link(node*head1,*head2){Node*p,*q;P=head1;While(p->next!=head1)p=p->next;q=head2；while（q->next!=head2）q=q->next;p->next=head2;q->next=head1;return(head1);}4.請(qǐng)簡(jiǎn)要說(shuō)明下列函數(shù)的主要功能。voidfunc(LinkListL1,LinkListL2){LNode*p,*q,*r;q=L2->next;while(q){P=L1;while(p->next){if(p->next->data==q->data){r=p->next;p->next=r->next;free(r);}p=p->next；}q=q->next；}return；}五、算法設(shè)計(jì)題1.編寫(xiě)算法實(shí)現(xiàn)順序表的按序號(hào)查找和按值查找。2.編寫(xiě)算法實(shí)現(xiàn)單鏈表的建立。3.編寫(xiě)算法實(shí)現(xiàn)單鏈表的按序號(hào)查找和按值查找。4.編寫(xiě)算法實(shí)現(xiàn)單鏈表逆置。5.已知帶頭結(jié)點(diǎn)的單鏈表有data和next兩個(gè)域，設(shè)計(jì)一個(gè)算法，將該鏈表中的重復(fù)元素結(jié)點(diǎn)刪除。第三章習(xí)題一、判斷題（）1.在表結(jié)構(gòu)中最常用的是線(xiàn)性表，棧和隊(duì)列不常用。（）2.對(duì)于不同的使用者，一個(gè)表結(jié)構(gòu)既可以是棧，又可以是隊(duì)列，或是線(xiàn)性表。（）3.同一組不重復(fù)輸入序列執(zhí)行不同的入出棧組合操作，所得結(jié)果也可能相同。（）4.棧和隊(duì)列是非線(xiàn)性數(shù)據(jù)結(jié)構(gòu)。（）5.棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，又可是鏈接方式。（）6.兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存利用率，減少溢出機(jī)會(huì)，應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。（）7.隊(duì)列是一種插入與刪除操作分別在表的兩端進(jìn)行的線(xiàn)性表，是一種先進(jìn)后出形式的結(jié)構(gòu)。（）8.一個(gè)棧的輸入序列是12345，則棧的輸出序列不可能是12345。（）9.隊(duì)列在程序調(diào)用時(shí)必不可少，因此遞歸離不開(kāi)隊(duì)列。（）10.設(shè)立尾指針的循環(huán)鏈表表示隊(duì)列，則入隊(duì)和出隊(duì)算法的時(shí)間復(fù)雜度均為O(1)。二、選擇題1.判定一個(gè)順序棧ST（最多元素為m0）為空的條件是（）。A.ST->top<0B.ST->top=0C.ST->top<>m0

D.ST->top=m02.判定一個(gè)隊(duì)列QU（最多元素為m0）為滿(mǎn)隊(duì)列的條件是（）。A.QU->rear－QU->front==m0B.QU->rear－QU->front－1==m0C.QU->front==QU->rearD.QU->front==QU->rear+13.數(shù)組Q［n］表示一個(gè)循環(huán)隊(duì)列，f為當(dāng)前隊(duì)列頭元素的前一位置，r為隊(duì)尾元素的位置，假定隊(duì)列中元素的個(gè)數(shù)小于n，計(jì)算隊(duì)列中元素的公式為（）。A.r?fB.（n＋f?r）%nC.n＋r?f

D.（n＋r?f）%n4.向一個(gè)棧頂指針為top的鏈棧中插入一個(gè)S所指結(jié)點(diǎn)時(shí)，則執(zhí)行（）。A.top->next=S;B.S->next=top->next;top->next=S;C.S->next=top;top=S;

D.S->next=top;top=top->next;5.若已知一個(gè)棧的入棧序列是1，2，3，，n，其輸出序列為p1，p2，p3，，pn，若p1=n，則pi為（）。A.iB.n=iC.n?i+1

D.不確定6.有六個(gè)元素按照6、5、4、3、2、1的順序進(jìn)棧，問(wèn)下列哪一個(gè)不是合法的出棧序列（）。A.543612B.453126C.346521D.2341567.若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為（）。A.1和5B.2和4C.4和2

D.5和18.為解決計(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.棧B.隊(duì)列C.樹(shù)D.圖9.執(zhí)行完下列語(yǔ)句段后，i值為（）intf(intx){return((x>0)?x*f(x-1):2);}inti;i=f(f(1));A.2B.4C.8D.1010.輸入序列為ABC，可以變?yōu)镃BA時(shí)，經(jīng)過(guò)的棧操作為（）A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop三、填空題1.線(xiàn)性表、棧和隊(duì)列都是________結(jié)構(gòu)，可以在線(xiàn)性表的________位置插入和刪除元素；對(duì)于棧只能在________插入和刪除元素；對(duì)于隊(duì)列只能在________插入和________刪除元素。2.棧是一種特殊的線(xiàn)性表，允許插入和刪除運(yùn)算的一端稱(chēng)為_(kāi)_______，不允許插入和刪除運(yùn)算的一端稱(chēng)為_(kāi)_______。3.________是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線(xiàn)性表。4.在一個(gè)循環(huán)隊(duì)列中，隊(duì)頭指針指向隊(duì)頭元素的________位置。5.在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿(mǎn)時(shí)共有________個(gè)元素。6.向棧中壓入元素的操作是先________后________。7.從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是先________，后________。8.帶表頭結(jié)點(diǎn)的空循環(huán)雙向鏈表的長(zhǎng)度等于________。9.在循環(huán)隊(duì)列中，隊(duì)列長(zhǎng)度為n,存儲(chǔ)位置從0到n-1編號(hào)，以rear指示實(shí)際的隊(duì)尾元素，現(xiàn)要在此隊(duì)列中插入一個(gè)新元素，新元素的位置是________。10.用S表示入棧操作，X表示出棧操作，若元素入棧順序?yàn)?,2,3,4，則為了得到1,3,4,2的出棧順序，相應(yīng)的S和X操作串為。四、簡(jiǎn)答題1.說(shuō)明線(xiàn)性表、棧與隊(duì)列的異同點(diǎn)。2.順序隊(duì)的“假溢出”是怎樣產(chǎn)生的？如何知道循環(huán)隊(duì)列是空還是滿(mǎn)？3.設(shè)循環(huán)隊(duì)列的容量為40（序號(hào)從0～39），現(xiàn)經(jīng)過(guò)一系列的入隊(duì)和出隊(duì)運(yùn)算后，有：（1）front=11，rear=19;（2）front=19，rear=11；問(wèn)在這兩種情況下，循環(huán)隊(duì)列中各有元素多少個(gè)？4.（1）什么是遞歸程序。（2）遞歸程序的優(yōu)、缺點(diǎn)。（3）遞歸程序在執(zhí)行時(shí)，應(yīng)借助于什么來(lái)完成。（4）遞歸程序的入口語(yǔ)句、出口語(yǔ)句一般用什么語(yǔ)句實(shí)現(xiàn)。5.寫(xiě)出下列程序段的輸出結(jié)果（隊(duì)列中的元素類(lèi)型QElemType為char）。voidmain（）{QueueQ;InitQueue（Q）;Charx=‘e’;y=’c’;EnQueue（Q,‘h’）;EnQueue（Q,‘r’）;EnQueue（Q,‘y’）;DeQueue（Q,x）;EnQueue（Q,x）;DeQueue（Q,x）;EnQueue（Q,‘a(chǎn)’）;while（!QueueEmpty（Q））{DeQueue（Q,y）;printf（y）;}Printf（x）;}6.簡(jiǎn)述以下算法的功能（棧和隊(duì)列的元素類(lèi)型均為int）。voidalgo3（Queue&Q）{StackS;intd;InitStack（S）;while（!QueueEmpty（Q））{DeQueue（Q,d）;Push（S,d）;while（!StackEmpty（S））{Pop（S,d）;EnQueue（Q,d）;}}五、算法設(shè)計(jì)題（可以?xún)H寫(xiě)出算法思想，也可以用C語(yǔ)言函數(shù)實(shí)現(xiàn)）1.假設(shè)一個(gè)算術(shù)表達(dá)式中包含圓括號(hào)、方括號(hào)和花括號(hào)三種類(lèi)型的括號(hào)，編寫(xiě)一個(gè)判別表達(dá)式中，括號(hào)是否正確配對(duì)的函數(shù)correct（exp）；其中，exp為字符串類(lèi)型的變量（可理解為每個(gè)字符占用一個(gè)數(shù)組元素），函數(shù)用來(lái)判別該數(shù)學(xué)表達(dá)式是否正確。2.假設(shè)一個(gè)數(shù)組squ[m]存放循環(huán)隊(duì)列的元素。若要使這m個(gè)分量都得到利用，則需另一個(gè)標(biāo)志tag，以tag為0或1來(lái)區(qū)分尾指針和頭指針值相同時(shí)隊(duì)列的狀態(tài)是“空”還是“滿(mǎn)”。試編寫(xiě)相應(yīng)的入隊(duì)和出隊(duì)的算法。第四章習(xí)題一、選擇題1．設(shè)主串T=“abaabaabcabaabc”,模式串S=“abaabc”,采用KMP算法進(jìn)行模式匹配，到匹配成功時(shí)為止，在匹配過(guò)程中進(jìn)行的單個(gè)字符間的比較次數(shù)是（）A.9B.10C.12D.152.已知字符串S為“abaabaabacacaabaabcc”,模式串t為“abaabc”,采用KMP算法進(jìn)行匹配，第一次出現(xiàn)“不匹配”時(shí)，i=j=5,則下次開(kāi)始匹配時(shí)，i和j的值分別是（）。A.i=1,j=0B.i=5,j=0C.i=5,j=2D.i=6,j=23.下面關(guān)于串的敘述中，哪一個(gè)是不正確的（）。A.串是字符的有限序列B.空串是由空格構(gòu)成的串C.模式匹配是串的一種重要運(yùn)算D.串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)4.若串S為“Myself”，則其子串的數(shù)目是（）A.20B.21C.22D.235.串是一種特殊的線(xiàn)性表，其特殊性體現(xiàn)在（）A.可以順序存儲(chǔ)B.數(shù)據(jù)元素是一個(gè)字符C.可以鏈接存儲(chǔ)D.數(shù)據(jù)元素可以是多個(gè)字符二、填空題1.組成串的數(shù)據(jù)元素只能是。2.設(shè)正文串長(zhǎng)度為n,模式串長(zhǎng)度為m,則串匹配的KMP算法的時(shí)間復(fù)雜度為。3.設(shè)T和P是兩個(gè)給定的串，在T中尋找等于P的子串的過(guò)程稱(chēng)為，又稱(chēng)P為。4.模式串P=’abaabcac’的next函數(shù)值序列為。5.使用“求子串”substring(S,pos,len)和“連接”concat(S1,S2)的串操作，可從串s=’conduction’中的字符得到串t=’cont’,則求t的串表達(dá)式為。6.設(shè)目標(biāo)T=”abccdcdccbaa”，模式P=“cdcc”，則采用樸素匹配算法第次匹配成功。7.實(shí)現(xiàn)字符串拷貝的函數(shù)strcpy為voidstrcpy(char*s,char*t)/*copytos*/{while;}8.下列程序判斷字符串s是否對(duì)稱(chēng)，對(duì)稱(chēng)則返回1，否則返回0,；如f(“abba”)返回1，f(“abab”)返回0。intf{inti=0,j=0;while(s[j]);for(j--;i<j&&s[i]==s[j];i++,j--);return;}三、應(yīng)用分析題1.在字符串模式匹配的KMP算法中，求模式的next數(shù)組值的定義如下：next（1）當(dāng)j=1時(shí)，為什么要取next[1]=0?（2）為什么要取max?{K}（3）其他情況是什么情況，為什么取next[j]=1?2.設(shè)字符串S='aabaabaabaac',P='abcabaa'。（1）計(jì)算S和P的next值。（2）若S作主串，P作模式串，試給出利用BF算法和KMP算法的匹配過(guò)程。四、算法設(shè)計(jì)題1.若X和Y是用結(jié)點(diǎn)大小為1的單鏈表表示的串，試設(shè)計(jì)一個(gè)算法找出X中第一個(gè)不在Y中出現(xiàn)的字符。2.試設(shè)計(jì)一個(gè)算法，在順序串上實(shí)現(xiàn)串的比較運(yùn)算strcmp（S，T）。3.若S和T是用結(jié)點(diǎn)大小為1的單鏈表存儲(chǔ)的兩個(gè)串，試設(shè)計(jì)一個(gè)算法將S中首次與串T匹配的子串逆置。第五章習(xí)題一、選擇題1、設(shè)二維數(shù)組A[1..m,1..n]按行存儲(chǔ)在數(shù)組B[1..m*n]中，則二維數(shù)組元素Ai,j在一維數(shù)組B中的下標(biāo)為（A．i-1*n+jB.C.i*(j-1)D.j*m+i-12、設(shè)有一個(gè)12×12的對(duì)稱(chēng)矩陣M，將其上三角部分的元素mi,j1≤i≤j≤12按行優(yōu)先存入C或Java語(yǔ)言的一維數(shù)組N中，那么元素m6,6A．50B.51C.55D.663、適用于壓縮存儲(chǔ)稀疏矩陣的兩種存儲(chǔ)結(jié)構(gòu)是（）A．三元組表和十字鏈表B.三元組表和鄰接矩陣C．十字鏈表和二叉鏈表D.鄰接矩陣和十字鏈表4、對(duì)矩陣壓縮存儲(chǔ)是為了（）A．方便運(yùn)算B.方便儲(chǔ)存C.提高運(yùn)算速度D.減少儲(chǔ)存空間5、在稀疏矩陣的快速轉(zhuǎn)置算法中，num[col]表示源矩陣M中（）A．第col行中非零元的個(gè)數(shù)B.第col行中零元的個(gè)數(shù)C．第col列中非零元的個(gè)數(shù)D．第col列中零元的個(gè)數(shù)6、對(duì)n階對(duì)稱(chēng)矩陣作壓縮存儲(chǔ)時(shí)，需要表長(zhǎng)為（）的順序表。A．n/2B.n2/2C.n(n+1)/2D.n(n-1)/27、一個(gè)非空廣義表的表尾（）A．不能是子表B.只能是子表C.只能是原子D.是原子或子表8、廣義表（（））的表頭是（）。A．（）B.NULLC.（（））D.（（（）））9、某字符串滿(mǎn)足concat(head(s),head(tail(tail(s))))=”ac”,則s=().A.aabcB.acbaC.acccD.acac10、下面說(shuō)法不正確的是（）A．廣義表的表頭總是一個(gè)廣義表B.廣義表的表尾總是一個(gè)廣義表C．廣義表難以用順序存儲(chǔ)結(jié)構(gòu)D.廣義表可以是一個(gè)多層次結(jié)構(gòu)二、填空題1.數(shù)組的存儲(chǔ)結(jié)構(gòu)采用存儲(chǔ)方式。2.二維數(shù)組A[10..20,5..10]采用行序?yàn)橹餍蚍绞酱鎯?chǔ)，每個(gè)數(shù)據(jù)元素占4個(gè)存儲(chǔ)單元，且[10,5]的存儲(chǔ)地址是1000，則A[18,9]的存儲(chǔ)地址是。3.對(duì)于數(shù)組An*n,每個(gè)數(shù)組元素所占存儲(chǔ)單元數(shù)為L(zhǎng)，其元素aij按行優(yōu)先與按列優(yōu)先存儲(chǔ)時(shí)地址之差為4.有一個(gè)10階對(duì)稱(chēng)矩陣A，采用壓縮存儲(chǔ)方式（下三角），以行序?yàn)橹餍?，且A[0][0]=1,每個(gè)元素占1個(gè)單元，則A[8][5]的地址為。5.已知三對(duì)角矩陣A[1..9,1..9]的每個(gè)元素占2個(gè)單元，現(xiàn)將其三條對(duì)角線(xiàn)上的元素逐行存儲(chǔ)在起始地址為1000的連續(xù)內(nèi)存單元中，則元素A[7,8]的地址為。6.廣義表（A，B，C，D）的表尾是。7.設(shè)有廣義表LS=（（a,b,c）,(d,e,f)）,取出原子e的運(yùn)算是。8.廣義表A（b,A）的長(zhǎng)度為，深度為。9、廣義表(a,(a,b),d,e,((i,j),k))的長(zhǎng)度是，深度是。10.已知廣義表A=(((a,b),(c),(d,e))),head(tail(tail(head(A))))的結(jié)果是。三、分析題1.按行優(yōu)先順序列出四維數(shù)組A[2][3][2][3]所有元素在內(nèi)存中的存放次序。2.作出矩陣X的三元組表和十字鏈表。四、算法設(shè)計(jì)題1、若在矩陣中存放一個(gè)元素A[i?1][j?1]滿(mǎn)足：A[i?1][j?1]是第i行元素中的最小值，且又是第j列元素中的最大值，則稱(chēng)此元素為該矩陣的一個(gè)馬鞍點(diǎn)。假設(shè)以二維數(shù)組存儲(chǔ)矩陣，試編寫(xiě)求矩陣中所有馬鞍點(diǎn)的算法，并分析該算法在最壞情況下的時(shí)間復(fù)雜度。2、給定n×m矩陣Aa..b,c..d,并設(shè)Ai,j≤A[i,j+1](a≤i≤b,c≤j≤d-1)和A第九章一、1.D2．B3．A4.B5.A6.D7.A8.B9.D10.C二、填空題1.順序查找2.83.1、2、8、3.74.28,6,12,205.散列查找6.關(guān)鍵字的值7.n(n-1)28.2.9、2.9、2.2、1.29.有時(shí)不相同10.11