1、一、 選擇題1從一個具有n個結點的單鏈表中查找值為x的結點，在查找成功情況下，需平均比較（ d）n個節(jié)點，單鏈表。如果x等于第一個元素的值。則要比較1次 x等于第二個元素的值，則要比較2次 最不巧：x值剛好等于第n個元素，則要比較x次所以總次數(shù)是1+2+3+n-1+n=(n+1)*n/2所以平均需要：(n+1)/2次。順序數(shù)組可以用折半查找，需要 log2為低N 次個結點。AnBn/2C（n-1）/2D（n+1）/22（a ）插入、刪除速度快，但查找速度慢。鏈表只需要修改前驅或者前驅與后繼的指針就可以，查找時鏈表需要順序查找，并且由于讀取指針耗費時間A鏈表B順序表C有序順序表D上述三項無法比較

2、3若希望從鏈表中快速確定一個結點的前驅，則鏈表最好采用（ c）方式。雙鏈表在結點前驅后繼查找上的時間復雜度是O(1)A單鏈表B循環(huán)單鏈表C雙向鏈表D任意4在一個單鏈表中，若刪除p所指結點的后繼結點，則執(zhí)行（d）。p->next指向p指針的后繼結點，p->next->next指向后繼結點的后繼結點。Ap->next=p->nextBp=p->next->nextCp=p->next;p->next=p->next->next;Dp->next=p->next->next5帶頭結點的單鏈表head為空的判定條件是（

3、b ）。Ahead=NULLBhead->next=NULLChead->next=headDhead!=NULL6在循環(huán)雙向鏈表的p所指結點之后插入s所指結點的操作是（ d）。Ap->next=s;s->prior=p;p->next->prior=s;s->next=p->next;Bp->next=s;p->next->prior=s;s->prior=p;s->next=p->next;Cs->prior=p;s->next=p->next;p->next=s;p->nex

4、t->prior=s;Ds->prior=p;s->next=p->next;p->next->prior=s;p->next=s;7若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（ a）存儲方式最節(jié)省時間。想要存取任一指定序號的元素，鏈表實現(xiàn)這個功能的代價很大本來順序表的弱點在于插入和刪除元素，但是題目要求只最后進行插入和刪除運算，所有順序表是最好的選擇！A順序表B雙向鏈表C帶頭結點的雙循環(huán)鏈表D單循環(huán)鏈表二、 填空題1對于采用順序存儲結構的線性表，當隨機插入或刪除一個數(shù)據(jù)元素時，平均約需移動表中 一半 元素。2當對

5、一個線性表經(jīng)常進行的是插入和刪除操作時，采用 鏈式 存儲結構為宜。因為采用鏈式結構存儲線性表，插入和刪除操作需要從頭結點起查找被插入或刪除結點的前驅結點，并修改這些結點的指針域，查找過程平均移動指針域為表長的一半3當對一個線性表經(jīng)常進行的是存取操作，而很少進行插入和刪除操作時，最好采用 順序 存儲結構。它的特點是邏輯關系上相鄰的兩個元素在物理位置上也相鄰，因此可以隨機存取表中任一元素，它的存儲位置可用一個簡單，直觀的公式來表示4在一個長度為n的順序存儲結構的線性表中，向第i個元素（1in+1）之前插入一個新元素時，需向后移動 n-i+1 個元素。這道題，可以進行舉例來驗證，比如要是在第一個元素

6、前插入元素，需要移動n個元素。i=1時，需要移動n個，進行驗證5從長度是n的采用順序存儲結構的線性表中刪除第i個元素（1in），需向前移動 n-i 個元素。6對于長度是n的順序存儲結構的線性表，插入或刪除元素的時間復雜度為 0（n） 。7在具有n個結點的有序單鏈表中插入一個新結點并仍然有序的時間復雜度是 0（n） 。因為單鏈表保存的信息只有表頭 如果要在特定位置插入一個節(jié)點 需要先從表頭一路找到那個節(jié)點 這個過程是O(n)的8在雙向鏈表中，每個結點共有兩個指針域，一個指向 前驅 結點，另一個則指向 后繼 結點。三、 判斷題1鏈表中的頭結點僅起到標識的作用。（ f）頭結點的數(shù)據(jù)域還可以存儲一些必

7、要的數(shù)據(jù)，如表長。2順序存儲結構的主要缺點是不利于插入和刪除操作。（ t）3線性表采用鏈表存儲時，結點和結點內部的存儲空間可以是不連續(xù)的。（ f）結點內部空間是連續(xù)的。4順序存儲方式插入和刪除時效率太低，因此它不如鏈式存儲方式好。（ f）還有其他比較參數(shù)。如空間利用率，難易程度，存取快捷等。5對任何數(shù)據(jù)結構鏈表存儲結構一定優(yōu)于順序存儲結構。（ f）還有其他比較參數(shù)。如空間利用率，難易程度，存取快捷等。6順序存儲方式只能用于存儲線性結構。（ f）也可用于樹、二叉樹等7循環(huán)鏈表不是線性表。（ f）8為了很方便地插入和刪除數(shù)據(jù)，可以使用雙向鏈表存放數(shù)據(jù)。（ t）9線性表的特點是每個元素都有一個前驅和

8、一個后繼。（ f）第一個結點無前驅，最后一個結點無后繼。10取線性表的第i個元素的時間與i的大小有關。（ f）看線性表的存儲機構，鏈表有關，順序表無關。四、 應用題1線性表有兩種存儲結構：一是順序表，二是鏈式表。試問：如果有n個線性表同時并存，并且在處理過程中各表的長度會動態(tài)變化，線性表的總數(shù)也會自動地改變。在此情況下，應選用哪種存儲結構？為什么？鏈表，理由是鏈表能夠高效的執(zhí)行插入刪除操作，適用于元素變化較多的情形若線性表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取線性表中的元素，那么應采用哪種存儲結構？為什么？順序存儲結構。順序表可以隨機存取，時間復雜度為O（1）2線性表的順

9、序存儲結構具有三個弱點：其一，在進行插入或刪除操作時，需移動大量元素；其二，由于難以估計，必須預先分配較大的空間，往往使存儲空間不能得到充分的利用。線性表的鏈式存儲結構是否一定都能克服以上缺點，試討論之。鏈式存儲結構一般說克服了順序存儲結構的三個弱點。首先，插入、刪除不需移動元素，只修改指針，時間復雜度為O(1)；其次，不需要預先分配空間，可根據(jù)需要動態(tài)申請空間；其三，表容量只受可用內存空間的限制。其缺點是因為指針增加了空間開銷，當空間不允許時，就不能克服順序存儲的缺點。3線性表（a1，a2，.，an）用順序映射表示時，ai和ai+1（1<=i<n）的物理位置相鄰嗎？鏈接表示時呢？

10、順序映射時，ai與ai+1的物理位置相鄰；鏈表表示時ai與ai+1的物理位置不要求相鄰。4試述頭結點，首元結點，頭指針這三個概念的區(qū)別。在線性表的鏈式存儲結構中，頭指針指鏈表的指針，若鏈表有頭結點則是鏈表的頭結點的指針，頭指針具有標識作用，故常用頭指針冠以鏈表的名字。頭結點是為了操作的統(tǒng)一、方便而設立的，放在第一元素結點之前，其數(shù)據(jù)域一般無意義（當然有些情況下也可存放鏈表的長度、用做監(jiān)視哨等等），有頭結點后，對在第一元素結點前插入結點和刪除第一結點，其操作與對其它結點的操作統(tǒng)一了。而且無論鏈表是否為空，頭指針均不為空。首元結點也就是第一元素結點，它是頭結點后邊的第一個結點。5在單鏈表和雙向鏈表

11、中，能否從當前結點出發(fā)訪問到任何一個結點？在單鏈表中不能從任意結點（若結點不是第一結點）出發(fā)訪問到任何一個結點，鏈表只能從頭指針開始，訪問到鏈表中每個結點。在雙鏈表中求前驅和后繼都容易，從任何一個結點向前到第一結點，向后到最后結點，可以訪問到任何一個結點。6如何通過改鏈表的方法，把一個單向鏈表變成一個與原來鏈接方向相反的單向鏈表？設該鏈表帶頭結點，將頭結點摘下，并將其指針域置空，然后從第一元素節(jié)點開始，直到最后一個結點為止，依次前插入頭結點的后面，則實現(xiàn)了鏈表的逆置五、 算法設計題1 已知單鏈表L，寫一個算法，刪除其中的重復結點。void delete(LinkList &L)Link

12、Node *p,*q,*s; ElemType e; for(p=L->next;p;p=p->next)  e=p->data;for(q=p->next;q;)  if(e=q->data) s=q; p->next=q->next; q=q->next; free(s);else q=q->next;  2 將數(shù)據(jù)元素x插入到遞增有序的順序表的適當位置，使插入后的順序表仍為遞增有序。struct list *p, *q, *s, *head; p = head; while(

13、p != NULL) if(x > p->data) q = p; p = p->next; else s = (struct list*)malloc(sizeof(struct list); s->data = x; q->next = s; s->next = p; 3 假設有兩個按元素值遞增次序排列的線性表，均以單鏈表形式存儲。請編寫算法將這兩個單鏈表歸并為一個按元素值遞減次序排列的單鏈表，并要求利用原來兩個單鏈表的結點存放歸并后的單鏈表。#include"stdio.h" #include"malloc.h"

14、 struct list int data; struct list *next; ; struct list *head1,*head2,*p1,*p2,*q1,*q2; void main() int n=0; void unionlist(); p1=q1=(struct list*)malloc(sizeof(struct list); printf("請輸入第一個鏈表的信息n"); scanf("%d",&p1->data); while(p1->data!=0) n=n+1; if(n=1) head1=q1; else

15、q1->next=p1; q1=p1; p1=(struct list*)malloc(sizeof(struct list); scanf("%d",&p1->data); q1->next=NULL; n=0; p2=q2=(struct list*)malloc(sizeof(struct list); printf("請輸入第二個鏈表的信息n"); scanf("%d",&p2->data); while(p2->data!=0) n=n+1; if(n=1) head2=q2;

16、else q2->next=p2; q2=p2; p2=(struct list*)malloc(sizeof(struct list); scanf("%d",&p2->data); q2->next=NULL; unionlist(); void unionlist() struct list *head,*p; int i=0; p1=head1; p2=head2; head=p=(struct list*)malloc(sizeof(struct list); p->data=0; while(p1 && p2) i

17、f(p1->data<=p2->data) p->next=p1; p=p1; p1=p1->next; else p->next=p2; p=p2; p2=p2->next; p->next=p1?p1:p2; p=head; printf("合并后的鏈表為如下:n"); while(p) i=i+1; if(i=1) p=p->next; printf("%3d",p->data); p=p->next; printf("n"); free(head1); free

18、(head2); 4 已知遞增有序的兩個單鏈表A，B分別存儲了一個集合。設計算法實現(xiàn)求兩個集合的并集的運算A=AB。/無頭鏈表 /#define data data_int #include "head.h" struct LNode / char data10; int data; struct LNode *next; ; typedef struct LNode * LinkList; void InitList_L(LinkList &L)/鏈表構造函數(shù) L=new LNode; L->next=NULL; void PrintList_L(LinkL

19、ist &H)/鏈表顯示函數(shù) LinkList L=H; L=L->next; while(1) cout<<"data value is "<<L->data<<endl; L=L->next; if (L=NULL) return; void Insert_L(LinkList &H,int n=0)/插入鏈表 LinkList L=H; LinkList p=L; int i=0; if (n=0) n=1; while(p->next!=NULL) p=p->next; n+; els

20、e if (n<1) cout<<"error"<<endl; return; for (i=0;i<n-1;i+) if (L->next=NULL) cout<<"error"<<endl; return; L=L->next; p=new LNode; cout<<"please input a value:" cin>>p->data; p->next=L->next; L->next=p; LinkList bing_LinkList(LinkList a,LinkList b) LinkList c; LinkList nc; LinkList t; InitList_L(c); nc=c; a=a->next; while (a!=NULL)/復制a到c t=new LNode; t->data=a->data; nc->next=t; t-