數(shù)據(jù)結(jié)構(gòu)習(xí)題

1、第一章選擇:1.數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的（ ）以及它們之間的相互關(guān)系。 A）存儲(chǔ)結(jié)構(gòu)，物理結(jié)構(gòu) B）理想結(jié)構(gòu)，抽象結(jié)構(gòu) C）物理結(jié)構(gòu)，邏輯結(jié)構(gòu) D）抽象結(jié)構(gòu)，邏輯結(jié)構(gòu)2.在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的（ ）結(jié)構(gòu)。 A）存儲(chǔ) B）物理 C）邏輯 D）物理與存儲(chǔ)3.數(shù)據(jù)結(jié)構(gòu)課程主要研究以下三方面的內(nèi)容，它們是（ ）。 A）數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型 B）數(shù)據(jù)元素、數(shù)據(jù)類型、算法實(shí)現(xiàn) C）數(shù)據(jù)元素、數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) D）數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算4.在以下的復(fù)雜度量級(jí)中，量級(jí)最低的是（）。 A）O(n) B）O(log2n) C）O(nlog2n) D）O(n2

2、)5.在下列敘述中，正確的是（）。 A）數(shù)據(jù)的邏輯結(jié)構(gòu)要考慮數(shù)據(jù)元素本身的內(nèi)容 B）不同類型的數(shù)據(jù)元素可以歸類到同一的邏輯結(jié)構(gòu)中 C）數(shù)據(jù)元素之間的關(guān)聯(lián)關(guān)系在數(shù)據(jù)的邏輯結(jié)構(gòu)中體現(xiàn) D）數(shù)據(jù)元素是數(shù)據(jù)不可分割的最小標(biāo)識(shí)單位6.計(jì)算機(jī)算法必須具備輸入、輸出和（）等五個(gè)特性。 A）可行性、可移植性和可擴(kuò)充性 B）可行性、確定性和有窮性 C）確定性、穩(wěn)定性和有窮性 D）易讀性、穩(wěn)定性和安全性7.算法分析的目的是（）。 A)找出數(shù)據(jù)結(jié)構(gòu)的合理性 B)研究算法中的輸入/輸出關(guān)系 C)分析算法的易讀性 D)分析算法的效率以求改進(jìn)8.設(shè)n>=10，下面程序段的時(shí)間復(fù)雜度是（）。 for(i=10; i&

3、lt;n; i+) j=k=0; while(j+k<=i) if(j>k)k+; else j+; A）O（log2n） B）O(n) C）O(nlog2n) D）O(n2)9.計(jì)算機(jī)算法是指( )。 A)計(jì)算方法 B)排序方法 C)調(diào)度方法 D)解決問(wèn)題的有限運(yùn)算序列10.數(shù)據(jù)的定義取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，而數(shù)據(jù)的實(shí)現(xiàn)取決于數(shù)據(jù)的物理結(jié)構(gòu)( )。 A)正確 B) 不正確 11.下面說(shuō)法錯(cuò)誤的是（ ） A)算法原地工作的含義是指不需要任何額外的輔助空間 B)在相同的規(guī)模n下，復(fù)雜度O(n)的算法在時(shí)間上總是優(yōu)于復(fù)雜度O(2n)的算法 C)所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)

4、間的一個(gè)上界 D)同一個(gè)算法，實(shí)現(xiàn)語(yǔ)言的級(jí)別越高，執(zhí)行效率就越低判斷：1. 數(shù)據(jù)元素是數(shù)據(jù)的最小單位。( )2. 記錄是數(shù)據(jù)處理的最小單位。 ( )3. 數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系；( )4. 算法的優(yōu)劣與算法描述語(yǔ)言無(wú)關(guān)，但與所用計(jì)算機(jī)有關(guān)。( )5. 健壯的算法不會(huì)因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。( )6. 算法可以用不同的語(yǔ)言描述，如果用C 語(yǔ)言或PASCAL語(yǔ)言等高級(jí)語(yǔ)言來(lái)描述，則算法實(shí)際上就是程序了。( )7. 數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的實(shí)際存儲(chǔ)形式。( ) 8. 數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實(shí)現(xiàn)有關(guān)。( )9. 數(shù)據(jù)結(jié)構(gòu)的基本操作的設(shè)置的最重要的

5、準(zhǔn)則是，實(shí)現(xiàn)應(yīng)用程序與存儲(chǔ)結(jié)構(gòu)的獨(dú)立。( ) 10. 數(shù)據(jù)的邏輯結(jié)構(gòu)說(shuō)明數(shù)據(jù)元素之間的順序關(guān)系,它依賴于計(jì)算機(jī)的存儲(chǔ)結(jié)構(gòu). ( ) 語(yǔ)句頻度與時(shí)間復(fù)雜度1.計(jì)算機(jī)執(zhí)行下面的語(yǔ)句時(shí),語(yǔ)句s的執(zhí)行次數(shù)為: (n+3)(n-2)/2。 for(i=l；i<n-l；i+) for(j=n;j>=i;j-) s; 2.下面程序段中帶有下劃線的語(yǔ)句執(zhí)行次數(shù)的量級(jí)是( log2n2 ) i=n*n while (i!=1) i=i / 2;3.下面程序段中帶下劃線的語(yǔ)句的執(zhí)行次數(shù)的數(shù)量級(jí)是(nlog2n )。 i=1; while( i<n) for j=1;j<=n;j+ x=x+

6、1; i=i*2； 4. 在下面的程序段中，對(duì)的賦值語(yǔ)句的頻度為: n(n+1)(n+2)/6 O(n3) for（i= 1；i<=n; i+） for(j=1;j<=i;j+) for (k1;k<=j; k+) +1；5. 已知如下程序段,則各語(yǔ)句的頻度為: for（i= n；i>=1; i- -） /語(yǔ)句1 n+1 x=x+1； /語(yǔ)句2 n for（j= n；j>=i;j-） /語(yǔ)句3 n(n+3)/2 y=y+1; /語(yǔ)句4 n(n+1)/2 答案：選擇：1. C 2.C 3. D 4.B 5.C 6.B 7. D 8.D 9.D 10.A 11.AD判

7、斷：1.× 2.× 3.× 4.× 5. 6.× 7. 8.× 9. 10.×第二章選擇：1.下列有關(guān)線性表的敘述中，正確的是（ ）。 A）線性表中元素之間的關(guān)系是線性關(guān)系 B）線性表中至少有一個(gè)元素 C）線性表中的任一元素有且僅有一個(gè)直接前趨 D）線性表中的任一元素有且僅有一個(gè)直接后繼2.下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？（ ） A）存儲(chǔ)密度大 B）插入方便 C）刪除方便 D）可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示3.在一個(gè)長(zhǎng)度為n的順序表中，在第i個(gè)元素（1<=i<=n）之前插入一個(gè)新元素時(shí)需向后移動(dòng)（ ）個(gè)元素。

8、 A）1 B）n-i C）n-i-1 D）n-i+14.如果某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前驅(qū)，那么采用（ ）存儲(chǔ)方式最節(jié)省時(shí)間。 A）順序表 B）單鏈表 C）雙鏈表 D）循環(huán)鏈表5.對(duì)順序存儲(chǔ)的線性表，設(shè)其長(zhǎng)度為n，且在任何位置上插入或刪除操作都是等概率的。則插入一個(gè)元素時(shí)平均要移動(dòng)表中的（ ）個(gè)元素。 A）n/2 B）(n+1)/2 C）(n-1)/2 D）n6.下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)？（ ） A）存儲(chǔ)密度太大 B）隨機(jī)存取 C）一般要估計(jì)最大的需要空間 D）只能應(yīng)用于少數(shù)幾種邏輯結(jié)構(gòu)的存儲(chǔ)表示7.在單鏈表中，增加頭結(jié)點(diǎn)的目的是（ ）。 A）使單鏈表至少有一個(gè)

9、結(jié)點(diǎn) B）標(biāo)志表中首結(jié)點(diǎn)的位置 C）方便運(yùn)算的實(shí)現(xiàn) D）說(shuō)明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)表示8.單鏈表不具有的特點(diǎn)是（ ）。 A)可隨機(jī)訪問(wèn)任一元素 B)插入和刪除不需要移動(dòng)元素 C)不必事先估計(jì)存儲(chǔ)空間 D)所需空間和線性表長(zhǎng)度成正比9.循環(huán)鏈表的主要優(yōu)點(diǎn)是（ ）。 A）不再需要頭指針了 B）已知某個(gè)結(jié)點(diǎn)的位置后，能夠容易找到他的直接前趨 C）在進(jìn)行插入、刪除運(yùn)算時(shí)，能更好的保證鏈表不斷開 D）從表中的任意結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表10.鏈表對(duì)于數(shù)據(jù)元素的插入與刪除是（ ）。 A）不需移動(dòng)結(jié)點(diǎn)，不需改變結(jié)點(diǎn)指針 B）不需移動(dòng)結(jié)點(diǎn)，只需改變結(jié)點(diǎn)指針 C）只需移動(dòng)結(jié)點(diǎn)，不需改變結(jié)點(diǎn)指針 D）既需移動(dòng)

10、結(jié)點(diǎn)，又需改變結(jié)點(diǎn)指針11.在一個(gè)單鏈表中,已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn),若要在q 和p所指結(jié)點(diǎn)之間插入s所指的結(jié)點(diǎn),則執(zhí)行（ ）。 A）s->next = p->next; p->next = s; B）q->next = s; s->next = p; C）p->next = s; s->next = q; D）p->next = s->next; s->next = p; 12.向一個(gè)有115個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變，平均要移動(dòng)（ ）個(gè)元素。 A) 115 B) 114 C) 58 D) 57 1

11、3.帶頭結(jié)點(diǎn)的單鏈表Head為空表的判定條件是 ( ) 。 A) Head->next=Head B) Head->next=NULL C) Head!=NULL D) Head=NULL14.若要求能快速地實(shí)現(xiàn)在鏈表的末尾插入結(jié)點(diǎn)和刪除第一個(gè)結(jié)點(diǎn)的運(yùn)算，則選擇( )最合適。 A) 單鏈表 B) 帶尾指針的單循環(huán)鏈表 C) 雙鏈表 D) 雙循環(huán)鏈表15.給定有n個(gè)元素的向量，建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度是( )。 A)O(n) B)O(log2n) C)O(nlog2n) D. O(n2)16.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址( )。 A)必須是連續(xù)的 B)必須是不連續(xù)的 C)連續(xù)與

12、否均可 D)部分地址必須是連續(xù)的17.在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中，插入一個(gè)新的結(jié)點(diǎn)并使之仍然有序的時(shí)間復(fù)雜度是( )。 A)O(n) B)O(log2n) C)O(1) D)O(n2) 答案：1.A 2.A 3. D 4.A 5.A 6.C 7.C 8.A 9.D 10.B 11.B 12.C 13.B 14.B15.D 16.C 17.A第三章選擇：1.在下列排序算法中，時(shí)間復(fù)雜度不受數(shù)據(jù)初始特性影響，恒為O(n2)的是（ ）。 A）插入排序 B）冒泡排序 C）選擇排序 D）堆排序2.在各種排序方法中，從未排序序列中依次取出元素與已排序序列（初始時(shí)為空）中的元素進(jìn)行比較，將其放入已排序

13、序列的正確位置上的方法，稱為（ ）。 A）希爾排序 B）冒泡排序 C）插入排序 D）選擇排序3.快速排序方法在（）情況下最不利于發(fā)揮其長(zhǎng)處。 A）要排序的數(shù)據(jù)量太大 B）要排序的數(shù)據(jù)含有多個(gè)相同值 C）要排序的數(shù)據(jù)已基本有序 D）要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù)4.已知10個(gè)數(shù)據(jù)元素為(54,28,16,34,73,62,95,60,26,43),對(duì)該數(shù)列按從小到大排序，經(jīng)過(guò)一趟冒泡排序后的序列為（）。 A）16，28，34，54，73，62，60，26，43，95 B）28，16，34，54，62，73，60，26，43，95 C）28，16，34，54，62，60，73，26，43，95 D）16，

14、28，34，54，62，60，73，26，43，955.一組記錄的關(guān)鍵字為（46,79,56,38,40,84）,則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)元素得到的一次劃分結(jié)果為（ ）。 A）38,40,46,56,79,84 B）40,38,46,79,56,84 C）40,38,46,56,79,84 D）40,38,46,84,56,79 6.用某種排序方法對(duì)線性表(25,84,21,47,15,27,68,35,20)進(jìn)行排序時(shí),元素序列的變化情況如下: (1)20,15,21,25,47,27,68,35,84 (2)15,20,21,25,35,27,47,68,84 (3)15,

15、20,21,25,27,35,47,68,84則所采用的排序方法是（ ）。 A）選擇排序 B）希爾排序 C）歸并排序 D）快速排序7.在待排序的元素序列基本有序的前提下，效率最高的排序方法是（）。 A）插入排序 B）快速排序 C）歸并排序 D）選擇排序8.一組記錄的排序碼為（20,29,11,74,35,3,8,56）,則利用堆排序方法建立的初始(小頂)堆為（ ）。 A）20,29,11,74,35,3,8,56 B）3,29,8,56,35,11,20,74 C）3,8,11,20,29,35,56,74 D）20,29,3,8,11,35,74,569.下列關(guān)鍵碼序列中，屬于堆的是（）。

16、A)（15，30，22，93，52，71） B)（15，71，30，22，93，52） C)（15，52，22，93，30，71） D)（93，30，52，22，15，71）10.若要求盡可能快地對(duì)實(shí)數(shù)數(shù)組進(jìn)行穩(wěn)定的排序，則應(yīng)選()。 A)快速排序 B)堆排序 C)歸并排序 D)基數(shù)排序11.下列排序算法的時(shí)間復(fù)雜度最小的是（）。 A)冒泡排序 B)希爾排序 C)簡(jiǎn)單選擇排序 D)歸并排序12.設(shè)有1000個(gè)無(wú)序的元素,希望用最快的速度挑選出其中前10個(gè)最大的元素,最好（ ）排序法。 A)起泡排序 B)快速排序 C)堆排序 D)基數(shù)排序13.插入排序算法在每一趟都能選取出一個(gè)元素放在其最終的位

17、置上。( ) A)正確 B)不正確 14.直接插入排序是不穩(wěn)定的排序方法。( ) A)正確 B)不正確15.直接插入排序的最壞情況是初始序列為（ ）序。 A)正 B)反 C)正和反 D)無(wú)16.在各排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始時(shí)為空）的一端的方法，稱為( )。 A)希爾排序 B)歸并排序 C)插入排序 D)選擇排序答案：1.C 2.C 3. C 4.B 5.C 6.D 7.A 8.B 9.A 10.C 11.D 12.C 13.B 14.B 15.B 16.D第四章選擇：1.棧的特點(diǎn)是( )。 A）先進(jìn)先出 B）后進(jìn)先出 C）進(jìn)優(yōu)于出 D）出優(yōu)于進(jìn)2.棧和

18、隊(duì)列都是（）。 A）順序存儲(chǔ)的線性結(jié)構(gòu) B）鏈?zhǔn)酱鎯?chǔ)的線性結(jié)構(gòu) C）操作受限的線性結(jié)構(gòu) D）操作受限的非線性結(jié)構(gòu)3.鏈棧與順序棧相比，有一個(gè)比較明顯的優(yōu)點(diǎn)是（）。 A）插入操作更加方便 B）通常不會(huì)出現(xiàn)棧滿的情況 C）不會(huì)出現(xiàn)棧滿的情況 D）刪除操作更加方便4.一個(gè)棧的入棧序列是a,b,c,d, 則下列序列中不可能的輸出序列是（ ）。 A）acbd B）dcba C）acdb D）dbac 5.設(shè)有一空棧,現(xiàn)有輸入序列為1,2,3,4,5,經(jīng)過(guò)PUSH,PUSH，POP，PUSH，POP，PUSH，PUSH后，輸出序列為（ ）。 A）5,4,3,2,1 B）2,1 C）2,3 D）2,4 6.

19、下面哪種數(shù)據(jù)結(jié)構(gòu)不適合作棧的存儲(chǔ)結(jié)構(gòu)（ ）。 A）數(shù)組 B）單鏈表 C）靜態(tài)鏈表 D）二叉樹結(jié)構(gòu)7.設(shè)計(jì)一個(gè)判別表達(dá)式中左右括號(hào)是否配對(duì)出現(xiàn)的算法，最好采用（ ）結(jié)構(gòu)。 A）線性表 B）隊(duì)列 C）堆棧 D）樹8.隊(duì)列的操作原則是( ) 。 A）先進(jìn)先出 B）先進(jìn)后出 C）只能進(jìn)行插入 D）只能進(jìn)行刪除 9. 判斷一個(gè)循環(huán)隊(duì)列是空隊(duì)列的條件是（ ）。 A）Q.rear = Q.front B）Q.front = 0 C）Q.rear = 0 D）(Q.rear+1)%maxsize = Q.front 10.在具有n個(gè)單元順序存儲(chǔ)的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有（ ）個(gè)元素。 A）n+1 B）n-1 C

20、）n D）n+211.若一個(gè)棧的輸入序列是1,2,3,n,輸出序列的第一個(gè)元素是n,則第i個(gè)輸出元素是( )。 A) n-i B) n-i+1 C) i D) 不確定 12.判斷當(dāng)字符序列 x5y 作為字符堆棧的輸入時(shí)，輸出長(zhǎng)度為3的且可以作為C語(yǔ)言標(biāo)識(shí)符的個(gè)數(shù)是（ ）。 A) 3個(gè) B) 4個(gè) C) 5個(gè) D) 6個(gè) 13.采用不帶尾指針的單鏈表方式表示一個(gè)棧，便于結(jié)點(diǎn)的插入與刪除。棧頂結(jié)點(diǎn)的插入與刪除通常在鏈表的（）進(jìn)行。 A)任意位置 B)鏈表頭尾兩端 C)鏈表頭一端 D)鏈表尾一端14.遞歸函數(shù)f(n)=f(n-1)十n(n>1)的遞歸出口，比較合理的是（ ）。 A)f(1)=0

21、 B)f(1)=1 C)f(0)=0 D)f(n)=n 15.在一個(gè)鏈隊(duì)列中,若Q.front、Q.rear分別為隊(duì)首、隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的操作為（ ）。 A) Q.front->next=s; Q.front=s; B) Q.rear->next=s; Q.rear=s; C) s->next=Q.front; Q.rear=s; D) s->next=Q.front; Q.front=s;答案: 1.B 2.C 3.B 4.D 5.C 6.D 7.C 8.A 9.A 10.B 11.B 12.A 13.C 14. B 15.B 第五章選擇;1.串是一種特殊的

22、線性表，其特殊性體現(xiàn)在( ) 。 A)可以順序存儲(chǔ) B)可以用鏈表存儲(chǔ) C)數(shù)據(jù)元素是一個(gè)字符 D)數(shù)據(jù)元素可以是多個(gè)字符2.串是（ ）。 A）少于一個(gè)字母的序列 B）任意個(gè)字母的序列 C）不少于一個(gè)字符的序列 D）有限個(gè)字符的序列3.串的長(zhǎng)度是（ ）。 A）串中不同字母的個(gè)數(shù) B）串中不同字符的個(gè)數(shù) C）串中所含字符的個(gè)數(shù)，且大于0 D）串中所含字符的個(gè)數(shù)4.設(shè)有兩個(gè)串p和q,求q在p中首次出現(xiàn)的位置的運(yùn)算( ). A）連接 B）模式匹配 C）求子串 D）求串長(zhǎng)5.若某串的長(zhǎng)度小于一個(gè)常數(shù)，則采用( )存儲(chǔ)方式最為節(jié)省空間。 A)鏈?zhǔn)?B)堆結(jié)構(gòu) C)順序6.串中任意多個(gè)連續(xù)字符組成的子序列

23、稱為該串的子串( ). A)正確 B)不正確7.如果兩個(gè)串含有相同的字符集，則說(shuō)兩者相等( ). A)正確 B)不正確 補(bǔ)充習(xí)題:8.存取數(shù)組中任一元素的時(shí)間都是相等的，這種存取方式為（ ）存取方式。 A）順序 B）隨機(jī) C）線性 D）非線性 9.設(shè)一個(gè)一維數(shù)組第一個(gè)元素的存儲(chǔ)單元的地址是100，每個(gè)元素的長(zhǎng)度是6，則它的第5個(gè)元素的地址是（ ）。 A）130 B）105 C）106 D）12410.設(shè)n階方陣是一個(gè)上三角矩陣，則需要存儲(chǔ)的元素個(gè)數(shù)是（）。 A）n2/2 B）n(n+1)/2 C）n D）n211.對(duì)一些特殊矩陣采用壓縮存儲(chǔ)的目的主要是為（ ）。 A）表達(dá)變得簡(jiǎn)單 B）減少不必

24、要的存儲(chǔ)空間的開銷 C）去掉矩陣中的多余元素 D）對(duì)矩陣元素的存取變得簡(jiǎn)單 12.三元組表不包括（ ）。 A) 行數(shù) B) 列數(shù) C) 元素值 D) 元素總數(shù) 13.設(shè)已知一個(gè)稀疏矩陣的三元組如下：(1,2,3),(1,6,1), (3,1,5),(3,2,-1),(4,5,4),(5,1,-3),則其轉(zhuǎn)置矩陣的三元組表中第3個(gè)三元組為（ ）。 A) (2,1,3) B) (3,1,5) C) (3,2,-1) D) (2,3,-1) 14.若采用三元組壓縮技術(shù)存儲(chǔ)稀疏矩陣，只要把每個(gè)元素的行下標(biāo)和列下標(biāo)互換，就完成了對(duì)該矩陣的轉(zhuǎn)置運(yùn)算，這種觀點(diǎn)（ ） A)正確 B)不正確15.兩維數(shù)組是一種

25、非線性結(jié)構(gòu)。（ ） A)正確 B)不正確16.數(shù)組A三維的長(zhǎng)度分別為b3,b2,b1；每個(gè)數(shù)組元素占一個(gè)存儲(chǔ)單元；LOC0，0，0為基址。若以行序?yàn)橹餍颍瑒t元素Aijk的地址為( )(其中0<=i<b3,0<=j<b2,0<=k<b1) A)LOC0,0,0+i*b2*b1+j*b1+k B)LOC0,0,0+i*b3*b2+j*b1+k C)LOC0,0,0+b3*i+b2*j+k D)LOC0,0,0+b3*i*j+b2*j+k 答案：1.C 2.D 3.D 4.B 5.C 6.A 7.B 8.B 9.D 10.B 11.B 12.D 13.A 14.B

26、 15.B 16.A 第六章選擇;1.樹最適合用來(lái)表示（ ）。 A)有序數(shù)據(jù)元素 B)無(wú)序數(shù)據(jù)元素 C)元素之間具有分支層次關(guān)系的數(shù)據(jù) D)元素之間無(wú)聯(lián)系的數(shù)據(jù)2.設(shè)深度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至多為( )。 A)2h-1 B)2(h-1) C)2*h-1 D)2*h3.在一棵二叉樹中，第5層上的結(jié)點(diǎn)數(shù)最多有( )。 A)10 B)15 C)16 D)32 4.下圖所示的二叉樹中，( )不是完全二叉樹。5.有100個(gè)結(jié)點(diǎn)的完全二叉樹,葉子結(jié)點(diǎn)的個(gè)數(shù)為:( )。 A)49 B)50 C)51 D)52說(shuō)明:由完全二叉樹的性質(zhì)知:第100個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)為

27、50，而且2*51>100,即第51個(gè)結(jié)點(diǎn)無(wú)左孩子,為葉子結(jié)點(diǎn),故葉子結(jié)點(diǎn)編號(hào)為:51- -100,葉子結(jié)點(diǎn)數(shù)為50。6.已知某二叉樹的葉子結(jié)點(diǎn)數(shù)為20 ,10個(gè)結(jié)點(diǎn)有一個(gè)左孩子,15個(gè)結(jié)點(diǎn)有一個(gè)右孩子，求該二叉樹的總結(jié)點(diǎn)數(shù)？解：該二叉樹葉子結(jié)點(diǎn)數(shù):n0=20,度為1的結(jié)點(diǎn)數(shù):n1=10+15,根據(jù)二叉樹的性質(zhì)3,n0=n2+1,n2=n0-1=19, 則:n=n0+n1+n2=64補(bǔ)充習(xí)題: 7.具有100個(gè)結(jié)點(diǎn)的二叉樹中，若用二叉鏈表存儲(chǔ)，其指針域部分用來(lái)指向結(jié)點(diǎn)的左、右孩子，其中（ ）個(gè)指針域?yàn)榭铡?A）50 B）99 C）100 D）1018.首先訪問(wèn)結(jié)點(diǎn)的左子樹，然后訪問(wèn)該結(jié)點(diǎn)

28、，最后訪問(wèn)結(jié)點(diǎn)的右子樹，這種遍歷稱為（ ）。 A）前序遍歷 B）后序遍歷 C）中序遍歷 D）層次遍歷9.任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷的序列中的相對(duì)次序（ ）。 A）不發(fā)生變化 B）發(fā)生變化 C）不能確定 D）以上都不對(duì)10.某非空二叉樹的前序序列和后序序列正好相反，則二叉樹一定是（ ）的二叉樹。 A）空或只有一個(gè)結(jié)點(diǎn) B）高度等于其結(jié)點(diǎn)數(shù) C）任一結(jié)點(diǎn)無(wú)左孩子 D）任一結(jié)點(diǎn)無(wú)右孩子11.如果某二叉樹的先序遍歷序列是abdcef，中序遍歷序列是dbaefc，則其后序遍歷序列是（ ）。 A）dbafec B）fecdba C）efcdba D）dbfeca 12.按照二叉樹的定義，

29、具有3個(gè)結(jié)點(diǎn)的二叉樹形態(tài)有( )種。 A）3 B）4 C）5 D）613.二叉樹的后序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其孩子結(jié)點(diǎn)的前面（ ）。 A）正確 B）錯(cuò)誤14.n個(gè)結(jié)點(diǎn)深度為h的二叉樹的線索化所需的時(shí)間復(fù)雜度是( )。 A)O(1) B)O(hn) C)O(n) D)O(nlog2h)15.設(shè)a,b為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，a在b前的條件是( )。 A)a是b祖先 B)a是b子孫 C)a在b左方 D)a在b右方16.關(guān)于二叉樹的三種遍歷，下列說(shuō)法正確的是( )。 A)任意兩種遍歷序列都不可以唯一決定該二叉樹 B)任意兩種遍歷序列都可以唯一決定該二叉樹 C)先序遍歷序列和后序

30、遍歷序列可以唯一決定該二叉樹 D)先序遍歷序列和中序遍歷序列可以唯一決定該二叉樹17.在某棵二叉樹的一種序列中，如果發(fā)現(xiàn)其中每一結(jié)點(diǎn)的左孩子均是其前趨，則可判斷定這種序列為中序序列( )。 A)正確 B)不正確 18.已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列是（ ）。 A)acbed B)decab C)deabc D)cedba 19.前序遍歷和中序遍歷結(jié)果相同的二叉樹為（ ）。 A)只有根結(jié)點(diǎn)的二叉樹 B)所有非葉子結(jié)點(diǎn)只有右子樹的二叉樹 C)根結(jié)點(diǎn)無(wú)右孩子的二叉樹 D)根結(jié)點(diǎn)無(wú)左孩子的二叉樹 20.前序遍歷和后序遍歷結(jié)果相同的二叉樹為（ ）。 A

31、)只有根結(jié)點(diǎn)的二叉樹 B)所有非葉子結(jié)點(diǎn)只有右子樹的二叉樹 C)根結(jié)點(diǎn)無(wú)右孩子的二叉樹 D)根結(jié)點(diǎn)無(wú)左孩子的二叉樹 21.樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵樹對(duì)應(yīng)的二叉樹。那么以下結(jié)論中，( )是正確的。 A)樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的先序遍歷序列相同 B)樹的后根遍歷序列與其對(duì)應(yīng)的二叉樹的后序遍歷序列相同 C)樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的中序遍歷序列相同 D)以上都不對(duì)22.若由森林轉(zhuǎn)化得到的二叉樹是非空的二叉樹，則二叉樹形狀是（ ） A)根結(jié)點(diǎn)無(wú)右子樹的二叉樹 B)根結(jié)點(diǎn)無(wú)左

32、子樹的二叉樹 C)根結(jié)點(diǎn)可能有左二叉樹和右二叉樹 D)各結(jié)點(diǎn)只有一個(gè)兒子的二叉樹 23.由分別帶權(quán)為9,2,5,7的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵Huffman樹，則該樹的帶權(quán)路徑長(zhǎng)度WPL為( )。 A)23 B)37 C)44 D)4624.有m個(gè)葉子結(jié)點(diǎn)的Huffman樹所具有的結(jié)點(diǎn)總數(shù)為( )。 A)m+1 B)2m-1 C)2m D. 2m+125.用HUFFMAN算法求最優(yōu)二叉樹時(shí),權(quán)越大的葉子離根越遠(yuǎn)( ) A)正確 B)不正確 26.若構(gòu)造一棵具有n個(gè)結(jié)點(diǎn)的二叉排序樹，最壞的情況下其深度不會(huì)超過(guò)（ ）。 A)n/2 B)n C)(n+1)/2 D)n+1 27.分別以下列序列構(gòu)造二叉排序

33、樹，則與其它幾個(gè)序列構(gòu)造的結(jié)果不同的是（ ） A)（80，70，60，75，90，85，100，10） B)（80，90，85，70，60，10，75，100） C)（80，90，70，85，10，60，75，100） D)（80，90，100，70，85，60，10，75）28.若以二叉樹的任一結(jié)點(diǎn)出發(fā)到根的路徑上所經(jīng)過(guò)的序列按其關(guān)鍵字有序,則該二叉樹是( )。 A）二叉排序樹 B）赫夫曼樹 C）堆 D）線索二叉樹 答案: 1.C 2.A 3.C 4.C 5. B 7.說(shuō)明:已知:n=n0+n1+n2,指針域?yàn)榭諅€(gè)數(shù):2*n0+n1=n0+n1+n2+1, 即n+1. D 8.C 9.A 1

34、0.B 11.D 12.C 13.B 14.C 15.C 16.D 17.B 18.D 19.B 20.A 21.A 22.C 23.C 24.B 25.B 26.B 27.C 28.C 29.B 30.C 第七章選擇：1.在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的( )倍。 A) 1/2 B) 1 C) 2 D) 42.具有5個(gè)頂點(diǎn)的有向完全圖有( )條弧。 A) 10 B) 16 C) 20 D) 253.一個(gè)有10個(gè)頂點(diǎn),6條邊的無(wú)向圖,該圖是否連通( )。 A) 能 B) 不能4.在任一有向圖中，所有頂點(diǎn)的入度之和一定等于所有頂點(diǎn)的出度之和( )。 A) 正確 B) 不正確5.圖的深度優(yōu)先遍歷類似于二叉樹的（ ）。 A）先序遍歷 B）中序遍歷 C）后序遍歷 D）層次遍歷6.在用鄰接表表示圖時(shí),深度優(yōu)先遍歷算法的時(shí)間復(fù)雜度為（） A)O（n） B)O（n+e） C)O（n2） D)O（n3）7.如果無(wú)向圖G必須進(jìn)行二次廣度優(yōu)先搜索才能訪問(wèn)其所有頂點(diǎn)，則下列說(shuō)法中不正確的是（） A)G肯定不是完全圖 B)G一定不是連通圖 C)G中一定有回路 D)G有2個(gè)連通分量9.連通圖的廣度優(yōu)先搜索中一般要采用隊(duì)列來(lái)暫存剛訪問(wèn)過(guò)的頂點(diǎn)( )。 A)正確 B)不正確10.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖,若采用鄰接表表示，則表頭向