數(shù)據(jù)結(jié)構(gòu) 第二章：線性表

1、第二章線性表：習題習題一、選擇題L是線性表，已知Length（L）的值是5,經(jīng)運算?Delete（L, 2）后，length（L）的值是（c）。一5 B.0 C.4 D.6線性表中，只有一個直接前驅(qū)和一個直接后繼的是（）。首元素B.尾元素C.中間的元素 D.所有的元素+3.帶頭結(jié)點的單鏈表為空的判定條件是（）。head= =NULL B. head-next= =NULLC. head-next=head D. head!=NULL不帶頭結(jié)點的單鏈表head為空的判定條件是（）。A. head=NULL B. head-next =NULLC.head-next=head D. head!=N

2、ULL非空的循環(huán)單鏈表head的尾結(jié)點P滿足（）。A. p-next = =NULL B. p=NULLC. p-next=head D. p= =head線性表中各元素之間的關(guān)系是（c）關(guān)系。A.層次 B.網(wǎng)狀C.有序 。.集合在循環(huán)鏈表的一個結(jié)點中有（）個指針。A. 1 B. 2 C. 0 D. 3在單鏈表的一個結(jié)點中有（）個指針。A. 1B. 2 C. 0 D. 3在雙鏈表的一個結(jié)點中有（）個指針。A. 1B. 2 C. 0 D. 3在一個單鏈表中，若刪除p所指結(jié)點的后繼結(jié)點，則執(zhí)行（）。p-next= p-next -next;p=p-next; p-next=p-next-next;

3、p-next= p-next;p=p-next-next;指針P指向循環(huán)鏈表L的首元素的條件是（）。A. P= =L B. P-next= =L C. L-next=P D. P- next= =NULL在一個單鏈表中，若在p所指結(jié)點之后插入s所指結(jié)點，則執(zhí)行 （）。A. s-next=p; p-next=s; B. s-next=p-next; p-next=s;C. s-next=p-next; p=s; D. p-next=s; s-next=p;在一個單鏈表中，已知q是p的前驅(qū)結(jié)點，若在q和p之間插入 結(jié)點s,則執(zhí)行（）。A. s-next= p-next; p-next=s; B.

4、p-next=s-next; s-next=p;?C. q-next=s; s-next=p; D. p-next=s; s-next=q;假設(shè)雙鏈表結(jié)點的類型如下：typedef struct linknode（ int data; / 數(shù)據(jù)域struct linknode *llink; /指向前驅(qū)結(jié)點的指針域struct linknode *rlink; /指向后繼結(jié)點的指針域bnode現(xiàn)將一個q所指新結(jié)點作為非空雙向鏈表中的p所指結(jié)點的前驅(qū) 結(jié)點插入到該雙鏈表中，能正確完成此要求的語句段是（）。q-rlink=p;q-llink=p-llink; p-llink=q; p-llink-

5、rlink=q;p-llink=q;q-rlink=p; p-llink-rlink=q; q-llink=p-llink;q-llink=p-rlink; q-rlink=p； p-link-rlink=q; p-llink=q;以上都不對在一個長度為n（n1）的單鏈表上，設(shè)有頭和尾兩個指針，執(zhí)行（） 操作與鏈表的長度無關(guān)。刪除單鏈表中的第一個元素刪除單鏈表中最后一個元素在單鏈表第一個元素前插入一個新元素在單鏈表最后一個元素后插入一個新元素二、填空題 在線性表的順序存儲中，元素之間的邏輯關(guān)系是通過決定的；在線性表的鏈式存儲中，元素之間的邏輯關(guān)系是通過 決定的。在一個單鏈表中，指針p所指結(jié)點為

6、最后一個結(jié)點的條件是O在一個單鏈表最后一個結(jié)點r之后插入結(jié)點s，則需執(zhí)行的3條語句是； r=s; r-next= NULLo對于一個具有n個結(jié)點的單鏈表，在已知p所指結(jié)點后插入一 個新結(jié)點的時間復雜度是;在值域為給定值的結(jié)點后插入一個新結(jié)點的時間復雜度是O 單鏈表是的鏈接存儲表示。 單鏈表中設(shè)置頭結(jié)點的作用是o一7.在單鏈表中，除首元結(jié)點外，任一結(jié)點的存儲位置由指示。在非空雙向循環(huán)鏈表中，在結(jié)點q的前面插入結(jié)點p的過程如下：p-prior; q-prior; q-prior-next-;p; TOC o 1-5 h z p-next=q; ； 在雙向鏈表中，每個結(jié)點有兩個指針域，一個指向，另一

7、個指向。順序表中邏輯上相鄰的元素的物理位置緊鄰。單鏈表中邏輯上相鄰的元素的物理位置緊鄰。三、簡答題在單鏈表和雙向鏈表中，能否從當前結(jié)點出發(fā)訪問到任一結(jié)點？線性表的順序存儲結(jié)構(gòu)具有3個不足：插入或刪除過程中需要移動大量的數(shù)據(jù)元素。在順序存儲結(jié)構(gòu)下，線性表的存儲空間不便擴充。線性表的順序存儲結(jié)構(gòu)不便于對存儲空間的動態(tài)分配。線性表的鏈式存儲結(jié)構(gòu)是否一定都能夠克服上述3點不足，請說 明之。用線性表的順序存儲結(jié)構(gòu)描述一個城市的設(shè)計和規(guī)劃是否合適？ 為什么？若較頻繁地對一個線性表進行插入和刪除操作，該線性表宜采用 哪種存儲結(jié)構(gòu)？為什么？簡述以下算法的功能。Status A(LinkedList L)( /

8、L是無表頭單鏈表if (L&L-next)Q=L; L=L-next; P=L;while (P-next) (p=P-next；p-next=Q;Q-next=NULL;return OK;線性表有兩種存儲結(jié)構(gòu)：一是順序表，二是鏈表，試問：(1)如果有n個線性表同時存在，并且在處理過程中各表的長度會 動態(tài)地發(fā)生變化，線性表的總數(shù)也會自動地變化。在此情況下，應選哪種存儲結(jié)構(gòu)？為什 么？（2）如線性表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除，但要求以 最快的速度存取線性表中的元素，那么應采取哪種存取結(jié)構(gòu)？為什么？鏈表所表示的兀素是否是有序的？如果有序，則有序性體現(xiàn)在 何處？鏈表所表示的元素是否一定要

9、在物理上是相鄰的？有序表的有序性該如何理解？四、算法設(shè)計題給定（已生成）一個帶頭結(jié)點的單鏈表，設(shè)head為頭指針，結(jié) 點的結(jié)構(gòu)為（data，next），data為整數(shù)元素，next為指針。試寫出算法：按遞增次序輸出單鏈表 中各結(jié)點的數(shù)據(jù)元素并釋放結(jié)點所占的存儲空間。（要求：不允許使 用數(shù)組作輔助空間）。已知數(shù)組線性表數(shù)據(jù)類型如下，寫一個算法，刪除線性表中小 于0的所有元素。有一個單鏈表，其頭指針為head，編寫一個函數(shù)計算數(shù)據(jù)域為 x的結(jié)點個數(shù)。編寫算法，實現(xiàn)在無頭結(jié)點的線性鏈表L中刪除第i個結(jié)點的 操作 Delete（L,i）。編寫算法，實現(xiàn)在無頭結(jié)點的線性鏈表L中第i個結(jié)點前插入 數(shù)據(jù)為e

10、的結(jié)點的操作insert（L，i，e）。設(shè)計將一個雙向循環(huán)鏈表逆置的算法。已知遞增有序的單鏈表A、B分別存儲了一個集合，請設(shè)計算 法以求出兩個集合A和B的差集A-B （即僅在A中出現(xiàn)而不在B中 出現(xiàn)的元素所構(gòu)成的集合），并以同樣的形式存儲，同時返回該集合 的元素個數(shù)。已知兩個整數(shù)集合A和B，它們的元素分別依元素值遞增有序 存放在兩個單鏈表H和Hb中，編寫一個函數(shù)求出這兩個集合的并集 丁并要求表示集合C的鏈表H的結(jié)點仍依元素值遞增有序存放。已知A、B和C為3個遞增有序的線性表，現(xiàn)要求對A表做如 下操作：刪去那些在B表中出現(xiàn)又在C表中出現(xiàn)的元素。試對單鏈 表編寫實現(xiàn)上述操作（要求釋放表A中的無用結(jié)

11、點空間）的算法， 并分析算法的時間復雜度（注：題中沒有特別指明表中的元素各不相 同）。有兩個單鏈表 A 和 B，A： （a，a，-, a ，（b，b，-, b ，i 2ni 2n編寫函數(shù)將其合并成一個鏈表C, C=（a ,b ,a ,b，a ,b .112 2 n n假設(shè)有兩個按元素遞增有序排列的線性表A和B,均以單鏈表 做存儲結(jié)構(gòu)。請編寫算法，將表A和表B歸并成一個按元素值非遞減有序（允許值相同） 排列的線性表6并要求利用原表（即表A和表B）的結(jié)點空間存放 表C。12 .設(shè)在一個帶表頭結(jié)點的單鏈表中所有元素結(jié)點的數(shù)據(jù)值按遞 增順序排列，試編寫一個函數(shù)，刪除表中所有大于min小于max的元素（

12、若存在）。13.有兩個循環(huán)鏈表，鏈頭指針分別為L1和L2,要求將L2鏈表 鏈到L1鏈表之后，且鏈接后仍保持循環(huán)鏈表形式，試寫出程序并估 計時間復雜度。第二章線性表 第2章線性表一、選擇題1.C2.C3.B4.A5.C6.C7.A8.A9.B10.AIl.C12.B13.C14.C15. A,C,D二、填空題相鄰位置，鏈接指針。 2. p-next=NULL。r-next=S. 4.O（1）,O（n）.5.線性表。6.插入和刪除首元素時不必進行特殊處理。其直接前驅(qū)結(jié)點的鏈域。8. q-prior二p。9.前驅(qū)結(jié)點，后繼結(jié)點。10.必定，不一定。三、簡答題在單鏈表和雙向鏈表中，能否從當前結(jié)點出發(fā)訪

13、問到任一結(jié) 點？在單鏈表中，只能由當前結(jié)點訪問其后繼的任一結(jié)點，但因其沒 有指向前驅(qū)的指針而無法訪問其前驅(qū)結(jié)點。在雙向鏈表中，由于當前 結(jié)點既有指向后繼結(jié)點的指針，又有指向前驅(qū)結(jié)點的指針，所以在雙 向鏈表中可以由當前結(jié)點出發(fā)訪問表中的任何一個結(jié)點。不一定。由于鏈式存儲需要額外的空間來存儲指針，所以要 比順序表存儲多占用空間。在空間允許的情況下，鏈存儲結(jié)構(gòu)可以克 服順序存儲結(jié)構(gòu)的弱點式，但空間不允許時，鏈式存儲結(jié)構(gòu)會出現(xiàn)新 的問題。不合適。因為一個城市的設(shè)計和規(guī)劃涉及非常多的項目，比 較復雜，經(jīng)常需要改動、擴充和刪除各種信息，以適應不斷發(fā)展的需 要，所以順序不能很好地滿足其需要。該線性表宜采用鏈

14、式存儲結(jié)構(gòu)。因為采用鏈式存儲結(jié)構(gòu)的線 性表，插入和刪除操作只需要改變指針，時間復雜度0(1)；而采用順 序存儲結(jié)構(gòu)的線性表插入和刪除涉及到數(shù)據(jù)的大量移動，時間復雜度 為 0(n)。如果L的長度大于或等于2,則將首結(jié)點移到表尾。6.鏈式存儲結(jié)構(gòu)可以用任意的空間來存儲線性表中的各數(shù)據(jù)元 素，其存儲空間可以是連續(xù)的，也可以不連續(xù);此外，這種存儲結(jié)構(gòu) 對元素進行插入和刪除操作時都無需移動元素，而僅修改指針即可， 所以很適用于線性表容量變化的情況。由于順序存儲結(jié)構(gòu)一旦確定了起始位置，線性表中的任何一 個元素都可以進行隨機存取，即存取速度較高；并且，由于線性表的 總數(shù)基本穩(wěn)定，且很少進行插入和刪除，故這一

15、特點恰好避開了順序 存儲結(jié)構(gòu)的缺點。因此，應選用順序存儲結(jié)構(gòu)。鏈表所表示的元素是有序的，其有序性體現(xiàn)在邏輯上有序， 即按指針指向的順序有序。鏈表所表示的元素在物理上不一定相鄰， 當然也可能會相鄰。有序表的有序性不僅體現(xiàn)在邏輯結(jié)構(gòu)上有序，而 且在物理結(jié)構(gòu)上也有序。四、算法設(shè)計題(對于有些題目只給出一種參考的解題思路)1. void increase (LkList*head) LkList *p, *q, *r; int min;p=head-next;while(p!=NULL) q=NULL;min=p-data;r=p;while(r-next! =NULL)if(r-next-data)

16、 next-data;r=r-next;printf( %d，min);if (q=NULL) p=p-next;else q-next=q-next-next;#define maxlen 100 /定義一個具體數(shù)字作為最大長度typedef struct int elem maxlen;int last; Listtp;算法如下：typedef struct( int elemmaxlen;int last; listtp;void Delete (listtp A) int i, j, k;k=0;if (A. last=0) printf( Its empty!)；else for (

17、i=l; i=A. last; i+)if (A.elemi 0)for(j =i;j data=x) n+;p=p-next; return n; status insert(LinkList *L,int i, Elentype e) (p=L;j=1;s= (LinkList) malloc (sizeof (Lnode);s-data=e;if(i=1) s-next=L; L=s;)elsewhile(p&jnext;+j;if( !p) return ERROR;s-next=p-next;p-next=s; return OK; 兩個表的公共元素指的是既存在單鏈表A中又存在于單鏈

18、表 B中的元素，為了操作方便，先讓單鏈表C帶有一個頭結(jié)點c,再后 將其刪除。函數(shù)實現(xiàn)如下：Linklist Inter_eq(LinkList a,LinkList b) linkList p, q, r, c;c=( Linklist) malloc( sizeof (LNode); / 建立單鏈表 C的頭指針r=C;p=a;q=b;while(p&q)(if (p-datadata) p=p-next; else if (p-dataq-data) q=q-next; else/*找到元素值相同的結(jié)點*/s=( LinkList) malloc( sizeof( LNode); s-dat

19、a=p-data; r-next=s;/*把s結(jié)點鏈接到c的末尾*/r=s;/*r始終指向C鏈表的最后一個結(jié)點while (p-data=p- next-data) /*跳過值相同的結(jié)點*/ p=p-next; p-p-next ;while(q-data=q- next-data) /*跳過值相同的結(jié)點*/ q=q-next;q=q-next;r-next=NUIL;S=c;c=c-next;free (s);return C：)invert (dLkList *head) dLkList p, q;p=head;do q=p-next;p-next=p-pre;p-pre=q;p=q; w

20、hile(p!=head);)void Sunset (LkList*A, LkList*B, LkList*C, int n) C=malloc (sizeof (LkList);r=C; n=0; p=A-next; q=B-next;switch(p!=NULL) & (q!二NULL) case p-dataq-data: q=q-next;case p-data=q-data: p=p-next; q=q- next;case p-datadata: (s=malloc( sizeof (lklist); s-data=p-data;p=p-next;n+;while (p!=NUL

21、L) s=malloc (sizeof (LkList); s-data=p-data;r-next=s ;r=s ;p=p-next;r-next=NULl;void MergeList(LinkList Ha, LinkList Hb, LinkList *Hc) LinkList p, q, r, s;Hc= ( LinkList) malloc ( sizeof) ( LNode) ;/*建立一個頭結(jié)點，r總是指向Hc鏈表的最后一個 結(jié)點*/r=Hc; p=Ha; q=Hb;while (p&q)s= (LinkList) malloc ( sizof ( LNode) ;r-next

22、=s ; r=s ;if (p-datadata) s-data=p-data; p=p-next; else if (p-dataq-data) s-data=q-data; q=q-data; else s-data=p-data;p=p-next ;q=q-next ;while (q) s= (LinkList) malloc (sizeof (LNode);s-data=q-data;r-next=s ; r=s ;q=q-next;while (p) s= (LinkList) malloc (sizeof ( LNode ;s-data=p-data;r-next=s; r=s;

23、p=p-next;r-next=NULL;s=Hc;Hc=Hc-next：free (s);)void ListSubInter(LinkList *A, LinkList B, LinkList C)( LinkList L,p,pre,q,s;L=Inter_eq (B,C);Pre=A; p=A-next;While (p) q=L;while(q&p-datadata)q=q-next;if (p-data=q-data) s=p; p=p-next;pre-next-p; free(s);pre=p;p=p-next;)假設(shè)a,b,c分別為單鏈表A, B,C的頭結(jié)點指針，同步遍歷兩

24、個鏈表，順序復制A,B的結(jié)點到C中，直到鏈表遍歷完為止。函數(shù)實 現(xiàn)如下：LinkList union (Linklist a, linkList b) linklist r, s, p, q, c;c=( LinkList) malloc( sizeof (LNode)/* 生成一個頭結(jié)點* /r=C;p=a; q=b;while (p)(/*復制一個與A鏈表中結(jié)點相同的結(jié)點，把它鏈到c中*/s= (LinkList) malloc (sizeof (LNode);S - data=p-data;r-next=s; p=p-next;r=S;s=(LinkList) malloc (sizeof( LNode);s-data=q-data;r-next=s ; q=q-next;r=S：r-next=NULL;s=c;c=c-next;free (s);return C;)將A、B兩個鏈表合成一個鏈表C且新鏈表必須使用A、B的 原有空間，因此需要一邊遍歷A、B兩個表一邊進行歸并;在歸并過程 中