數(shù)據(jù)結(jié)構練習題1

一、選擇題

1.下面說法錯誤的是一c_。

(1)算法原地工作的含義是指不需要任何額外的輔助空間。

(2)在相同的規(guī)模n下，復雜度O(n)的撒在時間上總是優(yōu)于復雜度0(2。)的算法。

(3)所謂時間復雜度是指最壞情況下，估算算法執(zhí)行時間的一個上界。

(4)同一個算法，實現(xiàn)語言的級別越高，執(zhí)行效率越低。

A、(1)B、(1)(2)C、(1)(4)D、(3)

2.一個遞歸算法必須包括__B_。

A、遞歸部分B、終止條件和遞歸部分

C、迭代部分D、終止條件和迭代部分

3.數(shù)據(jù)的_C_包括查找、插入、刪除、更新、排序等操作類型。

A、存儲結(jié)構B、邏輯結(jié)構

C、基本運算D、算法描述

4.在數(shù)據(jù)結(jié)構中，從邏輯上可以把數(shù)據(jù)結(jié)構分成_

A、動態(tài)結(jié)構和靜態(tài)結(jié)構B、緊湊結(jié)構利非緊湊結(jié)構

C、線性結(jié)構和非線性結(jié)構D、內(nèi)部結(jié)構和外部結(jié)構

5.與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關的是數(shù)據(jù)的_C

A、存儲結(jié)構B、存儲實現(xiàn)

C、邏輯結(jié)構D、運算實現(xiàn)

6.通常要求同一邏輯結(jié)構中的所有數(shù)據(jù)元素具有相同的特性，這意味著一B_。

A、數(shù)據(jù)具有同一特點

B、不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，而且對應數(shù)據(jù)項的類型要致

C、每個數(shù)據(jù)元素都一樣

D、數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等

7.以下說法正確的是__D_?

A、數(shù)據(jù)元素是數(shù)據(jù)的最小單位

B、數(shù)據(jù)項是數(shù)據(jù)的基本單位

C、數(shù)據(jù)結(jié)構是帶有結(jié)構的各數(shù)據(jù)項的集合

D、一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構

8.以下說法錯誤的是上_o

A、程序設計的實質(zhì)是數(shù)據(jù)處理

B、數(shù)據(jù)的邏輯結(jié)構是數(shù)據(jù)的組織形式，基本運算規(guī)定了數(shù)據(jù)的基本操作方式

C、運算實現(xiàn)是完成運算功能的算法或這些算法的設計

D、數(shù)據(jù)處理方式總是與數(shù)據(jù)的某種相應表示形式相聯(lián)系，反之亦然

9.下列程序段的時間復雜度為_B

x=n;

y=o；

while(x>=(y+l)*(y+l))

y=y+i;

A、0(n)B、0(n1/2)C、0(1)D、0(n2)

10.下列敘述中有關好的編程風格的正確描述是一C.。

A、程序中的注釋是可有可無的

B、對遞歸定義的數(shù)據(jù)結(jié)構不要使用遞歸過程

C、過程應是自封閉的，盡量少使用全程變量

D、多采用一些技巧以提高程序的運行效率

二、填空題

1.一個算法有5個特性：有窮性、確定性、可行性、有零個或多個輸入、有一個或

多個輸出。

2.算法的時間復雜度是指該算法所求解問題_規(guī)模(或頻度)的函數(shù)。

3.算法的可行性是指每一條_指令都應在有限的時間內(nèi)完成?

4、線性結(jié)構的特征：邏輯上滿足有且僅有一個開始結(jié)點和一個終端結(jié)點，且其余結(jié)點有一旦

僅有唯?的?個有接前趨和?個仃接后繼一。

5.數(shù)據(jù)的存儲結(jié)構被分為一順序、鏈接、一索引_和_散列4種。

6.存儲結(jié)構是邏輯結(jié)構的查僮實現(xiàn)，其基本目標是建立數(shù)據(jù)的一機內(nèi)表示?

7.數(shù)據(jù)表示任務是逐步完成的，即數(shù)據(jù)表示形式的變化過程是：_機外表示f

_邏輯結(jié)構f存儲結(jié)構o

8.數(shù)據(jù)處理任務也是逐步完成的，即轉(zhuǎn)化過程是：一處理要求一基本運

算_-_篁返?

9.從邏輯關系上講數(shù)據(jù)結(jié)構主要分為兩大類，它們是一線性結(jié)構和一非線性結(jié)構。

10.數(shù)據(jù)結(jié)構的基本任務是數(shù)據(jù)結(jié)構的一巡L和一實現(xiàn)_。

三、給出下列算法的時間復雜度。

1、Sum(intn)

{

intsum=0,i,j;

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

{

p=l;

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

P=P*j；

sum=sum+p;

}

return(sum);

?

T(n)=0(n2)

2、j=l；

while(j<=n)

{j=j*2；

?

O(log2n)

習題二

一、選擇題

1.線性表是具有n個_￡的有限序列。

A、表元素B、字符C、數(shù)據(jù)元素

D、數(shù)據(jù)項E、信息項

2.線性表的靜態(tài)鏈表存儲結(jié)構與順序存儲結(jié)構相比優(yōu)點是一C

A、所有的操作算法實現(xiàn)簡單B、便于隨機存儲

C、便于插入和刪除D、便于利用零散的存儲器空間

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

度為一C.。

A、O(log2n)B、0(1)

C、0(n)D、0(n2)

4.(1)靜態(tài)鏈表既有順序存儲的特點，又有動態(tài)鏈表的優(yōu)點。所以，它存取表中第i個元

素的時間與i無關；

(2)靜態(tài)鏈表中能容納元素個數(shù)的最大數(shù)在定義時就確定了，以后不能增加；

(3)靜態(tài)鏈表與動態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動.

以上錯誤的是__B—。

A、(1)、(2)B、(1)C、(1)、(2)、(3)D、(2)

5.將圖2-6所示的s所指結(jié)點加到p所指結(jié)點之后，其語句應為__D__o

A、s—>next=p+l;p—>next=s;

B、(*p).next=s;(*s).next=(*p).next;

C、s—>next=p—>next;p—>next=s—>next;

D、s—>next=p—>next;p->next=s;

P

s

圖2-6插入結(jié)點示意

6.在雙向鏈表存儲結(jié)構中，刪除p所指的結(jié)點時須修改指針A_o

A、p—>next—>prior=p—>prior;p—>prior—>next=p—>next;

B、p—>next=p—>next—>next;p—>next—>prior=p;

C、p—>prioi'■—>next=p;p—>prior=p—>prior—>prior;

D、p—>prior=p—>next—>next;p—>next=p—>prior—>prior;

7.在雙向循環(huán)鏈表中，在P指針所指的結(jié)點后插入q所指向的新結(jié)點，其修改指針的操作

是一￡。

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;

8.將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是A

A、nb.2n—1c.2nd.n—1

9.在一個長度為n的順序表中，在第i個元素(l&i&n+l)之前插入一個新元素時須向后

移動__B__個元素。

A、n—iB、n—i+1C、n—i—1D、i

10.線性表L=(ai，a2,……an),下列說法正確的是

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

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

C、表中諸元素的排列必須是由小到大或由大到小。

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

11.對單鏈表表示法，以下說法錯誤的是__c

A、數(shù)據(jù)域用于存儲線性表的一個數(shù)據(jù)元素

B、指針域(或鏈域)用于存放?個指向本結(jié)點所含數(shù)據(jù)元素的直接后繼所在結(jié)點的指針

C、所有數(shù)據(jù)通過指針的鏈接而組織成單鏈表

D、NULL稱為空指針，它不指向任何結(jié)點只起標志作用

12.若指定有n個元素的向量，則建立一個有序單向鏈表的時間復雜性的量級是_C_

2

A、0(1)B、0(n)A0(n)D、O(nlog2n)

13.以下說法正確的是_o

A、順序存儲方式的優(yōu)點是存儲密度大且插入、刪除運算率高

B、鏈表的每個結(jié)點中都恰好包含一個指針

C、線性表的順序存儲結(jié)構優(yōu)于鏈式存儲結(jié)構

D、順序存儲結(jié)構屬于靜態(tài)結(jié)構而鏈式結(jié)構屬于動態(tài)結(jié)構

14.以下說法錯誤的是_A_

A、對循環(huán)鏈表來說，從表中任一結(jié)點出發(fā)都能通過前后移操作掃描整個循環(huán)鏈表

B、對單鏈表來說，只有從頭結(jié)點開始才能掃描表中全部結(jié)點

C、雙鏈表的特點是找結(jié)點的前趨和后繼都很容易

D、對雙鏈中來說，結(jié)點*p的存儲位置既存放在其前趨結(jié)點的后繼指針域中，也存放在它

的后繼結(jié)點的前趨指針中

15.以下說法錯誤的是_D

A、求表長、定位這兩種運算在采用順序存儲結(jié)構時實現(xiàn)的效率不比采用鏈式存儲結(jié)構時實

現(xiàn)的效率低

B、序存儲的線性表可以隨機存取

C、由于順序存儲要求連續(xù)的存儲區(qū)域，所以在存儲管理上不夠靈活

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

二、判斷題

1.線性表采用鏈表存儲時;結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。（錯）

2.在具有頭結(jié)點的鏈式存儲結(jié)構中，頭指針指向鏈表中的第一個數(shù)據(jù)結(jié)點。（錯）

3.順序存儲的線性表可以隨機存取。（對）

4.在單鏈表中，要訪問某個結(jié)點，只要知道該結(jié)點的指針即可；因此，單鏈表是一種隨機存

儲結(jié)構。（錯）

5.在線性表的順序存儲結(jié)構中，插入和刪除元素時，移動元素的個數(shù)與該元素的位置有關。

（對）

6.順序存儲結(jié)構屬于靜態(tài)結(jié)構，鏈式結(jié)構屬于動態(tài)結(jié)構。（對）

3、簡述以下算法的功能：

statusA（linkedistL）

{〃L是無表頭結(jié)點的單鏈表

if（L&&L—>next）

{Q=L;L=L—>next;P=L;

while（P—>next）P=P—>next;

P—>next=Q;Q—>next=NULL;

returnok;

}//A

本程序?qū)崿F(xiàn)的功能就是：如果L的長度不小于2,則將首元結(jié)點刪去并插入到末尾。

4、寫出下列程序段的輸出結(jié)果。（假設此棧中元素的類型是char）

voidmain()pop(s,x)

{stacks;push(s,'H');

charx,y;while(!stackEmpty(a))

InitStack(a){pop(s,y);

,

x=L'zy='O'printf(y);

push(s,x);)

push(s,x);printf(x)

push(s,y);)

push(s,x);

push(s,'E');

push(s,x);

此題的輸出結(jié)果是HELOLLL,

5、以下為單鏈表刪除運算，分析算法，請在_______處填上正確的語句。

voiddelete_lkist(lklisthead,inti)

{p=find_lkist(head,i-l);

if(p!=NULL)&&(D->next!=NULL)

{q=D—>next;

p—>next=q—>next;

free(q);

}

elseerror("不存在第i個結(jié)點”)

}

6、以下為順序表的定位運算，分析算法，請在____處用正確的語句予以填充。

intlocate_sqlist(sqlistL,datatypeX)

{0,；

while(i￡L>last)&&(Ldata[i-l]!=X)i++;

if(iWL.Iast_)return(i);

elsereturn(O);

}

7、以下為單鏈表的建表算法，分析算法，請在一處填上正確的語句

Iklistcreate_lklist2()

{head=malloc(size);

p=head;

scanf("%f",%x);

while(x!='$')

{q=malloc(size);

q—>data=x;

p—>next=q;

p=q_；

scanf(

}

_p—>next=NULL_;

return(head);

?

此算法的量級為-0(n)

習題三

一、選擇題

1、若用單鏈表來表示隊列，則應該選用一上

A、帶尾指針的非循環(huán)鏈表B、帶尾指針的循環(huán)鏈表

C、帶頭指針的非循環(huán)鏈表D、帶頭指針的循環(huán)鏈表

2、若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當rear和front的值分別為。和3。當

從隊列中刪除?個元素，再加入兩個元素后，rear和front的值分別是一上一。

A、1和5B、2和4

C、4和2D、5和1

3、設棧的輸入序列為1、2、3、4,則__C_不可能是其出棧序列。

A、1243B、2134C、1432D、4312E、3214

4、已知一算術表達式的中綴形式為A+B*C-D/E,后綴形式為ABC*+DE/-,其前綴形

式為_C_。

A、-A+B*C/DEB、-A+B*CD/E

C、-+*ABC/DED、-4-A*BC/DE

5、設棧的輸入序列是1、2、…、n,若輸出序列的第一個元素是n,則第i個輸出元素

是一上一。

A、不確定B、n-i+1C、iD、n-i

6、假定一個順序循環(huán)隊列的隊首和隊尾指針分別用front和rear表示，則判隊空的條件

是_2_。

A、front+l==rearB、front==rear+l

C、front==0D、front==rear

7、假定一個順序循環(huán)隊列存儲于數(shù)組A[n]中，其隊首和隊尾指針分別用front和rear

表示，則判斷隊滿的條件是_B

A、(rear-l)%n==frontB、(rear+l)%n==front

C、rear==(front-l)%nD、rear==(front+l)%n

8、一個棧的的輸入序列為12345,則下列序列中不可能是棧的輸出序列的是_B

A、23415B、54132C、23145D、15432

9、若一個棧的輸入序列是1、2、3、…、n,輸出序列的第一個元素是i,則第i個輸出元

素是__D_。

A.i-j-1B、i-jC、j-i+1D、不確定

10、用單鏈表表示的鏈式隊列的隊頭在鏈表的_上一位置。

A、鏈頭B、鏈尾C、鏈中

11、設計一個判別表達式中左、右括號是否配對出現(xiàn)的算法，采用__D_數(shù)據(jù)結(jié)構最佳。

A、線性表的順序存儲結(jié)構B、隊列

C、線性表的鏈式存儲結(jié)構D、棧

12、在下列算法描述中，涉及到隊運算的算法是__D_o

A、表達式求值算法B、深度優(yōu)先搜索

C、二叉樹遍歷D、廣度優(yōu)先搜索

13、棧的插入和刪除操作在一A_進行。

A、棧頂B、棧底C、任意位置D、指定位置

14、在一個順序循環(huán)隊列中，隊首指針指向隊首元素的—A_位置。

A、前一個B、后一個C、當前D、最后

15、當利用大小為N的數(shù)組存儲順序循環(huán)隊列時，該隊列的最大長度為衛(wèi)

A、N-2B、N-lC、ND、N+1

16、如果以鏈表作為棧的存儲結(jié)構，則退棧操作時__C_o

A、必須判別棧是否滿B、判別棧元素的類型

C、必須判別棧是否空D、對棧不作任何判別

17、鏈棧與順序棧相比有一個明顯的優(yōu)點，BP_B

A、插入操作更加方便B、通常不會出現(xiàn)棧滿的情況

C、不會出現(xiàn)?？盏那闆rD、刪除操作更加方便

二、填空題

1、中綠式a+b*3+4*(c-d)對應的前綴式為++axb3x4-cd,若

a=l,b=2,c=3,d=4,則后綴式db/cc*a-b*+的運算結(jié)果為_18__。

2、用下標0開始的N元數(shù)組實現(xiàn)循環(huán)隊列時，為實現(xiàn)下標變量m加1后在數(shù)組有效下標

范圍內(nèi)循環(huán)，可采用的表達式是m=(m+1)%n_?

3、表達式求值是_找一應用的一個典型例子。

4、隊列是特殊的線性表，其特殊性在于_只允許在表的一端進行元素的插入而在另一端

進行元素的刪除_0

5、一個循環(huán)隊列存于A[M]中，假定隊首和隊尾指針分別為front和rear,則判斷隊空的

條件為_front==rear,判斷隊滿的條件為(rear+1)%M==front_。

6、向-一個循環(huán)隊列存入新元素時，需要首先移動隊尾指針然后再向它所指位置一在

入一新元素。

7、_又稱為先進先出表。

8、棧是特殊的線性表，其特殊性在于_只允許在棧頂加入或刪除元素

9、棧又稱為后進先出表，隊列又成為_先進先出表。

10、在一個用一維數(shù)組A[N]表示的順序棧中，該棧所含元素的個數(shù)最少為_Q_個，最

多為__N_一個。

11、在一個用一維數(shù)組A[N]表示的循環(huán)隊列中，該隊列中的元素個數(shù)最少為0個，最

多為—Nd.一個。

習題四

一、選擇題

1、設有兩個串p和q，求q和p中首次出現(xiàn)的位置的運算稱作一C_?

A、連接B、求子串C、模式匹配D、求串長

2、若串S='goodstudent’,其子串的數(shù)目是_C_。

A、12B、79C、78D、13

3、串是一種特殊的線性表，其特殊性體現(xiàn)在_B_。

A、可以順序存儲B、數(shù)據(jù)元素是?個字符

C、可以鏈接存儲D、數(shù)據(jù)元素可以是多個字符

4、串是任意有限個__D

A、符號構成的集合B、符號構成的序列

C、字符構成的集合D、字符構成的序列

5、已知模式串T='abcdabcd',則其next數(shù)組值為__B_

A,00123412B、01111234

C、01232412D、11213412

6、二維數(shù)組A的每個元素是由6個字符組成的串，其行下標i=0、1......8,列下標n

個]X110=[9i-108n=9j-10]8kl,2.....10。若A按行先存儲，元素A[8,5]

的起始地址與當A按列先存儲時的元素的—B—的起始地址相同。設每個字符占一個字

節(jié)。

A、A[8,5]B、A[3,10]C、A[5,8]D、A[0,9]

7、數(shù)組SZ[-3..5O,0..10]含有元素數(shù)目為一上一o

A、88B、99C、80D、90

8、稀疏矩陣??般的壓縮存儲方法有_C_兩種。

A、二維數(shù)組和三維數(shù)組B、三元組和散列表

C、三元組和十字鏈表D、散列表和十字鏈表

9、一個nxn的對稱矩陣，如果以行或列為主序放入內(nèi)存，則其容量為_C

A、nxnnxn/2

C、(n+1)xn/2D、(n+1)x(n+l)/2

io、對數(shù)組經(jīng)常進行的兩種基本操作是_c

A、建立與刪除B、索引與修改

C、查找與修改D、查找與索引

11、二維數(shù)組A[1O..2O,5..10]采用行序為主序方式存儲，每個數(shù)據(jù)元素占4個存儲單

元，且A[10,5]的存儲地址是1000,則A[18,91的地址是A。

A、1208B、1212C、1368D、1364

二、填空題

1、兩個字符串相等的充分必要條件是_長度相等且對應位置上字符相同,o

2、字符在串中的位置，即是字符在該序列中的序號。

3、串是指_含n個字符的有限序列且n>=0?

4、設有串S1='Ianastudent7,S2=,st,,index(Sl,S2)=8_?

5、含零個字符的串稱為空一串，用油—表示；其他串稱為一韭空一串。任何串中所含

的一包的個數(shù)稱為該串的長度。

6、一個串中任意個連續(xù)字符組成的子序列稱為該串的一王串，該串稱為它的所有子串

的一串。

7、設數(shù)組a[1..50,L.80]的基地址為2000,每個元素占2個存儲單元，若一行序為主

序順序存儲,則元素a[45,68]的存儲地址為9174」若以列序為主序存儲,則元素a[45,

68]的存儲地址為_8788_?

8、數(shù)組結(jié)構是由固定數(shù)量的且由一個值和一組下標組成的數(shù)據(jù)元素構成，其元素間的下標

關系具有上下界約束及下標有序。

9、?維數(shù)組的邏輯結(jié)構是線性結(jié)構存儲結(jié)構是順序結(jié)構_；對二維或多維數(shù)組，

分為按以行為主序一和以列為主序_兩種不同的存儲方式。

10、需要壓縮存儲的矩陣可分為_特正矩陣和_場置矩陣兩種。

11、數(shù)組元素間的關系由_W來限定。

12、有一個8x8的下三角矩陣A,若采用行序為主序順序存儲于一維數(shù)組a[l..n],則n

的值為_36。

三、判斷題

1、稀疏矩陣壓縮存儲后，必會失去隨機存取的功能。（對）

2、數(shù)組是同類型值的集合。（錯）

3、數(shù)組是一種復雜的數(shù)據(jù)結(jié)構；數(shù)組元素之間的關系既不是線性的，也不是樹形的。（對）

習題五

一、選擇題

1、一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿

足__C_O

A、所有的結(jié)點均無左孩子B、所有的結(jié)點均無右孩子

C、只有一個葉子結(jié)點D、是任意一棵二叉樹

2、一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是一E一。

A、250B、500C、254D、505E、以上答案都不對

3、以下說法正確的是—C

A、若一個樹葉是某二叉樹前序遍歷序列中的最后一個結(jié)點，則它必是該子樹后序遍歷序

列中的最后一個結(jié)點

B、若一個樹葉是某二叉樹前序遍歷序列中的最后一個結(jié)點，則它必是該子樹中序遍歷序列

中的最后一個結(jié)點

C、在二叉樹中，具有兩個子女的父結(jié)點，在中序遍歷序列中，它的后繼結(jié)點最多只能有一

個子女結(jié)點

D、在二叉樹中，具有一個子女的父結(jié)點，在中序遍歷序列中，它沒有后繼子女結(jié)點

4、以下說法錯誤的是_。

A、哈夫曼樹是帶權路徑長度最短得數(shù)，路徑上權值較大的結(jié)點離根較近

B、若一個二叉樹的樹葉是某子樹中序遍歷序列中的第一個結(jié)點，則它必是該子樹后序遍歷

序列中的第一個結(jié)點

C、已知二叉樹的前序遍歷和后序遍歷并不能唯地確定這棵樹，因為不知道樹的根結(jié)點是

哪一個

D、在前序遍歷二叉樹的序列中，任何結(jié)點其子樹的所有結(jié)點都是直接跟在該結(jié)點之后的

5、一棵有124個葉結(jié)點的完全二叉樹，最多有_A一個結(jié)點。

A、247B、248C、249D、250E、251

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

A、不發(fā)生變化B、發(fā)生變化C、不能確定

7、設a、b為一棵二叉樹上的兩個結(jié)點。在中序遍歷時，a在b前面的條件是—衛(wèi)

A、a在b的右方B、a在b的左方

C、a是b的祖先D、a是b的子孫

8、設深度為k的二叉樹上只有度為0和度為2的結(jié)點，則這類二叉樹上所含的結(jié)點總數(shù)

為_,C

A、k+1B,2kC、2k-lD、2k+l

9、設有13個值，用它們組成?棵哈夫曼樹，則該哈夫曼樹共有_D_個結(jié)點。

A、13B、12C、26D、25

10,下面幾個符號串編碼集合中，不是前綴編碼的是__B

A、{0,10,110,1111}B、{11,10,001,101,0001}

C、｛00,010,0110,1000｝D、｛b,c,aa,ac,aba,abb,abc)

11、欲實現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不使用棧結(jié)構，最佳的方案是二叉樹采

用_上一存儲結(jié)構。

A、三叉鏈表B、廣義表C、二叉鏈表D、順序表

12、以下說法錯誤的是_B

A、存在這樣的二叉樹，對它采用任何次序遍歷其結(jié)點訪問序列均相同

B、二叉樹是樹的特殊情形

C、由樹轉(zhuǎn)換成二叉樹，其根結(jié)點的右子樹總是空的

D、在二叉樹只有一棵子樹的情況下也要明確指出該子樹是左子樹還是右子樹

13、樹的基本遍歷策略可分為先根遍歷和后根遍歷，二叉樹的基本遍歷策略可分為先序、

中序和后序三種遍歷。我們把由樹轉(zhuǎn)化得到的二叉樹稱該樹對應的二叉樹，則下面

_A一是正確的。

A、樹的先根遍歷序列與其對應的二叉樹先序遍歷序列相同

B、樹的后根遍歷序列與其對應的二叉樹后序遍歷序列相同

C、樹的先根遍歷序列與其對應的二叉樹中序遍歷序列相同

D、以上都不對

14、若以二叉樹的任一結(jié)點出發(fā)到根的路徑上所經(jīng)過的結(jié)點序列按其關鍵字有序。則該二

叉樹是__C

A、二叉排序樹B、哈夫曼樹遍歷樹cC、堆

15、下列有關二叉樹的說法正確的是_B___。

A、二叉樹的度為2B、一棵二叉樹度可以小于2

C、二叉樹中至少有一個結(jié)點的度為2D、二叉樹中任一個結(jié)點的度都為2

16、某二叉樹中序序列為ABCDEFG,后序序列為BDCAFGE,則前序序列是一旦

A、EGFACDBB、EACBDGF

C、EAGCFBDD、上面的都不對

17＞對二叉排序樹進行__B__遍歷，可以得到該二叉樹所有結(jié)點構成的排序序列。

A、前序B、中序C、后序D、按層次

18、由二叉樹的前序和后序遍歷序列__B_唯一地確定這棵二叉樹。

A、能B、不能

19、在一棵度為3的樹中，度為3的結(jié)點數(shù)為2個，度為2的結(jié)點數(shù)為1個，度為1的

結(jié)點數(shù)為2個，則度為0的結(jié)點數(shù)為一￡個。

A、4B、5C、6D、7

20、在一棵深度為h的完全二叉樹中，所含結(jié)點的個數(shù)不小于_D_?

A、2hB、2h+1C、2h-lD、2h-1

21、在一棵具有n個結(jié)點的二叉樹第i層上，最多具有__C_個結(jié)點。

A、21B、2i+1C、24D、2n

22、在下列情況中，可稱為二叉樹的是一B

A、每個結(jié)點至多有兩棵子樹的樹B、哈夫曼樹

C、每個結(jié)點至多有兩棵子樹的有序樹D、每個結(jié)點只有一棵右子樹

E、以上答案都不對

二、填空題

1、8層完全二叉樹至少有_.128一個結(jié)點，擁有100個結(jié)點的完全二叉樹的最大層數(shù)

為一7__?

2、樹在計算機內(nèi)的表示方式有_雙親表示法、一孩子表示法一、孩子兄弟表示法。

3、,棵有n個結(jié)點的滿二叉樹有_0__個度為1的結(jié)點，有_」n/2」一個分支（非終

端）結(jié)點和5/2」+1一個葉子，該滿二叉樹的深度為_Hogzn」+1_。

4、若一個二叉樹的葉子結(jié)點是某子樹的中序遍歷序列中的最后一個結(jié)點，則它必是孩子樹

的一前序遍歷序列中的最后?個結(jié)點。

5、一棵共有n個結(jié)點的樹,其中所有分支結(jié)點的度均為k,則該樹中的葉子結(jié)點個數(shù)為（nx

（k-1）+1）/k。

6、深度為k（設根的層數(shù)為1）的完全二叉樹至少有2kzl個結(jié)點，至多有_2k-l個

結(jié)點。

7、設只包含根結(jié)點的二叉樹高度為0,則高度為k的二叉樹最大結(jié)點數(shù)為2k+l-l,

最小結(jié)點數(shù)為k+l。

8、?棵完全二叉樹有999個結(jié)點，它的深度為10o

9、對于一棵具有n個結(jié)點的樹，該樹中所有結(jié)點的度數(shù)之和為jvlo

10、有n個結(jié)點并且其高度為n的二叉樹有2rvl個。

11、一棵具有n個結(jié)點的二叉樹，若它有n0個葉子結(jié)點，則該二叉樹上度為1的結(jié)點

nl=_n-2no+1?

12、若一棵二叉樹的葉子數(shù)為n0,則該二叉樹中左、右子樹皆非空的結(jié)點個數(shù)為nQzl。

13、設n0為哈夫曼樹的葉子結(jié)點數(shù)目，則該哈夫曼樹共有2n0-l個結(jié)點。

14、若以｛4、5、6、7、8｝作為葉子結(jié)點的權值構造哈夫曼樹，則其帶權路徑長度是69。

三、判斷題

1、完全二叉樹的某結(jié)點若無左孩子，則它必是葉結(jié)點。（對）

2、存在這樣的二叉樹，對它采用任何次序的遍歷，結(jié)果相同。（對）

3、二叉樹就是結(jié)點度為2的樹。（錯）

4、二叉樹中不存在度大于2的結(jié)點，當某個結(jié)點只有?棵子樹時無所謂左、右子樹。

錯）

5、一知二叉樹的前序遍歷序列和后序遍歷序列并不能唯一地確定這棵樹，因為不知道樹的

根結(jié)點是哪一一個。（錯）

6、在哈夫曼編碼中，當兩個字符出現(xiàn)的頻率相同時，其編碼也相同，對于這種情況應作特

殊處理。（錯）

7、中序遍歷一棵二叉排序樹的結(jié)點就可得到排好序的結(jié)點序列。（對）

8、將一棵樹轉(zhuǎn)換成二叉樹后，根結(jié)點沒有左子樹。（錯）

9、用樹的前序遍歷和中序遍歷可以導出樹的后序遍歷。（對）

10、哈夫曼樹是帶權路徑長度最短的樹，路徑上權值較大的結(jié)點離根較近。（對）

11、不使用遞歸也能實現(xiàn)二叉樹前序、中序和后序遍歷。（對

第二部分判斷題

1、順序存儲方式的優(yōu)點是存儲密度大，且插入和刪除運算效率高（錯）

2、循環(huán)隊列中無上溢現(xiàn)象（錯）

3、在線性表的順序存儲結(jié)構中，邏輯上相鄰的兩個元素在物理位置并不?定緊鄰。（錯）

4、棧和隊列都是運算受限的線性表，只允許在表的兩端進行運算。（錯）

5、數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（錯）

6、順序存儲的線性表可以隨機存儲。（對）

7、線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。（對）

8、算法和程序沒有區(qū)別，在數(shù)據(jù)結(jié)構中二者是通用的。（錯）

9、順序存儲結(jié)構方式只能用于存儲線性結(jié)構。（錯）

10、線性表的鏈式存儲結(jié)構優(yōu)于順序存儲結(jié)構。（錯）

11、線性表的鏈接存儲，表中元素的邏輯順序與物理順序定相同。（錯）

12、由于順序存儲要求連續(xù)的存儲區(qū)域，所以在存儲管理上不夠靈活。（錯）

13、循環(huán)隊列只有下溢，沒有上溢。（錯）

14、如果單鏈表帶有頭結(jié)點，則插入操作永遠不會改變頭結(jié)點指針的值。（對）

15、在循環(huán)單鏈表中，任何一個結(jié)點的指針字段值都不可能為空。（時）

16、空棧沒有棧頂指針。（錯）

17、無論是順序隊列還是鏈接隊列，插入、刪除運算的時間復雜度都是0（1）。（對）

18、在表示稀疏矩陣的三元組順序表中，各元素的排列順序與矩陣元素值的大小有關

（錯）

19、線性表可以看成是廣義表的特例，如果廣義表中的每個元素都是單元素，則廣義表便

成為線性表。（對）

20、稀疏矩陣的特點是矩陣中元素較少。（錯）

第三部分填空題

1、q[l..maxsize]為一個順序存儲的棧，變量top指示棧頂元素的位置。作進棧操作時必

須判別棧滿o如果要把棧頂元素取到x中，需執(zhí)行下列語

句：a「++toDl=x。

2、帶有表頭結(jié)點的雙鏈表L中，指針P所指結(jié)點是第一個結(jié)點的條件

是L-->next==Do

3、數(shù)據(jù)結(jié)構的三個要素是邏輯結(jié)構、存儲結(jié)構、操作。

4、單鏈表中引入頭結(jié)點的作用是為了方便操作。

5、算法的主要特性有：有窮性、確定性、可行性、輸入和輸出。

6、設循環(huán)隊列存放在向量sq.data[0…m]中，隊頭指針sq.front在循環(huán)意義下的加1操

作可用模運算表示為（sa.front+l）%（m+l）；若用犧牲個單元的辦法來區(qū)分隊

滿和隊空的條件，則隊滿條件可以表示為（sa.rear+l）%（m+l）==sa.front

8、可以僅由一個尾指針來唯一確定，即從尾指針出發(fā)能訪問到鏈表上任何一個結(jié)點的鏈表

有雙向鏈及和循環(huán)鏈及。

9、單鏈表中，指針p所指結(jié)點為最后一個結(jié)點的條件是D-->next==NULL。

10、數(shù)據(jù)的邏輯結(jié)構包括線性結(jié)構、樹型結(jié)構和圖型結(jié)構三種類型。

11、對于長度為n的線性表A[L.n],插入和刪除一個元素的時間復雜度為O（n）。

12、用二元組（D,R）來表示數(shù)據(jù)結(jié)構，那么D指數(shù)據(jù)的集合,R指這些數(shù)據(jù)

之間的關系的第合o

13、一條語句重復執(zhí)行的次數(shù)稱為頻度

14、棧的運算主要有入棧、出棧、取棧頂元素、判斷?？铡N毀棧等兒種。

15、在帶頭結(jié)點的單鏈表L中，第一個元素結(jié)點的指針為L-->next。

16、為了最快的存取某元素，數(shù)據(jù)結(jié)構宜用順序存儲結(jié)構；為了方便插入一個元素，

宜用鏈接存儲結(jié)構。

17、帶頭結(jié)點的雙鏈表為空的條件是head->next==NULL。

18、在進棧運算時，應先判別棧是否為滿；作退棧運算時，應先判別棧是否為生。

2.選擇題

⑴線性表的順序存儲結(jié)構是一種（）的存儲結(jié)構，線性表的鏈接存儲結(jié)構是一種（）的

存儲結(jié)構。

A隨機存取B順序存取（：索引存取D散列存取

【解答】A,B

【分析】參見2,2.1。

⑵線性表采用鏈接存儲時，其地址（）。

A必須是連續(xù)的B部分地址必須是連續(xù)的

C一定是不連續(xù)的D連續(xù)與否均可以

【解答】D

【分析】線性表的鏈接存儲是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素，這組存儲單元

可以連續(xù)，也可以不連續(xù)，甚至可以零散分布在內(nèi)存中任意位置。

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

A不再需要頭指針了

B從表中任一結(jié)點出發(fā)都能掃描到整個鏈表；

C已知某個結(jié)點的位置后，能夠容易找到它的直接前趨；

D在進行插入、刪除操作時，能更好地保證鏈表不斷開。

【解答】B

（4）鏈表不具有的特點是（）。

A可隨機訪問任一元素B插入、刪除不需要移動元素

C不必事先估計存儲空間D所需空間與線性表長度成正比

【解答】A

⑸若某線性表中最常用的操作是取第i個元素和找第i個元素的前趨，則采用（）存儲方

法最節(jié)省時間。

A順序表B單鏈表C雙鏈表D單循環(huán)鏈表

【解答】A

【分析】線性表中最常用的操作是取第i個元素，所以，應選擇隨機存取結(jié)構即順序表，同

時在順序表中查找第i個元素的前趨也很方便。單鏈表和單循環(huán)鏈表既不能實現(xiàn)隨機存取，

查找第i個元素的前趨也不方便，雙鏈表雖然能快速查找第i個元素的前趨，但不能實現(xiàn)隨

機存取。

（6）若鏈表中最常用的操作是在最后一個結(jié)點之后插入?個結(jié)點和刪除第一個結(jié)點，則采用

（）存儲方法最節(jié)省時間。

A單鏈表B帶頭指針的單循環(huán)鏈表C雙鏈表D帶尾指針的單循環(huán)鏈表

【解答】D

【分析】在鏈表中的最后?個結(jié)點之后插入一個結(jié)點需要知道終端結(jié)點的地址，所以，單鏈

表、帶頭指針的單循環(huán)鏈表、雙鏈表都不合適，考慮在帶尾指針的單循環(huán)鏈表中刪除第一個

結(jié)點，其時間性能是0（1），所以，答案是D。

⑺若鏈表中最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點和刪除最后一個結(jié)點，則采

用（）存儲方法最節(jié)省運算時間。

A單鏈表B循環(huán)雙鏈表C單循環(huán)鏈表D帶尾指針的單循環(huán)鏈表

【解答】B

【分析】在鏈表中的最后一個結(jié)點之后插入一個結(jié)點需要知道終端結(jié)點的地址，所以，單鏈

表、單循環(huán)鏈表都不合適，刪除最后一個結(jié)點需要知道終端結(jié)點的前驅(qū)結(jié)點的地址，所以，

帶尾指針的單循環(huán)鏈表不合適，而循環(huán)雙鏈表滿足條件。

（8）在具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然有序的時間復雜度是（）。

A0（1）B0（n）C0（n2）DO（nlog2n）

【解答】B

2.選擇題

⑴線性表的順序存儲結(jié)構是一種（）的存儲結(jié)構，線性表的鏈接存儲結(jié)構是一種（）的

存儲結(jié)構。

A隨機存取B順序存取C索引存取D散列存取

【解答】A,B

【分析】參見2.2.1。

⑵線性表采用鏈接存儲時，其地址（）。

A必須是連續(xù)的B部分地址必須是連續(xù)的

C一定是不連續(xù)的D連續(xù)與否均可以

【解答】D

【分析】線性表的鏈接存儲是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素，這組存儲單元

可以連續(xù)，也可以不連續(xù)，甚至可以零散分布在內(nèi)存中任意位置。

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

A不再需要頭指針了

B從表中任一結(jié)點出發(fā)都能掃描到整個鏈表；

C已知某個結(jié)點的位置后，能夠容易找到它的直接前趨；

D在進行插入、刪除操作時，能更好地保證鏈表不斷開。

【解答】B

（4）鏈表不具有的特點是（）。

A可隨機訪問任一元素B插入、刪除不需要移動元素

C不必事先估計存儲空間D所需空間與線性表長度成正比

【解答】A

⑸若某線性表中最常用的操作是取第i個元素和找第i個元素的前趨，則采用（）存儲方

法最節(jié)省時間。

A順序表B單鏈表C雙鏈表D單循環(huán)鏈表

【解答】A

【分析】線性表中最常用的操作是取第i個元素，所以，應選擇隨機存取結(jié)構即順序表，同

時在順序表中查找第i個元素的前趨也很方便。單鏈表和單循環(huán)鏈表既不能實現(xiàn)隨機存取，

查找第i個元素的前趨也不方便，雙鏈表雖然能快速查找第i個元素的前趨，但不能實現(xiàn)隨

機存取。

⑹若鏈表中最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點和刪除第一個結(jié)點，則采用

（）存儲方法最節(jié)省時間。

A單鏈表B帶頭指針的單循環(huán)鏈表C雙鏈表D帶尾指針的單循環(huán)鏈表

【解答】D

【分析】在鏈表中的最后一個結(jié)點之后插入一個結(jié)點需要知道終端結(jié)點的地址，所以，單鏈

表、帶頭指針的單循環(huán)鏈表、雙鏈表都不合適，考慮在帶尾指針的單循環(huán)鏈表中刪除第個

結(jié)點，其時間性能是。(1),所以，答案是D。

⑺若鏈表中最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點和刪除最后一個結(jié)點，則采

用()存儲方法最節(jié)省運算時間。

A單鏈表B循環(huán)雙鏈表C單循環(huán)鏈表D帶尾指針的單循環(huán)鏈表

【解答】B

【分析】在鏈表中的最后一個結(jié)點之后插入一個結(jié)點需要知道終端結(jié)點的地址，所以，單鏈

表、單循環(huán)鏈表都不合適，刪除最后一個結(jié)點需要知道終端結(jié)點的前驅(qū)結(jié)點的地址，所以，

帶尾指針的單循環(huán)鏈表不合適，而循環(huán)雙鏈表滿足條件。

(8)在具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然有序的時間復雜度是()。

A0(1)B0(n)C0(n2)DO(nlog2n)

【解答】B

習題六

一、選擇題

1、設無向圖的頂點個數(shù)為n,則該無向圖最多有__B一條邊。

A、n-1B、n(n-1)/2C、n(n+1)/2

D、0E、n2

2、在下列兩種求圖的最小生成樹的算法中，一_B—算法適合于求邊稀疏的網(wǎng)的最小生成

樹。

A、PrimB、Kruskal

3、下面的敘述中不正確的是__B_o

A、關鍵活動不按期完成就會影響整個工程的完成時間

B、任何一個關鍵活動提前完成，將使整個工程提前完成

C、所有關鍵活動都提前完成，則整個工程將提前完成

D、某些關鍵活動若提前完成，將使整個工程提前完成

4、采用鄰接表存儲的圖，其深度優(yōu)先遍歷類似于二叉樹的__B_

A、中序遍歷B、先序遍歷

C、后序遍歷D、按層次遍歷

5、采用鄰接表存儲的圖，其廣度優(yōu)先遍歷類似于二叉樹的—A_。

A、按層次遍歷B、中序遍歷

C、后序遍歷D、先序遍歷

6、具有n個頂點的有向圖最多有__B__條邊。

A、nB、n(n-1)C>n(n+1)D、n2

7、?個n個頂點的連通無向圖，其邊的個數(shù)至少為A。

A、n-1B、nC、n+1D、nlog2n

8、下列說法中，正確的有一工_。

A、最小生成樹也是哈夫曼樹

B、最小生成樹唯一

C、普里姆最小生成樹算法時間復雜度為。(n2)

D、克魯斯卡爾最小生成樹算法普里姆算法更適合與邊稠密的網(wǎng)。

10、判定?個有向圖是否存在回路，除了可以利用拓撲排序的方法外，還可以利用一C_o

A、求關鍵路徑的方法B、求最短路徑的Dijkstra方法

C、深度優(yōu)先遍歷算法D、廣度優(yōu)先遍歷算法

11、在一個具有n個頂點的有向圖中，若所有頂點的出度之和為s,則所有頂點的入度之

和為_Ao

A、sB、s-1C、s+lD、n

12、在一個無向圖中，若兩個頂點之間的路徑長度為k,則該路徑上的頂點數(shù)為_B

A、kB、k+1C-.k+2D、2k

13、一個有n個頂點的無向連通圖，它所包含的連通分量個數(shù)為_B

A>0B、1C>nD、n+1

14、對于一個有向圖，若一個頂點的入度為kl、出度k2,則對應鄰接表中該頂點單鏈表

中的結(jié)點數(shù)為_o

A、klB、k2C、kl-k2D、kl+k2

15、對于一個有向圖，若一個頂點的入度為kl、出度k2,則對應逆鄰接表中該頂點單鏈

表中的結(jié)點數(shù)為一A_o

A、klB、k2C、kl-k2D、kl+k2

16、為了方便地對圖狀結(jié)構的數(shù)據(jù)進行存取操作，則其中數(shù)據(jù)存儲結(jié)構宜采用_Bo

A、順序存儲B、鏈式存儲

C、索引存儲D、散列存儲

二、填空題

1、具有10個頂點的無向圖，邊的總數(shù)最多為一變o

2、在有n個頂點的有向圖中，每個頂點的度最大可達2(n-1)。

3、克魯斯卡爾算法的時間復雜度為-O(e