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

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

3、p-next= p-next;p=p-next-next;指針P指向循環鏈表L的首元素的條件是（）。A. P= =L B. P-next= =L C. L-next=P D. P- next= =NULL在一個單鏈表中，若在p所指結點之后插入s所指結點，則執行 （）。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和p之間插入 結點s,則執行（）。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;假設雙鏈表結點的類型如下：typedef struct linknode（ int data; / 數據域struct linknode *llink; /指向前驅結點的指針域struct linknode *rlink; /指向后繼結點的指針域bnode現將一個q所指新結點作為非空雙向鏈表中的p所指結點的前驅 結點插入到該雙鏈表中，能正確完成此要求的語句段是（）。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）的單鏈表上，設有頭和尾兩個指針，執行（） 操作與鏈表的長度無關。刪除單鏈表中的第一個元素刪除單鏈表中最后一個元素在單鏈表第一個元素前插入一個新元素在單鏈表最后一個元素后插入一個新元素二、填空題 在線性表的順序存儲中，元素之間的邏輯關系是通過決定的；在線性表的鏈式存儲中，元素之間的邏輯關系是通過 決定的。在一個單鏈表中，指針p所指結點為

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

7、個指向。順序表中邏輯上相鄰的元素的物理位置緊鄰。單鏈表中邏輯上相鄰的元素的物理位置緊鄰。三、簡答題在單鏈表和雙向鏈表中，能否從當前結點出發訪問到任一結點？線性表的順序存儲結構具有3個不足：插入或刪除過程中需要移動大量的數據元素。在順序存儲結構下，線性表的存儲空間不便擴充。線性表的順序存儲結構不便于對存儲空間的動態分配。線性表的鏈式存儲結構是否一定都能夠克服上述3點不足，請說 明之。用線性表的順序存儲結構描述一個城市的設計和規劃是否合適？ 為什么？若較頻繁地對一個線性表進行插入和刪除操作，該線性表宜采用 哪種存儲結構？為什么？簡述以下算法的功能。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;線性表有兩種存儲結構：一是順序表，二是鏈表，試問：(1)如果有n個線性表同時存在，并且在處理過程中各表的長度會 動態地發生變化，線性表的總數也會自動地變化。在此情況下，應選哪種存儲結構？為什 么？（2）如線性表的總數基本穩定，且很少進行插入和刪除，但要求以 最快的速度存取線性表中的元素，那么應采取哪種存取結構？為什么？鏈表所表示的兀素是否是有序的？如果有序，則有序性體現在 何處？鏈表所表示的元素是否一定要

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

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

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

12、若存在）。13.有兩個循環鏈表，鏈頭指針分別為L1和L2,要求將L2鏈表 鏈到L1鏈表之后，且鏈接后仍保持循環鏈表形式，試寫出程序并估 計時間復雜度。第二章線性表 第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.插入和刪除首元素時不必進行特殊處理。其直接前驅結點的鏈域。8. q-prior二p。9.前驅結點，后繼結點。10.必定，不一定。三、簡答題在單鏈表和雙向鏈表中，能否從當前結點出發訪

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

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

15、特點恰好避開了順序 存儲結構的缺點。因此，應選用順序存儲結構。鏈表所表示的元素是有序的，其有序性體現在邏輯上有序， 即按指針指向的順序有序。鏈表所表示的元素在物理上不一定相鄰， 當然也可能會相鄰。有序表的有序性不僅體現在邏輯結構上有序，而 且在物理結構上也有序。四、算法設計題(對于有些題目只給出一種參考的解題思路)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 /定義一個具體數字作為最大長度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帶有一個頭結點c,再后 將其刪除。函數實現如下：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/*找到元素值相同的結點*/s=( LinkList) malloc( sizeof( LNode); s-dat

19、a=p-data; r-next=s;/*把s結點鏈接到c的末尾*/r=s;/*r始終指向C鏈表的最后一個結點while (p-data=p- next-data) /*跳過值相同的結點*/ p=p-next; p-p-next ;while(q-data=q- next-data) /*跳過值相同的結點*/ 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) ;/*建立一個頭結點，r總是指向Hc鏈表的最后一個 結點*/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;)假設a,b,c分別為單鏈表A, B,C的頭結點指針，同步遍歷兩

24、個鏈表，順序復制A,B的結點到C中，直到鏈表遍歷完為止。函數實 現如下：LinkList union (Linklist a, linkList b) linklist r, s, p, q, c;c=( LinkList) malloc( sizeof (LNode)/* 生成一個頭結點* /r=C;p=a; q=b;while (p)(/*復制一個與A鏈表中結點相同的結點，把它鏈到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兩個表一邊進行歸并;在歸并過程 中