南京郵電大學(xué)2000年碩士研究生入學(xué)考試

數(shù)據(jù)結(jié)構(gòu)試題

一、完成下列各題（每小題6分，共18分）

1.設(shè)n是偶數(shù)，試計(jì)算運(yùn)行下列程序段后m的值并給出該程序段的時(shí)間復(fù)雜度。

m:=0；

FORi:=lTOnDO

FORj:=2*iTOnDO

m：=m+l；

2.已知字符串'cddcdececdea',過算每介字符的next和nextval函數(shù)的值.

3.給出冒泡排序和快速排序的最好情況,平均情況和最壞情況下的時(shí)間復(fù)雜度。

二、完成下列各題：（每小題8分，共24分）

1、設(shè)有下圖所示的有向圖，給出其鄰接矩陣和強(qiáng)連通分量。

2、設(shè)有3階B-樹如下圖所示，

（1）從該B-樹上依次插入關(guān)鍵字33,97,畫出兩次插入后的B-樹；

（2）從（1）得到的B-樹上依次刪除66,43,畫出兩次刪除后的B-樹;

現(xiàn)有8人初始游程，每個(gè)游程的第一、二個(gè)記錄的關(guān)鍵字分別為:

T程12345678

記錄

1182197124519

二1533251416184823

(1)畫出據(jù)此構(gòu)造的敗選擇樹

(2)畫出輸出一個(gè)記錄后的敗方樹

三、閱讀下列二叉樹算法，每個(gè)結(jié)點(diǎn)三個(gè)域：Ichild,element,rchildo(10分)

(l)X(p)對以p為根的二叉樹執(zhí)行什么功能？

(2)以下圖所示的二叉樹調(diào)用此算法，則X(p)的執(zhí)行結(jié)果是什么？

(3)執(zhí)行中，棧s中元素個(gè)數(shù)最多時(shí)為多少?給出該時(shí)棧中元素的情況。

voidX(BinTree*t)

{structStacks;

BinTnode*q

Push(s,NULl)

While(*p)

{q=(*p)->lchild

(*p)->lchild=(*p)->rchild

(*p)->rchild=q

If((*p)->lchild)Push(s,(*p)->lchild);

If((*p)->rchiId)Push(s,(*p)->rchiId)；

else(*p)=Pop(s)

)

)

四、閱讀下列要求每對頂點(diǎn)之間的最短路徑的Floyd算法。(16分)

(1)若對下圖所示的有向圖執(zhí)行此算法，寫出對k為1到n的各步中，二維數(shù)組

a和path的值。

(2)試設(shè)計(jì)一個(gè)算法,打印每對頂點(diǎn)<ij>(l<=i,j<=n)之間的最短路徑長度

(a[i,j]的值)及其對應(yīng)的那條路徑(路徑上的頂點(diǎn)序列)。

CONSTn={usersuppliedinteger)

TYPEgraph=ARRAY[l..n,1..n]OFreal;

Pathtype=ARRAY[l..n,1..n]OFinteger;

PROCEDUREFloyd(cost:graph;VARa:graph;VARpath:pathtype);

VAR1,j,k,integer;

BEGIN

FORi:=lTOnDO

FORj:=lTOnDO

BEGIN

A[i,j]:=cost[i,j]；

IF(iOj)and(a[i.j]<maxnum)

THENpath[i,j]:=i

ELSEpath[i,j]:=0；

END

FORk:=lTOnDO

FORi:=lTOnDO

FORj=lTOnDO

IFa[i.j]:=a[i,k]+a[k,j]；

THENBEGIN

a[i,j]:=a[i,k]+a[k,j]；

path[i,j]:=path[k,j]；

END

END

五、設(shè)計(jì)一個(gè)算法判斷一個(gè)算數(shù)表達(dá)式中的括號是否配對。算數(shù)表達(dá)式保存在帶

表頭結(jié)點(diǎn)的單循環(huán)鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)域：ch和link,其中ch域?yàn)樽址?/p>

型。（16分）

六、試設(shè)計(jì)一個(gè)遞歸算法有一棵有n各結(jié)點(diǎn)的隨機(jī)建立的二叉排序樹上查找第k

（l〈=k〈=n）小元素，并返回指向該結(jié)點(diǎn)的指針。要求算法的平均時(shí)間復(fù)雜度為

o（log2n）2并說明你所設(shè)計(jì)的算法具有該時(shí)間復(fù)雜度的理由。二叉排序樹的每個(gè)

結(jié)點(diǎn)有四個(gè)域:Ichild,element,rchild,counto其中,count域中包存有以該

結(jié)點(diǎn)為根的樹（子樹）上的結(jié)點(diǎn)數(shù)目。（16分）

南京郵電學(xué)院

2001年攻讀碩士學(xué)位研究生入學(xué)

數(shù)據(jù)結(jié)構(gòu)試題

一、完成下列各題(每小題6分，共18分)：

1.已知字符串P='abbabbac',計(jì)算next(7)和mextval(7)的值.

2.給出下列排序軟法的最壞情況時(shí)間復(fù)雜性，并指出哪些算法是穩(wěn)定的？

(1)塊速排序(2)簡單選擇排序(3)堆排序

3.設(shè)度為m的樹采用多重鏈表存儲。每個(gè)結(jié)點(diǎn)有m+1個(gè)域，其中有一個(gè)數(shù)據(jù)域,

m個(gè)指向孩子的指針域。則空指針的數(shù)目是多少?說明這種存儲方式的利弊。

二、完成下列各題：(每小題8分，共40分)

1.設(shè)二叉樹以帶右鏈的先序次序順序存儲，其存儲結(jié)構(gòu)如下：則畫出該二叉樹。

6350009000

EHFIGABDCJ

2.對于下列AOE網(wǎng)絡(luò)，求出各活動可能的最早開始時(shí)間和允許的最晚完成時(shí)間。

并問整個(gè)工程的最短完成時(shí)間是多少？

3設(shè)有13個(gè)初始游程。其長度分別為28,16,33,19,5,7,18,20,12,31,

38,22,10。試畫出4路合并的最佳合并樹;并計(jì)算它的加權(quán)路徑長度。

4.設(shè)散列表ht長度為11,散列函數(shù),hl(key)=keymodll,h2(key)=keymod9+lo采

用雙重探查法解決沖突,請從空表開始,依次插入下列關(guān)鍵字值序列,70,25,80,

35,60,45,50,55,建立散列表。

5.設(shè)有初始關(guān)鍵字值序列為：71,74,2,72,54,93,52,28,現(xiàn)采用堆排序

方法進(jìn)行排序，請給出手工執(zhí)行堆排序的過程。

三、設(shè)E是一棵擴(kuò)充二叉樹的外路徑長度，I是內(nèi)路徑長度,n是內(nèi)結(jié)點(diǎn)個(gè)數(shù)。試

寫出三者的關(guān)系式，并使用數(shù)學(xué)歸納法證明之。（10分）

四、有序表以順序方式存儲，其存儲結(jié)構(gòu)說明如下：

typelist=array[1..n]ofinteger:

實(shí)現(xiàn)下列對半查找的函數(shù)過程：

Function,bisearch（r:list:low,high,tkey:integer）:integer:

其中，tkey為待查關(guān)鍵字值。若tkey在表r中，則返回該關(guān)鍵字值在表中的位

置，否則返回0。并畫出n=10的對半查找二叉判定樹。（16分）

五、已知有n個(gè)結(jié)點(diǎn)的樹以雙親表示法存儲在一維數(shù)組中。請?jiān)O(shè)計(jì)一個(gè)的算法求

樹中每個(gè)結(jié)點(diǎn)的層次和樹的高度，將求得的每個(gè)結(jié)點(diǎn)的層次保存在一維數(shù)組c

中、并分析你所設(shè)計(jì)的算法的時(shí)間復(fù)雜性.（16分）

南京郵電學(xué)院

2002年攻讀碩士學(xué)位研究生入學(xué)

數(shù)據(jù)結(jié)構(gòu)試題

一、回答下列各題(每小題4分，共36分)

1.設(shè)n是偶數(shù)，且有程序段：

Fori:=1tonDo

If2*i<=n

ThenForj:=2*itonDoy:=y+i*j；

則語句"y：=y+i*j”的執(zhí)行次數(shù)是多少?要求列出計(jì)算公式.

2.已知二叉樹T的中根序列是CBEDAGJIFH,后根序列是CEDBJIGHFA:二叉樹跟結(jié)

點(diǎn)的左、右孩子分別是何結(jié)點(diǎn)？

3.設(shè)有一個(gè)按元素的遞增次序排列的有序表(ai,a?…,a⑵)，現(xiàn)采用對半查找算法

在表中查找給定關(guān)鍵字值為K的元素，則當(dāng)K>a⑵和K=a^時(shí)，查找過程中元素之

間比較的次數(shù)分別是多少？

4.已知字符串P='cbcacbcc',則四*1;(4)和十*W21(7)的值分別為多少?

5.設(shè)A,B,C三個(gè)元素依次進(jìn)棧，進(jìn)棧后可立即出棧，則不可能得到的出棧次序

有哪些?列出所有不可能的出棧序列。

6.設(shè)結(jié)點(diǎn)X是樹T中的一個(gè)非根結(jié)點(diǎn)，B是T所對應(yīng)的二叉樹：在B中，結(jié)點(diǎn)Y

是X的右孩子，則

(1)在樹T中，結(jié)點(diǎn)X和Y是何關(guān)系？

(2)求二叉樹B的根結(jié)點(diǎn)的右子樹。

7.設(shè)線性表L=(a”a?,…，％)采用順序存儲表示。假定在任何一個(gè)元素之后以

及在第一個(gè)元素之前插入的概率相同。請寫出進(jìn)行一次插入操作平均移動元素次

數(shù)的計(jì)算公式，并進(jìn)行計(jì)算。

8.在快速排序方法中，每次劃分后：將對劃分所得的兩個(gè)長度不等的子表分別

排序。為提高排序效率，應(yīng)對其中哪個(gè)子表先排序？為什么？

9.說明下圖所示的結(jié)點(diǎn)是《數(shù)據(jù)結(jié)構(gòu)》中討論的何種數(shù)據(jù)結(jié)構(gòu)的結(jié)點(diǎn)，其中，

箭頭表示指向子樹的指針，數(shù)據(jù)為關(guān)鍵字值。并說明此數(shù)據(jù)結(jié)構(gòu)一般用作什么用

途。------------------------------------

9398,100,126、131

tt~~弋—

二.解答下列問題（每小題6分，共30分）

1.設(shè)有二叉樹如圖1所示，請畫出該樹的先序線索樹，試說明

構(gòu)造二叉線索樹的好處。

2.請給出圖2所示的有向圖的所有可能的拓?fù)溆行蛐蛄?。若拓?fù)渑判蚰茼樌谐?/p>

圖中全部頂點(diǎn)后結(jié)束，則表明該有向圖滿足什么條件？

圖2

3.在如圖3所示的二叉平衡樹上完成指定的插入新元素操作，畫出插入新元素,

并重新平衡后的樹。

⑴在（a）所示的二叉平衡樹上插入關(guān)鍵字值為15的新結(jié)點(diǎn)：

⑵在（b）所示的二叉平衡樹上插入關(guān)鍵字值為23的新結(jié)點(diǎn)；

(a)

(b)

圖3

4.采牛氏[m算法，以頂點(diǎn)片弊點(diǎn)，求圖4所示的無向圖的一棵最小代價(jià)生

成樹，！1，算該生成樹的（2；

5

圖4

5.設(shè)有關(guān)鍵字序列L=（12,2,16,30,8,28,4,10,20,6,18）。寫出

用下列排序方法從小到大排序時(shí)，第一趟處理結(jié)束時(shí)的序列。

（1）快速排序

（2）合并排序

三、（8分）

根據(jù)m階B樹的定義，求解下列問題。要求給出計(jì)算過程或說明理由。

1.計(jì)算m階旦樹的最大高度（不計(jì)葉子結(jié)點(diǎn)）；

2.從空樹田發(fā)構(gòu)造B樹，得到一裸有p個(gè)非葉結(jié)點(diǎn)的B樹。求為了得到該樹所

需的結(jié)點(diǎn)分裂的最多次數(shù)。

四、（12分）

設(shè)計(jì)一個(gè)算法將一個(gè)帶表頭結(jié)點(diǎn)的單鏈表Y,連接在另一個(gè)帶表頭結(jié)點(diǎn)單鏈

表X之后。單鏈表的每個(gè)結(jié)點(diǎn)有兩個(gè)域：data和link。算法可用PASCAL語言或

C語言描述，要求寫出類型說明。

五、（14分）

設(shè)計(jì)一個(gè)遞歸算法求一棵哈曼樹的帶權(quán)路徑長度。二叉樹的每個(gè)結(jié)點(diǎn)有三個(gè)

域：IchiId,rchild和elemento算法可用PASCAL語言或C語言描述，要求寫出

類型說明。

南京郵電學(xué)院

2003年攻讀碩士學(xué)位研究生入學(xué)

數(shù)據(jù)結(jié)構(gòu)試題

說明：1.本試卷有三類題型：填空題，解答題和算法設(shè)計(jì)題。

2.所有答題均寫在答題紙上（包括填空題），請務(wù)必準(zhǔn)確標(biāo)明答題的題號。

3.算法設(shè)計(jì)題使用Pascal或C/C++語言描述，但每位考生只能選用其中

一種語言描述。在同一試卷中不允許混用Pascal和C/C++兩種語言描述

算法

4.算法（程序）中需調(diào)用其他函數(shù)或過程，必須另行編寫，不允

許直接調(diào)用教材上已實(shí)現(xiàn)的過程或函數(shù)。

一、填空題（每小題4分，共40分）

1..在循環(huán)隊(duì)列中，隊(duì)列長度為n,存儲位置從0到n-1編號，以rear指示實(shí)際

的隊(duì)尾元素，現(xiàn)要在此隊(duì)列中插入一個(gè)新元素，新元素的位置是。

2..設(shè)二維數(shù)組A的行和列的下標(biāo)范圍分別為：［0：8］和［0：10］,每個(gè)元素占2

個(gè)單元,按行優(yōu)先順序存儲，第一個(gè)元素的查儲起始位置為b,則存儲位置為b+50

處的元素為o

3.已知字符串p='abcabcabbac',貝Unext（3）和next（6）分另U為。

4.現(xiàn)有值分別為A,B,C的3個(gè)元素，可組成個(gè)不同值的二叉樹。

5.設(shè)有3叉樹中度為1,2和3的結(jié)點(diǎn)的數(shù)目分別為15,6和7,則度為0的結(jié)

點(diǎn)數(shù)為o

6.設(shè)有向圖有n個(gè)頂點(diǎn)，e條邊，則對該圖執(zhí)行拓樸排序算法的時(shí)間復(fù)雜度

為。

7.當(dāng)采用拓樸排序算法求有向圖的拓樸有序序列時(shí)，有向圖具有特

性時(shí)，該算法在輸出圖中全部頂點(diǎn)后終止。

8.設(shè)5階B樹高度為2時(shí)（設(shè)根結(jié)點(diǎn)層飲為1,不計(jì)入最下層空子樹的層次，只

考慮包含元素的B樹結(jié)點(diǎn)的層次）,則該樹的最少關(guān)鍵字?jǐn)?shù)目是。

9.設(shè)用數(shù)組順序存儲線性表L=（al,,2..an）,假定刪除任何一個(gè)元素的概

率相同，則計(jì)算進(jìn)行一次刪除操作的平均移動元素的次數(shù)的計(jì)算公式為。

10.設(shè)有二叉樹的先序遍歷和中序遍歷的結(jié)點(diǎn)次序分別為：A,F,E,G,C,B,D,H和

E,F,G,C,A,D,B,H,則對其進(jìn)行后序遍歷的結(jié)點(diǎn)次序?yàn)椋骸?/p>

二、解答下列各題（每題8分，共40分）

1.設(shè)電文由6個(gè)字符A,B,C,D,E,F組成，它們在電文中出現(xiàn)的次數(shù)分別

為10,4,8,3,2,7。試畫出用于編碼的哈夫曼樹，并列出每個(gè)字符的編碼。

2.畫出對下列兩棵二叉（搜索）排序樹分別進(jìn)行平衡旋轉(zhuǎn)后的二叉平衡樹。設(shè)圖

中用矩形表示的各子樹都已是二叉平衡樹'要求說明是何種旋轉(zhuǎn)，并注明各圓形

結(jié)點(diǎn)的平衡因子。

I

hT-

3.求解下列各小題

（1）用克魯斯卡爾算法求下圖的最小代價(jià)生成樹，并畫出之。

（2）給出克魯斯卡爾算法的時(shí)間復(fù)雜度。設(shè)無向圖有n個(gè)頂點(diǎn)m條邊。

4.設(shè)有7個(gè)元素組成的數(shù)據(jù)元素集合S={1,2,3,4,5,6,7}。請分別給出使

下列排序算法產(chǎn)生最好和最壞情況時(shí)間的各一輸入數(shù)據(jù)實(shí)例。

（1）選擇排序

（2）冒泡排序

（3）快速排序

（4）直接插入排序

5.完成下列操作:

三、解答下列各題（12分）

1.試說明什么是好的散列函數(shù)。

2.設(shè)散列表的地址范圍是[0..M-1],寫出除留余數(shù)法的散列函數(shù)公式。

3.試說明線性探測法的不足之處。

4.現(xiàn)采用除留余數(shù)法計(jì)算地址，取M=ll,并采用線性探測法處理沖突。若輸入

一組記錄，其關(guān)鍵字值依此為；（60,78,63,121,77,80,35）,請畫出所構(gòu)造的

散列表。

四、解答下列各題（12分）

設(shè)有二又樹如下圖所示，bt

1、請畫出該樹的先序線索（穿線）樹。

2.請畫出該樹所對應(yīng)的森林。

3.請畫出該森林的雙親表示法的存儲結(jié)構(gòu)。B

五、（10分）

設(shè)A0E網(wǎng)如下圖所示。求各事件的可能的最早發(fā)生時(shí)間和允許的最遲較生時(shí)

間，以及關(guān)鍵活動和關(guān)鍵路徑及其長度。

六、（16分）

設(shè)計(jì)一個(gè)算法，實(shí)現(xiàn)在一個(gè)帶表頭結(jié)點(diǎn)的單鏈表上的簡單選擇排序算法。算

法用Pascal語言或C/C++語言的函數(shù)（或?qū)Τ蹋┟枋?。單鏈表中每個(gè)結(jié)點(diǎn)2個(gè)

域：data和link。要求先使用類型說明準(zhǔn)確描述你所使用的單鏈表存儲表示。

七、（20分）

設(shè)有一種被稱為"forgetfulversion的對半查找算法、

算法描述如下：設(shè)長度為n的有序表順序存儲在一維數(shù)組A中，數(shù)組A的下標(biāo)

從0開始編號。如果待查元素x在表中，則函數(shù)返回x在數(shù)組中的下標(biāo)，否則函

數(shù)返回一1。該函數(shù)在執(zhí)行一次待查元素和A中下標(biāo)為mid的元素之間的比較后，

即使比較相等也不終止算法，繼續(xù)將原表（設(shè)其上、下界下標(biāo)為low和high）劃

分成兩個(gè)子表。前一個(gè)子表的范圍是low到mid（含mid）,后一個(gè)子表的范圍是

mid+1到high。直到待查子表中只剩下一個(gè)元素時(shí)，再去判定待查元素與表中元

素是否相等，從而確定搜索成功與失敗。

（1）請寫出實(shí)現(xiàn)上述算法的Pascal語言或C/C++語言描述的非遞歸函數(shù)（或過

程）。要求先使用類型說明準(zhǔn)確描述你所使用的有序表的順序結(jié)構(gòu)。

（2）設(shè)以數(shù)組A存儲一個(gè)長度為10的有序表，試畫出以你的算法對A進(jìn)行對半

查找的二叉判定樹。該二叉判定樹上每個(gè)圓形結(jié)點(diǎn)代表一次元素間的比較。方形

結(jié)點(diǎn)代表算法終止（成功或失?。?。

南京郵電學(xué)院

2004年攻讀碩士學(xué)位研究生入學(xué)

數(shù)據(jù)結(jié)構(gòu)試題

說明：1.本試卷有五類題型：單選、填空，簡答、解答和算法設(shè)計(jì)題。

2.本試卷共4頁：所有答題均寫在答題紙上（包括單透題和填堂題），請

務(wù)必準(zhǔn)確標(biāo)明所答題的題號。

3.算法設(shè)計(jì)題使用Pascal或C/C++播言描速，但每住考生只能選用共中

一種語宮描述。在同一試卷中不允許混用Pascal和C/C++兩種語言描述

算法、你所使用的描述語言是（請考生填寫）.

4.算法（程序）中需調(diào)用其他函數(shù)或過程必須另行編寫，不允許直接調(diào)用

教材上已實(shí)現(xiàn)的過程或函數(shù)。

一、單選題（每題3分，共15分）

1.從堆中刪除一個(gè)元素的時(shí)間復(fù)雜度為（）

A.0（1）B.0（log2n）C.0（n）D.0（nlog2n）

2.下面關(guān)于二叉樹的結(jié)論正確的是（）

A二叉樹中，度為0的結(jié)點(diǎn)個(gè)數(shù)等于度為2的結(jié)點(diǎn)個(gè)數(shù)加1

B.二叉樹中結(jié)點(diǎn)個(gè)數(shù)必大于0

C.完全二叉樹中，任何一個(gè)結(jié)點(diǎn)的度或者為0,或者為2

D.二叉樹的度是2

3.對任意一棵樹，設(shè)它有n個(gè)結(jié)點(diǎn)，這n結(jié)點(diǎn)的度數(shù)之和為（）

A.nB.n-2C.n-1D.n+1

4.設(shè)X是樹T中的一個(gè)非根結(jié)點(diǎn)，B是T所對應(yīng)的二叉樹、在B中，X是

其雙親的右孩子，下列結(jié)論正確的是（）

A.在樹T中，X是其雙親的第一個(gè)孩子

B.在樹T中，X一定無右邊兄茅

C.在樹T中，X一定是葉子結(jié)點(diǎn)

D.在樹T中，X一定有左邊兄弟

5.送通的無向圖G有n個(gè)頂點(diǎn)，則圖G的最小生成樹的邊數(shù)為()

A.nB.n-lC.n*(n-l)/2D.n/2

二、填空題(每題5分，共40分)

1.設(shè)a=6,b=4,c=2,d=3,e=2,則后綴表達(dá)式abc-/de*+的值為.

2.設(shè)有元素序列的入棧次序?yàn)椋?a”a2,....an.),其出棧的次序?yàn)?

(apbap2-.ap?),現(xiàn)已知pl=n,則pi=。

3.設(shè)對一棵二叉樹進(jìn)行三種次序的遍歷(結(jié)點(diǎn)的值為字母，大小按字母

順序).已知其中序和后序遍歷的結(jié)果分別為dbeafcg和dbfgca,則先

序遍歷次序是o

4.在有序表(22,29,33,39,42,47,50,65,68)中以對半查找方法

查找元素39,40,則元素間的比較次數(shù)分別為和。

5.簡單選擇算法的最好和最壞情況時(shí)間復(fù)雜度分別為和o

6.設(shè)有一個(gè)二維數(shù)組(二維下標(biāo)為[O..mT,假定每

個(gè)元素占一個(gè)空間，元素A{0][0]和A[2][2]的存儲位置分別為644和

676(十進(jìn)制數(shù))，則元素A[3][3]的存儲位置為o

7.一無向圖中,存在一條從頂點(diǎn)u到頂點(diǎn)v的邊，則該圖的鄰接矩陣A中

代表該邊的元素有：若該圖中有e條邊，則圖中所有頂點(diǎn)

的度之和是.

8.T是一個(gè)散列表，H為散列(哈希)函數(shù)。若對于關(guān)鍵字集合中的任意一個(gè)關(guān)

鍵字，經(jīng)散列函數(shù)H映象到地址集合中的任意一個(gè)地址的概率是相等的，則稱此

散列函數(shù)是對兩個(gè)不同的關(guān)鍵碼klWk2,若H(kl)=H(k2),這種

現(xiàn)象稱為.

三、簡答題(每題8分，共40分)

1.設(shè)元素大小按字母順序?qū)Υ?。請從空樹開始，通過依次插入元素(V,A,X,C,

M,P)來構(gòu)造一棵二叉平衡樹。畫出二叉平衡樹的構(gòu)造過程。

2.圖1表示一個(gè)地區(qū)的通訊網(wǎng)，邊表示城市間的通訊線路，邊的權(quán)表示架設(shè)線路

花費(fèi)的代價(jià)，如何選擇能溝通每個(gè)城市且總代價(jià)最省的nT條線路，畫出所有可

能的選擇。

1

52

4.請采用弗洛伊德（Floyd）算法求圖2所示的有向圖的每對頂點(diǎn)之間的最短路

徑。寫出在算法執(zhí)行的每一步上，保存最短路徑長度的二維數(shù)組的值。

5.快速排序被認(rèn)為在已知的排序算法中速度較快的算法.

（1）是否在所有情況下快速排序都優(yōu)于直接插入排序?為什么？

（2）快速排序的最壞和平均情況時(shí)間復(fù)雜度各是多少？

（3）為什么說采用三者取中法選擇劃分（主）元親（即選擇被劃分的集合的最

左，最右和位于（left+right）/2處的三個(gè)元素的中間值作為劃分元素）可改進(jìn)

快速排序的性能？

四、解答題（每題12分，共24分）

1.設(shè)一個(gè)散列表的長度M=7,其下標(biāo)從0到6?，F(xiàn)采用線性探查法解決沖突。

（1）請從空散列表開始，通過依次將下列元素插入散列表中的方式建立散列表。

散列函教采用除留余數(shù)法（取余運(yùn)算）.

13,22,31,55,26,63

（2）對于除留余數(shù)法散列函數(shù)的模M,一般應(yīng)如何選擇。

（3）給出一種從上述散列表中刪除元素的可行且有效的方法，并說明理由。

2.如圖3所示的哈夫曼樹可得到字母F,G,H,I和J的編碼。

（1）設(shè)某字母串經(jīng)編碼后為“011101011101”，譯出原串。

（2）說明哈夫曼編碼和ASCH編碼的異同.

（3）為什么采用哈夫曼編碼？

9

IJ

圖3

五、算法設(shè)計(jì)題（13分）

設(shè)有序表以帶表頭結(jié)點(diǎn)的單鏈表存儲。請?jiān)O(shè)計(jì)一個(gè)函數(shù)（或過程），實(shí)現(xiàn)在該

表中插入一個(gè)新元素的操作。要求插入新元素后仍為有序表。假定每個(gè)結(jié)點(diǎn)有兩

個(gè)域：element（元素）和link（指針），element為整型，link具有指向后繼

結(jié)點(diǎn)的指針類型。要求使用類型說明定義單鏈表結(jié)構(gòu)，并實(shí)現(xiàn)函數(shù)（或過程）。

六、算法設(shè)計(jì)題（18分）

已知一棵完全二叉樹中結(jié)點(diǎn)按層次順序自上而下、自左向右存儲在一維整型

數(shù)組A[l：n]中（設(shè)結(jié)點(diǎn)的值為整數(shù)）。請?jiān)O(shè)計(jì)兩個(gè)函數(shù)（或過程），分別實(shí)現(xiàn)

下列功能。

（1）按層次依次打印完全二叉樹中所有元素，要求對每個(gè)元素以一個(gè)偶對顯示

（X,i）,X為元素值，i為該元親在樹中的層次。如元素X在完全二叉樹中的

層次為2,則該元素應(yīng)顯示為（X,2）o要求設(shè)計(jì)為非遞歸算法。

（2）按中序遍歷次序打印完全二叉樹中各元素，每個(gè)元素仍以上述元素值和層次

的偶對顯示，要求設(shè)計(jì)為遞歸算法。

南京郵電學(xué)院

2005年攻讀碩士學(xué)位研究生入學(xué)考試

數(shù)據(jù)結(jié)構(gòu)試題

一、單選題(每題3分，共30分)

1.設(shè)使用某算法對n個(gè)元素進(jìn)行處理，所需的時(shí)間是T(n)=100nlog2n+200n+2000

則該算法的漸進(jìn)時(shí)間復(fù)雜度為()

A.0(1)B.0(n)C.0(200n)D.0(nlog2n)

2.設(shè)順序表的長度為n,并設(shè)從表中刪除元素的概率相等。則在平均情況下，從

表中刪除一個(gè)元素需要移動的元素個(gè)數(shù)是()

A.(n-l)/2B.n/2C.(n-l)n/2D.(n+l)n/2

3.如果只保存一個(gè)n階對稱矩陣a的下三角元素(含對角線元素)，并采用行主

序存儲在一維數(shù)組b中,(或a[i,j])存于b[k],則對i〈j,下標(biāo)k與i,

j的關(guān)系是()。設(shè)一維數(shù)組和矩陣元素的行列下標(biāo)取值均從0開始。

A.i(i+l)/2+jB.j(j+l)/2+i

C.i(i-l)/2+jD.j(j-l)/2+i

4..一棵三叉樹中，已知度為3的結(jié)點(diǎn)個(gè)數(shù)等于度為2的節(jié)點(diǎn)數(shù)，且樹中葉子結(jié)

點(diǎn)的數(shù)目為13,則度為2的結(jié)點(diǎn)數(shù)目為()

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

5.在基于關(guān)鍵字比較的排序算法中，()算法在最壞情況下的時(shí)間復(fù)雜度

不高于0(nlog2n)

A.冒泡排序B.合并排序C.希爾排序D.快速排序

6.已知一棵由關(guān)鍵字集合｛18,43,27,77,44,36,39｝所構(gòu)造的二叉搜索樹

(也稱為二叉排序樹)，對該樹進(jìn)行中序遍歷得到的節(jié)點(diǎn)序列為()

A.樹形未定，無法確定B.18,43,27,77,44,36,99

C.18,27,36,39,43,44,77D.77,44,43,39,36,27,18

7.一個(gè)索引文件，如果經(jīng)常需要插入和刪除元素，宜采用()做索引。

A.二叉排序樹B.二叉平衡樹C.B-樹D.B+樹

8.均勻的散列函數(shù)應(yīng)當(dāng)使關(guān)鍵字集合中的元素，經(jīng)過散列函數(shù)映射到散列表中

任何位置的概率()

A.相等B.最小C.最大D.一定

9.關(guān)鍵路徑是指AOE(ActivityOnEdge)網(wǎng)中()

A.任意兩頂點(diǎn)間的最長路徑B.任意兩頂點(diǎn)間的最短路徑

C.從源點(diǎn)到匯點(diǎn)的最長路徑D.從源點(diǎn)到匯點(diǎn)的最短路徑

10.堆可以是最大堆，也可以是最小堆。下列序列中()既不是最大堆，也不

是最小堆。

A.(90,85,78,67,56,42,35,24,18)

B.(18,35,56,24,42,78,67,85,90)

C.(90,78,85,56,67,35,42,48,24)

D.(18,35,24,56,42,78,67,85,90)

二、填空題(每題6分，共42分)

1.設(shè)有n個(gè)頂點(diǎn)的有向圖采用鄰接矩陣表示，并保存在三維數(shù)組a中，則求第

i個(gè)頂點(diǎn)自的入度和出度的計(jì)算公式分別是和.

2.設(shè)有20個(gè)元素構(gòu)造二叉平衡樹，其最大和最小高度分別是—和—.

3.某二叉樹結(jié)點(diǎn)的中序序列為A,B,C,D,E,F,G,后序序列為B,D,C,A,F,G,E,則該

二叉樹的先序序列為，該二叉樹對應(yīng)的森林中包括棵樹。

4.對一個(gè)有向圖進(jìn)行拓?fù)渑判?，輸出的拓?fù)湫蛄胁荒馨▓D中全部頂點(diǎn)，表明此

圖。如果此圖代表一個(gè)工程之間的領(lǐng)先關(guān)系，當(dāng)算法執(zhí)行出現(xiàn)上述情況

時(shí)，應(yīng)當(dāng)檢查.

5.設(shè)對主串"bcdbcdcabcdbcdbac"和模式串"bcdbcbd”進(jìn)行KMP模式匹

配.第1趟匹配失敗后，若使用非改進(jìn)的Next函數(shù),則下一趟將由主串的第一字

符與模式串的第字符開始比較開始比較.若采用改進(jìn)的Next函數(shù),則下一

趟匹配將由主串的第一字符與模式串的第字符開始比較。字符串中

字符從1開始編號。

6.假定散列表使用除留余數(shù)法散列函數(shù)H,key為關(guān)鍵字，模為M,則該散列函

數(shù)的形式為o若采用移位折疊法散列函數(shù)，散列地址取3位，設(shè)

key=43256789654,則所得的散列函數(shù)值為。

7.在將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式和計(jì)算后綴表達(dá)式的算法中，都需要使用堆

棧。對于前者，進(jìn)入堆棧的元素為表達(dá)式中的而對于后者，進(jìn)入堆棧的元

素為0中綴表達(dá)式(a+b)/c-(f-d/e)所對應(yīng)的后綴表達(dá)武是.

三、解答題(每題8分，共48分)

1.已知有向圖如圖1所示，并已建成該圖的鄰接表。使用該鄰接表對此圖進(jìn)行深

度優(yōu)先遍歷時(shí)，結(jié)點(diǎn)被訪問的次序是：1,3,2,5,6,4；對其進(jìn)行廣度優(yōu)先遍

歷時(shí)，結(jié)點(diǎn)被訪問的次序是：1,3,2,4,6,50

(1)畫出產(chǎn)生上述遍歷結(jié)果的鄰接表；

(2)分別畫出產(chǎn)生上述遍歷結(jié)果的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。

圖1

2.設(shè)無向圖如圖2所示，現(xiàn)采用克魯斯卡爾算法求最小代價(jià)生成樹。再加入一條

新邊時(shí)，為了判定是否會因此形成回路，可以使用并查集(該數(shù)據(jù)結(jié)構(gòu)也用于求

等價(jià)關(guān)系問題)。

(1)畫出所生成的最小代價(jià)生成樹；

(2)給出在算法執(zhí)行中，當(dāng)生成樹上有5條邊時(shí)的并查集的狀態(tài)。

圖2

3.設(shè)有數(shù)據(jù)元素的有序序列(22,32,35,44,48,51,57,60)

(1)現(xiàn)采用對半查找方法查找60,請按比較的次序，列出與60做比較的表中元

素；

(2)對半查找方法要求元素序列采用何種存儲表示方法。

4.關(guān)于圖3所示的4階B-樹，回答下列問題：

⑴依次插入關(guān)鍵字70和85,畫出插入后的B-樹。

⑵依次刪除關(guān)鍵字14和16,畫出刪除后的B-樹(仍從原圖3中刪除)。

(3)你認(rèn)為用于存儲B-樹中每個(gè)結(jié)點(diǎn)的存儲塊的大小是否應(yīng)相同，為什么？

5.使用快速排序算法對元素序列(23,43,36,30,20,54,76,28)進(jìn)行排序。

(1)寫出對上述序列進(jìn)行第一趟排序后的結(jié)果；

(2)待排序的元素序列處于什么狀態(tài)時(shí)快速排序所需時(shí)間最長

(3)采用什么措施可改善快速排序的最壞情況時(shí)間性能？

6.設(shè)二叉搜索樹如圖4所示

(1)在該樹上插入元素35,畫出插入后的二叉搜索樹

(2)從(1)所生成的樹上刪除25,畫出刪除后的二叉搜索樹。

37

32

圖4

四、算法設(shè)計(jì)題（共30分）

1.（12分）

設(shè)計(jì)一個(gè)算法，按元素值的“非增”次序，打印一棵二叉搜索樹（也稱二叉排

序樹）的元素。設(shè)二叉搜索樹采用二叉鏈表存儲，每個(gè)結(jié)點(diǎn)有三個(gè)域：ichild

rchild,datao算法中，除二叉鏈表中原有的結(jié)點(diǎn)空間外，只允許使用若干指針

變量，不允許使用額外的元素空間。

2.（18分）

已知無向圖采用鄰接矩陣表示，但該鄰接矩陣不使用二維數(shù)組存儲，而今使

用一維數(shù)組g保存鄰接矩陣的下三角部分元素（不含對角線元素）。請?jiān)O(shè)計(jì)一個(gè)

或多個(gè)函數(shù)（或過程），求無向圖的各連通分量的頂點(diǎn)集。

南京郵電大學(xué)

2006年攻讀碩士學(xué)位研究生入學(xué)考試

數(shù)據(jù)結(jié)構(gòu)試題

考生注意：本試卷共4頁。所有答題均寫在答題紙上（包括單選和填空題），請

務(wù)必準(zhǔn)確標(biāo)明所答題的題號和填空號。

一、單選題（每題3分，共30分）

1.可以使用大0記號表示一個(gè)算法的時(shí)間復(fù)雜度。下列標(biāo)識中不正確的是（）

32

A.n'+2n=O（n）B.nlog2n+2n=0（n）

J2

C.n+nlog2n=0（n~log2n）D.n+n1og2n=0（n1og2n）

2.下列術(shù)語中，（）與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)。

A.循環(huán)隊(duì)列B.堆棧C.散列表D.單鏈表

3.設(shè)線性表非空，采用下列（）所描述的鏈表可以在0（1）時(shí)間內(nèi)在表尾插入

—*4*新點(diǎn)O

A.帶表頭泊點(diǎn)的單鏈表，一個(gè)鏈表指針指向表頭結(jié)點(diǎn)

B.帶表頭結(jié)點(diǎn)的單循環(huán)鏈表，一個(gè)鏈表指針指向表頭結(jié)點(diǎn)

C.不帶表頭結(jié)點(diǎn)的單鏈表，一個(gè)鏈表指針指向表的第一個(gè)結(jié)點(diǎn)

D.不帶表頭結(jié)點(diǎn)的單循環(huán)鏈表，一個(gè)鏈表指針指向表的第一個(gè)節(jié)點(diǎn)

4.設(shè)主串為"abceabceyabceabceab",字串為"abceabcea"。則在KMP匹配第

一趟失配后下一趟匹配開始時(shí)，子串指針指示的字符是（）

A.aB.bC.cD.e

5.二叉樹中第5層上的結(jié)點(diǎn)個(gè)數(shù)最多為（）假定根節(jié)點(diǎn)層次為1.

A.8B.15C.16D.32

6.用DFS遍歷一個(gè)有向無環(huán)圖，并在DFS算法退棧這回時(shí)打印當(dāng)前頂點(diǎn)，則輸出

的頂點(diǎn)序列是（）

A.拓?fù)溆行虻腂.無序的

C.逆拓?fù)溆行虻腄.按頂點(diǎn)編號次序的

7.下面（）算法可用于求無向圖的所有連通分量。

A.廣度優(yōu)先遍歷B.拓?fù)渑判?/p>

C.求最短路徑D.求關(guān)鍵路徑

8.設(shè)有以元素10,9,20,6,85,23,21,17為葉結(jié)點(diǎn)的8路合并勝方樹。在

輸出一個(gè)元素后，將有一個(gè)新元素補(bǔ)充到相應(yīng)的葉結(jié)點(diǎn)中。在重構(gòu)的勝方樹中，

應(yīng)有（）個(gè)元素需要修正。

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

9.在一棵二叉搜索樹上搜索一個(gè)元素的平均時(shí)間復(fù)雜度為（）

2

A.0（n）B.0（n）C.O（nlog2n）D.0（log2n）

10.下面關(guān)于倒排文件的說法中正確的是（）

A.倒排文件是對主關(guān)鍵字建立索引的

B.倒排文件是對次關(guān)鍵字建立索引的

C.倒排序文件的優(yōu)點(diǎn)是維護(hù)簡單

D.采用倒排文件是為了節(jié)省存儲空間

二、填空題（每題6分，共48分）

1.設(shè)有二維數(shù)組A[0...5,0...6],從地址Loc（A）開始順序存放，每個(gè)元素占

2個(gè)字節(jié)。元素A[4,4]在行優(yōu)先方式下的存儲地址為,在列優(yōu)先方式

下的存儲地址為o

2.已知一算法表達(dá)式的中綴形式為（A+B）*C-E/D,其后綴形式為

另有一算術(shù)表達(dá)式的后綴形式264-*2/,每個(gè)操作數(shù)均為0至9的一位數(shù)。此表

達(dá)式的值為o

3.使用如圖1所示的哈夫曼樹實(shí)現(xiàn)對字符集｛F,G,H,I,J｝的哈夫曼編碼。已知編

碼后得到的碼文為：011101011101,則利用此哈夫曼樹進(jìn)行譯碼得到的電文為

設(shè)該字符集中各字符的使用頻率各不相同，則其中使用頻率最小的

兩個(gè)字符應(yīng)當(dāng)是o

I

圖1

5.已知對一棵二叉樹的先序和中序遍歷的結(jié)點(diǎn)次序可以唯一確定該二叉樹。設(shè)

某棵二叉樹的先序和中序次序分別為ABCDEFG和BDCAEGF,則其后序次序?yàn)?/p>

0此外已知后序和序遍歷次序也可以唯一確定一棵二叉樹。

6.引入B-樹的最根本原因是-在有n個(gè)元素的m階B-樹中，

搜索一個(gè)元素的算法需要訪問外存的次數(shù)至多為。

7.分別采用直接插入排序和快速排序方法對下面所列出的四個(gè)序列進(jìn)行排序（由

小到大）。使得直接插入排序時(shí)間最長的序列是，使得快速排序時(shí)間最短

的序列是o

A.10,20,30,40,50,60,70

B.70,60,50,40,30,20,10

C.40,10,30,20,60,50,70

D.40,20,10,30,50,70,60

8.數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的存儲結(jié)構(gòu)是指

三、解答題（每題8分，共40分）

1.當(dāng)采用行三元組表存儲稀疏矩陣實(shí)現(xiàn)矩陣快速轉(zhuǎn)置算法時(shí)，需要附設(shè)兩個(gè)一維

數(shù)組，設(shè)為num和k,其中num[col]表示原矩陣第col列中非零元素個(gè)數(shù)?，F(xiàn)有

稀疏矩陣如右圖所示

（1）請給出它的轉(zhuǎn)置前后的行三元組表示的示意圖

（2）計(jì)算數(shù)組num和k的元素值

012000

-1013180

1120000

00000

00-500

00000

2.求解下列關(guān)于散列表的問題

（1）除法（除留余數(shù)法）散列函數(shù)是最常用的一種散列函數(shù)，請寫出散列函數(shù)的

一般形式。

（2）設(shè)有散列表Ht如下，現(xiàn)采用二次探查法解決沖突。已知H（38）=5,H（25）

=13,請將38和25依次插入表中適當(dāng)位置。請?jiān)诖痤}紙上畫出完整的插入兩個(gè)

新元素后的散列表。

012345678910

1314161718

3.已知AOE網(wǎng)如第二題第4小題圖2所示。

（1）計(jì)算每個(gè)頂點(diǎn)代表的事件可能的最早發(fā)生時(shí)間

（2）列出計(jì)算頂點(diǎn)4所代表事件允許的最遲發(fā)生時(shí)間的計(jì)算公式和計(jì)算結(jié)果。

（3）計(jì)算關(guān)鍵路徑長度，并列出關(guān)鍵路徑的頂點(diǎn)序列

4.從空二叉平衡樹開始，依次插入：19,25,43,16,18,220請畫出每插入

一個(gè)元素后的二叉平衡樹、

5.設(shè)有向圖如圖3所示，

（1）畫出鄰接表存儲表示的示意圖;

（2）求它的全部強(qiáng)連通分量

圖3

四、算法設(shè)計(jì)題（共32分）

解題要求：

（1）只允許使用pascal,C和C++語言中的一種語言描述數(shù)據(jù)結(jié)構(gòu)和算法

（2）算法描述中不允許直接調(diào)用教材上以實(shí)現(xiàn)的過程或函數(shù)

（3）要求對算法的每一條語句加明確注釋

1.（14分）設(shè)有n個(gè)元素保存在一維數(shù)組A中。枚舉排序的基本思想是借助于

一個(gè)一維數(shù)組；設(shè)為count。count[k]記錄在初始序列A中，比第k個(gè)元素小的

元素個(gè)數(shù).因此count*］也表明了第k個(gè)元素在有序序列中的位置。請?jiān)O(shè)計(jì)一個(gè)

算法計(jì)算數(shù)組count的值。分析此算法的最壞、最好和平均情況時(shí)間復(fù)雜度。

2.（16分）設(shè)一棵n個(gè)結(jié)點(diǎn)的完全二叉樹采用順序存儲結(jié)構(gòu)，保存在一維數(shù)組A

中。試設(shè)計(jì)一個(gè)遞歸算法，復(fù)制該完全二叉樹，得到一棵新的采用普通二叉鏈表

存儲的二叉樹。二叉鏈表的每個(gè)結(jié)點(diǎn)有三個(gè)域：lchild,rchild和element.算

法返回所構(gòu)造的新二叉樹的根結(jié)點(diǎn)地址。

南京郵電大學(xué)

2007年攻讀碩士學(xué)位研究生入學(xué)考試

數(shù)據(jù)結(jié)構(gòu)試題

考生注意：本試卷共4頁。所有答題均寫在答題紙上（包括判斷題、單選題和

填空題），請務(wù)必準(zhǔn)確表明所答題的題號。

一、判斷題（每題2分，共12分：請答“是”或“否”）

1.算法必須至少有一個(gè)輸入，否則就不能稱為一個(gè)算法。（）

2.設(shè)有一個(gè)堆棧和一個(gè)隊(duì)列?，F(xiàn)有元素序列（A,B,C,D）,依次進(jìn)棧，進(jìn)棧中允

許出棧，出棧的元素被加入隊(duì)列。那么從隊(duì)列輸出的元素序列可以是（D,C,B,A）。

（）

2.循環(huán)隊(duì)列是一種鏈?zhǔn)疥?duì)列。（）

4.一棵二叉樹中，必須有一個(gè)根結(jié)點(diǎn)。其余結(jié)點(diǎn)分屬于左右兩棵子二叉樹。（）

6.散列表在元素的存儲位置和它的關(guān)鍵字之間建立了一個(gè)確定的函數(shù)關(guān)系，所

以

無論是否表中存在同義詞，在查找記錄時(shí)，只需計(jì)算地址，而無需作關(guān)鍵字間

的比較。（）

6.在勝方樹上輸出一個(gè)結(jié)點(diǎn)后，從根在該結(jié)點(diǎn)的路徑上所有結(jié)點(diǎn)都必須更新。（）

二、單選題（每題3分，共30分）

1.現(xiàn)實(shí)生活中具有譜系結(jié)構(gòu)的數(shù)據(jù)，在計(jì)算機(jī)中處理時(shí)一般采用（）結(jié)構(gòu)表示。

A.線性B.樹C.圖D.集合

2.設(shè)后綴表達(dá)式為：“43*293/+2-/"，式中，每個(gè)操作數(shù)均為一位整數(shù)，則表達(dá)

式的值為

A.6B,4C.8D.A,B,C三者都不是

3.設(shè)二叉樹根結(jié)點(diǎn)的層次為1。在所有含135個(gè)結(jié)點(diǎn)的二叉樹中，最小高度是（）

A.6B.7C.8D.9

4.設(shè)A、X和Y是二叉樹B中的三個(gè)結(jié)點(diǎn)，X是A的左孩子，Y是X的左孩子。T

是與B對應(yīng)的樹：在T中，A是丫的()

A.孩子B.兄弟C.雙親D.祖先(非雙親)

5.下面哪一種結(jié)構(gòu)必定是完全二叉樹()

A.哈夫曼樹B.二叉搜索樹C.AVL搜索樹D.堆

6.在有序表(10,20,30,40,50,60,70,80,90)中以對半搜索法查元素30

和45時(shí)，所需的關(guān)鍵字值間的比較次數(shù)分別為()

A.3,3B.3,4C,4,4D.A,B,C三者都不是

7.假定從無向圖G的任何一個(gè)項(xiàng)點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索，都可以訪問圖中

每個(gè)頂點(diǎn)，則該圖一定是()

A.連通圖B.完全圖C.有回路的圖D.一棵樹

8.用DFS遍歷一個(gè)無環(huán)有向圖，并在DFS算法退棧返回時(shí)打印相應(yīng)的頂點(diǎn)，則輸

出的頂點(diǎn)序列是()

A.逆拓?fù)溆行駼.拓?fù)溆行駽.無序的D.按關(guān)鍵字有序

9.初始序列經(jīng)第一趟排序后，不能確定任何一個(gè)元素最終位置的排序算法是()

A.兩路合并排序B.冒泡排序C.快速排序D.簡單選擇排序

10.快速排序和冒泡排序的最壞情況時(shí)間復(fù)雜度分別為()

A.0(nlog2n),0(nlog2n)B.o(nlog2n),0(n2)

C.O(n'),0(nlog2n)D.0(n2),0(n2)

三、填空題(每題6分，共30分)

1.已知三維整型數(shù)組A,其維數(shù)為:A[4][5][6]或A[0..3,0..4,0..5](pascal),

每個(gè)元素2個(gè)單元，按行優(yōu)先(即最右下標(biāo)變化最快)的次序存儲?，F(xiàn)已知

A[3][4][5](A[3,4,5])在內(nèi)存中的地址是238,則三維數(shù)組為A[0][0][0]的地址

是,A[2][3][3]的地址是.

2.設(shè)有模式串p="abscdabscdxab”，若采用簡單匹配算法，則當(dāng)匹配在字符x

處失敗時(shí)，則下一趟匹配從串p的第一字符開始。若采用KMP算法，則下一趟

匹配從串的第位字符開始。

3.設(shè)散列表如圖1,X代表該位置處已經(jīng)存儲了元素，現(xiàn)在表中插入新元素y,

設(shè)h(y)=7。若此表是線性探查法散列表，則y應(yīng)插入下標(biāo)為的位置處。若

此表是二次探查法散列表，則y應(yīng)插入下標(biāo)為的位置處。

0123456789101112

XXXXXXXXX

4.已知某二叉樹的中序遍歷序列是becad,后序遍歷序列是ecbda,它的先序遍

歷序序列是此二叉樹上葉子結(jié)點(diǎn)有。

5.迪杰斯特拉算法用于求解最短路徑問題，它按次序

逐一產(chǎn)生最短路徑。

四、解答題(每題8分，共48分)

1.設(shè)有對字符集｛A,B,C,D,E｝的哈夫曼編碼為:A：OO,B:ObC:10,D：110,

E:lllo

(1)畫出該拿哈夫曼樹；

(2)已知電文：ADCEB,求編碼得到的碼文；

(3)已知碼文：010011011111110,求譯碼得到的電文。

2.給定關(guān)鍵字集合｛40,30,50,60,70,10,20,80｝。

(1)求以該集合元素所構(gòu)造的二叉搜索樹的最小和最大高度(設(shè)根結(jié)點(diǎn)的層次為

Do

(2)從空樹出發(fā),依次插入序列(40,30,50,60,70,10,20,80)中元素構(gòu)造一個(gè)

二叉樹。畫出該樹。

(3)給定無序序列(40,30,50,60,70,10,20,80)，構(gòu)造一個(gè)min堆。畫出該堆。

3.二叉搜索樹和堆是兩種特殊的二叉樹。

(1)給定一棵n個(gè)結(jié)點(diǎn)的二叉搜索樹，通過什么途徑可以產(chǎn)生元素的有序序列，

其時(shí)間復(fù)雜度是多少？

(2)給定一個(gè)n個(gè)結(jié)點(diǎn)的堆，通過什么途徑可以產(chǎn)生元素的有序序列，其時(shí)間復(fù)

雜度是多少？

4.設(shè)有向圖如圖2所示，

(1)給出此圖的所有強(qiáng)連通分量。

(2)畫出此圖從頂點(diǎn)A開始的深度優(yōu)先遍歷生成森林。

(3)畫出此圖從頂點(diǎn)A開始的廣度優(yōu)先遍生成森林。

圖2

5.設(shè)無向圖如圖3所示，

(1)畫出以A為源點(diǎn)，普里姆算法得到的最小代價(jià)生成樹。

(2)如果對每條邊的權(quán)值增加相同的正數(shù),則得到的最小代價(jià)生成樹是否與原

樹結(jié)構(gòu)相同？說明你的理由。

4階B-樹。

(2)從(1)所建成的B-樹上依次刪除:99,75,31,50,畫出刪除后的B-樹。

五、算法設(shè)計(jì)題(共30分)

解題要求：

⑴只允許使用pascal,C和C++語言中的一種語言描述本題中的算法。

(2)算法描述中不允許直接調(diào)用教材上已實(shí)現(xiàn)的過程或函數(shù)。

(3)要求對程序加上足以說明算法設(shè)計(jì)思想的明確注釋。

1.設(shè)G(V,E)是一個(gè)無向連通圖。如果頂點(diǎn)集V被分成兩個(gè)互不相交的子集，并

且圖中任意一條邊所關(guān)聯(lián)的兩個(gè)頂點(diǎn)分屬于兩個(gè)不同的子集。這樣的圖被稱為二

部圖?？梢栽O(shè)計(jì)一個(gè)算法來判定任意給定的一個(gè)無向圖是否二部圖。提示：一個(gè)

二部圖可以僅使用兩種顏色對圖中頂點(diǎn)著色(即為每個(gè)頂點(diǎn)分配一神顏色)，并

且保證每一條邊的兩個(gè)端點(diǎn)分配不同顏色?？梢圆捎蒙疃葍?yōu)先搜索圖的做法來實(shí)

現(xiàn)這一判定算法。無向連通圖采用鄰接矩陣存修。本題要求設(shè)計(jì)如下兩個(gè)算法并

分析算法的時(shí)間和空間復(fù)雜度：

(1)寫出深度優(yōu)先遍歷無向連通圖的算法，分析算法的時(shí)間和空間復(fù)雜度。

(2)寫出采用深度優(yōu)先搜索圖的思想判定任意給定一個(gè)無向連通圖是否二部圖

的算法，分析算法的時(shí)間和空間復(fù)雜度。

2.請?jiān)O(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)只包括下列三個(gè)運(yùn)算：

Create():創(chuàng)建一個(gè)數(shù)據(jù)結(jié)構(gòu)

Insert(x):插入一個(gè)元素x到該數(shù)據(jù)結(jié)構(gòu)

Min():返回該數(shù)據(jù)結(jié)構(gòu)中的最小元素

本題要求：

(1)描述你所設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)：

(2)用所選程序設(shè)計(jì)語言實(shí)現(xiàn)這三個(gè)運(yùn)