【正文】 i、 j、 k 分別指示 A、 B、 C 三個順序表的當前位置，若 A、 B 表中當前元素值相同，則寫入 C 中，并使 i、 j、 k 值增 1；若 A 表元素值較小，則使 i 增 1；若 B 表元素值較小，則使 j 增 1，直到有一個表先結束。個結點 p=p— next； ／／ p 指向原鏈表 A 中的奇數(shù)序號的結點 } r— next=NULL； ／／將生成 B 鏈表中的最后一個結點的 next 域置為空 } 9．假設以兩個元素值遞增有序排列的線性表 A、 B 分別表示兩個集合，要求另辟空間構造一個線性表 C，其元素為兩集合的交集，且表 C 中的元素值也遞增有序排列。amp。 答：分析：用兩個 工作指針 p 和 q 分別指示序號為奇數(shù)和序號為偶數(shù)的結點，將 q 所指向的結點從 A表刪除，并鏈接到 B表。amp。kj1) {r=r— next； k++； } ／／查找 Lb 表中第 i— 1 個元素 if(!r) exit(0)； q— next=r— next； r— next=p； ／／完成插入 } } 7．單鏈表 L 是一個遞減有序表，試寫一高效算法，刪除表中值大于 min 且小于 max 的結點 (若表中有這樣的結點 )，同時釋放被刪結點空間，這里 min 和 max是兩個給定的參數(shù)。 k=1； ／／ j1 時 while(ramp。amp。ki) ／／在 la 表中查找第 i 個結點 {pre=p； p=pnext。 void Deletelnsert(LinkedList *la， LinkedList *lb， int i， int j, int len) {／／刪除不帶頭結點的單鏈表 la 中第 i 個元素起共 len 個元素 ,并將這峰元素插入到單鏈表 lb中第 j個結點之前 if(i0||j0||len0) exit(0)； p=la； k=1； pre=NULL； while(pamp。 答：分析：先在 la 中找到第 i 個結點，分別用兩個指針 pre 和 p 指向第 i1 和第 i 個結點，然后用指針 q 從第 i 個結點起向后走 len 個元素，使 q 指向此位置。pb) ／／ A 和 B 都不為空時 {if(pa— datapb— data) ／／ A 當前結點值較小 {qa=panext； pCnext=pa； pc=pcnext； pa=qa； } else {qb=pbnext； pcnext=pb： pc=pcnext； pb=qb； } ／／ B 當前結點值較小 } if(pa)pc— next=pa； ／／ A 沒有結束，將 A 表剩余元素鏈接到 C 表 if(pb)pc— next=pb； ／／ B 沒有結束，將 B 表剩余元素鏈接到 C 表 free(B)； ／／釋放 B 表的頭結點 } 本算法需要遍歷兩個線性表，因此時間復雜度為 O(m+n)。} (2) VOid Linkmerge(LinkedList *A， LinkedList *B， LinkedList *C) {／／有序鏈表 A 和 B 歸并成有序鏈表 C pa=A— next； pb=B— next； C=A； pc=C； while(paamp。j++； } ／／ B 中當前元素較小 k++； } if (i==m) for(t=j； tn； t++) {Cdata[k]=[t]。amp。最后將沒結束的表的剩余元素寫入 C 表中。試寫一算法分別以順序存儲和鏈式存儲將 A 和 B 歸并成一個仍按元素值遞增有序的線性表 C。amp。 void LinkedListlnsert(LinkedList *L， int x， int i) {／／不帶頭結點的單鏈表的第 i 個元素之前插入一個元素 p=L： j=1。p— datax) ／ ／找到插入的位置 {q=p； p=p— next； } s=(LinkedList*)malloc(sizeof(LinkedList))； ／／生成新結點 S— data=x； S— next=p； q— next=s； } 4. 試寫出在不帶頭結點的單鏈表的第 i 個元素之前插入一個元素的算法。 void LinkListinsert(LinkedList *L， int x){／／ x 插入有序鏈表 L 中 q=L； p=q— next； while(p!=NULLamp。k=i； k) ／／元素從后往前依次后移 Ldata[k+1]=Ldata[k]； Ldata[i]=x； ／／ x 插入到正確位置 Llength++； ) L 是一個遞減有序表，試寫一個算法將 x 插入其中后仍保持 L 的有序性。amp。 void SeqListinsert(SeqList *L， int x){／／ x 插入到遞增有序的順序表 L 中 i=0。 void Linkedreverse(LinkedList *L){／／鏈表的就地逆置 p=Lnext； Lnext=NULL； while(p!=NULL) {r=p， p=pnext； ／／ r 指向當前待逆置的結點， p 記下下 — 個結點 rnext=L— next； Lnext=r； ／／放到表頭 } } 2．設順序表 L 是一個遞增 (允許有相同的值 )有序表，試寫一算法將 x 插入 L 中，并使 L仍為一個有序表。 Ldata[j]=t。 void Seqreverse(SeqList *L){／／順序表的就地逆置 for(i=0； j=Llength1； ij； i++， j) {t=Ldata[i]。 1．試用順序表作為存儲結構，實現(xiàn)將線性表 (a0， a1， a2，? an1)就地逆置的操作，所謂“就地”是指輔助空間為 O(1)。 Typedef struct node2 {datatype data。 Typedef struct node1 {datatype data[maxsize]。因為順序存儲結構存取元素操作的時間復雜度為 O(1)。而鏈表則可根據(jù)需要動態(tài)地申請空間，因此適用 6 于動態(tài)變化表長的線性表。在此情況下，應選擇哪一種存儲結構？為什么？ 答：應選用鏈式存儲結構。 qnext=NULL； } return L； } 答：如果長度大于 1，則將首元結點刪除并插入到表尾。Lnext) { q=L； L=Lnext； p=L。 6．下列算法的功能是什么？ LinkList *testl(LinkList *L) {//L 是無頭結點的單鏈表 LinkList *q， *p； if(Lamp。 5．雙鏈表和單循環(huán)鏈表中，若僅知道指針 p 指向某個結點，不知道頭指針，能否將結點 *p 從相應的鏈表中刪除？若可以，其時間復雜度各為多少？ 答：能刪除。 4．為什么在單循環(huán)鏈表中設置尾指針比設置頭指 針更好？ 答：單循環(huán)鏈表中無論設置尾指針還是頭指針都可以遍歷表中任一個結點，但設置尾指針時，若在表尾進行插入或刪除操作可在 O(1)時間內完成，同樣在表頭進行插入或刪除操作也可在 O(1)時間內完成。 3．在順序表中插入和刪除一個結點需平均移動多少個結點？具體的移動次數(shù)取決于哪兩個因素？ 答：平均移動表中大約一半的結點，插入操作平均移動 n/2 個結點，刪除操作平均移動（ n1） /2 個結點。從時間上來看，若線性表的操作主要是查找，很少進行插入和刪除操作時，應選用順序表。頭指針是指向鏈表中的第一個結點的指針。 答：首元結點是指鏈表中存儲的線性表中的第一個數(shù)據(jù)元素的結點。 17．設 r 指向單循環(huán)鏈表的最后一個結點，要在最后一個結點之后插入 s 所指的結點，需執(zhí)行的三條語句是 ___snext= rnext __； rnext=s； r=s； 18．在單鏈表中，指針 p 所指結點為最后一個結點的條件是 __ pnext=NULL___。 15．設 head 指向單鏈表的表頭， p 指向單鏈表的表尾結點，則執(zhí)行 pnext=head 后，該單鏈表構成 __單循環(huán)鏈表 ___。 13．在雙鏈表中，每個結點有兩個指針域，一個指向 ___前驅 __，另一個指向 ___后繼 ___。 11．在一個長度為 n 的向量的第 i(1≤ i≤ n+1)個元素之前插入一個元素時，需向后移動 ___ ni+1__個元素。 9．單鏈表表示法的基本思想是用 ___指針 ___表示結點間的邏輯關系。 7． rear 是指向非空帶頭結點的單循環(huán)鏈表的尾指針，則刪除起始結點的操作可表示為 __ p=rearnext； q=pnext； pnext=qnext； free(q)； ____。 5．在單鏈表中，刪除 p 所指結點的直接后繼的操作是 __ q=pnext； pnext=qnext； free(q)； ___ 5 3．所有結點按一對一的鄰接關系構成的整體就是 __線性 __結構。對任意一對相鄰結點 ai、 ai+1(1≤ in)， ai 稱為 ai+1 的直接 _前驅 _， ai+1稱為 ai的直接 __后繼 __。 三、填空題 1．為了便于討論，有時將含 n(n0)個結點的線性結構表示成 (a1， a2，?， an)，其中每個 ai 代表一個 __結點 _。 ╳ 9．在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此，單鏈表是隨機存取的存儲結構。 ╳ 7．線性表的鏈式存儲結構優(yōu)于順序存儲結構。 √ 5．在線性表的鏈式存儲結構中，邏輯上相鄰的元素在物理位置上不一定相鄰。 √ 3．線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性，因此是屬于同一數(shù)據(jù)對象。 A．單鏈表 B．雙鏈表 C．循環(huán)鏈表 *D．順序表 二、判斷題 √ 1．順序存儲的線性表可以隨機存取。 A． rear 和 rearnextnext *B． rearnext 和 rear C． rearnextnext 和 rear D． rear 和 rearnext 19．循環(huán)鏈表的主要優(yōu)點是 ( )。 *A． q=pnext； pnext=qnext； free(q)； B． p=pnext； pnext=pnextnext； free(p)； C． pnext=pnext； free(pnext)； D． p=pnextnext；free(pnext)； 17． 設指針 p 指向雙鏈表的某一結點，則雙鏈表結構的對稱性可用 ( )式來刻畫。 *A．順序表 B. 單鏈表 C．雙鏈表 D．單循環(huán)鏈表 15．設 rear 是指向非空帶頭結點的單循環(huán)鏈表的尾指針，則刪除表頭結點的操作可表示為 ( )。 *B． snext=pnext； pnext=s； C． snext=pnext； p=s； D． pnext=s； snext=p。在 *p 之后插入結點 *s，則執(zhí)行 ( )。 snext=p； D． pnext=s。 A． pnext=s； sprior=p； pnextprior=s； snext=pnext； B． pnext=s； pnextprior=s； sprior=p： snext=pnext； C． sprior=p；snext=pnext； pnext=s； pnextprior=s； *D． sprior=p； snext=pnext； pnextpror=s； pnext=s； 12. 在一個單鏈表中，已知 *q 結點是 *p 結點的前驅結點，若在 *q 和 *p 之間插入結點 *s，則執(zhí)行 ( )。 A． head=NULL *B． headnext=NULL C． headnext=head D． head!=NULL 10．非空單循環(huán)鏈表 head 的尾結點 *p 滿足 ( )。 4 A． n *B． n/2 C． (n1)/2 D． (n+1)/2 8．在含有 n 個結點的順序存儲的線性表中，刪除一個結點所需移動結點的平均次數(shù)為 ( )。 A．條件判斷 *B．結點移動 C．算術表達式 D．賦值語句 6．對于順序表的優(yōu)缺點，以下說法錯誤的是 ( )。 A．鏈式存儲結構 *B．順序存儲結構 C．索引存儲結構 D．散列存儲結構 4．對于順序表，以下說法錯誤的是 ( )。