【正文】 “jing＆” C. “ingNa” D. “ing＆N”6. 若INDEX（S，T）表示求T在S中的位置的操作，則對于S=“Beijing＆Nanjing”，T=“jing”，INDEX（S，T）=（ ）。，則T一定是S的一個子串4. 兩個字符串相等的條件是（ ）。 2. 一個子串在包含它的主串中的位置是指（ ）。return(1)。 // 比較并移動元素 (*L).elem[ i ] =x。 (*L).elem[ i1 ] x 。 i0 amp。return(0)。算法描述如下：int InsertDecreaseList( SqList *L, elemtype x ){ int i。elserearnext=rearnextnext。}}（2）刪除（即出隊）算法：delete(LinkList *rear){ //設循環(huán)鏈隊列的隊尾指針為rearif (rear= =NULL) //空隊 printf(underflow\n)。rearnext=p。rearnext=p。p=(LinkList *)malloc(sizeof(LinkList))。p=qnext。 }else{ qnext=pnext。 while (p!=NULL) if((pdata=min) || (pdata=max)) { q=p。 q=head。 qnext=p。amp。p=pnext。amp。 p=headnext。}}5．算法描述如下：delete(LinkList *head, int max, int min){ linklist *p, *q。 pprior=q。 q=qprior。amp。 // s指向q結點的前趨結點 q=headprior。 p=headnext。此題可采用插入排序的方法，設p指向待插入的結點，用q搜索已由prior域鏈接的有序表找到合適位置將p結點鏈入。 struct node *next,*prior。 } pnext=q。 p=pnext。 while (p!=head) //當表不為空時，逐個結點逆置 { s=q。 q=head。如要更改q結點的指針域時，設s指向其原前趨結點，p指向其原后繼結點，則只需進行qnext=s。}3．設單循環(huán)鏈表的頭指針為head，類型為LinkList?！　　en++?！?p=L。算法描述如下：int ListLength ( LinkList *L ){ //求帶頭結點的單鏈表的表長　 int len=0。 free(s)。t delete)。j++。 (s! = NULL)) { p=s。 while((ji) amp。 }else { j=0。 q=qnext。t delete)。 int j。四、算法設計題 1．算法思想為：（1）應判斷刪除位置的合法性，當i0或in1時，不允許進行刪除操作；（2）當i=0時，刪除第一個結點：（3）當０in時，允許進行刪除操作，但在查找被刪除結點時，須用指針記住該結點的前趨結點。將隊頭、隊尾看作是一個首尾相接的循環(huán)隊列，即用循環(huán)數(shù)組實現(xiàn)，此時隊首仍在隊尾之前，作插入和刪除運算時仍遵循“先進先出”的原則。 第二種：每當刪去一個隊頭元素，則可依次移動隊列中的元素總是使front指針指向隊列中的第一個位置。（2）要避免出現(xiàn)“假溢出”現(xiàn)象可用以下方法解決： 第一種：采用移動元素的方法。對于隊列，還有一種“假溢出”現(xiàn)象，隊列中尚余有足夠的空間，但元素卻不能入隊，一般是由于隊列的存儲結構或操作方式的選擇不當所致，可以用循環(huán)隊列解決。6．共有14種可能的出棧序列，即為：ABCD, ABDC，ACBD, ACDB，BACD，ADCB，BADC，BCAD, BCDA，BDCA,CBAD, CBDA，CDBA, DCBA7．在隊列的順序存儲結構中，設隊頭指針為front，隊尾指針為rear，隊列的容量（即存儲的空間大小）為maxnum。尾指針是指向終端結點的指針，用它來表示單循環(huán)鏈表可以使得查找鏈表的開始結點和終端結點都很方便，設一帶頭結點的單循環(huán)鏈表，其尾指針為rear，則開始結點和終端結點的位置分別是rearnextnext 和 rear, 查找時間都是O(1)。因此，只要確定了其起始位置，線性表中的任一個數(shù)據(jù)元素都可隨機存取，因此，線性表的順序存儲結構是一種隨機存取的存儲結構，而鏈表則是一種順序存取的存儲結構。3．應選用鏈接存儲結構，因為鏈式存儲結構是用一組任意的存儲單元依次存儲線性表中的各元素，這里存儲單元可以是連續(xù)的，也可以是不連續(xù)的：這種存儲結構對于元素的刪除或插入運算是不需要移動元素的，只需修改指針即可，所以很容易實現(xiàn)表的容量的擴充。2．線性表具有兩種存儲結構即順序存儲結構和鏈接存儲結構。習題2參考答案一、單項選擇題1．A 2．A 3．D 4．C 5．D 6．A 7．B 8．B 9．C 10．A 11．D 12．B 13．C 14．B 15．C 16．C 17．B 18．D 19．C 20．A二、填空題1．線性 2．ni+1 3．相鄰 4．前移，前，后5．物理存儲位置，鏈域的指針值 6．前趨，后繼7．順序，鏈接 8．一定，不一定9．線性，任何，棧頂，隊尾，隊頭10．單鏈表，雙鏈表，非循環(huán)鏈表，循環(huán)鏈表11．使空表和非空表統(tǒng)一；算法處理一致12．O(1)，O(n)13．棧滿，棧空，m，棧底，兩個棧的棧頂在棧空間的某一位置相遇14．315．O(1)三、簡答題1．頭指針是指向鏈表中第一個結點（即表頭結點）的指針；在表頭結點之前附設的結點稱為頭結點；表頭結點為鏈表中存儲線性表中第一個數(shù)據(jù)元素的結點。7. 假定用一個單循環(huán)鏈表來表示隊列（也稱為循環(huán)隊列），該隊列只設一個隊尾指針，不設隊首指針，試編寫下列各種運算的算法：（1）向循環(huán)鏈隊列插入一個元素值為x的結點；（2）從循環(huán)鏈隊列中刪除一個結點。6. 已知線性表的元素是無序的，且以帶頭結點的單鏈表作為存儲結構。5. 已知線性表的元素按遞增順序排列，并以帶頭結點的單鏈表作存儲結構。其中data為整型數(shù)域，next和prior均為指針域。3. 設計將帶表頭的鏈表逆置算法。}四、算法設計題1. 設計在無頭結點的單鏈表中刪除第i個結點的算法。 qnext=NULL?！　　hile (pnext) p=pnext。 L=Lnext。amp。8. 下述算法的功能是什么?LinkList *Demo(LinkList *L){ // L是無頭結點的單鏈表LinkList *q,*p。5. 在單循環(huán)鏈表中設置尾指針比設置頭指針好嗎？為什么?6. 假定有四個元素A, B, C, D依次進棧，進棧過程中允許出棧，試寫出所有可能的出棧序列。三、簡答題1. 描述以下三個概念的區(qū)別：頭指針，頭結點，表頭結點。14. 設有一空棧，現(xiàn)有輸入序列1，2，3，4，5，經(jīng)過push, push, pop, push, pop, push, push后，輸出序列是_________。 13. 對于一個棧作進棧運算時，應先判別棧是否為_______，作退棧運算時，應先判別棧是否為_______，當棧中元素為m時，作進棧運算時發(fā)生上溢，則說明棧的可用最大容量為_______。11. 在單鏈表中設置頭結點的作用是________。9. 線性表、棧和隊列都是_______結構，可以在線性表的______位置插入和刪除元素；對于棧只能在_______位置插入和刪除元素；對于隊列只能在_______位置插入元素和在_______位置刪除元素。相反，當經(jīng)常進行的是插入和刪除操作時，則采用_______存儲結構為宜。6. 在雙向鏈表中，每個結點含有兩個指針域，一個指向_______結點，另一個指向_______結點。4. 要從一個順序表刪除一個元素時，被刪除元素之后的所有元素均需_______一個位置，移動過程是從_______向_______依次移動每一個元素。2. 在一個長度為n的順序表的第i個元素之前插入一個元素，需要后移____個元素。A．rear％n= = front B．front+l= rearC．rear= = front D．(rear+l)％n= front20. 在一個鏈隊列中，假定front和rear分別為隊首和隊尾指針，則刪除一個結點的操作為________。 18. 在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊頭指針和隊尾指針，則判斷隊滿的條件為________。 D．snext=hs。C．snext=hsnext。 B．snext=hs。A．top不變 B．top=0 C．top D．top++17. 向一個棧頂指針為hs的鏈棧中插入一個s結點時，應執(zhí)行______。 A．O(1) B．O(n) C．O(n2) D．O(log2n)15. 設有一個棧，元素的進棧次序為A, B, C, D, E,下列是不可能的出棧序列__________。 A．全部 B．一半 C．三分之一 D．四分之一13. 在______運算中，使用順序表比鏈表好。 A．隨機存取 B．順序存取 C．索引存取 D．散列存取11. 在順序表中，只要知道_______，就可在相同時間內(nèi)求出任一結點的存儲地址。D．存在這樣的線性表：表中各結點都沒有直接前趨和直接后繼。B．線性表中包含的數(shù)據(jù)元素個數(shù)不是任意的。 snext=q9. 以下關于線性表的說法不正確的是______。 snext=pC．pnext=snext。A．ni B．ni+l C．ni1 D．i8. 在一個單鏈表中，已知q結點是p結點的前趨結點，若在q和p之間插入s結點，則須執(zhí)行A．snext=pnext。 D．pnext=p。 B．p=pnext。 6. 設單鏈表中指針p指向結點m，若要刪除m之后的結點（若存在），則需修改指針的操作為________。 pnextprior=s。D． sprior=p。 sprior=p。C． pnext=s。 pnext=s。B． sprior=p。 pnextprior=s。A． pnext=s。A．必須是連續(xù)的 B．一定是不連續(xù)的C．部分地址必須是連續(xù)的 D．連續(xù)與否均可以 4. 從一個具有n個結點的單鏈表中查找其值等于x的結點時，在查找成功的情況下，需平均比較________個元素結點。A．一個有限序列，可以為空 B．一個有限序列，不可以為空C．一個無限序列，可以為空 D．一個無限序列，不可以為空2. 在一個長度為n的順序表中刪除第i個元素(0=i=n)時，需向前移動 個元素。}習題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. O( )11. O(log n)12. 程序對于精心設計的典型合法數(shù)據(jù)輸入能得出符合要求的結果。5. fact(n){ if(n=1)return (1)。A[i]!=k))j。while((i=0)amp。kn。j++) { c[i][j]=0。i++)for(j=0。for(i=0。j++) x++。i++)for(j=1。for(i=1。j++)x++。i++)for(j=i+1。for(i=1。三、求下列程序段的時間復雜度。12. 衡量算法正確性的標準通常是____________________________________。i=1。sum=s。jn。in。s=0。 s+=i。i=s=0。j++)A[i][j]=0。i++)for(j=0。for(i=0。7. 線性結構中元素之間存在__________________關系；樹型結構中元素之間存在__________________關系；圖型結構中元素之間存在__________________關系。5. 在樹型結構中，樹根結點沒有__________________結點，其余每個結點的有且只有__________________