數(shù)據(jù)結(jié)構(gòu)考試試卷（一）

總分：100分考試時間：90分鐘

注意事項：

>考生要認(rèn)真核對條形碼上打印的姓名、座位號是否與本人準(zhǔn)考證上一致

>作答有誤需重新作答時,盡量避免使用橡皮擦除,以防卡面破損，個別錯誤可用正確的

刪除和修改符號進(jìn)行修改；不準(zhǔn)修改答題卡上的題號，否則答案無效。

>考試結(jié)束信號發(fā)出后，要立即停筆并起立。

一.單項選擇題（每小題2分，共100分）

1、最大容量為n的循環(huán)隊列，隊尾指針為rear,隊頭指針為front,則隊空的條件

是

A、rear==front

B、（rear+l）%n==front

C、rear+l==front

D、（rear-l）%n==front

【答案】A

2、帶頭結(jié)點的單鏈表L為空的條件是（）

A、L!=NULL

B、L==NULL

C、L->next==NULL

D、L->next==L

【答案】C

3、二叉樹的深度為k,則二叉樹最多有（）個結(jié)點。（3.0分）

A、2k

B、2k-l

C、2k-1

D、2k-l

【答案】C

4、設(shè)無向圖G中有n個頂點e條邊,則其對應(yīng)的鄰接表中的表頭結(jié)點和表結(jié)點

的個數(shù)分別為（）。

A、n,e

、

Bezn

C、2n,e

D、n,2e

【答案】D

5、設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點，則此類二叉樹中所包

含的結(jié)點數(shù)至少為

A、2h

B、2h-l

C、2h+l

D、h+1

【答案】B

6、插入和刪除分別在兩端端進(jìn)行的線性表是

A、循環(huán)隊列

B、棧

C、隊列

D、循環(huán)棧

【答案】C

7、棧和隊列的共同特點是

A、只允許在端點處插入和刪除元素

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

C、都是先進(jìn)先出

D、沒有共同點

【答案】A

8、對于一個具有N個頂點的無向圖,若采用鄰接矩陣表示，則該矩陣大小是()

A、N

B、(N-l)2

C、(N-1)*N

D、N*N

【答案】D

9、(4分)在一個單鏈表中，已知q指向p所指向結(jié)點的前趨結(jié)點，若在q.p所指

結(jié)點之間插入一個s所指向的新結(jié)點則執(zhí)行的操作是(A)。

A、q->next=s;s->next=p

B、p->next=s;s->next=q

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

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

【答案】A

10、在表長為n的鏈表中進(jìn)行順序查找，它的平均查找長度為()。(5.0分)

A、n/2

B.(n+l)/2

C、Vn+1

D.Ig(n+1)-1

【答案】B

11、順序隊列的初始化時，需要將front和rear分別設(shè)置為()

A、都是0

B、0和-1

C、都是-1

D、-1和0

【答案】A

12、分析以下程序段，其時間復(fù)雜度為T(n)=()i=l;While(i<=n)

i=3*i;

A、0(n)

B、0(nA2)

C、0(nA3)

D、0(1)

【答案】D

13、打印楊輝三角形時，可以使用的數(shù)據(jù)結(jié)構(gòu)是()。

A、線性表的順序存儲結(jié)構(gòu)

B、隊列

C、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)

D、棧

【答案】B

14、如果以鏈表作為棧的存儲結(jié)構(gòu),則退棧操作時

A、必須判別棧是否滿

B、對棧不作任何判別

C、必須判別棧是否為空

D、判別棧元素的類型

【答案】C

15、遞歸函數(shù)調(diào)用時，處理參數(shù)及返回地址，要用一種稱為（）的數(shù)據(jù)結(jié)

構(gòu)。

A、隊列

B、多維數(shù)組

C、棧

D、線性表

【答案】C

16、若廣義表A滿足heaD（A）=tail（A）廁A為（\

A、（）

B、（（））

C、（（）,（））

D、（（）,（）,（））

【答案】B

17、數(shù)據(jù)結(jié)構(gòu)這門學(xué)科的研究內(nèi)容下面選項最準(zhǔn)確的是

A、研究數(shù)據(jù)對象和數(shù)據(jù)之間的關(guān)系

B、研究數(shù)據(jù)對象

C、研究數(shù)據(jù)對象和數(shù)據(jù)的操作

D、研究數(shù)據(jù)對象、數(shù)據(jù)之間的關(guān)系和操作

【答案】D

18、（4分）若棧采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，則下列說法中正確的是（B）。

A、需要判斷棧滿且需要判斷?？?/p>

B、不需要判斷棧滿但需要判斷棧空

C、需要判斷棧滿但不需要判斷?？?/p>

D、不需要判斷棧滿也不需要判斷?？?/p>

【答案】B

19、一棵具有n個結(jié)點的完全二叉樹的樹高度（深度）是（A）

A、Flog2nJ+1

BxIog2n+1

Cs[Iog2nj

DxIog2n-1

【答案】A

20、在一棵深度為k的完全二叉樹中，所含結(jié)點個數(shù)至少（）

A、2Ak

B、2Ak+l

C、2Ak-l

D、2Ak-l

【答案】D

21、(3分)用鄰接表表示n個頂點e條邊的無向圖，其邊表結(jié)點的總數(shù)是(C)。

A、nxe

B、e

C、2e

D、n+e

【答案】C

22、當(dāng)待排序的整數(shù)是有序序列時，無論待排序序列排列是否有序，采用

()方法的時間復(fù)雜度都是0(n2)

A、快速排序

B、冒泡排序

C、歸并排序

D、直接選擇排序

【答案】D

23、可進(jìn)行拓?fù)渑判虻膱D只能是(C)。

A、有向圖

B、無向圖

C、有向無環(huán)圖

D、無向連通圖

【答案】C

24、設(shè)某無向圖有20個頂點很［］該無向圖的鄰接表中有()個表頭結(jié)點。

A、40

B、20

C、5

D、380

【答案】B

25、對于順序循環(huán)隊列，以下說法正確的是（）

A、無法判斷隊列是否為空

B、無法判斷隊列是否為滿

C、隊列不可能滿

D、以上說法都不對

【答案】D

26、對長度為4的順序表進(jìn)行查找,若查找第一個記錄的概率為1/24,查找第

二個記錄的概率為1/6,查找第三個記錄的概率為2/3,查找第四個記錄的概率

為1/8,則查找任意一個記錄的平均查找長度為（）。（5.0分）

A、23/8

B、20/8

C、17/8

D、13/8

【答案】A

27、在平衡二叉樹中插入一個結(jié)點后造成了不平衡,設(shè)最低不平衡結(jié)點為A,并

已知結(jié)點A的左孩子的平衡因子為0,右孩子的平衡因子為L則應(yīng)做（）型調(diào)整其

平衡。

A、LL

B、LR

C、RL

D、RR

【答案】C

28、數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)之間的相互關(guān)系,即數(shù)據(jù)的組織形式。數(shù)據(jù)結(jié)構(gòu)一般包

括()三方面內(nèi)容。(5.0分)

A、數(shù)據(jù)的邏輯結(jié)構(gòu).數(shù)據(jù)的存儲結(jié)構(gòu).數(shù)據(jù)的描述

B、數(shù)據(jù)的邏輯結(jié)構(gòu).數(shù)據(jù)的存儲結(jié)構(gòu).數(shù)據(jù)的運算

C、數(shù)據(jù)的存儲結(jié)構(gòu).數(shù)據(jù)的運算.數(shù)據(jù)的描述

D、數(shù)據(jù)的邏輯結(jié)構(gòu).數(shù)據(jù)的運算.數(shù)據(jù)的描述

【答案】B

29、設(shè)二叉樹如下則后序序列為()

A、ABDEGCFH

B、DBGEAFHC

C、DGEBHFCA

D、ABCDEFGH

【答案】C

30、下面程序段的時間復(fù)雜度是(\for(i=0;i(1分)

A、0(mA2)

B、0(nA2)

C、0(m*n)

D、O(m+n)

【答案】C

31、某哈希查找表有n條記錄，對應(yīng)的哈希函數(shù)具有m個值很」i()

A、n<m

B、n>m

C、n<=m

D、n>=m

【答案】D

32、線性表(al,a2，…,an)以鏈接方式存儲時，訪問第i位置元素的時間復(fù)雜

性為(\

A、0(i)

B、0(1)

C、0(n)

D、0(i-1)

【答案】C

33、下列4種基本邏輯結(jié)構(gòu)中，數(shù)據(jù)元素之間關(guān)系最弱的是('

A、集合

B、線性結(jié)構(gòu)

C、樹形結(jié)構(gòu)

D、圖形結(jié)構(gòu)

【答案】A

34、若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素

算法的時間復(fù)雜度(1(1分)

A、0(Iog2n)

B、0(1)

C、0(n)

D、0(nA2)

【答案】C

35、n個頂點的強(qiáng)連通圖，若該連通圖含有最少的邊，其形狀是(I

A、無回路

B、有多個回路

C、環(huán)狀

D、無法確定

【答案】C

36、隊列的刪除操作是在()。(4.0分)

A、隊首

B、隊尾

C、隊前

D、隊后

【答案】A

37、以下各階時間復(fù)雜度中,性能最優(yōu)的是()。

A、O(log2n)

B、O(n)

C、O(nA3)

D、0(2An)

【答案】A

38、下列程序段的時間復(fù)雜度為()。For(i=0;i<m;i++)for(j=0;j<t;

j++)c[i][j]=0;For(i=0;i<m;i++)for(j=0;j<t;j++)

for(k=0;k<n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];

A、O(m*n*t)

B、O(m+n+t)

C、O(m+n*t)

D、O(m*t+n)

【答案】A

39、線性表采用鏈?zhǔn)酱鎯r,其地址()

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

B、一定是不連續(xù)的

C、部分地址必須是連續(xù)的

D、連續(xù)與否均可以

【答案】D

40、關(guān)于線性表的說法不正確的是？

A、存在唯一的一個被稱為〃第一個"的數(shù)據(jù)元素(開始結(jié)點)

B、存在唯一的一個被稱為“最后一個"的數(shù)據(jù)元素(終端結(jié)點)

C、除第一個之外，集合中的每個數(shù)據(jù)元素均只有一個前驅(qū)

D、除第一個之外，集合中的每個數(shù)據(jù)元素均只有一個后繼

【答案】D

41、已知某二叉樹的后序遍歷序列是DabeC,中序遍歷序列是DebaC,它的

前序遍歷序列是（）

A、aCbeD

B、DeCaB

C、DeabC

D、CeDba

【答案】D

42、二維數(shù)組A行下標(biāo)i的范圍從1到12,列下標(biāo)j的范圍從3到10,采用

行序為主序存儲，每個數(shù)據(jù)元素占用4個存儲單元，該數(shù)組的首地址（即

的地址）為1200,則A[6]⑸的地址為（\

A、1400

B、1404

C、1372

D、1368

【答案】D

43、某班級的學(xué)生成績表中查得張三同學(xué)的各科成績記錄,其中數(shù)據(jù)結(jié)構(gòu)考了

90分，那么下面關(guān)于數(shù)據(jù)對象、數(shù)據(jù)元素、數(shù)據(jù)項描述正確的是

A、某班級的學(xué)生成績表是數(shù)據(jù)元素，90分是數(shù)據(jù)項

B、某班級的學(xué)生成績表是數(shù)據(jù)對象，90分是數(shù)據(jù)元素

C、某班級的學(xué)生成績表是數(shù)據(jù)對象，90分是數(shù)據(jù)項

D、某班級的學(xué)生成績表是數(shù)據(jù)元素,90分是數(shù)據(jù)元素

【答案】C

44、設(shè)F是由Tl、T2和T3三棵樹組成的森林，與F對應(yīng)的二叉樹為B,

Tl、T2和T3的結(jié)點數(shù)分別為Nl、N2和N3,則二叉樹B的根結(jié)點的左子樹

的結(jié)點數(shù)為（\

A、N1-1

B、N2-1

C、N2+N3

D、N1+N3

【答案】A

45、設(shè)有向無環(huán)圖G中的有向邊集合E={<1,2>,<2,3>,<3,4>,<1,

4>},則下列屬于該有向圖G的一種拓?fù)渑判蛐蛄械氖牵╔

A、1,2,3,4

B、2,3,4,1

C、1,4,2,3

D、1,2,4,3

【答案】A

46、判斷帶頭結(jié)點的單鏈表為空表的條件是（”段設(shè)頭指針為head。（3.0

分）

A、this.head.next==null;

B、this.head==null;

C、this.head.next==this.head;

D、this.head!=null;

【答案】A

47、(4分)長度為n的順序表，刪除位置i上的元素(Osisn-1),需要移動的元素個

數(shù)為(B)。

A、n-i

B、n-i-1

C、i

D、i+1

【答案】B

48、廣義表L=((a,b,c),(e,f))則L的長度和深度分別為()。

A、3,2

B、2,3

C、2,2

D、2,5

【答案】C

49、在長度為n的字符串S的第i個位置插入另外一個字符串,i的合法值應(yīng)該

是()

A、i>0

Bxi<n

C、l<i?n

D、l<i<n+l

【答案】C

50、如果以鏈表作為棧的存儲結(jié)構(gòu),則退棧操作時()。

A、必須判別棧是否滿

B、判別棧元素的類型

C、必須判別棧是否空

D、不做任何判別

【答案】C

數(shù)據(jù)結(jié)構(gòu)考試試卷（二）

總分：100分考試時間：90分鐘

注意事項：

＞考生要認(rèn)真核對條形碼上打印的姓名、座位號是否與本人準(zhǔn)考證上一致

＞作答有誤需重新作答時,盡量避免使用橡皮擦除，以防卡面破損，個別錯誤可用正確的

刪除和修改符號進(jìn)行修改；不準(zhǔn)修改答題卡上的題號，否則答案無效。

＞考試結(jié)束信號發(fā)出后，要立即停筆并起立。

一.單項選擇題（每小題2分，共100分）

1、從沒有排序序列中挑選元素，并將其一次插入已排序序列末端的方法，稱（）

A、歸并排序

B、冒泡排序

C、插入排序

D、選擇排序

【答案】D

2、以下說法正確的是（）。

A、線性結(jié)構(gòu)的基本特征是:每個結(jié)點有且僅有一個直接前驅(qū)和一個直接后繼

B、線性表的各種基本運算在順序存儲結(jié)構(gòu)上的實現(xiàn)均比在鏈?zhǔn)酱鎯Y(jié)溝上

的實現(xiàn)效率要低

C、在線性表的順序存儲結(jié)構(gòu)中插入和刪除元素時移動元素的個數(shù)與該元素

位置有關(guān)

D、順序存儲的線性表的插入和刪除操作不需要付出很大的代價，因此平均操

作只有近一半的元素需要移動

【答案】C

3、在下面的幾種排序方法中,需要內(nèi)存空間最大的方法是（A）。

A、歸并排序

B、直接選擇排序

C、快速排序

D、插入排序

【答案】A

4、向一個隊首指針為front,隊尾指針為rear的鏈隊列中插入一個s所指

結(jié)點時，其操作步驟為（）

A、s->next=front;

B、front=front->next;front->next=s;

C、s->next=rear;

D、rear=s;rear=s;s->next=rear;

【答案】C

、設(shè)棧的順序存儲空間為初始狀態(tài)為現(xiàn)經(jīng)過一系列正常

5SQ:m）top=m+lo

的入棧與退棧操作后top=20廁棧中的元素個數(shù)為（）。

A、30

B、20

C、m-19

D、M-20

【答案】C

6、以下排序方法中,（）不需要進(jìn)行關(guān)鍵字的比較。

A、快速排序

B、歸并排序

C、基數(shù)排序

D、堆排序

【答案】C

7、設(shè)有1000個無序的元素，希望用最快的速度挑出其中前10個最大的元

素，最好（）排序法。

A、起泡排序

B、選擇排序

C、堆排序

D、希爾排序

【答案】B

8、對一個滿二叉樹，它有m個樹葉，n個結(jié)點，深度為h,則（）

A、n=h+m

B、、h+m=2n

C、、m=h-l

D、、n=2h-l

【答案】D

9、具有6個頂點的無向圖至少有（）條邊才能確保是一個連通圖

A、5

B、6

C、7

D、8

【答案】A

、分析以下程序段，其時間復(fù)雜度為

10T(n)=()x=0;For(i=l;i<n;i++);

for(j=l;j<n;j++)；For(k=l;k<n;k++);x++;

A、O(n)

B、O(nA2)

C、O(nA3)

D、0(1)

【答案】A

11、數(shù)據(jù)的運算定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上，只有確定了()，才能具體實現(xiàn)這些運

算。(5.0分)

A、數(shù)據(jù)對象

B、邏輯結(jié)構(gòu)

C、存儲結(jié)構(gòu)

D、數(shù)據(jù)操作

【答案】C

12、串"abcabcef"的nextval為()

A、01112341

B、01112111

C、01123111

D、01111123

【答案】A

13、設(shè)指針變量p指向雙向鏈表中結(jié)點A,指針變量s指向插.入的結(jié)點X,則

在結(jié)點A的后面插入結(jié)點X的操作序列為(工

A、p->right=s;s->left=p;p->right->left=s;s->right=p->right;

B、s->left=p;s->right=p->right;p->right=s;p->right->left=s;

C、p->right=s;p->right->left=s;s->left=p;s->right=p->right;

D、s->left=p;s->right=p->right;p->right->left=s;p->right=s;

【答案】D

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

A、正確

B、錯誤

C、前半句正確，后半句錯誤

D、前半句錯誤，后半句正確

【答案】B

15、若INDEX(S,T)表示求T在S中的位置,則對于

S="BeiJing&Nanjing",T="jing",INDEX(S,T)=()。

A、2

B、3

C、4

D、5

【答案】C

16、設(shè)一棵完全二叉樹中有65個結(jié)點，則該完全二叉樹的深度為(\

A、8

B、7

C、6

D、5

【答案】B

17、有n個數(shù)據(jù)的二叉排序樹最大可能深度是()

A、n

B、n+1

C、Iog2(n)

D、Iog2(n+1)

【答案】A

18、設(shè)指針變量front表示鏈?zhǔn)疥犃械年狀^指針，指針變量rear表示鏈?zhǔn)疥犃?/p>

的隊尾指針，指針變量s指向?qū)⒁腙犃械慕Y(jié)點X,則入隊列的操作序列為

(X

A、front->next=s;front=s;

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

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

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

【答案】C

19、順序棧是空棧的條件是(1

A、top==0

B、top==l

C、top==-l

D、top==m

【答案】A

20、算法分析的目的是（）。（5.0分）

A、分析算法的效率以求改進(jìn)

B、找出數(shù)據(jù)結(jié)構(gòu)的合理性

C、分析算法的可讀性

D、研究算法中的輸入輸出關(guān)系

【答案】A

21、數(shù)據(jù)的基本單位（）

A、數(shù)據(jù)結(jié)構(gòu)

B、數(shù)據(jù)元素

C、數(shù)據(jù)項

D、文件

【答案】B

22、為解決計算機(jī)主機(jī)與打印機(jī)間速度不匹配問題，通常設(shè)一個打印數(shù)據(jù)緩沖

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

出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是（\

A、隊列

B、棧

C、線性表

D、有序表

【答案】A

【解析】解釋：解決緩沖區(qū)問題應(yīng)利用一種先進(jìn)先出的線性表，而隊列正是一

種先進(jìn)先出的線性表。

23、已知線性表L=(al,a2,...,ai，…,an),下列說法正確的是()。

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

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

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

D、除第一個元素和最后一個元素外，其余每個元素都有一個數(shù)，且僅有一個直

接前驅(qū)和直接后繼

【答案】D

24、用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時，通常借助()來實現(xiàn)算法。

A、棧

B、隊列

C、樹

D、圖

【答案】B

【解析】解釋：廣度優(yōu)先遍歷通常借助隊列來實現(xiàn)算法，深度優(yōu)先遍歷通常借

助棧來實現(xiàn)算法。

25、對一些特殊矩阱采用壓縮存儲的目的主要是為了()

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

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

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

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

【答案】D

26、設(shè)一組初始記錄關(guān)鍵字序列為（13,18,24,35,47,50,62,83,

90,115,134）,則利用二分法查找關(guān)鍵字90需要比較的關(guān)鍵字個數(shù)為（X

A、1

B、2

C、3

D、4

【答案】B

27、一顆二叉樹高度為h（根的高度為1）,所有結(jié)點的度為0,或者為2,則這顆二

叉樹最少（）結(jié)點。（3.0分）

A、2h

B、2h-l

C、2h+l

D、h+1

【答案】B

28、有n個十進(jìn)制整數(shù)進(jìn)行基數(shù)排序，其中最大的整數(shù)為5位很（］基數(shù)排序過程

中臨時建立的隊數(shù)個數(shù)是（）。

A、10

B、n

C、5

D、2

【答案】A

29、給定排序碼值序列為｛F,B,J,C,E,A,I,D,C,H｝,對其按字母的

字典序列的次序進(jìn)行排列，二路歸并排序的第一趟排序結(jié)果是

A、｛B,F,C,J,A,E,D,I,C,H

B、｛C,B,D,A,E,F,I,C,J,H｝

C、｛B,F,C,E,A,I,D,C,H,J｝

D、｛A,B,D,C,E,F,I,J,C,H｝

【答案】A

30、深度為4的完全:二叉樹的結(jié)點數(shù)至少為。

A、4

B、8

C、13

D、15

【答案】B

31、k=m*n;For(i=0;i<k;i++)i++;

A、O(m)

B、O(n)

C、O(m*n)

D、O(i)

【答案】C

32、若查找每個記錄的概率均等，則在具有n個記錄的連續(xù)順序文件中采用順

序查找法查找一個記錄，其平均查找長度ASL為()

A、(n-1)/2

B、n/2

C、(n+l)/2

D、n

【答案】C

33、下面程序段的時間復(fù)雜性的量級為(\For(inti=0;i<m;i++)For(int

j=O;j<n;j++)A[i][j]=i*j;

A、0(m3)

B、0(n2)

C、O(m*n)

D、O(m+n)

【答案】C

34、下面關(guān)于串的敘述中，哪個是不正確的?()。

A、串是字符的有限序列

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

C、模式匹配是串的一種重要運算

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

【答案】B

35、對線性表進(jìn)行二分查找時，要求線性表必須

A、以順序方式存儲

B、以順序方式存儲，且結(jié)點按關(guān)鍵字有序排序

C、以鏈接方式存儲

D、以鏈接方式存儲，且結(jié)點按關(guān)鍵字有序排序

【答案】B

36、有一份電文中共使用5個字符：a、b、c、d、e,它們的出現(xiàn)頻率依次

為4、7、5、2、9,對應(yīng)的哈夫曼樹（請按左子樹根結(jié)點的權(quán)小于等于右子樹

根結(jié)點的權(quán)的次序構(gòu)造）中字符a的赫夫曼編碼長度為（）

A、1

B、2

C、3

D、4

【答案】C

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

A、（n?l）/2

B、n

C、n+1

D、n/2

【答案】D

38、在二叉排序樹的（）序列是一個遞增有序序列。

A、先序遍歷

B、中序遍歷

C、后序遍歷

D、層次遍歷

【答案】B

39、森林F中有三棵樹，每棵樹上的結(jié)點個數(shù)分別為nl,N2和n3,森林

F轉(zhuǎn)換二叉樹后，根結(jié)點的右子樹上結(jié)點個數(shù)為()

A、nl

B、nl+n2

C、n2+n3

D、nl+n2+n3

【答案】C

40、下列敘述中,不符合m階B樹定義要求的是()。

A、根結(jié)點最多有m棵子樹

B、所有葉子結(jié)點都在同一層上

C、各結(jié)點內(nèi)關(guān)鍵字均升序或降序排列

D、葉子結(jié)點之間通過指針鏈接

【答案】D

41、下列線性表中，能使用二分查找的是(C)。

A、順序存儲(2,12,5,6,9389,34,25)

B、鏈?zhǔn)酱鎯?2,12,5,6,9389,34,25)

C、JII頁序存儲(2,3,5,6,9,12,25,34,89)

D、鏈?zhǔn)酱鎯?23,5.6,9,12,25,34.89)

【答案】C

42、該二叉樹對應(yīng)的森林有()棵樹。

A、1

B、2

C、3

D、4

【答案】D

43、下列關(guān)于棧敘述正確的是()。

A、棧頂元素最先能被刪除

B、棧頂元素最后才能被刪除

C、棧底元素永遠(yuǎn)不能被刪除

D、棧底元素最先被刪除

【答案】A

44、迪杰斯特拉(Djkstr)算法的功能是(A)。

A、求圖中某頂點到其他頂點的最短路徑

B、求圖中所有頂點之間的最短路徑

C、求圖的最小生成樹

D、求圖的拓?fù)渑判蛐蛄?/p>

【答案】A

45、存取任何J一個元素的時間復(fù)雜度是0(1)的數(shù)據(jù)結(jié)構(gòu)稱為()。(3.0分)

A、隨機(jī)存取結(jié)構(gòu)

B、簡單結(jié)構(gòu)

C、順序結(jié)構(gòu)

D、隨機(jī)結(jié)構(gòu)

【答案】A

46、(4分)若用一個大小為7的數(shù)組作為循環(huán)隊列的存儲結(jié)構(gòu),且當(dāng)前rear和

front的值分別為2和4,在此之前的操作是從隊列中刪除了一個元素及加入兩

個元素，請問這3個操作之前rear和front的值分別是(B)。

A、0和1

B、0和3

C、3和6

D、4和5

【答案】B

47、堆排序是一種()排序。

A、插入

B、選擇

C、交換

D、歸并

【答案】B

48、利用數(shù)組a[N]存儲一個順序棧時，用top標(biāo)識棧頂指針，已知棧未滿,

當(dāng)兀素x進(jìn)行進(jìn)棧時執(zhí)行的操作是()

A、a[—top]=x;

B、a[top--]=x;

C、a[++top]=x;

D、a[top++]=x;

【答案】C

49、對有n個數(shù)的數(shù)列進(jìn)行冒泡排序，至少應(yīng)該交換()次？

A、0

B、n/2

c、n

D、2n

【答案】A

50、已知森林F={T1,T2,T3},各棵樹Ti(i=l,2,3)中所含結(jié)點的個數(shù)分別

為7,3,5,則與F對應(yīng)的二叉樹的右子樹中的結(jié)點個數(shù)不可能是(I

A、10

B、12

C、8

D、15

【答案】D

數(shù)據(jù)結(jié)構(gòu)考試試卷（三）

總分：100分考試時間：90分鐘

注意事項：

＞考生要認(rèn)真核對條形碼上打印的姓名、座位號是否與本人準(zhǔn)考證上一致

＞作答有誤需重新作答時,盡量避免使用橡皮擦除，以防卡面破損，個別錯誤可用正確的

刪除和修改符號進(jìn)行修改；不準(zhǔn)修改答題卡上的題號，否則答案無效。

＞考試結(jié)束信號發(fā)出后，要立即停筆并起立。

一.單項選擇題（每小題2分，共100分）

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

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

A、4

B、5

C、6

D、7

【答案】D

2、下面關(guān)于求關(guān)鍵路徑的說法不正確的是（C）。

A、求關(guān)鍵路徑是以拓?fù)渑判驗榛A(chǔ)的

B、一個事件的最早開始時間同以該事件為尾的弧的活動最早開始時間相同

C、一個事件的最遲開始時間為以該事件為尾的弧的活動最遲開始時間與該

活動的持續(xù)時間的差

D、關(guān)鍵活動一定位于關(guān)鍵路徑上

【答案】C

3、(3分)下列關(guān)于無向圖廣度優(yōu)先搜索序列的敘述中，正確的是(C)。

A、廣度優(yōu)先搜索序列只有一種

B、廣度優(yōu)先搜索序列可能不存在

C、廣度優(yōu)先搜索序列可能有多種

D、廣度優(yōu)先搜索序列一定有多種

【答案】C

4、(3分)若某二叉樹的后序遍歷序列為dabec,中序遍歷序列是debac,則它的

前序遍歷序列是(B)。

A、acbed

B、cedba

C、deabc

D、decab.

【答案】B

5、下列敘述中正確的是()。

A、在循環(huán)隊列中，隊頭指針和隊尾指針的動態(tài)變化決定隊列的長度

B、在循環(huán)隊列中，隊尾指針的動態(tài)變化決定隊列的長度

C、在帶鏈的隊列中,隊頭指針與隊尾指針的動態(tài)變化決定隊列的長度

D、在帶鏈的棧中，棧頂指針的動態(tài)變化決定棧中元素的個數(shù)

【答案】A

6、在哈夫曼編碼中，根結(jié)點的權(quán)值是()。

A、根的左右兩個子結(jié)點的權(quán)值之和

B、根的左右兩個子結(jié)點的權(quán)值的平均值

C、所有結(jié)點的權(quán)值的平均值

D、所有結(jié)點的權(quán)值之和

【答案】A

7、二維數(shù)組M的元素是4個字符（每個字符占一個存儲單元）組成的串，行

下標(biāo)i的范圍從。到4,列下標(biāo)j的范圍從。到5,M按行存儲時元素M[3][5]

的起始地址與M按列存儲時元素（）的起始地址相同。

A、M[2][4]

B、M[3][4]

C、M[3][5]

D、M[4][4]

【答案】B

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

（）

A、不發(fā)生變化

B、發(fā)生變化

C、某些樹中發(fā)生變化，某些樹中不發(fā)生變化

D、沒有規(guī)律，無法確定

【答案】A

9、用鏈?zhǔn)酱鎯Φ臈?，在進(jìn)行出棧W入棧運算時（）

A、僅修改頭指針

B、僅修改尾指針

C、頭、尾指針都要修改

D、頭、尾指針可能都要修改

【答案】D

10、如果按關(guān)鍵碼值遞增的順序依次將99個關(guān)鍵碼值插入到二叉排序樹中，則

對這樣的二叉排序樹檢索時，在等概率情況下查找成功時的平均查找長度ASL為

A、50

B、48

C、45

D、47

【答案】A

11、下面()的時間復(fù)雜性最好，即執(zhí)行時間最短。

A、O(n)

B、O(logn)

C、O(nlogn)

D、O(n2)

【答案】B

12、通常從正確性、易讀性、健壯性、高效性等4個方面評價算法的質(zhì)量，以下

解釋錯誤的是()

A、正確性算法應(yīng)能正確地實現(xiàn)預(yù)定的功能

B、易讀性算法應(yīng)易于閱讀和理解，以便調(diào)試、修改和擴(kuò)充

C、健壯性當(dāng)環(huán)境發(fā)生變化時,算法能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，不會產(chǎn)生不

需要的運行結(jié)果

D、高效性即達(dá)到所需要的功能花費的時間和空間

【答案】D

13、一個無向圖有20個頂點，共有50條邊。則一個頂點的度最多是()。

A、50

B、49

C、20

D、19

【答案】D

14、若長度為n的線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，訪問其第i個元素的算法時間

復(fù)雜度為()

A、O(n)

B、O(nA2)

C、O(nA3)

D、0(log2An)

【答案】B

15、(3分)設(shè)有一組關(guān)鍵字(19.14,23.1.6.20.4275.1109),用散列函數(shù)

H(key)=key%13構(gòu)造散列表，用拉鏈法解決沖突，散列地址為1的鏈中記錄個數(shù)

為(C)。

A、1

B、2

C、3

D、4

【答案】C

16、已知指針p指向單鏈表L中的某結(jié)點，則刪除其后繼結(jié)點的語句是

A、p=p->next

B、p=null

C、p->next=null

D、p->next=p->next->next

【答案】D

17、用鏈?zhǔn)酱鎯Φ臈?，在進(jìn)棧操作之前，需要（）

A、判斷棧是否滿了

B、判斷棧是否空了

C、不需判斷

D、以上答案都不對

【答案】C

18、采用鄰接表存儲的圖的寬度優(yōu)先遍萬算法類似于二叉樹的。

A、按層遍歷

B、前序遍歷

C、后序遍歷

D、中序遍歷

【答案】A

19、以下說法正確的是（X

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ù)元素的集合。

20、一個隊列的進(jìn)隊序列為:a,b,c,d,則出隊序列是:()。

A、a,bed

、

Bd,cza,b

C、a,d,b,c

D、c,a,d,b

【答案】A

21、設(shè)有序順序表中有n個數(shù)據(jù)元素很I」利用二分查找法查找數(shù)據(jù)元素X的最

多比較次數(shù)不超過()。

A、Iog2(n)+1

BxIog2(n)-1

C、Iog2(n)

D、Iog2(n+1)

【答案】A

22、若讓元素1,2,3,4,5依次進(jìn)棧，則出棧次序不可能出現(xiàn)在()種情

況。

A、5,4,3,2,1

B、2,1,5,4,3

C、4,3,1,2,5

D、2,3,5,4,1

【答案】C

【解析】解釋：棧是后進(jìn)先出的線性表，不難發(fā)現(xiàn)C選項中元素1比元素2先

出棧，違背了棧的后送先出原則，所以不可能出現(xiàn)C選項所示的情況。

23、(2分)苦一棵二叉樹的前序遍歷序列與后序遍歷序列相同，則該二二叉樹可

能的形狀是(B)。

A、樹中沒有度為2的結(jié)點

B、樹中只有一一個根結(jié)點

C、樹中非葉結(jié)點均只有左子樹

D、樹中非葉結(jié)點均只有右子樹

【答案】B

24、序列｛3,2,4,156,8,7｝是第一趟遞增排序后的結(jié)果則采用的排序方法可能是

()o

A、快速排序

B、冒泡排序

C、堆排序

D、簡單選擇排序

【答案】A

25、循環(huán)隊列的隊空條件為()。

A、(sq.rear+l)%maxsize==(sq.front+l)%maxsize

B、(sq.rear+l)%maxsize==sq.front+l

C、sq.(rear+l)%maxsize==sq.front

D、sq.rear==sq.front

【答案】D

26、設(shè)森林F對應(yīng)的二叉樹有m個結(jié)點，二叉樹的根節(jié)點的右子樹上結(jié)點

個數(shù)為n,則森林F中第一個樹的結(jié)點個數(shù)為（）

A、m-n

B、m-n-1

C、m-n+1

D、無法確定

【答案】A

27、對于順序表的優(yōu)缺點，以下說法不正確的是（）。（3.0分）

A、無需為表示結(jié)點間的邏輯關(guān)系而增加額外的存儲空間

B、可以方便地隨機(jī)存取表中的任一結(jié)點

C、插入和刪除運算比較方便

D、容易造成一部分空間長期閑置而得不到充分利用

【答案】C

28、下面屬于整數(shù)類I的實例的是（）

A、229

B、0.229

C、229E-2

D."229"

【答案】A

29、樹的后序遍歷等價于該樹對應(yīng)二叉樹的。

A、層次遍歷

B、前序遍歷

C、中序遍歷

D、后序遍歷

【答案】C

30、設(shè)按照從上到下、從左到右的順序從1開始對完全二叉樹進(jìn)行順序編號很(J

編號為i結(jié)點的左孩子結(jié)點的編號為()。

A、2i+l

B、2i

C、i/2

D、2i-l

【答案】B

31、無向圖G=(V,E),其

中:V={a,b,c,d?f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},對該圖進(jìn)行深度優(yōu)

先遍歷彳導(dǎo)到的頂點序列正確的是(D)。

A、a,b,e,c,d,f

B、a,c,f,e,b,d

C、a,e,b,c,f,d

Dsa,e,d,tc,b

【答案】D

32、隊列的插入操作是在()o

A、隊尾

B、隊頭

C、隊列任意位置

D、隊頭元素后

【答案】A

33、(4分)順序表便于(D)。

A、插入結(jié)點

B、刪除結(jié)點

C、：按值查找結(jié)點

D、按序號查找結(jié)點

【答案】D

34、difference(ABC)表示求集合A和B的差集差若A={bqd},B={c,e},則

difference(A,B,C)運算后C=(\

A、{b,c,d,e}

B、?

C、{b,d}

D、{b,c,c,d,e}

【答案】C

35、圖中有關(guān)路徑的定義是(A)。

A、由頂點和相鄰頂點序偶構(gòu)成的邊所形成的序列

B、由不同頂點所形成的序列

C、由不同邊所形成的序列

D、上述定義都不是

【答案】A

36、對于一個具有n個結(jié)點的單鏈表，在已知的結(jié)點*p后插入一個新結(jié)點的時

間復(fù)雜度和在給定值為x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度分別為

A、O(l),O(n)

B、O(n),O(n)

C、0(1),0(1)

D、0(n),0(l)

【答案】A

37、算法的有窮性是指()。

A、算法程序的運行時間是有限的

B、算法程序所處理的數(shù)據(jù)量是有限的

C、算法程序的長度是有限的

D、算法只能被有限的用戶使用

【答案】A

38、(3分)某索引順序表共有元素395個，.平均分成5塊。若先對引表采用順序

查找,再對塊中元素進(jìn)行順序查找，則在等概率情況下，分塊查找成功的平均查找

長度是(A)。

A、43

B、79

C、198

D、200

【答案】A

39、算法的時間復(fù)雜度取決于（X

A、問題的規(guī)模

B、待處理數(shù)據(jù)的初態(tài)

C、計算機(jī)的配置

D、A和B

【答案】D

【解析】解釋：算法的時間復(fù)雜度不僅與問題的規(guī)模有關(guān)，還與問題的其他因

素有關(guān)。如某些排序的算法，其執(zhí)行時間與待排序記錄的初始狀態(tài)有關(guān)。為

此,有時會對算法有最好、最壞以及平均時間復(fù)雜度的評價。

40、鏈表適用于（）。（5.0分）

A、順序查找

B、二分查找

C、插值查找

D、隨機(jī)

【答案】A

41、下列四種排序中（）的空間復(fù)雜度最大。（2.0分）

A、快速排序

B、冒泡排序

C、希爾排序

D、堆排序

【答案】A

42、一棵二叉排序樹采用二叉鏈存儲，對于關(guān)鍵字最小的結(jié)點，它的（）。

A、左指針一定為空

B、右指針一定為空

C、左、右指針均為空

D、左、右指針均不為空

【答案】A

43、數(shù)據(jù)序列(8,9,10,4,5,6,20,1,2)只能是下列排序算法中的(C)的

兩趟排序后的結(jié)果。

A、選擇排序

B、冒泡排序

C、插入排序

D、堆排序

【答案】C

44、在順序表中，只要知道(),就可在相同時間內(nèi)求出任一結(jié)點的存儲地址。

A、基地址

B、結(jié)點大小

C、向量大小

D、基地址和結(jié)點大小

【答案】D

45、下列敘述中正確的是()。

A、對數(shù)據(jù)進(jìn)行壓縮存儲會降彳氐算法的空間復(fù)雜度

B、算法的優(yōu)化主要通過程序的編制技巧來實現(xiàn)

C、算法的復(fù)雜度與問題的規(guī)模無關(guān)

D、數(shù)值型算法只需考慮計算結(jié)果的可靠性

【答案】A

46、循環(huán)隊列的隊滿條件為()。

A、(sq.rear+l)%maxsize==(sq.front+l)%maxsize

B、(sq.rear+l)%maxsize==sq.front+l

C、sq.(rear+l)%maxsize==sq.front

D、sq.rear==sq.front

【答案】C

47、若需要時間復(fù)雜度在O(nlog2n)內(nèi),對整數(shù)數(shù)組進(jìn)行排序，且要求排序方法

是穩(wěn)定的，則可選擇的排序方法是()0

A、塊速排序

B、歸并排序

C、堆排序

D、直接插入排序

【答案】B

48、線性表的順序存儲結(jié)構(gòu)是一種()的存儲結(jié)構(gòu)，線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是

一種()存儲結(jié)構(gòu)。

A、隨機(jī)存取

B、順序存取

C、索引存取

D、散列存取

【答案】A

49、數(shù)據(jù)在計算機(jī)存儲器內(nèi)表示時，物理地址與邏輯地址不相同的，稱為()

A、存儲結(jié)構(gòu)

B、邏輯結(jié)構(gòu)

C、鏈?zhǔn)酱鎯Y(jié)構(gòu)

D、順序存儲結(jié)構(gòu)

【答案】C

50、設(shè)有序順序表中有n個數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最

多比較次數(shù)不超過(\

A、Iog2n+1

B、Iog2n-1

C、Iog2n

DxIog2(n+1)

【答案】D

數(shù)據(jù)結(jié)構(gòu)考試試卷（四）

總分：100分考試時間：90分鐘

注意事項：

＞考生要認(rèn)真核對條形碼上打印的姓名、座位號是否與本人準(zhǔn)考證上一致

＞作答有誤需重新作答時,盡量避免使用橡皮擦除,以防卡面破損，個別錯誤可用正確的

刪除和修改符號進(jìn)行修改；不準(zhǔn)修改答題卡上的題號，否則答案無效。

＞考試結(jié)束信號發(fā)出后，要立即停筆并起立。

一.單項選擇題（每小題2分，共100分）

L下面幾種排序方法中，要求內(nèi)存最大的是（）c

A、快速排序

B、歸并排序

C、堆排序

D、冒泡排序

【答案】B

2、設(shè)順序表的長度為16,對該表進(jìn)行簡單插入排序。在最壞情況下需要的比較

次數(shù)為（）

A、15

B、60

C、30

D、120

【答案】D

3、設(shè)棧S和隊列Q的初始狀態(tài)為空，元素el、e2、e3、e4、e5和e6依次

進(jìn)入棧s,一個元素出棧后即進(jìn)入Q,若6個元素出隊的序列是e2、e4、

e3、e6、e5和el,則棧S的容量至少應(yīng)該是（\

A、2

B、3

C、4

D、6

【答案】B

【解析】解釋：元素出隊的序列是e2、e4、e3、e6、e5和el,可知元素入

隊的序列是e2、e4、e3、e6、e5和el,即元素出棧的序列也是e2、e4、

e3、e6、e5和el,而元素el、e2、e3、e4、e5和e6依次進(jìn)入棧,易知棧

S中最多同時存在3個元素，故棧S的容量至少為30

4、將一棵有100個結(jié)點的完全二叉樹從根這一層開始，每一層上從左到右依次

對結(jié)點進(jìn)行編號，根結(jié)點的編號為L則編號為49的結(jié)點的左孩子編號為（）。

A、98

B、99

C、50

D、48

【答案】A

5、（4分）在單循環(huán)鏈表中,p指向表中任-結(jié)點，判斷表不是訪問結(jié)束的條件是

（B）o

A、p!=NULL

B、p!=head

C、p->next!=head

D、p->next!=NULL

【答案】B

6、(3分)在具有n個頂點的無向完全圖G中邊的總數(shù)為(B)。

A、n+1

B、n(-l)/2

C、n(n+l)

D、n-1

【答案】B

7、在具有2n個結(jié)點的完全二叉樹中，葉子結(jié)點個數(shù)為()。

A、n

B、n+1

C、n-1

D、n/2

【答案】A

8、下列關(guān)于算法輸出的敘述中，正確的是()。

A、算法一定沒有輸出

B、算法可以沒有輸出

C、算法至少有一個輸出

D、算法必須有多個

【答案】C

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

A、n-i

B、n-i+1

C、n-i-1

D、i+1

【答案】A

10、單鏈表不具備的特點是()?(3.0分)

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

B、鏈表長度可動態(tài)增長

C、所需空間與線性長度成正比

D、可隨機(jī)訪問任一個元素

【答案】D

11、執(zhí)行下面程序段時，S語句的執(zhí)行次數(shù)為()For(inti=l;i<n-

l;i++)For(intj=i+l;j<=n;j++)S;

A、n(n-l)/2

B、n2/2

C、n(n-l)/2

D、n

【答案】A

12、鏈表不具有的特點是()。

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

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

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

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

【答案】A

13、從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較，將其放入

已排序序列的正確位置上的方法，這種排序方法稱為（\

A、歸并排序

B、冒泡排序

C、插入排序

D、選擇排序

【答案】C

14、一^棧的輸入序列為123，…,"其輸出序列為pLp2,p3,...,pn,若pn是n,

貝！Jpi是（）。

A、不確定

B、n-i+1

C、i

D、n-i

【答案】D

15、若已知一個棧的入棧序列是123,..,n,其輸出序列為pl,p2,p3，…,pn,若pl

=n,則pn為（）。

A、1

B、n

C、n/2

D、n-1

【答案】A

16、設(shè)有100個元素，用折半查找法進(jìn)行查找時，最大、最小匕喉次數(shù)分別時

()

A、7,1

B、6,1

C、5,1

D、8,1第九章排序

【答案】A

17、數(shù)據(jù)元素之間存在一對多的關(guān)系，這種數(shù)據(jù)間的結(jié)構(gòu)屬于()

A、集合

B、線性結(jié)構(gòu)

C、樹型結(jié)構(gòu)

D、圖型結(jié)構(gòu)

【答案】C

18、假設(shè)以行序為主序存儲二維數(shù)組A=array。..100,1...100],設(shè)每個數(shù)組元素

占個存儲單元，基地址為則

210,LOC[5Z5]=

A、818

B、808

C、1010

D、1020

【答案】A

19、樹最適合用來表示。

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

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

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

D、元素之間無聯(lián)系的數(shù)據(jù)，是平衡二叉樹。

【答案】C

20、隊和棧的主要區(qū)別是(I(1分)

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

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

C、所包含的運算個數(shù)不同

D、限定插入和刪除的位置不同

【答案】D

21、下面程序段的時間復(fù)雜度為()。i=l；while(i<=n)

A、O(n)

B、O(3n)

C、O(log3n)

D、O(n3)

【答案】C

22、某算法的空間復(fù)雜度為OQ),表明執(zhí)行該算法時()

A、不需要儲存空間

B、需要的臨時存儲空間為常量

C、需要的存儲空間恰好為1

D、需要的臨時存儲空間為1

【答案】B

23、設(shè)有一個遞歸算法如下:Intfun(intn){if(n<=0)return0;else

n+fun(n-l);}則計算fun(n)(n>0)需要調(diào)用該函數(shù)的次數(shù)為()。

A、n+1

B、n-1

C、n

D、n+2

【答案】A

24、線性表是一個有限序列，組成線性表的基本單位是(B)。

A、數(shù)據(jù)項

B、數(shù)據(jù)元素

C、數(shù)據(jù)域

D、擔(dān)

【答案】B

25、棧和隊列的共同點是(I

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

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

C、只允許在端點處插入和刪除元素

D、沒有共同點

【答案】C

【解析】解釋：棧只允許在棧頂處進(jìn)行插入和刪除元素，隊列只允許在隊尾插

入元素和在隊頭刪除元素。

26、(6分)計算機(jī)算法指的是解決問題的有限運算序列,它必具備輸入輸出和()等

五個特性。

A、可行性、可移植性和可擴(kuò)充性

B、可行^性、確定性和有窮性

C、確定性、有窮性和穩(wěn)定性

D、易讀性、穩(wěn)定性和安全性

【答案】B

、設(shè)循環(huán)隊列的存儲空間為初始狀態(tài)為現(xiàn)經(jīng)過

27QQ:35)front=rear=35e

一系列入隊與退隊運算后fronts15,rear=15則循環(huán)隊列中的元素個數(shù)為()。

A、15

B、16

C、20

D、0或35

【答案】D

28、一棵具有1028個結(jié)點的二叉樹的深度h為()。

A、11

B、10

C、11-1028

D、10~1027

【答案】C

29、快速排序在下列哪種情況下最易發(fā)揮其長處()。

A、被排序的數(shù)據(jù)中含有多個相同排序碼

B、被排序的數(shù)據(jù)已基本有序

C、被排序的數(shù)據(jù)隨機(jī)分布

D、被排序的數(shù)據(jù)中最大值和最小值相差懸殊

【答案】C

30、后綴表達(dá)式"45*32+-"的值為（）

A、21

B、17

C、15

D、5

【答案】C

【解析】（4、5入棧,遇到*，取出4*5=20;20、3、2入棧，遇到+,取出

3+2=5;5入棧，遇到-,取出20-5=15）第2

31、由權(quán)值分別是8,7,2,5的葉子結(jié)點生成一棵赫夫曼樹,它的帶權(quán)路徑

長度為（）

A、23

B、37

C、43

D、46

【答案】C

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

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

B、哈夫曼樹

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

D、每個結(jié)點只有一棵右子樹

【答案】B

33、在一個圖中，所有頂點的度數(shù)之后等于所有邊數(shù)的（）倍。（4.0分）

A、1/2

B、1

C、2

D、4

【答案】A

34、設(shè)一組權(quán)值集合W=（15,3,14,2,6,9,16,17）,要求根據(jù)這些權(quán)

值集合構(gòu)造一棵哈夫曼樹，則這棵哈夫曼樹的帶權(quán)路徑長度為（L

A、129

B、219

C、189

D、229

【答案】D

35、算法具有五個重要特性不包括

A、有窮性

B、確定性

C、可行性

D、易讀性

【答案】D

36、在完全二叉樹中，若一個結(jié)點是葉結(jié)點，則它沒

A、左子結(jié)點

B、右子結(jié)點

C、左子結(jié)點和右子結(jié)點

D、左子結(jié)點，右子結(jié)點和兄弟結(jié)點

【答案】C

37、設(shè)廣義表L=((a,b,c)),則L的長度和深度分別為(I

A、1和1

B、1和3

C、1和2

D、2和3

【答案】C

【解析】解釋：廣義表的深度是指廣義表中展開后所含括號的層數(shù)，廣義表的

長度是指廣義表中所含元素的個數(shù)。根據(jù)定義易知L的長度為1,深度為20

38、由4個結(jié)點可以構(gòu)造出多少種不同的二叉樹？

A、9

B、14

C、16

D、27

【答案】B

39、某算法的時間復(fù)雜度是0(門人2),表明該算法的

A、執(zhí)行時間與n，、2成正比

B、問題規(guī)模是「八2

C、執(zhí)行時間等于”2

D、問題規(guī)模與n^2成正比

【答案】A

40、（）二叉排序樹可以得到一個從小到大的有序序列。

A、先序遍歷

B、中序遍歷

C、后序遍歷

D、層次遍歷

【答案】B

41、在單鏈表L中才旨針p所指結(jié)點有后繼結(jié)點的條件是（）。

A、p=p.next

B、p.next!=null

C、p.next=null

D、p.next=p.next.next

【答案】B

42、雙向鏈表中有兩個指針域,llink和rlink分別指向前趨及后繼，設(shè)p指

向鏈表中的一個結(jié)點，現(xiàn)要求刪去p所指結(jié)點，則正確的刪除是（）（鏈中

結(jié)點數(shù)大于2,p不是第一個結(jié)點\

A、p->llink->rlink=p->llink;

B、

free(p);P->llink->rlink=p->rlink;p->llink->rlink=p->llink;Free(p);p->llink

->rlink=p->rlink;

C、p->llink->rlink=p->llink;

D、以上A,B,C都不對。free(p);P->llink->rlink=p->rlink;

【答案】D

43、索引順序表的特點是順序表中的數(shù)據(jù)()。

A、有序

B、無序

C、塊間有序

D、散列

【答案】C

44、(4分)棧結(jié)構(gòu)通常采用的兩種存儲結(jié)構(gòu)是(A)。

A、順序存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)

B、散鏈方式^口索引方式

C、鏈表存儲結(jié)構(gòu)和數(shù)組

D、線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)

【答案】A

45、設(shè)在一棵度數(shù)為3的樹中，度數(shù)為3的結(jié)點數(shù)有2個，度數(shù)為2的結(jié)點數(shù)

有1個，度數(shù)為1