華東理工大學(xué)數(shù)據(jù)結(jié)構(gòu)(新)期末考試復(fù)習(xí)題及參考答案_第1頁
華東理工大學(xué)數(shù)據(jù)結(jié)構(gòu)(新)期末考試復(fù)習(xí)題及參考答案_第2頁
華東理工大學(xué)數(shù)據(jù)結(jié)構(gòu)(新)期末考試復(fù)習(xí)題及參考答案_第3頁
華東理工大學(xué)數(shù)據(jù)結(jié)構(gòu)(新)期末考試復(fù)習(xí)題及參考答案_第4頁
華東理工大學(xué)數(shù)據(jù)結(jié)構(gòu)(新)期末考試復(fù)習(xí)題及參考答案_第5頁
已閱讀5頁,還剩169頁未讀 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

一、計算(每題參考分值5分)

1、已知一個網(wǎng)的鄰接矩陣A如下,試畫出該網(wǎng)。

0015co22QOco

coco118QO00

co3cococo28

22coco8QOco

00coQOcoCO00

15cococococo

1311

123

正確答案:

2、以{24Z68,2Z55,23,U,10,19,20,79,84},構(gòu)造hash表并求平均查找

長度。hash表長度為17,hash(key)=key%17o

用線性探測法解決沖突。

正確答案:

02578910111213141516

68119205523271110791484

ASL=(l*10+3*2)/12=16/12

3、已知二叉樹先序遍歷序列是:abcdefg;中序遍歷

序列是:生司%寫出后序遍歷序列。

正確答案:

后序遍歷序列:cdbgfea

4、設(shè)通信用8個字符abcdefgh,各字符使用的相對頻率分別

為25,36,2,5,8,10,14,50,構(gòu)造哈夫曼樹,設(shè)計哈夫曼編碼,求該樹的帶樹路

徑長度WPLO

正確答案:

OTOW

IOOI:9

IOOOI:P

OOOOI:)

io:q

oo:e

g:1011

h:ll

WPL=(25+36+50)*2+(8+10+14)*4+(2+5)*5

=385

5、對{49,38,65,97,76,13,27,49)進行直接插入排序,寫出每一趟排序

過程

正確答案:

第1趟i=2(3849)659776132749

第2趟(384965)9776132749

第3趟(38496597)76132749

第4趟(3849657697)132749

第5趟i=6(133849657697)2749

第6趟i=7(13273849657697)49

第7趟(1327384949657697

6、用kruskal方法求下圖的最小生成樹

正確答案:

?

?

o

7、對對{278,109,63,930,589r184,505,269,8r83)用基數(shù)排序方法進行排

序,寫出每一趟排序過程

正確答案:

第一趟排序后(個位有序):

930,063,083,184,505,278,008,109,589,269

第二趟排序后(在個位有序的基礎(chǔ)上使拾位有序):

505,008,109,930,063,269,278,083,184,589

第三趟排序后(在拾位有序的基礎(chǔ)上使百位有序):

008,063,083,109,184,269,278,505,589,930

8、以{45,53,12,37,24,100,3,61,90,78}

構(gòu)造二叉排序樹。

正確答案:

二、論述(每題參考分值5分)

9、設(shè)計算法求二叉樹的高度

正確答案:

intdepth(BTreeT)

{intl,r;

if(T==NULL)

return0;

else{

1=depth(T->lchild);

r=depth(T->rchild);

return(l>r)?(l+l):(r+l)

)

)

10、已知線性表中的元素按值遞增排列,并以單鏈表作存儲結(jié)構(gòu)。寫一高效算

法,刪除表中所有值大于min且小于max的元翦若表中存在這樣的元素X

正確答案:

voiddel_l(node*h,intmin,intmax){

//h:帶頭結(jié)點的單鏈表的頭指針

q=h;p=h->next;〃初值

while(p!=NULL&&p->data<=min)

{q=p;p=p->next;}

//p指向其值〉min的結(jié)點,q是p的前趨

while(p!=NULL&&p->data<max)

{u=p;p=p->next;deleteu;}

//刪除所有的其值〉min并且vmax的結(jié)點p(u)

q->next=p;

}//del,l

三、單選(每題參考分值2.5分)

11、深度為k的完全二叉樹中最少有()個結(jié)點。

A.

2匕1-1

2匕1

c.

21+1

D.

2k-l

答案:【B】

12、設(shè)輸入序列1、2、3、…、n經(jīng)過棧作用后,輸出序列中的第一個元素是n,則輸出

序列中的第i個輸出元素是()。

A.

n-i

B.

n-1-i

C.

n+l-i

D.

不能確定

答案:【O

13、設(shè)散列表中有m個存儲單元,散列函數(shù)H(key)=key%p,貝Up最好選擇(

A.

小于等于m的最大奇數(shù)

B.

小于等于m的最大素數(shù)

C.

小于等于m的最大偶數(shù)

D.

小于等于m的最大合數(shù)

答案:【B】

14、某二叉樹的后序遍歷序列為DABEC、中序遍歷序列為DEBAC,則前序遍歷為

A.

ACBED

B.

DECAB

C.

DEABC

D.

CEDBA

答案:【D】

15、下列排序算法中時間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響,恒為0(己)的是

A.

堆排序

B.

冒泡排序

C.

直接叫排序

D.

快速排序

答案:【C

16、利用直接插入排序法的思想建立一個有序線性表的時間復(fù)雜度為()。

A.

O(n)

B.

O(nlog2n)

C.

0(n2)

D.

O(log2n)

答案:【C】

17、圖G的某一最小生成樹的代價一定小于其他生成樹的代價

A.

一定是

B.

肯定不是

C.

不一定是

D.

都不對

答案:【O

18、設(shè)按照從上到下、從左到右的順序從1開始對完全二叉樹進行順序編號,則編號為

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

A.

2i+l

B.

2i

C.

i/2

D.

2i-l

答案:【B】

19、兩個字符串相等的充要條件是()。

A.

兩個字符串的長度相等

B.

兩個字符串中對應(yīng)位置上的字符相等

C.

同時具備(A)和(B)兩個條件

D.

以上答案都不對

答案:

20、設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏5臈m?,則刪除棧頂元素的操作序列為()c

A.

top=top+l;

B.

top=top-l;

C.

top->next=top;

D.

top=top->next;

答案:【D】

21、設(shè)某無向圖有n個頂點,則該無向圖的鄰接表中有()個表頭結(jié)點。

A.

2n

B.

n

C.

n/2

D.

n(n-l)

答案:【B】

22、JII頁序查找不論在J順序線性表中還是在鏈?zhǔn)骄€性表中的時間復(fù)雜度為(

A.

O(n)

B.

0(帝)

C.

0(nV2)

D.

O(log2n)

答案:【A】

23、設(shè)III頁序線性表中有n個數(shù)據(jù)元素,則刪除表中第i個元素需要移動()個元素。

A.

n-i

B.

n+l-i

C.

n-l-i

D.

i

答案:【A】

24、算法必須具備輸入、輸出和

A.

計算方法

B.

排序方法

C.

解決問題的有限運算步驟

D.

程序設(shè)計方法

答案:【C

25、()是線性表。

A.

(123,...)

B.

{abode}

C.

(135,7)

D.

{'A';C}

答案:【。

26、下列各種排序算法中平均時間復(fù)雜度為0(M)是()。

A.

快速排序

B.

堆排序

C.

歸并排序

D.

冒泡排序

答案:【D】

27、在二叉排序樹中插入一個關(guān)鍵字值的平均時間復(fù)雜度為()。

A.

0(n)

B.

O(log2n)

C.

O(nlog2n)

D.

0(M)

答案:【B】

28、設(shè)某哈夫昌樹中有199個結(jié)點,則該哈夫晝樹中有()個葉子結(jié)點C

A.

99

B.

100

C.

101

D.

102

答案:【B】

29、設(shè)二叉排序樹上有n個結(jié)點廁在二叉排序樹上查找結(jié)點的平均時間復(fù)雜度為()。

A.

O(n)

B.

O(M)

C.

O(nlog2n)

D.

O(log2n)

答案:【D】

30、設(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;

答案:【A】

31、設(shè)用鄰接矩陣A表示有向圖G的存儲結(jié)構(gòu),則有向圖G中頂點i的入度為()。

A.

第i行非0元素的個數(shù)之和

B.

第i列非0元素的個數(shù)之和

C.

第i彳亍0元素的個數(shù)之和

D.

第i列0元素的個數(shù)之和

答案:【B】

32、設(shè)輸入序列為L2.3、4、5、6,則通i寸棧的作用后可以得到的輸出序列為(]

A.

5,3,4,6,1,2

B.

3,256,4,1

C.

3,1,254,6

D.

1,5,4,6,2,3

答案:【B】

33、設(shè)一條單鏈表的頭指針變量為head且該鏈表沒有頭結(jié)點,則其判空條件是()。

A.

head==O

B.

head->next==O

C.

head->next==head

D.

head!=O

答案:【A】

34、設(shè)順序表的長度為n,則JI質(zhì)序杳找的平均比較次數(shù)為()。

A.

n

B.

n/2

C.

(n+l)/2

D.

(n-l)/2

答案:【C】

35、設(shè)某強連通圖中有n個頂點,則該強連通圖中至少有()條邊。

A.

n(n-l)

B.

n+1

C.

n

D.

n(n+l)

答案:【C】

36、設(shè)某散列表的長度為100,散列函數(shù)H(k)=k%P,則P通常情況下最好選擇(

A.

99

B.

97

C.

91

D.

93

答案:【B】

37、若線性表最常用的操作是存取第i個元素的值,則采用______存儲方式節(jié)省時間。

A.

單鏈表

B.

雙鏈表

C.

單循環(huán)鏈表

D.

順序表

答案:【D】

38、設(shè)一棵三叉樹中有2個度數(shù)為1的結(jié)點,2個度數(shù)為2的結(jié)點,2個度數(shù)為3的結(jié)

點,則該三叉樹中有()個度數(shù)為0的結(jié)點。

A.

5

B.

6

C.

7

D.

8

答案:

39、設(shè)有n個關(guān)鍵字具有相同的Hash函數(shù)值,則用線性探測法把這n個關(guān)鍵字映射到

HASH表中需要做()次線性探測。

A.

n2

B.

n(n+l)

C.

n(n+l)/2

D.

n(n-l)/2

答案:【D】

40、對n個記錄的文件進行快速排序,所需要的輔助存儲空間大致為()

A.

0(1)

B.

O(n)

c.

O(log2n)

D.

O(n2)

答案:【O

41、設(shè)某無向圖中有n個頂點e條邊,則建立該圖鄰接表的時間復(fù)雜度為()。

A.

O(n+e)

B.

0(M)

C.

O(ne)

D.

0(n3)

答案:【A】

42、設(shè)一棵m叉樹中度數(shù)為0的結(jié)點數(shù)為No,度數(shù)為1的結(jié)點數(shù)為Ni..........度數(shù)為

m的結(jié)點數(shù)為Nm,則No=()。

A.

N1+N2+.....+Nm

B.

I+N2+2N3+3N4+……+(m-l)Nm

C.

N2+2N3+3N4+......+(m-l)Nm

D.

2N+3N2++(m+l)Nm

答案:【B】

43、二叉樹的第k層的結(jié)點數(shù)最多為()。

A.

2k-l

B.

2K+1

C.

2K-1

D.

2k-l

答案:【D】

44、設(shè)指針q指向單躡中結(jié)點A,指針p指向單鏈表中結(jié)點A的后繼結(jié)點B,指針s

指向被插入的結(jié)點X,則在結(jié)點A和結(jié)點B插入結(jié)點X的操作序列為()。

A.

s->next=p->next;p->next=-s

B.

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

C.

p->next=s->next;s->next=p

D.

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

答案:【B】

45、設(shè)輸入序列是1、2、3.............n,經(jīng)過棧的作用后輸出序列的第一個元素是n,則

輸出序列中第i個輸出元素是()。

A.

n-i

B.

n-1-i

C.

n+1-i

D.

不能確定

答案:【。

46、樹最適合用來表示i)。

A.

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

B.

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

C.

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

D.

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

答案:【O

47、設(shè)一個有序的單鏈表中有n個結(jié)點,現(xiàn)要求插入一個新結(jié)點后使得單鏈表仍然保持

有序,則該操作的時間復(fù)雜度為()。

A.

O(log2n)

B.

0(1)

C.

0(n2)

D.

0(n)

答案:【D】

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

A.

8

B.

7

C.

6

D.

5

答案:【B】

49、設(shè)二叉排序樹中有n個結(jié)點,則在二叉排序樹的平均杳找長度為().

A.

0(1)

B.

O(log2n)

C.

O(nlog2n)

D.

0(n2)

答案:【B】

50、設(shè)有5000個待排序的記錄關(guān)鍵字,如果需要用最快的方法選出其中最小的10個記

錄關(guān)鍵字,則用下列()方法可以達到此目的。

A.

快速排序

B.

堆排序

C.

歸并排序

D.

插入排序

答案:【B】

一、簡答(每題參考分值5分)

1、二維數(shù)組inta[10][10],以行優(yōu)先存儲,第1個元素的首址是100,每個

元素的長度為4,求A[4][5]的存儲首址。

正確答案:

A[4H5]的存儲首址

=100+(4*10+5)*4=100+45*2

=280

二、辨析(每題參考分值5分)

2、閱讀下列算法,并回答問題。

floatwhat(floatx,intn){

floaty=x;

while(n>l)

{y=y*x;n=n^Cl;}

returny;}

問題:(1)該算法的功能是計算

(2)該算法的時間復(fù)雜度是_______

正確答案:

xn,0(n)

三、計算(每題參考分值5分)

3、對對{278,109,63,930,589,184,505,269,8,83}用基數(shù)排序方法進行排

序,寫出每一趟排序過程

正確答案:

第一趟排序后(個位有序):

930,063,083,184,505,278,008,109,589,269

第二趟排序后(在個位有序的基礎(chǔ)上使拾位有序):

505,008,109,930,063,269,278,083,184,589

第三趟排序后(在拾位有序的基礎(chǔ)上使百位有序):

008r063,083,109,184,269,278,505,589,930

4、對給定的單鏈表L,下面算法完成刪除L中值為x的結(jié)點的直接前驅(qū)結(jié)點。請?zhí)羁铡?/p>

voidDeleteX(LinkListL,DataTypex)

{/*L是帶頭結(jié)點的單鏈表*/

ListNode*p,*q;

q=L;p=L->next;

while(p&&p->data!=x)

{q=p;

P=_________;}

if()

Error("xisthefirstnode,ithasnopriornode");

q->data=x;

q->next=p->next;

free();

)

正確答案:

解:

(l)p->next(2分)

(2)p==NULL(2分)

⑶P(1分)

5、以{45,53,12,37,24,100,3,61,90,78}

構(gòu)造二叉排序樹。

正確答案:

6、設(shè)無向圖G(如右圖所示),給出該圖的最小生成樹上邊的集合并計算最小生成樹各

邊上的權(quán)值之和。

正確答案:

解:E={(1,5),(5,2),(5,3),(3,4)},W=1O

7、已知二叉樹先序遍歷序列是:abcdefg;中序遍歷

序列是:皿a曲;寫出后序遍歷序列。

正確答案:

后序遍歷序列:cdbgfea

8、設(shè)計將所有奇數(shù)移到所有偶數(shù)之前的算法。

正確答案:

解:設(shè)計將所有奇數(shù)移到所有偶數(shù)之前的算法。

voidquickpass(intr[],ints,intt)

inti=sj=t/x=r[s];

while(i<j)

(

while(i<j&&r[j]%2==0)j=j-l;if(i<j){r[i]=r[j];i=i+l;}

while(i<j&&r[i]%2==l)i=i+l;if(i<j){r[j]=r[i];j=j-l;}

)

r[i]=x;

)

9、voidABC(BTNode*BT)

(

ifBT(

ABC(BT->left);

ABC(BT->right);

cout<<BT->data<<'

)

)

該算法的功能是:

正確答案:

解:遞歸地后序遍歷鏈?zhǔn)酱鎯Φ亩鏄洹?/p>

10、在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉排序樹。

正確答案:

解:在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉排序樹。

#definen10

typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;

voidbstinsert(bitree*&btjntkey)

(

if(bt==O){bt=(bitree*)malloc(sizeof(bitree));

bt->key=key;bt->lchild=bt->rchild=O;}

elseif(bt->key>key)bstinsert(bt->lchild,key);else

bstinsert(bt->rchild,key);

}

voidcreatebsttree(bitree*&bt)

inti;

for(i=l;i<=n;i++)bstinsertfbt/andomflOO));

)

四、單選(每題參考分值2.5分)

11、深度為k的完全二叉樹中最少有()個結(jié)點。

A.

2k-i-l

B.

2匕1

C.

2匕1+1

D.

2k-l

答案:【B】

12、設(shè)輸入序列1、2、3、…、n經(jīng)過棧作用后,輸出序列中的第一個元素是n,則輸出

序列中的第i個輸出元素是()。

A.

n-i

B.

n-1-i

C.

n+l-i

D.

不能確定

答案:【O

13、設(shè)散列表中有m個存儲單元,散列函數(shù)H(key)二key%p,則p最好選擇()。

A.

小于等于m的最大奇數(shù)

B.

小于等于m的最大素數(shù)

C.

小于等于m的最大偶數(shù)

D.

小于等于m的最大合數(shù)

答案:【B】

14、某二叉樹的后序遍歷序列為DABEC、中序遍歷序列為DEBAC,則前序遍歷為

A.

ACBED

B.

DECAB

C.

DEABC

D.

CEDBA

答案:【D】

15、下列排序算法中時間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響,恒為0(己)的是

A.

堆排序

B.

冒泡排序

C.

直接選擇排序

D.

快速排序

答案:【。

16、利用直接插入排序法的思想建立一個有序線性表的時間復(fù)雜度為()。

A.

O(n)

B.

O(nlog2n)

C.

0(n2)

D.

O(log2n)

答案:【C】

17、圖G的某一最小生成樹的代價一定小于其他生成樹的代價

A.

一定是

B.

肯定不是

C.

不一定是

D.

都不對

答案:【。

18、設(shè)按照從上到下、從左到右的順序從1開始對完全二叉樹講行順序編號,則編號為

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

A.

2i+l

B.

2i

c.

i/2

D.

2i-l

答案:【B】

19、兩個字符串相等的充要條件是()。

A.

兩個字符串的長度相等

B.

兩個字符串中對應(yīng)位置上的字符相等

C.

同時具備(A)和(B)兩個條件

D.

以上答案都不對

答案:【C】

20、設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏5臈m?,則刪除棧頂元素的操作序列為()。

A.

top=top+l;

B.

top=top-l;

C.

top->next=top;

D.

top=top->next;

答案:【D】

21、設(shè)某無向圖有n個頂點,則該無向圖的鄰接表中有()個表頭結(jié)點。

A.

2n

B.

n

C.

n/2

D.

n(n-l)

答案:【B】

22、Jll頁序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時間復(fù)雜度為()。

A.

0(n)

B.

0(n2)

c.

0(nV2)

D.

O(log2n)

答案:【A】

23、設(shè)III頁序線性表中有n個數(shù)據(jù)元素,則刪除表中第i個元素需要移動()個元素。

A.

n-i

B.

n+1-i

C.

n-1-i

D.

答案:【A】

24、算法必須具備輸入、輸出和

A.

計算方法

B.

排序方法

C.

解決問題的有限運算步驟

D.

程序設(shè)計方法

答案:

25、()是線性表。

A.

(1,2,3,...)

B.

{a,b,c,d,e}

C.

(L3,5,7)

D.

{4:B';C'}

答案:【C】

26、下列各種排序算法中平均時間復(fù)雜度為0(d)是()。

A.

快速排序

B.

堆排序

c.

歸并排序

D.

冒泡排序

答案:【D】

27、設(shè)二叉排序樹上有n個結(jié)點廁在二叉排序樹上查找結(jié)點的平均時間復(fù)雜度為()。

A.

0(n)

B.

0(M)

C.

O(nlog2n)

D.

0(10020)

答案:【D】

28、在二叉排序樹中插入一個關(guān)鍵字值的平均時間復(fù)雜度為()。

A.

0(n)

B.

O(log2n)

C.

O(nlog2n)

D.

0(M)

答案:【B】

29、設(shè)某哈夫曼樹中有199個結(jié)點,則該哈夫曼樹中有()個葉子結(jié)點。

A.

99

B.

100

C.

101

D.

102

答案:【B】

30、設(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;

答案:【A】

31、設(shè)用鄰接矩陣A表示有向圖G的存儲結(jié)構(gòu),則有向圖G中頂點i的入度為()。

A.

第i行非0元素的個數(shù)之和

B.

第i歹IJ非0元素的個數(shù)之和

C.

第i行0元素的個數(shù)之和

D.

第i列0元素的個數(shù)之和

答案:【B】

32、設(shè)輸入序列為1、2、3、4、5、6,則通過棧的作用后可以得到的輸出序列為()。

A.

5,3,4,6,1,2

B.

3,256,4,1

C.

3,1,2,5,4,6

D.

1,5,4,6,2,3

答案:【B】

33、設(shè)一條單鏈表的頭指針變量為head且該鏈表沒有頭結(jié)點,則其判空條件是().

A.

head==O

B.

head->next==O

C.

head->next==head

D.

head!=O

答案:[A]

34、設(shè)某強連通圖中有n個頂點,則該強連通圖中至少有()條邊。

A.

n(n-l)

B.

n+1

c.

n

D.

n(n+l)

答案:【O

35、設(shè)順序表的長度為n,貝州頁序查找的平均比較次數(shù)為()。

A.

n

B.

n/2

C.

(n+l)/2

D.

(n-l)/2

答案:【。

36、設(shè)一棵三叉樹中有2個度數(shù)為1的結(jié)點,2個度數(shù)為2的結(jié)點,2個度數(shù)為3的結(jié)

點,則該三叉樹中有()個度數(shù)為0的結(jié)點。

A.

5

B.

6

C.

7

D.

8

答案:【。

37、若線性表最常用的澡作是存取第i個元素的值,則采用存儲方式節(jié)省時間。

A.

單鏈表

B.

雙鏈表

C.

單循環(huán)鏈表

D.

順序表

答案:【D】

38、設(shè)某散列表的長度為100,散列函數(shù)H(k)=k%P,則P通常情況下最好選擇(

A.

99

B.

97

c.

91

D.

93

答案:【B】

39、設(shè)有n個關(guān)鍵字具有相同的Hash函數(shù)值,則用線性探測法把這n個關(guān)鍵字映射到

HASH表中需要做()次線性探測。

A.

n2

B.

n(n+l)

C.

n(n+l)/2

D.

n(n-l)/2

答案:【D】

40、設(shè)某無向圖中有n個頂點e條邊,則建立該圖鄰接表的時間復(fù)雜度為()。

A.

O(n+e)

B.

0(小)

C.

O(ne)

D.

O(n3)

答案:【A】

41、設(shè)一棵m叉樹中度數(shù)為0的結(jié)點數(shù)為No,度數(shù)為1的結(jié)點數(shù)為N................

m的結(jié)點數(shù)為Nm,則N0=()。

A.

N1+N2+.....+Nm

B.

I+N2+2N3+3N4+.....+(m-l)Nm

C.

N2+2N3+3N4+.....+(m-l)Nm

D.

2NI+3N2+......+(m+l)Nm

答案:【B】

42、設(shè)指針q指向單躡中結(jié)點A,指針p指向單鏈表中結(jié)點A的后繼結(jié)點B,指針s

指向被插入的結(jié)點X,則在結(jié)點A和結(jié)點B插入結(jié)點X的操作序列為()。

A.

s->next=p->next;p->next=-s

B.

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

C.

p->next=s->next;s->next=p

D.

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

答案:【B】

43、對n個記錄的文件講行快速排序,所需要的輔助存儲空間大致為()

A.

0(1)

B.

0(n)

C.

O(log2n)

D.

O(n2)

答案:【o

44、二叉樹的第k層的結(jié)點數(shù)最多為()。

A.

2k-l

B.

2K+1

C.

2K-1

D.

2k-l

答案:【D】

45、設(shè)輸入序列是1、2、3..........n,經(jīng)過棧的作用后輸出序列的第一個元素是n,則

輸出序列中第i個輸出元素是()。

A.

n-i

B.

n-1-i

C.

n+1-i

D.

不能確定

答案:

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

A.

8

B.

7

C.

6

D.

5

答案:【B】

47、樹最適合用來表示]).

A.

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

B.

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

C.

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

D.

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

答案:【C】

48、設(shè)一個有序的單鏈表中有n個結(jié)點,現(xiàn)要求插入一個新結(jié)點后使得單鏈表仍然保持

有序,則該操作的時間復(fù)雜度為()。

A.

O(log2n)

B.

0(1)

C.

0(M)

D.

0(n)

答案:【D】

49、設(shè)有5000個待排序的記錄關(guān)鍵字,如果需要用最快的方法選出其中最小的10個記

錄關(guān)鍵字,則用下列()方法可以達到此目的。

A.

快速排序

B.

堆排序

C.

歸并排序

D.

插入排序

答案:【B】

50、設(shè)二叉排序樹中有n個結(jié)點,則在二叉排序樹的平均查找長度為()。

A.

0(1)

B.

O(log2n)

C.

O(nlog2n)

D.

0(?。?/p>

答案:【B】

一、計算(每題參考分值5分)

1、對對{278,109,63,930,589,184,505,269,8,83}用基數(shù)排序方法進行排

序,寫出每一趟排序過程

正確答案:

第一趟排序后(個位有序):

930,063,083,184,505,278,008r109,589,269

第二趟排序后(在個位有序的基礎(chǔ)上使拾位有序):

505,008,109,930,063,269,278,083,184,589

第三趟排序后(在拾位有序的基礎(chǔ)上使百位有序):

008,063,083,109,184,269,278,505,589,930

2、已知一個網(wǎng)的鄰接矩陣A如下,試畫出該網(wǎng)。

00150022COco

QOco11QCcoco

co3coccco28

22co00QCcoco

00coQOQCcoco

15COcoCCcoCO

正確答案:

3、設(shè)通信用8個字符abcdefgh,各字符使用的相對頻率分別

為25,36,2,5,8,10,14,50,構(gòu)造哈夫曼樹,設(shè)計哈夫曼編碼,求該樹的帶樹路

徑長度WPLe

正確答案:

OTOW

IOOI:9

IOOOI:P

OOOOI:)

io:q

oo:e

g:1011

h:ll

WPL=(25+36+50)*2+(8+10+14)*4+(2+5)*5

二385

4、用kruskal方法求下圖的最小生成樹

正確答案:

5、對{49,38,65,97,76,13,27,49)進行直接插入排序,寫出每一趟排序

過程

正確答案:

第1趟i=2(3849)659776132749

第2趟i=3384965)9776132749

第3趟i=438496597)76132749

第4趟i=53849657697)132749

第5趟i=6(133849657697)2749

第6趟i=7(13273849657697)49

第7趟i=8(1327384949657697

6、以{45,53,12,37,24,100361,90,78}

構(gòu)造二叉排序樹。

正確答案:

7、以{24Z68,2755,23,11,10,19,20,79,84},構(gòu)造hash表并求平均查找

長度。表長度為

hash17,hash(key)=key%17o

用線性探測法解決沖突。

正確答案:

012345678910111213141516

68119205523271110791484

ASL=(l*10+3*2)/12=16/12

8、對對{278,109f63,930,589,184,505,269,8,83}用基數(shù)排序方法進行排

序,寫出每一趟排序過程

正確答案:

第一趟排序后(介位有序):

930,063,083,184,505,278,008f109f589,269

第二趟排序后(在個位有序的基礎(chǔ)上使拾位有序):

505,008,109,930,063,269,278,083,184,589

第三趟排序后(在拾位有序的基礎(chǔ)上使百位有序):

008,063,083,109,184,269,278,505,589,930

9、已知二叉樹先序遍歷序列是:abcdefg;中序遍歷

序列是:史更必寫出后序遍歷序列。

正確答案:

后序遍歷序列:cdbgfea

二、論述(每題參考分值5分)

10、設(shè)線性表存于整型數(shù)據(jù)a[l..MAXSIZE]的前n個分量中且遞增有序,將x

插入到線性表的適當(dāng)位置。

正確答案:

voidinsert(){

if(nv=MAXSIZE)〃當(dāng)順序表不滿時

{inti=n;

while(i>=l&&x<a[i])

{a[i+l]=a[i];i-;)

//我插入位置,并后移

a[i+l]=x;

n++;

}

)

p=p->next;

else

mark=O;

returnmark;

)

一、辨析(每題參考分值5分)

1、分析下列的算法,求T(n).(用大0表示)

i=l;j=O;

while(i+j<=n)

if(i>j)j++;elsei++;

正確答案:

T(n)=O(n)

二、計算(每題參考分值5分)

2、設(shè)有一組初始記錄關(guān)鍵字為(45,80,48,40,22,78),要求構(gòu)造一棵二叉排序樹

并給出構(gòu)造過程。

正確答案:

78-

3、請畫出下圖的鄰接矩陣和鄰接表。

正確答案:

解:鄰接矩陣:

01110

10101

11011

10101

01110

鄰接表:

4、設(shè)關(guān)鍵字序列(%,k2,…,kn-i)是堆,設(shè)計算法將關(guān)鍵字序列(ki,k2,…,kn-i,x)

調(diào)整為堆。

正確答案:

解:設(shè)關(guān)鍵字序列,是堆,設(shè)計算法將關(guān)鍵字序列(%,

(ki,k2…,kn-i)k2kn-i,x)

調(diào)整為堆。

voidadjustheap(intr[],intn)

(

intj=nj=j/2,temp=r[j-l];

while(i>=l)if(temp>=r[i-l])break;else{r[j-l]=r[i-l];j=i;i=i/2;}

r[j-l]=temp;

)

5、已知二叉樹先序遍歷序列是:abcdefg;中序遍歷

序列是:但a四寫出后序遍歷序列。

正確答案:

后序遍歷序列:cdbgfea

6、設(shè)計在鏈?zhǔn)浇Y(jié)構(gòu)上實現(xiàn)簡單選擇排序算法。

正確答案:

解:設(shè)計在鏈?zhǔn)浇Y(jié)構(gòu)上實現(xiàn)簡單選擇排序算法。

voidsimpleselectsorlklist(lklist*&head)

Iklist*p,*q,*s;intmin,t;

if(head==0||head->next==O)return;

for(q=head;q!=0;q=q->next)

min=q->data;s=q;

for(p=q->next;p!=0;p=p->next)if(min>p->data){min=p->data;s=p;}

if(s!=q){t=s->data;s->data=q->data;q->data=t;}

)

}

7、已知一個網(wǎng)的鄰接矩陣A如下,試畫出該網(wǎng)。

00150022coQO

on0011on0Oon

co3QOccco28

22coQOQCQOco

00co00QCQOco

15coCOccCOCO

正確答案:

8、已知一個散列表如下圖所示:

012345678910

2457364668

其散列函數(shù)為h(key)=key%U,處理沖突的方法為二次探查法,探查序列為:

22222

hi=(h(key)+di)%mdi=l/-l,2/-2,...,±k,(k<m/2)i=

回答下列問題:

(1)對表中關(guān)鍵字36,46,68和24進行杳找時,所需進行的比較次數(shù)各為多少?

(2)該散列表在等概率查找時查找成功的平均查找長度為多少?

正確答案:

解:(1)杳找36,46,68和24時,所需進行的匕徽次數(shù)各為1,4,5和3次。(2

分)

(2)ASLsuCC=(l+l+3+4+5)/5=14/5(3分)

9、已知二叉樹的前序遍歷序列是AEFBGCDHIKJ,中序遍歷序列是EFAGBCHKIJD,畫

出此二叉樹,并畫出它的后序線索二叉樹。

正確答案:

解:

NULL八,

10、設(shè)有一組初始記錄關(guān)鍵字序列(Ki,K2,...,Kn),要求設(shè)計一個算法能夠在O(n)

的時間復(fù)雜度內(nèi)將線性表劃分成兩部分,其中左半部分的每個關(guān)鍵字均小于Ki,右半部

分的每個關(guān)鍵字均大于等于心

正確答案:

解:設(shè)有一組初始記錄關(guān)睇字序列(Ki,K?,…,Kn),要求設(shè)計一個算法能夠在O(n)

的時間復(fù)雜度內(nèi)將線性表劃分成兩部分,其中左半部分的每個關(guān)鍵字均小于Ki,右半部

分的每個關(guān)鍵字均大于等于心

voidquickpass(intr[],ints,intt)

inti=sj=t,x=r[s];

while(i<j){

while(i<j&&r[j]>x)j=j-l;if(i<j){r[i]=r[j];i=i+l;}

while(i<j&&r[i]<x)i=i+l;if(i<j){r[j]=r[i];j=j-l;}

r[i]=x;

)

三、單選(每題參考分值2.5分)

11、設(shè)有序順序表中有n個數(shù)據(jù)元素,則利用二分查找法查找數(shù)據(jù)元素X的最多比較次

數(shù)不超過()0

A.

Iog2n+1

B.

Iog2n-1

C.

log2n

D.

Iog2(n+1)

答案:【A】

12、下面關(guān)于線性表的敘述錯誤的是()o

A.

線性表采用順序存儲必須占用一片連續(xù)的存儲空間

B.

線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間

C.

線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實現(xiàn)

D.

線性表采用順序存儲便于插入和刪除操作的實現(xiàn)

答案:【D】

13、隊列是一種()的線性表。

A.

先進先出

B.

先進后出

C.

只能插入

D.

只能刪除

答案:【A】

14、在二叉排序樹中插入一個關(guān)鍵字值的平均時間復(fù)雜度為().

A.

0(n)

B.

O(log2n)

C.

O(nlog2n)

D.

0(小)

答案:【B】

15、深度為k的完全二叉樹中最少有()個結(jié)點。

A.

2匕1-1

B.

21

C.

2k-1+l

D.

2k.i

答案:【B】

16、若線性表最常用的操作是存取第i個元素的值,則采用_____存儲方式節(jié)省時間。

A.

單鏈表

B.

雙鏈表

C.

單循環(huán)鏈表

D.

順序表

答案:【D】

17、設(shè)某棵二叉樹中只有度數(shù)為0和度數(shù)為2的結(jié)點二度數(shù)為0的結(jié)點數(shù)為n,則這棵

二叉中共有()個結(jié)點。

A.

2n

B.

n+l

C.

2n-l

D.

2n+l

答案:【C】

18、()二叉排序樹可以得到一個從小到大的有序序列.

A.

先序遍歷

B.

中序遍歷

C.

后序遍歷

D.

層次遍歷

答案:【B】

19、下面程序的時間復(fù)雜度為()

for(i=l,s=0;i<=n;i++){t=l;for(j=l;j<=i;j++)t=t*j;s=s+t;}

A.

0(n)

B.

0(n2)

C.

0(n3)

D.

0(n4)

答案:【B】

20、設(shè)有n個待排序的記錄關(guān)鍵字,則在堆排序中需要()個輔助記錄單元。

A.

1

B.

n

C.

nlog2n

D.

n2

答案:[A]

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

A.

8

B.

7

C.

6

D.

5

答案:【B】

22、利用直接插入排序法的思根建立一個有序線性表的時間復(fù)雜度為().

A.

0(n)

B.

O(nlog2n)

C.

0(己)

D.

O(log2n)

答案:【C】

23、二路歸并排序的時間復(fù)雜度為()。

A.

0(n)

B.

0(小)

C.

O(nlog2n)

D.

O(log2n)

答案:【。

24、設(shè)輸入序列是1、2、3..........n,經(jīng)過棧的作用后輸出序列的第一個元素是n,則

輸出序列中第i個輸出元素是()。

A.

n-i

B.

n-1-i

C.

n+1-i

D.

不能確定

答案:

25、設(shè)有一個二維數(shù)組A[mi[n\,假設(shè)40]⑼存放位置在644(i0),42][2]存放位置在

676(io),每個元素占一個空間,問43][3]QO)存放在什么位置?腳注(10)表示用10進制表

A.

688

B.

678

C.

692

D.

696

答案:【。

26、一隊列的入隊序列是1,2,3,4,則隊列的輸出序列是

A.

1,2,3,4

B.

4,3,2,1

c.

1,4,3,2

D.

3,2,4,1

答案:【A】

27、下列四種排序中()的空間復(fù)雜度最大。

A.

插入排序

B.

冒泡排序

C.

堆排序

D.

歸并排序

答案:【D】

28、若有18個元素的有序表存放在一維數(shù)組A[19]中,第一個元素放A[l]中,現(xiàn)進行

二分查找,則查找A[3]的比較序列的下標(biāo)依次為()

A.

1,2,3

B.

952,3

C.

9,5,3

D.

9,4,2,3

答案:【D】

29、對于線性表(7,34,55,25,64,46,20,10)進行散列存儲時,若選用H(K)

=K%9作為散列函數(shù),則散列地址為1的元素有()個。

A.

1

B.

2

C.

3

D.

4

答案:【D】

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

針,指針變量s指向?qū)⒁腙犃械慕Y(jié)點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

31、設(shè)一棵m叉樹中有Ni個度數(shù)為1的結(jié)點,Nz個度數(shù)為2的結(jié)點.....Nm個度

數(shù)為m的結(jié)點,則該樹中共有()個葉子結(jié)點。

A.

m

}=i

B.

m

1=1

c.

2地

2=2

D.

m

1+Z(-1)M

2=2

答案:【D】

32、一個非空廣義表的表頭

A.

一定是子表

B.

一定是原子

C.

不能是子表

可以是原子,也可以是子表

答案:【B】

33、單鏈表的存儲密度

A.

大于1

B.

等于1

C.

小于1

D.

不能確定

答案:【C】

34、設(shè)某哈夫曼樹中有199個結(jié)點,則該哈夫曼樹中有()個葉子結(jié)點。

A.

99

B.

100

C.

101

D.

102

答案:【B】

35、建立一個長度為n的有序單鏈表的時間復(fù)雜度為()

A.

O(n)

B.

0(1)

C.

0(己)

D.

O(log2n)

答案:【C】

36、設(shè)某有向圖的鄰接表中有n個表頭結(jié)點和m個表結(jié)點,則該圖中有()條有向邊。

A.

n

B.

n-1

C.

m

D.

m-1

答案:【。

37、設(shè)一組初始記錄關(guān)鍵字序列為(25,50,15,35,80,85,20,40,36,70),其

中含有5個長度為2的有序子表,則用歸并排序的方法對該記錄關(guān)鍵字序列進行一趟歸

并后的結(jié)果為()。

A.

15,25,35,50,20,40,80,85,36,70

B.

15,25,35,50,80,20,85,40,70,36

C.

15,25,35,50,80,85,20,36,40,70

D.

15,25,35,50,80,20,36,40,70,85

答案:【A】

38、設(shè)完全無向圖中有n個頂點,則該完全無向圖中有()條邊。

A.

n(n-l)/2

B.

n(n-l)

C.

n(n+l)/2

D.

(n-l)/2

答案:[A]

39、具有n個結(jié)點的完全二叉樹的深度為

A.

riog2nj+1

B.

Iog2n+1

c.

log2n

D.

[logznj

答案:【D】

40、下列算法的時間復(fù)雜度是

for(i=0;i<n;i++)c[i]=i;

A.

0(1)

B.

0(n)

C.

O(log2n)

D.

O(nlog2n)

答案:【B】

41、設(shè)某棵三叉樹中有40個結(jié)點,則該三叉樹的最小高度為()。

A.

3

B.

4

C.

5

D.

6

答案:【B】

42、若有18個元素的有序表存放在一維數(shù)組A[19]中,第一個元素放A[l]中,現(xiàn)進行

二分查找,則查找A[3]的比較序列的下標(biāo)依次為()

A.

1,2,3

B.

952,3

C.

9,5,3

D.

9,4,2,3

答案:【D】

43、循環(huán)隊列SQ的存儲空間是數(shù)組d[m],隊頭、尾指針分別是front和rear,則執(zhí)行

入隊后其尾指針值rear是

A.

rear=rear+l

B.

rear=(rear+l)%(m-l)

C.

rear=(rear+l)%m

D.

rear=(rear-l)%m

答案:【O

44、設(shè)無向圖G中有n個頂點,則該無向圖的最小生成樹上有()條邊c

A.

n

B.

n-1

C.

2n

D.

2n-l

答案:【B】

45、設(shè)一組初始記錄關(guān)鍵字序列為(45,80,55,40,42,85),則以第一個記錄關(guān)鍵

字45為基準(zhǔn)而得到一趟快速排序的結(jié)果是()。

A.

40,42,45,55,80,83

B.

42,40,45,80,85,88

C.

42,40,45,55,80,85

D.

42,40,45,85,55,80

答案:【。

46、對n個記錄的文件進行快速排序,所需要的輔助存儲空間大致為()

A.

0(1)

B.

0(n)

C.

0(log2n)

D.

0(n2)

答案:【C】

47、設(shè))1質(zhì)序線性表的長度為30,分成5塊,每塊6個元素,如果采用分塊查找,則其

平均查找長度為()。

A.

6

B.

11

C.

5

D.

6.5

答案:【D】

48、設(shè)散列表中有m個存儲單元,散列函數(shù)H(key)=key%p,則p最好選擇(

A.

小于等于m的最大奇數(shù)

B.

小于等于m的最大素數(shù)

c.

小于等于m的最大偶數(shù)

D.

小于等于m的最大合數(shù)

答案:【B】

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

分別為()。

A.

n,e

B.

e,n

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論