數(shù)據(jù)結構課后答案

1、第1章 緒論1簡述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對象、數(shù)據(jù)結構、邏輯結構、存儲結構、抽象數(shù)據(jù)類型。答案：數(shù)據(jù)：是客觀事物的符號表示，指所有能輸入到計算機中并被計算機程序處理的符號的總稱。如數(shù)學計算中用到的整數(shù)和實數(shù)，文本編輯所用到的字符串，多媒體程序處理的圖形、圖像、聲音、動畫等通過特殊編碼定義后的數(shù)據(jù)。數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在計算機中通常作為一個整體進行考慮和處理。在有些情況下，數(shù)據(jù)元素也稱為元素、結點、記錄等。數(shù)據(jù)元素用于完整地描述一個對象，如一個學生記錄，樹中棋盤的一個格局（狀態(tài)）、圖中的一個頂點等。數(shù)據(jù)項：是組成數(shù)據(jù)元素的、有獨立含義的、不可分割的最小單位。例如，學生基本

2、信息表中的學號、姓名、性別等都是數(shù)據(jù)項。數(shù)據(jù)對象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。例如：整數(shù)數(shù)據(jù)對象是集合N=0，±1，±2，字母字符數(shù)據(jù)對象是集合C=A，B，Z， a，b，z，學生基本信息表也可是一個數(shù)據(jù)對象。數(shù)據(jù)結構：是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。換句話說，數(shù)據(jù)結構是帶“結構”的數(shù)據(jù)元素的集合，“結構”就是指數(shù)據(jù)元素之間存在的關系。邏輯結構：從邏輯關系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲無關，是獨立于計算機的。因此，數(shù)據(jù)的邏輯結構可以看作是從具體問題抽象出來的數(shù)學模型。存儲結構：數(shù)據(jù)對象在計算機中的存儲表示，也稱為物理結構。抽象數(shù)據(jù)類型：由用戶定

3、義的，表示應用問題的數(shù)學模型，以及定義在這個模型上的一組操作的總稱。具體包括三部分：數(shù)據(jù)對象、數(shù)據(jù)對象上關系的集合和對數(shù)據(jù)對象的基本操作的集合。2試舉一個數(shù)據(jù)結構的例子，敘述其邏輯結構和存儲結構兩方面的含義和相互關系。答案：例如有一張學生基本信息表，包括學生的學號、姓名、性別、籍貫、專業(yè)等。每個學生基本信息記錄對應一個數(shù)據(jù)元素，學生記錄按順序號排列，形成了學生基本信息記錄的線性序列。對于整個表來說，只有一個開始結點(它的前面無記錄)和一個終端結點(它的后面無記錄)，其他的結點則各有一個也只有一個直接前趨和直接后繼。學生記錄之間的這種關系就確定了學生表的邏輯結構，即線性結構。這些學生記錄在計算機

4、中的存儲表示就是存儲結構。如果用連續(xù)的存儲單元(如用數(shù)組表示)來存放這些記錄，則稱為順序存儲結構；如果存儲單元不連續(xù)，而是隨機存放各個記錄，然后用指針進行鏈接，則稱為鏈式存儲結構。即相同的邏輯結構，可以對應不同的存儲結構。3簡述邏輯結構的四種基本關系并畫出它們的關系圖。答案：（1）集合結構數(shù)據(jù)元素之間除了“屬于同一集合”的關系外，別無其他關系。例如，確定一名學生是否為班級成員，只需將班級看做一個集合結構。（2）線性結構數(shù)據(jù)元素之間存在一對一的關系。例如，將學生信息數(shù)據(jù)按照其入學報到的時間先后順序進行排列，將組成一個線性結構。（3）樹結構數(shù)據(jù)元素之間存在一對多的關系。例如，在班級的管理體系中，班

5、長管理多個組長，每位組長管理多名組員，從而構成樹形結構。（4）圖結構或網(wǎng)狀結構數(shù)據(jù)元素之間存在多對多的關系。例如，多位同學之間的朋友關系，任何兩位同學都可以是朋友，從而構成圖形結構或網(wǎng)狀結構。其中樹結構和圖結構都屬于非線性結構。 四類基本邏輯結構關系圖4存儲結構由哪兩種基本的存儲方法實現(xiàn)？答案：（1）順序存儲結構順序存儲結構是借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關系，通常借助程序設計語言的數(shù)組類型來描述。（2）鏈式存儲結構順序存儲結構要求所有的元素依次存放在一片連續(xù)的存儲空間中，而鏈式存儲結構，無需占用一整塊存儲空間。但為了表示結點之間的關系，需要給每個結點附加指針字段，用于存

6、放后繼元素的存儲地址。所以鏈式存儲結構通常借助于程序設計語言的指針類型來描述。5選擇題（1）在數(shù)據(jù)結構中，從邏輯上可以把數(shù)據(jù)結構分成（ ）。A動態(tài)結構和靜態(tài)結構 B緊湊結構和非緊湊結構C線性結構和非線性結構 D內(nèi)部結構和外部結構答案：C（2）與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關的是數(shù)據(jù)的（ ）。A存儲結構 B存儲實現(xiàn)C邏輯結構 D運算實現(xiàn)答案：C（3）通常要求同一邏輯結構中的所有數(shù)據(jù)元素具有相同的特性，這意味著（ ）。 A數(shù)據(jù)具有同一特點B不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，而且對應數(shù)據(jù)項的類型要一致C每個數(shù)據(jù)元素都一樣D數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等答案：B（4）以下說法正

7、確的是（ ）。A數(shù)據(jù)元素是數(shù)據(jù)的最小單位B數(shù)據(jù)項是數(shù)據(jù)的基本單位C數(shù)據(jù)結構是帶有結構的各數(shù)據(jù)項的集合D一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結構答案：D解釋：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，數(shù)據(jù)項是數(shù)據(jù)的最小單位，數(shù)據(jù)結構是帶有結構的各數(shù)據(jù)元素的集合。（5）算法的時間復雜度取決于（ ）。A問題的規(guī)模B待處理數(shù)據(jù)的初態(tài)C計算機的配置DA和B答案：D解釋：算法的時間復雜度不僅與問題的規(guī)模有關，還與問題的其他因素有關。如某些排序的算法，其執(zhí)行時間與待排序記錄的初始狀態(tài)有關。為此，有時會對算法有最好、最壞以及平均時間復雜度的評價。（6）以下數(shù)據(jù)結構中，（ ）是非線性數(shù)據(jù)結構A樹 B字符串 C隊列 D棧答案

8、：A6試分析下面各程序段的時間復雜度。（1）x=90; y=100; while(y>0)if(x>100) x=x-10;y-;else x+;答案：O(1)解釋：程序的執(zhí)行次數(shù)為常數(shù)階。（2）for (i=0; i<n; i+)for (j=0; j<m; j+)aij=0;答案：O(m*n)解釋：語句aij=0;的執(zhí)行次數(shù)為m*n。（3）s=0; for i=0; i<n; i+)for(j=0; j<n; j+) s+=Bij;sum=s;答案：O(n2)解釋：語句s+=Bij;的執(zhí)行次數(shù)為n2。（4）i=1; while(i<=n)

9、 i=i*3;答案：O(log3n) 解釋：語句i=i*3;的執(zhí)行次數(shù)為 ëlog3nû。（5）x=0;for(i=1; i<n; i+) for (j=1; j<=n-i; j+)x+;答案：O(n2)解釋：語句x+;的執(zhí)行次數(shù)為n-1+n-2+1= n(n-1)/2。（6）x=n; /n>1y=0;while(x(y+1)* (y+1) y+;答案：O()解釋：語句y+;的執(zhí)行次數(shù)為 ëû。第2章 線性表1選擇題（1）順序表中第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（ ）。A110

10、B108 C100 D120答案：B解釋：順序表中的數(shù)據(jù)連續(xù)存儲，所以第5個元素的地址為：100+2*4=108。（2）在n個結點的順序表中，算法的時間復雜度是O(1)的操作是（ ）。A訪問第i個結點（1in）和求第i個結點的直接前驅(qū)（2in） B在第i個結點后插入一個新結點（1in）C刪除第i個結點（1in）D將n個結點從小到大排序答案：A解釋：在順序表中插入一個結點的時間復雜度都是O(n2)，排序的時間復雜度為O(n2)或O(nlog2n)。順序表是一種隨機存取結構，訪問第i個結點和求第i個結點的直接前驅(qū)都可以直接通過數(shù)組的下標直接定位，時間復雜度是O(1)。（3） 向一個有127個元素的

11、順序表中插入一個新元素并保持原來順序不變，平均要移動 的元素個數(shù)為（ ）。A8 B63.5 C63 D7答案：B解釋：平均要移動的元素個數(shù)為：n/2。（4）鏈接存儲的存儲結構所占存儲空間（ ）。A分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針B只有一部分，存放結點值C只有一部分，存儲表示結點間關系的指針D分兩部分，一部分存放結點值，另一部分存放結點所占單元數(shù)答案：A（5）線性表若采用鏈式存儲結構時，要求內(nèi)存中可用存儲單元的地址（ ）。A必須是連續(xù)的 B部分地址必須是連續(xù)的C一定是不連續(xù)的 D連續(xù)或不連續(xù)都可以答案：D（6）線性表在（ ）情況下適用于使用鏈式結構實現(xiàn)。A需經(jīng)常修改中

12、的結點值 需不斷對進行刪除插入 C中含有大量的結點 中結點結構復雜答案：B解釋：鏈表最大的優(yōu)點在于插入和刪除時不需要移動數(shù)據(jù)，直接修改指針即可。（7）單鏈表的存儲密度（ ）。A大于1 B等于1 C小于1 D不能確定答案：C解釋：存儲密度是指一個結點數(shù)據(jù)本身所占的存儲空間和整個結點所占的存儲空間之比，假設單鏈表一個結點本身所占的空間為D，指針域所占的空間為N，則存儲密度為：D/(D+N)，一定小于1。（8）將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是（ ）。An B2n-1 C2n Dn-1答案：A解釋：當?shù)谝粋€有序表中所有的元素都小于（或大于）第二個表中的元素，只需要用第二個

13、表中的第一個元素依次與第一個表的元素比較，總計比較n次。（9）在一個長度為n的順序表中，在第i個元素（1in+1）之前插入一個新元素時須向后移動（ ）個元素。An-i Bn-i+1 Cn-i-1 DI答案：B(10) 線性表L=(a1，a2,an)，下列說法正確的是（ ）。A每個元素都有一個直接前驅(qū)和一個直接后繼B線性表中至少有一個元素C表中諸元素的排列必須是由小到大或由大到小D除第一個和最后一個元素外，其余每個元素都有一個且僅有一個直接前驅(qū)和直接后繼。答案：D(11) 創(chuàng)建一個包括n個結點的有序單鏈表的時間復雜度是（ ）。AO(1) BO(n) CO(n2) DO(nlog2n)答案：C解釋

14、：單鏈表創(chuàng)建的時間復雜度是O(n)，而要建立一個有序的單鏈表，則每生成一個新結點時需要和已有的結點進行比較，確定合適的插入位置，所以時間復雜度是O(n2)。(12) 以下說法錯誤的是（ ）。A求表長、定位這兩種運算在采用順序存儲結構時實現(xiàn)的效率不比采用鏈式存儲結構時實現(xiàn)的效率低B順序存儲的線性表可以隨機存取C由于順序存儲要求連續(xù)的存儲區(qū)域，所以在存儲管理上不夠靈活D線性表的鏈式存儲結構優(yōu)于順序存儲結構答案：D解釋：鏈式存儲結構和順序存儲結構各有優(yōu)缺點，有不同的適用場合。(13) 在單鏈表中，要將s所指結點插入到p所指結點之后，其語句應為（ ）。As->next=p+1; p->ne

15、xt=s;B(*p).next=s; (*s).next=(*p).next;Cs->next=p->next; p->next=s->next;Ds->next=p->next; p->next=s; 答案：D (14) 在雙向鏈表存儲結構中，刪除p所指的結點時須修改指針（ ）。Ap->next->prior=p->prior; p->prior->next=p->next;Bp->next=p->next->next; p->next->prior=p;Cp->prior-&g

16、t;next=p; p->prior=p->prior->prior;Dp->prior=p->next->next; p->next=p->prior->prior;答案：A(15) 在雙向循環(huán)鏈表中，在p指針所指的結點后插入q所指向的新結點，其修改指針的操作是（ ）。Ap->next=q; q->prior=p; p->next->prior=q; q->next=q;Bp->next=q; p->next->prior=q; q->prior=p; q->next=p->

17、;next;Cq->prior=p; q->next=p->next; p->next->prior=q; p->next=q;Dq->prior=p; q->next=p->next; p->next=q; p->next->prior=q;答案：C第3章 棧和隊列1選擇題（1）若讓元素1，2，3，4，5依次進棧，則出棧次序不可能出現(xiàn)在（ ）種情況。A5，4，3，2，1 B2，1，5，4，3 C4，3，1，2，5 D2，3，5，4，1答案：C解釋：棧是后進先出的線性表，不難發(fā)現(xiàn)C選項中元素1比元素2先出棧，違背了棧的后進

18、先出原則，所以不可能出現(xiàn)C選項所示的情況。（2）若已知一個棧的入棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1=n，則pi為（ ）。Ai Bn-i Cn-i+1 D不確定答案：C解釋：棧是后進先出的線性表，一個棧的入棧序列是1，2，3，n，而輸出序列的第一個元素為n，說明1，2，3，n一次性全部進棧，再進行輸出，所以p1=n，p2=n-1，pi=n-i+1。（3）數(shù)組用來表示一個循環(huán)隊列，為當前隊列頭元素的前一位置，為隊尾元素的位置，假定隊列中元素的個數(shù)小于，計算隊列中元素個數(shù)的公式為（ ）。Ar-f B(n+f-r)%n Cn+r-f D（n+r-f)%n答案：D解釋：對

19、于非循環(huán)隊列，尾指針和頭指針的差值便是隊列的長度，而對于循環(huán)隊列，差值可能為負數(shù)，所以需要將差值加上MAXSIZE（本題為n），然后與MAXSIZE（本題為n）求余，即（n+r-f)%n。（4）鏈式棧結點為：(data,link)，top指向棧頂.若想摘除棧頂結點，并將刪除結點的值保存到x中,則應執(zhí)行操作（ ）。Ax=top->data;top=top->link； Btop=top->link;x=top->link； Cx=top;top=top->link； Dx=top->link；答案：A解釋：x=top->data將結點的值保存到x中，to

20、p=top->link棧頂指針指向棧頂下一結點，即摘除棧頂結點。（5）設有一個遞歸算法如下        int fact(int n)   /n大于等于0             if(n<=0) return 1;             else return n*fact(n-1);

21、60;       則計算fact(n)需要調(diào)用該函數(shù)的次數(shù)為（ ）。 A n+1       B n-1      C n      D n+2答案：A解釋：特殊值法。設n=0，易知僅調(diào)用一次fact(n)函數(shù)，故選A。（6）棧在 （ ）中有所應用。A遞歸調(diào)用 B函數(shù)調(diào)用 C表達式求值 D前三個選項都有答案：D解釋：遞歸調(diào)用、函數(shù)調(diào)用、表達式求值均用到了棧

22、的后進先出性質(zhì)。（7）為解決計算機主機與打印機間速度不匹配問題，通常設一個打印數(shù)據(jù)緩沖區(qū)。主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結構應該是（ ）。A隊列 B棧 C 線性表 D有序表答案：A解釋：解決緩沖區(qū)問題應利用一種先進先出的線性表，而隊列正是一種先進先出的線性表。（8）設棧S和隊列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次進入棧S，一個元素出棧后即進入Q，若6個元素出隊的序列是e2、e4、e3、e6、e5和e1，則棧S的容量至少應該是（）。A2 B3 C4 D 6答案：B解釋：元素出隊的序列是e2、e4、e3、e6、e5和e

23、1，可知元素入隊的序列是e2、e4、e3、e6、e5和e1，即元素出棧的序列也是e2、e4、e3、e6、e5和e1，而元素e1、e2、e3、e4、e5和e6依次進入棧，易知棧S中最多同時存在3個元素，故棧S的容量至少為3。（9）若一個棧以向量V1.n存儲，初始棧頂指針top設為n+1，則元素x進棧的正確操作是( )。Atop+; Vtop=x;BVtop=x; top+;Ctop-; Vtop=x;DVtop=x; top-;答案：C解釋：初始棧頂指針top為n+1，說明元素從數(shù)組向量的高端地址進棧，又因為元素存儲在向量空間V1.n中，所以進棧時top指針先下移變?yōu)閚，之后將元素x存儲在Vn。

24、（10）設計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用（）數(shù)據(jù)結構最佳。A線性表的順序存儲結構 B隊列 C. 線性表的鏈式存儲結構 D. 棧答案：D解釋：利用棧的后進先出原則。（11）用鏈接方式存儲的隊列，在進行刪除運算時（）。A. 僅修改頭指針 B. 僅修改尾指針C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改答案：D解釋：一般情況下只修改頭指針，但是，當刪除的是隊列中最后一個元素時，隊尾指針也丟失了，因此需對隊尾指針重新賦值。（12）循環(huán)隊列存儲在數(shù)組A0.m中，則入隊時的操作為（）。A. rear=rear+1 B. rear=(rear+1)%(m-1) C. rear=

25、(rear+1)%m D. rear=(rear+1)%(m+1) 答案：D解釋：數(shù)組A0.m中共含有m+1個元素，故在求模運算時應除以m+1。（13）最大容量為n的循環(huán)隊列，隊尾指針是rear，隊頭是front，則隊空的條件是（）。 A. (rear+1)%n=front B. rear=front Crear+1=front D. (rear-l)%n=front答案：B解釋：最大容量為n的循環(huán)隊列，隊滿條件是(rear+1)%n=front，隊空條件是rear=front。（14）棧和隊列的共同點是（）。A. 都是先進先出 B. 都是先進后出 C. 只允許在端點處插入和刪除元素 D. 沒

26、有共同點答案：C解釋：棧只允許在棧頂處進行插入和刪除元素，隊列只允許在隊尾插入元素和在隊頭刪除元素。（15）一個遞歸算法必須包括（）。A. 遞歸部分 B. 終止條件和遞歸部分C. 迭代部分 D. 終止條件和迭代部分答案：B第4章 串、數(shù)組和廣義表1選擇題（1）串是一種特殊的線性表，其特殊性體現(xiàn)在（ ）。 A可以順序存儲 B數(shù)據(jù)元素是一個字符 C可以鏈式存儲 D數(shù)據(jù)元素可以是多個字符若 答案：B（2）串下面關于串的的敘述中，（ ）是不正確的？ A串是字符的有限序列 B空串是由空格構成的串C模式匹配是串的一種重要運算 D串既可以采用順序存儲，也可以采用鏈式存儲答案：B解釋：空格常常是串的字符集合中

27、的一個元素，有一個或多個空格組成的串成為空格串，零個字符的串成為空串，其長度為零。 （3）串“ababaaababaa”的next數(shù)組為（ ）。A012345678999 B012121111212 C011234223456 D0123012322345答案：C（4）串“ababaabab”的nextval為（ ）。A010104101 B010102101 C010100011 D010101011 答案：A（5）串的長度是指（ ）。A串中所含不同字母的個數(shù) B串中所含字符的個數(shù)C串中所含不同字符的個數(shù) D串中所含非空格字符的個數(shù)答案：B解釋：串中字符的數(shù)目稱為串的長度。（6）假設以行序為

28、主序存儲二維數(shù)組A=array1.100,1.100，設每個數(shù)據(jù)元素占2個存儲單元，基地址為10，則LOC5,5=（ ）。A808 B818 C1010 D1020答案：B解釋：以行序為主，則LOC5,5=（5-1）*100+（5-1）*2+10=818。（7）設有數(shù)組Ai,j，數(shù)組的每個元素長度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當用以列為主存放時，元素A5,8的存儲首地址為（ ）。ABA+141 BBA+180 CBA+222 DBA+225答案：B解釋：以列序為主，則LOC5,8=（8-1）*8+（5-1）*3+BA=BA+180。（8）設有一個

29、10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一元素，其存儲地址為1，每個元素占一個地址空間，則a85的地址為（ ）。A13 B32 C33 D40答案：C（9）若對n階對稱矩陣A以行序為主序方式將其下三角形的元素(包括主對角線上所有元素)依次存放于一維數(shù)組B1.(n(n+1)/2中，則在B中確定aij（i<j）的位置k的關系為（ ）。Ai*(i-1)/2+j Bj*(j-1)/2+i Ci*(i+1)/2+j Dj*(j+1)/2+i答案：B（10）二維數(shù)組A的每個元素是由10個字符組成的串，其行下標i=0,1,8,列下標j=1,2,10。若A按行先存儲，元素A8,5

30、的起始地址與當A按列先存儲時的元素（ ）的起始地址相同。設每個字符占一個字節(jié)。AA8,5 BA3,10 C. A5,8 DA0,9答案：B解釋：設數(shù)組從內(nèi)存首地址M開始順序存放，若數(shù)組按行先存儲，元素A8,5的起始地址為：M+（8-0）*10+（5-1）*1=M+84；若數(shù)組按列先存儲，易計算出元素A3,10的起始地址為：M+（10-1）*9+（3-0）*1=M+84。故選B。（11）設二維數(shù)組A1. m，1. n（即m行n列）按行存儲在數(shù)組B1. m*n中，則二維數(shù)組元素Ai,j在一維數(shù)組B中的下標為（ ）。A(i-1)*n+j B(i-1)*n+j-1 Ci*(j-1) Dj*m+i-1答

31、案：A解釋：特殊值法。取i=j=1，易知A1,1的的下標為1，四個選項中僅有A選項能確定的值為1，故選A。（12）數(shù)組A0.4,-1.-3,5.7中含有元素的個數(shù)（ ）。A55 B45 C36 D16答案：B解釋：共有5*3*3=45個元素。（13）廣義表A=(a,b,(c,d),(e,(f,g)，則Head(Tail(Head(Tail(Tail(A)的值為（ ）。A(g) B(d) Cc Dd答案：D解釋：Tail(A)=(b,(c,d),(e,(f,g)；Tail(Tail(A)=( (c,d),(e,(f,g)； Head(Tail(Tail(A)= (c,d)；Tail(Head(T

32、ail(Tail(A)=(d)；Head(Tail(Head(Tail(Tail(A)=d。（14）廣義表(a,b,c,d)的表頭是（ ），表尾是（ ）。Aa B( ) C(a,b,c,d) D(b,c,d)答案：C、B解釋：表頭為非空廣義表的第一個元素，可以是一個單原子，也可以是一個子表，(a,b,c,d)的表頭為一個子表(a,b,c,d)；表尾為除去表頭之外，由其余元素構成的表，表為一定是個廣義表，(a,b,c,d)的表尾為空表( )。（15）設廣義表L=(a,b,c)，則L的長度和深度分別為（ ）。A1和1 B1和3 C1和2 D2和3 答案：C解釋：廣義表的深度是指廣義表中展開后所含括

33、號的層數(shù)，廣義表的長度是指廣義表中所含元素的個數(shù)。根據(jù)定義易知L的長度為1，深度為2。2應用題 （1）已知模式串t=abcaabbabcab寫出用KMP法求得的每個字符對應的next和nextval函數(shù)值。答案：模式串t的next和nextval值如下：j1 2 3 4 5 6 7 8 9 10 11 12 t串a(chǎn) b c a a b b a b c a bnextj0 1 1 1 2 2 3 1 2 3 4 5nextvalj0 1 1 0 2 1 3 0 1 1 0 5（2）設目標為t=“abcaabbabcabaacbacba”,模式為p=“abcabaa” 計算模式p的naxtval函

34、數(shù)值； 不寫出算法,只畫出利用KMP算法進行模式匹配時每一趟的匹配過程。答案： p的nextval函數(shù)值為0110132。（p的next函數(shù)值為0111232）。 利用KMP(改進的nextval)算法，每趟匹配過程如下： 第一趟匹配： abcaabbabcabaacbacba abcab(i=5,j=5) 第二趟匹配： abcaabbabcabaacbacba abc(i=7,j=3) 第三趟匹配： abcaabbabcabaacbacba a(i=7,j=1) 第四趟匹配： abcaabbabcabaac bacba (成功) abcabaa(i=15,j=8)（3）數(shù)組A中，每個元素Ai

35、,j的長度均為32個二進位,行下標從-1到9，列下標從1到11，從首地址S開始連續(xù)存放主存儲器中，主存儲器字長為16位。求： 存放該數(shù)組所需多少單元？ 存放數(shù)組第4列所有元素至少需多少單元？ 數(shù)組按行存放時，元素A7,4的起始地址是多少？ 數(shù)組按列存放時，元素A4,7的起始地址是多少？答案：每個元素32個二進制位，主存字長16位，故每個元素占2個字長，行下標可平移至1到11。（1）242 （2）22 （3）s+182 （4）s+142(4)請將香蕉banana用工具 H( )Head( )，T( )Tail( )從L中取出。L=(apple,(orange,(strawberry,(banan

36、a),peach),pear)答案：H（H（T（H（T（H（T（L）第5章 樹和二叉樹1選擇題（1）把一棵樹轉換為二叉樹后，這棵二叉樹的形態(tài)是（ ）。 A唯一的 有多種C有多種，但根結點都沒有左孩子 有多種，但根結點都沒有右孩子答案：A 解釋：因為二叉樹有左孩子、右孩子之分，故一棵樹轉換為二叉樹后，這棵二叉樹的形態(tài)是唯一的。（2）由3個結點可以構造出多少種不同的二叉樹？（ ）A2 B3 C4 D5 答案：D解釋：五種情況如下： （3）一棵完全二叉樹上有1001個結點，其中葉子結點的個數(shù)是（ ）。A250 B 500 C254 D501 答案：D解釋：設度為0結點（葉子結點）個數(shù)為A，度為1的結

37、點個數(shù)為B，度為2的結點個數(shù)為C，有A=C+1，A+B+C=1001，可得2C+B=1000，由完全二叉樹的性質(zhì)可得B=0或1，又因為C為整數(shù)，所以B=0，C=500，A=501，即有501個葉子結點。（4）一個具有1025個結點的二叉樹的高h為（ ）。A11 B10 C11至1025之間 D10至1024之間答案：C解釋：若每層僅有一個結點，則樹高h為1025；且其最小樹高為 ëlog21025û + 1=11，即h在11至1025之間。（5）深度為h的滿m叉樹的第k層有（ ）個結點。(1=<k=<h) Amk-1 Bmk-1 C

38、mh-1 Dmh-1答案：A解釋：深度為h的滿m叉樹共有mh-1個結點，第k層有mk-1個結點。（6）利用二叉鏈表存儲樹，則根結點的右指針是（ ）。A指向最左孩子 B指向最右孩子 C空 D非空答案：C解釋：利用二叉鏈表存儲樹時，右指針指向兄弟結點，因為根節(jié)點沒有兄弟結點，故根節(jié)點的右指針指向空。（7）對二叉樹的結點從1開始進行連續(xù)編號，要求每個結點的編號大于其左、右孩子的編號，同一結點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用（ ）遍歷實現(xiàn)編號。A先序 B. 中序 C. 后序 D. 從根開始按層次遍歷答案：C解釋：根據(jù)題意可知按照先左孩子、再右孩子、最后雙親結點的順序遍歷二叉樹，即

39、后序遍歷二叉樹。（8）若二叉樹采用二叉鏈表存儲結構，要交換其所有分支結點左、右子樹的位置，利用（ ）遍歷方法最合適。A前序 B中序 C后序 D按層次答案：C解釋：后續(xù)遍歷和層次遍歷均可實現(xiàn)左右子樹的交換，不過層次遍歷的實現(xiàn)消耗比后續(xù)大，后序遍歷方法最合適。（9）在下列存儲形式中，（ ）不是樹的存儲形式？A雙親表示法 B孩子鏈表表示法 C孩子兄弟表示法 D順序存儲表示法答案：D解釋：樹的存儲結構有三種：雙親表示法、孩子表示法、孩子兄弟表示法，其中孩子兄弟表示法是常用的表示法，任意一棵樹都能通過孩子兄弟表示法轉換為二叉樹進行存儲。（10）一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二

40、叉樹一定滿足（ ）。A所有的結點均無左孩子 B所有的結點均無右孩子C只有一個葉子結點 D是任意一棵二叉樹答案：C解釋：因為先序遍歷結果是“中左右”，后序遍歷結果是“左右中”，當沒有左子樹時，就是“中右”和“右中”；當沒有右子樹時，就是“中左”和“左中”。則所有的結點均無左孩子或所有的結點均無右孩子均可，所以A、B不能選，又所有的結點均無左孩子與所有的結點均無右孩子時，均只有一個葉子結點，故選C。（11）設哈夫曼樹中有199個結點，則該哈夫曼樹中有（ ）個葉子結點。A99B100 C101D102答案：B解釋：在哈夫曼樹中沒有度為1的結點，只有度為0（葉子結點）和度為2的結點。設葉子結點的個數(shù)為

41、n0，度為2的結點的個數(shù)為n2，由二叉樹的性質(zhì)n0=n2+1，則總結點數(shù)n= n0+n2=2*n0-1，得到n0=100。（12）若X是二叉中序線索樹中一個有左孩子的結點，且X不為根，則X的前驅(qū)為（ ）。AX的雙親 BX的右子樹中最左的結點 CX的左子樹中最右結點 DX的左子樹中最右葉結點答案：C（13）引入二叉線索樹的目的是（ ）。A加快查找結點的前驅(qū)或后繼的速度 B為了能在二叉樹中方便的進行插入與刪除C為了能方便的找到雙親 D使二叉樹的遍歷結果唯一答案：A（14）設F是一個森林，B是由F變換得的二叉樹。若F中有n個非終端結點，則B中右指針域為空的結點有（ ）個。An1BnCn + 1Dn

42、+ 2答案：C（15）n（n2）個權值均不相同的字符構成哈夫曼樹，關于該樹的敘述中，錯誤的是（ ）。A該樹一定是一棵完全二叉樹B樹中一定沒有度為1的結點C樹中兩個權值最小的結點一定是兄弟結點D樹中任一非葉結點的權值一定不小于下一層任一結點的權值答案：A解釋：哈夫曼樹的構造過程是每次都選取權值最小的樹作為左右子樹構造一棵新的二叉樹，所以樹中一定沒有度為1的結點、兩個權值最小的結點一定是兄弟結點、任一非葉結點的權值一定不小于下一層任一結點的權值。2應用題（1）試找出滿足下列條件的二叉樹 先序序列與后序序列相同 中序序列與后序序列相同 先序序列與中序序列相同 中序序列與層次遍歷序列相同答案

43、：先序遍歷二叉樹的順序是“根左子樹右子樹”，中序遍歷“左子樹根右子樹”，后序遍歷順序是：“左子樹右子樹根，根據(jù)以上原則有 或為空樹，或為只有根結點的二叉樹  或為空樹，或為任一結點至多只有左子樹的二叉樹  或為空樹，或為任一結點至多只有右子樹的二叉樹 或為空樹，或為任一結點至多只有右子樹的二叉樹（2）設一棵二叉樹的先序序列： A B D F C E G H ，中序序列： B F D A G E H C畫出這棵二叉樹。畫出這棵二叉樹的后序線索樹。將這棵二叉樹轉換成對應的樹（或森林）。答案： ABFDCEHG      

44、;   （3） 假設用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。 試為這8個字母設計赫夫曼編碼。 試設計另一種由二進制表示的等長編碼方案。 對于上述實例，比較兩種方案的優(yōu)缺點。答案：方案1；哈夫曼編碼先將概率放大100倍，以方便構造哈夫曼樹。 w=7,19,2,6,32,3,21,10，按哈夫曼規(guī)則：【（2,3），6, (7,10)】, 19, 21, 32（100）（40） （60）19 21 32 （28）（17） （11） 7 10 6 （5） 2 3 0 1 0 1 0

45、119 21 32 0 10 1 0 17 10 6 0 12 3 方案比較：字母編號對應編碼出現(xiàn)頻率10000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10字母編號對應編碼出現(xiàn)頻率111000.072000.193111100.02411100.065100.326111110.037010.21811010.10方案1的WPL2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61方案2的WPL3(0.19+0.32+0.21+0.07+0

46、.06+0.10+0.02+0.03)=3結論：哈夫曼編碼優(yōu)于等長二進制編碼 （4）已知下列字符A、B、C、D、E、F、G的權值分別為3、12、7、4、2、8，11，試填寫出其對應哈夫曼樹HT的存儲結構的初態(tài)和終態(tài)。答案： weightparentlchildrchild13000212000370004400052000680007110008 0009 00010 00011 00012 00013 000初態(tài): 終態(tài)： weightparentlchildrchild13800212120037100044900528006810007111100859519911481015123611201397122713210134701112第6章 圖1選擇題（1）在一個圖中，所有頂點的度數(shù)之和等于圖的邊數(shù)的（ ）倍。 A1/2 B1 C2 D4 答案：C（2）在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（ ）倍。 A1/2 B1 C2 D4 答案：B解釋：有向圖所有頂點入度之和等于所有頂點出度之和。（3）具有n個頂點的有向