聯(lián)大-《數(shù)據(jù)結(jié)構(gòu)》B及答案

11.在單鏈表指針為P的結(jié)點(diǎn)之后插入指針為S的結(jié)點(diǎn)，正確的操作是：()。

數(shù)據(jù)結(jié)構(gòu)課程考試試卷BA.p->next=s;s->next=p->next;B.s->next=p->next;p->next=s;

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

專(zhuān)業(yè)：考試日期：時(shí)間：120分鐘總分：100分閉卷

一大題：選擇題(共20小題，每小題1分，共25分)12.若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間

復(fù)雜度為()(l<=i<=n+l)o

1.算法的時(shí)間復(fù)雜度取決于()

A.0(0)B.0(1)C.0(n)D.0(n2)

A.問(wèn)題的規(guī)模B.待處理數(shù)據(jù)的初態(tài)C.A和BD.無(wú)正確答案

2.對(duì)于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的單鏈表，判定該表為空表的條件是()

A.head==NULLB.head->next==NULLC.head--next—headD.head!=NULL

13.若已知一個(gè)棧的入棧序列是1,2,3,…，n,其輸出序列為出,P2,P3,…，出若6是n,則

3.下面關(guān)于算法說(shuō)法錯(cuò)誤的是()

Pi是()。

A.算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)

A.iB.n-iC.n-i+1D.不確定

B.為解決某問(wèn)題的算法同為該問(wèn)題編寫(xiě)的程序含義是相同的

14.有六個(gè)元素6,5,4,3,2,1的順序進(jìn)棧，問(wèn)下列哪一個(gè)不是合法的出棧序列？()

C.算法的可行性是指指令不能有二義性D.以上幾個(gè)都是錯(cuò)誤的

A.543612B.453126C.346521D.234156

4.下面說(shuō)法錯(cuò)誤的是()

15.設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素el,e2,e3,e4,e5和e6依次通過(guò)棧S,一個(gè)元

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

素出棧后即進(jìn)隊(duì)列Q，若6個(gè)元素出隊(duì)的序列是e2,e4,e3,e6,e5,el則棧S的容量至少應(yīng)

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

該是()。

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

A.6B.4C.3D.2

(4)同一個(gè)算法，實(shí)現(xiàn)語(yǔ)言的級(jí)別越高，執(zhí)行效率就越低

16.串的長(zhǎng)度是指()

A.(1)B.(1),(2)C.(1),(4)D.(3)

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

5.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為()兩大類(lèi)。

C.串中所含不同字符的個(gè)數(shù)D.串中所含非空格字符的個(gè)數(shù)

A.動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B.順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)

17.假設(shè)以行序?yàn)橹餍虼鎯?chǔ)二維數(shù)組A=array[L.100,1..100],設(shè)每個(gè)數(shù)據(jù)元素占2個(gè)存

C.線性結(jié)構(gòu)、非線性結(jié)構(gòu)D.初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)

儲(chǔ)單元，基地址為10,則LOC[5,5]=(

6.以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)的術(shù)語(yǔ)是()。

A.808B.818C.1010D.1020

A.循環(huán)隊(duì)列B.鏈表C.哈希表D.棧

18.數(shù)組4[0..4,-1..-3,5..7]中含有元素的個(gè)數(shù)

7.下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？()

A.55B.45C.36D.16

0“.A.存儲(chǔ)密度大B.插入運(yùn)算方便C.刪除運(yùn)算方便D.可方便地用于各種邏輯結(jié)構(gòu)

19.用數(shù)組r存儲(chǔ)靜態(tài)鏈表，結(jié)點(diǎn)的next域指向后繼，工作指針j指向鏈中結(jié)點(diǎn)，使j沿

忠.的存儲(chǔ)表示

鏈移動(dòng)的操作為0。

當(dāng).8.下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪?個(gè)？()

A.j=r[j].nextB.j=j+lC.j=j->nextD.j=r[j]->next

的.A.線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。

20.二叉樹(shù)的第I層上最多含有結(jié)點(diǎn)數(shù)為()

.B.線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。

A.21B.2'-1C.2,HD.21-1

C.線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。

21.一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹(shù)的高h(yuǎn)為()

蟒D.線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。

A.11B.10C.11至1025之間D.10至1024之間

9.若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，

22.下列說(shuō)法不正確的是()。

則利用()存儲(chǔ)方式最節(jié)省時(shí)間。

A.圖的遍歷是從給定的源點(diǎn)出發(fā)每一個(gè)頂點(diǎn)僅被訪問(wèn)一次

A.順序表B.雙鏈表C.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D.單循環(huán)鏈表

C.圖的深度遍歷不適用于有向圖

10.若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入?個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)。則

B.遍歷的基本算法有兩種：深度遍歷和廣度遍歷

S采用()存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。

D.圖的深度遍歷是一個(gè)遞歸過(guò)程

A.單鏈表B.雙鏈表C.單循環(huán)鏈表D.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表

23.假定有k個(gè)關(guān)鍵字互為同義詞，若用線性探測(cè)法把這k個(gè)關(guān)鍵字存入散列表中，至少要

進(jìn)行多少次探測(cè)？（）按照普里姆算法從頂點(diǎn)2出發(fā)得到最小生成樹(shù)，試寫(xiě)出在最小生成樹(shù)中依次得到的各條邊。

A.k-1次B.k次C.k+1次D.k（k+l）/2次（要求給出詳細(xì)的求解過(guò)程）

24.將10個(gè)元素散列到100000個(gè)單元的哈希表中,則（）產(chǎn)生沖突。

A.一定會(huì)B.一定不會(huì)C.仍可能會(huì)

25.下列排序方法中，哪一個(gè)是穩(wěn)定的排序方法？（）

4.己知一個(gè)有向圖的頂點(diǎn)集V和邊集G分別為：

A.直接選擇排序B.二分法插入排序C.希爾排序D.快速排序

二大題：填空題（共10空，每小空2分，共20分）V={V0,VI,V2,V3,V4,V5}；

1.對(duì)于棧操作數(shù)據(jù)的原則是,隊(duì)列操作數(shù)據(jù)的原則是。E={<V1,V2>10,<V0,V2>10,<V0,V5>95,<V0,V4>30,<V2,V3>50,<V3,V5>10,

2.下面程序段的時(shí)間復(fù)雜度為o（n>l）<V4,V5>60,<V4,V3>20}；

sum=l；

for（i=0;sum<n;i++）sum+=l;給出從VO出發(fā)到各個(gè)終點(diǎn)的最短路徑和路徑長(zhǎng)度。（要求給出詳細(xì)的求解過(guò)程）

3.設(shè)單鏈表的結(jié)點(diǎn)結(jié)構(gòu)為（data,next）,next為指針域，已知指針px指向單鏈表中data為

x的結(jié)點(diǎn)，指針py指向data為y的新結(jié)點(diǎn)，若將結(jié)點(diǎn)y插入結(jié)點(diǎn)x之后，則需要執(zhí)行以下5.已一組記錄為（46,74,53,34,26,38,76,62,27,14）,試以順序表為存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)簡(jiǎn)單插入

語(yǔ)句：；O排序（從大到?。┑乃惴ā＃?0分）

4.設(shè)一棵完全二叉樹(shù)共有30個(gè)結(jié)點(diǎn)，則在該二叉樹(shù)中的葉子結(jié)點(diǎn)數(shù)為

度為2的結(jié)點(diǎn)個(gè)數(shù)為o

5.在雙向鏈表中，每個(gè)結(jié)點(diǎn)含有兩個(gè)指針域，一個(gè)指向結(jié)點(diǎn)，另一個(gè)指向___

結(jié)點(diǎn)。

6.一個(gè)棧的輸入序列是：1,2,3則不可能的棧輸出序列是o

三大題：應(yīng)用題（共6小題，共55分，第一題15分，后幾題每題10）

1.試對(duì)右圖中的二叉樹(shù)畫(huà)出其：

（I）順序存儲(chǔ)表示的示意圖；（5分）

（2）二叉鏈表存儲(chǔ)表示的示意圖。（5分）y尸尸

（3）給出該二叉樹(shù)的后序遍歷.（5分）缸、⑤、O'

圖

2.若字母兒8,（\。忑產(chǎn)給定一組權(quán)值（5,8,11,17,7,2）,試設(shè)計(jì)相應(yīng)的哈夫曼樹(shù)和字

母相應(yīng)的哈夫曼編碼。

3.已知一個(gè)圖的頂點(diǎn)集V和邊集G分別為:

V=(0.1,2,3,4,5,6,7)；

E={(0,1)3,(0,3)5,(0.5)18,(1,3)7,(1,4)6,(2,4)1(),(2,7)20,(3,

5)15,(3,6)12,(4,6)8,(4,7)12)；

《數(shù)據(jù)結(jié)構(gòu)與算法》課程試卷B

一、單項(xiàng)選擇題（每題1分，共25小題，總共25分）

數(shù)據(jù)結(jié)構(gòu)課程考試答題紙

(l-10)cbdccdabad

一大題：選擇題（共2°小題,每小題1分,共2。分）0

(ll-20)bcdecbbbac

123456789］加

堂（21-25）ccdcb

二、填空題（每空1分，共8小題，總共10分）

而

r

1112131415161718194

料1.數(shù)據(jù)元素?cái)?shù)據(jù)元素間關(guān)系

2.0（n）

3.順序4.(n-1)/25.py->next=px->next;px->next=py

二大題：填空（共10小空，每小空1分，共10分）..6、后進(jìn)先出

7、棧8、312

三、判斷（每題1分，共10小題，總共10分）

1.___________,.____________2._____________超

1.X2.J3.J4.J5.V6.X7.J8.X9.X10.V

Q?

3.?,四、應(yīng)用題（共四小題，第二題10分，其余小題每題15分，總共55分）

2“

會(huì)4.________________第一?題：⑴E

AF

DH

5.,.CGI

B（5分）

“

三大題：應(yīng)用題（共6小題，共70分）會(huì)（2）前序序列為EADCBFHGI中序序列為ABCDEFGH1

后序序列為BCDAGIHFE（10分）

與

第二題：

峭

01234567891011121314

心

991001893534537829452402021208350

”

疑-

-11121361812235(5分)

與-查找成功的查找長(zhǎng)度為：（6*1+3*2+2*3+54-6+8）/14=37/14（5分）

授-

-第三題：

的

-