1、第1章緒論課后習題講解1.填空是數據的根本單位,在計算機程序中通常作為一個整體進行考慮和處理.【解答】數據元素是數據的最小單位,是討論數據結構時涉及的最小數據單位.【解答】數據項,數據元素【分析】數據結構指的是數據元素以及數據元素之間的關系.從邏輯關系上講,數據結構主要分為、和【解答】集合,線性結構,樹結構,圖結構數據的存儲結構主要有和兩種根本方法,不管哪種存儲結構,都要存儲兩方面的內容：和.【解答】順序存儲結構,鏈接存儲結構,數據元素,數據元素之間的關系算法具有五個特性,分別是、.【解答】有零個或多個輸入,有一個或多個輸出,有窮性,確定性,可行性算法的描述方法通常有、和四種,其中,被稱為算法

2、語言.【解答】自然語言,程序設計語言,流程圖,偽代碼,偽代碼在一般情況下,一個算法的時間復雜度是的函數.【解答】問題規模設待處理問題的規模為n,假設一個算法的時間復雜度為一個常數,那么表示成數量級的形式為,假設為n*10g25n,那么表示成數量級的形式為.【解答】01,On1og2n【分析】用大O記號表示算法的時間復雜度,需要將低次幕去掉,將最高次幕的系數去掉.2.選擇題順序存儲結構中數據元素之間的邏輯關系是由表示的,鏈接存儲結構中的數據元素之間的邏輯關系是由表示的.A線性結構B非線性結構C存儲位置D指針【解答】C,D【分析】順序存儲結構就是用一維數組存儲數據結構中的數據元素,其邏輯關系由存儲

3、位置即元素在數組中的下標表示；鏈接存儲結構中一個數據元素對應鏈表中的一個結點,元素之間的邏輯關系由結點中的指針表示.假設有如下遺產繼承規那么：丈夫和妻子可以相互繼承遺產；子女可以繼承父親或母親的遺產； 子女間不能相互繼承.那么表示該遺產繼承關系的最適宜的數據結構應該是.A樹B圖C線性表D集合【解答】B【分析】將丈夫、妻子和子女分別作為數據元素,根據題意畫出邏輯結構圖.算法指的是.A對特定問題求解步驟的一種描述,是指令的有限序列.B計算機程序C解決問題的計算方法D數據處理【解答】A【分析】計算機程序是對算法的具體實現；簡單地說,算法是解決問題的方法；數據處理是通過算法完成的.所以,只有A是算法的

4、準確定義.下面不是算法所必須具備的特性.A有窮性B確切性C高效性D可行性【解答】C【分析】高效性是好算法應具備的特性.算法分析的目的是,算法分析的兩個主要方面是.A找出數據結構的合理性B研究算法中輸入和輸出的關系C分析算法的效率以求改良D分析算法的易讀性和文檔性E空間性能和時間性能F正確性和簡明性G可讀性和文檔性H數據復雜性和程序復雜性【解答】C,E3.判斷題算法的時間復雜度都要通過算法中的根本語句的執行次數來確定.【解答】錯.時間復雜度要通過算法中根本語句執行次數的數量級來確定.每種數據結構都具備三個根本操作：插入、刪除和查找.【解答】 錯.如數組就沒有插入和刪除操作.此題注意是每種數據結構

5、.所謂數據的邏輯結構指的是數據之間的邏輯關系.【解答】錯.是數據之間的邏輯關系的整體.邏輯結構與數據元素本身的內容和形式無關.【解答】對.因此邏輯結構是數據組織的主要方面.基于某種邏輯結構之上的根本操作,其實現是唯一的.【解答】 錯.根本操作的實現是基于某種存儲結構設計的,因而不是唯一的4 .分析以下各程序段,并用大O記號表示其執行時間.【解答】(1)根本語句是k=k+10*i,共執行了n-2次,所以T(n)=O(n)根本語句是k=k+10*i,共執行了n次,所以T(n)=O(n)分析條件語句,每循環一次,i+j整體加1,共循環n次,所以T(n)=O(n).設循環體共執行T(n)次,每循環一次

6、,循環變量y加1,最終T(n)=y,即：(T(n)+1)2next=p-next-next單鏈表中設置頭結點的作用是.【解答】為了運算方便【分析】例如在插入和刪除操作時不必對表頭的情況進行特殊處理.非空的單循環鏈表由頭指針head指示,那么其尾結點由指針p所指滿足.【解答】p-next=head【分析】如圖2-8所示.在由尾指針rear指示的單循環鏈表中,在表尾插入一個結點s的操作序列是；刪除開始結點的操作序列為.【解答】s-next=rear-next;rear-next=s;rear=s;q=rear-next-next;rear-next-next=q-next;deleteq;【分析】

7、操作示意圖如圖2-9所示：一個具有n個結點的單鏈表,在指針p所指結點后插入一個新結點的時間復雜度為；在給定值為x的結點后插入一個新結點的時間復雜度為I.【解答】01,0n【分析】在p所指結點后插入一個新結點只需修改指針,所以時間復雜度為01;而在給定值為x的結點后插入一個新結點需要先查找值為x的結點,所以時間復雜度為0n0可由一個尾指針唯一確定的鏈表有、.【解答】循環鏈表,循環雙鏈表,雙鏈表9 .選擇題線性表的順序存儲結構是一種的存儲結構,線性表的鏈接存儲結構是一種的存儲結構.A隨機存取B順序存取C索引存取D散列存取【解答】A,B【分析】參見2.2.10線性表采用鏈接存儲時,其地址.A必須是連

8、續的B局部地址必須是連續的C一定是不連續的D連續與否均可以【解答】D【分析】 線性表的鏈接存儲是用一組任意的存儲單元存儲線性表的數據元素,這組存儲單元可以連續,也可以不連續,甚至可以零散分布在內存中任意位置.單循環鏈表的主要優點是A不再需要頭指針了B從表中任一結點出發都能掃描到整個鏈表；C某個結點的位置后,能夠容易找到它的直接前趨；D在進行插入、刪除操作時,能更好地保證鏈表不斷開.【解答】B鏈表不具有的特點是.A可隨機訪問任一元素B插入、刪除不需要移動元素C不必事先估計存儲空間D所需空間與線性表長度成正比【解答】A假設某線性表中最常用的操作是取第i個元素和找第i個元素的前趨,那么采用存儲方法最

9、節省時間.A順序表B單鏈表C雙鏈表D單循環鏈表【解答】A【分析】 線性表中最常用的操作是取第i個元素,所以,應選擇隨機存取結構即順序表,同時在順序表中查找第i個元素的前趨也很方便.單鏈表和單循環鏈表既不能實現隨機存取,查找第i個元素的前趨也不方便,雙鏈表雖然能快速查找第i個元素的前趨,但不能實現隨機存取.假設鏈表中最常用的操作是在最后一個結點之后插入一個結點和刪除第一個結點,那么采用存儲方法最節省時間.A單鏈表B帶頭指針的單循環鏈表C雙鏈表D帶尾指針的單循環鏈表【解答】D【分析】在鏈表中的最后一個結點之后插入一個結點需要知道終端結點的地址,所以,單鏈表、帶頭指針的單循環鏈表、雙鏈表都不適宜,考

10、慮在帶尾指針的單循環鏈表中刪除第一個結點,其時間性能是0(1),所以,答案是D假設鏈表中最常用的操作是在最后一個結點之后插入一個結點和刪除最后一個結點,那么采用()存儲方法最節省運算時間.A單鏈表B循環雙鏈表C單循環鏈表D帶尾指針的單循環鏈表【解答】B【分析】在鏈表中的最后一個結點之后插入一個結點需要知道終端結點的地址,所以,單鏈表、 單循環鏈表都不適宜,刪除最后一個結點需要知道終端結點的前驅結點的地址,所以,帶尾指針的單循環鏈表不適宜,而循環雙鏈表滿足條件.在具有n個結點的有序單鏈表中插入一個新結點并仍然有序的時間復雜度是().A0(1)B0(n)C0(n2)DO(nlog2n)【解答】B【

11、分析】首先應順序查找新結點在單鏈表中的位置.對于n個元素組成的線性表,建立一個有序單鏈表的時間復雜度是().A0(1)B0(n)C0(n2)DO(nlog2n)【解答】C【分析】該算法需要將n個元素依次插入到有序單鏈表中,而插入每個元素需On.使用雙鏈表存儲線性表,其優點是可以.A提升查找速度B更方便數據的插入和刪除C節約存儲空間D很快回收存儲空間【解答】B【分析】 在鏈表中一般只能進行順序查找,所以,雙鏈表并不能提升查找速度,由于雙鏈表中有兩個指針域,顯然不能節約存儲空間,對于動態存儲分配,回收存儲空間的速度是一樣的.由于雙鏈表具有對稱性,所以,其插入和刪除操作更加方便.ID在一個單鏈表中,

12、q所指結點是p所指結點的直接前驅,假設在q和p之間插入s所指結點,那么執行操作.As-next=p-next;p-next=s;Bq-next=s;s-next=p;Cp-next=s-next;s-next=p;Dp-next=s;s-next=q;【解答】B【分析】注意此題是在q和p之間插入新結點,所以,不用考慮修改指針的順序.在循環雙鏈表的p所指結點后插入s所指結點的操作是 .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=

13、p;s-next=p-next;p-next=s;p-next-prior=s;Ds-prior=p;s-next=p-next;p-next-prior=s;p-next=s【解答】D【分析】 在鏈表中,對指針的修改必須保持線性表的邏輯關系,否那么,將違背線性表的邏輯特征,圖2-10給出備選答案C和D的圖解.10判斷題線性表的邏輯順序和存儲順序總是一致的.【解答】 錯.順序表的邏輯順序和存儲順序一致,鏈表的邏輯順序和存儲順序不,定致.線性表的順序存儲結構優于鏈接存儲結構.【解答】錯.兩種存儲結構各有優缺點.設p,q是指針,假設p=q,那么*p=*q.【解答】錯.p=q只能表示p和q指向同一起

14、始地址,而所指類型那么不一定相同.線性結構的根本特征是：每個元素有且僅有一個直接前驅和一個直接后繼.【解答】 錯.每個元素最多只有一個直接前驅和一個直接后繼,第一個元素沒有前驅,最后一個元素沒有后繼.在單鏈表中,要取得某個元素,只要知道該元素所在結點的地址即可,因此單鏈表是隨機存取結構【解答】錯.要找到該結點的地址,必須從頭指針開始查找,所以單鏈表是順序存取結構.11請說明順序表和單鏈表各有何優缺點,并分析以下情況下,采用何種存儲結構更好些.假設線性表的總長度根本穩定,且很少進行插入和刪除操作,但要求以最快的速度存取線性表中的元素.如果n個線性表同時并存,并且在處理過程中各表的長度會動態發生變

15、化.描述一個城市的設計和規劃.【解答】 順序表的優點： 無需為表示表中元素之間的邏輯關系而增加額外的存儲空間；可以快速地存取表中任一位置的元素即隨機存取.順序表的缺點：插入和刪除操作需移動大量元素；表的容量難以確定；造成存儲空間的“碎片.單鏈表的優點：不必事先知道線性表的長度；插入和刪除元素時只需修改指針,不用移動元素.單鏈表的缺點：指針的結構性開銷；存取表中任意元素不方便,只能進行順序存取.應選用順序存儲結構.由于順序表是隨機存取結構,單鏈表是順序存取結構.此題很少進行插入和刪除操作,所以空間變化不大,且需要快速存取,所以應選用順序存儲結構.應選用鏈接存儲結構.鏈表容易實現表容量的擴充,適合

16、表的長度動態發生變化.應選用鏈接存儲結構.由于一個城市的設計和規劃涉及活動很多,需要經常修改、擴充和刪除各種信息,才能適應不斷開展的需要.而順序表的插入、刪除的效率低,故不適宜.12算法設計設計一個時間復雜度為O(n)的算法,實現將數組An中所有元素循環右移k個位置.【解答】算法思想請參見主教材第一章思想火花.下面給出具體算法.分析算法,第一次調用Reverse函數的時間復雜度為O(k),第二次調用Reverse函數的時間復雜度為O(n-k),第三次調用Reverse函數的時間復雜度為O(n),所以,總的時間復雜度為O(n).數組An中的元素為整型,設計算法將其調整為左右兩局部,左邊所有元素為

17、奇數,右邊所有元素為偶數,并要求算法的時間復雜度為O(n)0【解答】從數組的兩端向中間比擬,設置兩個變量i和j,初始時i=0,j=n-1,假設Ai為偶數并且Aj為奇數,那么將Ai與Aj交換.具體算法如下：分析算法,兩層循環將數組掃描一遍,所以,時間復雜度為O(n)0試編寫在無頭結點的單鏈表上實現線性表的插入操作的算法,并和帶頭結點的單鏈表上的插入操作的實現進行比擬.【解答】參見2.2.3.試分別以順序表和單鏈表作存儲結構,各寫一實現線性表就地逆置的算法.【解答】順序表的逆置,即是將對稱元素交換,設順序表的長度為length,那么將表中第i個元素與第length-i-1個元素相交換.具體算法如下

18、：單鏈表的逆置請參見2.2.4算法2-4和算法2-6.假設在長度大于1的循環鏈表中,即無頭結點也無頭指針,s為指向鏈表中某個結點的指針,試編寫算法刪除結點s的前趨結點.【解答】利用單循環鏈表的特點,通過指針s可找到其前驅結點r以及r的前驅結點p,然后將結點r刪除,如圖2-11所示,具體算法如下：一單鏈表中的數據元素含有三類字符：字母、數字和其他字符.試編寫算法,構造三個循環鏈表,使每個循環鏈表中只含同一類字符.【解答】在單鏈表A中依次取元素,假設取出的元素是字母,把它插入到字母鏈表B中,假設取出的元素是數字,那么把它插入到數字鏈表D中,直到鏈表的尾部,這樣表B,D,A中分別存放字母、 數字和其

19、他字符.具體算法如下：設單鏈表以非遞減有序排列,設計算法實現在單鏈表中刪去值相同的多余結點.【解答】從頭到尾掃描單鏈表,假設當前結點的元素值與后繼結點的元素值不相等,那么指針后移；否那么刪除該后繼結點.具體算法如下：判斷帶頭結點的雙循環鏈表是否對稱.【解答】設工作指針p和q分別指向循環雙鏈表的開始結點和終端結點,假設結點p和結點q的數據域相等,那么工作指針p后移,工作指針q前移,直到指針p和指針q指向同一結點循環雙鏈表中結點個數為奇數,或結點q成為結點p的前驅循環雙鏈表中結點個數為偶數.如圖2-12所示.學習自測及答案1 .一維數組A采用順序存儲結構,每個元素占用4個存儲單元,第9個元素的地址

20、為144,那么第一個元素的地址是.A108B180C176D112【解答】D2.在長度為n的線性表中查找值為x的數據元素的時間復雜度為：().AO(0)B0(1)CO(n)DO(n2)【解答】C3.在一個長度為n的順序表的第i(1in+1)個元素之前插入一個元素,需向后移動()個元素,刪除第i(1&i&n)個元素時,需向前移動()個元素.【解答】n-i+1,n-i4.在單鏈表中,除了頭結點以外,任一結點的存儲位置由()指示.【解答】其前趨結點的指針域5.當線性表采用順序存儲結構時,其主要特點是().【解答】邏輯結構中相鄰的結點在存儲結構中仍相鄰6.在雙鏈表中,每個結點設置了兩個

21、指針域,其中一個指向()結點,另一個指向()結點.【解答】前驅,后繼7 .設A是一個線性表(a1,a2,an),采用順序存儲結構,那么在等概率的前提下,平均每插入一個元素需要移動的元素個數為多少？假設元素插在ai【解答】08 .線性表存放在整型數組Aarrsize的前elenum個單元中,且遞增有序.編寫算法,將元素x插入到線性表的適當位置上,以保持線性表的有序性,并且分析算法的時間復雜度.【解答】此題是在一個遞增有序表中插入元素x,根本思路是從有序表的尾部開始依次取元素與x比擬,假設大于X,此元素后移一位,再取它前面一個元素重復上述步驟；否那么,找到插入位置,將X插入.具體算法如下：9 ,單

22、鏈表中各結點的元素值為整型且遞增有序,設計算法刪與ai+1之間14Wn的概率為素個數又是多少？,那么平均每插入一個元素所要移動的元除鏈表中所有大于mink且小于maxk的所有元素,并釋放被刪結點的存儲空間.【解答】 由于是在有序單鏈表上的操作,所以,要充分利用其有序性.在單鏈表中查找第一個大于mink的結點和第一個小于maxk的結點,再將二者間的所有結點刪除.x1,x2,x3,xn-1,xn.請將該循環鏈表拆成兩個單循環鏈表L1和L2,使得L1中含有原L1表中序號為奇數的結點且遍歷結果為：x1,x3,；L2中含有原L1表中序號為偶數的結點且遍歷結果為：,x4,x2.【解答】算法如下：第3章特殊

23、線性表一一棧、隊列和申課后習題講解1.填空設有一個空棧,棧頂指針為1000H,現有輸入序列為1、2、3、4、10.設單循環鏈表L1,對其遍歷的結果是:5,經過push,push,pop,push,pop,push,push后,輸出序歹!J是,棧頂指針為.【解答】23,1003H棧通常采用的兩種存儲結構是；其判定棧空的條件分別是,判定棧滿的條件分別是.【解答】順序存儲結構和鏈接存儲結構或順序棧和鏈棧,棧頂指針top=-1和top=NULL,棧頂指針top等于數組的長度和內存無可用空間可作為實現遞歸函數調用的一種數據結構【解答】?！痉治觥窟f歸函數的調用和返回正好符合后進先出性.表達式a*b+c-d

24、的后綴表達式是.【解答】abc+*d-【分析】 將中綴表達式變為后綴表達式有一個技巧：將操作數依次寫下來,再將算符插在它的兩個操作數的后面.棧和隊列是兩種特殊的線性表,棧的操作特性是,隊列的操作特性是,棧和隊列的主要區別在于.【解答】后進先出,先進先出,對插入和刪除操作限定的位置不同循環隊列的引入是為了克服.【解答】假溢出數組Qn用來表示一個循環隊列,front為隊頭元素的前一個位置,rear為隊尾元素的位置,計算隊列中元素個數的公式為.【解答】rear-front+n%n【分析】也可以是rear-front%n,但rear-front的結果可能是負整數,而對一個負整數求模,其結果在不同的編譯

25、器環境下可能會有所不同.用循環鏈表表示的隊列長度為n,假設只設頭指針,那么出隊和入隊的時間復雜度分別是和.【解答】O(1),O(n)【分析】 在帶頭指針的循環鏈表中,出隊即是刪除開始結點,這只需修改相應指針； 入隊即是在終端結點的后面插入一個結點,這需要從頭指針開始查找終端結點的地址.用是一種特殊的線性表,其特殊性表達在.【解答】數據元素的類型是一個字符兩個用相等的充分必要條件是.【解答】長度相同且對應位置的字符相等【分析】例如abcyabc,abc/bca.2.選擇題假設一個棧的輸入序列是1,2,3,n,輸出序列的第一個元素是n,那么第i個輸出元素是.A不確定Bn-iCn-i-1Dn-i+1

26、【解答】D【分析】此時,輸出序列一定是輸入序列的逆序.設棧S和隊列Q的初始狀態為空,元素el、e2、e3、e4、e5、e6依次通過棧S,一個元素出棧后即進入隊列Q,假設6個元素出隊的順序是e2、e4、e3、e6、e5、el,那么棧S的容量至少應該是.A6B4C3D2【解答】C【分析】由于隊列具有先進先出性,所以,此題中隊列形同虛設,即出棧的順序也是e2、e4、e3、e6、e5、el.一個棧的入棧序列是1,2,3,4,5,那么棧的不可能的輸出序列是 .A54321B45321C43512D12345【解答】C【分析】 此題有一個技巧： 在輸出序列中任意元素后面不能出現比該元素小并且是升序指的是元

27、素的序號的兩個元素.設計一個判別表達式中左右括號是否配對的算法,采用數據結構最正確A順序表B棧C隊列D鏈表【解答】B【分析】每個右括號與它前面的最后一個沒有匹配的左括號配對,因此具有后進先出性.在解決計算機主機與打印機之間速度不匹配問題時通常設置一個打印緩沖區,該緩沖區應該是一個結構.A棧B隊列C數組D線性表【解答】B【分析】 先進入打印緩沖區的文件先被打印,因此具有先進先出性.6一個隊列的入隊順序是1,2,3,4,那么隊列的輸出順序是.A4321B1234C1432D3241【解答】B【分析】隊列的入隊順序和出隊順序總是一致的.棧和隊列的主要區別在于.A它們的邏輯結構不一樣B它們的存儲結構不

28、一樣C所包含的運算不一樣D插入、刪除運算的限定不一樣【解答】D【分析】棧和隊列的邏輯結構都是線性的,都有順序存儲和鏈接存儲,有可能包含的運算不一樣,但不是主要區別,任何數據結構在針對具體問題時包含的運算都可能不同.設數組Sn作為兩個棧S1和S2的存儲空間,對任何一個棧只有當Sn全滿時才不能進行進棧操作.為這兩個棧分配空間的最正確方案是.AS1的棧底位置為0,S2的棧底位置為n-1BS1的棧底位置為0,S2的棧底位置為n/2CS1的棧底位置為0,S2的棧底位置為nDS1的棧底位置為0,S2的棧底位置為1【解答】A【分析】兩棧共享空間首先兩個棧是相向增長的,棧底應該分別指向兩個棧中的第一個元素的位

29、置,并注意C+中的數組下標是從0開始的.設有兩個由p和q,求q在p中首次出現的位置的運算稱作.A連接B模式匹配C求子由D求用長【解答】B3.判斷題(1)有n個元素依次進棧,那么出棧序列有(n-1)/2種.【解答】錯.應該有種.?？梢宰鳛閷崿F過程調用的一種數據結構.【解答】 對.只要操作滿足后進先出性,都可以采用棧作為輔助數據結構.在棧滿的情況下不能做進棧操作,否那么將產生“上溢.【解答】對.在循環隊列中,front指向隊頭元素的前一個位置,rear指向隊尾元素的位置,那么隊滿的條件是front=rear.【解答】 錯.這是隊空的判定條件,在循環隊列中要將隊空和隊滿的判定條件區別開.空用與空格用是相同的.【解答】錯.空用的長度為零,而空格用的長度不為0,其長度是由中空格的個數.4.設有一個棧,元素進棧的次序為A,B,C,D,E,能否得到如下出棧序列,假設能,請寫出操作序列,假設不能,請說明原因.(1) C,E,A,