溫州大學(xué)數(shù)據(jù)結(jié)構(gòu)2017-2018,2020-2021年考研專業(yè)課初試真題

絕密★考試結(jié)束前溫州大學(xué)

2021年碩士研究生招生考試試題

科目代碼及名稱：826數(shù)據(jù)結(jié)構(gòu)

適用專業(yè)（方向）：081200計(jì)算機(jī)科學(xué)與技術(shù)

請考生按規(guī)定用筆將所有試題的答案寫在答題紙上，在此試題紙上答題無效

一、單項(xiàng)選擇題（共10小題，每小題4分，共40分）

1.數(shù)組的邏輯結(jié)構(gòu)不同于下列（）的邏輯結(jié)構(gòu)。

A.線性表B.棧

C.隊(duì)列D.樹

2.采用開放定址法處理散列表的沖突時(shí)，其平均查找長度（）。

A.低于鏈接法處理沖突B.高于鏈接法處理沖突

C.與鏈接法處理沖突相同D.高于二分查找

3.一個(gè)線性表中最常用操作是根據(jù)第i個(gè)元素獲取其前驅(qū)節(jié)點(diǎn)i-1,則（）方式存儲最節(jié)省

存儲空間。

A.單鏈表B.循環(huán)雙鏈表C.循環(huán)單鏈表D.順序表

4.哪種遍歷方式在遍歷它的左子樹和右子樹之前遍歷它自身？（）

A.后序遍歷B.先序遍歷

C.中序遍歷D.層次遍歷

5.設(shè)有一個(gè)二維數(shù)組Data[m][n],假設(shè)Data⑼[0]存放位置在921,Data⑵⑵存放位置在965,每

個(gè)元素占一個(gè)空間，問Data[3]⑶存放在（）位置？

A.987B.986C.985D.996

6.設(shè)棧Stack和隊(duì)列Que的初始狀態(tài)為空，元素al、a2、a3、a4、a5和a6依次通過棧Stack,一

個(gè)元素出棧后即進(jìn)入隊(duì)列Que。若6個(gè)元素出列的順序?yàn)閍2、a4、a3、a6、a5和al,則棧

Stack的容量至少應(yīng)該是()。

A.6B.4

C.3D.2

7.下列四種排序中()的空間復(fù)雜度最大。

A.插入排序B.冒泡排序

C.歸并排序D.堆排序

8.用指向左、右孩子結(jié)點(diǎn)的二個(gè)引用域的二叉鏈表存儲有n個(gè)結(jié)點(diǎn)的二叉樹，則一共有()

個(gè)空的引用域。

A.n+1B.n-1C.nD.不能確定

9.設(shè)一組初始記錄關(guān)鍵字序列(25,12,26,23,38),以第一個(gè)記錄關(guān)鍵字25為基準(zhǔn)進(jìn)行一趟

快速排序的結(jié)果為()。

A.12,23,25,38,26B.23,12,25,38,26

C.23,12,25,26,38D.12,23,26,25,28

10.設(shè)數(shù)組data[MAX]作為循環(huán)隊(duì)列SQ的存儲空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行

出隊(duì)操作后其頭指針front值為()

A.front=front+lB.front=(front+l)%(MAX-1)

C.front=(fiont-l)%MAXD.front=(front+l)%MAX

二、分析題（共5小題，每小題10分，共50分）

1.從給定二叉樹的先序和中序遍歷序列，可以構(gòu)造一棵二叉樹。已知先序遍歷序列為

{ABCDEFGH）,中序遍歷序列為{DCBEAGFH},完成以下要求。

（1）實(shí)現(xiàn)由先序、中序構(gòu)造二叉樹程序（7分）。

（2）畫出構(gòu)造的二叉樹（3分）。

注：將下述代碼抄寫到答題紙上，并在答題紙上編寫完成createBTree函數(shù)的代碼。

typedefstructNode{

ElementTypedata;

structNode*left;

structNode*right;

JBTNode,*Blree;

intpre[MAX],in[MAX];//存放先序、中序遍歷序列

〃先序、中序遍歷構(gòu)造二叉樹

//bl,tl分別是先序序列的下界（下標(biāo)）和上界（下標(biāo)）

//b2,t2分別是中序序列的下界（下標(biāo)）和上界（下標(biāo)）

BTreecreateBTree（intbl,inttl,iiitb2,intt2）

2.用普里姆算法構(gòu)造圖1所示的無向圖從頂點(diǎn)vO開始的最小生成樹。完成以下要求。

（1）從圖2開始，依次畫出最小生成樹生成過程（6分）。

（注：從圖2開始，根據(jù)算法過程，每幅圖依次增加一個(gè)頂點(diǎn)及相應(yīng)的邊。圖n中應(yīng)保留圖n-1

的所有頂點(diǎn)和邊。）

（2）簡述普里姆算法（4分）。

3.雙鏈表的數(shù)據(jù)結(jié)構(gòu)如下所示。請實(shí)現(xiàn)在雙鏈表的表頭節(jié)點(diǎn)之后插入新節(jié)點(diǎn)操作。

注：將下述代碼抄寫到答題紙上，并在答題紙上編寫完成doubleLinkedListHeadlnsert函數(shù)的代碼。

typedefstructDNode〃數(shù)據(jù)結(jié)構(gòu)

(

ELEMTYPdata;

structDNode*prev;

structDNode*next;

}DNode;

typedefstructDoubleLinkedList//數(shù)據(jù)結(jié)構(gòu)

(

DNode*head;

intlen;

}DoubleLinkedList;

intdoubleLinkedListHeadInsert(DoubleLinkedList*dlList,ELEMTYPx)〃函數(shù)原型

(

)

4.在如圖的平衡二叉樹節(jié)點(diǎn)A的左子樹的左子樹上插入節(jié)點(diǎn)5,導(dǎo)致平衡二叉樹不平衡，完成以

下要求。

(1)繪出調(diào)整后的平衡二叉樹(6分)。

(2)指出這種失衡的類型并簡要其調(diào)整過程(4分)。

5.某工程中AOE網(wǎng)如下圖所示。為了更好的完成工作，需要幫助他們找出關(guān)鍵活動和關(guān)鍵路徑。

請回答下列問題:

（1）各事件的最早發(fā)生時(shí)間和最晚發(fā)生時(shí)間（4分）。

V0VIV2V3V4V5

最早發(fā)生時(shí)間

最晚發(fā)生時(shí)間

（2）各活動的最早開始時(shí)間和最晚開始時(shí)間（4分）。

ala2a3a4a5a6a7a8

最早開始時(shí)間

最晚開始時(shí)間

（3）關(guān)鍵路徑：；關(guān)鍵路徑的長度：（2分）。

三、綜合應(yīng)用題（共4小題，每小題15分，共60分）

1.調(diào)整整數(shù)數(shù)組array口中的元素位置，并返回分界位置i,使所有值為奇數(shù)的元素均落在array[l..i]

上，使所有值為偶數(shù)的元素均落在array[i+l..h]±o

要求：（1）時(shí)間復(fù)雜度為0（n）、空間復(fù)雜度為0（1）；（2）算法用下面的函數(shù)原型表示。

注：將下述代碼抄寫到答題紙上，并在答題紙上編寫完成arrange函數(shù)的代碼。

/*順序表結(jié)構(gòu)*/

typedefintElementType;

typedefstruct{

ElementTypearray[MAX];/*存放元素的數(shù)組*/

intlength;/*已經(jīng)有多少元素*/

intcapacity;/*容量*/

}*SeqList;

intarrange（SeqListlist）

2.鄰接矩陣法存儲有向圖及度的計(jì)算：

（1）寫出圖中有向圖的鄰接矩陣（6分）。

（2）計(jì)算圖中各頂點(diǎn)的出度、入度和度（6分）。

（3）描述根據(jù)有向圖的鄰接矩陣計(jì)算有向圖的度的算法（3分）。

3.假設(shè)用于通信的電文由字符集｛a,b,c,d,e,￡g,h｝中的字符組成，這8個(gè)字符在電文中出現(xiàn)的

頻率為｛0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10｝。

（1）畫出哈夫曼樹（8分）。

（2）計(jì)算最小帶權(quán)路徑和（3分）。

（3）給出各字符的編碼，左孩子編號0,右孩子編號1（4分）。

4.編寫一個(gè)算法，用下面指定的鏈表結(jié)構(gòu)實(shí)現(xiàn)兩個(gè)多項(xiàng)式相加。如LA:2x2+3,LB:3x3+x2+l,LA和

LB相力U后得至ILA：3x3+3x2+4o

注：將下述代碼抄寫到答題紙上，并在答題紙上編寫完成polyAdd函數(shù)的代碼。

structNode｛〃鏈表的數(shù)據(jù)結(jié)構(gòu)

intcoef;//系數(shù)

intexpon;〃指數(shù)

structNode*next;

}Node,*LinkList;

voidpolyAdd(LinkListpolyl,LinkListpoly2)〃計(jì)算多項(xiàng)式的和

（請考生在答題紙上答題，在此試題紙上答題無效）

一、單項(xiàng)選擇題（共10小題，每小題4分，共40分）

1.在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的（）。

A.邏輯結(jié)構(gòu)B.存儲結(jié)構(gòu)

C.邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)D.物理結(jié)構(gòu)

2.算法的時(shí)間復(fù)雜度屬于一種（）。

A.事前統(tǒng)計(jì)的方法B.事前分析估算的方法

C.事后統(tǒng)計(jì)的方法D.事后分析估算的方法

3.線性表中的所有元素都有一個(gè)前驅(qū)元素和后繼元素。這個(gè)說法是()。

A.正確的B.錯(cuò)誤的

4.鏈?zhǔn)酱鎯Φ拇鎯Y(jié)構(gòu)所占存儲空間()

A.分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針

B.只有一部分，存放結(jié)點(diǎn)值

C.只有一部分，存儲表示結(jié)點(diǎn)間關(guān)系的指針

D.分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)

5.經(jīng)過以下棧運(yùn)算后，x的值是()。

initStack(s);push(s,a);push(s,b);pop(s,&x);top(s,&x);

A.aB.bC.1D.0

6.數(shù)組A中，每個(gè)元素的長度為4個(gè)字節(jié)，行下標(biāo)i從1到8,列下標(biāo)j從1到10,從首地址

100開始連續(xù)存放在存儲器內(nèi)。若該數(shù)組按行主序存放，則元素A[8][5]的起始地址為()；

若該數(shù)組按列主序存放，則元素A[8J⑸的起始地址為()。

A.396,217B,396,256C.256,396D.256,217

7.若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，則該二叉樹的度為0的結(jié)點(diǎn)個(gè)數(shù)是()。

A.9B.11C.12D.不確定

8.設(shè)有無向連通圖G中的邊集氏{(A,B),(A,C),(A,E),(B,E),(E,D),(D,F),(F,C)}。若從

頂點(diǎn)A出發(fā)按深度優(yōu)先搜索進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為()。

A.{A,B,E,C,D,F}B.{A,C,F,E,B,D}

C.{A,E,B,C,F,D}D.{A,E,D,F,C,B)

9.對于長度為9的有序順序表，若采用折半查找法，在等概率情況下查找成功的平均查找長度

為()的值除以9。

A.20B.18C.25D.22

10.排序算法的穩(wěn)定性是指()。

A.經(jīng)過排序之后，能使值相同的數(shù)據(jù)保持原順序中的相對位置不變

B.經(jīng)過排序之后，能使值相同的數(shù)據(jù)保持原順序中的絕對位置不變

C.排序算法的性能與待排序元素的數(shù)量關(guān)系不大

D.排序算法的性能與待排序元素的數(shù)量關(guān)系密切

二、填空題(共5小題，每小題10分，共50分)

1.請完成下面順序表的操作。順序表的類型如下。

typedefstruct)

ElementType*array;/*存放元素的數(shù)組刃

intlength;/*已經(jīng)有多少元素*/

intcapacity;/*容量*/

JSeqList;

/*在順序表的第i個(gè)位置插入元素X*/

intinsertList(SeqList*L,inti,ElementTypex)

(

if(L->length>=L->capacity){

return0;

)

if(i<1||i>L->length+l){

return0;

)

for(k=L->length-1;k>=i-l;k-){

L->array[k+l]=L->arraylk];

return1;

)

2.假設(shè)通訊電文中只用到A,B,C,D,E,F六個(gè)字母，它們在電文中出現(xiàn)的相對頻率分別為：

8,3,16,10,5,20。(1)用這些信息構(gòu)造哈夫曼樹；(2)計(jì)算該哈夫曼樹的帶權(quán)路徑長度。

這棵哈夫曼樹有個(gè)結(jié)點(diǎn)；該哈夫曼樹的帶權(quán)路徑長度(WPL)：。

3.己知序列{99,5,36,7,22,17,46,12,2,19,25,28,1,92},用這些序列建小根堆。

按照從上到下，從左到右，小根堆的結(jié)點(diǎn)序列是：。

4.已知序列{13,2,16,3,8,28,4,10,5,6,7},請按照下面的快速排序算法，給出該序列作升序排

列時(shí)前三趟的結(jié)果。

第]趟：;

第2趟：；

第3趟：o

typedefintElementType;

intpartition(ElementTyper[],intlow,inthigh)

(

intpivot;

pivot=r[lowj;

while(low<high){

while(low<high&&r[high]>=pivot){

high-;

)

r[low]=r[high];

while(low<high&&r[low]<=pivot){

low++;

)

r[high]=r[low];

}一

r[lowj=pivot;

returnlow;

)

voidqSort(ElemenlTyper[],intlow,inthigh)

(

intpos;

if(low<high){

pos=partition(r,low,high);/*將r[Iow..high]一分為二*/

qSort(r,low,pos-1);/*對左邊子表快速排序*/

qSort(r,pos+1,high);/*對右邊子表快速排序*/

)

)

voidquickSort(ElementTyper[],intn){

qSort(r,1,n);

)

5.計(jì)算下圖所示的AOE網(wǎng)中各頂點(diǎn)所表示的事件最早發(fā)生時(shí)間、最晚發(fā)生時(shí)間和各邊所表示的

活動最早開始時(shí)間、最晚開始時(shí)間，找出關(guān)鍵路徑并計(jì)算關(guān)鍵路徑的長度。

(1)(5分)

各事件的最早發(fā)生時(shí)間和最晚發(fā)生時(shí)間:

vOvlv2v3v4v5v6v7v8

最早發(fā)生時(shí)間

最晚發(fā)生時(shí)間

各活動的最早開始時(shí)間和最晚開始時(shí)間:

ala2a3a4a5a6a7a8A9alOall

最早開始時(shí)間

最晚開始時(shí)間

(2)關(guān)鍵路徑：；關(guān)鍵路徑的長度：o(5分)

三、應(yīng)用題(共4小題，每小題15分，共60分)

1.設(shè)計(jì)一個(gè)高效算法，刪除順序表中所有元素值為X的元素。假設(shè)順序表的數(shù)據(jù)元素類型為整

型。要求：(1)用下面指定的順序表結(jié)構(gòu)；(2)時(shí)間復(fù)雜度為O(n)、空間復(fù)雜度為0(1)；(3)

算法用下面的函數(shù)原型表示。

/*順序表結(jié)構(gòu)*/

typedefintElementType;

typedefstruct{

ElementType*array;/*存放元素的數(shù)組*/

intlength;/*已經(jīng)有多少元素*/

intcapacity;/*容量*/

(SeqList;

/*刪除所有元素值為x的元素*/

voiddeleteAHX(SeqList*L,intx);

2.有兩個(gè)單鏈表LA和LB,它們的元素均為非遞減有序排列。編寫一個(gè)算法，將它們合并成一

個(gè)單鏈表，要求合并后的單鏈表中的元素也是非遞減有序序列，并且不需要額外申請結(jié)點(diǎn)空

間。例如，LA=(2,2,3),LB=(1,3,3,4),合并后為(1,2,2,3,3,3,4)。要求：(1)用下面指定

的鏈表結(jié)構(gòu)；(2)算法用下面的函數(shù)原型表示。

/*鏈表結(jié)構(gòu)*/

typedefstructNode{

ElementTypedata;

structNode*next;

[Node,*LinkList;/*LinkLisl為結(jié)構(gòu)指針類型*/

/*兩個(gè)單鏈表的合并。

LA表示第1個(gè)單鏈表，LB表示第2個(gè)單鏈表。相加到LA單鏈表*/

voidmergeList(LinkListLA,LinkListLB);

3.編寫一個(gè)算法，完成對一棵二叉樹的左右子樹的交換。二叉樹的存儲結(jié)構(gòu)如下：

typedefstructNode{

ElementTypedata;

structNode*left;

structNode*right;

)BTNode,*BTree;

4.暑假，小白準(zhǔn)備去一些城市旅游。有些城市之間有公路，有些城市之間則沒有，如下圖。為

了節(jié)省經(jīng)費(fèi)以及方便計(jì)劃旅程，小白希望在出發(fā)之前知道任意兩個(gè)城市之間的最短路徑。請

設(shè)計(jì)算法幫助小白解決這個(gè)問題！

溫州大學(xué)

2017年碩士研究生招生考試試題（A卷）

牛目代碼及名稱：831數(shù)據(jù)結(jié)構(gòu)適用專業(yè)：081201計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)081202

計(jì)算機(jī)軟件與理論

（請考生在答題紙上答題，在此試題紙上答題無效）

四、單項(xiàng)選擇題（每小題3分，共45分）

1.線性表中的每一個(gè)元素都有一個(gè)前驅(qū)和后繼元素。這個(gè)斷言是（）。

A.正確的B.錯(cuò)誤的

2.線性表的鏈接實(shí)現(xiàn)有利于（）運(yùn)算。

A插入B.讀表元C.查找D.定位

3.在一個(gè)帶有頭結(jié)點(diǎn)的單鏈表HL中，若要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行（）。

A.HL=p;p->next=HL;B.p->next=HL;HL=p;

C.p->next=Hl;p=HL;D.p->next=HL->next;HL->next=p;

4.字符A、B、C、D依次進(jìn)入一個(gè)棧，按出棧的先后順序組成不同的字符串，至多可以組成（）

個(gè)不同的字符串？

A.15B.14C.16D.21

5.采用鏈結(jié)構(gòu)存儲線性表時(shí)，其結(jié)點(diǎn)地址（）。

A.必須是連續(xù)的B.連續(xù)不連續(xù)都可以

C.部分地址必須是連續(xù)的D.必須是不連續(xù)的

6.隊(duì)列的刪除操作是在（）進(jìn)行。

A.隊(duì)首B.隊(duì)尾C.隊(duì)前D,對后

7.當(dāng)利用大小為N的數(shù)組順序存儲一個(gè)棧時(shí)，假定用top=N表示?？?，則退棧時(shí)，用（）語句

修改top指針。

A.top++;B.top=0;C.top—;D.top=N;

8.二叉樹的第i層上最多含有結(jié)點(diǎn)數(shù)為（）。

A.TB.2^-1C.2iuD.2i+1-l

9.完全二叉樹中，若一個(gè)結(jié)點(diǎn)沒有左孩子，則它必是葉子。這個(gè)斷言是（）。

A.正確的B.錯(cuò)誤的

10.不使用遞歸也可實(shí)現(xiàn)二叉樹的先序、中序和后序遍歷。這個(gè)斷言是（）。

A.正確的B.錯(cuò)誤的

11.對于下圖的AOE網(wǎng)中，計(jì)算頂點(diǎn)4所表示的事件最早發(fā)生時(shí)間丫以4）是（）。

A.6B.11C.12D.13

12.采用折半查找法對有序表進(jìn)行查找總比采用順序查找法對其進(jìn)行查找要快。這個(gè)斷言是（）。

A.正確的B.錯(cuò)誤的

13.已知數(shù)據(jù)序列為｛34,76,45,18,26,54,92,65｝,按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序

樹，則該樹的深度為（）。說明：如果樹只有一個(gè)結(jié)點(diǎn)，深度為1。

A.4B.5C.6D.7

14.有一棵平衡二叉樹，它的廣義表表示為40（30,130（60,150））,在它中插入關(guān)鍵字50后，重新調(diào)整

得到一棵新平衡二叉樹，在新平衡二叉樹中，關(guān)鍵字60所在結(jié)點(diǎn)的左、右子結(jié)點(diǎn)的關(guān)鍵字分別是（）。

A.30,130B.30,150C.40,130D.50,130

15.對不穩(wěn)定的排序算法，不論采用何種描述方式，總能舉出一個(gè)說明它不穩(wěn)定的實(shí)例來。這個(gè)斷言

是（）。

A.正確的B.錯(cuò)誤的

五、簡答題（每個(gè)小問5分，共35分）

1.已知二叉樹的后序遍歷序列為41253,中序遍歷序列為45213,則它的先序遍歷序列？

2.以｛3,7,8,2,6,10,14）為，權(quán)值構(gòu)造一棵Huffman樹，這棵Huffman樹的WPL?

3.對于下圖，按照Kruskal算法構(gòu)造它的-一棵最小生成樹，拭寫出在最小生成樹中依次得到的各條邊。

4.對一組關(guān)鍵字序列｛20,66,34,98,15,53,21,58,2,10,44,30｝,散列函數(shù)為H（key）=key%

13,表長為13。用線性探測法（F（i）=i）處理沖突，計(jì)算在等概率情況下查找成功的平均查找長度

和查找不成功的平均查找長度。

ASLSUCC=

^^?unsucc

5.給定關(guān)鍵字序列｛72,87,61,23,94,16,5,58｝,建小根堆。畫出小根堆。

6.設(shè)一組初始記錄關(guān)鍵字序列｛5,2,6,3,8）,以第一個(gè)記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的

結(jié)果？

六、算法填空題（每空2分，共30分）

1.本題針對線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，完成相應(yīng)的算法。

typedefintElementType;

typedefstructNode{

ElementTypedata;

structNode*next;

}Node,*LinkList;

voidoutputList(LinkListL)/*輸出帶頭結(jié)點(diǎn)的單鏈表*/

(

Node*p;

m；/*使p指向單鏈表的第i個(gè)結(jié)點(diǎn)*/

whHe(p!=NULL){

printf(p->data);

(2);/*p后移*/

)

)

voidinsertHead(LinkListL,ElementTypex)/*L指向頭結(jié)點(diǎn)。在單鏈表中插入一個(gè)結(jié)點(diǎn)。頭插法*/

(

/*開辟空間*/

___________L3)____________;

s->data=x;

/*鏈接*/

___________(42___________;

___________(5)___________;

2.下面是三元組表的存儲結(jié)構(gòu)及相應(yīng)的算法，完成相應(yīng)的算法。

typedefstruct{

introw,col;/*非零元素的行下標(biāo)和列下標(biāo)*/

ElementTypevalue;/*非零元素的值*/

{Triple;

#defineMAXSIZE1000/*非零元素個(gè)數(shù)最多為1000*/

typedefstrucl{/*非零元素的三元組表*/

Tripledata[MAXSIZE+1];/*data[0]不用*/

intm,n,number;/*矩陣的行數(shù)m,列數(shù)n和非零元素個(gè)數(shù)number*/

JTSMatrix;

/*采用”列序遞增”法，將矩陣A轉(zhuǎn)置為矩陣B*/

voidtransposeTSMatrix(TSMatrix*A,(6))

(

intcol,t,p;

B->m=A->n;

B->n=A->m;

B->number=A->number;

if(A->number>0)

(

p=0;/*記錄下標(biāo)*/

for(col=l;col<=___________(_22____________:col++){/*三元組表A的列值*/

/*從頭至尾掃描三元組表A,尋找列為col的三元組進(jìn)行轉(zhuǎn)置*/

for((8);t<=(9);t++){

if(A->data[t].col==col){

_____oo)_____;

B->data[p].row=A->data[t].col;

B->data[p].col=A->data[t].row;

B->data[p].value=A->data[t].value;

)

)

)

3.下面是圖的鄰接表存儲結(jié)構(gòu)及相應(yīng)的算法，完成相應(yīng)的算法。

#defineMAXVEX100/*最大頂點(diǎn)數(shù)*/

typedefcharVirtexType;

structALGraphStruct;

typedefstructALGraphStruct*ALGraph;

typedefstructEdgeNode{

intadj\fertex;/*該邊所指的頂點(diǎn)的位置*/

intweight;/*邊的權(quán)*/

structEdgeNode*nextEdge;/*指向下一條邊的指針*/

JEdgeNode;

typedefstructVNode{

XfertexTypedata;/*頂點(diǎn)信息*/

EdgeNode*firslEdge;/*指向第一條依附該頂點(diǎn)的邊的弧指針*/

}VNode;

structALGraphStruct{

VNodevexs[MAXVEX];

intvertexNum,edgeNum;/*圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)*/

)；

/*在無向網(wǎng)中插入一條邊。

插入的邊結(jié)點(diǎn)作為邊鏈表的第1個(gè)結(jié)點(diǎn)。

如果待插入的邊己存在，存儲小權(quán)值。*/

voidaddEdge(ALGraphg,\fertexTypevl,\fertexTypev2,intw)

(

EdgeNode

inti=locate\fertex(g,vl);/*找頂點(diǎn)vl的位置*/

intj=locate\fertex(g,v2);/*找頂點(diǎn)vl的位置*/

if(i==-l||j==-l)

__________CID___________;

s=findEdge(g,i,j);

if(s!=NULL){

t=findEdge(g,j,i);

if(s->weight>w){

s->weight=w;

(12);

return;

)

s=(EdgeNode*)malloc(sizeof(EdgeNode));

s?>adj\fertex=j;

s->weight=w;

__________03)___________;

g->vexs[i].firstEdge=s;

t=(EdgeNode*)malloc(sizeof(EdgeNode));

t->adj\fertex=i;

t->weight=w;

__________04)___________;

g->vexs[j].firstEdge=t;

(15);

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

i.按照給定的函數(shù)原型完成冒泡排序。（io分）

/*冒泡排序（升序）*/

voidbubbleSort（intr[],intn）;

2.下面是順序表的結(jié)構(gòu)，設(shè)計(jì)一個(gè)高效算法，在順序表中刪除所有元素值為x的元素，要求空間復(fù)

雜度為0（1）。假設(shè)順序表的數(shù)據(jù)元素類型為整型。（10分）

typedefintElementType;

typedefstruct{

ElementType*array;/*存放元素的數(shù)組*/

intlength;/*已經(jīng)有多少元素*/

intcapacity;/*容量*/

JSeqList;

3.下面是哈夫曼樹的存儲結(jié)構(gòu)，按照給定的函數(shù)原型完成求哈夫曼編碼算法。（20分）

#defineN20/*葉子結(jié)點(diǎn)數(shù)*/

typedefstruct{

intweight;/*結(jié)點(diǎn)的權(quán)值*/

intparent;/*雙親的下標(biāo)*/

intleft;/*左孩子結(jié)點(diǎn)的下標(biāo)*/

intright;/*右孩子結(jié)點(diǎn)的下標(biāo)*/

JHTNode,HTree;

/*從葉子結(jié)點(diǎn)到根，逆向求每個(gè)葉子結(jié)點(diǎn)對應(yīng)的哈夫曼編碼*/

/*第1個(gè)參數(shù)存儲哈夫曼樹，第2個(gè)參數(shù)存儲哈夫曼編碼，第3個(gè)參數(shù)是葉子數(shù)*/

voidcreateHuffmanCode（HTreeht[],char*hc[],intn）;

溫州大學(xué)

2018年碩士研究生招生考試試題（A卷）

斗目代碼及名稱：831數(shù)據(jù)結(jié)構(gòu)適用專業(yè)：081201計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)081202

計(jì)算機(jī)軟件與理論

（請考生在答題紙上答題，在此試題紙上答題無效）

八、單項(xiàng)選擇題（10小題，每小題4分，共40分）

1.計(jì)算機(jī)所處理的數(shù)據(jù)一般具有某種內(nèi)在聯(lián)系，這是指（）。

A.數(shù)據(jù)和數(shù)據(jù)之間存在某種關(guān)系

B.數(shù)據(jù)元素和數(shù)據(jù)元素之間存在某種關(guān)系

C.數(shù)據(jù)元素內(nèi)部具有某種結(jié)構(gòu)

D.數(shù)據(jù)項(xiàng)和數(shù)據(jù)項(xiàng)之間存在某種關(guān)系

2.順序存儲方式只能用于線性結(jié)構(gòu)，不能用于非線性結(jié)構(gòu)。這個(gè)斷言是（）。

A.正確的B.錯(cuò)誤的

3.設(shè)某算法完成對n個(gè)元素進(jìn)行處理，所需的時(shí)間是T（n）=100nlog2n+200n+500,則該算法的時(shí)間復(fù)

雜度是（）。

A.0（1）B.O（n）C.O（nlogn）D.O（nlogn+n）

4.采用順序存儲的兩個(gè)棧它的共享空間為lop[i]代表第i個(gè)棧（i=l,2）的棧頂，棧1的底

在S[l],棧2的底在S[m],則棧滿的條件是（）。

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

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

5.已知二叉樹有50個(gè)葉子結(jié)點(diǎn)，則該二叉樹的總結(jié)點(diǎn)數(shù)至少應(yīng)有（）個(gè)。

A.99B.100C.101D.102

6.無向圖G有16條邊，度為4的頂點(diǎn)有3個(gè)，度為3的頂點(diǎn)有4個(gè)，其余頂點(diǎn)的度均小于3,則圖

G至少有（）個(gè)頂點(diǎn)。

A.10B.11C.12D.13

7.對于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是（）。

A.nB.（n-l）/2C.n-1D.n2

8.適合于折半查找的表的存儲方式及元素排列要求為（）o

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

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

9.排序算法的穩(wěn)定性是指（）.

A.經(jīng)過排序之后，能使值相同的數(shù)據(jù)保持原順序中的相對位置不變

B.經(jīng)過排序之后，能使值相同的數(shù)據(jù)保持原順序中的絕對位置不變

C.排序算法的性能與待排序元素的數(shù)量關(guān)系不大

D.排序算法的性能與待排序元素的數(shù)量關(guān)系密切

10.5個(gè)不同的數(shù)據(jù)元素進(jìn)行直接插入排序，最多需要進(jìn)行（）次比較。

A.8B.14C.15D.25

九、簡答題（4小題，每小題10分，共40分）

1.找出滿足以下條件的所有二叉樹：（1）二叉樹的前序序列與中序序列相同；（2）二叉樹的中序序列

與后序序列相同；（3）二叉樹的前序序列與后序序列相同。

2.假設(shè)通訊電文中只用到A,B,C,D,E,F六個(gè)字母，它們在電文中出現(xiàn)的相對頻率分別為：8,

3,16,10,5,20。（1）構(gòu)造哈夫曼樹。（2）計(jì)算該哈夫曼樹的帶權(quán)路徑長度WPL。

3.己知序列{355,672,91,83,781,34,410,76,125,320},建大根堆。

4.已知序列{12,2,16,30,8,28,4,10,20,6,18},請按照下面的快速排序算法，給出該序列作升序排列

時(shí)前三趟的結(jié)果。

intpartition(ElementTyper[],intlow,inthigh)

intpivot;

pivot=r[low];

while(low<high){

while(low<high&&r[high]>=pivot){

high-;

)

r[low]=r[high];

while(low<high&&r[