杭州電子科技大學(xué)數(shù)據(jù)結(jié)構(gòu)2011-2019年考研專業(yè)課真題

杭州電子科技大學(xué)

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

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

(試題共五大題，共6頁，總分150分)

姓名報考專業(yè)準(zhǔn)考證號

【所有答案必須寫在答題紙上，做在試卷或草稿紙上無效！】

一、判斷題(本大題共10小題，每小題1分，本大題共10分)

1.數(shù)據(jù)的邏輯結(jié)構(gòu)說明數(shù)據(jù)元素之間的順序關(guān)系，它依賴于計算機的存儲結(jié)構(gòu)。()

2.對任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。()

3.循環(huán)隊列通常用指針來實現(xiàn)隊列的頭尾相接。()

4.若棧的入棧序列為】,2,3,4,5,6,則其出棧序列可以是325,6,1,4.()

5.用鄰接矩陣法存儲一個圖所需的存儲單元數(shù)目與圖的邊數(shù)有關(guān)。()

6.取廣義表的表尾就是返回廣義表中最后一個元素。()

7.稀疏矩陣壓縮存儲后，必會失去隨機存取功能。()

8.關(guān)鍵路徑是AOE網(wǎng)中從源點到終點的最長路徑。()

9,對一棵二叉樹進行層次遍歷時，應(yīng)借助于一個棧。()

10.在用弗洛伊德算法求解各頂點的最短路徑時，每個表示兩點間路徑的

path"i[I,J]一定是pathk[IJ的子集(k=l,2,3,….n)。()

二、單項選擇題(本大題共15小題，每小題2分，本大題共30分)

1.從邏輯上.可以把數(shù)據(jù)結(jié)構(gòu)分為()大類

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

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

2.在一個二維數(shù)組A中，假設(shè)每個數(shù)組元素在長度為3個存儲單元，行下標(biāo)i

為0-8,列下標(biāo)j為。?9,從首地址SA開始連續(xù)存放。在這種情況下，元素

A[8][5]的起始地址為()

A.SA+141B.SA+144C.SA+222D.SA+255

3.在雙向鏈表指針p的結(jié)點前插入一個指針q的結(jié)點操作是()

A.p->Llink=q;q->Rlink=p;p->Llink->Rlink=q:q->Llink=q;

B.p->Llink=q;p->Llink->Rlink=q;q->RIink=p;q->Llink=p->Llink;

C.q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;

D.q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;

4.在一個長為n的順序表中刪除第i個元素和第i個位置插入一個元素的時間復(fù)

雜度為()

A.nB.i-1C.n-iD.n-i+1

第I頁共6頁

5.對于一個頭指針為head的帶頭結(jié)點的單鏈表，判定該表為空表的條件是

（）

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

6.一個棧的輸入序列為1,2,3,…,n,若輸出序列的第一個元素是n,輸出第i

（l<=i<=n）個元素是（）

A.不確定B.n-i+1C.iD.n-i

7.設(shè)表頭不帶頭結(jié)點且所有操作均在表頭進行，則下列最不適合作為鏈棧的是

（）

A.只有表頭結(jié)點指針，沒有表尾指針的雙向循環(huán)鏈表

B.只有表尾結(jié)點指針，沒有表頭指針的雙向循環(huán)鏈表

C.只有表頭結(jié)點指針，沒有表尾指針的單向循環(huán)鏈表

D.只有表尾結(jié)點指針，沒有表頭指針的單向循環(huán)鏈表

8.若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間top[i]代表第i個棧（i

=1,2）棧頂，棧1的底在V[l],棧2的底在V[m],則棧滿的條件是（）?

A.|top[2]-top[l]|=0B.top[l]+l=top[2]

C.top[l]+top[2]=mD.top[lj=top[2]

9.表達(dá)式a*（b+c）-d的后綴表達(dá)式是（）

A.abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd

10.已知操作符包括"*"、ur\"（"和"）將中綴表達(dá)式a+b-a*（（c+d）/e-f）+g

轉(zhuǎn)換為等價的后綴表達(dá)式ab+acd+e/f-*-g+時，用棧來存放哲時還不能確定運算次

序的操作符。若棧初始時為空，則轉(zhuǎn)換過程中同時保存在棧中的操作符的最大個

數(shù)是（）

A.5B.7C.8D.11

11.若將關(guān)鍵字1,2,3,4,5,6,7依次插入到初始為空的平衡二叉樹r中，則r

中平衡因子為0的分支結(jié)點的個數(shù)是（）.

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

12.設(shè)無向圖G=（V,E）和G，=（V，，E）如果G，是G的生成樹，則下面說法中錯誤的是

（）

A.G，是G的子圖B.G，是G的連通分量

C.G，是G的極小連通子圖且V=V，D.G，是G的一個無環(huán)子圖

13.設(shè)給定權(quán)值總數(shù)有n個，其哈夫曼樹的結(jié)點總數(shù)為（）

A.不確定B.2nC.2n+lD.2n-l

14.用相鄰矩陣A表示圖，判定任意兩個頂點Vi和Vj之間是否有長度為m的

路徑相連，則只要檢查（）的第i行第j列的元素是否為零即可。

A.mAB.AC.AmD.Am-1

第2頁共6貞

15.下圖中給出由7個頂點組成的無向圖。從頂點1出發(fā)，對它進行深度優(yōu)先遍

歷得到的序列可能是（）

A.1354267B.1347652C.1534276D.1247653

三、填空題（本大題共15小題，每小題2分，本大題共30分）

1.N個頂點的連通圖的生成樹含有條邊。

2.假定有K個關(guān)鍵字互為同義詞，著用線性探測法把這K個關(guān)鍵字填入散列表

中，至少要進行次探測。

3.對序列｛98.36,-9,0,47,23,1,8,10.7｝采用增量為4的希爾排序，第一趟的排序結(jié)

果是0

4,一組記錄的關(guān)鍵碼是（46,79,56,38,40,84）,以第一個記錄為基準(zhǔn)，從

小到大得到的快速排序第一次劃分結(jié)果是o

5.對數(shù)據(jù)序列（8,9,10,4,5,6,20,1,2）采用冒泡排序（從后向前升序

進行），需要進行趟完成排序。

6.若一棵完全二叉樹有768個結(jié)點，則該二叉樹中葉結(jié)點的個數(shù)是o

7,已知一棵二叉樹的層序排列是ABCDEF,中序序列為BADCFE,則先序序列

為。

8.下圖中的強連通分量的個數(shù)為_____個。

第3頁共6頁

9.已知字符集缶力凡(1?￡&11},若各字符的哈夫曼編碼依次是0100,10,0000,

0101,001,011,11,0001,則編碼序列0100011001001011110101的譯碼結(jié)果

是。

10.使用迪杰斯特拉(Dijkstra)算法求下圖中從頂點1到其他各頂點的最短路徑,

依次得到的各最短路徑的目標(biāo)頂點是。

11.對于一個非連通無向圖.共有28條邊,則該圖至少有個頂點。

12.n個頂點的無向圖的鄰接表最多有個表結(jié)點。

13.對n階對稱矩陣壓縮存儲時，需要表長為的順序表。

14.若無向圖G=(V,E)中含有7個頂點，要保證G在任何情況下都是連通的.則需要

的邊數(shù)最少是條。

15.對下圖進行拓?fù)渑判?，可以得到不同的拓?fù)湫蛄械膫€數(shù)是。

第4頁共6頁

四、簡答題(本大題共5小題，每小題8分，本大題共40分)

1.某帶權(quán)有向圖及其鄰接表如F：

(1)寫出從A點開始深度優(yōu)先的訪問序列(鄰接邊的順序按鄰接表鏈表順序);

(2)畫出深度優(yōu)先生成樹；

(3)該圖為AOE網(wǎng)絡(luò)，求頂點C的最早發(fā)生時間和及活動FC的最晚開始時間。

2.將關(guān)鍵字序列(7,8,30,11,18,9,14)散列存儲到散列表中，散列表的

存儲空間是一個下標(biāo)從0開始的一位數(shù)組，散列函數(shù)為：H(key)=(key*3)

MOD7,處理沖突采用線性探測再散列法，要求裝填因子為0.7。

(1)請畫出所構(gòu)造的散列表。

(2)分別計算等概率情況下，查找成功和查找不成功的平均杳找長度。

3.設(shè)圖G=(V,E)以鄰接表存儲，如圖所示，畫出其鄰接矩陣以及圖G。

4.設(shè)計一個算法，求出指定結(jié)點在給定二叉排序樹中的層次。

節(jié)點結(jié)構(gòu)：

structTree

(

intdata;

structTree*left;

structTree*right;

);

intfindLevel(Treeroot,intdata)

第5頁共6頁

5.給定一個二叉樹和其中的一個結(jié)點，請找出中序遍歷順序中該節(jié)點的下一個

結(jié)點并且返回。注意，樹中的結(jié)點不僅包含左右子結(jié)點，同時包含指向父結(jié)點的

指針。

節(jié)點結(jié)構(gòu)如下：

structTreeLinkNode{

intval;

structTreeLinkNode*left;

structTreeLinkNode*right;

structTreeLinkNode*next;

TreeLinkNode(intx):val(x),Ieft(NULL),right(NULL),next(NULL){

}

};

TreeLinkNode*GetNext(TreeLinkNode*pNode)

五、程序題(本大題共4小題，每小題10分，本大題共40分)

1.編寫算法，實現(xiàn)在單向鏈表上刪除具有重復(fù)值的多余節(jié)點，使得表中每個節(jié)

點的數(shù)值均保持不同。

2.假設(shè)?個算數(shù)表達(dá)式中包括圓括號()，方括號[],和花括號{},編寫?個算法

來判別表達(dá)式中的括號是否配對，以字符'\0’作為算數(shù)表達(dá)式的結(jié)束符

boolBracketsCheck(char*str)

3.已知圖的鄰接矩陣的存儲結(jié)構(gòu)說明為:

TypedefStruct{

intvertex[m];

intedge[m];}gadjmatrix;

圖的鄰接表的存儲結(jié)構(gòu)說明為

TypedefStructnodel{

intinfo;

intadjvertex;

structnodel*nextarc;}glinklistnode;

TypedefStructnode2{

intvertexinto;

glinklistnode*firstarc;}glinkheadnode:

請設(shè)計計算法MatToList,將無向圖的鄰接矩陣轉(zhuǎn)為對應(yīng)的鄰接表。

voidMatToList(gadjmatrixgl[],glinkheadnodeg2[]){

}

4.在n個元素中，找出第k大的元素，用C語言寫出數(shù)據(jù)結(jié)構(gòu)，設(shè)計算法實現(xiàn)

上述要求，并分析時間復(fù)雜性，最好是平均時間復(fù)雜性為O(n).

第6頁共6頁

杭州電子科技大學(xué)

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

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

(試題共五大題，共5頁，總分150分)

姓名報考專業(yè)_____________準(zhǔn)考證號

【所有答案必須寫在答題紙上，做在試卷或草稿紙上無效！】

一、判斷題(本大題共10小題，每小題2分，本大題共20分)

1.數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關(guān)系。()

2.單鏈表中設(shè)置的頭結(jié)點只具有標(biāo)識的作用。()

3.隊列是一種能分別在表的兩端進行插入與刪除操作的線性表結(jié)構(gòu)，具有先進后

出的特性。()

4.采用順序存儲方式存儲，兩個棧共享個存儲區(qū)V[0..maxsizcT],為提高空

間利用率，減少溢出的可能，應(yīng)把兩個棧的棧底分別設(shè)在向量空間的兩端。()

5.哈夫曼樹是帶權(quán)路徑長度最短的樹，帶權(quán)路徑長度等于所有結(jié)點的權(quán)值之和。

()

6.一顆有n個結(jié)點的二叉樹，采用鏈衣(Uink-rlink)存儲結(jié)構(gòu)，則樹中共有

n+1個空指針.()

7.強連通分量是無向圖的極大強連通了?圖。()

8.有向圖和無向圖可以采用鄰接矩陣存儲，但帶權(quán)的有向圖和無向圖，不能采用

鄰接矩陣存儲，只能使用鄰接衣存儲。()

9.設(shè)T為一棵二叉平衡樹，向樹中插入一個結(jié)點n,然后立即刪除該結(jié)點，則不

會破壞樹的結(jié)構(gòu)。()

10.歸并排序在任何情況卜,都比所有簡單排序速度快。＜)

二、單項選擇題(本大題共10小題，每小題2分，本大題共20分)

1.下面關(guān)于算法說法正確的是().

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

第I貞大5頁

B.算法是對特定問題求解步驟的描述，是指令的有限序列，其中每一條指令表

示一個操作.

C.算法的可行性是指指令不能有二義性

D.以上幾個都是錯誤的

2.下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點？（）。

A.存儲密度大B.插入運算方便

C.刪除運算方便D.可方便地用于各種邏輯結(jié)構(gòu)的存儲表示

3.設(shè)1、2、…、n-Kn共n個數(shù)按順序入棧，若第一個出棧的元素是n,則

第三個出棧的元素是

A.3B.n-2C.n-3D.任何元素均可能

4.若一棵二叉樹具有7個度為2的結(jié)點，6個度為1的結(jié)點，則度為。的結(jié)點個

數(shù)是（）。

A.9B.8C.15D.不確定

5.一棵二叉樹的前序遍歷序列為ABCDEFG,它的中序遍歷序列可能是（）.

A.CABDEFGB.ABCDEFGC.DACEFBGD.ADCFEG

6.連通一個n個頂點的無向圖，其邊的個數(shù)至少為（）,如果是有向圖則邊

數(shù)至少為（）.

A.n-1,nB.n,n-lC.n*2-l,n*2D.n,n+1

7.已知有向圖G=（V,E）,其中V=（V1,V2,V3,V4,V5,V6,V7,V8},

E=?V1,V2>,<V1,V4>,<V2,V7>,<V4,V7>,<V7,V8>,<V3,V4>,<V3,V5>,<V4,V6>,<V

5,V6>},下列哪個序列不是G的拓?fù)溆行蛐蛄校ǎ?

A.V1,V2,V3.V4,V5,V6,V7,V8B,V3,VI,V2,V4,V5,V6,V7,V8

C.V1,V3,V2,V4,V5,V6,V7,V8D.VI,V3,V4,V2,V5,V6,V7,V8

8.對線性表進行折半查找，表中元素的存儲方式及元素排列要求為（）.

A.鏈接方式存儲，元素?zé)o序B.鏈接方式存儲，元素有序

C.順序方式存儲，元素?zé)o序D,順序方式存儲，元素有序

9.設(shè)哈希表長為15,哈希函數(shù)是H（key）=key%13,表中已有數(shù)據(jù)的關(guān)鍵字為15,

22,50,13,20,36,28,現(xiàn)要將關(guān)鍵字為48的結(jié)點加到表中，用二次探測再

散列法解決沖突，則放入的位置是（）.

第2頁共5頁

A.8B.3C.5D.9

10.對序列｛16,8,6,7,21,-2,4｝進行排序，進行一趟后數(shù)據(jù)的排列變?yōu)?4,

8,-2,7,21,6,16)：則采用的是()排序.

A.選擇B.快速C.希爾D.冒泡

三、填空題(本大題共15空，每空2分，本大題共30分)

1.元素總數(shù)基本穩(wěn)定的線性表，采用存儲結(jié)構(gòu)，能在很少進行插入和刪

除操作的情況下，以最快的速度存取表中元素.

2.長度為n的列表，被等分為n/k段，每段長度為k,不同段之間的元素不存在

逆序。對該列表進行插入排序的最壞時間復(fù)雜度為。

3.順序棧用data[l..n]存儲數(shù)據(jù)，棧頂指針是top,則值為x的元素入棧的操作

是.

4.樹在計算機內(nèi)的表示方式有一(1)_,_(2)_,_(3)_。

5.一棵度為m的樹有n個節(jié)點。若每個節(jié)點直接用m個鏈指向相應(yīng)的兒子，則

表示這個樹所需要的總空間是n*(m+l)(假定每個鏈以及表示節(jié)點的數(shù)據(jù)域都是

一個單位空間).當(dāng)采用兒子/兄弟(FirstChild/NextSibling)表示法時，所

需的總空間是.

6.設(shè)深度為d(只有一個根結(jié)點時，d為1)的二叉樹只有度為。和2的結(jié)點，

則此類二叉樹的結(jié)點數(shù)至少為.

7.如果一個完全二叉樹最底下一層為第六層(根為第一層)且該層共有8個葉結(jié)

點，那么該完全二叉樹共有一個結(jié)點。

8.G是一個非連通無向圖，共有30條邊，則該圖至少有個頂點.

9.Dijkstra短路徑算法從源點到其余各頂點的短路徑的路徑長度按次序

依次產(chǎn)生，該算法弧上的權(quán)出現(xiàn)情況時，不能正確產(chǎn)生最短路徑.

10.在一個大小為K的空散列表中，按照線性探測沖突解決策略連續(xù)插入散列值

相同的N個元素(N<K).問：此時，該散列表的平均成功查找次數(shù)是.

11.設(shè)用希爾排序?qū)?shù)組｛97,35,-10,0,48,22,1,8,9,7)進行排序，給

出的步長(也稱增量序列)依次是4,2,1則排序需趟，寫出第一趟

結(jié)束后，數(shù)組中數(shù)據(jù)的排列次序.

第3頁共5頁

四、簡答題（本大題共5題，本大題共40分）

1.（本題5分）斐波那契數(shù)列Fn定義如下:FO=O,Fl=l,Fn=Fn-l+Fn-2,

n=2,3...,如果用大0表示法，試給出遞歸計算Fn時遞歸函數(shù)的時間復(fù)雜度是

多少.

2.（本題8分）假設(shè)一棵二叉樹的層次次序（按層次遞增順序排列，同一層次自

左向右）為ECRAHXMS,中序序列為ACEHMRSXo請畫出該二叉樹，并將其轉(zhuǎn)換為

對應(yīng)的森林。

3.（本題8分）下圖是帶權(quán)的有向圖G的鄰接表表示法，求：

（1）以結(jié)點VI出發(fā)深度遍歷圖G所得的結(jié)點序列；

（2）從結(jié)點VI到結(jié)點V8的最短路徑；

4.（本題10分）對輸入關(guān)鍵字序列501,89,513,60,906,170,879,245,

653.460進行：

（1）建立堆排序的初始堆（小頂堆），要求畫出主要過程.

（2）輸出最小值后，如何得到次小值?（并畫出相應(yīng)結(jié)果圖）

5.（本題9分）設(shè)一組數(shù)據(jù)為{1,13,27,30,56,70,9,12,23},現(xiàn)采用的哈希函數(shù)

是H（key）=keyM0D13,即關(guān)鍵字對13取模，沖突用鏈地址法解決，設(shè)哈希表

的大小為13（0..12）,試畫出插入上述數(shù)據(jù)后的哈希表。

第4頁共5頁

五、程序題（本大題共3題，本大題共40分）

L（本題10分）設(shè)單鏈表的表頭指針為h,結(jié)點結(jié)構(gòu)由data和next兩個域構(gòu)

成，其中data域為字符型。寫出算法dc（h,n）,判斷該鏈表的前n個字符是否中

心對稱。例如xyx,xyyx都是中心對稱。

2.（本題15分）在二叉樹中查找值為x的結(jié)點，試編寫算法（用C語言）打印

值為x的結(jié)點的所有祖先，假設(shè)值為x的結(jié)點不多于一個，后試分析該算法的

時間復(fù)雜度。

3.（本題15分）設(shè)有順序n個盒子，每個盒子有一個小球，每個小球的顏色是

紅，白，藍(lán)之一。要求重新安排這些小球，使得所有紅色小球在前，所有白色小球

居中，所有藍(lán)色小球居后，重新安排時對每個小球的顏色只能看一次，并且只允

許交換操作來調(diào)整小球的位置。

第5頁共5頁

/

杭州電子科技大學(xué)

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

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

(試題共五大題，5頁，150分)

姓名報考專業(yè)_______________準(zhǔn)考證號

【所有答案必須寫在答題紙上，做在試卷或草稿紙上無效！】

一、選擇題(每小空2分，共28分)

1.在下列數(shù)據(jù)結(jié)構(gòu)中具有先進先出特性，具有先進后出特性.

a：線性表b：棧c：隊列d：串

2.如下關(guān)于串的陳述中，正確的是、.

a：串是數(shù)據(jù)元素類型特殊的線性表b：串中的元素是字母

c：串中若干個元素構(gòu)成的子序列稱為子串d：空串即為空格串

3.對廣義表A=(((a),(b)),((c)))

執(zhí)行操作gettail(gethead(gettail(A)))的結(jié)果是：.

執(zhí)行操作gethead(gettail(gethead(A)))的結(jié)果是：.

a：()b：(())c：(a)d：(b)e：(c)

4.任何一個連通網(wǎng)的最小生成樹.

a：只有一棵b:有一棵或多棵c:一定有多棵d:可能不存在

5.在有n個結(jié)點的二叉樹的三叉鏈表表示中，空指針數(shù)為.

a:不確定b:nc:n+1d:n+2

6.關(guān)鍵路徑是指在只有一個源點和一個匯點的有向無環(huán)網(wǎng)中源點至匯點

的路徑.

a:弧的數(shù)目最多b:弧的數(shù)目懶少c:權(quán)值之和最大d:權(quán)值之和最小

7.設(shè)無向圖6=(丫鵬)和6=(V\E),若G,是G的生成樹，

則下面不正確的說法是..

a:G.是G的子圖b:G,是G的連通分量-

c:G是G的無環(huán)子圖d:G,是G的極小連通子圖且V'=V

8.下列查找方法中適用于查找單鏈表.

a:順序查找b:折半查找c:分塊查找d:hash查找

9.卜.列排序方法中，是穩(wěn)定的；具有最好的平均性能：當(dāng)恃排

序序列的關(guān)鍵字次序為倒序時，若需為之進行正序排序，下列方案中以

為佳.

a:堆排序b:快速排序c:直接插入排序d:簡單選擇排序

第I頁共5頁

二、填空題(每空2分，共26分)

1.數(shù)據(jù)結(jié)構(gòu)通常有下列4類基本結(jié)構(gòu)：線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖型結(jié)構(gòu)、.

2.線性表的存儲結(jié)構(gòu)是以物理位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系的.

而線性表的存儲結(jié)構(gòu)是通過指針保持?jǐn)?shù)據(jù)元素之間的邏輯關(guān)系的.

3.n個頂點的強連通圖至少有條狐，至多有條狐。

4.若某一二叉樹按中序遍歷可得到有■序序列，則該二叉樹是.若某一二又

樹從根結(jié)點到其它任一結(jié)點的路徑上所經(jīng)過的結(jié)點序列按其關(guān)鍵字遞增有序，

則該二叉樹是.

5,若對完全二叉樹中的結(jié)點從1開始按層進行編號，設(shè)最人編號為n,則編號為i

的結(jié)點(1。9)的父結(jié)點編號為；所有編號的結(jié)點為葉子結(jié)點?

6.壓棧次序為a、b、c,則不可能得到的輸出序列是.

7.已知特排序序列為：33,34,7,28,38,11.65,15.37,20.則：

以第一個元素為樞軸的快速排序一趟分劃的結(jié)果是?

堆排序初始建堆(小頂堆)的結(jié)果是.

希爾排序第一越(增量為3)的結(jié)果是.

三、圖示結(jié)構(gòu)題(每小題8分，共40分)

I,已知某二叉樹的先序遍歷次序為：ABCDEFG.中序遍歷次序為：BADCFEG.

(1)畫出該二叉樹形.

(2)給出該二叉樹的后序遍歷次序.

(3)畫出中序線索化后的二叉樹形.c

2.已知某無向圖如右圖所示：

(1)畫出該圖的鄰接表存儲結(jié)構(gòu).(VW-V/T)

(2)畫出該圖的鄰接矩陣存儲結(jié)構(gòu)。只)

(3)根據(jù)你所繪制的鄰接表給出DFS

及BFS次序.

3.依序?qū)㈥P(guān)鍵字20、40、30、80、70、50、60、10插入到一棵2-3樹中(初始狀

態(tài)為空)，

(1)請畫出該B-樹.

(2)再先后刪除關(guān)鍵字40、60.畫出刪除后的B-樹。

4,設(shè)哈希函數(shù)為H(key)=keymod7,用鏈地址法處理沖突，若依次在哈希表中插入

12個元素32、65、83、25、74、21、33、18、61、27,47、28.

(1)畫出它們在表中的分布情形.

(2)計算其平均成功的查找長度.

5.假設(shè)用于通訊的電文僅由8個字符A、B、C、D、E、F、G、II組成，字符在電文

中出現(xiàn)的頻率分別為3、12、9,23、2,17,21、13

(1)畫出你所建的哈夫曼樹，

(2)給出每一字符的哈夫曼編碼.

笫2頁共5頁

四、閱讀以下函數(shù)，指出算法的功能(每小題6分，共36分)

1.StatusAl(SqListL,ElemTypecur_e,ElcmType&next_e)

{//初始條件：順序線性表L已存在

inti=l;

ElemType*p=L.elem;

while(i<L.length&&*p?=cur_e){

if

p++：

)

if(i=L.length)

returnINFEASIBLE;

else{

next_e=*++p;

returnOK;

)

)

2.StatusA2(LinkListL,inti,ElemTypee)

(〃初始條件：帶頭結(jié)點的單鏈表L已存在

intj=0：

LinkListp=L,s;

whi1e(p&&j<i-1){

p=p->next;

j++：

)

if(!pIIj>i-1)

returnERROR：

s=(LinkList)malloc(sizeof(LNode)):

s->data=e;

s->next=p->next;

p->next=s;

returnOK：

)

3.intA3(LinkQueueQ)

I//初始條件：鏈隊列Q已存在

inti=0;

QueuePtrp：

P=Q.front;

第3頁共5頁

while(Q.rear!=p){

i++：

p=p->next;

)

returni;

}

4.voidA4(BiTreeT,Status(*Visit)(TElemType))

{//初始條件：二叉樹T已存在

if(T){

A4(T->lchiId,Visit);

A4(T->rchild,Visit):

Visit(T->data);

)

5.intA5(SSTableST,KeyTypckey)

(〃初始條件:順序表ST已存在

inti;

ST.elem[0].kcy=key;

for(i=ST.length;!EQ(ST.elem[i].key,key)：—i);

returni;

)

6.intA6(SqListL,inti)

{〃初始條件:順序表L已存在

intmin：

intj,k;

k=i;

min=L.r[i].key;

for(j=i+1;j<=L.length;j++)

if(L.r[j].key<min){

k=j;

min=L.r[j].key;

)

returnk：

笫4頁共5頁

五、算法設(shè)計題(每小題10分，共20分)

I.設(shè)單鏈表結(jié)點結(jié)構(gòu)為：

typedefstructLNode{

intdata;

structLnode*next：

)*LinkList;

寫一函數(shù)voidA7(LinkListL)

試采用直接插入排序的方法將單鏈表4(帶頭結(jié)點)中的結(jié)點按非遞減次序排列。

2.設(shè)二叉鏈表結(jié)構(gòu)為：

typedefstructBiTNode{

TElernTypedata;

structBiTNode*lchild,*rchild;

}*BiTree;

寫一函數(shù)voidA8(BiTreeT)求二叉樹7的深度。

第5頁共5頁

/

杭州電子科技大學(xué)

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

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

（試題共五大題，共四頁，總分150分）

姓名報考專業(yè)準(zhǔn)考證號

【所有答案必須寫在答題紙上，做在試卷或草稿紙上無效！】

一、判斷題（本大題共10小題，每小超2分.本大題共20分）

1.數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲無關(guān)，是獨立于計算

機的.

2.數(shù)據(jù)對象是數(shù)據(jù)元素的有限集合.

3.順序存儲結(jié)構(gòu)要求存儲單元地址連續(xù),而鏈?zhǔn)酱鎯Y(jié)構(gòu)要求存儲單元地址不連

續(xù).

4.若某完全二叉樹中共有121個結(jié)點，則第68個結(jié)點的度為0.

5.一個連通圖必定是一個無向完全圖.

6.平衡二叉樹必定是完全二叉樹.

7.只要精心設(shè)計，總是可以設(shè)計出無沖突的哈希函數(shù).

8.在最壞情況下，堆排序的時間性能是0（nlogn）,比快速排序最壞情況好.

9.通常，在一棵非空的二叉排序樹中.“刪除某個元素后乂將其插入.則所得的二又

排序樹與刪除前的二叉排序樹相同.

10.若哈希表采用線性探測法處理沖突，同義詞在表中不一定相鄰存儲.

二、單項選擇題（本大題共9小題，12個選項，每個選項2分，本大題共24分）

1,線性表的順序存儲結(jié)構(gòu)是一種的存儲結(jié)構(gòu).

A.散列存取B.索引存取C.隨機存取D.順序存取

2.循環(huán)隊列用數(shù)組A[a]存放其元素值，已知隊列的頭和尾分別用front和rear來

指示，初始化時置front=rear=0,則當(dāng)前隊列長度是.

A.（rear-front+m）%mB.rear-front+1

C.rear-front_1D.rear-front

3.線性表的鏈?zhǔn)酱尜A結(jié)構(gòu)的優(yōu)點為.

A.存儲空間可充分利用B.可隨機存取表中任一元素

C.插入刪除操作較為方便D.便于不找線性表中的元素

4.折半插入排序是對直接插入持序算法的改進，它著眼T減少?

A.移動元素的次數(shù)C.排序的超數(shù)

C.與關(guān)鍵字比較的次數(shù)D.空間復(fù)雜度

第I頁共4頁

5.設(shè)有向圖的頂點個數(shù)為n,則該有向圖最多有條弧.

A.n-1B.n(n-l)C.n(n+l)D.n'

6.如果二又樹中任何一個祚終端結(jié)點的值都人了其左子樹上所有結(jié)點的值而小丁

其右于樹上所有結(jié)點的值，要得到各結(jié)點值的遞增序列，應(yīng)按遍歷次序揖

列結(jié)點.

A.先序B.中序C.后序D.層序

7.具有n個結(jié)點的Huffman樹有個葉子結(jié)點..

A.n-1B.「n/21C.|_n/2」D.不定

8.已知廣義表工=(々,%2),4(53?)),從L中取出原子項y的運算是.

A.head(tai1(head(L)))B.tai1(head(head(tail(L))))

C.tai1(tai1(head(tai1(L))))D.head(tail(head(head(L))))

9.已知待排序的關(guān)鍵字序列為：36,21,78,63,6,52,15,39,48,70,10,需按非遞減

次序排序，則希爾排序第一趟(增埴為5)的結(jié)果為(1):起泡排序第一趟的

結(jié)果為(2):快速排序第一趟(以第一個元素為支點)的結(jié)果為(3):

堆排序初始建堆(大頂堆)的結(jié)果為(4).

A.21,36,63,6.52,15,39,48,70,10,78

B.78,70,52,63,21,36,15,39,48,6,10

C.78,52,63.70,21,15,36,39,48.6,10

D.10,21,15,6,36,52,63.39,48.70.78

E.10,15,39,48,6,36,21,78,63,70,52

F.21,36,78.63,6,52,15,39,48,70,10

三、填空題(本大題共12小題，20個填空項，每個填空項2分，本大題共40分)

1.一個隊列的入隊序列是1,2,3,4,則隊列可能的掠出序列是.

2.判斷不帶頭結(jié)點的單循環(huán)鏈表L為空的條件是.

3.設(shè)二維數(shù)組的“以行序為主序存儲，每個元素占4個字節(jié)，存儲器按字節(jié)編址.

已知A的起始存儲位置(即數(shù)組元素A?的存儲地址)為1000,則數(shù)組元素標(biāo)的存儲

地址是(1).數(shù)組A的存儲址是(2)字節(jié).

4.含n個頂點的連通圖中的任意一條簡單路徑，其長度不可能超過.

5.若無向圖有100個頂點、200條邊.用鄰接矩陣存儲,則該鄰接矩陣有(1)個

矩陣元素，(2)個非零元素.

6.高度為5的完全二叉樹至少有(1)個葉/結(jié)點,至多有(2)個葉子結(jié)

點.

7.將一個森林F話換為二叉樹B,則F的先序遍歷是B的遍歷?

8.一個餌法的語句頻度之和為T(n)=(3n'+2n'lo&n+4n-7)/(5n),用時間復(fù)雜

度表示為0().

9.在一棵m階B樹中，每個非終端結(jié)點至多有棵子樹。

笫2頁共4列

10.根據(jù)數(shù)據(jù)元素之間的關(guān)系的不同特征,可以分成集合、(1)、(2)和

圖狀結(jié)構(gòu)4類基本結(jié)構(gòu).

11.statusDeleteRear(LinkList&rear,ElemType&e)

(〃rear是帶頭結(jié)點的單循環(huán)鏈表的尾指針(指向循環(huán)偌表的表尾元素結(jié)點)，

〃本算法刪除首元結(jié)點，并由e返同其值.

if(rear->next=rear)

returnERROR;

____(1)____；

rear->next->next=p->next:

e=p->data;

if(p==rear)

⑵：

________(3)________：

returnOK;

)

12.BiTreeSearchBST(BiTreet,KeyTypekey)

(〃在根指針t所指的一義排序樹中遞歸地音找某關(guān)鍵字等于key的數(shù)據(jù)元素.

〃若杳找成功，則返回該元素結(jié)點的指針，否則返回空指針

if(!t)

⑴：

elseif(t->data.key=key)

returnt;

elseif(t->data.key<key)

⑵：

else

⑶；

四、簡答題(本大題共6小題，每小題6分，本大題共36分)

1.某二叉樹的先序遍歷序列為：JCBADEFIGH,中序遍歷序列為ABCEDFJGIH。

(1)請畫出該二叉樹；

(2)畫出其中序線索二叉樹.

2.對如心所示的有向圖，

(1)畫出其鄰接表：

(2)針對⑴的鄰接專寫出從頂點1

開始的深度優(yōu)先和廣最優(yōu)先遍歷序列.

3.設(shè)數(shù)據(jù)元素的關(guān)鍵字序列為(10,14,7,23,80,65,54,90,36,47,23),依次輸入這

些元素，創(chuàng)建一棵平衡的二義排序樹(AVL樹)，請逐一畫出每插入一個元素后的AVL

第3頁共4頁

樹的形態(tài).

4.什么是穩(wěn)定排序方法？希爾排序是不是穩(wěn)定排序方法？簡單選抒排序是不是稔

定持序方法？

5.設(shè)哈希表長度是16,哈希函數(shù)為H(key)=keymod13,用線性探測再散列法處

理沖突，依次在哈希表中插入12個元素(47,38,80,45,14,51,31,18,63.72,9.581.

(1)畫出它們在表中的分布情形.

(2)計算等概率時杳找成功的平均杳找K度ASL?

6.假設(shè)用于通訊的電文僅由8個字符組成,字符在電文中出現(xiàn)的領(lǐng)率及現(xiàn)有的一進

制前綴編碼如卜所示：

字符ABCDEFGH

頻率A137242202315

編碼uno111010000mu11001101

請問這套編碼是不是最優(yōu)的前綴編碼？為什么？如果不是，請給出更高效的編碼。

五、算法設(shè)計題(本大題共3小題，每小題10分，本大題共30分)

1.設(shè)有一個不帶頭結(jié)點的單鏈表，表中元素值均不相同.試編寫一個算法，刪除該

單鏈表中元素值為x的數(shù)據(jù)元素,若刪除成功，則返問irue,否則返回false.

單鏈表的結(jié)點定義為：

typedefstructLNode{

ElemTypedata;

structLNode*next;

ILNode,*LinkList;

【以卜兩展均假設(shè)一叉樹采用二叉鏈表存儲結(jié)構(gòu)，結(jié)點定義如卜：

typedefstructBiTNode{

TElemTypedata;

structBiTNode?IchiId,*rchiId;

IBiTNode,*BiTree;]

2.設(shè)計一算法,計算給定二義樹T中度為2的結(jié)點個數(shù)。

3.設(shè)指針p(升空)指向一義樹中的某個結(jié)點.且該結(jié)點的左右千樹均1F空，試寫

出求P所指結(jié)點的中序后繼的算法.

第4貢共4頁

杭州電子科技大學(xué)

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

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

(試題共六大題，6頁，150分)

姓名報考專業(yè)______________準(zhǔn)考證號

【所有答案必須寫在答題紙上，做在試卷或草稿紙上無效！】

一、是非題(每小題2分，共10分)

1.對「插入、刪除操作，單鏈衣和順序衣的時間復(fù)雜及都可計為.

2.隊列是種操件受限的線性表，所有對數(shù)據(jù)元素的操作僅限一端進行“

3.II線性結(jié)構(gòu)的遍歷過程是對結(jié)構(gòu)中的蜉數(shù)據(jù)元素訪問H.僅訪問?次,“結(jié)構(gòu)

中數(shù)據(jù)元素之間的美系無關(guān).

4.對r?求坡小代價生成樹的力.法，Kruskal方法優(yōu)「Prim方法.

5.哈希衣的杏找效率。衣找表的長位無關(guān)。

二、選擇題(每空2分，共28分)

1.線性表在的情況卜適「使用鏈表結(jié)構(gòu)實現(xiàn)＜

n：表中含有人址結(jié)點M需處常修改衣中結(jié)點如

c：需經(jīng)常對我進行刪除、插入d：表中數(shù)據(jù)幾索依美鍵字有序

2.如卜關(guān)丁巾的陳述中，錯誤的是.

a：串是數(shù)據(jù)對象為字符集的線性&b：中的長度為字符的個數(shù)

c：串中若干個連續(xù)字符構(gòu)成的子序列稱為廣小?巾中的數(shù)據(jù)元索是？私

3.設(shè)仃.維數(shù)組A[6][5]，庫一數(shù)組元素所川存儲空間為1個字必存儲器按字

?編址。已知A在存儲冊中的起始地址為100.則按行為儲此無索A12J⑶的

第一?個字。的地址是：按列存儲時，元素A12N3]的第-個字苗的

地址是.

a:128b:152c:IHOd:200

4.對廣義&A二(((a?b),(c)),(d))

執(zhí)行操作Rettai1(gelhead(geltai1(A)))的結(jié)果足：.

執(zhí)行操作gelhead(geHail(geIhcmi(A)))(f)結(jié)果是：-

a：《)b?(a)c：(h)(I