山西大學第1章緒論⑴（）是數據的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。【解答】數據元素⑵（）是數據的最小單位，（）是討論數據結構時涉及的最小數據單位。【解答】數據項，數據元素【分析】數據結構指的是數據元素以及數據元素之間的關系。⑶從邏輯關系上講，數據結構主要分為（）、（）、（）和（）。集合，線性結構，樹結構，圖結構（4）數據的存儲結構主要有（）和（）兩種基本方法，不論哪種存儲結構，都要存儲兩方面的內容：（）和（）。【解答】順序存儲結構，鏈接存儲結構，數據元素，數據元素之間的關系（5）算法具有五個特性，分別是（）、（）、（）、（）、（）.【解答】有零個或多個輸入，有一個或多個輸出，有窮性，確定性，可行性（6）算法的描述方法通常有（）、（）、（）和（）四種，其中，（）被稱為算法語言.【解答】自然語言，程序設計語言，流程圖，偽代碼，偽代碼⑺在一般情況下，一個算法的時間復雜度是（）的函數。【解答】問題規模（8）設待處理問題的規模為n,若一個算法的時間復雜度為一個常數，則表示成數最級的形式為（），若為n*log25n,則表示成數量級的形式為（）。【解答】0（1）,O（nlog2n）【分析】用大0記號表示算法的時間復雜度，需要將低次幕去掉，將最高次事的系數去掉。2.選擇題⑴順序存儲結構中數據元素之間的邏輯關系是由（）表示的，鏈接存儲結構中的數據元素之間的邏輯關系是由（）表示的。A線性結構B非線性結構C存儲位置D指針【解答】C,D【分析】順序存儲結構就是用一維數組存儲數據結構中的數據元素，其邏輯關系由存儲位置（即元素在數組中的卜標）表示；鏈接存儲結構中一個數據元素對應鏈表中的一個結點，元素之間的邏輯關系由結點中的指針表示。⑵假設有如下遺產繼承規則：丈夫和妻了?可以相互繼承遺產；子女可以繼承父親或母親的遺產：了女間不能相互繼承。則表示該遺產繼承關系的最合適的數據結構應該是（）。A樹B圖C線性表D集合解答】B【分析】將丈夫、妻子和子女分別作為數據元素，根據題意畫出邏輯結構圖。圖1-2遺產繼承邏輯結構圖⑶算法指的是（）.A對特定問題求解步驟的?種描述，是指令的有限序列。B計算機程序C解決問題的計算方法D數據處理【解答】A【分析】計算機程序是對算法的具體實現；簡單地說，算法是解決問題的方法：數據處理是通過算法完成的。所以，只有A是算法的準確定義。（4）卜一面（）不是算法所必須具備的特性。A有窮性B確切性C高效性D可行性【解答】C【分析】高效性是好算法應具備的特性。⑸算法分析的目的是（），算法分析的兩個主要方面是（）。A找出數據結構的合理性B研究算法中輸入和輸出的關系C分析算法的效率以求改進D分析算法的易讀性和文檔性E空間性能和時間性能F正確性和簡明性G可讀性和文檔性H數據復雜性和程序復雜性【解答】C,E3.判斷題（1）算法的時間復雜度都要通過算法中的基本語句的執行次數來確定。【解答】錯。時間復雜度要通過算法中基本語句執行次數的數量級來確定。⑵每種數據結構都具備三個基本操作：插入、刪除和杏找。【解答】錯。如數組就沒有插入和刪除操作。此題注意是每種數據結構。⑶所謂數據的邏輯結構指的是數據之間的邏輯關系。【解答】錯。是數據之間的邏輯關系的整體。（4）邏輯結構與數據元素本身的內容和形式無關。【解答】對。因此邏輯結構是數據組織的主要方面.⑸基于某種邏輯結構之上的基本操作，其實現是唯一的。【解答】錯。基本操作的實現是基于某種存儲結構設計的，因而不是唯一的。.分析以下各程序段，并用大。記號表示其執行時間。⑴⑴i=l,k=O;while(i<n-l)(k=k+10*i;i++；}i=l;j=0,while(i+j<=n)if(i>j)j++；elsei++;(5)for(i=l;i<=n;i++)for(j=l;j<=i,j++)for(k=l;k<=j;k++)x++;do(k=k+10*i;i++；}while(i<=n)y=0;while((y+l)*(y+l)<=n)y=y+l;【解答】⑴基本語句是k=k+10*i,共執行了n?2次,所以T(n)=O(n)。⑵基本語句是k=k+10*i,共執行了n次，所以T(n)=O(n)。(3)分析條件語句，每循環?次，i+j整體加1,共循環n次，所以T(n)=O(n)。(4)設循環體共執行T(n)次，每循環一次，循環變量y加1,最終T(n)=y,即：(T(n)+l)2<n,所以T(n)=O(nl/2).⑸X++是基本語句，所以.設有數據結構(D,R),其中D={1,2,3,4,5,6},R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。試畫出其邏輯結構圖并指出屬「何種結構。【解答】其邏輯結構圖如圖1-3所示，它是一種圖結構。圖1-3圖1-3邏輯結構圖.為整數定義一個抽象數據類型，包含整數的常見運算，每個運算對應一個基本操作，每個基本操作的接口需定義前置條件、輸入、功能、輸出和后置條件.【解答】整數的抽象數據類型定義如下：ADTintegerData整數a：可以是正整數(1,2,3,...)、負整數(-1,?2,?3,…)和零OperationConstructor前置條件：整數a不存在輸入：一個整數b功能：構造一個與輸入值相同的整數輸出:無后置條件：整數a具有輸入的值Set前置條件：存在一個整數a輸入：一個整數b功能：修改整數a的值，使之與輸入的整數值相同輸出:無后置條件：整數a的值發生改變Add前置條件：存在一個整數a輸入：一個整數b功能：將整數a與輸入的整數b相加輸出：相加后的結果后置條件：整數a的值發生改變Sub前置條件：存在一個整數a輸入：一個整數b功能：將整數a與輸入的整數b相減輸出：相減的結果后置條件：整數a的值發生改變Multi前置條件：存在個整數a輸入：一個整數b功能：將整數a與輸入的整數b相乘輸出：相乘的結果后置條件：整數a的值發生改變Div前置條件：存在?個整數a輸入：一個整數b功能：將整數a與輸入的整數b相除輸出：若整數b為零，則拋出除零異常，否則輸出相除的結果后置條件：整數a的值發生改變Mod前置條件：存在?個整數a輸入：一個整數b功能：求當前整數與輸入整數的模，即正的余數輸出：若整數b為零，則拋出除零異常，否則輸出取模的結果后置條件：整數a的值發生改變Equal前置條件：存在?個整數a輸入：一個整數b功能：判斷整數a與輸入的整數b是否相等輸出：若相等返叵II,否則返回0后置條件：整數a的值不發生改變endADT.求多項式A(x)的算法可根據下列兩個公式之一來設計：A(x)=anxn+an-lxn-l+...+alx+aOA(x)=(...(anx+an-l)x+...+al)x)+aO根據算法的時間復雜度分析比較這兩種算法的優劣。【解答】第二種算法的時間性能要好些。第一種算法需執行大量的乘法運算，而第二種算法進行了優化,減少了不必要的乘法運算。8.算法設計(要求：算法用偽代碼和C++描述，并分析最壞情況下的時間復雜度)⑴對?個整型數組A［n］設計?個排序算法。【解答】下面是簡單選擇排序算法的偽代碼描述.隙1.對n個記錄進行n-1趟簡單選擇排序：1.1在無序區［i，n-1］中選取最小記錄，設其下標為index；| 1.2將最小記錄與第i個記錄交換；下而是簡單選擇排序算法的C++描述簡單選擇排序算法SelectSortvoidSdectSort(intr[],intn)(for(1=0;i<n-l;i++) /網n個記錄進行n-1趟簡單選擇排序(index=i,far(j=i+l,j<n,j++) 〃在無序區中選取最小記錄if(r[j]<r[index])index=j,if(index!=i)r[i]-<~?r[index];餃換元素))n-2n-1 0?(?)-sei-o(m)分析算法，有兩層嵌套的for循環，所以，⑵找出整型數組A［n］中元素的最大值和次最大值。【解答】算法的偽代碼描述如卜?：.將前兩個元素進行比較，較大者癱！Imax中，較小者游!Inmax中；.從第3個元素開始直到最后一個元素依次取元素川小執行下列操作:如果A[i]>max,則A[i]為最大值，原來的最大值為次最大值；否則，如果A[i]>nmax,則最大值不變，A[i]為次最大值；.輸出最大值max,次最大值nmax；算法的C++描述如下:最大值和次最大值算法Max_NextMax|voidMax_NextMax(intA[],intn,int&max,int&nmax)(if(A[O]>=A[1])(max=A[0];nmax=A[l];)dse(max=A[l];nmax=A[0];)for(i=2;i<n;i++)if(A[i]>=max){nmax551!^,max=A[i];)elseif(A[i]>nmax)nmax^Afi],cout<〈"最大值買hM?max?"\n次最大值為："<<nmax<<endl,)分析算法,只有一層循環,共執行n?2次，所以，T(n)=0(n)o學習自測及答案.順序存儲結構的特點是()，鏈接存儲結構的特點是()。【解答】用元素在存儲器中的相對位置來表示數據元素之間的邏輯關系，用指示元素存儲地址的指針表示數據元素之間的邏輯關系。.算法在發生非法操作時可以作出處理的特性稱為()。【解答】健壯性.常見的算法時間復雜度用大0記號表示為：常數階()、對數階()、線性階()、平方階()和指數階()。【解答】0(1),O(log2n),0(n),0(n2),0(2n).將下列函數按它們在n時的無窮大階數，從小到大排列。n,n-n3+7n5,nlogn,2n/2,n3,Iog2n,nl/2+log2n,(3/2)n,n!,n2+log2n【解答】Iog2n,nl/2+log2n,n,nlog2n,n2+log2n,n3,n-n3+7n5,2n/2,(3/2)n,n!

.試描述數據結構和抽象數據類型的概念與程序設計語言中數據類型概念的區別。【解答】數據結構是指相互之間存在一定關系的數據元素的集合。而抽象數據類型是指一個數據結構以及定義在該結構I:的一組操作。程序設計語言中的數據類型是一個值的集合和定義在這個值集上一組操作的總稱。抽象數據類型可以看成是對數據類型的一種抽象。.對下列用二元組表示的數據結構，試分別畫出對應的邏輯結構圖，并指出屬于何種結構。A=(D,R),其中D={al,a2,a3,a4},R={}⑵B=(D,R),其中D={a,b,c,d,e,f),R={??}C=(D,R),其中D={a,b,c,d,e,f},R={“”,}D=(D,R),其中D={1,2,3,4,5,6},R={(1,2),(1,4),(2,3),(2,4),(3,4),(3,5),(3,6),(4,6)}【解答】⑴屬于集合，其邏輯結構圖如圖l-4(a)所示：⑵屬于線性結構，其邏輯結構圖如圖l-4(b)所示;⑶屬于樹結構，其邏輯結構圖如圖l-4(c)所示；⑷屬于圖結構，其邏輯結構圖如圖l-4(d)所示。圖1-4第7題對應的邏輯結構圖7.求卜.列算法的時間復雜度。count=0;x=l;while(x{x*=2;count++;}returncount;【解答】O(log2n)第2章線性表課后習題講解i.填空⑴在順序表中，等概率情況下，插入和刪除一個元素平均需移動（）個元素，具體移動元素的個數與（）和（）有關。【解答】表長的一半，表長，該元素在表中的位置⑵順序表中第?個元素的存儲地址是100,每個元素的長度為2,則第5個元素的存儲地址是（）.【解答】108【分析】第5個元素的存儲地址=第1個元素的存儲地址+（5—1）x2=108⑶設單鏈表中指針p指向結點A,若要刪除A的后繼結點（假設A存在后繼結點），則需修改指針的操作為（）。【解答】p->next=（p->next）->next（4）單鏈表中設置頭結點的作用是（）.【解答】為了運算方便【分析】例如在插入和刪除操作時不必對表頭的情況進行特殊處理。⑸非空的單循環鏈表由頭指針head指示，則其尾結點（由指針p所指）滿足（）。【解答】p->next=head【分析】如圖2-8所示。dErM（6）在由尾指針rear指示的單循環鏈表中，在表尾插入一個結點s的操作序列是（）；刪除開始結點的操作序列為（）。【解答】s->next=rear->next;rear->next=s;rear=s;q=rear->next->next;rear->next->next=q->next;deleteq;t分析】操作示意圖如圖2-9所示：圖2-9帶尾指針的循環鏈表中插入和刪除操作示意圖⑺一個具有n個結點的單鏈表，在指針p所指結點后插入一個新結點的時間復雜度為（）；在給定值為x的結點后插入?個新結點的時間復雜度為（）.【解答】0（1）,O（n）【分析】在p所指結點后插入一個新結點只需修改指針，所以時間復雜度為0（1）；而在給定值為x的結點后插入一個新結點需要先查找值為x的結點，所以時間復雜度為O（n）。（8）可由一個尾指針唯一確定的鏈表有（）、（）、（）.【解答】循環鏈表，循環雙鏈表，雙鏈表2.選擇題⑴線性表的順序存儲結構是種（）的存儲結構，線性表的鏈接存儲結構是種（）的存儲結構。A隨機存取B順序存取C索引存取D散列存取【解答】A.B【分析】參見2.2.L⑵線性表采用鏈接存儲時，其地址（）.A必須是連續的 B部分地址必須是連續的C一定是不連續的 D連續與否均可以【解答】D【分析】線性表的鏈接存儲是用組任意的存儲單元存儲線性表的數據元素，這組存儲單元可以連續，也可以不連續，甚至可以零散分布在內存中任意位置。（3）單循環鏈表的主要優點是（）。A不再需要頭指針了B從表中任一結點出發都能掃描到整個鏈表；C已知某個結點的位置后，能夠容易找到它的直接前趨；D在進行插入、刪除操作時，能更好地保證鏈表不斷開。【解答】B⑷鏈表不具有的特點是（）.A可隨機訪問任?元素B插入、刪除不需要移動元素C不必事先估計存儲空間D所需空間與線性表長度成正比【解答】A⑸若某線性表中最常用的操作是取第i個元素和找第i個元素的前趨，則采用（）存儲方法最節省時間。A順序表B單鏈去C雙鏈&D單循環鏈發【解答】A【分析】線性表中最常用的操作是取第i個元素，所以，應選擇隨機存取結構即順序發，同時在順序表中查找第i個元索的前趨也很方便。單鏈表和單循環鏈表既不能實現隨機存取，查找第i個元索的前趨也不方便，雙鏈表雖然能快速查找第i個元素的前趨，但不能實現隨機存取。（6）若鏈表中最常用的操作是在最后一個結點之后插入一個結點和刪除第一個結點，則采用（）存儲方法最節省時間。A單鏈表B帶頭指針的單循環鏈表C雙鏈表D帶尾指針的單循環鏈表【解答】Dt分析】在鏈表中的最后一個結點之后插入一個結點需要知道終端結點的地址，所以，單鏈表、帶頭指針的雅循環鏈表、雙鏈表都不合適，考慮在帶尾指針的單循環鏈表中刪除第一個結點，其時間性能是。（1），所以，答案是D。⑺若鏈表中最常用的操作是在最后一個結點之后插入一個結點和刪除最后一個結點，則采用（）存儲方法最節省運算時間。A單鏈表B循環雙鏈表C單循環鏈表D帶尾指針的單循環鏈表【解答】B【分析】在鏈表中的最后一個結點之后插入一個結點需耍知道終端結點的地址，所以，單鏈表、單循環鏈表都不合適，刪除最后一個結點需要知道終端結點的前驅結點的地址，所以，帶尾指針的單循環鏈表不合適，而循環雙鏈表滿足條件。(8)在具有n個結點的有序單鏈表中插入?個新結點并仍然有序的時間復雜度是()。A0(1)B0(n)C0(n2)DO(nlog2n)【解答】B(分析］首先應順序查找新結點在單鏈表中的位置.⑼對于n個元素組成的線性表，建立個有序單鏈表的時間復雜度是()。A0(1)B0(n)C0(n2)DO(nlog2n)【解答】C【分析】該算法需要將n個元素依次插入到有序單鏈表中，而插入每個元素需0(n)。00)使用雙鏈表存儲線性表，其優點是可以()。A提高荏找速度B更方便數據的插入和刪除C節約存儲空間D很快回收存儲空間【解答】B【分析】在鏈表中一般只能進行順序查找，所以，雙鏈表并不能提高查找速度，因為雙鏈表中有兩個指針域，顯然不能節約存儲空間，對于動態存儲分配，回收存儲空間的速度是一樣的。由于雙鏈表具有對稱性，所以，其插入和刪除操作更加方便。(1D在?個單鏈表中，已知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=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的圖解。(a)備選答案C操作示意圖(第4步指針修改無法進行) (b)備選答案D操作示意圖圖2-10雙鏈表插入操作修改指針操作示意圖.判斷題⑴線性表的邏輯順序和存儲順序總是一致的。【解答】錯.順序表的邏輯順序和存儲順序?致，鏈表的邏輯順序和存儲順序不?定?致。⑵線性表的順序存儲結構優于鏈接存儲結構.【解答】錯。兩種存儲結構各有優缺點。⑶設p,q是指針,^p=q.M*p=*q.【解答】錯。p=q只能表示p和q指向同一起始地址，而所指類型則不一定相同。⑷線性結構的基本特征是：每個元素有且僅有一個直接前驅和個直接后繼。【解答】錯。每個元素最多只有一個直接前驅和一個直接后繼，第一個元素沒有前驅，最后一個元素沒有后繼。⑸在單鏈表中，要取得某個元素，只要知道該元素所在結點的地址即可，因此單鏈表是隨機存取結構。【解答】錯。要找到該結點的地址，必須從頭指針開始查找，所以單鏈表是順序存取結構。.請說明順序表和單鏈表各有何優缺點，并分析下列情況下，采用何種存儲結構更好些。⑴若線性表的總長度基本穩定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素。⑵如果n個線性表同時并存，并且在處理過程中各表的長度會動態發生變化。⑶描述一個城市的設計和規劃。【解答】順序發的優點：①無需為表示表中元素之間的邏輯關系而增加額外的存儲空間；②可以快速地存取表中任??位置的元素(即隨機存取)。順序表的缺點：①插入和刪除操作需移動大量元素；②表的容量難以確定；③造成存儲空間的''碎片"。單鏈表的優點：①不必事先知道線性表的長度；②插入和刪除元素時只需修改指針，不用移動元素。單鏈表的缺點：①指針的結構性開銷；②存取表中任意元素不方便，只能進行順序存取。⑴應選用順序存儲結構。因為順序表是隨機存取結構，單鏈表是順序存取結構。本題很少進行插入和刪除操作，所以空間變化不大，且需要快速存取，所以應選用順序存儲結構。⑵應選用鏈接存儲結構。鏈表容易實現表容量的擴充，適合表的長度動態發生變化。⑶應選用鏈接存儲結構。因為?個城市的設計和規劃涉及活動很多，需要經常修改、擴充和刪除各種信息,才能適應不斷發展的需要。而順序表的插入、刪除的效率低，故不合適。.算法設計⑴設計一個時間復雜度為0(n)的算法，實現將數組A[n]中所有元素循環右移k個位置。【解答】算法思想請參見主教材第一章思想火花。卜面給出具體算法。儲壞右移算法Converse|voidConverse(intA[],intn,intk)(Reverse(A,0,k-l);Reverse(A,k,n-l),Reverse(A,0,n-l);}voidReverse(intA[],intfrom,intto)假數犯A中元素從from到to逆置(far(i=0,i<(to-from+l)/2,i++)A[from+i]-<—?A[to-i], 較換元素J分析算法,第?次調用Reverse函數的時間復雜度為0(k),第二次調用Reverse函數的時間復雜度為O(n-k),第三次調用Reverse函數的時間復雜度為0(n),所以，總的時間復雜度為0(n)。⑵已知數組A[n]中的元素為整型，設計算法將其調整為左右兩部分，左邊所有元素為奇數，右邊所有元素為偶數，并要求算法的時間復雜度為O(n).,【解答】從數組的兩端向中間比較，設置兩個變量i和j,初始時i=0,j=n-l,若A[i]為偶數并且A[j]為奇數，則將A[i]與A[j]交換。具體算法如卜.：數如奇偶調整算法AdjustvoidAdjust(intA[],n){1=0;j=n-l;while(i<j)(while(A[i]%21=0)i++;while(A[j]%2=0)j~if(i<j)A。]—A[j];}}分析算法，兩層循環將數組掃描一遍，所以，時間復雜度為o(n)。⑶試編寫在無頭結點的推鏈表L實現線性表的插入操作的算法，并和帶頭結點的單鏈表I:的插入操作的實現進行比較。【解答】參見2.2.3。(4)試分別以順序表和單鏈發作存儲結構，各寫?實現線性表就地逆置的算法。【解答】順序表的逆置，即是將對稱元索交換，設順序表的長度為length,則將表中第i個元素與第length-i-1個元素相交換。具體算法如下：順序表逆置算法Reverse|template<classT>voidReverseddata[],intlength)(for(i=0,i<=length/2,i++)(temp=data[i],data[i]=data[length-r1],data[length-i_1]=temp,))單鏈表的逆置請參見2.2.4算法2-4和算法2-6o⑸假設在長度大于1的循環鏈衣中，即無頭結點也無頭指針，s為指向徒表中某個結點的指針，試編寫算法刪除結點s的前趨結點。【解答】利用單循環鏈表的特點，通過指針s可找到其前驅結點r以及r的前驅結點p,然后將結點r刪除,如圖2?11所示，具體算法如下：彳后環鞋表刪除算法Dei[template<classT>voidDel(Node<T>*s)(p=s, "工作指針P初始化，查找S的前驅結點的前驅結點，用P指示while(p->next->next!=s)p=p->next,r=p->next, 加為p的前驅結點，q為r的前驅結點p->next=s; "刪除r所指結點deleter;圖2-11刪除結點s的前驅結點操作示意圖(6)已知單鏈表中的數據元素含有三類字符：字母、數字和其他字符.試編寫算法，構造三個循環鏈表，使每個循環鏈表中只含同一類字符。【解答】在單鏈表A中依次取元素，若取出的元素是字母，把它插入到字母鏈&B中，若取出的元素是數字，則把它插入到數字鏈表D中，宜到鏈表的尾部，這樣表B,D.A中分別存放字母、數字和其他字符。具體算法如下：單鞋表折分算法Adjusttemplate<classT>voidAdjust(Node<T>*A,Node<int>*D,Node<char>*B)(D=newNode<int>;D->next=D, 倒建空循環鏈表D,存放數字B=newNode<char>;B->next=B, "創建空循環鏈表B,存放字符p=A;q=p->next, 力工作指針q初始化while(q)(if((,A,<=q->data)&&(q->data>=,Z')||('a,<=q->data)&&(q->data>=,z,))(p->next=q->next;q->ne5rt=B->next;B->next=q, "采用頭插法插在循環鏈表B的頭結點的后面)elseif((,0,<=q->data)&&(q->data>=,9,)){p->next=q->next,q->next=D->next;D->next=q, /探用頭插法插在循環鏈表D的頭結點的后面)risep=q,q=p->next,}p->next=A,R=A,解鏈表A構造為循環鏈表，為除字母和數字的其他字符)⑺設單鏈表以非遞減有序排列，設計算法實現在單鏈表中刪去值相同的多余結點。【解答】從頭到尾掃描單鏈衣，若當前結點的元素值與后繼結點的元素值不相等，則指針后移；否則刪除該后繼結點。具體算法如下：單鞋表刪除相同值算法PurgevoidPurge(Node<T>*first)(p=first->next;while(p->next)if(p->data==p->next->data)(q=p->next;p->next=q->next,deleteq;)dsep=p->next;)（8）判斷帶頭結點的雙循環鏈表是杳對稱。【解答】設工作指針p和q分別指向循環雙鏈表的開始結點和終端結點，若結點p和結點q的數據域相等,則工作指針p后移，工作指針q前移，直到指針p和指針q指向同?結點（循環雙鏈表中結點個數為奇數）,或結點q成為結點p的前驅（循環雙鏈表中結點個數為偶數）。如圖2-12所示。

圖2-12判斷循環雙鏈表對稱的操作示意圖判斷雙版表對稱算法Equal template<classT>structDulNode(Tdata;DulNode<T>*prior,*next,);template<classT>boolEqual(DulNode<T>*first)(p=first->next,q=first->prior,while(p!=q&&p->prior!=q)if(p->data==q->data){p=p->next;"工作指針p后移

q=q->prior;"工作指針q前移)elsereturn0;return1;學習自測及答案.已知?維數組A采用順序存儲結構，每個元素占用4個存儲單元，第9個元素的地址為144,則第?個元素的地址是()。A108B180C176D112【解答】D.在長度為n的線性表中查找值為x的數據元素的時間復雜度為：()。AO(0)BO(l)CO(n)DO(n2)【解答】C.在一個長度為n的順序表的第i(IWiWn+l)個元素之前插入一個元素，需向后移動()個元素，刪除第i(l<i<n)個元素時，需向前移動()個元素。【解答】n-i+1,n-i.在單鏈表中，除了頭結點以外，任一結點的存儲位置由()指示。【解答】其前趨結點的指針域.當線性表采用順序存儲結構時，其主要特點是()。【解答】邏輯結構中相鄰的結點在存儲結構中仍相鄰.在雙鏈表中，每個結點設置了兩個指針域，其中一個指向()結點，另一個指向()結點。【解答】前驅，后繼.設A是一個線性表(al,a2,...,an),采用順序存儲結構，則在等概率的前提下，平均每插入一個元素需要移動的元素個數為多少？若元素插在ai與ai+1之間(l<i<n)的概率為“6+1)/2 ,則平均每插入一個元素所要移動的元素個數又是多少？【解答】s(M-J+1)=-2-1 2,n俳一力2EF二匕=伽+1)/31=1閥5+1)/2.線性表存放在整型數組ARrrsize］的前elenum個單元中，且遞增有序。編寫算法，將元素x插入到線性表的適當位置上，以保持線性表的有序性，并且分析算法的時間復雜度。【解答】本題是在?個遞增有序表中插入元素x,基本思路是從有序表的尾部開始依次取元素與x比較，若大于x,此元素后移一位，再取它前面一個元素重復上述步驟：否則，找到插入位置，將x插入。具體算法如下：有序順序表插入算法Insert[constintarrsize=100,classSeqList(private:intdata[arrsize];intdenum,public:Insert(intx);)；voidSeqList::Insert(intx)(if(denum==arrsize)throw"overflow'1;dse(i=denum-l;while(i>=l&&x<data[i])(data[i+l]=data[i];if)data[i+l]=x,)}.已知單鏈衣中各結點的元素值為整型且遞增有序，設計算法刪除鏈發中所有大于mink且小于maxk的所有元素，并釋放被刪結點的存儲空間。【解答】因為是在有序單鏈表上的操作，所以，要充分利用其有序性。在單鏈衣中查找第?個大于mink的結點和第一個小于maxk的結點，再將二者間的所有結點刪除。有序鞋表刪除算法DdeteBetween template<classT>voidDeleteBetween(Node<T>*first,intmink,intmaxk)(p=first;while(p->next&&p->next->data<=mink)p=p->next;if(p->next){q=p->next;wMe(q->data<maxk)(u=q->next,p->next=q->next,deleteq,q=u；))).設單循環鏈表LI,對其遍歷的結果是：xl,x2,x3,..?xn-1,xn.請將該循環鏈表拆成兩個單循環鏈表L1和L2,使得L1中含有原L1表中序號為奇數的結點且遍歷結果為：xl,x3,...；L2中含有原L1表中序號為偶數的結點且遍歷結果為：...，x4,x2。【解答】算法如下：彳后壞鞋表拆分算法DePatchtemplate<classT>Node<T>*DePatch(Node<T>*L1)(L2=newNode<T>;L2->next=L2;q=Ll->next;Ll->next=Ll;p=Ll,i=l,while(q!=Ll)(if(i%2=1)(力應用尾插法p->nesrt=q,p=q,p->next=Ll;q=q->next,i++,)dse(L2->next=q,u=q->next;q->next=L2->next;q=u,i++;)J)第3章特殊線性表一棧、隊列和串課后習題講解.填空⑴設有?個空棧，棧頂指針為1000H,現有輸入序列為L2,3、4、5.經過push,push,pop.push,pop.push,push后，輸出序列是（），棧頂指針為（）。【解答】23,1003H⑵棧通常采用的兩種存儲結構是（）；其判定棧空的條件分別是（），判定棧滿的條件分別是（）。【解答】順序存儲結構和鏈接存儲結構（或順序棧和鏈棧），棧頂指針top=-l和top=NULL,棧頂指針top等于數組的長度和內存無可用空間⑶（）可作為實現遞歸函數調用的一種數據結構。【解答】棧【分析】遞歸函數的調用和返回正好符合后進先出性。（4）表達式a*（b+c）-d的后綴發達式是（）.【解答】abc+*d-【分析】將中級表達式變為后綴表達式有?個技巧：將操作數依次寫下來，再將算符插在它的兩個操作數的后面。⑸棧和隊列是兩種特殊的線性表，棧的操作特性是（），隊列的操作特性是（），棧和隊列的主要區別在于（）。【解答】后進先出，先進先出，對插入和刪除操作限定的位置不同（6）循環隊列的引入是為了克服（）。【解答】假溢出⑺數組Q[n]用來表示一個循環隊列，front為隊頭元素的前一個位置，rear為隊尾元素的位置，計算隊列中元素個數的公式為（）.【解答】（rear-front+n）%n【分析】也可以是（rear-front）%n,但rear-front的結果可能是負整數，而對一個負整數求模，其結果在不同的編譯器環境F可能會有所不同。（8）用循環鏈表表示的隊列長度為n,若只設頭指針，則出隊和入隊的時間復雜度分別是（）和（）。【解答】0（1）,0（n）【分析】在帶頭指針的循環鏈表中，出隊即是刪除開始結點，這只需修改相應指針；入隊即是在終端結點的后面插入一個結點，這需要從頭指針開始杳找終端結點的地址。（9）串是一種特殊的線性表，其特殊性體現在（）。【解答】數據元素的類型是一個字符（10）兩個串相等的充分必要條件是（）。【解答】長度相同H.對應位置的字符相等【分析】例如"abc"w"abc","abc"#"bca"。.選擇題（1）若一個棧的輸入序列是1，2,3，…，n,輸出序列的第一個元素是n,則第i個輸出元素是（）。A不確定Bn-iCn-i-1Dn-i+1【解答】D【分析】此時，輸出序列一定是輸入序列的逆序。（2）設棧S和隊列Q的初始狀態為空，元素el、e2、e3、e4、e5、e6依次通過棧S,?個元素出棧后即進入隊列Q,若6個元素出隊的順序是e2、e4、e3、e6、e5、el,則棧S的容量至少應該是（ ）。A6B4C3 D2【解答】C【分析】由于隊列具有先進先出性，所以，此題中隊列形同虛設，即出棧的順序也是e2、e4、e3、e6、e5、el=⑶一個棧的入棧序列是1,2,3,4,5,則棧的不可能的輸出序列是（）。A54321B45321C43512D12345【解答】C【分析】此題有一個技巧：在輸出序列中任意元素后面不能出現比該元素小并且是升序（指的是元素的序號）的兩個元素。⑷設計一個判別表達式中左右括號是否配對的算法，采用（）數據結構最佳A順序表B棧C隊列D鏈發【解答】B【分析】每個右括號與它前面的最后?個沒有匹配的左括號配對，因此具有后進先出性。⑸在解決計算機主機與打印機之間速度不匹配問題時通常設置一個打印緩沖區，該緩沖區應該是一個（）結構。A棧B隊列C數組D線性表【解答】B【分析】先進入打印緩沖區的文件先被打印，因此具有先進先出性。（6）一個隊列的入隊順序是1,2,3,4,則隊列的輸出順序是（）。A4321B1234C1432D3241【解答】B［分析】隊列的入隊順序和出隊順序總是一致的.⑺棧和隊列的主要區別在于（）。A它們的邏輯結構不樣B它們的存儲結構不樣C所包含的運算不一樣D插入、刪除運算的限定不一樣【解答】D【分析】棧和隊列的邏輯結構都是線性的，都有順序存儲和鏈接存儲，有可能包含的運算不一樣，但不是主要區別，任何數據結構在針對具體問題時包含的運算都可能不同。（8）設數組S[n]作為兩個棧S1和S2的存儲空間，對任何一個棧只有當S[n]全滿時才不能進行進棧操作.為這兩個棧分配空間的最佳方案是（）。AS1的棧底位置為0,S2的棧底位置為n-1BS1的棧底位置為0,S2的棧底位置為n/2CS1的棧底位置為0,S2的棧底位置為nDS1的棧底位置為0,S2的棧底位置為1【解答】A【分析】兩棧共享空間首先兩個棧是相向增長的，棧底應該分別指向兩個棧中的第?個元素的位置，并注意C++中的數組下標是從。開始的。⑼設有兩個串p和q，求q在p中首次出現的位置的運算稱作（）。A連接B模式匹配C求子串D求串長【解答】B.判斷題（1）有n個元素依次進棧，則出棧序列有（n-l）/2種。⑵）！【解答】錯。應該有s+D5!）種。⑵棧可以作為實現過程調用的一種數據結構。【解答】對。只要操作滿足后進先出性，都可以采用棧作為輔助數據結構。⑶在棧滿的情況下不能做進棧操作，否則將產生"上溢"。【解答】對。⑷在循環隊列中，front指向隊頭元素的前一個位置，rear指向隊尾元素的位置，則隊滿的條件是front=rear?【解答】錯。這是隊空的判定條件，在循環隊列中要將隊空和隊滿的判定條件區別開。⑸空串與空格串是相同的。【解答】錯。空串的長度為零，而空格串的長度不為0,其長度是中中空格的個數。.設有一個棧，元素進棧的次序為A,B,C,D,E,能否得到如下出棧序列，若能，請寫出操作序列，若不能，請說明原因。（1）C,E,A,B,D⑵C,B.A,D,E【解答】⑴不能，因為在C、E出棧的情況下，A一定在棧中，而且在B的下面，不可能先于B出棧。（2）可以，設I為進棧操作，0為入棧操作，則其操作序列為HI000I0I0.

.舉例說明順序隊列的“假溢出“現象。【解答】假設有一個順序隊列，如圖3-6所示，隊尾指針rear=4,隊頭指針front=L如果再有元素入隊,就會產生”1:溢〃，此時的''上溢"又稱為”假溢出“，因為隊列并不是真的溢出了，存儲隊列的數組中還有2個存儲單元空閑，其卜標分別為。和1。rearfrontrearfront圖3-6順序隊列的假溢出.在操作序列push(l)、push(2)>pop.push(5)>push(7)>pop、push(6)之后，棧頂元素和棧底元素分別是什么？(push(k)表示整數k入棧，pop表示棧頂元素出棧。)【解答】棧頂元素為6,棧底元素為1。其執行過程如圖3-7所示。651(a)push(1)?pushQ)(b)pop?push(5)?push(7) (c)pop?push(6)圖3-7棧的執行過程示意圖.在操作序列EnQueue(l)、EnQueue(3)>DeQueue^EnQueue(5).EnQueue(7)>DeQueueEnQueue(9)之后，隊頭元素和隊尾元素分別是什么？(EnQueue(k)表示整數k入隊，DeQueue表示隊頭元素出隊)。【解答】隊頭元素為5,隊尾元素為9。其執行過程如圖3-8所示。出隊 入隊 J13 」 357 579(a)EnQueue(1)>EnQueueG)(b)DeQueue>EnQueue(5)*EnQueueC7) (c)DeQueue/EnQueue9)圖3-8隊列的執行過程示意圖.空串和空格串有何區別？串中的空格符有何意義？空串在串處理中有何作用？【解答】不含任何字符的串稱為空串，其長度為零。僅含空格的串稱為空格串，它的長度為串中空格符的個數。串中的空格符可用來分隔一般的字符，便于人們識別和閱讀，但計算串長時應包括這些空格符。空串在串處理中可作為任意串的子串。.算法設計⑴假設以不帶頭結點的循環鏈表表示隊列，并且只設一個指針指向隊尾結點，但不設頭指針。試設計相應的入隊和出隊的算法。【解答】出隊操作是在循環鏈表的頭部進行，相當于刪除開始結點，而入隊操作是在循環鏈表的尾部進行,相當于在終端結點之后插入一個結點。由于循環鏈表不帶頭結點，需要處理空表的特殊情況。入隊算法如下：循環隊列入隊算法Enqueue[template<classT>voidEnqueue(Node<T>*rear,Tx)(s=newNode<T>;s-,datav;if(rear-=NULL)( V處理空表的特殊情況rear=s,rear->next=s;)else( 。處理除空表以外的一般情況s->next=rear->next;rear^>next=s,reams,)出隊算法如下:循M隊列出版算』Dequeue]template<classT>TDequeue(Node<T>*rear)(if(rear==NULL)throw"underflow",償！I斷表空else(s=rear->next,if(s==rear)rear=NULL; /犍表中只有一個結點elserear->next=s->next,deletes;})(2)設順序棧S中有2n個元素，從棧頂到棧底的元素依次為a2n,a2n-l，…，al,要求通過一個循環隊列重新排列棧中元素，使得從棧頂到棧底的元素依次為a2n,a2n-2，…，a2,a2n-l,a2n-3，…，al.請設計算法實現該操作，要求空間復雜度和時間復雜度均為O(n)。【解答】操作步驟為：①將所有元素出棧并入隊：②依次將隊列元素出隊，如果是偶數結點，則再入隊，如果是奇數結點，則入棧；③將奇數結點出棧并入隊；④將偶數結點出隊并入棧：⑤將所有元素出棧并入隊；⑥將所有元素出隊并入棧即為所求。⑶用順序存儲結構存儲率S,編寫算法刪除S中第i個字符開始的連續j個字符。【解答】先判斷串S中要刪除的內容是否存在，若存在，則將第i+j-1之后的字符前移j個位置。算法如下:串刪除算法Del voidDeKcharS[],inti,intj)”數組0號單元存放串的長度(if(i+j<S[O])(for(k=i;k<S[0],k++)S[k]=S[k+j];S[O]=S[O]-j;)elsecout<<"參數非法"，}（4）對于采用順序存儲結構的串S,編寫一個函數刪除其值等于ch的所有字符。【解答】從后向前刪除值為ch的所有元素，這樣所有移動的元素中沒有值為ch的元素，能減少移動元素的次數，提高算法的效率。算法如F：串刪除算法DelvoidDel(charS[],charch)儆組的0號單元存放串的長度(for(i=S[0];i>0,i")if(S[i]==ch){forG=i+l；j<=S[0],j++)SU-l]=S[j]；S[Q]—,})⑸對串的模式匹配KMP算法設計求模式滑動位置的next函數。【解答】參見3.2.5學習自測及答案.在一個具有n個單元的順序棧中，假定以地址低端（即卜標為。的單元）作為棧底，以top作為棧頂指針，當出棧時，top的變化為（）。A不變Btop=0;Ctop=top-l;Dtop=top+l;【解答】C.一個棧的入棧序列是a,b,c,d,e,則棧的不可能的出棧序列是()。AedcbaBcdebaCdebcaDabcde【解答】C.從棧頂指針為top的鏈棧中刪除一個結點，用x保存被刪除結點的值，則執行()。Ax=top;top=top->next;Bx=top->data;Ctop=top->next;x=top->data;Dx=top->data;top=top->next;【解答】D.設元素1,2,3,P,A依次經過?個棧，進棧次序為123PA,在棧的輸出序列中，有哪些序列可作為C++程序設計語言的變量名。【解答】PA321,P3A21,P32A1,P321A,AP321.設S="I_am_a_teacther”，其長度為()。【解答】15第4章廣義線性表一多維數組和廣義表課后習題講解.填空⑴數組通常只有兩種運算：()和()，這決定了數組通常采用()結構來實現存儲。【解答】存取，修改，順序存儲【分析】數組是?個具有固定格式和數量的數據集合，在數組上般不能做插入、刪除元素的操作。除了初始化和銷毀之外，在數組中通常只有存取和修改兩種操作.⑵.維數組A中行下標從10到20,列卜標從5到10,按行優先存儲，每個元素占4個存儲單元,A[10][5]的存儲地址是1000,則元素A[15][10]的存儲地址是().【解答】1140【分析】數組A中每行共有6個元素，元素A[15][10]的前面共存儲了(15-10)x6+5個元素，每個元素占4個存儲單元，所以，其存儲地址是1000+140=1140。⑶設有一個10階的對稱矩陣A采用壓縮存儲，A[0][0]為第一個元素，其存儲地址為d,每個元素占1個存儲單元，則元素A[8][5]的存儲地址為()。【解答】d+41【分析】元素A網⑸的前面共存儲了(1+2+...+8)+5=41個元素。⑷稀疏矩陣一般壓縮存儲方法有兩種，分別是()和()。【解答】三元組順序表，十字鏈表(5)廣義表(口),((9),(：)),(6)的長度是(【解答】3.4,(a),((((b),c)),(d))(6)已知廣義表LS=(a,(b,c,d),e),用Head和Tail函數取出LS中原子b的運算是().【解答】Head(Head(Tail(LS))).選擇題⑴二維數組A的每個元素是由6個字符組成的串，行下標的范圍從0?8,列下標的范圍是從。?9,則存放A至少需要( )個字節，A的第8列和第5行共占( )個字節，若A按行優先方式存儲，元素A[8][5]的起始地址與當A按列優先方式存儲時的()元素的起始地址致。A90B180C240D540E108F114G54HA[8][5]IA[3][10]JA[5][8]KA[4][9]【解答】D,E,K【分析】數組A為9行10歹ij,共有90個元素，所以，存放A至少需要90x6=540個存儲單元，第8列和第5行共有18個元素(注意行列有一個交叉元素)，所以，共占108個字節，元素A[8][5]按行優先存儲的起始地址為d+8xl0+5=d+85,設元素按列優先存儲的起始地址與之相同，則d+jx9+i=d+85,解此方程，得此方j=9.⑵將數組稱為隨機存取結構是因為( )A數組元素是隨機的B對數組任一元素的存取時間是相等的C隨時可以對數組進行訪問D數組的存儲結構是不定【解答】B⑶下面的說法41,不正確的是( )A數組是?種線性結構B數組是?種定長的線性結構C除了插入與刪除操作外，數組的基本操作還有存取、修改、檢索和排序等D數組的基本操作有存取、修改、檢索和排序等，沒有插入與刪除操【解答】C【分析】數組屬于廣義線性表，數組被創建以后，其維數和每維中的元素個數是確定的，所以，數組通常沒有插入和刪除操作。⑷對特殊矩陣采用壓縮存儲的口的主要是為了( )A表達變得簡單B對矩陣元素的存取變得簡單C去掉矩陣中的多余元素D減少不必要的存儲空間【解答】Dt分析】在特殊矩陣中，有很多值相同的元素并且他們的分布有規律，沒有必要為值相同的元素重復存儲。⑸下面( )不屬于特殊矩陣。A對角矩陣B三角矩陣C稀疏矩陣D對稱矩陣【解答】C(6)若廣義表A滿足Head(A)=Tail(A),則人為()A()B(())C((),())D((),(),())【解答】B⑺下面的說法中，不正確的是( )A廣義表是一種多層次的結構B廣義表是一種非線性結構C廣義表是一種共享結構D廣義表是一種遞歸【解答】B【分析】從各層元素各自具有的線性關系講，廣義表屬了線性結構。(8)下面的說法中，不正確的是( )A對稱矩陣只須存放包括主對角線元素在內的下(或上)三角的元素即可。B對角矩陣只須存放非零元素即可.C稀疏矩陣中值為零的元素較多，因此可以采用三元組表方法存儲。D稀疏矩陣中大量值為零的元素分布有規律，因此可以采用三元組衣方法存儲【解答】D【分析】稀疏矩陣中大量值為零的元素分布沒有規律，因此采用三元組表存儲。如果零元素的分布有規律,就沒有必要存儲指零元素的行號和列號，而需要按其壓縮規律找出相應的映象函數。.判斷題⑴數組是一種復雜的數據結構，數組元素之間的關系既不是線性的，也不是樹形的。【解答】錯。例如二維數組可以看成是數據元素為線性表的線性表。⑵使用三元組表存儲稀疏矩陣的元素，有時并不能節省存儲空間。【解答】對。因為三元組表除了存儲非零元素值外，還需要存儲其行號和列號。⑶稀疏矩陣壓縮存儲后，必會失去隨機存取功能。【解答】時。因為壓縮存儲后，非零元素的存儲位置和行號、列號之間失去了確定的關系。(4)線性表可以看成是廣義表的特例，如果廣義表中的每個元素都是單元素，則廣義表便成為線性去。【解答】對。⑸若一個廣義表的表頭為空表，則此廣義表亦為空表.【解答】錯.如廣義表L=((),(a,b))的表頭為空表，但L不是空表..一個稀疏矩陣如圖4-4所示，寫出對應的三元組順序表和十字鏈表存儲表示。TOC\o"1-5"\h\z0 0 2 03 0 0 00 0-150 0 0 0圖4-4稀疏矩陣【解答】對應的三元組順序表如圖4-5所示，十字鏈衣如圖4-6所示■

圖4-6稀疏矩降的十字鏈表.已知A為稀疏矩陣，試從空間和時間角度比較采用二維數組和三元組順序表兩種不同的存儲結構完成求運算的優缺點。【解答】設稀疏矩陣為m行n列，如果采用二維數組存儲，其空間復雜度為O(mxn)：因為要將所有的矩陣元素累加起來，所以，需要用一個兩層的嵌套循環，北時間復雜度亦為O(mxn)。如果采用三元組順序表進行壓縮存儲，假設矩陣中有t個非零元素，其空間復雜度為o(t),將所有的矩陣元素累加起來只需將三元組順序表掃描一遍，其時間復雜度亦為O(t)。當t<<mxn時，采用三元組順序表存儲可獲得較好的時、空性能。.設某單位職工工資表ST由'‘工資"、''扣除"和"實發金額"三項組成，其中工資項包括''基本工資"、"津貼"和“獎金”，扣除項包括"水"、''電"和"煤氣"。⑴請用廣義表形式表示所描述的工資表ST,并用表頭和表尾求表中的''獎金"項：⑵畫出該工資表ST的存儲結構。【解答】⑴ST=((基本工資，津貼，獎金)，(水，電，煤氣)，實發金額)Head(Tail(Tail(Head(ST))))=獎金⑵工資表ST的頭尾表示法如圖4-7所示。|1l/八I圖4-7工資表的存儲示意圖7.若在矩陣A中存在一個元素ai,j(OWWn-L0<j<m-l),該元素是第i行元素中最小值且又是第j列元素中最大值，則稱此元素為該矩陣的個馬鞍點.假設以二維數組存儲矩陣A,試設計一個求該矩陣所有馬鞍點的算法，并分析最壞情況下的時間復雜度。【解答】在矩陣中逐行尋找該行中的最小值，然后對其所在的列尋找最大值，如果該列上的最大值與該行上的最小值相等，則說明該元素是鞍點，將它所在行號和列號輸出。具體算法如下:馬鞍點算法Andian|voidAndian(inta[][],intm,intn)(for(i=0;i<n,i++)(d=^[i][0];k=0, //d為第i行中的最小值for(j=l;j<m;j++)if(a[i]U]<d)(d=^[i]UJ；k=j.}qaG][k]為第i行最小值for(j=O;j<n;j++)if(a[j][k]>d)break;if(j==n)cout<〈"輸出鞍點))分析算法，外層for循環共執行n次，內層第一個for循環執行m次，第二個for循環最壞情況下執行n次，所以，最壞情況卜的時間復雜度為0(mn+n2)。學習自測及答案.二維數組M中每個元素的長度是3個字節，行卜,標從0到7.列卜,標從0到9,從首地址d開始存儲。若按行優先方式存儲，元素M[7][5]的起始地址為( )，若按列優先方式存儲，元素M[7][5]的起始地址為( )。【解答】d+22,d+141.一個nxn的對稱矩陣，按行優先或列優先進行壓縮存儲，則其存儲容量為( ).【解答】n(n+l)/2.設n行n列的下三角矩陣A(行列下標均從1開始)已壓縮到一維數組S[l]?S[n(n+l)/2]中，若按行優先存儲，則在數組S中的存儲位置是()。【解答】ix(i-l)/2+j.已知廣義表LS=(a,(b,c),(d,e,a)),運用Head函數和Tail函數取出LS中原子d的運算是( ).【解答】Head(Head(Tail(Tail(LS)))).廣義表(a,b,(c,(d)))的表尾是()。A(d)B(c,(d))Cb,(c,(d))D(b,(c,(d)))【解答】D.設有二對角矩陣Anxn(行、列下標均從。開始)，將其三條對角線上的元素逐行存于數組B[3n-2]中，使得B[k]=aij求：⑴用i,j表示k的下標變換公式；⑵用k表示i,j的下標變換公式.【解答】⑴要求i,j去示k的下標變換公式，就是要求在k之前已經存儲了多少個非零元素，這些非零元素的個數就是k的值。元素aij求所在的行為i,列為j,則在其前面的非零元素的個數是；k=2+3(i-l)+(j-i+1)=2i+j.⑵因為k和i,j之間是一一時應的關系，k+1是當前非零元素的個數，整除即為其所在行號，取余表示當前行中第兒個非零元素，加上前面零元素所在列數就是當前列號，即：fz=(AM-1)/3t;=(M-l)%3+0t+l)/3-l.已知兩個nxn的對稱矩陣按壓縮存儲方法存儲在己維數組A和B中，編寫算法計算對稱矩陣的乘積.【解答】對稱矩陣采用壓縮存儲，乘積矩陣也采用壓縮存儲。注意矩陣元素的表示方法。矩陣乘積算法Mui 1voidMuKintA[],intB[],intC[],intn)(for(i=0,i<n,i++)for(j=0,j<n,j++)(mi=max(i,j),mj=min(i,j);x=mi*(mi-1)/2+mj-l;"計篁矩降元素Cfi][j]壓縮后的存儲地址C[x]=0,far(k=0,k<n;k++)(ul=max(i,k),vl=min(i,k);u2=max(k,j),v2=min(k,j);wl=ul*(ul-l)/2+vl-l,"計算AH囚的存儲地址w2=u2*(u2-l)/2+v2-l;"計苴B因[j]的存儲地址c[x]=A[wl]*B[w2];)}第5章樹和二叉樹課后習題講解i.填空題⑴樹是n(n>0)結點的有限集合，在一棵『空樹中，有()個根結點，其余的結點分成m(m>0)個()的集合，每個集合都是根結點的子樹.【解答】有且僅有一個，互不相交⑵樹中某結點的子樹的個數稱為該結點的()，子樹的根結點稱為該結點的()，該結點稱為其子樹根結點的()。【解答】度，孩子，雙親⑶一棵二叉樹的第i(iNl)層最多有()個結點；一棵有n(n>0)個結點的滿二叉樹共有()個葉子結點和()個非終端結點。【解答】2i-l.(n+l)/2,(n-l)/2【分析】設滿二叉樹中葉子結點的個數為nO,度為2的結點個數為n2,由于滿二叉樹中不存在度為1的結點，所以n=n0+n2；山：叉樹的性質n0=n2+l,得n0=(n+l)/2,n2=(n-l)/2.(4)設高度為h的二叉樹上只有度為0和度為2的結點，該二叉樹的結點數可能達到的最大值是()，最小值是（）。【解答】2h-L2h-l【分析】最小結點個數的情況是第1層有1個結點，其他層上都只有2個結點。⑸深度為k的二叉樹中，所含葉子的個數最多為（）。【解答】2k-l【分析】在滿二叉樹中葉子結點的個數達到最多。（6）具有100個結點的完全二叉樹的葉子結點數為（）。【解答】50【分析】100個結點的完全二叉樹中最后一個結點的編號為100,其雙親即最后一個分支結點的編號為50,也就是說，從編號51開始均為葉子。⑺已知一棵度為3的樹有2個度為1的結點，3個度為2的結點，4個度為3的結點.則該樹中有（）個葉子結點.【解答】12【分析】根據：叉樹性質3的證明過程，有n0=n2+2n3+l（n0,n2>n3分別為葉子結點、度為2的結點和度為3的結點的個數）。（8）某二叉樹的前序遍歷序列是ABCDEFG.中序遍歷序列是CBDAFGE,則其后序遍歷序列是（）■（【解答】CDBGFEA【分析】根據前序遍歷序列和后序遍歷序列將該二叉樹構造出來。⑼在具有n個結點的二叉鏈表中，共有（）個指針域，其中（）個指針域用了指向其左右孩子，剩下的（）個指針域則是空的。【解答】2n,n-1,n+1（1?在有n個葉子的哈夫曼樹中，葉子結點總數為（），分支結點總數為（）。【解答】n,n-1【分析】n-1個分支結點是經過n-1次合并后得到的。2.選擇題⑴如果結點A有3個兄弟，B是A的雙親，則結點B的度是（ ）。A1B2C3D4【解答】D⑵設：叉樹有n個結點，則其深度為（）。An-1BnC"」+1D不能確定【解答】D【分析】此題并沒有指明是完全二叉樹，則其深度最多是n,最少是1°g2T+lo⑶二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是（）的二叉樹。A空或只有一個結點B高度等于其結點數C任一結點無左孩子D任一結點無右孩子【解答】B【分析】此題注意是序列正好相反，則左斜樹和右斜樹均滿足條件。⑷線索二叉樹中某結點R沒有左孩子的充要條件是（ ）。AR.lchild=NULLBR.ltag=OCR.ltag=lDR.rchild=NULL【解答】C【分析】線索二義樹中某結點是否有左孩子，不能通過左指針域是否為空來判斷，而要判斷左標志是否為⑸深度為k的完全;叉樹至少有（）個結點，至多有（）個結點，具有n個結點的完全：叉樹按層序從1開始編號，則編號最小的葉子的序號是（）。A2k-2+lB2k-lC2k-1D2k-l-1E2k+lF2k+l-1G2k-1+1H2k【解答】B,C,A【分析】深度為k的完全二叉樹最少結點數的情況應是第k層上只有1個結點，最多的情況是滿二義樹，編號最小的葉子應該是在結點數最少的情況下，葉子結點的編號。⑹一個高度為h的滿二叉樹共有n個結點，其中有m個葉子結點，則有（）成立。An=h+mBh+m=2nCm=h-lDn=2m-l【解答】D【分析】滿二叉樹中沒有度為1的結點，所以有m個葉子結點，則度為2的結點個數為m-E⑺任何一棵二叉樹的葉子結點在前序、中序、后序遍歷序列中的相對次序（）。A肯定不發生改變B肯定發生改變C不能確定D有時發生變化【解答】A【分析】三種遍歷次序均是先左子樹后石子樹。（8）如果T是由有序樹T轉換而來的二叉樹，那么T中結點的前序序列就是T中結點的（）序列，T中結點的后序序列就是T中結點的（ ）序列。A前序B中序C后序D層序【解答】A,B⑼設森林中有4棵樹，樹中結點的個數依次為nl、n2、n3、n4,則把森林轉換成二叉樹后，其根結點的右子樹上有（）個結點，根結點的左子樹上有（）個結點。Anl-1BnlCnl+n2+n3Dn2+n3+n4【解答】D,A【分析】由森林轉換的二叉樹中，根結點即為第一棵樹的根結點，根結點的左子樹是由第一棵樹中除了根結點以外其余結點組成的，根結點的右子樹是由森林中除第?棵樹外其他樹轉換來的。⑩討論樹、愈林和二叉樹的關系，目的是為了（）。A借助二叉樹上的運算方法去實現時樹的一些運算B將樹、森林按二義樹的存儲方式進行存儲并利用二叉樹的算法解決樹的有關問題C將樹、森林轉換成二叉樹D體現種技巧，沒有什么實際意義【解答】B.判斷題（1）在線索二叉樹中，任一結點均有指向其前趨和后繼的線索。【解答】錯。某結點是否有前驅或后繼的線索，取決于該結點的標志域是杳為1。⑵在：叉樹的前序遍歷序列中，任意一個結點均處在其子女的前面。【解答】對。由前序遍歷的操作定義可知。⑶二叉樹是度為2的樹。【解答】錯。二叉樹和樹是兩種不同的樹結構，例如，左斜樹是棵二又樹，但它的度為1。（4）由樹轉換成二叉樹，其根結點的右子樹總是空的。【解答】對。因為根結點無兄弟結點。⑸用一維數組存儲：叉樹時，總是以前序遍歷存儲結點。【解答】錯。二叉樹的順序存儲結構是按層序存儲的，一般適合存儲完全二叉樹。.證明：對任一滿二叉樹，其分枝數B=2（n0-l）.（其中，nO為終端結點數）【解答】因為在滿二叉樹中沒有度為1的結點，所以有：n=n0+n2設B為樹中分枝數，則n=B+l所以B=nO+n2-l再由二叉樹性質：n0=n2+l代入上式有：B=nO+nO-l-l=2(nO-l).證明：已知一棵二叉樹的前序序列和中序序列，則可唯一確定該二叉樹。【解答】證明采用歸納法。設二叉樹的前序遍歷序列為ala2a3…an,中序遍歷序列為bib2b3…bn.當n=l時，前序遍歷序列為al,中序遍歷序列為bl,二叉樹只有?個根結點，所以，al=bl,可以唯一確定該二叉樹；假設當n<=k時，前序遍歷序列ala2a3...ak和中序遍歷序列bib2b3…bk可唯?確定該二叉樹,下面證明當n=k+l時，前序遍歷序列ala2a3…akak+1和中序遍歷序列bib2b3...bkbk+1可唯一確定一棵二叉樹。在前序遍歷序列中第一個訪問的一定是根結點，即二叉樹的根結點是al,在中序遍歷序列中查找值為al的結點,假設為bi,則al=biILblb2...bi-1是對根結點al的左子樹進行中序遍歷的結果，前序遍歷序列a2a3…ai是對根結點al的左子樹進行前序遍歷的結果，由歸納假設，前序遍歷序列a2a3…ai和中序遍歷序列blb2...bi-1唯一確定了根結點的左子樹,同樣可證前序遍歷序列ai+lai+2...ak+1和中序遍歷序列bi+lbi+2...bk+1唯一確定了根結點的右子樹。.已知一棵度為m的樹中有：nl個度為1的結點，n2個度為2的結點 nm個度為m的結點，問該樹中共有多少個葉子結點？【解答】設該樹的總結點數為n,則n=n0+nl+n2+ +nm又：n=分枝數+l=0xn0+lxnl+2xn2+......+mxnm+l由上述兩式可得：nO=n2+2n3+......+(m-l)nm+l.已知：叉樹的中序和后序序列分別為CBEDAFIGH和CEDBIFHGA,試構造該：叉樹。【解答】二叉樹的構造過程如圖5-12所示。圖5-12構造二叉樹的過程

.對給定的一組權值W=(5,2,9,11,8,3,7),試構造相應的哈夫蛙樹，并計算它的帶權路徑長度。【解答】構造的哈夫曼樹如圖5-13所示.圖5-13構造的哈夫曼樹及帶權路徑長度樹的帶權路徑長度為：WPL=2x4+3x4+5x3+7x3+8x3+9x2+llx2=120.已知某字符串S中共有8種字符，各種字符分別出現2次、1次、4次、5次、7次、3次、4次和9次,對該字符串用［0,1］進行前綴編碼，問該字符串的編碼至少有多少位。【解答】以各字符出現的次數作為葉子結點的權值構造的哈夫蛀編碼樹如圖5-14所示.其帶權路徑長度=2x5+1x5+3x4+5x3+9x2+4x3+4x3+7x2=98,所以，該字符串的編碼長度至少為98位。圖5-14哈夫曼編碼樹.算法設計⑴設計算法求二叉樹的結點個數。【解答】本算法不是要打印每個結點的值，而是求出結點的個數。所以可將遍歷算法中的"訪問"操作改為''計數操作”，將結點的數目累加到一個全局變量中，每個結點累加一次即完成了結點個數的求解。具體算法如E：求二叉樹結點個數算法CouiT]voidCount(BiNode*root)//n為全局量并已初始化為0(if(root){Count(root->lchild);n++;Count(root->rchild);))（2）設計算法按前序次序打印二叉樹中的葉子結點。【解答】本算法的要求與前序遍歷算法既有相同之處，又有不同之處。相同之處是打印次序均為前序，不同之處是此處不是打印每個結點的值，而是打印出其中的葉子結點，即為有條件打印。為此，將前序遍歷算法中的訪問操作改為條件打印即可。算法如下：打印葉子結點算法PreOrder]voidPreOrder(BiNode*root)(if(root)(if(!root->lchild&&!root->rchild)cout<<root->data,PreOrder(root->lchild),PreOrder(root->rchild);}}⑶設計算法求二叉樹的深度。【解答】當二叉樹為空時，深度為0；若二叉樹不為空，深度應是其左右子樹深度的最大值加1,而其左右子樹深度的求解又可通過遞歸調用木算法來完成。具體算法如下：求二叉樹深度算法Depth|intDepth(BiNode*root)(if((root)