第2章測試題(1)

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

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

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

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

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

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

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

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

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

11、中，能否從當(dāng)前結(jié)點(diǎn)出發(fā)訪問到任何一個結(jié)點(diǎn)？在單鏈表中不能從任意結(jié)點(diǎn)（若結(jié)點(diǎn)不是第一結(jié)點(diǎn)）出發(fā)訪問到任何一個結(jié)點(diǎn)，鏈表只能從頭指針開始，訪問到鏈表中每個結(jié)點(diǎn)。在雙鏈表中求前驅(qū)和后繼都容易，從任何一個結(jié)點(diǎn)向前到第一結(jié)點(diǎn)，向后到最后結(jié)點(diǎn)，可以訪問到任何一個結(jié)點(diǎn)。6如何通過改鏈表的方法，把一個單向鏈表變成一個與原來鏈接方向相反的單向鏈表？設(shè)該鏈表帶頭結(jié)點(diǎn)，將頭結(jié)點(diǎn)摘下，并將其指針域置空，然后從第一元素節(jié)點(diǎn)開始，直到最后一個結(jié)點(diǎn)為止，依次前插入頭結(jié)點(diǎn)的后面，則實(shí)現(xiàn)了鏈表的逆置五、 算法設(shè)計(jì)題1 已知單鏈表L，寫一個算法，刪除其中的重復(fù)結(jié)點(diǎn)。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插入到遞增有序的順序表的適當(dāng)位置，使插入后的順序表仍為遞增有序。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 假設(shè)有兩個按元素值遞增次序排列的線性表，均以單鏈表形式存儲。請編寫算法將這兩個單鏈表歸并為一個按元素值遞減次序排列的單鏈表，并要求利用原來兩個單鏈表的結(jié)點(diǎn)存放歸并后的單鏈表。#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分別存儲了一個集合。設(shè)計(jì)算法實(shí)現(xiàn)求兩個集合的并集的運(yù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)/鏈表構(gòu)造函數(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)/復(fù)制a到c t=new LNode; t->data=a->data; nc->next=t; t-