第2章測試題(1)

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

2、B.順序表C.有序順序表D.上述三項(xiàng)無法比較3 .若希望從鏈表中快速確定一個(gè)結(jié)點(diǎn)的前驅(qū)，則鏈表最好采用（雙鏈表在結(jié)點(diǎn)前驅(qū)后繼查找上的時(shí)間復(fù)雜度是O（1）A.單鏈表B,循環(huán)單鏈表C.雙向鏈表 D.任意4 .在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行（c）方式。d)。p->next指向p指針的后繼結(jié)點(diǎn)，p->next->next 指向后繼結(jié)點(diǎn)的后繼結(jié)點(diǎn)。A.C.p->next=p->nextp=p->next;p->next=p->next->next;B. p=p->next->nextD. p->next=p-&g

3、t;next->next5.A.C.6.A.B.C.D.帶頭結(jié)點(diǎn)的單鏈表head=NULLhead->next=head在循環(huán)雙向鏈表的7.head為空的判定條件是（b ）。B. head->next=NULLD. head!=NULLp所指結(jié)點(diǎn)之后插入 s所指結(jié)點(diǎn)的操作是（d）op->next=s;s->prior=p;p->next->prior=s;s->next=p->next;p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;s->

4、prior=p;s->next=p->next;p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;若某線性表最常用的操作是存取任一指定序號的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（a）存儲方式最節(jié)省時(shí)間。想要存取任一指定序號的元素，鏈表實(shí)現(xiàn)這個(gè)功能的代價(jià)很大所有順本來順序表的弱點(diǎn)在于插入和刪除元素，但是題目要求只最后進(jìn)行插入和刪除運(yùn)算,序表是最好的選擇！A.順序表B,雙向鏈表二、填空題C.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D.單循環(huán)

5、鏈表1 .對于采用順序存儲結(jié)構(gòu)的線性表，當(dāng)隨機(jī)插入或刪除一個(gè)數(shù)據(jù)元素時(shí)，平均約需移動表 中一半元素。鏈?zhǔn)酱鎯Y(jié)構(gòu)為宜。2 .當(dāng)對一個(gè)線性表經(jīng)常進(jìn)行的是插入和刪除操作時(shí)，采用因?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)對一個(gè)線性表經(jīng)常進(jìn)行的是存取操作，而很少進(jìn)行插入和刪除操作時(shí)，最好采用順序存儲結(jié)構(gòu)。它的特點(diǎn)是邏輯關(guān)系上相鄰的兩個(gè)元素在物理位置上也相鄰，因此可以隨機(jī)存取表中任一元素，它的存儲位置可用一個(gè)簡單，直觀的公式來表示4 .在一個(gè)長度為n的順序存儲結(jié)構(gòu)的線性表中，向第 i個(gè)元素（

6、1三i三n+1）之前插入一個(gè) 新兀素時(shí)，需向后移動 n-i+1個(gè)兀素。這道題，可以進(jìn)行舉例來驗(yàn)證，比如要是在第一個(gè)元素前插入元素，需要移動n個(gè)元素。i=1時(shí)，需要移動n個(gè)，進(jìn)行驗(yàn)證5 .從長度是n的采用順序存儲結(jié)構(gòu)的線性表中刪除第i個(gè)元素（1三i Wn）,需向前移動n-i個(gè)元素。6 .對于長度是n的順序存儲結(jié)構(gòu)的線性表， 插入或刪除元素的時(shí)間復(fù)雜度為0 （n）7 .在具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜度是0 （n）。因?yàn)閱捂湵肀４娴男畔⒅挥斜眍^如果要在特定位置插入一個(gè)節(jié)點(diǎn)需要先從表頭一路找到那個(gè)節(jié)點(diǎn)這個(gè)過程是O（n）的8 .在雙向鏈表中，每個(gè)結(jié)點(diǎn)共有兩個(gè)指針域，一個(gè)指

7、向 前驅(qū) 結(jié)點(diǎn)，另一個(gè)則指向后繼結(jié)點(diǎn)。三、判斷題1 .鏈表中的頭結(jié)點(diǎn)僅起到標(biāo)識的作用。（f）頭結(jié)點(diǎn)的數(shù)據(jù)域還可以存儲一些必要的數(shù)據(jù)，如表長。2 .順序存儲結(jié)構(gòu)的主要缺點(diǎn)是不利于插入和刪除操作。（t ）3 .線性表采用鏈表存儲時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲空間可以是不連續(xù)的。（f）結(jié)點(diǎn)內(nèi)部空間是連續(xù)的。4 .順序存儲方式插入和刪除時(shí)效率太低，因此它不如鏈?zhǔn)酱鎯Ψ绞胶谩＃╢）還有其他比較參數(shù)。如空間利用率，難易程度，存取快捷等。5 .對任何數(shù)據(jù)結(jié)構(gòu)鏈表存儲結(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。（f）還有其他比較參數(shù)。如空間利用率，難易程度，存取快捷等。6 .順序存儲方式只能用于存儲線性結(jié)構(gòu)。（f ）也可用于樹、二叉

8、樹等7 .循環(huán)鏈表不是線性表。（f）8 .為了很方便地插入和刪除數(shù)據(jù)，可以使用雙向鏈表存放數(shù)據(jù)。（t ）9 .線性表的特點(diǎn)是每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼。（f ）第一個(gè)結(jié)點(diǎn)無前驅(qū)，最后一個(gè)結(jié)點(diǎn)無后繼。10 .取線性表的第i個(gè)元素的時(shí)間與i的大小有關(guān)。（f）看線性表的存儲機(jī)構(gòu)，鏈表有關(guān)，順序表無關(guān)。四、應(yīng)用題1 .線性表有兩種存儲結(jié)構(gòu)：一是順序表，二是鏈?zhǔn)奖怼Ｔ噯枺喝绻衝個(gè)線性表同時(shí)并存， 并且在處理過程中各表的長度會動態(tài)變化，線性表的總數(shù)也會自動地改變。在此情況下，應(yīng)選用哪種存儲結(jié)構(gòu)為什么鏈表，理由是鏈表能夠高效的執(zhí)行插入刪除操作，適用于元素變化較多的情形若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行

9、插入和刪除， 但要求以最快的速度存取線性表中的元素，那么應(yīng)采用哪種存儲結(jié)構(gòu)為什么順序存儲結(jié)構(gòu)。順序表可以隨機(jī)存取，時(shí)間復(fù)雜度為O (1)2 .線性表的順序存儲結(jié)構(gòu)具有三個(gè)弱點(diǎn)：其一，在進(jìn)行插入或刪除操作時(shí)，需移動大量元素；其二，由于難以估計(jì)，必須預(yù)先分配較大的空間，往往使存儲空間不能得到充分的利用。線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是否一定都能克服以上缺點(diǎn)，試討論之。鏈?zhǔn)酱鎯Y(jié)構(gòu)一般說克服了順序存儲結(jié)構(gòu)的三個(gè)弱點(diǎn)。首先，插入、刪除不需移動元素，只修改指針，時(shí)間復(fù)雜度為0(1);其次，不需要預(yù)先分配空間，可根據(jù)需要動態(tài)申請空間；其三，表容量只受可用內(nèi)存空間的限制。其缺點(diǎn)是因?yàn)橹羔樤黾恿丝臻g開銷，當(dāng)空間不允許時(shí)

10、，就不能克服順序存儲的缺點(diǎn)。3 .線性表(ai, a2,，an)用順序映射表示時(shí)，ai和ai+i (1<=i<n)的物理位置相鄰嗎鏈 接表示時(shí)呢順序映射時(shí)，ai與ai+1的物理位置相鄰；鏈表表示時(shí)ai與ai+1的物理位置不要求相鄰。4 .試述頭結(jié)點(diǎn)，首元結(jié)點(diǎn)，頭指針這三個(gè)概念的區(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)

11、和刪除第一結(jié)點(diǎn)，其 操作與對其它結(jié)點(diǎn)的操作統(tǒng)一了。而且無論鏈表是否為空，頭指針均不為空。首元結(jié)點(diǎn)也就是第一元素結(jié)點(diǎn)，它是頭結(jié)點(diǎn)后邊的第一個(gè)結(jié)點(diǎn)。5 .在單鏈表和雙向鏈表中，能否從當(dāng)前結(jié)點(diǎn)出發(fā)訪問到任何一個(gè)結(jié)點(diǎn)在單鏈表中不能從任意結(jié)點(diǎn)(若結(jié)點(diǎn)不是第一結(jié)點(diǎn))出發(fā)訪問到任何一個(gè)結(jié)點(diǎn)，鏈表只能從 頭指針開始，訪問到鏈表中每個(gè)結(jié)點(diǎn)。 在雙鏈表中求前驅(qū)和后繼都容易， 從任何一個(gè)結(jié)點(diǎn)向 前到第一結(jié)點(diǎn)，向后到最后結(jié)點(diǎn)，可以訪問到任何一個(gè)結(jié)點(diǎn)。6 .如何通過改鏈表的方法，把一個(gè)單向鏈表變成一個(gè)與原來鏈接方向相反的單向鏈表設(shè)該鏈表帶頭結(jié)點(diǎn)，將頭結(jié)點(diǎn)摘下，并將其指針域置空，然后從第一元素節(jié)點(diǎn)開始，直到最后一個(gè)結(jié)點(diǎn)為

12、止，依次前插入頭結(jié)點(diǎn)的后面，則實(shí)現(xiàn)了鏈表的逆置五、算法設(shè)計(jì)題1 .已知單鏈表L,寫一個(gè)算法，刪除其中的重復(fù)結(jié)點(diǎn)。void delete(LinkList &L)LinkNode *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)位置，使插入后的順序表仍為遞增

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

14、;"#include""struct listint 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("請輸入第一個(gè) 鏈表的信息n");scanf("%d",&p1->data);while(p1->data!=0)n=n+1;if(n=1)hea

15、d1=q1;elseq1->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("請輸入第二個(gè)鏈表的信息n");scanf("%d",&p2->data);while(p2->data!=0)n=n+1;if(n=1)head2=q2;els

16、eq2->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)if(p1->data<=p2->data)p->next=p1;p=p1；p1=p1->next;elsep->next=p2;p=p2；p2=p2->next;p->next=p1p1: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(headl);free(head2);4