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

杭州電子科技大學

2019年攻讀碩士學位研究生招生考試

《數(shù)據(jù)結構》試題

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

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

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

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

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

2.對任何數(shù)據(jù)結構鏈式存儲結構一定優(yōu)于順序存儲結構。()

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

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

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

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

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

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

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

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

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

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

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

A.動態(tài)結構、靜態(tài)結構B.順序結構、鏈式結構

C.線性結構、非線性結構D.初等結構、構造型結構

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

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

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

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

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

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個位置插入一個元素的時間復

雜度為()

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

第I頁共6頁

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

（）

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.設表頭不帶頭結點且所有操作均在表頭進行，則下列最不適合作為鏈棧的是

（）

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

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

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

D.只有表尾結點指針，沒有表頭指針的單向循環(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.表達式a*（b+c）-d的后綴表達式是（）

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

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

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

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

數(shù)是（）

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

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

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

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

12.設無向圖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ù)有n個，其哈夫曼樹的結點總數(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個關鍵字互為同義詞，著用線性探測法把這K個關鍵字填入散列表

中，至少要進行次探測。

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

果是0

4,一組記錄的關鍵碼是（46,79,56,38,40,84）,以第一個記錄為基準，從

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

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

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

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

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

為。

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

第3頁共6頁

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

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

是。

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

依次得到的各最短路徑的目標頂點是。

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

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

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

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

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

15.對下圖進行拓撲排序，可以得到不同的拓撲序列的個數(shù)是。

第4頁共6頁

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

1.某帶權有向圖及其鄰接表如F：

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

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

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

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

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

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

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

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

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

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

節(jié)點結構：

structTree

(

intdata;

structTree*left;

structTree*right;

);

intfindLevel(Treeroot,intdata)

第5頁共6頁

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

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

指針。

節(jié)點結構如下：

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)在單向鏈表上刪除具有重復值的多余節(jié)點，使得表中每個節(jié)

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

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

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

boolBracketsCheck(char*str)

3.已知圖的鄰接矩陣的存儲結構說明為:

TypedefStruct{

intvertex[m];

intedge[m];}gadjmatrix;

圖的鄰接表的存儲結構說明為

TypedefStructnodel{

intinfo;

intadjvertex;

structnodel*nextarc;}glinklistnode;

TypedefStructnode2{

intvertexinto;

glinklistnode*firstarc;}glinkheadnode:

請設計計算法MatToList,將無向圖的鄰接矩陣轉為對應的鄰接表。

voidMatToList(gadjmatrixgl[],glinkheadnodeg2[]){

}

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

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

第6頁共6頁

杭州電子科技大學

2018年攻讀碩士學位研究生招生考試

《數(shù)據(jù)結構》試題

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

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

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

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

1.數(shù)據(jù)的邏輯結構是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關系。()

2.單鏈表中設置的頭結點只具有標識的作用。()

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

出的特性。()

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

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

5.哈夫曼樹是帶權路徑長度最短的樹，帶權路徑長度等于所有結點的權值之和。

()

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

n+1個空指針.()

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

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

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

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

會破壞樹的結構。()

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

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

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

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

第I貞大5頁

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

示一個操作.

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

D.以上幾個都是錯誤的

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

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

C.刪除運算方便D.可方便地用于各種邏輯結構的存儲表示

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

第三個出棧的元素是

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

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

數(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的拓撲有序序列（）.

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.鏈接方式存儲，元素無序B.鏈接方式存儲，元素有序

C.順序方式存儲，元素無序D,順序方式存儲，元素有序

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

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

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

第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)定的線性表，采用存儲結構，能在很少進行插入和刪

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

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

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

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

是.

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

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

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

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

需的總空間是.

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

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

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

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

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

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

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

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

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

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

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

結束后，數(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ù)的時間復雜度是

多少.

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

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

對應的森林。

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

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

（2）從結點VI到結點V8的最短路徑；

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

653.460進行：

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

（2）輸出最小值后，如何得到次小值?（并畫出相應結果圖）

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

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

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

第4頁共5頁

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

L（本題10分）設單鏈表的表頭指針為h,結點結構由data和next兩個域構

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

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

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

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

時間復雜度。

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

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

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

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

第5頁共5頁

/

杭州電子科技大學

2011年攻讀碩士學位研究生入學考試

《數(shù)據(jù)結構》試題

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

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

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

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

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

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

2.如下關于串的陳述中，正確的是、.

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

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

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

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

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

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

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

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

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

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

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

的路徑.

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

7.設無向圖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)定的；具有最好的平均性能：當恃排

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

為佳.

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

第I頁共5頁

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

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

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

而線性表的存儲結構是通過指針保持數(shù)據(jù)元素之間的邏輯關系的.

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

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

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

則該二叉樹是.

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

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

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

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

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

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

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

三、圖示結構題(每小題8分，共40分)

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

(1)畫出該二叉樹形.

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

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

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

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

(2)畫出該圖的鄰接矩陣存儲結構。只)

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

及BFS次序.

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

態(tài)為空)，

(1)請畫出該B-樹.

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

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

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

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

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

5.假設用于通訊的電文僅由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)

(〃初始條件：帶頭結點的單鏈表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頁

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

I.設單鏈表結點結構為：

typedefstructLNode{

intdata;

structLnode*next：

)*LinkList;

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

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

2.設二叉鏈表結構為：

typedefstructBiTNode{

TElernTypedata;

structBiTNode*lchild,*rchild;

}*BiTree;

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

第5頁共5頁

/

杭州電子科技大學

2012年攻讀碩士學位研究生入學考試

《數(shù)據(jù)結構》試題

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

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

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

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

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

機的.

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

3.順序存儲結構要求存儲單元地址連續(xù),而鏈式存儲結構要求存儲單元地址不連

續(xù).

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

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

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

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

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

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

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

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

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

1,線性表的順序存儲結構是一種的存儲結構.

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

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

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

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

C.rear-front_1D.rear-front

3.線性表的鏈式存貯結構的優(yōu)點為.

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

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

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

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

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

第I頁共4頁

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

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

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

其右于樹上所有結點的值，要得到各結點值的遞增序列，應按遍歷次序揖

列結點.

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

7.具有n個結點的Huffman樹有個葉子結點..

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.已知待排序的關鍵字序列為：36,21,78,63,6,52,15,39,48,70,10,需按非遞減

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

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

堆排序初始建堆(大頂堆)的結果為(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.判斷不帶頭結點的單循環(huán)鏈表L為空的條件是.

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

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

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

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

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

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

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

點.

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

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

度表示為0().

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

笫2頁共4列

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

圖狀結構4類基本結構.

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

(〃rear是帶頭結點的單循環(huán)鏈表的尾指針(指向循環(huá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所指的一義排序樹中遞歸地音找某關鍵字等于key的數(shù)據(jù)元素.

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

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ù)據(jù)元素的關鍵字序列為(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.設哈希表長度是16,哈希函數(shù)為H(key)=keymod13,用線性探測再散列法處

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

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

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

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

制前綴編碼如卜所示：

字符ABCDEFGH

頻率A137242202315

編碼uno111010000mu11001101

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

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

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

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

單鏈表的結點定義為：

typedefstructLNode{

ElemTypedata;

structLNode*next;

ILNode,*LinkList;

【以卜兩展均假設一叉樹采用二叉鏈表存儲結構，結點定義如卜：

typedefstructBiTNode{

TElemTypedata;

structBiTNode?IchiId,*rchiId;

IBiTNode,*BiTree;]

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

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

出求P所指結點的中序后繼的算法.

第4貢共4頁

杭州電子科技大學

2013年攻讀碩士學位研究生入學考試

《數(shù)據(jù)結構》試題

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

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

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

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

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

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

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

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

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

5.哈希衣的杏找效率。衣找表的長位無關。

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

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

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

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

2.如卜關丁巾的陳述中，錯誤的是.

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

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

3.設仃.維數(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)))的結果足：.

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

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