數(shù)據(jù)結(jié)構(gòu)習題參考答案殷人昆版

1、數(shù)據(jù)結(jié)構(gòu)第二章習題參考答案、判斷題(在正確說法的題后括號中打，錯誤說法的題后括號中打“X”1、順序存儲方式插入和刪除時效率太低，因此它不如鏈式存儲方式好。(X)2、鏈表中的頭結(jié)點僅起到標識的作用。(X)3、所謂靜態(tài)鏈表就是一直不發(fā)生變化的鏈表。(x)4、線性表的特點是每個元素都有一個前驅(qū)和一個后繼。(x)5、在順序表中，邏輯上相鄰的元素在物理位置上不一定相鄰。(X)6、線性表就是順序存儲的表。(x)7、課本P842.4題(1)，(2)義(3)義(4)義(5)，(6)義(7)義(8)V(9)X(10)X(11)V(12)V二、單項選擇題1、下面關(guān)于線性表的敘述中，錯誤的是哪一個？(B)A.線性表

2、采用順序存儲，必須占用一片連續(xù)的存儲單元。B.線性表采用順序存儲，便于進行插入和刪除操作。C.線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D.線性表采用鏈接存儲，便于插入和刪除操作。2、鏈表不具有的特點是(B)A.插入、刪除不需要移動元素B.可隨機訪問任一元素C.不必事先估計存儲空間D.所需空間與線性長度成正比3、(1)靜態(tài)鏈表既有順序存儲的優(yōu)點，又有動態(tài)鏈表的優(yōu)點。所以，它存取表中第i個元素的時間與i無關(guān)。(2)靜態(tài)鏈表中能容納的元素個數(shù)的最大數(shù)在表定義時就確定了，以后不能增加。(3)靜態(tài)鏈表與動態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動。以上錯誤的是(B)A.(1),(2)B.(

3、1)C.(1),(2),(3)D.(2)4、在單鏈表指針為p的結(jié)點之后插入指針為s的結(jié)點，正確的操作是(B)A.p-link=s;s-link=p-link;B.s-link=p-link;p-link=s;C.p-link=s;p-link=s-link;D.p-link=s-link;p-link=s;5、若某線性表最常用的操作是取任一指定序號的元素及其前驅(qū)，則利用(C)存儲方式最節(jié)省時間。A.單鏈表B,雙鏈表C.順序表D.帶頭結(jié)點的雙循環(huán)鏈表6、對于順序存儲的線性表，訪問結(jié)點和增加、刪除結(jié)點的時間復雜度為(C)。A.O(n),O(n)B.O(n),O(1)C.O(1),O(n)D.O(1

4、),O(1)7、在一個以h為頭的單循環(huán)鏈中，p指針指向鏈尾的條件是(A)A.p-next=hB.p-next=NULLC.p-next-next=hD.p-data=-1三、填空題1、當線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應采用順序.存儲結(jié)構(gòu)。2、線性表L=(a1,a2,an)用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數(shù)是一(n-1)/2。3、在單鏈表中設(shè)置頭結(jié)點的作用是可以使鏈表的操作統(tǒng)一、編程簡潔。4、一個頭指針為head的帶頭結(jié)點的單鏈表為空表的條件是：head-link=NULLq5.在一個長度

5、為n的順序表中第i個元素(1=i=n)之前插入一個元素時，需向后移動n-i+1個元素。6、對于一個具有n個結(jié)點的單鏈表，在已知的結(jié)點*p后插入一個新結(jié)點的時間復雜度為O(1).，在給定值為x的結(jié)點后插入一個新結(jié)點的時間復雜度為O(n)四、綜合題1、線性表可用順序表或鏈表存儲。問：(1)兩種存儲表示各有哪些主要優(yōu)缺點？(2)如果要求對n個表長動態(tài)變化的表進行處理，表的總數(shù)可能也發(fā)生改變，在此情況下，應選用哪種存儲表示？為什么？參考解答：(1)順序存儲時，邏輯上相鄰的數(shù)據(jù)元素，其物理存放地址也相鄰。順序存儲的優(yōu)點是存儲密度大，存儲空間利用率高，可實現(xiàn)隨機存??；缺點是插入或刪除元素時不方便。鏈式存儲

6、時，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針。鏈式存儲的優(yōu)點是插入或刪除元素時很方便，使用靈活；缺點是存儲密度小，存儲空間利用率低，只能順序存取。宜選用鏈式存儲結(jié)構(gòu)，有利于高效進行動態(tài)內(nèi)存開辟和插入、刪除操作。2、試述頭結(jié)點，首元結(jié)點，頭指針這三個概念的區(qū)別。參考解答：在線性表的鏈式存儲結(jié)構(gòu)中，頭指針指鏈表的指針，若鏈表有頭結(jié)點則是鏈表的頭結(jié)點的指針，頭指針具有標識作用，故常用頭指針冠以鏈表的名字。頭結(jié)點是為了操作的統(tǒng)一、方便而設(shè)立的，放在第一元素結(jié)點之前，其數(shù)據(jù)域一般無意義(也可存放鏈表的長度、用做監(jiān)視哨等)，有頭結(jié)點后，對在第一元素

7、結(jié)點前插入結(jié)點和刪除第一結(jié)點，其操作與對其它結(jié)點的操作統(tǒng)一了。而且無論鏈表是否為空，頭指針均不為空。首元結(jié)點也就是第一元素結(jié)點，它是頭結(jié)點后邊的第一個結(jié)點。3、課本P832.3題參考解答：64,634、課本P852.10題參考解答：(1)刪除最小元素并返回其值X,空出最小元素的位置用最后一個元素填補voidSeqList:DelMin(T&x)if(IsEmpty()cerr表為空！endl;exit;intlen=Length();Ttemp,val;GetData(1,temp);for(inti=1;i=len;i+)GetData(i,val);if(valtemp)temp=val;

8、x=temp;intpos=Search(temp);GetData(len,val);SetData(pos,val);Remove(len,val);其他解答略5、課本P852.14題參考解答：(1)templateLinkNode*List二Locate(inti)返回第i個元素的地址if(iLength()returnNULL;/i不合理，返回空指針LinkNode*p=first-link;intk=1;while(p!=NULL&klink;k+;returnp;(4)templatevoidList:Create(T*a,intn)LinkNode*p=first;for(int

9、i=0;ilink=newLinkNode(ai);elsep-link=newLinkNode(ai);p=p-link;(5)templatevoidList:tidyup()LinkNode*p=first-link,*q;while(p-link!=NULL)if(p-data!=p-link-data)p=p-link;elseq=p-link;p-link=q-link;deleteq;其他解答略6、課本P862.17題參考解答：voidInverseList(ListNode*h)ListNode*pr=NULL,*p=h-link;while(p!=NULL)h-link=pr;pr=h;h=p;p=p-link;7、課本P