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

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

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

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

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

姓名報(bào)考專(zhuān)業(yè)準(zhǔn)考證號(hào)

【所有答案必須寫(xiě)在答題紙上，做在試卷或草稿紙上無(wú)效！】

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

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

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

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

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

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

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

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

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

9,對(duì)一棵二叉樹(shù)進(jìn)行層次遍歷時(shí)，應(yīng)借助于一個(gè)棧。()

10.在用弗洛伊德算法求解各頂點(diǎn)的最短路徑時(shí)，每個(gè)表示兩點(diǎn)間路徑的

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

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

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

A.動(dòng)態(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.在一個(gè)二維數(shù)組A中，假設(shè)每個(gè)數(shù)組元素在長(zhǎng)度為3個(gè)存儲(chǔ)單元，行下標(biāo)i

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

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

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

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

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.在一個(gè)長(zhǎng)為n的順序表中刪除第i個(gè)元素和第i個(gè)位置插入一個(gè)元素的時(shí)間復(fù)

雜度為()

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

第I頁(yè)共6頁(yè)

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

（）

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

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

（l<=i<=n）個(gè)元素是（）

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

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

（）

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

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

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

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

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

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

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)換為等價(jià)的后綴表達(dá)式ab+acd+e/f-*-g+時(shí)，用棧來(lái)存放哲時(shí)還不能確定運(yùn)算次

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

數(shù)是（）

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

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

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

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

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

（）

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

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

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

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

14.用相鄰矩陣A表示圖，判定任意兩個(gè)頂點(diǎn)Vi和Vj之間是否有長(zhǎng)度為m的

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

A.mAB.AC.AmD.Am-1

第2頁(yè)共6貞

15.下圖中給出由7個(gè)頂點(diǎn)組成的無(wú)向圖。從頂點(diǎn)1出發(fā)，對(duì)它進(jìn)行深度優(yōu)先遍

歷得到的序列可能是（）

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

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

1.N個(gè)頂點(diǎn)的連通圖的生成樹(shù)含有條邊。

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

中，至少要進(jìn)行次探測(cè)。

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

果是0

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

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

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

進(jìn)行），需要進(jìn)行趟完成排序。

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

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

為。

8.下圖中的強(qiáng)連通分量的個(gè)數(shù)為_(kāi)____個(gè)。

第3頁(yè)共6頁(yè)

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

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

是。

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

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

11.對(duì)于一個(gè)非連通無(wú)向圖.共有28條邊,則該圖至少有個(gè)頂點(diǎn)。

12.n個(gè)頂點(diǎn)的無(wú)向圖的鄰接表最多有個(gè)表結(jié)點(diǎn)。

13.對(duì)n階對(duì)稱(chēng)矩陣壓縮存儲(chǔ)時(shí)，需要表長(zhǎng)為的順序表。

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

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

15.對(duì)下圖進(jìn)行拓?fù)渑判颍梢缘玫讲煌耐負(fù)湫蛄械膫€(gè)數(shù)是。

第4頁(yè)共6頁(yè)

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

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

(1)寫(xiě)出從A點(diǎn)開(kāi)始深度優(yōu)先的訪問(wèn)序列(鄰接邊的順序按鄰接表鏈表順序);

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

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

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

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

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

(1)請(qǐng)畫(huà)出所構(gòu)造的散列表。

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

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

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

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

structTree

(

intdata;

structTree*left;

structTree*right;

);

intfindLevel(Treeroot,intdata)

第5頁(yè)共6頁(yè)

5.給定一個(gè)二叉樹(shù)和其中的一個(gè)結(jié)點(diǎn)，請(qǐng)找出中序遍歷順序中該節(jié)點(diǎn)的下一個(gè)

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

指針。

節(jié)點(diǎn)結(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ě)算法，實(shí)現(xiàn)在單向鏈表上刪除具有重復(fù)值的多余節(jié)點(diǎn)，使得表中每個(gè)節(jié)

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

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

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

boolBracketsCheck(char*str)

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

TypedefStruct{

intvertex[m];

intedge[m];}gadjmatrix;

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

TypedefStructnodel{

intinfo;

intadjvertex;

structnodel*nextarc;}glinklistnode;

TypedefStructnode2{

intvertexinto;

glinklistnode*firstarc;}glinkheadnode:

請(qǐng)?jiān)O(shè)計(jì)計(jì)算法MatToList,將無(wú)向圖的鄰接矩陣轉(zhuǎn)為對(duì)應(yīng)的鄰接表。

voidMatToList(gadjmatrixgl[],glinkheadnodeg2[]){

}

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

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

第6頁(yè)共6頁(yè)

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

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

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

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

姓名報(bào)考專(zhuān)業(yè)_____________準(zhǔn)考證號(hào)

【所有答案必須寫(xiě)在答題紙上，做在試卷或草稿紙上無(wú)效！】

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

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

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

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

出的特性。()

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

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

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

()

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

n+1個(gè)空指針.()

7.強(qiáng)連通分量是無(wú)向圖的極大強(qiáng)連通了?圖。()

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

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

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

會(huì)破壞樹(shù)的結(jié)構(gòu)。()

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

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

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

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

第I貞大5頁(yè)

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

示一個(gè)操作.

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

D.以上幾個(gè)都是錯(cuò)誤的

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

A.存儲(chǔ)密度大B.插入運(yùn)算方便

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

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

第三個(gè)出棧的元素是

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

4.若一棵二叉樹(shù)具有7個(gè)度為2的結(jié)點(diǎn)，6個(gè)度為1的結(jié)點(diǎn)，則度為。的結(jié)點(diǎn)個(gè)

數(shù)是（）。

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

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

A.CABDEFGB.ABCDEFGC.DACEFBGD.ADCFEG

6.連通一個(gè)n個(gè)頂點(diǎn)的無(wú)向圖，其邊的個(gè)數(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è)序列不是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.對(duì)線性表進(jìn)行折半查找，表中元素的存儲(chǔ)方式及元素排列要求為（）.

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

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

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

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

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

第2頁(yè)共5頁(yè)

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

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

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

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

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

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

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

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

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

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

是.

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

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

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

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

需的總空間是.

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

則此類(lèi)二叉樹(shù)的結(jié)點(diǎn)數(shù)至少為.

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

點(diǎn)，那么該完全二叉樹(shù)共有一個(gè)結(jié)點(diǎn)。

8.G是一個(gè)非連通無(wú)向圖，共有30條邊，則該圖至少有個(gè)頂點(diǎn).

9.Dijkstra短路徑算法從源點(diǎn)到其余各頂點(diǎn)的短路徑的路徑長(zhǎng)度按次序

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

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

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

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

出的步長(zhǎng)(也稱(chēng)增量序列)依次是4,2,1則排序需趟，寫(xiě)出第一趟

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

第3頁(yè)共5頁(yè)

四、簡(jiǎn)答題（本大題共5題，本大題共40分）

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

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

多少.

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

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

對(duì)應(yīng)的森林。

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

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

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

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

653.460進(jìn)行：

（1）建立堆排序的初始堆（小頂堆），要求畫(huà)出主要過(guò)程.

（2）輸出最小值后，如何得到次小值?（并畫(huà)出相應(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)鍵字對(duì)13取模，沖突用鏈地址法解決，設(shè)哈希表

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

第4頁(yè)共5頁(yè)

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

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

成，其中data域?yàn)樽址?。?xiě)出算法dc（h,n）,判斷該鏈表的前n個(gè)字符是否中

心對(duì)稱(chēng)。例如xyx,xyyx都是中心對(duì)稱(chēng)。

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

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

時(shí)間復(fù)雜度。

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

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

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

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

第5頁(yè)共5頁(yè)

/

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

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

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

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

姓名報(bào)考專(zhuān)業(yè)_______________準(zhǔn)考證號(hào)

【所有答案必須寫(xiě)在答題紙上，做在試卷或草稿紙上無(wú)效！】

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

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

a：線性表b：棧c：隊(duì)列d：串

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

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

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

3.對(duì)廣義表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.任何一個(gè)連通網(wǎng)的最小生成樹(shù).

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

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

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

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

的路徑.

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

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

則下面不正確的說(shuō)法是..

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

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

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

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

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

序序列的關(guān)鍵字次序?yàn)榈剐驎r(shí)，若需為之進(jìn)行正序排序，下列方案中以

為佳.

a:堆排序b:快速排序c:直接插入排序d:簡(jiǎn)單選擇排序

第I頁(yè)共5頁(yè)

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

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

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

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

3.n個(gè)頂點(diǎn)的強(qiáng)連通圖至少有條狐，至多有條狐。

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

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

則該二叉樹(shù)是.

5,若對(duì)完全二叉樹(shù)中的結(jié)點(diǎn)從1開(kāi)始按層進(jìn)行編號(hào)，設(shè)最人編號(hào)為n,則編號(hào)為i

的結(jié)點(diǎn)(1。9)的父結(jié)點(diǎn)編號(hào)為；所有編號(hào)的結(jié)點(diǎn)為葉子結(jié)點(diǎn)?

6.壓棧次序?yàn)閍、b、c,則不可能得到的輸出序列是.

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

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

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

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

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

I,已知某二叉樹(shù)的先序遍歷次序?yàn)椋篈BCDEFG.中序遍歷次序?yàn)椋築ADCFEG.

(1)畫(huà)出該二叉樹(shù)形.

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

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

2.已知某無(wú)向圖如右圖所示：

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

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

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

及BFS次序.

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

態(tài)為空)，

(1)請(qǐng)畫(huà)出該B-樹(shù).

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

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

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

(1)畫(huà)出它們?cè)诒碇械姆植记樾?

(2)計(jì)算其平均成功的查找長(zhǎng)度.

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

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

(1)畫(huà)出你所建的哈夫曼樹(shù)，

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

笫2頁(yè)共5頁(yè)

四、閱讀以下函數(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é)點(diǎn)的單鏈表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//初始條件：鏈隊(duì)列Q已存在

inti=0;

QueuePtrp：

P=Q.front;

第3頁(yè)共5頁(yè)

while(Q.rear!=p){

i++：

p=p->next;

)

returni;

}

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

{//初始條件：二叉樹(shù)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頁(yè)共5頁(yè)

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

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

typedefstructLNode{

intdata;

structLnode*next：

)*LinkList;

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

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

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

typedefstructBiTNode{

TElernTypedata;

structBiTNode*lchild,*rchild;

}*BiTree;

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

第5頁(yè)共5頁(yè)

/

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

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

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

（試題共五大題，共四頁(yè)，總分150分）

姓名報(bào)考專(zhuān)業(yè)準(zhǔn)考證號(hào)

【所有答案必須寫(xiě)在答題紙上，做在試卷或草稿紙上無(wú)效！】

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

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

機(jī)的.

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

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

續(xù).

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

5.一個(gè)連通圖必定是一個(gè)無(wú)向完全圖.

6.平衡二叉樹(shù)必定是完全二叉樹(shù).

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

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

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

排序樹(shù)與刪除前的二叉排序樹(shù)相同.

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

二、單項(xiàng)選擇題（本大題共9小題，12個(gè)選項(xiàng)，每個(gè)選項(xiàng)2分，本大題共24分）

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

A.散列存取B.索引存取C.隨機(jī)存取D.順序存取

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

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

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

C.rear-front_1D.rear-front

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

A.存儲(chǔ)空間可充分利用B.可隨機(jī)存取表中任一元素

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

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

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

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

第I頁(yè)共4頁(yè)

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

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

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

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

列結(jié)點(diǎn).

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

7.具有n個(gè)結(jié)點(diǎn)的Huffman樹(shù)有個(gè)葉子結(jié)點(diǎn)..

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

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

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):快速排序第一趟(以第一個(gè)元素為支點(diǎn))的結(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個(gè)填空項(xiàng)，每個(gè)填空項(xiàng)2分，本大題共40分)

1.一個(gè)隊(duì)列的入隊(duì)序列是1,2,3,4,則隊(duì)列可能的掠出序列是.

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

3.設(shè)二維數(shù)組的“以行序?yàn)橹餍虼鎯?chǔ)，每個(gè)元素占4個(gè)字節(jié)，存儲(chǔ)器按字節(jié)編址.

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

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

4.含n個(gè)頂點(diǎn)的連通圖中的任意一條簡(jiǎn)單路徑，其長(zhǎng)度不可能超過(guò).

5.若無(wú)向圖有100個(gè)頂點(diǎn)、200條邊.用鄰接矩陣存儲(chǔ),則該鄰接矩陣有(1)個(gè)

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

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

點(diǎn).

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

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

度表示為0().

9.在一棵m階B樹(shù)中，每個(gè)非終端結(jié)點(diǎn)至多有棵子樹(shù)。

笫2頁(yè)共4列

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

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

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

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

〃本算法刪除首元結(jié)點(diǎn)，并由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所指的一義排序樹(shù)中遞歸地音找某關(guān)鍵字等于key的數(shù)據(jù)元素.

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

if(!t)

⑴：

elseif(t->data.key=key)

returnt;

elseif(t->data.key<key)

⑵：

else

⑶；

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

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

(1)請(qǐng)畫(huà)出該二叉樹(shù)；

(2)畫(huà)出其中序線索二叉樹(shù).

2.對(duì)如心所示的有向圖，

(1)畫(huà)出其鄰接表：

(2)針對(duì)⑴的鄰接專(zhuān)寫(xiě)出從頂點(diǎn)1

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

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

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

第3頁(yè)共4頁(yè)

樹(shù)的形態(tài).

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

定持序方法？

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

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

(1)畫(huà)出它們?cè)诒碇械姆植记樾?

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

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

制前綴編碼如卜所示：

字符ABCDEFGH

頻率A137242202315

編碼uno111010000mu11001101

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

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

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

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

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

typedefstructLNode{

ElemTypedata;

structLNode*next;

ILNode,*LinkList;

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

typedefstructBiTNode{

TElemTypedata;

structBiTNode?IchiId,*rchiId;

IBiTNode,*BiTree;]

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

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

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

第4貢共4頁(yè)

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

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

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

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

姓名報(bào)考專(zhuān)業(yè)______________準(zhǔn)考證號(hào)

【所有答案必須寫(xiě)在答題紙上，做在試卷或草稿紙上無(wú)效！】

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

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

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

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

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

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

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

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

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

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

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

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

a：串是數(shù)據(jù)對(duì)象為字符集的線性&b：中的長(zhǎng)度為字符的個(gè)數(shù)

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

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

?編址。已知A在存儲(chǔ)冊(cè)中的起始地址為100.則按行為儲(chǔ)此無(wú)索A12J⑶的

第一?個(gè)字。的地址是：按列存儲(chǔ)時(shí)，元素A12N3]的第-個(gè)字苗的

地址是.

a:128b:152c:IHOd:200

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

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

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

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