數(shù)據(jù)結構習題及參考答案

1、習題1一、單項選擇題1. 數(shù)據(jù)結構是指（ ）。A.數(shù)據(jù)元素的組織形式B.數(shù)據(jù)類型C.數(shù)據(jù)存儲結構 D.數(shù)據(jù)定義2. 數(shù)據(jù)在計算機存儲器內(nèi)表示時，物理地址與邏輯地址不相同的，稱之為（ ）。A.存儲結構B.邏輯結構 C.鏈式存儲結構D.順序存儲結構3. 樹形結構是數(shù)據(jù)元素之間存在一種（ ）。A.一對一關系B.多對多關系 C.多對一關系D.一對多關系4. 設語句x+的時間是單位時間，則以下語句的時間復雜度為（ ）。for(i=1; i<=n; i+)for(j=i; j<=n; j+)x+;A.O(1)B.O()C.O(n)D.O()5. 算法分析的目的是（1），算法分析的兩個主要方面是

2、（2）。（1） A.找出數(shù)據(jù)結構的合理性 B.研究算法中的輸入和輸出關系C.分析算法的效率以求改進 D.分析算法的易懂性和文檔性（2） A.空間復雜度和時間復雜度 B.正確性和簡明性C.可讀性和文檔性 D.數(shù)據(jù)復雜性和程序復雜性6. 計算機算法指的是（1），它具備輸入，輸出和（2）等五個特性。（1） A.計算方法 B.排序方法C.解決問題的有限運算序列 D.調(diào)度方法（2） A.可行性，可移植性和可擴充性 B.可行性，確定性和有窮性C.確定性，有窮性和穩(wěn)定性 D.易讀性，穩(wěn)定性和安全性7. 數(shù)據(jù)在計算機內(nèi)有鏈式和順序兩種存儲方式，在存儲空間使用的靈活性上，鏈式存儲比順序存儲要（ ）。A.低 B.

3、高 C.相同D.不好說8. 數(shù)據(jù)結構作為一門獨立的課程出現(xiàn)是在（ ）年。A.1946B.1953C.1964D.19689. 數(shù)據(jù)結構只是研究數(shù)據(jù)的邏輯結構和物理結構，這種觀點（ ）。A.正確B.錯誤C.前半句對，后半句錯D.前半句錯，后半句對10. 計算機內(nèi)部數(shù)據(jù)處理的基本單位是（ ）。A.數(shù)據(jù) B.數(shù)據(jù)元素C.數(shù)據(jù)項D.數(shù)據(jù)庫二、填空題 1. 數(shù)據(jù)結構按邏輯結構可分為兩大類，分別是_和_。2. 數(shù)據(jù)的邏輯結構有四種基本形態(tài)，分別是_、_、_和_。3. 線性結構反映結點間的邏輯關系是_的，非線性結構反映結點間的邏輯關系是_的。4. 一個算法的效率可分為_效率和_效率。5. 在樹型結構中，樹根

4、結點沒有_結點，其余每個結點的有且只有_個前趨驅(qū)結點；葉子結點沒有_結點；其余每個結點的后續(xù)結點可以_。6. 在圖型結構中，每個結點的前趨結點數(shù)和后續(xù)結點數(shù)可以_。7. 線性結構中元素之間存在_關系；樹型結構中元素之間存在_關系；圖型結構中元素之間存在_關系。8. 下面程序段的時間復雜度是_。for(i=0;i<n;i+)for(j=0;j<n;j+)Aij=0;9. 下面程序段的時間復雜度是_。i=s=0;while(s<n) i+; s+=i;10. 下面程序段的時間復雜度是_。s=0;for(i=0;i<n;i+)for(j=0;j<n;j+)s+=Bij;

5、sum=s;11. 下面程序段的時間復雜度是_。i=1;while(i<=n)i=i*3;12. 衡量算法正確性的標準通常是_。13. 算法時間復雜度的分析通常有兩種方法，即_和_的方法，通常我們對算法求時間復雜度時，采用后一種方法。三、求下列程序段的時間復雜度。1. x=0;for(i=1;i<n;i+)for(j=i+1;j<=n;j+)x+;2. x=0;for(i=1;i<n;i+)for(j=1;j<=n-i;j+) x+;3. int i,j,k;for(i=0;i<n;i+)for(j=0;j<=n;j+) cij=0;for(k=0;k

6、<n;k+) cij=aik*bkj4. i=n-1;while(i>=0)&&Ai!=k)j-;return (i);5. fact(n) if(n<=1) return (1); else return (n*fact(n-1);習題1參考答案一、單項選擇題1. A 2. C 3. D 4. B 5. C、A 6. C、B 7. B 8. D 9. B 10. B二、填空題1. 線性結構，非線性結構2. 集合，線性，樹，圖3. 一對一，一對多或多對多4. 時間，空間5. 前趨，一，后繼，多6. 有多個7. 一對一，一對多，多對多8. O()9. O()10

7、. O()11. O(logn)12. 程序?qū)τ诰脑O計的典型合法數(shù)據(jù)輸入能得出符合要求的結果。13. 事后統(tǒng)計，事前估計三、算法設計題1. O() 2. O() 3. O(n) 4. O(n) 5. O(n)習題2一、單項選擇題 1. 線性表是_。A一個有限序列，可以為空B一個有限序列，不可以為空C一個無限序列，可以為空D一個無限序列，不可以為空2. 在一個長度為n的順序表中刪除第i個元素(0<=i<=n)時，需向前移動 個元素。An-iBn-i+lCn-i-1Di3. 線性表采用鏈式存儲時，其地址_。A必須是連續(xù)的B一定是不連續(xù)的C部分地址必須是連續(xù)的D連續(xù)與否均可以 4. 從

8、一個具有n個結點的單鏈表中查找其值等于x的結點時，在查找成功的情況下，需平均比較_個元素結點。An/2 BnC（n+1）/2D（n-1）/2 5. 在雙向循環(huán)鏈表中，在p所指的結點之后插入s指針所指的結點，其操作是_。A 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=

9、s; s->prior=p; s->next=p->next;D s->prior=p; s->next=p->next; p->next->prior=s; p->next=s; 6. 設單鏈表中指針p指向結點m，若要刪除m之后的結點（若存在），則需修改指針的操作為_。Ap->next=p->next->next;Bp=p->next;Cp=p->next->next; Dp->next=p; 7. 在一個長度為n的順序表中向第i個元素(0< i<n+l )之前插入一個新元素時，需向后

10、移動_個元素。An-i Bn-i+lCn-i-1Di8. 在一個單鏈表中，已知q結點是p結點的前趨結點，若在q和p之間插入s結點，則須執(zhí)行As->next=p->next; p->next=sBq->next=s; s->next=pCp->next=s->next; s->next=pDp->next=s; s->next=q9. 以下關于線性表的說法不正確的是_。  A線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型。B線性表中包含的數(shù)據(jù)元素個數(shù)不是任意的。C線性表中的每個結點都有且只有一個直接前趨和直接后繼。D存在這

11、樣的線性表：表中各結點都沒有直接前趨和直接后繼。10. 線性表的順序存儲結構是一種_的存儲結構。  A隨機存取B順序存取C索引存取D散列存取11. 在順序表中，只要知道_，就可在相同時間內(nèi)求出任一結點的存儲地址。A基地址B結點大小 C向量大小 D基地址和結點大小12. 在等概率情況下，順序表的插入操作要移動_結點。  A全部 B一半  C三分之一   D四分之一13. 在_運算中，使用順序表比鏈表好。  A插入   B刪除  C根據(jù)序號查找   D根據(jù)元素值查找14. 在一個具有n個結點的有序單鏈表中插入一個新結點

12、并保持該表有序的時間復雜度是_。  AO(1)   BO(n)  CO(n2) DO(log2n)15. 設有一個棧，元素的進棧次序為A, B, C, D, E,下列是不可能的出棧序列_。AA, B, C, D, E BB, C, D, E, ACE, A, B, C, D DE, D, C, B, A 16. 在一個具有n個單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當做出棧處理時，top變化為_。Atop不變 Btop=0 Ctop- Dtop+17. 向一個棧頂指針為hs的鏈棧中插入一個s結點時，應執(zhí)行_。Ahs->nex

13、t=s; Bs->next=hs; hs=s;Cs->next=hs->next;hs->next=s; Ds->next=hs; hs=hs->next; 18. 在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊頭指針和隊尾指針，則判斷隊滿的條件為_。Arearn= = front B（front+l）n= = rearCrearn -1= = front D(rear+l)n= = front 19. 在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊頭指針和隊尾指針，則判斷隊空的條件為_。Arearn= = f

14、ront Bfront+l= rearCrear= = front D(rear+l)n= front20. 在一個鏈隊列中，假定front和rear分別為隊首和隊尾指針，則刪除一個結點的操作為_。Afront=front->next Brear=rear->nextCrear=front->next Dfront=rear->next二、填空題 1. 線性表是一種典型的_結構。2. 在一個長度為n的順序表的第i個元素之前插入一個元素，需要后移_個元素。3. 順序表中邏輯上相鄰的元素的物理位置_。4. 要從一個順序表刪除一個元素時，被刪除元素之后的所有元素均需_一個位置

15、，移動過程是從_向_依次移動每一個元素。5. 在線性表的順序存儲中，元素之間的邏輯關系是通過_決定的；在線性表的鏈接存儲中，元素之間的邏輯關系是通過_決定的。6. 在雙向鏈表中，每個結點含有兩個指針域，一個指向_結點，另一個指向_結點。7. 當對一個線性表經(jīng)常進行存取操作，而很少進行插入和刪除操作時，則采用_存儲結構為宜。相反，當經(jīng)常進行的是插入和刪除操作時，則采用_存儲結構為宜。8. 順序表中邏輯上相鄰的元素，物理位置_相鄰，單鏈表中邏輯上相鄰的元素，物理位置_相鄰。9. 線性表、棧和隊列都是_結構，可以在線性表的_位置插入和刪除元素；對于棧只能在_位置插入和刪除元素；對于隊列只能在_位置插

16、入元素和在_位置刪除元素。10. 根據(jù)線性表的鏈式存儲結構中每個結點所含指針的個數(shù)，鏈表可分為_和_；而根據(jù)指針的聯(lián)接方式，鏈表又可分為_和_。11. 在單鏈表中設置頭結點的作用是_。12. 對于一個具有n個結點的單鏈表，在已知的結點p后插入一個新結點的時間復雜度為_，在給定值為x的結點后插入一個新結點的時間復雜度為_。 13. 對于一個棧作進棧運算時，應先判別棧是否為_，作退棧運算時，應先判別棧是否為_，當棧中元素為m時，作進棧運算時發(fā)生上溢，則說明棧的可用最大容量為_。為了增加內(nèi)存空間的利用率和減少發(fā)生上溢的可能性，由兩個棧共享一片連續(xù)的內(nèi)存空間時，應將兩棧的_分別設在這片內(nèi)存空間的兩端，

17、這樣只有當_時才產(chǎn)生上溢。14. 設有一空棧，現(xiàn)有輸入序列1，2，3，4，5，經(jīng)過push, push, pop, push, pop, push, push后，輸出序列是_。15. 無論對于順序存儲還是鏈式存儲的棧和隊列來說，進行插入或刪除運算的時間復雜度均相同為_。三、簡答題 1. 描述以下三個概念的區(qū)別：頭指針，頭結點，表頭結點。2. 線性表的兩種存儲結構各有哪些優(yōu)缺點？3. 對于線性表的兩種存儲結構，如果有n個線性表同時并存，而且在處理過程中各表的長度會動態(tài)發(fā)生變化，線性表的總數(shù)也會自動改變，在此情況下，應選用哪一種存儲結構？為什么？4. 對于線性表的兩種存儲結構，若線性表的總數(shù)基本穩(wěn)

18、定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素，應選用何種存儲結構？試說明理由。5. 在單循環(huán)鏈表中設置尾指針比設置頭指針好嗎？為什么?6. 假定有四個元素A, B, C, D依次進棧，進棧過程中允許出棧，試寫出所有可能的出棧序列。7. 什么是隊列的上溢現(xiàn)象？一般有幾種解決方法，試簡述之。8. 下述算法的功能是什么?LinkList *Demo(LinkList *L) / L是無頭結點的單鏈表LinkList *q,*p;if(L&&L->next) q=L; L=L->next; p=L;while (p->next) p=p->

19、next; p->next=q; q->next=NULL;return (L);四、算法設計題1. 設計在無頭結點的單鏈表中刪除第i個結點的算法。2. 在單鏈表上實現(xiàn)線性表的求表長ListLength(L)運算。3. 設計將帶表頭的鏈表逆置算法。4. 假設有一個帶表頭結點的鏈表，表頭指針為head，每個結點含三個域：data, next和prior。其中data為整型數(shù)域，next和prior均為指針域。現(xiàn)在所有結點已經(jīng)由next域連接起來，試編一個算法，利用prior域（此域初值為NULL）把所有結點按照其值從小到大的順序鏈接起來。5. 已知線性表的元素按遞增順序排列，并以帶頭

20、結點的單鏈表作存儲結構。試編寫一個刪除表中所有值大于min且小于max的元素（若表中存在這樣的元素）的算法。6. 已知線性表的元素是無序的，且以帶頭結點的單鏈表作為存儲結構。設計一個刪除表中所有值小于max但大于min的元素的算法。7. 假定用一個單循環(huán)鏈表來表示隊列（也稱為循環(huán)隊列），該隊列只設一個隊尾指針，不設隊首指針，試編寫下列各種運算的算法：（1）向循環(huán)鏈隊列插入一個元素值為x的結點；（2）從循環(huán)鏈隊列中刪除一個結點。8. 設順序表L是一個遞減有序表，試寫一算法，將x插入其后仍保持L的有序性。習題2參考答案一、單項選擇題1A 2A 3D 4C 5D 6A 7B 8B 9C 10A 11

21、D 12B 13C 14B 15C 16C 17B 18D 19C20A二、填空題1線性 2n-i+1 3相鄰 4前移，前，后5物理存儲位置，鏈域的指針值 6前趨，后繼7順序，鏈接 8一定，不一定9線性，任何，棧頂，隊尾，隊頭10單鏈表，雙鏈表，非循環(huán)鏈表，循環(huán)鏈表11使空表和非空表統(tǒng)一；算法處理一致12O(1)，O(n)13棧滿，?？?，m，棧底，兩個棧的棧頂在?？臻g的某一位置相遇142、315O(1)三、簡答題1頭指針是指向鏈表中第一個結點（即表頭結點）的指針；在表頭結點之前附設的結點稱為頭結點；表頭結點為鏈表中存儲線性表中第一個數(shù)據(jù)元素的結點。若鏈表中附設頭結點，則不管線性表是否為空表，頭

22、指針均不為空，否則表示空表的鏈表的頭指針為空。2線性表具有兩種存儲結構即順序存儲結構和鏈接存儲結構。線性表的順序存儲結構可以直接存取數(shù)據(jù)元素，方便靈活、效率高，但插入、刪除操作時將會引起元素的大量移動，因而降低效率：而在鏈接存儲結構中內(nèi)存采用動態(tài)分配，利用率高，但需增設指示結點之間關系的指針域，存取數(shù)據(jù)元素不如順序存儲方便，但結點的插入、刪除操作較簡單。3應選用鏈接存儲結構，因為鏈式存儲結構是用一組任意的存儲單元依次存儲線性表中的各元素，這里存儲單元可以是連續(xù)的，也可以是不連續(xù)的：這種存儲結構對于元素的刪除或插入運算是不需要移動元素的，只需修改指針即可，所以很容易實現(xiàn)表的容量的擴充。4應選用順

23、序存儲結構，因為每個數(shù)據(jù)元素的存儲位置和線性表的起始位置相差一個和數(shù)據(jù)元素在線性表中的序號成正比的常數(shù)。因此，只要確定了其起始位置，線性表中的任一個數(shù)據(jù)元素都可隨機存取，因此，線性表的順序存儲結構是一種隨機存取的存儲結構，而鏈表則是一種順序存取的存儲結構。5設尾指針比設頭指針好。尾指針是指向終端結點的指針，用它來表示單循環(huán)鏈表可以使得查找鏈表的開始結點和終端結點都很方便，設一帶頭結點的單循環(huán)鏈表，其尾指針為rear，則開始結點和終端結點的位置分別是rear->next->next 和 rear, 查找時間都是O(1)。若用頭指針來表示該鏈表，則查找終端結點的時間為O(n)。6共有1

24、4種可能的出棧序列，即為：ABCD, ABDC，ACBD, ACDB，BACD，ADCB，BADC，BCAD, BCDA，BDCA,CBAD, CBDA，CDBA, DCBA7在隊列的順序存儲結構中，設隊頭指針為front，隊尾指針為rear，隊列的容量（即存儲的空間大小）為maxnum。當有元素要加入隊列（即入隊）時，若rear=maxnum，則會發(fā)生隊列的上溢現(xiàn)象，此時就不能將該元素加入隊列。對于隊列，還有一種“假溢出”現(xiàn)象，隊列中尚余有足夠的空間，但元素卻不能入隊，一般是由于隊列的存儲結構或操作方式的選擇不當所致，可以用循環(huán)隊列解決。 一般地，要解決隊列的上溢現(xiàn)象可有以下幾種方法：（1）

25、可建立一個足夠大的存儲空間以避免溢出，但這樣做往往會造成空間使用率低，浪費存儲空間。（2）要避免出現(xiàn)“假溢出”現(xiàn)象可用以下方法解決： 第一種：采用移動元素的方法。每當有一個新元素入隊，就將隊列中已有的元素向隊頭移動一個位置，假定空余空間足夠。 第二種：每當刪去一個隊頭元素，則可依次移動隊列中的元素總是使front指針指向隊列中的第一個位置。 第三種：采用循環(huán)隊列方式。將隊頭、隊尾看作是一個首尾相接的循環(huán)隊列，即用循環(huán)數(shù)組實現(xiàn)，此時隊首仍在隊尾之前，作插入和刪除運算時仍遵循“先進先出”的原則。8該算法的功能是：將開始結點摘下鏈接到終端結點之后成為新的終端結點，而原來的第二個結點成為新的開始結點，

26、返回新鏈表的頭指針。四、算法設計題 1算法思想為：（1）應判斷刪除位置的合法性，當i<0或i>n-1時，不允許進行刪除操作；（2）當i=0時，刪除第一個結點：（3）當<i<n時，允許進行刪除操作，但在查找被刪除結點時，須用指針記住該結點的前趨結點。算法描述如下：delete(LinkList *q,int i) /在無頭結點的單鏈表中刪除第i個結點 LinkList *p,*s; int j; if(i<0) printf("Can't delete"); else if(i= =0) s=q; q=q->next; free(s

27、); else j=0; s=q; while(j<i) && (s! = NULL) p=s; s=s->next;j+;if (s= =NULL) printf("Cant't delete"); else p->next=s->next; free(s); 2由于在單鏈表中只給出一個頭指針，所以只能用遍歷的方法來數(shù)單鏈表中的結點個數(shù)了。算法描述如下：int ListLength ( LinkList *L ) /求帶頭結點的單鏈表的表長 int len=0; ListList *p; p=L; while ( p->

28、;next!=NULL ) p=p->next;len+; return (len);3設單循環(huán)鏈表的頭指針為head，類型為LinkList。逆置時需將每一個結點的指針域作以修改，使其原前趨結點成為后繼。如要更改q結點的指針域時，設s指向其原前趨結點，p指向其原后繼結點，則只需進行q->next=s;操作即可，算法描述如下：void invert(LinkList *head) /逆置head指針所指向的單循環(huán)鏈表linklist *p, *q, *s; q=head; p=head->next; while (p!=head) /當表不為空時，逐個結點逆置 s=q; q=

29、p; p=p->next; q->next=s; p->next=q; 4定義類型LinkList如下：typedef struct node int data; struct node *next,*prior;LinkList;此題可采用插入排序的方法，設p指向待插入的結點，用q搜索已由prior域鏈接的有序表找到合適位置將p結點鏈入。算法描述如下：insert (LinkList *head) LinkList *p,*s,*q; p=head->next; /p指向待插入的結點，初始時指向第一個結點 while(p!=NULL) s=head; / s指向q結點

30、的前趨結點 q=head->prior; /q指向由prior域構成的鏈表中待比較的結點 while(q!=NULL) && (p->data>q->data) /查找插入結點p的合適的插入位置 s=q; q=q->prior; s->prior=p; p->prior=q; /結點p插入到結點s和結點q之間 p=p->next;5算法描述如下：delete(LinkList *head, int max, int min) linklist *p, *q; if (head!=NULL) q=head; p=head->n

31、ext; while(p!=NULL) && (p->data<=min) q=p;p=p->next;while(p!=NULL) && (p->data<max) p=p->next; q->next=p;6算法描述如下：delete(LinkList *head, int max, int min) LinkList *p,*q; q=head; p=head->next; while (p!=NULL) if(p->data<=min) | (p->data>=max) q=p; p

32、=p->next; else q->next=p->next;free(p);p=q->next; 7本題是對一個循環(huán)鏈隊列做插入和刪除運算，假設不需要保留被刪結點的值和不需要回收結點，算法描述如下：（1）插入（即入隊）算法：insert(LinkList *rear, elemtype x) /設循環(huán)鏈隊列的隊尾指針為rear,x為待插入的元素 LinkList *p;p=(LinkList *)malloc(sizeof(LinkList);if(rear= =NULL) /如為空隊，建立循環(huán)鏈隊列的第一個結點 rear=p;rear->next=p; /鏈接

33、成循環(huán)鏈表else /否則在隊尾插入p結點 p->next=rear->next;rear->next=p; rear=p;（2）刪除（即出隊）算法：delete(LinkList *rear) /設循環(huán)鏈隊列的隊尾指針為rearif (rear= =NULL) /空隊 printf("underflown"); if(rear->next= =rear) /隊中只有一個結點rear=NULL;elserear->next=rear->next->next; /rear->next指向的結點為循環(huán)鏈隊列的隊頭結點8只要從終端結

34、點開始往前找到第一個比x大(或相等)的結點數(shù)據(jù)，在這個位置插入就可以了。算法描述如下：int InsertDecreaseList( SqList *L, elemtype x ) int i;if ( (*L).len>= maxlen) printf(“overflow");return(0);for ( i=(*L).len ; i>0 && (*L).elem i-1 < x ; i-) (*L).elem i =(*L).elem i-1 ; / 比較并移動元素 (*L).elem i =x; (*L).len+;return(1);習題3

35、一、單項選擇題1. 空串與空格字符組成的串的區(qū)別在于（ ）。A.沒有區(qū)別 B.兩串的長度不相等C.兩串的長度相等D.兩串包含的字符不相同2. 一個子串在包含它的主串中的位置是指（ ）。A.子串的最后那個字符在主串中的位置B.子串的最后那個字符在主串中首次出現(xiàn)的位置C.子串的第一個字符在主串中的位置D.子串的第一個字符在主串中首次出現(xiàn)的位置3. 下面的說法中，只有（ ）是正確的。A.字符串的長度是指串中包含的字母的個數(shù)B.字符串的長度是指串中包含的不同字符的個數(shù)C.若T包含在S中，則T一定是S的一個子串D.一個字符串不能說是其自身的一個子串4. 兩個字符串相等的條件是（ ）。A.兩串的長度相等

36、B.兩串包含的字符相同C.兩串的長度相等，并且兩串包含的字符相同D.兩串的長度相等，并且對應位置上的字符相同5. 若SUBSTR（S，i，k）表示求S中從第i個字符開始的連續(xù)k個字符組成的子串的操作，則對于S=“BeijingNanjing”，SUBSTR（S，4，5）=（ ）。A. “ijing”B. “jing” C. “ingNa”D. “ingN”6. 若INDEX（S，T）表示求T在S中的位置的操作，則對于S=“BeijingNanjing”，T=“jing”，INDEX（S，T）=（ ）。A.2 B.3 C.4 D.57. 若REPLACE（S，S1，S2）表示用字符串S2替換字符

37、串S中的子串S1的操作，則對于S=“BeijingNanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（ ）。A. “NanjingShanghai” B. “NanjingNanjing”C. “ShanghaiNanjing” D. “ShanghaiNanjing”8. 在長度為n的字符串S的第i個位置插入另外一個字符串，i的合法值應該是（ ）。A.i0 B. in C.1in D.1in+19. 字符串采用結點大小為1的鏈表作為其存儲結構，是指（ ）。A.鏈表的長度為1B.鏈表中只存放1個字符C.鏈表的每個鏈結點的數(shù)據(jù)域中不僅只存放

38、了一個字符D.鏈表的每個鏈結點的數(shù)據(jù)域中只存放了一個字符二、填空題1. 計算機軟件系統(tǒng)中，有兩種處理字符串長度的方法：一種是_，第二種是_。2. 兩個字符串相等的充要條件是_和_。3. 設字符串S1= “ABCDEF”，S2= “PQRS”，則運算S=CONCAT（SUB（S1，2，LEN（S2），SUB（S1，LEN（S2），2）后的串值為_。4. 串是指_。5. 空串是指_，空格串是指_。三、算法設計題1. 設有一個長度為s的字符串，其字符順序存放在一個一維數(shù)組的第1至第s個單元中（每個單元存放一個字符）。現(xiàn)要求從此串的第m個字符以后刪除長度為t的子串，m<s，t<(s-m)，

39、并將刪除后的結果復制在該數(shù)組的第s單元以后的單元中，試設計此刪除算法。2. 設s和t是表示成單鏈表的兩個串，試編寫一個找出s中第1個不在t中出現(xiàn)的字符（假定每個結點只存放1個字符）的算法。習題3參考答案一、單項選擇題1B2D3C4D5B6C7D8C9D二、填空題1. 固定長度，設置長度指針2. 兩個串的長度相等，對應位置的字符相等3. “BCDEDE”4. 含n個字符的有限序列 （n0）5. 不含任何字符的串，僅含空格字符的字符串三、算法設計題1算法描述為：int delete(r,s,t,m) /從串的第m個字符以后刪除長度為t的子串char r ;int s,t,m; int i,j; f

40、or(i=1;i<=m;i+)rs+i=ri; for(j=m+t-i;j<=s;j+)rs-t+j=rj;return (1); /delete2算法思想為：（1）鏈表s中取出一個字符；將該字符與單鏈表t中的字符依次比較；（2）當t中有與從s中取出的這個字符相等的字符，則從t中取下一個字符重復以上比較；（3）當t中沒有與從s中取出的這個字符相等的字符，則算法結束。設單鏈表類型為LinkList；注意，此時類型 LinkList中的data成分為字符類型。LinkString find(s,t)LinkString *s, *t; LinkString *ps, *pt; ps=s

41、;while(ps!=NULL) pt=t; while(pt!=NULL)&&(ps->data!=pt->data) pt=pt->next; if(pt= =NULL) ps=NULL; else ps=ps->next;s=ps; return s; /find習題4一、單項選擇題1. 設二維數(shù)組A0m-10n-1按行優(yōu)先順序存儲在內(nèi)存中，第一個元素的地址為p，每個元素占k個字節(jié)，則元素aij的地址為（ ）。A.p +i*n+j-1*kB.p+(i-1)*n+j-1*kC.p+(j-1)*n+i-1*kD.p+j*n+i-1*k2. 已知二維數(shù)組

42、A10×10中，元素a20的地址為560，每個元素占4個字節(jié)，則元素a10的地址為（ ）。A.520B.522C.524D.5183. 若數(shù)組A0m0n按列優(yōu)先順序存儲，則aij地址為（ ）。A.LOC(a00)+j*m+i B. LOC(a00)+j*n+iC.LOC(a00)+(j-1)*n+i-1 D. LOC(a00)+(j-1)*m+i-14. 若下三角矩陣An×n，按列順序壓縮存儲在數(shù)組Sa0(n+1)n/2中，則非零元素aij的地址為（ ）。（設每個元素占d個字節(jié)）A. (j-1)*n-+i-1*dB. (j-1)*n-+i*dC(j-1)*n-+i+1*dD

43、(j-1)*n-+i-2*d5. 設有廣義表D=(a,b,D)，其長度為（ ），深度為（ ）。A.無窮大 B.3C.2 D.56. 廣義表A=（a），則表尾為（ ）。A.a B.( )C.空表 D.(a)7. 廣義表A=(x,(a,B),(x,(a,B),y)，則運算head(head(tail(A)的結果為（ ）。A.x B.(a,B) C.(x,(a,B) D.A8. 下列廣義表用圖來表示時，分支結點最多的是（ ）。A.L=(x,(a,B),(x,(a,B),y)B.A=(s,(a,B)C.B=(x,(a,B),y)D.D=(a,B),(c,(a,B),D)9. 通常對數(shù)組進行的兩種基本操

44、作是（ ）。A.建立與刪除B.索引和修改 C.查找和修改 D.查找與索引10. 假定在數(shù)組A中，每個元素的長度為3個字節(jié)，行下標i從1到8，列下標j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，存放該數(shù)組至少需要的單元數(shù)為（ ）。A.80B.100C.240D.27011. 數(shù)組A中，每個元素的長度為3個字節(jié)，行下標i從1到8，列下標j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，元素A85的起始地址為（ ）。A.SA+141B.SA+144C.SA+222D.SA+22512. 稀疏矩陣一般的壓縮存儲方法有兩種，即（ ）。A.二維數(shù)組和三維數(shù)組 B.三元組和散列C.三元

45、組和十字鏈表 D.散列和十字鏈表13. 若采用三元組壓縮技術存儲稀疏矩陣，只要把每個元素的行下標和列下標互換，就完成了對該矩陣的轉(zhuǎn)置運算，這種觀點（ ）。A.正確B.不正確14. 一個廣義表的表頭總是一個（ ）。A.廣義表B.元素C.空表D.元素或廣義表15. 一個廣義表的表尾總是一個（ ）。A.廣義表B.元素C.空表 D.元素或廣義表16. 數(shù)組就是矩陣，矩陣就是數(shù)組，這種說法（ ）。A.正確 B.錯誤 C.前句對，后句錯 D.后句對二、填空題1. 一維數(shù)組的邏輯結構是_，存儲結構是_；對于二維或多維數(shù)組，分為_和_兩種不同的存儲方式。2. 對于一個二維數(shù)組Amn，若按行序為主序存儲，則任一

46、元素Aij相對于A00的地址為_。3. 一個廣義表為(a,(a,b),d,e,(i,j),k)，則該廣義表的長度為_，深度為_。4. 一個稀疏矩陣為 ，則對應的三元組線性表為_。5. 一個n×n的對稱矩陣，如果以行為主序或以列為主序存入內(nèi)存，則其容量為_。6. 已知廣義表A=(a,b,c),(d,e,f)，則運算head(tail(tail(A)=_。7. 設有一個10階的對稱矩陣A，采用壓縮存儲方式以行序為主序存儲，a為第一個元素，其存儲地址為0，每個元素占有1個存儲地址空間，則a的地址為_。8. 已知廣義表Ls=(a,(b,c,d),e)，運用head和tail函數(shù)取出Ls中的原

47、子b的運算是_。9. 三維數(shù)組Rc1d1,c2d2,c3d3共含有_個元素。（其中：c1d1,c2d2,c3d3）10. 數(shù)組A110，-26，28以行優(yōu)先的順序存儲，設第一個元素的首地址是100，每個元素占3個存儲長度的存儲空間，則元素A5，0，7的存儲地址為_。三、判斷題1. 數(shù)組可看作基本線性表的一種推廣，因此與線性表一樣，可以對它進行插入、刪除等操作。（ ）2. 多維數(shù)組可以看作數(shù)據(jù)元素也是基本線性表的基本線性表。（ ）3. 以行為主序或以列為主序?qū)τ诙嗑S數(shù)組的存儲沒有影響。（ ）4. 對于不同的特殊矩陣應該采用不同的存儲方式。（ ）5. 采用壓縮存儲之后，下三角矩陣的存儲空間可以節(jié)約

48、一半。（ ）6. 在一般情況下，采用壓縮存儲之后，對稱矩陣是所有特殊矩陣中存儲空間節(jié)約最多的。（ ）7. 矩陣不僅是表示多維數(shù)組，而且是表示圖的重要工具。（ ）8. 距陣中的數(shù)據(jù)元素可以是不同的數(shù)據(jù)類型。（ ）9. 矩陣中的行列數(shù)往往是不相等的。（ ）10. 廣義表的表頭可以是廣義表，也可以是單個元素。（ ）11. 廣義表的表尾一定是一個廣義表。（ ）12. 廣義表的元素可以是子表，也可以是單元素。（ ）13. 廣義表不能遞歸定義。（ ）14. 廣義表實際上是基本線性表的推廣。（ ）15. 廣義表的組成元素可以是不同形式的元素。（ ）習題4參考答案一、單項選擇題1. A 2. A 3. A 4. B 5. BA 6. C 7. A 8. A 9. C 10. C 11. C 12. C 13. B 14. D 15.A 16.B 二、填空題1.