數(shù)據(jù)結(jié)構(gòu)課后答案[共44頁]

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ù)元素的、有獨立含義的、不可分割的最小單位。例

2、如,學(xué)生基本信息表中的學(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ù)對象在計算機中的存儲表示,也稱為 物

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

4、系就確定了學(xué)生表的邏輯結(jié)構(gòu),即線性結(jié)構(gòu)。這些學(xué)生記錄在計算機中的存儲表示就是存儲結(jié)構(gòu)。 如果用連續(xù)的存儲單元 ( 如用數(shù)組表示 ) 來存放這些記錄, 則稱為順序存儲結(jié)構(gòu)； 如果存儲單元不連續(xù), 而是隨機存放各個記錄, 然后用指針進行鏈接,則稱為鏈?zhǔn)酱鎯Y(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é)報到的時間先后順序進行排列,將組成

5、一個線性結(jié)構(gòu)。（3）樹結(jié)構(gòu)數(shù)據(jù)元素之間存在一對多的關(guān)系。例如,在班級的管理體系中,班長管理多個組長,每位組長管理多名組員,從而組成樹形結(jié)構(gòu)。（4）圖結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)數(shù)據(jù)元素之間存在多對多的關(guān)系。例如,多位同學(xué)之間的朋友關(guān)系,任何兩位同學(xué)都可以是朋友,從而組成圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。其中樹結(jié)談判圖結(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è)計語言的數(shù)組類型來描述。（2）鏈?zhǔn)酱鎯Y(jié)構(gòu)順序存儲結(jié)構(gòu)要求所有的元素依次存放在一片連續(xù)的存儲空間中,而鏈?zhǔn)酱鎯Y(jié)

6、構(gòu),無需占用一整塊存儲空間。但為了表示結(jié)點之間的關(guān)系,需要給每個結(jié)點附加指針字段,用于存放后繼元素的存儲地址。所以鏈?zhǔn)酱鎯Y(jié)構(gòu)通常借助于程序設(shè)計語言的指針類型來描述。5選擇題（1）在數(shù)據(jù)結(jié)構(gòu)中,從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（ ）。A動態(tài)結(jié)談判靜態(tài)結(jié)構(gòu) B 緊湊結(jié)談判非緊湊結(jié)構(gòu)C線性結(jié)談判非線性結(jié)構(gòu) D 內(nèi)部結(jié)談判外部結(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ù)要相同

7、,而且對應(yīng)數(shù)據(jù)項的類型要一致C每個數(shù)據(jù)元素都一樣D數(shù)據(jù)元素所包含的數(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ù)的最小單位, 數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)元素的集合。（5）算法的時間復(fù)雜度取決于（ ）。A問題的規(guī)模 B待處理數(shù)據(jù)的初態(tài)C計算機的配置 DA 和 B參考答案： D解釋：算法的時間復(fù)雜度不僅與問題的規(guī)模有關(guān), 還與問題的其他因素有關(guān)。 如某些排序的算法,其執(zhí)行時間與待排序記錄的初

8、始狀態(tài)有關(guān)。為此,有時會對算法有最好、最壞以及平均時間復(fù)雜度的評價。（6）以下數(shù)據(jù)結(jié)構(gòu)中, （ ）是非線性數(shù)據(jù)結(jié)構(gòu)A樹 B 字符串 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;su

9、m=s;參考答案： O(n2)2解釋：語句 s+=Bij; 的執(zhí)行次數(shù)為 n。（4）i=1;while(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; j1y=0;while(x (y+1)* (y+1)y +;參考答案： O( n )解釋：語句 y+; 的執(zhí)行次數(shù)為n 。第 2 章線性表1選擇題（1）順序表中第一個元素的存儲地址是 100,每個元素的長度為2,則第 5 個元素的地址是（ ）。A110 B108 C 100 D120參考答案： B解釋：順序表中的數(shù)據(jù)連續(xù)存

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

11、有 127 個元素的順序表中插入一個新元素并保持原來順序不變,平均要移動的元素個數(shù)為（ ）。A8 B63.5 C63 D7參考答案： B解釋：平均要移動的元素個數(shù)為： n/2。（4）鏈接存儲的存儲結(jié)構(gòu)所占存儲空間（ ）。A分兩部分,一部分存放結(jié)點值,另一部分存放表示結(jié)點間關(guān)系的指針B只有一部分,存放結(jié)點值C只有一部分,存儲表示結(jié)點間關(guān)系的指針D分兩部分,一部分存放結(jié)點值,另一部分存放結(jié)點所占單元數(shù)參考答案： A（5）線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時,要求內(nèi)存中可用存儲單元的地址（ ）。A必須是連續(xù)的 B部分地址必須是連續(xù)的C一定是不連續(xù)的 D連續(xù)或不連續(xù)都可以參考答案： D（6）線性表在（ ）情況下

12、適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實現(xiàn)。A需經(jīng)常修改中的結(jié)點值需不斷對進行刪除插入C中含有大量的結(jié)點 中結(jié)點結(jié)構(gòu)復(fù)雜參考答案： B解釋：鏈表最大的優(yōu)點在于插入和刪除時不需要移動數(shù)據(jù),直接修改指針即可。（7）單鏈表的存儲密度（ ）。A大于 1 B等于 1 C小于 1 D不能確定參考答案： C解釋：存儲密度是指一個結(jié)點數(shù)據(jù)本身所占的存儲空間和整個結(jié)點所占的存儲空間之比,假設(shè)單鏈表一個結(jié)點本身所占的空間為 D,指針域所占的空間為 N,則存儲密度為： D/(D+N),一定小于 1。（8）將兩個各有 n 個元素的有序表歸并成一個有序表,其最少的比較次數(shù)是（ ）。An B2n-1 C2n Dn-1參考答案： A解釋：當(dāng)?shù)?/p>

13、一個有序表中所有的元素都小于（或大于）第二個表中的元素,只需要用第二個表中的第一個元素依次與第一個表的元素比較,總計比較n 次。（9）在一個長度為n 的順序表中,在第 i 個元素（ 1 i n+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 個結(jié)點的有

14、序單鏈表的時間復(fù)雜度是（ ）。AO(1) BO(n) CO(n 2) DO(nlog2n)參考答案： C解釋：單鏈表創(chuàng)建的時間復(fù)雜度是 O(n),而要建立一個有序的單鏈表,則每生成一個新結(jié)點時需要和已有的結(jié)點進行比較,確定合適的插入位置,所以時間復(fù)雜度是 O(n2)。(12) 以下說法錯誤的是（ ）。A求表長、定位這兩種運算在采用順序存儲結(jié)構(gòu)時實現(xiàn)的效率不比采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時實現(xiàn)的效率低B順序存儲的線性表可以隨機存取C由于順序存儲要求連續(xù)的存儲區(qū)域,所以在存儲管理上不夠靈活D線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)參考答案： D解釋：鏈?zhǔn)酱鎯Y(jié)談判順序存儲結(jié)構(gòu)各有優(yōu)缺點,有不同的適用場合。(13)

15、 在單鏈表中,要將 s 所指結(jié)點插入到 p 所指結(jié)點之后,其語句應(yīng)為（ ）。As-next=p+1; p-next=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) 在雙向鏈表存儲結(jié)構(gòu)中,刪除 p 所指的結(jié)點時須修改指針（ ）。Ap-next-prior=p-prior; p-prior-next=p-next;Bp-next=p-next-next; p-next-prior=p;Cp-prior-next=p; p-prior=p-pr

16、ior-prior;D p-prior=p-next-next; p-next=p-prior-prior;參考答案： A(15) 在雙向循環(huán)鏈表中, 在p 指針?biāo)傅慕Y(jié)點后插入 q 所指向的新結(jié)點, 其修改指針的操作是 （ ）。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-next;Cq-prior=p; q-next=p-next; p-next-prior=q; p-next=q;Dq-prior=p; q-next=p-next; p-next=

17、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,5D2,3,5,4,1參考答案： C解釋：棧是后進先出的線性表,不難發(fā)現(xiàn) C選項中元素 1 比元素 2 先出棧,違背了棧的后進先出原則,所以不可能出現(xiàn) C選項所示的情況。（2）若已知一個棧的入棧序列是 1,2,3, , n,其輸出序列為 p1,p2,p3, , pn,若 p1=n,則 pi 為（ ）。Ai B n-i C n-i+1 D 不確定參考答案： C解釋：棧是后進先出

18、的線性表,一個棧的入棧序列是 1,2,3, , n,而輸出序列的第一個元素為 n,說明 1,2,3, , n 一次性全部進棧,再進行輸出,所以 p1=n,p2=n-1, , pi=n-i+1。（3）數(shù)組用來表示一個循環(huán)隊列,為當(dāng)前隊列頭元素的前一位置,為隊尾元素的位置,假定隊列中元素的個數(shù)小于,計算隊列中元素個數(shù)的公式為（ ）。Ar-f B (n+f-r)%n C n+r-f D （n+r-f)%n參考答案： D解釋：對于非循環(huán)隊列,尾指針和頭指針的差值便是隊列的長度,而對于循環(huán)隊列,差值可能為負數(shù),所以需要將差值加上 MAXSIZE（本題為 n）,然后與 MAXSIZE（本題為 n）求余,即

19、（ n+r-f)%n 。（4）鏈?zhǔn)綏＝Y(jié)點為： (data,link) ,top 指向棧頂 .若想摘除棧頂結(jié)點,并將刪除結(jié)點的值保存到 x 中,則應(yīng)執(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 將結(jié)點的值保存到 x 中,top=top-link 棧頂指針指向棧頂下一結(jié)點,即摘除棧頂結(jié)點。（5）設(shè)有一個遞歸算法如下int fact(int n) /n 大于等于 0if(n=0) return 1;else re

20、turn n*fact(n-1); 則計算 fact(n)需要調(diào)用該函數(shù)的次數(shù)為（ ）。A n+1 B n-1 C n D n+2參考答案： A解釋：特殊值法。設(shè) n=0,易知僅調(diào)用一次 fact(n)函數(shù),故選 A。（6）棧在 （ ）中有所應(yīng)用。A遞歸調(diào)用 B函數(shù)調(diào)用 C表達式求值 D前三個選項都有參考答案： 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有序表參考答案：

21、 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)該是 （ ）。A2 B3 C4 D 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 依次進入棧

22、,易知棧 S中最多同時存在 3 個元素,故棧 S的容量至少為 3。（9）若一個棧以向量 V1.n存儲,初始棧頂指針 top 設(shè)為 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)?n,之后將元素 x 存儲在 Vn。（10）設(shè)計一個判別表達式中左,右括號是否配對出現(xiàn)的算法,采用（ ）數(shù)據(jù)結(jié)構(gòu)最佳。A線性表的順序存儲結(jié)構(gòu) B

23、隊列C. 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) D. 棧參考答案： D解釋：利用棧的后進先出原則。（11）用鏈接方式存儲的隊列,在進行刪除運算時（ ）。A. 僅修改頭指針 B. 僅修改尾指針C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改參考答案： D解釋： 一般情況下只修改頭指針, 但是,當(dāng)刪除的是隊列中最后一個元素時, 隊尾指針也丟失了,因此需對隊尾指針重新賦值。（12）循環(huán)隊列存儲在數(shù)組 A0.m 中,則入隊時的操作為（ ）。A. rear=rear+1 B. rear=(rear+1)%(m-1)C. rear=(rear+1)%m D. rear=(rear+1)%(m+1)參考答案： D解釋

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

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

26、多個空格組成的串成為空格串,零個字符的串成為空串,其長度為零。（3）串“ ababaaababaa”的 next 數(shù)組為（ ）。A9 B2 C6 D45參考答案： C（4）串“ ababaabab”的 nextval 為（ ）。A010104101 B010102101 C010100011 D010101011參考答案： A（5）串的長度是指（ ）。A串中所含不同字母的個數(shù) B串中所含字符的個數(shù)C串中所含不同字符的個數(shù) D串中所含非空格字符的個數(shù)參考答案： B解釋：串中字符的數(shù)目稱為串的長度。（6）假設(shè)以行序為主序存儲二維數(shù)組 A=array1.100,1.100 ,設(shè)每個數(shù)據(jù)元素占 2 個

27、存儲單元,基地址為 10,則 LOC5,5=（ ）。A808 B818 C1010 D1020參考答案： 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 開始順序存放,當(dāng)用以列為主存放時,元素 A5,8 的存儲首地址為（ ）。ABA+141 BBA+180 CBA+222 DBA+225參考答案： B解釋：以列序為主,則 LOC5,8=（8-1）*8+ （5-1）*3+BA=BA+180。（8）設(shè)有一個 10 階的對

28、稱矩陣 A,采用壓縮存儲方式,以行序為主存儲, a11 為第一元素,其存儲地址為 1,每個元素占一個地址空間,則 a85 的地址為（ ）。A13 B32 C33 D40參考答案： C（9）若對 n 階對稱矩陣 A 以行序為主序方式將其下三角形的元素 (包括主對角線上所有元素 )依次存放于一維數(shù)組 B1.(n(n+1)/ 2中,則在 B 中確定 aij（ij）的位置 k 的關(guān)系為（ ）。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個字符組成的串, 其行下標(biāo) i=0,1, , ,

29、8, 列下標(biāo) j=1,2, , ,10 。若 A 按行先存儲,元素 A8,5 的起始地址與當(dāng) A 按列先存儲時的元素（ ）的起始地址相同。設(shè)每個字符占一個字節(jié)。AA8,5 BA3,10 C. A5,8 DA0,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-0 ）*1=M+84 。故選 B。（11）設(shè)二維數(shù)組 A1. m,1. n（即 m 行 n 列）按行存儲在數(shù)組 B1. m*n 中,則

30、二維數(shù)組元素Ai,j 在一維數(shù)組 B 中的下標(biāo)為（ ）。A(i-1)*n+j B(i-1)*n+j-1 Ci*(j-1) Dj*m+i-1參考答案： A解釋：特殊值法。取 i=j=1,易知 A1,1的的下標(biāo)為 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解 釋 ：

31、 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)的表頭是（ ）,表尾是（ ）。Aa B( ) C(a,b,c,d) D(b,c,d)參考答案： C、B解釋：表頭為非空廣義表的第一個元素,可以是一個單原子,也可以是一個子表, (a,b,c,d)的表頭為一個子表 (a,b,c,d)；表尾為除去表頭之外,由其余元素組成的表,表為一

32、定是個廣義表, (a,b,c,d)的表尾為空表 ( )。（15）設(shè)廣義表 L=(a,b,c),則 L 的長度和深度分別為（ ）。A1 和 1 B1 和 3 C1 和 2 D2 和 3參考答案： C解釋：廣義表的深度是指廣義表中展開后所含括號的層數(shù),廣義表的長度是指廣義表中所含元素的個數(shù)。根據(jù)定義易知 L 的長度為 1,深度為 2。2應(yīng)用題（1）已知模式串 t=abcaabbabcab 寫出用 KMP法求得的每個字符對應(yīng)的 next 和 nextval 函數(shù)值。參考答案：模式串 t 的 next 和 nextval 值如下：j 1 2 3 4 5 6 7 8 9 10 11 12t 串 a b

33、c a a b b a b c a bnextj 0 1 1 1 2 2 3 1 2 3 4 5nextvalj 0 1 1 0 2 1 3 0 1 1 0 5（2）設(shè)目標(biāo)為 t= “abcaabbabcabaacbacba ”, 模式為 p=“abcabaa” 計算模式 p 的 naxtval 函數(shù)值； 不寫出算法 , 只畫出利用 KMP算法進行模式匹配時每一趟的匹配過程。參考答案： p 的 nextval 函數(shù)值為 。（p 的 next 函數(shù)值為 ）。 利用 KMP(改進的 nextval) 算法,每趟匹配過程如下：第一趟匹配： abcaabbabcabaacbacbaabcab(i=5,

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

35、4,7 的起始地址是多少？參考答案：每個元素 32 個二進制位,主存字長 16 位,故每個元素占 2 個字長,行下標(biāo)可平移至 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é)點都沒有左孩子 有多種,但根

36、結(jié)點都沒有右孩子參考答案： A解釋：因為二叉樹有左孩子、右孩子之分,故一棵樹轉(zhuǎn)換為二叉樹后,這棵二叉樹的形態(tài)是唯一的。（2）由 3 個結(jié)點可以構(gòu)造出多少種不同的二叉樹？（ ）A2 B 3 C 4 D5參考答案： D解釋：五種情況如下：A A A AA B B B BB C C C C C（3）一棵完全二叉樹上有 1001 個結(jié)點,其中葉子結(jié)點的個數(shù)是（ ）。A250 B 500 C 254 D 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ì)

37、可得 B=0 或 1,又因為 C為整數(shù),所以 B=0,C=500,A=501,即有 501 個葉子結(jié)點。（4）一個具有 1025 個結(jié)點的二叉樹的高 h 為（ ）。A11 B 10 C 11 至 1025 之間 D 10 至 1024 之間參考答案： C解釋：若每層僅有一個結(jié)點,則樹高 h 為 1025；且其最小樹高為 log21025 + 1=11,即 h 在 11 至1025 之間。（5）深度為 h 的滿 m叉樹的第 k 層有（ ）個結(jié)點。 (1=k=h) k-1 B mk-1 C mh-1 D mh-1Am參考答案： A解釋：深度為 h 的滿 m叉樹共有 m h-1 個結(jié)點,第 k 層有

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

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

40、,則該二叉樹一定滿足（ ）。A所有的結(jié)點均無左孩子 B 所有的結(jié)點均無右孩子C只有一個葉子結(jié)點 D 是任意一棵二叉樹參考答案： C解釋：因為先序遍歷結(jié)果是“中左右” ,后序遍歷結(jié)果是“左右中” ,當(dāng)沒有左子樹時,就是“中右”和“右中” ；當(dāng)沒有右子樹時,就是“中左”和“左中” 。則所有的結(jié)點均無左孩子或所有的結(jié)點均無右孩子均可,所以 A、B 不能選,又所有的結(jié)點均無左孩子與所有的結(jié)點均無右孩子時,均只有一個葉子結(jié)點,故選C。（11）設(shè)哈夫曼樹中有 199 個結(jié)點,則該哈夫曼樹中有（ ）個葉子結(jié)點。A99 B100 C 101 D102參考答案： B解釋：在哈夫曼樹中沒有度為1 的結(jié)點,只有度為

41、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 的雙親B X 的右子樹中最左的結(jié)點CX 的左子樹中最右結(jié)點 D X 的左子樹中最右葉結(jié)點參考答案： C（13）引入二叉線索樹的目的是（ ）。A加快查找結(jié)點的前驅(qū)或后繼的速度 B 為了能在二叉樹中方便的進行插入與刪除C為了能方便的找到雙親D 使二叉樹的遍歷結(jié)果唯一參考答案： A（14）設(shè)F 是一個森林, B 是由 F變換得的

42、二叉樹。若 F 中有 n 個非終端結(jié)點,則B 中右指針域為空的結(jié)點有（ ）個。An- 1 Bn Cn + 1 Dn + 2參考答案： C（15）n（n 2）個權(quán)值均不相同的字符組成哈夫曼樹,關(guān)于該樹的敘述中,錯誤的是（ ）。A該樹一定是一棵完全二叉樹B樹中一定沒有度為1 的結(jié)點C樹中兩個權(quán)值最小的結(jié)點一定是兄弟結(jié)點D樹中任一非葉結(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）試找出

43、滿足下列條件的二叉樹 先序序列與后序序列相同 中序序列與后序序列相同 先序序列與中序序列相同 中序序列與層次遍歷序列相同參考答案：先序遍歷二叉樹的順序是“根 左子樹 右子樹” ,中序遍歷“左子樹 根 右子樹” ,后序遍歷順序是： “左子樹 右子樹根,根據(jù)以上原則有 或為空樹,或為只有根結(jié)點的二叉樹 或為空樹,或為任一結(jié)點至多只有左子樹的二叉樹 或為空樹,或為任一結(jié)點至多只有右子樹的二叉樹 或為空樹,或為任一結(jié)點至多只有右子樹的二叉樹（2）設(shè)一棵二叉樹的先序序列： A B D F C E G H ,中序序列： B F D A G E H C畫出這棵二叉樹。畫出這棵二叉樹的后序線索樹。將這棵二叉樹

44、轉(zhuǎn)換成對應(yīng)的樹（或森林） 。參考答案： AAA CB C B CB D E H D ED Enull GF F G HF G H （3） 假設(shè)用于通信的電文僅由 8 個字母組成,字母在電文中出現(xiàn)的頻率分別為 0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。 試為這 8 個字母設(shè)計赫夫曼編碼。 試設(shè)計另一種由二進制表示的等長編碼方案。 對于上述實例,比較兩種方案的優(yōu)缺點。參考答案：方案 1；哈夫曼編碼先將概率放大 100 倍,以方便構(gòu)造哈夫曼樹。w=7,19,2,6,32,3,21,10 ,按哈夫曼規(guī)則： 【（2,3）,6, (7,10)】, , 19, 21,

45、32（100）（40） （60）19 21 32 （28）（17） （11）7 10 6 （5）2 30 10 1 0 119 21 320 10 1 0 17 10 60 12 3方案比較：字母 對 應(yīng) 出現(xiàn) 字母 對應(yīng) 出 現(xiàn)編號 編碼 頻率 編號 編碼 頻率1 1100 0.07 1 000 0.072 00 0.19 2 001 0.193 11110 0.02 3 010 0.024 1110 0.06 4 011 0.065 10 0.32 5 100 0.326 11111 0.03 6 101 0.037 01 0.21 7 110 0.218 1101 0.10 8 111

46、0.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.06+0.10+0.02+0.03)=3結(jié)論：哈夫曼編碼優(yōu)于等長二進制編碼（4）已知下列字符 A、B、C、D、E、F、G的權(quán)值分別為 3、12、7、4、2、8,11,試填寫出其對應(yīng)哈夫曼樹 HT的存儲結(jié)構(gòu)的初態(tài)和終態(tài)。參考答案：初態(tài):weight parent lchild rchild1 3 0 0 02 12 0 0 03 7 0 0 04 4 0 0 05 2

47、 0 0 06 8 0 0 07 11 0 0 08 0 0 09 0 0 010 0 0 011 0 0 012 0 0 013 0 0 0終態(tài)：weight parent lchild rchild1 3 8 0 02 12 12 0 03 7 10 0 04 4 9 0 05 2 8 0 06 8 10 0 07 11 11 0 08 5 9 5 19 9 11 4 810 15 12 3 611 20 13 9 712 27 13 2 1013 47 0 11 12第 6 章 圖1選擇題（1）在一個圖中,所有頂點的度數(shù)之和等于圖的邊數(shù)的（ ）倍。A1/2 B1 C2 D4參考答案： C

48、（2）在一個有向圖中,所有頂點的入度之和等于所有頂點的出度之和的（ ）倍。A1/2 B1 C2 D4參考答案： B解釋：有向圖所有頂點入度之和等于所有頂點出度之和。（3）具有 n 個頂點的有向圖最多有（ ）條邊。2An Bn(n-1) Cn(n+1) Dn參考答案： B解釋：有向圖的邊有方向之分,即為從 n 個頂點中選取 2 個頂點有序排列,結(jié)果為 n(n-1)。（4）n 個頂點的連通圖用鄰接距陣表示時,該距陣至少有（ ）個非零元素。2An B2(n-1) Cn/2 Dn參考答案： B（5）G 是一個非連通無向圖,共有 28 條邊,則該圖至少有（ ）個頂點。A7 B8 C9 D10參考答案：

49、C解釋：8 個頂點的無向圖最多有 8*7/2=28 條邊,再添加一個點即組成非連通無向圖,故至少有 9 個頂點。（6）若從無向圖的任意一個頂點出發(fā)進行一次深度優(yōu)先搜索可以訪問圖中所有的頂點,則該圖一定是（ ）圖。A非連通 B連通 C強連通 D有向參考答案：B解釋：即從該無向圖任意一個頂點出發(fā)有到各個頂點的路徑,所以該無向圖是連通圖。（7）下面（ ）算法適合構(gòu)造一個稠密圖 G 的最小生成樹。A Prim 算法 BKruskal算法 CFloyd 算法 DDijkstra 算法參考答案： A解釋： Prim 算法適合構(gòu)造一個稠密圖 G 的最小生成樹, Kruskal 算法適合構(gòu)造一個稀疏圖 G 的

50、最小生成樹。（8）用鄰接表表示圖進行廣度優(yōu)先遍歷時,通常借助（ ）來實現(xiàn)算法。A棧 B. 隊列 C. 樹 D圖參考答案： B解釋：廣度優(yōu)先遍歷通常借助隊列來實現(xiàn)算法,深度優(yōu)先遍歷通常借助棧來實現(xiàn)算法。（9）用鄰接表表示圖進行深度優(yōu)先遍歷時,通常借助（ ）來實現(xiàn)算法。A棧 B. 隊列 C. 樹 D圖參考答案： A解釋：廣度優(yōu)先遍歷通常借助隊列來實現(xiàn)算法,深度優(yōu)先遍歷通常借助棧來實現(xiàn)算法。（10）深度優(yōu)先遍歷類似于二叉樹的（ ）。A先序遍歷 B中序遍歷 C后序遍歷 D層次遍歷參考答案： A（11）廣度優(yōu)先遍歷類似于二叉樹的（ ）。A先序遍歷 B中序遍歷 C后序遍歷 D層次遍歷參考答案：D（12）圖

51、的 BFS生成樹的樹高比 DFS生成樹的樹高（ ）。A小 B相等 C小或相等 D大或相等參考答案：C解釋：對于一些特殊的圖,比如只有一個頂點的圖,其 BFS 生成樹的樹高和 DFS 生成樹的樹高相等。一般的圖,根據(jù)圖的 BFS 生成樹和 DFS 樹的算法思想, BFS 生成樹的樹高比 DFS 生成樹的樹高小。（13）已知圖的鄰接矩陣如圖 6.30 所示,則從頂點 v0 出發(fā)按深度優(yōu)先遍歷的結(jié)果是（ ）。圖 6.30 鄰接矩陣（14）已知圖的鄰接表如圖 6.31 所示,則從頂點 v0 出發(fā)按廣度優(yōu)先遍歷的結(jié)果是（ ）,按深度優(yōu)先遍歷的結(jié)果是（ ）。圖 6.31 鄰接表A0 1 3 2 B0 2

52、3 1 C0 3 2 1 D0 1 2 3參考答案：D、D（15）下面（ ）方法可以判斷出一個有向圖是否有環(huán)。A深度優(yōu)先遍歷 B拓撲排序 C求最短路徑 D求關(guān)鍵路徑參考答案： B2應(yīng)用題（1）已知圖 6.32 所示的有向圖,請給出： 每個頂點的入度和出度； 鄰接矩陣； 鄰接表； 逆鄰接表。圖 6.32 有向圖 圖 6.33 無向網(wǎng)參考答案：（2）已知如圖 6.33 所示的無向網(wǎng),請給出： 鄰接矩陣； 鄰接表； 最小生成樹參考答案： 4 34 5 5 93 5 5 55 5 7 6 5 49 7 36 3 25 2 65 4 6a b 4 c 3b a 4 c 5 d 5 e 9c a 3 b 5 d 5 h 5d b 5 c 5 e 7 f 6 g 5 h 4e b 9 d 7 f 3f d 6 e 3 g 2g d 5 f 2 h 6（3）已知圖的鄰接矩陣如圖 6.34 所示。試分別畫出自頂點 1 出發(fā)進行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。（4）有向網(wǎng)如圖 6.35 所示,試用迪 杰斯特拉算法求