數(shù)據(jù)結(jié)構(gòu)課后.doc

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

2、本信息表中的學(xué)號、姓名、性別等都是數(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 ，學(xué)生基本信息表也可是一個數(shù)據(jù)對象。數(shù)據(jù)結(jié)構(gòu) ：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。換句話說，數(shù)據(jù)結(jié)構(gòu)是帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合， “結(jié)構(gòu)”就是指數(shù)據(jù)元素之間存在的關(guān)系。邏輯結(jié)構(gòu) ：從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲無關(guān)，是獨立于計算機的。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學(xué)模型。存儲結(jié)構(gòu)： 數(shù)據(jù)對象在計算機中的存儲表示，也稱為物理結(jié)構(gòu) 。抽象

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

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

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

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

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

8、結(jié)構(gòu)中， （A樹B字符串）是非線性數(shù)據(jù)結(jié)構(gòu)C隊列D棧答案： A6試分析下面各程序段的時間復(fù)雜度。（ 1） x=90; y=100; while(y0)if(x100) x=x-10;y-;else x+;答案： O(1)解釋：程序的執(zhí)行次數(shù)為常數(shù)階。（ 2） for (i=0; in; i+) for (j=0; jm; j+)aij=0;答案： O(m*n)解釋：語句 aij=0;的執(zhí)行次數(shù)為 m*n。（3） s=0;for i=0; in; i+)for(j=0; jn; j+)s+=Bij;sum=s;答案： O(n2)解釋：語句 s+=Bij;的執(zhí)行次數(shù)為2n 。（4） i=1;whi

9、le(i=n)i=i*3;答案： O(log解釋：語句3n) i=i*3;的執(zhí)行次數(shù)為log 3n。（5） x=0;for(i=1; in; i+)for (j=1; j1 y=0;while(x (y+1)* (y+1)y+;答案： O(n )解釋：語句y+; 的執(zhí)行次數(shù)為n。第 2 章線性表1選擇題（1）順序表中第一個元素的存儲地址是100 ，每個元素的長度為2，則第5 個元素的地址是（）。A 110B 108C 100D120答案： B解釋：順序表中的數(shù)據(jù)連續(xù)存儲，所以第5 個元素的地址為：100+2*4=108 。（2）在n 個結(jié)點的順序表中，算法的時間復(fù)雜度是O(1)的操作是（）。A

10、訪問第i 個結(jié)點（ 1 i n）和求第B在第 i 個結(jié)點后插入一個新結(jié)點（C刪除第i 個結(jié)點（ 1 i n）D將 n 個結(jié)點從小到大排序i 個結(jié)點的直接前驅(qū)（ 1 i n）2 in ）答案：A解釋：在順序表中插入一個結(jié)點的時間復(fù)雜度都是O(n2)，排序的時間復(fù)雜度為O(n2)或 O(nlog2n)。順序表是一種隨機存取結(jié)構(gòu)，訪問第i 個結(jié)點和求第i 個結(jié)點的直接前驅(qū)都可以直接通過數(shù)組的下標直接定位，時間復(fù)雜度是O(1)。（3） 向一個有 127 個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動的元素個數(shù)為（）。A 8B 63.5C 63D 7答案： B解釋：平均要移動的元素個數(shù)為：

11、n/2。（4）鏈接存儲的存儲結(jié)構(gòu)所占存儲空間（）。A分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針B只有一部分，存放結(jié)點值C只有一部分，存儲表示結(jié)點間關(guān)系的指針D分兩部分，一部分存放結(jié)點值，另一部分存放結(jié)點所占單元數(shù)答案： A（5）線性表若采用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址（）。A必須是連續(xù)的B部分地址必須是連續(xù)的C一定是不連續(xù)的D連續(xù)或不連續(xù)都可以答案： D（6）線性表在（）情況下適用于使用鏈式結(jié)構(gòu)實現(xiàn)。A需經(jīng)常修改中的結(jié)點值需不斷對進行刪除插入C中含有大量的結(jié)點中結(jié)點結(jié)構(gòu)復(fù)雜答案：B解釋：鏈表最大的優(yōu)點在于插入和刪除時不需要移動數(shù)據(jù)，直接修改指針即可。（7）單鏈

12、表的存儲密度（）。A大于1B等于1C小于1D不能確定答案： C解釋：存儲密度是指一個結(jié)點數(shù)據(jù)本身所占的存儲空間和整個結(jié)點所占的存儲空間之比，假設(shè)單鏈表一個結(jié)點本身所占的空間為D，指針域所占的空間為N，則存儲密度為：D/(D+N) ，一定小于（8）將兩個各有n 個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是（）。1。A nB 2n-1C2nD n-1答案： A解釋：當?shù)谝粋€有序表中所有的元素都小于（或大于）第二個表中的元素，只需要用第二個表中的第一個元素依次與第一個表的元素比較，總計比較n 次。（ 9）在一個長度為 n 的順序表中，在第 i 個元素（ 1 i n+1）之前插入一個新元素時須向

13、后移動（ ）個元素。A n-iB n-i+1C n-i-1D I答案： B(10) 線性表L=(a1， a2,an)，下列說法正確的是（）。A每個元素都有一個直接前驅(qū)和一個直接后繼B線性表中至少有一個元素C表中諸元素的排列必須是由小到大或由大到小D除第一個和最后一個元素外，其余每個元素都有一個且僅有一個直接前驅(qū)和直接后繼。答案：D(11) 創(chuàng)建一個包括A O(1)n 個結(jié)點的有序單鏈表的時間復(fù)雜度是（B O(n)C O(n2)）。D O(nlog2n)答案： C解釋：單鏈表創(chuàng)建的時間復(fù)雜度是O(n)，而要建立一個有序的單鏈表，則每生成一個新結(jié)點時需要和已有的結(jié)點進行比較，確定合適的插入位置，所

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

15、 s-next=p-next; p-next=s;答案： D(14) 在雙向鏈表存儲結(jié)構(gòu)中，刪除p 所指的結(jié)點時須修改指針（）。A p-next-prior=p-prior; p-prior-next=p-next;B p-next=p-next-next; p-next-prior=p;C p-prior-next=p; p-prior=p-prior-prior;D p-prior=p-next-next; p-next=p-prior-prior;答案：A(15) 在雙向循環(huán)鏈表中， 在 p 指針所指的結(jié)點后插入q 所指向的新結(jié)點， 其修改指針的操作是 （A p-next=q; q-pr

16、ior=p; p-next-prior=q; q-next=q;B p-next=q; p-next-prior=q; q-prior=p; q-next=p-next;C q-prior=p; q-next=p-next; p-next-prior=q; p-next=q;D q-prior=p; q-next=p-next; p-next=q; p-next-prior=q;）。答案：C第 3 章棧和隊列1選擇題（1）若讓元素1， 2， 3，4， 5 依次進棧，則出棧次序不可能出現(xiàn)在（A 5， 4， 3，2， 1B2， 1， 5， 4，3C4，3， 1， 2， 5D 2， 3，5，4， 1

17、）種情況。答案： C解釋：棧是后進先出的線性表，不難發(fā)現(xiàn)C選項中元素1 比元素原則，所以不可能出現(xiàn)C 選項所示的情況。2 先出棧，違背了棧的后進先出（ 2）若已知一個棧的入棧序列是 1，2， 3， ， n，其輸出序列為 p1， p2，p3， ， pn，若 p1=n，則 pi 為（ ）。A iB n-iC n-i+1D不確定答案： C解釋：棧是后進先出的線性表，一個棧的入棧序列是1，2， 3， ， n ，而輸出序列的第一個元素為 n，說明 1， 2， 3， ， n 一次性全部進棧，再進行輸出，所以p1=n， p2=n-1 ， ， pi=n-i+1 。（3）數(shù)組用來表示一個循環(huán)隊列，為當前隊列頭元

18、素的前一位置，為隊尾元素的位置，假定隊列中元素的個數(shù)小于，計算隊列中元素個數(shù)的公式為（）。A r-fB (n+f-r)%nCn+r-fD（ n+r-f)%n答案： D解釋：對于非循環(huán)隊列，尾指針和頭指針的差值便是隊列的長度，而對于循環(huán)隊列，差值可能為負數(shù)，所以需要將差值加上MAXSIZE（本題為n），然后與 MAXSIZE（本題為 n）求余，即（n+r-f)%n（4）鏈式棧結(jié)點為：(data,link) ， top 指向棧頂 .若想摘除棧頂結(jié)點，并將刪除結(jié)點的值保存到x則應(yīng)執(zhí)行操作（）。A x=top-data;top=top-link ；B top=top-link;x=top-link ；

19、。中 ,C x=top;top=top-link；D x=top-link ；答案： A解釋： x=top-data 將結(jié)點的值保存到頂結(jié)點。（5）設(shè)有一個遞歸算法如下x 中， top=top-link棧頂指針指向棧頂下一結(jié)點，即摘除棧int fact(int n) /n大于等于0if(n=0) return 1;else return n*fact(n-1);則計算Afact(n) 需要調(diào)用該函數(shù)的次數(shù)為（n+1B n-1）。C nDn+2答案： A解釋：特殊值法。設(shè)n=0，易知僅調(diào)用一次fact(n) 函數(shù)，故選（6）棧在 （）中有所應(yīng)用。A遞歸調(diào)用B函數(shù)調(diào)用C表達式求值A(chǔ)。D前三個選項都

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

21、2B3C4D 6答案： B解釋：元素出隊的序列是e2、 e4、 e3、e6、 e5 和 e1，可知元素入隊的序列是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 設(shè)為 n+1，則元素 x 進棧的正確操作是()。A top+; Vtop=x;BVtop=x; top+;C top-; Vtop=x;DVtop=x; top-;答案： C解釋：初始棧頂指針top 為 n+

22、1，說明元素從數(shù)組向量的高端地址進棧，又因為元素存儲在向量空間 V1.n 中，所以進棧時top 指針先下移變?yōu)閚，之后將元素x 存儲在 Vn。（10）設(shè)計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳。A線性表的順序存儲結(jié)構(gòu)B隊列C. 線性表的鏈式存儲結(jié)構(gòu)D. 棧答案： D解釋：利用棧的后進先出原則。（11）用鏈接方式存儲的隊列，在進行刪除運算時（A. 僅修改頭指針B.C. 頭、尾指針都要修改D.）。僅修改尾指針頭、尾指針可能都要修改答案： D解釋：一般情況下只修改頭指針，因此需對隊尾指針重新賦值。（12）循環(huán)隊列存儲在數(shù)組A0.m但是，當刪除的是隊列中最后一個元素時，中，

23、則入隊時的操作為（）。隊尾指針也丟失了，A. rear=rear+1B. rear=(rear+1)%(m-1)C. rear=(rear+1)%mD. rear=(rear+1)%(m+1)答案： D解釋：數(shù)組A0.m中共含有m+1個元素，故在求模運算時應(yīng)除以（13）最大容量為n 的循環(huán)隊列，隊尾指針是rear ，隊頭是frontm+1。，則隊空的條件是（）。A. (rear+1)%n=frontB. rear=frontC rear+1=frontD. (rear-l)%n=front答案： B解釋：最大容量為n 的循環(huán)隊列，隊滿條件是(rear+1)%n=front（14）棧和隊列的共同

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

25、配是串的一種重要運算D串既可以采用順序存儲，也可以采用鏈式存儲答案： B解釋：空格常常是串的字符集合中的一個元素，有一個或多個空格組成的串成為空格串，零個字符的串成為空串，其長度為零。（3）串“ ababaaababaa”的 next 數(shù)組為（）。A012345678999B 012121111212C011234223456D 0123012322345答案： C（4）串“ ababaabab”的 nextval 為（ ）。A010104101B 010102101C 010100011D010101011答案： A（5）串的長度是指（）。A串中所含不同字母的個數(shù)B串中所含字符的個數(shù)C串中所

26、含不同字符的個數(shù)D串中所含非空格字符的個數(shù)答案： B解釋：串中字符的數(shù)目稱為串的長度。（6）假設(shè)以行序為主序存儲二維數(shù)組 A=array1.100,1.100 ，設(shè)每個數(shù)據(jù)元素占 2 個存儲單元，基地址為 10，則 LOC5,5=（ ）。A 808B 818C 1010D1020答案： B解釋：以行序為主，則LOC5,5=（ 5-1）*100+ （ 5-1） *2+10=818 。（7）設(shè)有數(shù)組 Ai,j ，數(shù)組的每個元素長度為3 字節(jié)， i 的值為 1到 8， j 的值為 1 到 10，數(shù)組從內(nèi)存首地址 BA 開始順序存放，當用以列為主存放時，元素A5,8 的存儲首地址為（）。A BA+14

27、1B BA+180C BA+222D BA+225答案： B解釋：以列序為主，則LOC5,8=（ 8-1）*8+ （ 5-1）*3+BA=BA+180。（8）設(shè)有一個10 階的對稱矩陣 A，采用壓縮存儲方式，以行序為主存儲，a11為第一元素，其存儲地址為 1，每個元素占一個地址空間，則a85 的地址為（）。A 13B 32C33D 40答案： C（9）若對 n 階對稱矩陣 A 以行序為主序方式將其下三角形的元素(包括主對角線上所有元素)依次存放于一維數(shù)組 B1.(n(n+1)/ 2 中，則在 B 中確定 aij（ij）的位置 k的關(guān)系為（）。A i*(i-1)/ 2+jB j*(j-1)/ 2

28、+iC i*(i+1)/ 2+jDj*(j+1)/ 2+i答案： B（ 10）二維數(shù)組 A的每個元素是由10 個字符組成的串， 其行下標 i=0,1,8, 列下標 j=1,2,10 。若 A 按行先存儲，元素A8,5 的起始地址與當 A 按列先存儲時的元素（）的起始地址相同。設(shè)每個字符占一個字節(jié)。A A8,5BA3,10C. A5,8D A0,9答案： B解釋：設(shè)數(shù)組從內(nèi)存首地址M 開始順序存放，若數(shù)組按行先存儲，元素A8,5 的起始地址為：M+（ 8-0 ）*10+（ 5-1 ）*1=M+84 ；若數(shù)組按列先存儲， 易計算出元素 A3,10的起始地址為： M+（ 10-1 ）*9+ （ 3-

29、0 ） *1=M+84 。故選 B。（11）設(shè)二維數(shù)組A1. m， 1. n（即 m 行 n 列）按行存儲在數(shù)組 B1. m*n 中，則二維數(shù)組元素Ai,j 在一維數(shù)組 B 中的下標為（）。A (i-1)*n+jB (i-1)*n+j-1C i*(j-1)D j*m+i-1答案： A解釋：特殊值法。取 i=j=1，易知A1,1 的的下標為 1，四個選項中僅有A 選項能確定的值為 1，故選 A。（ 12）數(shù)組 A0.4,-1.-3,5.7 中含有元素的個數(shù)（）。A 55B45C 36D 16答案： B解釋：共有5*3*3=45個元素。（13）廣義表A=(a,b,(c,d),(e,(f,g)，則H

30、ead(Tail(Head(Tail(Tail(A)的值為（）。A (g)B(d)C cDd答案： 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(Tail(Tail(A)=(d)；Head(Tail(Head(Tail(Tail(A)=d。（14）廣義表 (a,b,c,d) 的表頭是（），表尾是（）。A aB( )C(a,b,c,d)D (b,c,d)答案： C、 B解釋：表頭為非空廣義表的第一個元素，可以是一個單原子，也可以是一個子表，頭為一個子

31、表(a,b,c,d) ；表尾為除去表頭之外，由其余元素構(gòu)成的表，表為一定是個廣義表，的表尾為空表( )。（15）設(shè)廣義表L=(a,b,c)，則 L 的長度和深度分別為（）。A1和 1B1和3C1和2D2和3(a,b,c,d)的表 (a,b,c,d)答案： C解釋：廣義表的深度是指廣義表中展開后所含括號的層數(shù)，廣義表的長度是指廣義表中所含元素的個數(shù)。根據(jù)定義易知 L 的長度為 1，深度為 2。2應(yīng)用題（1）已知模式串答案：模式串 t 的 nextt= abcaabbabcab 寫出用和 nextval值如下：KMP法求得的每個字符對應(yīng)的next和nextval函數(shù)值。j1234567891011

32、12t 串a(chǎn)bcaabbabcabnextj011122312345nextvalj011021301105（2）設(shè)目標為t= “ abcaabbabcabaacbacba ” , 模式為 p=“ abcabaa” 計算模式p 的 naxtval函數(shù)值； 不寫出算法 , 只畫出利用KMP算法進行模式匹配時每一趟的匹配過程。答案： p 的 nextval函數(shù)值為0110132。（ p 的 next函數(shù)值為0111232 ）。 利用 KMP(改進的 nextval) 算法，每趟匹配過程如下：第一趟匹配： abcaabbabcabaacbacbaabcab(i=5,j=5)第二趟匹配： abcaab

33、babcabaacbacbaabc(i=7,j=3)第三趟匹配： abcaabbabcabaacbacbaa(i=7,j=1)第四趟匹配： abcaabbabcabaac bacba( 成功)abcabaa(i=15,j=8)（3）數(shù)組 A 中，每個元素 Ai,j 的長度均為 32個二進位 , 行下標從 -1 到 9，列下標從1 到 11，從首地址 S 開始連續(xù)存放主存儲器中，主存儲器字長為16 位。求： 存放該數(shù)組所需多少單元？ 存放數(shù)組第4 列所有元素至少需多少單元？ 數(shù)組按行存放時，元素A7,4的起始地址是多少？ 數(shù)組按列存放時，元素A4,7的起始地址是多少？答案：每個元素32 個二進制

34、位，主存字長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,(banana),peach),pear)答案： H（ H（ T（ H（T（ H（ T（ L）第 5 章樹和二叉樹1選擇題（ 1）把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是（）。A唯一的有多種C有多種，但根結(jié)點都沒有左孩子有多種，但根結(jié)點都沒有右孩子答案： A解釋：因為二叉樹有左孩子、右孩子之分，

35、故一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是唯一的。（ 2）由A 23 個結(jié)點可以構(gòu)造出多少種不同的二叉樹？（B3C4）D 5答案：D解釋：五種情況如下：AAAAABBBBBCCCCC（ 3）一棵完全二叉樹上有1001 個結(jié)點，其中葉子結(jié)點的個數(shù)是（）。A250B 500C254D 501答案： D解釋：設(shè)度為0 結(jié)點（葉子結(jié)點）個數(shù)為A，度為 1 的結(jié)點個數(shù)為B，度為 2 的結(jié)點個數(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 個葉子結(jié)點。（ 4）一個具有1025

36、個結(jié)點的二叉樹的高h 為（）。A 11B10C 11 至 1025 之間D10 至 1024 之間答案： C解釋：若每層僅有一個結(jié)點，則樹高h 為 1025；且其最小樹高為log21025 + 1=11，即 h 在 11 至1025 之間。（ 5）深度為 h 的滿 m叉樹的第 k 層有（）個結(jié)點。 (1=k=h)k-1BkCh-1DhA m m-1 m m-1答案： A解釋：深度為h 的滿 m叉樹共有 mh-1個結(jié)點，第 k 層有 mk-1個結(jié)點。（ 6）利用二叉鏈表存儲樹，則根結(jié)點的右指針是（）。A指向最左孩子B指向最右孩子C空D非空答案： C解釋：利用二叉鏈表存儲樹時，右指針指向兄弟結(jié)點，

37、因為根節(jié)點沒有兄弟結(jié)點，故根節(jié)點的右指針指向空。（ 7）對二叉樹的結(jié)點從 1 開始進行連續(xù)編號，要求每個結(jié)點的編號大于其左、右孩子的編號，同一結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用（）遍歷實現(xiàn)編號。A先序B.中序C.后序D.從根開始按層次遍歷答案： C解釋：根據(jù)題意可知按照先左孩子、再右孩子、最后雙親結(jié)點的順序遍歷二叉樹，即后序遍歷二叉樹。（ 8）若二叉樹采用二叉鏈表存儲結(jié)構(gòu)，要交換其所有分支結(jié)點左、右子樹的位置，利用（歷方法最合適。A前序B中序C后序D按層次）遍答案： C解釋：后續(xù)遍歷和層次遍歷均可實現(xiàn)左右子樹的交換，不過層次遍歷的實現(xiàn)消耗比后續(xù)大，后序遍歷方法最合適。（

38、9）在下列存儲形式中， （）不是樹的存儲形式？A雙親表示法B孩子鏈表表示法C 孩子兄弟表示法D 順序存儲表示法答案： D解釋：樹的存儲結(jié)構(gòu)有三種：雙親表示法、孩子表示法、孩子兄弟表示法，其中孩子兄弟表示法是常用的表示法，任意一棵樹都能通過孩子兄弟表示法轉(zhuǎn)換為二叉樹進行存儲。（ 10）一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（A所有的結(jié)點均無左孩子B所有的結(jié)點均無右孩子C只有一個葉子結(jié)點D是任意一棵二叉樹）。答案：C解釋：因為先序遍歷結(jié)果是“中左右” ，后序遍歷結(jié)果是“左右中” ，當沒有左子樹時，就是“中右”和“右中” ；當沒有右子樹時，就是“中左”和“左中” 。

39、則所有的結(jié)點均無左孩子或所有的結(jié)點均無右孩子均可，所以 A、 B 不能選，又所有的結(jié)點均無左孩子與所有的結(jié)點均無右孩子時，均只有一個葉子結(jié)點，故選C。（11）設(shè)哈夫曼樹中有A99B 100199 個結(jié)點，則該哈夫曼樹中有（C 101D102）個葉子結(jié)點。答案： B解釋：在哈夫曼樹中沒有度為1 的結(jié)點，只有度為0（葉子結(jié)點）和度為2 的結(jié)點。設(shè)葉子結(jié)點的個數(shù)為n0，度為 2 的結(jié)點的個數(shù)為n2，由二叉樹的性質(zhì)n0=n2+1，則總結(jié)點數(shù)n= n0+n2=2*n0-1 ，得到 n0=100。（ 12）若 X 是二叉中序線索樹中一個有左孩子的結(jié)點，且X 不為根，則X 的前驅(qū)為（）。AX 的雙親BX 的

40、右子樹中最左的結(jié)點CX 的左子樹中最右結(jié)點DX 的左子樹中最右葉結(jié)點答案： C（ 13）引入二叉線索樹的目的是（）。A加快查找結(jié)點的前驅(qū)或后繼的速度C為了能方便的找到雙親B 為了能在二叉樹中方便的進行插入與刪除 D 使二叉樹的遍歷結(jié)果唯一答案： A（14）設(shè) F 是一個森林，空的結(jié)點有（）個。An- 1BnB 是由F 變換得的二叉樹。若Cn + 1F 中有n 個非終端結(jié)點，則Dn + 2B 中右指針域為答案： C（15） n（n2）個權(quán)值均不相同的字符構(gòu)成哈夫曼樹，關(guān)于該樹的敘述中，錯誤的是（ ）。A該樹一定是一棵完全二叉樹B樹中一定沒有度為1 的結(jié)點C樹中兩個權(quán)值最小的結(jié)點一定是兄弟結(jié)點D樹

41、中任一非葉結(jié)點的權(quán)值一定不小于下一層任一結(jié)點的權(quán)值答案： A解釋：哈夫曼樹的構(gòu)造過程是每次都選取權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，所以樹中一定沒有度為 1 的結(jié)點、兩個權(quán)值最小的結(jié)點一定是兄弟結(jié)點、任一非葉結(jié)點的權(quán)值一定不小于下一層任一結(jié)點的權(quán)值。2應(yīng)用題（1）試找出滿足下列條件的二叉樹 先序序列與后序序列相同中序序列與后序序列相同 先序序列與中序序列相同中序序列與層次遍歷序列相同答案：先序遍歷二叉樹的順序是“根左子樹右子樹”，中序遍歷“左子樹根右子樹”序遍歷順序是： “左子樹右子樹根，根據(jù)以上原則有 或為空樹，或為只有根結(jié)點的二叉樹 或為空樹，或為任一結(jié)點至多只有左子樹的二叉樹 或為空樹，或為任一結(jié)點至多只有右子樹的二叉樹 或為空樹，或為任一結(jié)點至多只有右子樹的二叉