數據結構試題-溫州大學2021年碩士研究生招生考試專業(yè)課真題

絕密★考試結束前溫州大學

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

科目代碼及名稱：826數據結構

適用專業(yè)（方向）：081200計算機科學與技術

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

一、單項選擇題（共10小題，每小題4分，共40分）

1.數組的邏輯結構不同于下列（）的邏輯結構。

A.線性表B.棧

C.隊列D.樹

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

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

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

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

存儲空間。

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

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

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

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

5.設有一個二維數組Data[m][n],假設Data[0][0]存放位置在921,Data⑵⑵存放位置在965,每

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

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

第1頁共9頁

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

個元素出棧后即進入隊列Que。若6個元素出列的順序為。、a4、a3、a6、a5和al,則棧Stack

的容量至少應該是()。

A.6B.4

C.3D.2

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

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

C.歸并排序D.堆排序

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

個空的引用域。

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

9.設一組初始記錄關鍵字序列(25,12,26,23,38),以第一個記錄關鍵字25為基準進行一趟

快速排序的結果為()。

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

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

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

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

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

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

第2頁共9頁

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

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

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

（1）實現由先序、中序構造二叉樹程序（7分）。

（2）畫出構造的二叉樹（3分）。

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

typedefstructNode{

ElementTypedata;

structNode*left;

structNode*right;

JBTNode,*BTree;

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

〃先序、中序遍歷構造二叉樹

〃bl,H分別是先序序列的下界（下標）和上界（下標）

〃b2,t2分別是中序序列的下界（下標）和上界（下標）

BTreecreateBTree（intbl,inttl,intb2,intt2）

第3頁共9頁

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

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

（注：從圖2開始，根據算法過程，每幅圖依次增加一個頂點及相應的邊。圖n中應保留圖n-1

的所有頂點和邊。）

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

圖1圖2圖3

第4頁共9頁

3.雙鏈表的數據結構如下所示。請實現在雙鏈表的表頭節(jié)點之后插入新節(jié)點操作。

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

typedefstructDNode〃數據結構

(

ELEMTYPdata;

structDNode*prev;

structDNode*next;

}DNode;

typedefstructDoubleLinkedList〃數據結構

(

DNode*head;

intlen;

}DoubleLinkedList;

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

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

下要求。

（1）繪出調整后的平衡二叉樹（6分）。

（2）指出這種失衡的類型并簡要其調整過程（4分）。

第5頁共9頁

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

請回答下列問題:

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

V0VIV2V3V4V5

最早發(fā)生時間

最晚發(fā)生時間

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

ala2a3a4a5a6a7a8

最早開始時間

最晚開始時間

（3）關鍵路徑：；關鍵路徑的長度：（2分）。

第6頁共9頁

三、綜合應用題(共4小題，每小題15分，共60分)

1.調整整數數組array口中的元素位置,并返回分界位置L使所有值為奇數的元素均落在array[l..i]

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

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

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

/*順序表結構*/

typedefintElementType;

typedefstruct{

ElementTypearray[MAXI;/*存放元素的數組刃

intlength;/*已經有多少元素*/

intcapacity;/*容量*/

}*SeqList;

intarrange(SeqListlist)

第7頁共9頁

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

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

（2）計算圖中各頂點的出度、入度和度（6分）。

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

3.假設用于通信的電文由字符集｛4'3&%[811｝中的字符組成，這8個字符在電文中出現的

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

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

（2）計算最小帶權路徑和（3分）。

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

第8頁共9頁

4.編寫一個算法，用下面指定的鏈表結構實現兩個多項式相加。如LA:2X2+3,LB:3X3+X2+1,LA和