華東交通大學(xué)-學(xué)年第一學(xué)期考試卷數(shù)據(jù)結(jié)構(gòu)

k紀違試考道知22不k紀違試考道知22將分處上以及過

華東交通大學(xué)第一學(xué)期考試卷試卷編號：（A）卷構(gòu)(課程類別（考試日期：記到

受弊作

因和籍學(xué)除開被將

考生注意事項：1、本試卷共頁總分100分考試時間120分。、考試結(jié)束后，考生不得將試卷、答題紙和草稿紙帶出考場。者考人他代或考代人他

題題分，分)1．以下不于算法要素的是（有窮性B.可行性C.可讀性D.輸入2．順序表機訪問元素a基本操作的時間復(fù)雜度為（1O(nC.logn)D.O(k)

得

評人請道知還，性重嚴的弊作、。果后切一的，起律引紀此場由考擔(dān)守承遵愿格，嚴位將學(xué)我士：學(xué)諾予承授

3．圖的廣優(yōu)先搜索算法中定義的輔助數(shù)據(jù)結(jié)構(gòu)為（）A.隊列B.棧C.鄰接表D.二叉樹4．求T在串S首次出現(xiàn)位置的基本操作叫做（）求子串B.模式匹配C.串替換D.串連接5．廣義表L=(apple,pear),(banana,orange))的表尾是（）(apple,)B.((apple,pear)C.(banana,orange)D.(()6．n×n對稱矩陣壓縮存儲到（）個元的空間中考范圍之）nB.nC.n(n+1)D.7．在一棵有2009結(jié)點的完全二叉樹中，葉子結(jié)點有（）個。1001B.C.1005D.8．由權(quán)值為7，1926，32，3，，10的結(jié)點構(gòu)成的赫夫曼樹的帶權(quán)路徑長度為（）271B.261C.241D.2319．有向圖所有頂點的入度之和為n，則出之和為（）B.C.n-110在有序表(1,8,9,16,23)中折半查找關(guān)鍵字的比較次數(shù)是（）A.2B.3C.4D.5/

題空分，分)

得

評人1．線性表順序表示稱為_順序表_。2．8個頂點的連通圖最多有_邊，最少有_7___條邊。3．含9葉子結(jié)點的3階B-樹中至少有_非葉子結(jié)點考試范圍外）4．廣義表(()a,((b,),d)的深度為_3__。5．按低下優(yōu)先存儲整數(shù)數(shù)A9×3×5×8

時，1元素a的存儲地址是0，每個整數(shù)40000字節(jié)，a的地址是____________考試范之外）31256．設(shè)S=‘IAMAWORKER!T=‘GOOD，Concat(SubString(6,2),Concat(SubString(S,7,))=

AGOOD

。7．總長的順序循環(huán)隊列中，隊頭指針為front，隊指針為rear，隊列滿的件為______(rear+1)n=front____，隊列空的條件為_front=rear__。8．下圖中AOE-關(guān)鍵活動為

<A,B>__，，，<H,I。9．下圖中有向圖，從頂點A出發(fā)進行廣度優(yōu)先遍歷的頂點序列為_ABCDEFGHI___。10p指向單鏈表L的中間結(jié)點的指針，補充下列刪除p后繼結(jié)點的程序段。

G

2s

B

1

8

I__p->nexet=s->next;____free();11程序段

A

6

4

C1

E

7

H

4for(i=0;i<n;)for(j=0;j<i;j++)k++;

5

D

2

F

4中，語句的執(zhí)行次數(shù)為_。題題分，分)1．寫出圖所示的AOV網(wǎng)的個不同的拓撲序列。參考答：11，5，2，，6231，5，2，，3

得

評人5

4

1，5，6，，36/

2．畫出和圖中的森林對應(yīng)的二叉樹。A

H

J

M

IK

LN

OC

D

E

PF

G參考答：AB

HC

I

JD

K

MF

E

L

NG

O3．進棧序為ABC寫出所有可能的出棧序列。參考答：可以通窮舉所有可性來求：①A入A出，B出C入C出，即；②A入A出，B、、，即ACB③、B入，出，C入出，A出即BCA；④、B入，BA出C入出，即BAC⑤、、入，、B、出，即CBA；合計有可能性。4．按照四運算加、減、乘、除和冪運算(∧)的優(yōu)先關(guān)系的慣例，將表達式A－＋∧F轉(zhuǎn)換為前綴和后綴表式（試范圍外）5．畫3結(jié)點的二叉樹的所有形態(tài)。5形態(tài)6．二叉樹先序序列為，中序序列為CBAEDF，畫出該二叉樹。參考答：AB

DCE

F/4

i7．按下表關(guān)鍵字的順序構(gòu)造一棵二叉平衡樹。i

（考試圍之外）(5,1,9,2,10,)8選取哈希函數(shù)H(k)(3k)MOD11用開放地址法處理沖突d=i((7k)MOD10+1)(i1,3,在的散列地址空間中對關(guān)鍵字序列(53,30,67構(gòu)造哈希表。參考答：01357891022674153461301題題分共)1．寫一算，對帶頭結(jié)點的單鏈表L實現(xiàn)就地逆置。單鏈表結(jié)點