線性結(jié)構(gòu)各章習(xí)題及答案

第1章概述【例1-1】分析以下程序段的時(shí)間復(fù)雜度。for(i=0;i<n;i++)for(j=0;j<m;j++)A[i][j]=0;解：該程序段的時(shí)間復(fù)雜度為O(m*n)?！纠?-2】分析以下程序段的時(shí)間復(fù)雜度。i=s=0;①while(s<n){i++;②s+=i;③}解：語句①為賦值語句，其執(zhí)行次數(shù)為1次，所以其時(shí)間復(fù)雜度為O(1)。語句②和語句③構(gòu)成while循環(huán)語句的循環(huán)體，它們的執(zhí)行次數(shù)由循環(huán)控制條件中s與n的值確定。假定循環(huán)重復(fù)執(zhí)行x次后結(jié)束，則語句②和語句③各重復(fù)執(zhí)行了x次。其時(shí)間復(fù)雜度按線性累加規(guī)則為O(x)。此時(shí)s與n滿足關(guān)系式：s≥n，而s=1+2+3+…+x。所以有：1+2+3+…+x≥n，可以推出：x=x與n之間滿足x=f(），所以循環(huán)體的時(shí)間復(fù)雜度為O()，語句①與循環(huán)體由線性累加規(guī)則得到該程序段的時(shí)間復(fù)雜度為O(）?！纠?-3】分析以下程序段的時(shí)間復(fù)雜度。i=1;①while(i<=n)i=2*i;②解：其中語句①的執(zhí)行次數(shù)是1，設(shè)語句②的執(zhí)行次數(shù)為f(n)，則有：。得：T（n）=O()【例1-4】有如下遞歸函數(shù)fact(n)，分析其時(shí)間復(fù)雜度。fact(intn){if(n<=1)return(1);①elsereturn(n*fact(n-1));②}解：設(shè)fact（n）的運(yùn)行時(shí)間函數(shù)是T(n)。該函數(shù)中語句①的運(yùn)行時(shí)間是O(1)，語句②的運(yùn)行時(shí)間是T(n-1)+O(1)，其中O(1)為常量運(yùn)行時(shí)間。由此可得fact（n）的時(shí)間復(fù)雜度為O(n)。習(xí)題1一、單項(xiàng)選擇題1.數(shù)據(jù)結(jié)構(gòu)是指（1.A）。A.數(shù)據(jù)元素的組織形式 B.數(shù)據(jù)類型C.數(shù)據(jù)存儲結(jié)構(gòu)D.數(shù)據(jù)定義2.數(shù)據(jù)在計(jì)算機(jī)存儲器內(nèi)表示時(shí)，物理地址與邏輯地址不相同的，稱之為（2.C）。A.存儲結(jié)構(gòu) B.邏輯結(jié)構(gòu)C.鏈?zhǔn)酱鎯Y(jié)構(gòu) D.順序存儲結(jié)構(gòu)3.樹形結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種（3.D）。A.一對一關(guān)系 B.多對多關(guān)系C.多對一關(guān)系 D.一對多關(guān)系4.設(shè)語句x++的時(shí)間是單位時(shí)間，則以下語句的時(shí)間復(fù)雜度為（4.B）。for(i=1;i<=n;i++)for(j=i;j<=n;j++)x++;A.O(1) B.O() C.O(n) D.O()5.算法分析的目的是（5.C、），算法分析的兩個(gè)主要方面是（A）。（1）A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中的輸入和輸出關(guān)系C.分析算法的效率以求改進(jìn)D.分析算法的易懂性和文檔性（2）A.空間復(fù)雜度和時(shí)間復(fù)雜度B.正確性和簡明性C.可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性6.計(jì)算機(jī)算法指的是（6.C、），它具備輸入，輸出和（B）等五個(gè)特性。（1）A.計(jì)算方法B.排序方法C.解決問題的有限運(yùn)算序列D.調(diào)度方法（2）A.可行性，可移植性和可擴(kuò)充性B.可行性，確定性和有窮性C.確定性，有窮性和穩(wěn)定性D.易讀性，穩(wěn)定性和安全性7.數(shù)據(jù)在計(jì)算機(jī)內(nèi)有鏈?zhǔn)胶晚樞騼煞N存儲方式，在存儲空間使用的靈活性上，鏈?zhǔn)酱鎯Ρ软樞虼鎯σ?.B）。A.低 B.高 C.相同 D.不好說8.數(shù)據(jù)結(jié)構(gòu)作為一門獨(dú)立的課程出現(xiàn)是在（8.D）年。A.1946 B.1953 C.1964 D.9.數(shù)據(jù)結(jié)構(gòu)只是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，這種觀點(diǎn)（9.B）。A.正確 B.錯(cuò)誤C.前半句對，后半句錯(cuò) D.前半句錯(cuò)，后半句對10.計(jì)算機(jī)內(nèi)部數(shù)據(jù)處理的基本單位是（10.B）。A.數(shù)據(jù)B.數(shù)據(jù)元素 C.數(shù)據(jù)項(xiàng) D.數(shù)據(jù)庫二、填空題1.數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，分別是______________和_________________。1.線性結(jié)構(gòu)，非線性結(jié)構(gòu)2.數(shù)據(jù)的邏輯結(jié)構(gòu)有四種基本形態(tài)，分別是________________、__________________、__________________和__________________。2.集合，線性，樹，圖3.線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是__________________的，非線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是__________________的。3.一對一，一對多或多對多4.一個(gè)算法的效率可分為__________________效率和__________________效率。4.時(shí)間，空間5.在樹型結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有__________________結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的有且只有__________________個(gè)前趨驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有__________________結(jié)點(diǎn)；其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以__________________。5.前趨，一，后繼，多6.在圖型結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前趨結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以__________________。6.有多個(gè)7.線性結(jié)構(gòu)中元素之間存在__________________關(guān)系；樹型結(jié)構(gòu)中元素之間存在__________________關(guān)系；圖型結(jié)構(gòu)中元素之間存在__________________關(guān)系。7.一對一，一對多，多對多8.下面程序段的時(shí)間復(fù)雜度是__________________。8.O()for(i=0;i<n;i++)for(j=0;j<n;j++)A[i][j]=0;9.下面程序段的時(shí)間復(fù)雜度是__________________。9.O()i=s=0;while(s<n){i++;s+=i;}10.下面程序段的時(shí)間復(fù)雜度是__________________。10.O()s=0;for(i=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;11.下面程序段的時(shí)間復(fù)雜度是__________________。11.O(logn)i=1;while(i<=n)i=i*3;12.衡量算法正確性的標(biāo)準(zhǔn)通常是__________________________。12.程序?qū)τ诰脑O(shè)計(jì)的典型合法數(shù)據(jù)輸入能得出符合要求的結(jié)果。13.算法時(shí)間復(fù)雜度的分析通常有兩種方法，即___________和___________的方法，通常我們對算法求時(shí)間復(fù)雜度時(shí)，采用后一種方法。13.事后統(tǒng)計(jì)，事前估計(jì)三、求下列程序段的時(shí)間復(fù)雜度。1.x=0;for(i=1;i<n;i++)for(j=i+1;j<=n;j++)x++;1.O()2.x=0;for(i=1;i<n;i++)for(j=1;j<=n-i;j++)x++;2.O()3.inti,j,k;for(i=0;i<n;i++)for(j=0;j<=n;j++){c[i][j]=0;for(k=0;k<n;k++) c[i][j]=a[i][k]*b[k][j]}3.O(n)4.i=n-1;while((i>=0)&&A[i]!=k))j--;return(i);4.O(n)5.fact(n){if(n<=1)return(1);elsereturn(n*fact(n-1));}5.O(n)第2章線性表【例2-1】試編寫出將兩個(gè)順序存儲的有序表A和B合成一個(gè)有序表C的算法。解：假設(shè)A、B和C的類型為下述SqList類型：#definemaxlen1000typedefintelemtypetypedefstruct{elemtypeelem[maxlen];intlen;}SqList;設(shè)A和B的數(shù)據(jù)元素均為整數(shù)且為升序排列，設(shè)A的長度為m，B的長度為n，則合并后C的長度為m+n。合并時(shí)進(jìn)行A、B元素的比較，將較小的鏈入C中，算法描述如下：intmerge(SqList*A,SqList*B,SqList*C)//將兩個(gè)有序表A和B合成一個(gè)有序表C{intm,n,i,j,k;m=(*A).len;n=(*B).len;if(m+n>maxlen-1){printf("overflow");exit(0);}i=0;j=0;//i和j分別作為掃描順序表A和B的指針k=0;//k指示順序表C中當(dāng)前位置while((i<=m)&&(j<=n))if((*A).elem[i]<＝(*B).elem[j]){(*C).elem[k]＝(*A)elem[i];i++;k++;}else{(*C).elem[k]＝(*B)elem[j];j++;k++;}while(i<=m)//表B已結(jié)束，表A沒有結(jié)束，鏈入表A的剩余部分{(*C).elem[k]＝(*A).elem[i];i++;k++;}while(j<=m)//表A已結(jié)束，表B沒有結(jié)束，鏈入表B的剩余部分{(*C).elem[k]＝(*B).elem[j];i++;k++;}return(1);}【例2-2】寫一算法實(shí)現(xiàn)單鏈表的逆置。解：假設(shè)單鏈表的表頭指針用head表示，其類型為下面定義的LinkList，并且單鏈表不帶頭結(jié)點(diǎn)。逆置后原來的最后一個(gè)結(jié)點(diǎn)成為第一個(gè)結(jié)點(diǎn)，于是從第一個(gè)結(jié)點(diǎn)開始逐個(gè)修改每個(gè)結(jié)點(diǎn)的指針域進(jìn)行逆置，且剛被逆置的結(jié)點(diǎn)總是新鏈表的第一個(gè)結(jié)點(diǎn)，故令head指向它（如圖2-1所示）。typedefstructNode{elemtypedata;structNode*next;}LinkList;具體算法描述如下：圖圖2-1單鏈表逆置示意圖示示圖head∧…h(huán)ead∧qphead…q(a)單鏈表初始狀態(tài)示示圖(b)第三個(gè)結(jié)點(diǎn)逆置示示圖voidcontray(LinkList*head){//將head單鏈表中所有結(jié)點(diǎn)按相反次序鏈接LinkList*p,*q;p=head;//p指向未被逆序的第一個(gè)結(jié)點(diǎn),初始時(shí)指向原表頭結(jié)點(diǎn)head=NULL;while(p!=NULL){q=p;//q指向?qū)⒈荒嫘蜴溄拥慕Y(jié)點(diǎn)p=p->next;q->next=head;head=q;}}習(xí)題2一、單項(xiàng)選擇題1.線性表是________。1．AA．一個(gè)有限序列，可以為空 B．一個(gè)有限序列，不可以為空C．一個(gè)無限序列，可以為空 D．一個(gè)無限序列，不可以為空2.在一個(gè)長度為n的順序表中刪除第i個(gè)元素(0<=i<=n)時(shí)，需向前移動個(gè)元素。2．AA．n-i B．n-i+l C．n-i-1 D．i3.線性表采用鏈?zhǔn)酱鎯r(shí)，其地址________。3．DA．必須是連續(xù)的 B．一定是不連續(xù)的C．部分地址必須是連續(xù)的 D．連續(xù)與否均可以4.從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x的結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較________個(gè)元素結(jié)點(diǎn)。4．CA．n/2 B．n C．（n+1）/2 D．（n-1）/25.在雙向循環(huán)鏈表中，在p所指的結(jié)點(diǎn)之后插入s指針?biāo)傅慕Y(jié)點(diǎn)，其操作是____。5．DA．p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;B．s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;C．p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;D．s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;6.設(shè)單鏈表中指針p指向結(jié)點(diǎn)m，若要刪除m之后的結(jié)點(diǎn)（若存在），則需修改指針的操作為________。6．AA．p->next=p->next->next; B．p=p->next;C．p=p->next->next; D．p->next=p;7.在一個(gè)長度為n的順序表中向第i個(gè)元素(0<i<n+l)之前插入一個(gè)新元素時(shí)，需向后移動______個(gè)元素。7．BA．n-i B．n-i+l C．n-i-1 D．i8.在一個(gè)單鏈表中，已知q結(jié)點(diǎn)是p結(jié)點(diǎn)的前趨結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則須執(zhí)行8．BA．s->next=p->next;p->next=sB．q->next=s;s->next=pC．p->next=s->next;s->next=pD．p->next=s;s->next=q9.以下關(guān)于線性表的說法不正確的是______。9．C

A．線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型。B．線性表中包含的數(shù)據(jù)元素個(gè)數(shù)不是任意的。C．線性表中的每個(gè)結(jié)點(diǎn)都有且只有一個(gè)直接前趨和直接后繼。D．存在這樣的線性表：表中各結(jié)點(diǎn)都沒有直接前趨和直接后繼。10.線性表的順序存儲結(jié)構(gòu)是一種_______的存儲結(jié)構(gòu)。

10．AA．隨機(jī)存取 B．順序存取 C．索引存取 D．散列存取11.在順序表中，只要知道_______，就可在相同時(shí)間內(nèi)求出任一結(jié)點(diǎn)的存儲地址。11．DA．基地址 B．結(jié)點(diǎn)大小C．向量大小 D．基地址和結(jié)點(diǎn)大小12.在等概率情況下，順序表的插入操作要移動______結(jié)點(diǎn)。

12．BA．全部 B．一半

C．三分之一

D．四分之一13.在______運(yùn)算中，使用順序表比鏈表好。

13．CA．插入

B．刪除

C．根據(jù)序號查找

D．根據(jù)元素值查找14.在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并保持該表有序的時(shí)間復(fù)雜度是_______。

14．BA．O(1)

B．O(n)

C．O(n2) D．O(log2n)15.設(shè)有一個(gè)棧，元素的進(jìn)棧次序?yàn)锳,B,C,D,E,下列是不可能的出棧序列__________。15．CA．A,B,C,D,E B．B,C,D,E,AC．E,A,B,C,D D．E,D,C,B,A16.在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當(dāng)做出棧處理時(shí)，top變化為______。16．CA．top不變 B．top=0 C．top-- D．top++17.向一個(gè)棧頂指針為hs的鏈棧中插入一個(gè)s結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行______。17．BA．hs->next=s;B．s->next=hs;hs=s;C．s->next=hs->next;hs->next=s;D．s->next=hs;hs=hs->next;18.在具有n個(gè)單元的順序存儲的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)滿的條件為________。18．DA．rear％n==front B．（front+l）％n==rearC．rear％n-1==frontD．(rear+l)％n==front19.在具有n個(gè)單元的順序存儲的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)空的條件為________。19．C A．rear％n==front B．front+l=rearC．rear==front D．(rear+l)％n=front20.在一個(gè)鏈隊(duì)列中，假定front和rear分別為隊(duì)首和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的操作為________。20．AA．front=front->nextB．rear=rear->nextC．rear=front->nextD．front=rear->next二、填空題1.線性表是一種典型的_________結(jié)構(gòu)。1．線性2.在一個(gè)長度為n的順序表的第i個(gè)元素之前插入一個(gè)元素，需要后移____個(gè)元素。2．n-i+13.順序表中邏輯上相鄰的元素的物理位置________。3．相鄰4.要從一個(gè)順序表刪除一個(gè)元素時(shí)，被刪除元素之后的所有元素均需_______一個(gè)位置，移動過程是從_______向_______依次移動每一個(gè)元素。4．前移，前，后5.在線性表的順序存儲中，元素之間的邏輯關(guān)系是通過_______決定的；在線性表的鏈接存儲中，元素之間的邏輯關(guān)系是通過_______決定的。5．物理存儲位置，鏈域的指針值6.在雙向鏈表中，每個(gè)結(jié)點(diǎn)含有兩個(gè)指針域，一個(gè)指向_______結(jié)點(diǎn)，另一個(gè)指向_______結(jié)點(diǎn)。6．前趨，后繼7.當(dāng)對一個(gè)線性表經(jīng)常進(jìn)行存取操作，而很少進(jìn)行插入和刪除操作時(shí)，則采用_______存儲結(jié)構(gòu)為宜。相反，當(dāng)經(jīng)常進(jìn)行的是插入和刪除操作時(shí)，則采用_______存儲結(jié)構(gòu)為宜。7．順序，鏈接8.順序表中邏輯上相鄰的元素，物理位置_______相鄰，單鏈表中邏輯上相鄰的元素，物理位置_______相鄰。8．一定，不一定9.線性表、棧和隊(duì)列都是_______結(jié)構(gòu)，可以在線性表的______位置插入和刪除元素；對于棧只能在_______位置插入和刪除元素；對于隊(duì)列只能在_______位置插入元素和在_______位置刪除元素。9．線性，任何，棧頂，隊(duì)尾，隊(duì)頭10.根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每個(gè)結(jié)點(diǎn)所含指針的個(gè)數(shù)，鏈表可分為_________和_______；而根據(jù)指針的聯(lián)接方式，鏈表又可分為________和_________10．單鏈表，雙鏈表，非循環(huán)鏈表，循環(huán)鏈表11.在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是________。11．使空表和非空表統(tǒng)一；算法處理一致12.對于一個(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ù)雜度為_______。12．O(1)，O(n)13.對于一個(gè)棧作進(jìn)棧運(yùn)算時(shí)，應(yīng)先判別棧是否為_______，作退棧運(yùn)算時(shí)，應(yīng)先判別棧是否為_______，當(dāng)棧中元素為m時(shí)，作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說明棧的可用最大容量為_______。為了增加內(nèi)存空間的利用率和減少發(fā)生上溢的可能性，由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí)，應(yīng)將兩棧的_______分別設(shè)在這片內(nèi)存空間的兩端，這樣只有當(dāng)_______時(shí)才產(chǎn)生上溢。13．棧滿，?？?，m，棧底，兩個(gè)棧的棧頂在?？臻g的某一位置相遇14.設(shè)有一空棧，現(xiàn)有輸入序列1，2，3，4，5，經(jīng)過push,push,pop,push,pop,push,push后，輸出序列是_________。14．2、315.無論對于順序存儲還是鏈?zhǔn)酱鎯Φ臈：完?duì)列來說，進(jìn)行插入或刪除運(yùn)算的時(shí)間復(fù)雜度均相同為__________。15．O(1)三、簡答題1.線性表的兩種存儲結(jié)構(gòu)各有哪些優(yōu)缺點(diǎn)？答：線性表具有兩種存儲結(jié)構(gòu)即順序存儲結(jié)構(gòu)和鏈接存儲結(jié)構(gòu)。線性表的順序存儲結(jié)構(gòu)可以直接存取數(shù)據(jù)元素，方便靈活、效率高，但插入、刪除操作時(shí)將會引起元素的大量移動，因而降低效率：而在鏈接存儲結(jié)構(gòu)中內(nèi)存采用動態(tài)分配，利用率高，但需增設(shè)指示結(jié)點(diǎn)之間關(guān)系的指針域，存取數(shù)據(jù)元素不如順序存儲方便，但結(jié)點(diǎn)的插入、刪除操作較簡單。2.對于線性表的兩種存儲結(jié)構(gòu)，如果有n個(gè)線性表同時(shí)并存，而且在處理過程中各表的長度會動態(tài)發(fā)生變化，線性表的總數(shù)也會自動改變，在此情況下，應(yīng)選用哪一種存儲結(jié)構(gòu)？為什么？答：應(yīng)選用鏈接存儲結(jié)構(gòu)，因?yàn)殒準(zhǔn)酱鎯Y(jié)構(gòu)是用一組任意的存儲單元依次存儲線性表中的各元素，這里存儲單元可以是連續(xù)的，也可以是不連續(xù)的：這種存儲結(jié)構(gòu)對于元素的刪除或插入運(yùn)算是不需要移動元素的，只需修改指針即可，所以很容易實(shí)現(xiàn)表的容量的擴(kuò)充。3.對于線性表的兩種存儲結(jié)構(gòu)，若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素，應(yīng)選用何種存儲結(jié)構(gòu)？試說明理由。答：應(yīng)選用順序存儲結(jié)構(gòu)，因?yàn)槊總€(gè)數(shù)據(jù)元素的存儲位置和線性表的起始位置相差一個(gè)和數(shù)據(jù)元素在線性表中的序號成正比的常數(shù)。因此，只要確定了其起始位置，線性表中的任一個(gè)數(shù)據(jù)元素都可隨機(jī)存取，因此，線性表的順序存儲結(jié)構(gòu)是一種隨機(jī)存取的存儲結(jié)構(gòu)，而鏈表則是一種順序存取的存儲結(jié)構(gòu)第3章串【例3-1】已知字符串：a=“anapple”，b=“otherhero”，c=“her”，求：（1）concat(substr(a,1,2),b)。（2）replace(a,substr(a,5,1),c)。（3）index(a,c)和index(b,c)。解：（1）返回值為“anotherhero”，其中substr(a,1,2)的返回值為“an”。（2）返回值為“anaherherle”，其中sub(a,5,1)的返回值為“p”。（3）返回值分別為0和3。習(xí)題3一、單項(xiàng)選擇題1.空串與空格字符組成的串的區(qū)別在于（1．B）。A.沒有區(qū)別 B.兩串的長度不相等C.兩串的長度相等 D.兩串包含的字符不相同2.一個(gè)子串在包含它的主串中的位置是指（2．D）。A.子串的最后那個(gè)字符在主串中的位置B.子串的最后那個(gè)字符在主串中首次出現(xiàn)的位置C.子串的第一個(gè)字符在主串中的位置D.子串的第一個(gè)字符在主串中首次出現(xiàn)的位置3.下面的說法中，只有（3．C ）是正確的。A.字符串的長度是指串中包含的字母的個(gè)數(shù)B.字符串的長度是指串中包含的不同字符的個(gè)數(shù)C.若T包含在S中，則T一定是S的一個(gè)子串D.一個(gè)字符串不能說是其自身的一個(gè)子串4.兩個(gè)字符串相等的條件是（4．D）。A.兩串的長度相等B.兩串包含的字符相同C.兩串的長度相等，并且兩串包含的字符相同D.兩串的長度相等，并且對應(yīng)位置上的字符相同5.若SUBSTR（S，i，k）表示求S中從第i個(gè)字符開始的連續(xù)k個(gè)字符組成的子串的操作，則對于S=“Beijing＆Nanjing”，SUBSTR（S，4，5）=（5．B ）。A.“ijing” B.“jing＆”C.“ingNa” D.“ing＆N”6.若INDEX（S，T）表示求T在S中的位置的操作，則對于S=“Beijing＆Nanjing”，T=“jing”，INDEX（S，T）=（6．C）。A.2B.3C7.若REPLACE（S，S1，S2）表示用字符串S2替換字符串S中的子串S1的操作，則對于S=“Beijing＆Nanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（7．D）。A.“Nanjing＆Shanghai” B.“Nanjing＆Nanjing”C.“ShanghaiNanjing” D.“Shanghai＆Nanjing”8.在長度為n的字符串S的第i個(gè)位置插入另外一個(gè)字符串，i的合法值應(yīng)該是（8．C ）。A.i＞0B.i≤nC.1≤i≤nD.1≤i≤n+1二、填空題2.兩個(gè)字符串相等的充要條件是_____________________和___________________。2.兩個(gè)串的長度相等，對應(yīng)位置的字符相等3.設(shè)字符串S1=“ABCDEF”，S2=“PQRS”，則運(yùn)算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值為___________________。3.“BCDEDE”4.串是指___________________。4.含n個(gè)字符的有限序列（n≥0）5.空串是指___________________，空格串是指___________________。5.不含任何字符的串，僅含空格字符的字符串第4章數(shù)組和廣義表【例4-1】二維數(shù)組A的每一個(gè)元素是由6個(gè)字符組成的串，其行下標(biāo)i=0，1，…，8，列下標(biāo)j=1，2，…，10。若A以行為主序存儲元素，A[8][5]的物理地址與當(dāng)A按列為主序存儲時(shí)的元素（）的物理地址相同。設(shè)每個(gè)字符占一個(gè)字節(jié)。A．A[8][5]B．A[3][10]C．A[5][8]D．A[0][9]解：二維數(shù)A是一個(gè)