數(shù)據(jù)結構課后習題

1、網(wǎng)絡工程2011級1班、計算機科學與技術 2011級2班算法與數(shù)據(jù)結構課后習題(第 2章)【課后習題】第2章線性表2011 級計科(網(wǎng)工)班 學號： 姓名：題號一一三四總分得分一、判斷題(如果正確，在題號前打“寸'，否則打“ X”。每題2分，共10分)()1.線性表若采用順序存儲表示時所有結點之間的存儲單元地址必須連續(xù)。()2.順序表結構適宜于進行順序存取，而鏈表適宜于進行隨機存取。()3.如果某個數(shù)據(jù)結構的每一個元素都是最多只有一個直接前驅，則必為線性結構。()4.線性表的邏輯順序與物理順序總是一致的。()5.線性表的長度是指它所占存儲空間的大小。二、填空題(每空1.5分，共21分)

2、1. 從邏輯結構看，線性表是典型的 。2. 在一個長度為 n的向量中在第i (Ki< n+1)個元素之前插入一個元素時，需向后移動 個元素，算法的時間復雜度為 。3. 在一個長度為n的向量中刪除第i (1 <i< n)個元素時，需向前移動 個元素，算 法的時間復雜度為 。4. 若長度為n的線性表采用鏈式存儲結構，在其第i個結點前插入一個新的元素的算法的時間復雜度為 。刪除其第i個元素的算法的時間復雜度為 。5. 線性表順序存儲結構的優(yōu)點是可以實現(xiàn),主要缺點6. 不帶頭結點的單鏈表 L為空的條件是 ,帶頭結點的單鏈表 L為空的條件是，帶頭結點的單循環(huán)鏈表L為空的條件是 。7.

3、兩指針p和q,分別指向單鏈表的兩個元素，p所指元素是q所指元素的前導的條件8.設雙向循環(huán)鏈表中結點的結構為(data, prior, next)，若指針p指向該鏈表的某個結點，則有下面的關系： p->next->prior= = 。題號12345678910答案題號11121314151617181920答案2分，共40分）三、單項選擇（請將正確答案的代號填寫在下表對應題號下面。每題1.P和Q兩個指針分別指向雙向循環(huán)表 件是L的兩個元素，P所指元素是Q所指元素的后繼的條2.A.P= =QB.Q- > Next=PC.P- > Next=QD.Q- > PRIOR=

4、P指針P指向不帶頭結點的線性鏈表L的首元素的條件是（A.P= =LB.L- > Next=PC.P- > next=LD.P- > next=NULL第6頁共5頁B.L- > Next=P4.C.P- > next=L指針P指向單鏈表A.P= =LC.P- > next=LD.P- > next=NULLL的尾元素的條件是B.L- > Next=PD.P- > next=NULL3.指針p指向帶頭結點的單循環(huán)鏈表L的首元素的條件是（A. P= =L5.指針P所指的元素是雙向循環(huán)鏈表L的尾元素的條件是A.P= =LB.P= =NULLC. P

5、- > next=LD. P- > prior=L6.在一個具有n個結點的有序單鏈表中插入一個新結點，并使插入后仍然有序，則該操作的 時間復雜性量級為（）。A.0(1)B.0(n)C.0(nlog 2n)D.0(n 2)7.順序存儲的線性表（a1,a2, an）,在任一結點前插入一個新結點時所需移動結點的平均次 數(shù)為（）。A.nB.n/2C.n+1D.（n+1）/28.刪除長度為n的順序表的第i（1 < i< n）個位置上的元素，元素的移動次數(shù)為 （）A) i-1B) iC) n-iD) n-i+19. 在C語言中可用（）描述線性表。A、數(shù)組；B、指針；C10. 鏈表不

6、具有的特點是（）A）插入、刪除不需要移動元素C）不必事先估計存儲空間、數(shù)組或指針；D、結構B）可隨機訪問任一元素D）所需空間與線性長度成正比x的后繼”的語句是（11. 在單鏈表中，指針p指向元素為x的結點，實現(xiàn)“刪除A) p=p->next; B)p->next=p; C)p->next=p->next->next; D)p=p->next->next;12. 單鏈表的存儲密度（A）大于1; B）等于1 ;C）不能確定；D）小于113. 非空的循環(huán)單鏈表first 的尾結點（由p所指向）滿足：。A. p-> next = NULL ; B. p

7、= NULL ; C. p-> next = first ; D. p = first14. 下列靜態(tài)鏈表沒有設置空閑指針鏈，則其表示的線性表邏輯結構為（）。01234567,100abcdef,32516410,A、(c, a, b ,e, d, f,)； B、(c, a,b,e,d, f) ； C、(a,b,c, d ,e, f,)；D、(a,b,c, d, e, f)。）。（已知:15. 在下列線性表如下圖所示中將結點P插入到Q結點之前采用的操作是（結點的前驅指針域為pre ,后繼指針域為next ）。圖1A、P->next=Q->next ; P->pre=P-

8、>next->pre ; P->next->pre=P->pre ; P->pre->next=P ;B、P->next=Q ; P->next->pre=P->pre ; P->pre->next=P ; P->pre=P->next->pre ;C、P->pre=P->next->pre ; P->next->pre=P->pre ; P->pre->next=P ; P->next=Q ;D、P->next=Q ; P->pre

9、=P->next->pre ; P->next->pre=P ; P->pre->next=P。16.設雙向循環(huán)鏈表中結點的結構為( data, prior, next )，且不帶表頭結點。若想在指針p所指結點之后插入指針s所指結點，則應執(zhí)行下列哪一個操作？A) p->next = s; s->prior = p; p->next->prior = s; s->next = p->next;B) p->next = s; p->next->prior = s; s->prior = p; s->

10、;next = p->next;C) s->prior = p; s->next = p->next; p->next = s; p->next->prior = s;D) s->prior = p; s->next = p->next; p->next->prior = s; p->next = s;17. 下列說法正確的是（）。A. 線性表的邏輯順序與存儲順序總是一致的B. 線性表的鏈式存儲結構中，要求內(nèi)存中可用的存儲單元可以是連續(xù)的，也可以不連續(xù)C. 線性表的順序存儲結構優(yōu)于鏈式存儲結構D. 每種數(shù)據(jù)結構都具有

11、插入、刪除和查找三種基本運算18. 關于線性結構的特性描述不恰當是（）。A、有唯一個被稱作“第一個”的數(shù)據(jù)元素；B、有唯一個被稱作"最后一個”的數(shù)據(jù)元素；C、除最后一個之外，線性表中每個數(shù)據(jù)元素都有后繼；D、棧、隊列、串和數(shù)組也屬于線性表。19.線性表（4*2,，an,an）中任一元素ai（i =0,1,2、，n）在（ ）中存儲位置為L0C（a1）+（i）*l,其中LOC（aJ表示元素 a1的存儲首地址，l為每一個元素占用的存儲單元數(shù)。A、線性表邏輯結構；B、線性表存儲結構；C、線性表鏈式存儲結構；D、線性表順序存儲結構。20.設雙鏈表中結點的前趨指針和后繼指針的域名分別為t1和r1

12、 ,則刪除雙鏈表中指針s所指結點的操作為（）。A.s- > tl- >r1=s-> tl;s-> rl- > tl=s- > rl;free(s);B.s- > tl- >rl=s-> rl;s-> rl- > tl=s- > tl;free(s);C.s- > rl=s-> tl-> rl;s-> tl=s- > rl- > tl;free(s);D.s- > tl=s-> tl-> rl;s-> rl=s- > rl- > tlfree(s);四、

13、算法分析與設計（請將答案填在下表對應位置。共 29分）第1題（7分）第2題（8分）第3題（8分）第4題（6分）；1、已知無頭結點的單鏈表L,簡述下列對L鏈表操作算法的功能。LinkList Demo(LinkList L) / L是無頭結點單鏈表ListNode *Q,*P;if(L&&L->next)Q=L; L=L->next; P=L;while (P->next) P=P->next;P->next=Q; Q->next=NULL;return L;/ Demo2、已知線性表的帶頭結點雙向循環(huán)鏈表存儲結構如下所示:typedef st

14、ruct DuLNodeElemType data; struct DuLNode *prior; Struct DuLNode *next;DuLNode , *DuLinkList ;請完成在帶頭結點的雙向循環(huán)鏈表L中第i個位置之前插入元素e (K i v表長+1)算法:status ListInsert_DuL(DuLinkList&L , int I; ElemType e)(P=L ; j=0 ；while(p<>p->next)&&(j<i-1)p=p->next ; j+ ; if(p= =L)&&(i<

15、>1)|(j>i-1) return ERROR ;p=p->next;if(!(s=(DuLinkList)malloc(sizeof(DuLNode) rerurn ERROR ; = p ;s->prior=p->prior ; return OK ;/ListInsert_DuL3、設順序表L是一個遞增有序表，試寫一算法，將 x插入L中，并使L仍是一個有序表。void InsertIncreaseList( Seqlist *L , Datatype x ) int i;if ( L->length>=ListSize)Error( “over

16、flow");for ( i=L -> length ; i>0 && L->data i ; i-)L->data i+1 = ® /比較并移動元素=x;4、有一個不帶頭結點的單鏈表，其頭指針為 統(tǒng)計數(shù)據(jù)域的值為x的結點個數(shù)。int countx ( LinkList head, ElemType x)LinkList p; int n=0;while (p!=NULL) if (p->data= =x)head,其結點的數(shù)據(jù)域值可能相同，編寫一個函數(shù) return(n);網(wǎng)絡工程2011級1班、計科2011級2班算法與數(shù)據(jù)結

17、構課后習題(第 2章)參考答案【課后習題】第2章 線性表（參考答案）2014-10-16第8頁、判斷題（如果正確，在題號前打“ 否則打“ X”。每題2分，共10分）1.2. X3. X 4. X 5. X、填空題（每空 1.5分，共21分）1. 從邏輯結構看，線性表是典型的線性結構。2. 在一個長度為n的向量中在第i （K i< n+1）個元素之前插入一個元素時，需向后移動n-i+1個元素，算法的時間復雜度為O（n） 。3. 在一個長度為n的向量中刪除第i （1 <i < n）個元素時，需向前移動n-i個元素,算法的時間復雜度為O（n）。4.若長度為n的線性表采用鏈式存儲結構

18、，在其第 i個結點前插入一個新的元素的算法的時 間復雜度為 O（n）。刪除其第i個元素的算法的時間復雜度為O（n）。5.線性表順序存儲結構的優(yōu)點是可以實現(xiàn)隨機存取，主要缺點是：不利于插入或刪除操作。6.不帶頭結點的單鏈表L為空的條件是_L=NULL_ ，帶頭結點的單鏈表L為空的條件是L->next=NULL，帶頭結點的單循環(huán)鏈表L為空的條件是 L->next=L 。7. 兩指針p和q,分別指向單鏈表的兩個元素，p所指元素是q所指元素的前導的條件是止> next=q 。8. 設雙向循環(huán)鏈表中結點的結構為（ data, prior, next），若指針p指向該鏈表的某個結點，則有

19、下面的關系:p->next->prior= = p （或 p->prior->next ）。、單項選擇（請將正確答案的代號填寫在下表對應題號下面。每題 2分，共40分）題號12345678910答案BABDCBBCCB題號11121314151617181920答案CDCADDBCDB四、算法分析與設計（請將答案填在下表對應位置。共 29分）第1題（7分）將第一個結點摘卜鏈接到終端結點之后成為新的終端結點，而原來的第二個結點 成為新的開始結點，返回新鏈表的頭指針第2題（8分） s->data=e s->next p->prior->next=s

20、p->prior=s第3題（8分）>x L->datai L->datai+1 L->length+第4題（6分） p=head; n+; p=p->next;【課后習題】第2章 線性表（參考答案）、判斷題（如果正確，在題號前打“寸，否則打“ X”。每題2分，共10分）寸1.線性表若采用順序存儲表示時所有結點之間的存儲單元地址必須連續(xù)。x 2.順序表結構適宜于進行順序存取，而鏈表適宜于進行隨機存取。x 3.如果某個數(shù)據(jù)結構的每一個元素都是最多只有一個直接前驅，則必為線性結構。x 4.線性表的邏輯順序與物理順序總是一致的。x 5.線性表的長度是指它所占存儲空間

21、的大小。、填空題（每空 2分，共18分）1. 從邏輯結構看，線性表是典型的線性結構。2. 在一個長度為n的向量中在第i （K i< n+1）個元素之前插入一個元素時，需向后移動n-i+1個元素，算法的時間復雜度為O（n） 。3. 在一個長度為n的向量中刪除第i （1 <i < n）個元素時，需向前移動n-i個元素,算法的時間復雜度為O（n）。4. 若長度為n的線性表采用鏈式存儲結構，在其第 i個結點前插入一個新的元素的算法的時間復雜度為O（n）。刪除其第i個元素的算法的時間復雜度為O（n）。5. 線性表順序存儲結構的優(yōu)點是可以實現(xiàn)隨機存取 ，主要缺點是：不利于插入或刪除操作

22、。6. 不帶頭結點的單鏈表L為空的條件是 L=NULL ,帶頭結點的單鏈表 L為空的條件是L->next=NULL，帶頭結點的單循環(huán)鏈表L為空的條件是L->next=L 。7. 兩指針p和q,分別指向單鏈表的兩個元素，p所指元素是q所指元素的前導的條件是p- > next=q 。8. 設雙向循環(huán)鏈表中結點的結構為（ data, prior, next），若指針p指向該鏈表的某個結點，則有下面的關系:p->next->prior= = p （或 p->prior->next ）。:、單項選擇（請將正確答案的代號填寫在下表對應題號下面。每題 2分，共40分

23、）1. P和Q兩個指針分別指向雙向循環(huán)表L的兩個元素，P所指元素是Q所指元素的后繼的條件是（）。A. P= =QB.Q- > Next=P C.P-> Next=Q D.Q- > PRIOR=P2. 指針P指向不帶頭結點的線性鏈表L的首元素的條件是（）。A.P= =LB.L-> Next=PC.P- > next=LD.P-> next=NULL3. 指針p指向帶頭結點的單循環(huán)鏈表L的首元素的條件是（）。A.P= =LB.L-> Next=PC.P- > next=LD.P-> next=NULL4. 指針P指向單鏈表L的尾元素的條件是（）

24、。網(wǎng)絡工程2011級1班、計科2011級2班算法與數(shù)據(jù)結構課后習題（第 2章）參考答案5.6.7.8.9.10.11.12.13.14.A、A.P= =LC.P- > next=LB.L- > Next=PD.P- > next=NULL指針P所指的元素是雙向循環(huán)鏈表L的尾元素的條件是A.P= =LB.P= =NULLC. P- > next=L)。D. P- > prior=L在一個具有n個結點的有序單鏈表中插入一個新結點，并使插入后仍然有序，則該操作的時 間復雜性量級為（）。A.0(1)B.0(n)C.0(nlog 2n)D.0(n 2)順序存儲的線性表（a1

25、,a2, an），在任一結點前插入一個新結點時所需移動結點的平均次數(shù)為（ ）。A.n刪除長度為A） i-1B.n/2C.n+1D.(n+1)/2n的順序表的第i（1 < i < n）個位置上的元素，元素的移動次數(shù)為（）B） i在C語言中可用（A、數(shù)組；B、指針;C) n-iD) n-i+1）描述線性表。C、數(shù)組或指針;D、結構鏈表不具有的特點是（A）插入、刪除不需要移動元素C）不必事先估計存儲空間B）可隨機訪問任兀系D）所需空間與線性長度成正比在單鏈表中，指針p指向元素為x的結點，實現(xiàn)“刪除 xA）p=p->next; B）p->next=p;C)p->next=

26、p->next->next;的后繼”的語句是（）D）p=p->next->next;單鏈表的存儲密度（A）大于1 ; B）等于非空的循環(huán)單鏈表 firstA. p-> next = NULL ;)1；C）不能確定;D）小于1的尾結點（由p所指向）滿足：B. p = NULL ; C. p-> next = first卜列靜態(tài)鏈表沒有設置空閑指針鏈，則其表示的線性表邏輯結構為（D. p = first ;01234567,100abcdef,32516410,(c, a, b ,e, d, f,)； B、(c, a, b,e,d, f) ； C、(a,b,c,

27、 d,e, f,)；D、(a,b,c,d,e,15.在下列線性表如圖1所示中將結點P插入到Q結點之前采用的操作是（ 的前驅指針域為 pre，后繼指針域為next ）。）。（已知：結點第3頁P 2014-10-16網(wǎng)絡工程2011級1班、計科2011級2班算法與數(shù)據(jù)結構課后習題(第 2章)參考答案A、P->next=Q->next ; P->pre=P->next->pre ; P->next->pre=P->pre ; P->pre->next=P ;B、P->next=Q ; P->next->pre=P->

28、pre ; P->pre->next=P ; P->pre=P->next->pre ;C、P->pre=P->next->pre ; P->next->pre=P->pre ; P->pre->next=P ; P->next=Q ;D、P->next=Q ; P->pre=P->next->pre ; P->next->pre=P ; P->pre->next=P。16.設雙向循環(huán)鏈表中結點的結構為( data, prior, next )，且不帶表頭結點。若

29、想在指針p所指結點之后插入指針s所指結點，則應執(zhí)行下列哪一個操作？A) p->next =s;s->prior= p; p->next->prior =s;s->next = p->next;B) p->next =s;p->next->prior = s;s->prior =p;s->next = p->next;C) s->prior =p;s->next= p->next;p->next =s;p->next->prior = s;D) s->prior =p;s->n

30、ext= p->next;p->next->prior = s; p->next = s;17. 下列說法正確的是（）。A. 線性表的邏輯順序與存儲順序總是一致的B. 線性表的鏈式存儲結構中，要求內(nèi)存中可用的存儲單元可以是連續(xù)的，也可以不連續(xù)C. 線性表的順序存儲結構優(yōu)于鏈式存儲結構D. 每種數(shù)據(jù)結構都具有插入、刪除和查找三種基本運算18. 關于線性結構的特性描述不恰當是（）。A、有唯一個被稱作“第一個”的數(shù)據(jù)元素；B、有唯一個被稱作"最后一個”的數(shù)據(jù)元素；C、除最后一個之外，線性表中每個數(shù)據(jù)元素都有后繼;D、棧、隊列、串和數(shù)組也屬于線性表。19. 線性表（a

31、，a2,，ana,an）中任一元素a（i =0,1,2" ,n）在（）中存儲位置為LOC（a（1）*l?其中 LOC（q） 表示元素a的存儲首地址，l為每一個元素占用的存儲單元數(shù)。A、線性表邏輯結構；B、線性表存儲結構；C、線性表鏈式存儲結構；D、線性表順序存儲結構。20. 設雙鏈表中結點的前趨指針和后繼指針的域名分別為t1和r1,則刪除雙鏈表中指針 s所指結點的操作為（）。A.s- > tl- > r1=s- > tl;s-> rl- > tl=s- > rl;free(s);B.s- > tl- > rl=s- > rl;s-

32、 > rl- > tl=s- > tl;free(s);C.s- > rl=s- > tl- > rl;s- > tl=s- > rl- > tl;free(s);D.s- > tl=s- > tl- > rl;s- > rl=s- > rl- > tlfree(s);四、算法分析與設計（請將答案填在下表對應位置。共 29分）第1題（7分）將第一個結點摘卜鏈接到終端結點之后成為新的終端結點，而原來的第二個結點成為新的開始結點，返回新鏈表的頭指針第2題（8分） s->data=e s->next=p p->prior->next=s p->prior=s第3題（8分） >x L->datai L->datai+1 L->length+第4題（6分） p=head; n+; p=p->next;1、已知無表頭的單鏈表L,簡述下列對L鏈表操作算法的功能。LinkList Demo(LinkList L)( / L是無頭結點單鏈表ListNode *Q,*P;if(L&&L->next)Q=L; L=L->next; P=L;while (P->nex