濟(jì)南大學(xué)數(shù)據(jù)結(jié)構(gòu)期末考試題庫期末考試試題復(fù)習(xí)備考

單選題

計算機(jī)算法必須具備輸入、輸出、()等5個特性。

A.可行性、可移植性和可擴(kuò)展性B.可行性、確定性和有窮性

C.確定性、有窮性和穩(wěn)定性D.易讀性、安全性和穩(wěn)定性

答案：B

知識點(diǎn)：第一章

難度：1

解析：算法是解決特定問題的方法。具有5個特性：

(1)有窮性：一個算法必須在執(zhí)行有窮步之后結(jié)束

(2)確定性：算法中的每一步都必須具有確切的含義，無二義性

(3)可行性：算法中的每一步都是可行的

(4)輸入：有。個、1個或多個輸入量

(5)輸出：一個算法執(zhí)行結(jié)束后至少要有一個輸出量。

算法在發(fā)生非法操作時可以作出處理的特性稱為()。

A.正確性B.易讀性C.健壯性D.可靠性

答案：C

知識點(diǎn)：第一章

難度：1

解析：算法是解決特定問題的方法。衡量算法的5個指標(biāo)：

(1)正確性(correctness)：在合理的數(shù)據(jù)輸入下，能夠在有限的運(yùn)行時間內(nèi)得出正確的結(jié)

果。是設(shè)計和評價一個算法的首要條件。

(2)可使用性

(3)穩(wěn)健性(robustness健壯性)：算法對不合理(不正確、非法、錯誤)數(shù)據(jù)輸入的反應(yīng)

和處理能力。

(4)可讀性(readability)：符合結(jié)構(gòu)化和模塊化程序設(shè)計的思想，對每個功能模塊、重要

數(shù)據(jù)類型或語句加以注釋，建立有相應(yīng)的文檔。

(5)高效率與低存儲量需求。

數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的操作對象以及它們之間的

()和運(yùn)算的學(xué)科。

A.結(jié)構(gòu)B.關(guān)系C.運(yùn)算D.算法

答案：B

知識點(diǎn)：第一章

難度：1

解析：數(shù)據(jù)結(jié)構(gòu)的定義：是指數(shù)據(jù)以及數(shù)據(jù)元素相互之間的聯(lián)系。可以看作是相互之間存在

著某種特定關(guān)系的數(shù)據(jù)元素的集合。

在數(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)

答案：B

知識點(diǎn)：第一章

難度：2

解析：數(shù)據(jù)結(jié)構(gòu)中，邏輯結(jié)構(gòu)分為：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。非線性結(jié)構(gòu)又包括：樹形結(jié)構(gòu)、

圖形結(jié)構(gòu)。

為了描述n個人之間的同學(xué)關(guān)系，可用（）結(jié)構(gòu)表示

A.線性表B.樹C.圖D.隊(duì)列

答案：C

知識點(diǎn)：第一章

難度：3

解析：數(shù)據(jù)結(jié)構(gòu)中，邏輯結(jié)構(gòu)分為：線性結(jié)構(gòu)（1：1的關(guān)系）和非線性結(jié)構(gòu)。非線性結(jié)構(gòu)

又包括：樹形結(jié)構(gòu)（1：n的關(guān)系）、圖形結(jié)構(gòu)（m：n的關(guān)系）。n個人之間的同學(xué)關(guān)系是多

對多的關(guān)系，因此屬于圖形關(guān)系。

下面的程序段違反了算法的(）原則

voidsam0

{intn-2;

while(!odd(n))n+=2;

printf(n);

A.有窮性B.確定性C.可行性D.健壯性

答案：A

知識點(diǎn)：第一章

難度：2

解析：算法是解決特定問題的方法。具有5個特性：

（1）有窮性：一個算法必須在執(zhí)行有窮步之后結(jié)束

（2）確定性：算法中的每一步都必須具有確切的含義，無二義性

（3）可行性：算法中的每一步都是可行的

（4）輸入：有。個、1個或多個輸入量

（5）輸出：一個算法執(zhí)行結(jié)束后至少要有一個輸出量。

樹形結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種()。

A.一對一關(guān)系B.多對多關(guān)系

C.多對一關(guān)系D.一對多關(guān)系

答案：D

知識點(diǎn)：第一章

難度:2

解析：數(shù)據(jù)結(jié)構(gòu)中，邏輯結(jié)構(gòu)分為：線性結(jié)構(gòu)(1：1的關(guān)系)和非線性結(jié)構(gòu)。非線性結(jié)構(gòu)

又包括：樹形結(jié)構(gòu)(1：n的關(guān)系)、圖形結(jié)構(gòu)(m：n的關(guān)系)。

設(shè)語句x++的時間是單位時間，則以下語句的時間復(fù)雜度為()。

for(i=l;i<=n;i++)

for(j=i;j<=n;j++)

x++;

A.0(1)B.0(〃2)C.0(n)D.0(n3)

答案：B

知識點(diǎn)：第一章

難度：3

解析：在算法分析中，起決定作用的是循環(huán)操作。首先找到循環(huán)嵌套的最內(nèi)層語句。本題中

是x++,計算此語句的執(zhí)行次數(shù)，并取其最高階，得到0(〃2)。

數(shù)據(jù)在計算機(jī)內(nèi)有鏈?zhǔn)胶晚樞騼煞N存儲方式，在存儲空間使用的靈活性上，鏈?zhǔn)酱鎯Ρ软樞?/p>

存儲要()。

A.低B.高C.相同D.不好說

答案：B

知識點(diǎn)：第一章

難度：3

解析：順序存儲結(jié)構(gòu)的三個弱點(diǎn)：作插入或刪除操作時，需移動大量元數(shù)；長度變化較大時，

需按最大空間分配；表的容量難以擴(kuò)充。

鏈?zhǔn)酱鎯Φ奶攸c(diǎn)：比順序存儲結(jié)構(gòu)的存儲密度小;邏輯上相鄰的節(jié)點(diǎn)物理上不必相鄰;插入、

刪除靈活。

數(shù)據(jù)結(jié)構(gòu)只是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，這種觀點(diǎn)(B)。

A.正確B.錯誤

C.前半句對，后半句錯D.前半句錯，后半句對

答案：B

知識點(diǎn)：第一章

難度：1

解析：數(shù)據(jù)結(jié)構(gòu)的定義：是指數(shù)據(jù)以及數(shù)據(jù)元素相互之間的聯(lián)系。可以看作是相互之間存在

著某種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)研究邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、以及其運(yùn)算。

若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素算法的時間復(fù)雜度

()。

A.0(log2n)

B.0(1)

C.0(n)

D.0(n2)

答案：C

知識點(diǎn)：第二章

難度：2

解析：在順序表中插入一個元素，需要將第i個元素以后的數(shù)據(jù)都依次往后移動一個位置。

時間復(fù)雜度與i的位置有關(guān)。平均時間復(fù)雜度是0(n)。

若一個線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素，則采用()

存儲方式最節(jié)省時間。

A.順序表

B.單鏈表

C.雙鏈表

D.單循環(huán)鏈表

答案：A

知識點(diǎn)：第二章

難度：2

解析：使用順序表，可以實(shí)現(xiàn)隨機(jī)存取，直接找到第i個元素和找第i個元素的前趨元素。

具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是()。

A.圖

B.樹

C.順序表

D.棧

答案：C

知識點(diǎn)：第二章

難度：1

解析：順序表是線性結(jié)構(gòu)。

在一個長度為n的順序表中，在第i個元素之前插入一個新元素時，需向后移動（）個元

素。

A.n-i

B.n-i+1

C.n-i-1

D.i

答案：B

知識點(diǎn)：第二章

難度：2

解析：在順序表中插入一個元素，需要將第i個元素以后的數(shù)據(jù)都依次往后移動一個位置。

則移動數(shù)據(jù)的個數(shù)是n-i+1。

非空的單鏈表head的尾結(jié)點(diǎn)p滿足（）。

A.p->next-head

B.p->next==NULL

C.p—NULL

D.p-head

答案：B

知識點(diǎn)：第二章

難度：2

解析：單鏈表中每個節(jié)點(diǎn)的指針next指向后繼結(jié)點(diǎn)。尾節(jié)點(diǎn)沒有后繼節(jié)點(diǎn)，因此，其next

為NULL。

鏈表不具有的特點(diǎn)是（）。

A.可隨機(jī)訪問任一元素

B.插入刪除不需要移動元素

C.不必事先估計存儲空間

D.所需空間與線性表長度成正比

答案：A

知識點(diǎn)：第二章

難度：1

解析：鏈表的特點(diǎn)是順序存取，即需要從頭節(jié)點(diǎn)開始一次存取。

在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點(diǎn)后插入一個指針q所指向的新結(jié)點(diǎn)，修改指針的操作

是（）。

A.p->next=q;q->prior=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->next=p->next;q->prior=p;p->next=q;p->next=q;

答案：C

知識點(diǎn)：第二章

難度：5

解析：略。

線性表采用鏈?zhǔn)酱鎯r，結(jié)點(diǎn)的存儲地址（）。

A.必須是連續(xù)的

B.必須是不連續(xù)的

C.連續(xù)與否均可

D.和頭結(jié)點(diǎn)的存儲地址相連續(xù)

答案：C

知識點(diǎn)：第二章

難度：3

解析：鏈?zhǔn)浇Y(jié)構(gòu)并不要求存儲空間必須是連續(xù)的。因此，其對存儲空間沒有要求。

在一個長度為n的順序表中刪除第i個元素，需要向前移動（）個元素。

A.n-i

B,n-i+1

C.n-i-1

D.i+1

答案：A

知識點(diǎn)：第二章

難度：3

解析：在一個長度為n的順序表中刪除第i個元素，要將i+1元素及之后的元素依次向前移

動一個位置，故共有n-i個元素。

線性表是n個（）的有限序列。

A.表元素

B.字符

C.數(shù)據(jù)元素

D.數(shù)據(jù)項(xiàng)

答案：C

知識點(diǎn)：第二章

難度：1

解析：這是線性表的定義。線性表是n個數(shù)據(jù)元素的有限序列

從表中任一結(jié)點(diǎn)出發(fā)，都能掃描整個表的是（）。

A.單鏈表

B.順序表

C.循環(huán)鏈表

D.靜態(tài)鏈表

答案：C

知識點(diǎn)：第二章

難度：4

解析：這幾個選項(xiàng)中，只有循環(huán)鏈表首尾相連，構(gòu)成了一個環(huán)形結(jié)構(gòu)，可以實(shí)現(xiàn)從表中任一

結(jié)點(diǎn)出發(fā)，都能掃描整個表的功能。

在具有n個結(jié)點(diǎn)的單鏈表上查找值為x的元素時，其時間復(fù)雜度為()。

A.0(n)

B.0(1)

C.0(n2)

D.0(n-l)

答案：A

知識點(diǎn)：第二章

難度：3

解析：在單鏈表中查找元素，要從表頭開始，由第1個元素依次向后尋找。相當(dāng)于單鏈表的

遍歷運(yùn)算。時間復(fù)雜度是0(n)。

線性表L=(al,a2,……,an),下列說法正確的是()。

A.每個元素都有一個直接前驅(qū)和一個直接后繼

B.線性表中至少要有一個元素

C.表中諸元素的排列順序必須是由小到大或由大到小

D.除第一個和最后一個元素外，其余每個元素都由一個且僅有一個直接前驅(qū)和直接后

繼

答案：D

知識點(diǎn)：第二章

難度：1

解析：此題考查線性表的特點(diǎn)：除第一個和最后一個元素外，其余每個元素都由一個且僅有

一個直接前驅(qū)和直接后繼。

一個順序表的第一個元素的存儲地址是90,每個元素的長度為2,則第6個元素的存儲地址

是()。

A.98

B.100

C.102

D.106

答案：B

知識點(diǎn)：第二章

難度：3

解析：第6個元素的地址是：90+2*5=100。

在線性表的下列存儲結(jié)構(gòu)中，讀取元素花費(fèi)的時間最少的是()。

A.單鏈表

B.雙鏈表

C.循環(huán)鏈表

D.順序表

答案：D

知識點(diǎn)：第二章

難度：2

解析：順序表是隨機(jī)存取結(jié)構(gòu)，可以直接實(shí)現(xiàn)數(shù)據(jù)元素的讀取。鏈表是順序存取結(jié)構(gòu)，需要

從第1個元素依次向后查找。

在一個單鏈表中，若刪除p所指向結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行()。

A.p->next=p->next->next;

B.p=p->next;p->next=p->next->next;

C.p=p->next;

D.p=p->next->next;

答案：A

知識點(diǎn)：第二章

難度：4

解析：略。

將長度為n的單鏈表連接在長度為m的單鏈表之后的算法的時間復(fù)雜度為()。

A.0(1)

B.0(n)

C.0(m)

D.0(m+n)

答案：C

知識點(diǎn)：第二章

難度：4

解析：將長度為n的單鏈表連接在長度為m的單鏈表之后，只需要將長度為n的單鏈表的第一

個元素連接在長度為m的單鏈表的最后一個元素的后面。主要的問題就是尋找長度為m的單鏈

表的最后一個元素。故時間復(fù)雜度為0(m)。

線性表的順序存儲結(jié)構(gòu)是一種()存儲結(jié)構(gòu)。

A.隨機(jī)存取

B.順序存取

C.索引存取

D.散列存取

答案：A

知識點(diǎn)：第二章

難度：2

解析：順序存儲結(jié)構(gòu)的數(shù)據(jù)存儲在一塊地址連續(xù)的空間中，數(shù)據(jù)元素依次存放。是一種隨機(jī)

存取結(jié)構(gòu)。

順序表中，插入一個元素所需移動的元素平均數(shù)是（）。

A.（n-l）/2

B.n

C.n+1

D.（n+l）/2

答案：D

知識點(diǎn)：第二章

難度：4

解析：略。

循環(huán)鏈表的主要優(yōu)點(diǎn)是（）。

A.不再需要頭指針

B.已知某結(jié)點(diǎn)位置后能容易找到其直接前驅(qū)

C.在進(jìn)行插入、刪除運(yùn)算時能保證鏈表不斷開

D.在表中任一結(jié)點(diǎn)出發(fā)都能掃描整個鏈表

答案：D

知識點(diǎn)：第二章

難度：5

解析：略。

不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（）。

A.head==NULL

B.head->next==NULL

C.head->next==head

D.head!=NULL

答案：A

知識點(diǎn)：第二章

難度：4

解析：不帶頭節(jié)點(diǎn)的單鏈表,head頭指針指向第一個節(jié)點(diǎn)，單鏈表為空的條件是head==null?

在下列對順序表進(jìn)行的操作中，算法時間復(fù)雜度為0（1）的是（）。

A.訪問第i個元素的前驅(qū)（l<i=n）

B.在第i個元素之后插入一個新元素（14i4n）

C.刪除第i個元素（14i4n）

D.對順序表中元素進(jìn)行排序

答案：A

知識點(diǎn)：第二章

難度：3

解析：順序表是隨機(jī)存取方式，可以直接取得一個元素，時間復(fù)雜度是0(1)。插入、刪除

的操作需要對元素進(jìn)行移動，時間復(fù)雜度是0(n)?排序操作的時間復(fù)雜度是0(/)。

已知指針P和q分別指向某單鏈表中第一個結(jié)點(diǎn)和最后一個結(jié)點(diǎn)。假設(shè)指針s指向另一個單鏈

表中某個結(jié)點(diǎn)，則在s所指結(jié)點(diǎn)之后插入上述鏈表應(yīng)執(zhí)行的語句為(

A.q->next=s->next；s->next=p；

B.s->next=p；q->next=s->next；

C.p->next=s->next；s->next=q；

D.s->next=q；p->next=s->next；

答案：A

知識點(diǎn)：第二章

難度：4

解析：略。

在以下的敘述中，正確的是()0

A.線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)

B.線性表的順序存儲結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況

C.線性表的鏈表存儲結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況

D.線性表的鏈表存儲結(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)

答案：C

知識點(diǎn)：第二章

難度：2

解析：順序表是隨機(jī)存取結(jié)構(gòu)，查找某個元素的操作簡單，插入、刪除操作需要移動元素,

效率較低。鏈表結(jié)構(gòu)中，插入、刪除操作只需要改變指針，因此比較簡單。但是它是順序存

取機(jī)制，查找元素比較復(fù)雜。二者各有優(yōu)缺點(diǎn)。

在表長為n的順序表中，當(dāng)在任何位置刪除一個元素的概率相同時，刪除一個元素所需移動

的平均個數(shù)為()o

A.(n-l)/2

B.n/2

C.(n+l)/2

D.n

答案：A

知識點(diǎn)：第二章

難度：3

解析：平均移動個數(shù)為(nT)/2。

在一個單鏈表中，已知q所指結(jié)點(diǎn)是P所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和P之間插入一個結(jié)點(diǎn)

s,則執(zhí)行(

A.s->next=p->next;p->next=s;

B.p->next=s->next;s->next=p;

C.q->next=s;s->next=p;

D.p->next=s;s->next=q;

答案：c

知識點(diǎn)：第二章

難度：3

解析：略。

在單鏈表中，指針P指向元素為x的結(jié)點(diǎn)，實(shí)現(xiàn)刪除x的后繼的語句是（）。

A.p=p->next;

B.p->next=p->next->next;

C.p->next=p;

D.p=p-〉next->next;

答案：B

知識點(diǎn)：第二章

難度：3

解析：略。

一個棧的輸入序列為：a,b,c,d,e,則棧的不可能輸出的序列是（）。

A.a,b,c,d,e

B.d,e,c,b,a

C.d,c,e,a,b

D.e,d,c,b,a

答案：C

知識點(diǎn)：第三章

難度：2

解析：棧的特點(diǎn)是只能在一端進(jìn)行插入和刪除操作，數(shù)據(jù)是先進(jìn)后出的。C中d首先出棧,

說明a,b,c在棧中。則a,b,c的出棧的相對順序肯定是c,b,a。

判斷一個循環(huán)隊(duì)列Q（最多n個元素）為滿的條件是（）.

A.Q->rear==Q->front

B.Q->rear==Q->front+l

C.Q->front-（Q->rear+l）%n

D.Q->front==（Q->rear-l）%n

答案：C

知識點(diǎn)：第三章

難度：2

解析：循環(huán)隊(duì)列的為滿的條件是Q->front==（Q->rear+l）%no

設(shè)計一個判別表達(dá)式中括號是否配對的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳。

A.順序表

B.鏈表

C.隊(duì)列

D.棧

答案：D

知識點(diǎn)：第三章

難度：3

解析：棧的特點(diǎn)是只能在一端進(jìn)行插入和刪除操作，數(shù)據(jù)是先進(jìn)后出的。括號配對的問題可

以通過左右括號對應(yīng)比較來實(shí)現(xiàn)。需要用到棧。

棧的操作特點(diǎn)是（）。

A.隨機(jī)存取

B.順序存取

C.先進(jìn)后出

D.先進(jìn)先出

答案：C

知識點(diǎn)：第三章

難度：1

解析：棧的特點(diǎn)是只能在一端進(jìn)行插入和刪除操作，數(shù)據(jù)是先進(jìn)后出的。

隊(duì)列的操作特點(diǎn)是（）。

A.隨機(jī)存取

B.順序存取

C.先進(jìn)后出

D.先進(jìn)先出

答案：D

知識點(diǎn)：第三章

難度：1

解析：棧的特點(diǎn)是只能在一端進(jìn)行插入和刪除操作，數(shù)據(jù)是先進(jìn)后出的。隊(duì)列的特點(diǎn)是在一

段進(jìn)行插入，在另一端進(jìn)行刪除。數(shù)據(jù)是先進(jìn)先出的。

隊(duì)列的插入操作是在（）?

A.隊(duì)尾

B.隊(duì)頭

C.隊(duì)列任意位置

D.隊(duì)頭元素后

答案：A

知識點(diǎn)：第三章

難度：1

解析：隊(duì)列的特點(diǎn)是在一段進(jìn)行插入，在另一端進(jìn)行刪除。數(shù)據(jù)是先進(jìn)先出的。插入的一段

稱為隊(duì)尾。刪除的一段稱為對頭或隊(duì)首。

隊(duì)列的刪除操作是在（）。

A.隊(duì)尾

B.隊(duì)頭

C.隊(duì)列任意位置

D.隊(duì)頭元素后

答案：B

知識點(diǎn)：第三章

難度：1

解析：隊(duì)列的特點(diǎn)是在一段進(jìn)行插入，在另一端進(jìn)行刪除。數(shù)據(jù)是先進(jìn)先出的。插入的一段

稱為隊(duì)尾。刪除的一段稱為對頭或隊(duì)首。

循環(huán)隊(duì)列的隊(duì)頭和隊(duì)尾指針分別為front和rear,則判斷循環(huán)隊(duì)列為空的條件是（）。

A.front==rear

B.front==0

C.rear==0

D.front=rear+l

答案：A

知識點(diǎn)：第三章

難度：1

解析：循環(huán)隊(duì)列的隊(duì)頭和隊(duì)尾指針分別為front和rear,則判斷循環(huán)隊(duì)列為空的條件是

front-rear

一個順序棧S,其棧頂指針為top,則將元素e入棧的操作是（）。

A.S->top=e;S->top++;

B.S->top++;S->top=e;

C.S->top=e

D.S->top=e;

答案：B

知識點(diǎn)：第三章

難度：2

解析：略。

將遞歸算法轉(zhuǎn)換成對應(yīng)的非遞歸算法時，通常需要使用（）來保存中間結(jié)果。

A.隊(duì)列

B.棧

C.鏈表

D.樹

答案：B

知識點(diǎn)：第三章

難度：5

解析：將遞歸算法轉(zhuǎn)換成對應(yīng)的非遞歸算法時，通常需要使用棧來保存中間結(jié)果。

棧的插入和刪除操作在（）。

A.棧底

B.棧頂

C.任意位置

D.指定位置

答案：B

知識點(diǎn)：第三章

難度：1

解析：棧的特點(diǎn)是只能在一端進(jìn)行插入和刪除操作，數(shù)據(jù)是先進(jìn)后出的。進(jìn)行插入和刪除的

操作稱為棧頂。

五節(jié)車廂以編號1,2,3,4,5順序進(jìn)入鐵路調(diào)度站（棧），可以得到（）的編組。

A.3,4,5,1,2

B.2,4,1,3,5

C.3,5,4,2,1

D.1,3,5,2,4

答案：c

知識點(diǎn)：第三章

難度：3

解析：棧的特點(diǎn)是只能在一端進(jìn)行插入和刪除操作，數(shù)據(jù)是先進(jìn)后出的。

判定一個順序棧S（?？臻g大小為n）為空的條件是（）。

A.S->top==T

B.S->top!=-l

C.S->top==n

D.S->top!=n

答案：A

知識點(diǎn)：第三章

難度：2

解析：判定一個順序棧S（?？臻g大小為n）為空的條件是S->top==T。

在一個鏈隊(duì)列中，front和rear分別為頭指針和尾指針，則插入一個結(jié)點(diǎn)s的操作為（

A.front=front->next

B.s->next=rear;rear=s

C.rear->next=s;rear=s;

D.s->next=front;front=s;

答案：C

知識點(diǎn)：第三章

難度：3

解析：在隊(duì)尾插入一個節(jié)點(diǎn)。

一個隊(duì)列的入隊(duì)序列是1,2,3,4,則隊(duì)列的出隊(duì)序列是（）。

A.1,2,3,4

B.4,3,2,1

C.1,4,3,2

D.3,4,1,2

答案：A

知識點(diǎn)：第三章

難度：1

解析：隊(duì)列的特點(diǎn)是在一段進(jìn)行插入，在另一端進(jìn)行刪除。數(shù)據(jù)是先進(jìn)先出的。

依次在初始為空的隊(duì)列中插入元素a,b,c,d以后，緊接著做了兩次刪除操作，此時的隊(duì)頭元

素是（）。

A.a

B.b

C.c

D.d

答案：C

知識點(diǎn)：第三章

難度：1

解析：隊(duì)列的特點(diǎn)是在一段進(jìn)行插入，在另一端進(jìn)行刪除。數(shù)據(jù)是先進(jìn)先出的。

正常情況下，刪除非空的順序存儲結(jié)構(gòu)的堆棧的棧頂元素，棧頂指針top的變化是（）。

A.top不變

B.top=0

C.top=top+l

D.top=topT

答案：D

知識點(diǎn)：第三章

難度：2

解析：棧的特點(diǎn)是只能在一端進(jìn)行插入和刪除操作，數(shù)據(jù)是先進(jìn)后出的。

當(dāng)用大小為N的數(shù)組存儲順序循環(huán)隊(duì)列時，該隊(duì)列的最大長度為（）。

A.N

B.N+1

C.N-1

D.N-2

答案：c

知識點(diǎn)：第三章

難度：4

解析：循環(huán)隊(duì)列中，需要一個借用一個空閑空間來區(qū)分隊(duì)空和隊(duì)滿兩個條件.因此，最大長

度為NT。

隊(duì)列的刪除操作是在（）。

A.隊(duì)首

B.隊(duì)尾

C.隊(duì)前

D.隊(duì)后

答案：A

知識點(diǎn)：第三章

難度：2

解析：解析：隊(duì)列的特點(diǎn)是在一段進(jìn)行插入，在另一端進(jìn)行刪除。數(shù)據(jù)是先進(jìn)先出的。隊(duì)尾

rear是數(shù)據(jù)插入的位置，每插入一個元素，rear++?隊(duì)首front是數(shù)據(jù)刪除的位置，每刪除

一個元素，front++o另外還要考慮到循環(huán)隊(duì)列的問題。

若讓元素1,2,3依次進(jìn)棧，則出棧次序不可能是（）。

A.3,2,1

B.2,1,3

C.3,1,2

D.1,3,2

答案：C

知識點(diǎn)：第三章

難度：3

解析：棧的特點(diǎn)是只能在一端進(jìn)行插入和刪除操作，數(shù)據(jù)是先進(jìn)后出的。

循環(huán)隊(duì)列用數(shù)組A[0,mT]存放其元素值，已知其頭尾指針分別是front和rear,則當(dāng)前隊(duì)列

中的元素個數(shù)是（）。

A.（rear-front+m）%m

B.rear-front+1

C.rear-front-1

D.rear-front

答案：A

知識點(diǎn)：第三章

難度：4

解析：隊(duì)列的特點(diǎn)是在一段進(jìn)行插入，在另一端進(jìn)行刪除。數(shù)據(jù)是先進(jìn)先出的。隊(duì)尾rear

是數(shù)據(jù)插入的位置，每插入一個元素，rear++0隊(duì)首front是數(shù)據(jù)刪除的位置，每刪除一個

元素，front++o另外還要考慮到循環(huán)隊(duì)列的問題。

鏈?zhǔn)綏Ｅc順序棧相比，一個比較明顯的優(yōu)點(diǎn)是（）。

A.插入操作更加方便

B.通常不會出現(xiàn)棧滿的情況

C.不會出現(xiàn)?？盏那闆r

D.刪除操作更加方便

答案：B

知識點(diǎn)：第三章

難度：3

解析：略

棧和隊(duì)列的共同點(diǎn)是（）。

A.都是先進(jìn)先出

B.都是先進(jìn)后出

C.只允許在端點(diǎn)處插入和刪除元素

D.沒有共同點(diǎn)

答案：C

知識點(diǎn)：第三章

難度：1

解析：略

在解決計算機(jī)主機(jī)和打印機(jī)之間速度不匹配問題時，通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機(jī)將

要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則從該緩沖區(qū)中取走數(shù)據(jù)打印。該緩沖區(qū)應(yīng)該是

一個（）結(jié)構(gòu)。

A.堆棧

B.隊(duì)列

C.數(shù)組

D.線性表

答案：B

知識點(diǎn)：第三章

難度：5

解析：這是隊(duì)列的一個應(yīng)用。

棧和隊(duì)列都是（）。

A.鏈?zhǔn)酱鎯Φ木€性結(jié)構(gòu)

B.鏈?zhǔn)酱鎯Φ姆蔷€性結(jié)構(gòu)

C.限制存取點(diǎn)的線性結(jié)構(gòu)

D.限制存取點(diǎn)的非線性結(jié)構(gòu)

答案：C

知識點(diǎn)：第三章

難度：3

解析：略。

在一個鏈隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，刪除一個結(jié)點(diǎn)的操作是

（）。

A.front=front->next

B.rear=rear->next

C.rear->next=front

D.front->next=rear

答案：A

知識點(diǎn)：第三章

難度：4

解析：略。

隊(duì)和棧的主要區(qū)別是（）。

A.邏輯結(jié)構(gòu)不同

B.存儲結(jié)構(gòu)不同

C.所包含的運(yùn)算個數(shù)不同

1）.限定插入和刪除的位置不同

答案：D

知識點(diǎn)：第三章

難度：3

解析：略。

下面關(guān)于串的的敘述中，哪一個是不正確的？（）

A.串是字符的有限序列

B.空串是由空格構(gòu)成的串

C.模式匹配是串的一種重要運(yùn)算

D.串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯?/p>

答案：B

知識點(diǎn)：第四章

難度：1

解析：空串是不含有任何字符的串。

串Si='ABCDEFG'的長度為（）。

A.7

B.8

C.6

D.9

答案：A

知識點(diǎn)：第四章

難度：1

解析：略。

串S1='ABCDEFG',S2='9898',則concat(SI,S2)的結(jié)果為()。

A.ABCDEFG9898

B.9898ABCDEFG

C.ABCDEFG

D.9898

答案：A

知識點(diǎn)：第四章

難度：2

解析：略。

串'ABCDEFG',S2='998',則instr(SI,3,S2)的結(jié)果為()。

A.ABCDEFG9898

B.9898ABCDEFG

C.ABC998DEFG

D.ABC998G

答案：C

知識點(diǎn)：第四章

難度：2

解析：略。

串S1='ABCDEFG',S2='998',則repstr(S1,3,S2)的結(jié)果為()。

A.ABCDEFG9898

B.9898ABCDEFG

C.ABC998DEFG

D.ABC998G

答案：D

知識點(diǎn)：第四章

難度：2

解析：略。

串S1='ABCDEFG',S2='998',則substr(SI,3,2)的結(jié)果為()。

A.ABC

B.CD

C.CDEF

D.FG

答案：B

知識點(diǎn)：第四章

難度：2

解析：略。

串S1='Iamastudent.',S2='good',則concat(SI,S2)的結(jié)果為()。

A.Iamastudent,good

B.Iamagoodstudent.

C.Iamgoodastudent.

D.goodIamastudent

答案：A

知識點(diǎn)：第四章

難度：2

解析：略。

串Sl='Iamastudent.',S2='good',則instr(SI,6,S2)的結(jié)果為()。

A.Iamagoodstudent.

B.Iamagoodstudent.

C.Iamgoodastudent.

D.goodIamastudent

答案：A

知識點(diǎn)：第四章

難度：2

解析：略。

串Sl=i1amastudent.J,S2='good',則repstr(SI,3,S2)的結(jié)果為()。

A.Iamgoodstudent.

B.Iagoodstudent.

C.Iamagoodstudent.

D.Iagoodstudent.

答案：D

知識點(diǎn)：第四章

難度：2

解析：略。

串Sl=*Iamastudent.*,S2='good',則substr（SI,8,7）的結(jié)果為（）。

A.am

B.student

C.good

D.Iamastudent,good

答案：B

知識點(diǎn)：第四章

難度：2

解析：略。

串Sl='Iamastudent.*,S2='good',則delstr（SI,6,1）的結(jié)果為（）。

A.Iamastudent,good

B.Iamastu.

C.Iamstudent.

D.Iastudent.

答案：C

知識點(diǎn)：第四章

難度：2

解析：略。

設(shè)有兩個串p和q,其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為（）

A.求子串

B.聯(lián)接

C.匹配

D.求串長

答案：C

知識點(diǎn)：第四章

難度：2

解析：略。

已知串S='abcac',其Next數(shù)組值為（）。

A.-10001

B.-11001

C.-10010

D.-11000

答案：A

知識點(diǎn)：第四章

難度：3

解析:略。

串'abab'的next數(shù)組為（）。

A.-1002

B.-1110

C.-1001

D.-1101

答案：C

知識點(diǎn)：第四章

難度：3

解析：略。

字符串'aaaab'的next為（）

A.-10113

B.-10223

C.-10122

D.-10123

答案：D

知識點(diǎn)：第四章

難度：3

解析：略。

串的長度是指（）

A.串中所含不同字母的個數(shù)

B.串中所含字符的個數(shù)

C.串中所含不同字符的個數(shù)

D.串中所含非空格字符的個數(shù)

答案：B

知識點(diǎn)：第四章

難度：1

解析：略。

設(shè)數(shù)組a[L.10,5..15]的元素以行為主序存放，每個元素占用4個存儲單元，則數(shù)組元素

a[i,j]（l<iW10,5<jW15）的地址計算公式為（）

A.a-204+2i+j

B.a-204+40i+4j

C.a-84+i+j

D.a-64+44i+4j

答案：D

知識點(diǎn)：第五章

難度：3

解析：a[i,j]=a+((i-1)*(15-5+1)+(j-5))*4

對于二維數(shù)組A[L.4,3..6],設(shè)每個元素占兩個存儲單元，以行主序存儲，則元素A[3,4]

相對于數(shù)組空間起始地址的偏移量是()o

A.12

B.14

C.16

D.18

答案：D

知識點(diǎn)：第五章

難度：3

解析：a[3,4]=a+((3-1)*(6-3+1)+4-3)*2

對于二維數(shù)組A[l..4,3??6],設(shè)每個元素占兩個存儲單元，以列主序存儲，則元素A[3,4]

相對于數(shù)組空間起始地址的偏移量是()o

A.12

B.14

C.16

D.18

答案：A

知識點(diǎn)：第五章

難度：3

解析:a[3,4]=a+((4-3)*(4-1+1)+3-1)*2

對于二維數(shù)組A[L.4,1..6],設(shè)每個元素占兩個存儲單元，以行主序存儲，則元素A[3,4]

相對于數(shù)組空間起始地址的偏移量是()。

A.12

B.30

C.16

D.18

答案：B

知識點(diǎn)：第五章

難度：2

解析：a[3,4]=a+((3-1)*(6-1+1)+4-1)*2

關(guān)于二維數(shù)組的描述中，不正確的是（）。

A.二維數(shù)組是順序存儲

B.二維數(shù)組是隨機(jī)存儲

C.二維數(shù)組是鏈?zhǔn)酱鎯?/p>

D.二維數(shù)組是散列存儲

答案：A

知識點(diǎn)：第五章

難度：1

解析：略。

將一個A[L.100,1..100]的三對角矩陣，按行優(yōu)先存入一維數(shù)組B[L.298]中,A中元素A666s

（即元素下標(biāo)）在B中的位置長為（）

A.198

B.195

C.197

答案：B

知識點(diǎn)：第五章

難度：3

解析：略。

三對角線矩陣以行序?yàn)橹黜樞虼鎯?，其存儲始址是B,每個元素占一個存儲

單元，則元素的存儲起始地址為（）（IWLjWn）

A.b+2*j+i-2

B.b+2*i+j-2

C.b+2*j+i-3

D.b+2*i+j-3

答案：D

知識點(diǎn)：第五章

難度：2

解析：略。

設(shè)二維數(shù)組A[m][n],每個數(shù)組元素占用d個存儲單元，第一個數(shù)組元素的存儲地址是如

Loc（a[0][0]）,求按行優(yōu)先順序存放的數(shù)組元素OWjWn-1）的存儲地

址。

A.Loc（a[0][O]+[（i-l）*n+j-l]*d

B.Loc（a[0][O]）+[i*n+j]*d

C.Loc(a[0][O]+[j*m+i]*d

D.Loc(a[0][O])+[(j-l)*m+i-l]*d

答案：C

知識點(diǎn)：第五章

難度：2

解析：略。

設(shè)二維數(shù)組A[m][n],每個數(shù)組元素占d個存儲單元，第1個數(shù)組元素的存儲地址是

Loc(a[0][0]),求按列優(yōu)先順序存放的數(shù)組元素a[j][j](OWiWm-1,OWjWnT)的存儲地

址⑶。

A.Loc(a[0][O]+[(i-l)*n+j-l]*d

B.Loc(a[0][0])+[i*n+j]*d

C.Loc(a[0][O]+[(j-l)*m+i]*d

D.Loc(a[0][O])+[j*m+i]*d

答案：B

知識點(diǎn)：第五章

難度：2

解析：略。

若將n階下三角矩陣A,按列優(yōu)先順序壓縮存放在一維數(shù)組F[n(n+1)/2]中，第一個非零元

素all,存于F[0]中，則應(yīng)存放到F[K]中的非零元素aij(lWjWn,lWjWi)的下標(biāo)i,i

與K的對應(yīng)關(guān)系是_(6)_。

A.(2n-j+l)j/2+i-j

B.(2n-j+2)(j-l)/2+i-j

C.(2n-i+l)i/2+j-i

D.(2n-i+2)i/2+j-i

答案：B

知識點(diǎn)：第五章

難度：5

解析：略。

二維數(shù)組A[12][18]采用列優(yōu)先的存儲方法，若每個元素各占3個存儲單元，且A[0][0]地

址為150,則元素A[9][7]的地址為()。

A.429

B.432

C.435

D.438

答案：A

知識點(diǎn)：第五章

難度:2

解析:AL9][7]=150+(7*12+9)*3

設(shè)有一個10階的對稱矩陣采用壓縮方式按行將矩陣中下三角部分的元素存入

一維數(shù)組B□中，A[0][0]存入B[0]中,則A[8][5]在B□中()位置。

A.32

B.33

C.41

D.65

答案：A

知識點(diǎn)：第五章

難度：3

解析：略。

若對n階對稱矩陣A以行序?yàn)橹餍蚍绞綄⑵湎氯切蔚脑?包括主對角線上所有元素)依次

存放于一維數(shù)組B[L.(n(n+l))/2]中，則在B中確定aij(i<j)的位置k的關(guān)系為()。

A.i*(i-l)/2+j

B.j*(j-l)/2+i

C.i*(i+l)/2+j

D.j*(j+l)/2+i

答案：A

知識點(diǎn)：第五章

難度：2

解析：略。

對稀疏矩陣進(jìn)行壓縮存儲目的是().

A.便于進(jìn)行矩陣運(yùn)算

B.便于輸入和輸出

C.節(jié)省存儲空間

D.降低運(yùn)算的時間復(fù)雜度

答案：C

知識點(diǎn)：第五章

難度：1

解析：略。

數(shù)組A[0..5,0..6]的每個元素占5個字節(jié)，將其按列優(yōu)先次序存儲在起始地址為1000的內(nèi)存

單元中，則元素A[5][5]的地址是（）。

A.1175

B.1180

C.1205

D.1210

答案：A

知識點(diǎn)：第五章

難度：2

解析：A[5][5]=1000+5*（5*6+5）?

采用稀疏矩陣的三元組表形式進(jìn)行壓縮存儲，若要完成對三元組表進(jìn)行轉(zhuǎn)置，只要將行和列

對換，這種說法（）。

A.正確

B.錯誤

C.無法確定

D.以上均不對

答案：B

知識點(diǎn)：第五章

難度：2

解析：略。

常對數(shù)組進(jìn)行兩種基本操作是（）。

A.建立和刪除

B.索引和修改

C.查找和修改

D.查找與索引

答案：C

知識點(diǎn)：第五章

難度：1

解析：略。

對一些特殊矩陣采用壓縮存儲的目的主要是為了（）。

A.表達(dá)變得簡單

B.對矩陣元素的存取變得簡單

C.去掉矩陣中的多余元素

D.減少不必要的存儲空間的開銷

答案：D

知識點(diǎn)：第五章

難度：1

解析：略。

設(shè)有一個10階的對稱矩陣A,采用壓縮存儲方式，以行序?yàn)橹鞔鎯?，all為第一個元素，其存

儲地址為1,每元素占1個地址空間，則a85的地址為()o

A.13

B.33

C.18

D.40

答案：B

知識點(diǎn)：第五章

難度：4

解析：a85=l+(1+7)*7/2+4=33。

設(shè)矩陣A是一個對稱矩陣，為了節(jié)省存儲，將其下三角部分按行序存放在一維數(shù)組

B[l,n(n-l)/2]中，對下三角部分中任一元素ai,j(i>=j),在一維數(shù)組B的下標(biāo)位置k的值是

(B)。

A.i(i-l)/2+j-l

B.i(i-l)/2+j

C.i(i+l)/2+j-l

D.i(i+l)/2+j

答案：C

知識點(diǎn)：第五章

難度：3

解析：略。

稀疏矩陣一般的壓縮存儲方法有兩種，即().

A.二維數(shù)組和三維數(shù)組

B.三元組和散列

C.三元組和十字鏈表

D.散列和十字鏈表

答案：C

知識點(diǎn)：第五章

難度：4

解析：略。

假設(shè)以三元組表表示稀疏矩陣，則與如圖所示三元組表對應(yīng)的4X5的稀疏矩陣是（注：矩

陣的行列下標(biāo)均從1開始）（）。

012-8

1146

2217

3253

431-5

533460、

LcrU00

A.

000

0400?

-8060、

0003

0400

0000,

-8060、

0003

0000

0400,

-8060、

0000

0403

0000,

答案：B

知識點(diǎn)：第五章

難度：2

解析：略。

在一顆非空二叉樹中，葉子節(jié)點(diǎn)的總數(shù)比度為2的節(jié)點(diǎn)總數(shù)多（）個。

A.-1

B.0

C.1

D.2

答案：C

知識點(diǎn)：第六章

難度：2

解析：這是二叉樹的一個性質(zhì)：非空二叉樹上葉結(jié)點(diǎn)數(shù)等于雙分支結(jié)點(diǎn)數(shù)加1。

在一棵完全二叉樹中，其根的序號為1，()可判定序號為P和q的兩個結(jié)點(diǎn)是否在同

一層。

A.|log2pj=|log2qj

B.Iog2p=logzq

C.|log2pj+1=|log2qj

D.|log2pj=|log2qj+1

答案：A

知識點(diǎn)：第六章

難度：3

解析：P和q是兩個結(jié)點(diǎn)的序號，計算以p和q為最后一個結(jié)點(diǎn)的樹的層次，利用二叉樹的

性質(zhì)：具有n個(n>0)結(jié)點(diǎn)的完全二叉樹的高度為「logzn+l］或Llogzn」+1。

如果根的層次為1,具有61個結(jié)點(diǎn)的完全二叉樹的高度為()

A.5

B.6

C.7

D.8

答案：B

知識點(diǎn)：第六章

難度：3

解析:利用二叉樹的性質(zhì)：具有n個(n>0)結(jié)點(diǎn)的完全二叉樹的高度為「logzn+1］或Llogzn」+1。

若二叉樹的先序遍歷序列為ABDECF,中序遍歷序列DBEAFC,則其后序遍歷序列為()。

A.DEBAFC

B.DEFBCA

C.DEBCFA

D.DEBFCA

答案：D

知識點(diǎn)：第六章

難度：3

解析：由二叉樹的先序遍歷序列和中序遍歷序列，可以得到一棵唯一的二叉樹,，然后計算后

序遍歷序列。

()的遍歷需要先訪問根節(jié)點(diǎn)，再訪問左子樹，最后訪問右子樹。

A.前序遍歷

B.中序遍歷

C.后序遍歷

答案：A

知識點(diǎn)：第六章

難度：2

解析：先序遍歷、中序遍歷和后序遍歷主要從訪問根節(jié)點(diǎn)的順序上來區(qū)分。先序遍歷先訪問

根節(jié)點(diǎn)，再訪問左子樹，最后訪問右子樹。

()的遍歷需要先訪問左子樹，再訪問根節(jié)點(diǎn)，最后訪問右子樹。

A.前序遍歷

B.中序遍歷

C.后序遍歷

答案：B

知識點(diǎn)：第六章

難度：2

解析：先序遍歷、中序遍歷和后序遍歷主要從訪問根節(jié)點(diǎn)的順序上來區(qū)分。中序遍歷先訪問

左子樹，再訪問根節(jié)點(diǎn)，最后訪問右子樹。

()的遍歷需要先訪問左子樹，再訪問右子樹，最后訪問根節(jié)點(diǎn).

A.前序遍歷

B.中序遍歷

C.后序遍歷

答案：C

知識點(diǎn)：第六章

難度：2

解析：先序遍歷、中序遍歷和后序遍歷主要從訪問根節(jié)點(diǎn)的順序上來區(qū)分。后序遍歷先訪問

左子樹，再訪問右子樹，最后訪問根節(jié)點(diǎn)。

哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較小的結(jié)點(diǎn)離根()

A.不確定

B.較近

C.較遠(yuǎn)

答案：C

知識點(diǎn)：第六章

難度：3

解析：哈夫曼樹是帶權(quán)路徑長度最小的樹，因此，權(quán)值較小的節(jié)點(diǎn)離根較遠(yuǎn)。

樹中所有結(jié)點(diǎn)的度之和等于所有結(jié)點(diǎn)數(shù)加()。

A.0

B.1

C.-1

D.2

答案：C

知識點(diǎn)：第六章

難度：1

解析：結(jié)點(diǎn)的度之和等于其樹中分支的數(shù)量，而n個結(jié)點(diǎn)做成的樹中有nT個分支。

在一棵具有n個結(jié)點(diǎn)的二叉鏈表中，所有結(jié)點(diǎn)的空域個數(shù)等于()。

A.n

B.n-1

C)n+1

D)2*n

答案：c

知識點(diǎn)：第六章

難度：4

解析：二叉鏈表中每個結(jié)點(diǎn)有兩個指針域，n個結(jié)點(diǎn)共有2*n個指針域。N個節(jié)點(diǎn)需要n-1

個分支，因此，有n-1個分支是被占用的。則空閑的指針域包括2*n-(n-l)=n+l個。

在一棵具有n個結(jié)點(diǎn)的二叉鏈表中，不為空的指針域有()個。

A.n

B.n-1

C)n+1

D)2*n

答案：B

知識點(diǎn)：第六章

難度：4

解析：二叉鏈表中每個結(jié)點(diǎn)有兩個指針域，n個結(jié)點(diǎn)共有2*n個指針域。N個節(jié)點(diǎn)需要n-1

個分支，因此，有n-1個分支是被占用的。

含有10個結(jié)點(diǎn)的二叉樹中，度為。的結(jié)點(diǎn)數(shù)為4,則度為2的結(jié)點(diǎn)數(shù)為（）

A.3

B.4

C.5

D.6

答案：A

知識點(diǎn)：第六章

難度：2

解析：這是二叉樹的一個性質(zhì)：非空二叉樹上葉結(jié)點(diǎn)數(shù)等于雙分支結(jié)點(diǎn)數(shù)加1。

除第一層外，滿二叉樹中每一層結(jié)點(diǎn)個數(shù)是上一層結(jié)點(diǎn)個數(shù)的（）

A.1/2倍

B.1倍

C.2倍

D.3倍

答案：C

知識點(diǎn)：第六章

難度：5

解析：滿二叉樹中，每個分支節(jié)點(diǎn)的度數(shù)都是2.除第一層外，滿二叉樹中每一層結(jié)點(diǎn)個數(shù)

是上一層結(jié)點(diǎn)個數(shù)的2倍。

對一棵有100個結(jié)點(diǎn)的完全二叉樹按層編號，則編號為49的結(jié)點(diǎn)，它的父結(jié)點(diǎn)的編號為

（）

A.24

B.25

C.98

D.99

答案：A

知識點(diǎn)：第六章

難度：4

解析：根據(jù)二叉樹的性質(zhì)4對完全二叉樹中編號為i的結(jié)點(diǎn)（IWiWn,n》l,n為結(jié)點(diǎn)數(shù)）

有如下性質(zhì)。

（1）若編號為i的結(jié)點(diǎn)有左孩子，則左孩子結(jié)點(diǎn)的編號為2i；若編號為i的結(jié)點(diǎn)有右孩子，

則右孩子結(jié)點(diǎn)的編號為2i+l。

（2）除樹根結(jié)點(diǎn)外，若一個結(jié)點(diǎn)的編號為i,則它的雙親結(jié)點(diǎn)的編號為i/2o

（3）若iWLn/2」，BP2iWn,則編號為i的結(jié)點(diǎn)為分支結(jié)點(diǎn)，否則為葉子結(jié)點(diǎn)。

（4）若n為奇數(shù)，則每個分支結(jié)點(diǎn)都既有左孩子，又有右孩子；若n為偶數(shù)，則編號最大

的分支結(jié)點(diǎn)（編號為n/2）只有左孩子，沒有右孩子，其余分支結(jié)點(diǎn)左、右孩子都有。

可以惟一地轉(zhuǎn)化成一棵一般樹的二叉樹的特點(diǎn)是（）

A.根結(jié)點(diǎn)無左孩子

B.根結(jié)點(diǎn)無右孩子

C.根結(jié)點(diǎn)有兩個孩子

D.根結(jié)點(diǎn)沒有孩子

答案：B

知識點(diǎn)：第六章

難度：5

解析：將一棵一般樹轉(zhuǎn)化為二叉樹時，樹中的兄弟節(jié)點(diǎn)連接成第一個孩子節(jié)點(diǎn)的右分支。故

在生成的二叉樹中，根結(jié)點(diǎn)沒有右孩子，因?yàn)楦Y(jié)點(diǎn)沒有兄弟結(jié)點(diǎn)。

設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為

（）?

A.2h

B.2h-l

C.2h+l

D.h+1

答案：B

知識點(diǎn)：第六章

難度：5

解析：當(dāng)樹中每層只有一個分支結(jié)點(diǎn)時，結(jié)點(diǎn)數(shù)最少，并且滿足只有度為0和度為2的結(jié)點(diǎn)。

此時，結(jié)點(diǎn)數(shù)量為2h-l.

在一棵度為3的樹中，度為3的節(jié)點(diǎn)個數(shù)為2,度為2的節(jié)點(diǎn)個數(shù)為2,則度為0的節(jié)點(diǎn)個

數(shù)為（）。

A.4

B.5

C.6

D.7

答案：C

知識點(diǎn)：第六章

難度：5

解析：結(jié)點(diǎn)個數(shù)為:n0+nl+n2+n3,分支個數(shù)為：3*n3+2*n2+l*nl+0*n0.

因此有：nO+n1+n2+n3=3*n3+2*n2+1*n1+0*n0+1

n0=2*n3+n2=2*2+2=6

將一株有100個節(jié)點(diǎn)的完全二叉樹從上到下，從左到右依次進(jìn)行編號，根節(jié)點(diǎn)的編號為1,

則編號為49的節(jié)點(diǎn)的左孩子編號為（）。

A.98

B.89

C.50

D.沒有孩子

答案：A

知識點(diǎn)：第六章

難度：4

解析：根據(jù)二叉樹的性質(zhì)4對完全二叉樹中編號為i的結(jié)點(diǎn)（IWiWn,nel,n為結(jié)點(diǎn)數(shù)）

有如下性質(zhì)。

（1）若編號為i的結(jié)點(diǎn)有左孩子，則左孩子結(jié)點(diǎn)的編號為2i；若編號為i的結(jié)點(diǎn)有右孩子，

則右孩子結(jié)點(diǎn)的編號為2i+l。

（2）除樹根結(jié)點(diǎn)外，若一個結(jié)點(diǎn)的編號為i,則它的雙親結(jié)點(diǎn)的編號為i/2。

（3）若iWLn/2J,BP2iWn,則編號為i的結(jié)點(diǎn)為分支結(jié)點(diǎn)，否則為葉子結(jié)點(diǎn)。

（4）若n為奇數(shù)，則每個分支結(jié)點(diǎn)都既有左孩子，又有右孩子；若n為偶數(shù)，則編號最大

的分支結(jié)點(diǎn)（編號為n/2）只有左孩子，沒有右孩子，其余分支結(jié)點(diǎn)左、右孩子都有。

下列圖示的順序存儲結(jié)構(gòu)表示的二叉樹是（）

答案：A

知識點(diǎn)：第六章

難度：3

解析：順序存儲按照完全二叉樹對應(yīng)節(jié)點(diǎn)的編號，作為數(shù)組的下標(biāo)值來存儲數(shù)據(jù)。

樹最適合用來表示（）。

A.有序數(shù)據(jù)元素

B.無序數(shù)據(jù)元素

C.元素之間具有分支層次關(guān)系的數(shù)據(jù)

D.元素之間無聯(lián)系的數(shù)據(jù)

答案：C

知識點(diǎn)：第六章

難度：1

解析：層次結(jié)構(gòu)的1對多的關(guān)系，是樹形結(jié)構(gòu)的特點(diǎn)。

在一個非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊（）。

A.只有右子樹上的所有結(jié)點(diǎn)

B.只有右子樹上的部分結(jié)點(diǎn)

C.只有左子樹的上的部分結(jié)點(diǎn)

D.只有左子樹上的所有結(jié)點(diǎn)

答案：A

知識點(diǎn)：第六章

難度：3

解析：這是由中序遍歷的規(guī)則決定的。先遍歷左子樹，再訪問根節(jié)點(diǎn)，最后訪問右子樹。

在二叉樹的（）遍歷序列中，根節(jié)點(diǎn)總是在最前面。

A.先序

B.中序

C.后序

D.不確定

答案：A

知識點(diǎn)：第六章

難度：2

解析：這是由先序遍歷的規(guī)則決定的。先訪問根節(jié)點(diǎn)，再遍歷左子樹，最后訪問右子樹。

在二叉樹的（）遍歷序列中，根節(jié)點(diǎn)總是在最后面。

A.先序

B.中序

C.后序

D.不確定

答案：C

知識點(diǎn)：第六章

難度：2

解析：這是由后序遍歷的規(guī)則決定的。先遍歷左子樹，再遍歷右子樹，最后訪問根節(jié)點(diǎn)。

任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中相對次序（）?

A.不發(fā)生改變

B.發(fā)生改變

C.不能確定

D.以上都不對

答案：D

知識點(diǎn)：第六章

難度：4

解析：葉節(jié)點(diǎn)出現(xiàn)的次序，在先序、中序和后序遍歷序列中是沒有規(guī)律的.

在有n個葉子結(jié)點(diǎn)的哈夫曼樹中，其結(jié)點(diǎn)總數(shù)為（）。

A.不確定

B.2n

C.2n+l

D.2n-l

答案：D

知識點(diǎn)：第六章

難度：4

解析：這是哈夫曼樹的構(gòu)造過程決定的。

權(quán)值為｛1,2,6,8｝的四個結(jié)點(diǎn)構(gòu)成的哈夫曼樹的帶權(quán)路徑長度是（）。

A.18

B.28

C.19

D.29

答案：D

知識點(diǎn)：第六章

難度：4

解析：構(gòu)造的哈夫曼樹為：

17

/\

89

/\

36

/\

12

帶權(quán)路徑長度為：8*1+6*2+1*3+2*3=29

對一個滿二叉樹，m個樹葉，k個分枝結(jié)點(diǎn)，n個結(jié)點(diǎn)，則（）?

A.n=m+l

B.m+l=2n

C.m=k-l

D.n=2k+l

答案：D

知識點(diǎn)：第六章

難度：5

解析：略。

哈夫曼樹是（）=

A.帶權(quán)路徑長度最短的樹

B.帶權(quán)路徑長度最長的樹

C.遍歷最優(yōu)的樹

D.遍歷最短的樹

答案：A

知識點(diǎn)：第六章

難度：1

解析：略。

下列描述中，不正確的是（）?

A.任何一棵二叉樹都能還原為一棵樹

B.任何一棵樹都能轉(zhuǎn)換為一棵二叉樹

C一棵樹轉(zhuǎn)換為二叉樹后，根節(jié)點(diǎn)的右分支總是空

D.一棵樹轉(zhuǎn)換為二叉樹后，根節(jié)點(diǎn)的左分支總是空

答案：C

知識點(diǎn)：第六章

難度：2

解析：略。

具有同一雙親的結(jié)點(diǎn)，互相稱為（）。

A.葉結(jié)點(diǎn)

B.兄弟結(jié)點(diǎn)

C.朋友結(jié)點(diǎn)

D.分支結(jié)點(diǎn)

答案：B

知識點(diǎn)：第六章

難度：1

解析：略。

在含有n個頂點(diǎn)和e條邊的無向圖的鄰接矩陣中，零元素的個數(shù)為