2023年廣東財經(jīng)大學(xué)809數(shù)據(jù)結(jié)構(gòu)考研真題碩士研究生專業(yè)課考試試題_百

2023年12月9日發(fā)(作者：石榴的好處)

-

1 4

廣東財經(jīng)大學(xué)碩士研究生入學(xué)考試試卷

考試年度：2023年 　　　　考試科目代碼及名稱：809-數(shù)據(jù)結(jié)構(gòu)

適用專業(yè)：085404計算機技術(shù)

［友情提醒：請在考點提供的專用答題紙上答題，答在本卷或草稿紙上無效！］、

一、單選題（10題，每題1分，共10分）

1. 算法的時間復(fù)雜度取決于（ ）。

A.問題的規(guī)模 B.待處理數(shù)據(jù)的初態(tài) C.計算機的配置 D.A和B

2. 某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（ ）存儲方式最節(jié)省運算時間。

A．單鏈表 B．僅有頭指針的單循環(huán)鏈表

C．雙鏈表 D．僅有尾指針的單循環(huán)鏈表

3. 設(shè)一個棧的輸入序列是 1，2，3，4，5,則下列序列中，（ ）是棧的合法輸出序列。

A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4

4. 若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為( )。

A. 1和 5 B. 2和4 C. 4和2 D. 5和1

5. 下面關(guān)于串的的敘述中，（ ）是不正確的。

A．串是字符的有限序列 B．空串是由空格構(gòu)成的串

C．模式匹配是串的一種重要運算 D．串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯?

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

A．不確定 B．2n C．2n+1 D．2n-1

7. 具有k條邊的無向圖，對其鄰接矩陣的對稱性及非零元素的數(shù)量，下列說法正確的是（ ）。

A. 不對稱 2k個 B.對稱 2k個 C. 不對稱 k個 D. 對稱 k個

8. 對50個記錄的有序表作折半查找，當(dāng)查找失敗時，至少需要比較（ ）次關(guān)鍵字。

A．3 B．4 C．5 D．6

9. 不能保證每趟排序至少能將一個元素放到其最終位置上的排序方法是（ ）。

A. 插入排序 B. 快速排序 C. 冒泡排序 D. 堆排序

10. 下列幾種排序方法中，（ ）是穩(wěn)定的排序方法。

A. 堆排序、冒泡排序 B. 快速排序、堆排序

C.希爾排序、歸并排序 D. 歸并排序、冒泡排序

二、簡答題（5題，每題10分，共50分）

1. 以下是二叉鏈表存儲結(jié)構(gòu)的表示，s是初值為0的全局變量。假設(shè)已經(jīng)用二叉鏈表實

1 2 4

現(xiàn)了如圖1所示的二叉樹的存儲，指針root 指向其根結(jié)點。函數(shù)func( )的代碼如圖2所示：

typedef struct BiTNode

{ int data ;struct BiTNode *lchild, *rchild ;

}*BiTree; //二叉鏈表定義

int s=0; //全局變量s

圖1 根為root的二叉樹

int func(BiTree T)

{

if (T)

{ func(T->lchild);if (T->data%2!=0)

printf("%dt",T->data+10);

el s+=T->data;func(T->rchild);

return s;

}//if圖2 函數(shù)func( )的代碼}//func

圖2 函數(shù)function()的偽代碼根據(jù)以上描述回答問題：

（1）遞歸算法必須包括哪幾個部分？ （2分）

（2）描述func( )函數(shù)的基本功能，并說明該函數(shù)的遞歸終止條件。（4分）

（3）執(zhí)行語句printf(“n%dn”,func(root))后，按屏幕格式寫出相應(yīng)的輸出結(jié)果。（4分）

2.設(shè)一棵二叉樹的先序序列是：A B D E G C F H K，中序序列是：D B G E A C H F K。

（1）寫出這棵二叉樹的后序序列。 （3分）

（2）畫出這棵二叉樹的中序線索二叉樹。 （3分）

（3）將這棵二叉樹轉(zhuǎn)換為對應(yīng)的樹（或森林）。 （4分）

3.假設(shè)圖G如圖3所示，頂點的存儲順序如圖4所示：

V4V6圖3 圖G的拓?fù)浣Y(jié)構(gòu)V5V1V2V3根據(jù)上圖的拓?fù)浣Y(jié)構(gòu)和頂點順序，回答以下問題：

（1）畫出該圖的鄰接表存儲結(jié)構(gòu)。 （4分）

（2）根據(jù)所畫的鄰接表，從頂點v1開始按頂點存儲順序正向遍歷，寫出深度優(yōu)先遍歷序列。 （3分）

（3）根據(jù)所畫的鄰接表，從頂點v6開始按頂點存儲順序逆向遍歷，寫出廣度優(yōu)先遍歷序列。 （3分）

4. 假設(shè)散列表長度為11，散列函數(shù)為H(key)=key%7，現(xiàn)要將關(guān)鍵字值為{24，10，16，31，19，17}的記錄依次放入散列表中，請按要求回答問題：

（1）如果沖突處理方法為開放地址法，增量序列di=12，-12，22，-22，32，-32……，請

2 3 4

畫出相應(yīng)的散列表，并計算等概率下查找成功時的平均查找長度ASLsucc。 （5分）

（2）如果沖突處理方法為鏈地址法，請畫出對應(yīng)的散列表，并計算等概率下查找失敗時的平均查找長度ASLunsucc。 （5分）

5. 假設(shè)待排序元素的關(guān)鍵字序列為{ 78，55，86，45，60，100，70，98，35 }，試回答以下問題：

（1）寫出第一趟快速排序的執(zhí)行過程，要求寫出原始序列，之后每移動一次元素寫出一行。（5分）

（2）快速排序在什么情況下達(dá)到最佳時間性能？寫出最佳情況下的時間復(fù)雜度。（2分）

（3）為避免最壞情況的出現(xiàn)可采取什么優(yōu)化措施？寫出其基本思想。（3分）

三、綜合分析題（3題，每題30分，共90分）

1. 假設(shè)某班的班長創(chuàng)建如下圖所示的班級通訊錄，包括學(xué)號、姓名和電話號碼三項內(nèi)容并按學(xué)號遞增順序排列，對通訊錄的日常管理包括存儲、查詢和編輯（增刪改）。

Number(in型)

220501

220502

220503

220504

……

Name(char型)

張三

李四

王五

趙六

……

Telephone(int型)

185****2222185****4444185****6666185****8888……

如果你是班長，需要編程實現(xiàn)對通訊錄的日常管理，試回答以下問題：

（1）你認(rèn)為該通訊錄在內(nèi)存中處理時應(yīng)采用何種存儲結(jié)構(gòu)？請說明理由。（4分）

（2）根據(jù)你所采用的存儲結(jié)構(gòu)，寫出記錄的結(jié)構(gòu)定義和通訊錄的存儲表示。（6分）

（3）假如有同學(xué)要轉(zhuǎn)學(xué)離開班級，設(shè)計算法Delete( )實現(xiàn)下述功能：根據(jù)給定的姓名值查找該同學(xué)，如果找到則將該記錄從通訊錄中刪除，未找到則給出“該同學(xué)不在本班！”的提示信息。（10分）

（4）假如有新同學(xué)要插班進(jìn)來，設(shè)計算法Inrt( )實現(xiàn)下述功能：根據(jù)給定的學(xué)號查找是否存在對應(yīng)的記錄，如果未找到則將該記錄插入相應(yīng)位置依然保持按學(xué)號遞增有序，找到則用新記錄替換原記錄。（10分）

溫馨提示：算法首選用類C或其他語言的偽代碼描述，也可用自然語言或流程圖描述。

2. 某省的六個地級市（用符號A、B、C、D、E、F表示）之間計劃修建可雙向行駛的高速公路，從而實現(xiàn)任意兩個城市之間的連通。根據(jù)地質(zhì)結(jié)構(gòu)和經(jīng)費預(yù)算列出可能修建的高速路段以及預(yù)計費用（單位：億元）如下表所示：

城市1

A

A

A

B

B

C

C

C

城市2

B

C

D

C

E

D

E

F

3

預(yù)計費用（億元）

5

2

4

7

3

5

8

3 4 4

D

E

F

F

6

1

現(xiàn)在要解決的問題是如何以最少的建設(shè)費用、修建最少的高速路段以連通任意兩個城市。如果讓你設(shè)計施工方案，請根據(jù)以上信息回答問題：

（1）你認(rèn)為用什么數(shù)據(jù)結(jié)構(gòu)描述該問題？請根據(jù)上表信息畫出拓?fù)浣Y(jié)構(gòu)圖并標(biāo)出權(quán)值。

（3分）

（2）寫出你打算采用的存儲結(jié)構(gòu)表示，并設(shè)計Create( )算法創(chuàng)建基于該存儲結(jié)構(gòu)之上的相應(yīng)數(shù)據(jù)結(jié)構(gòu)。（12分）

（3）你認(rèn)為可以用什么算法解決該問題？請說明你選擇該算法的理由，然后按步驟畫出該算法的執(zhí)行過程。 （12分）

（4）假如每個路段的預(yù)計費用即為最終的實際費用，那么建成連通這六個地級市的高速公路的總費用是多少？ （3分）

溫馨提示：算法首選用類C或其他語言的偽代碼描述，也可用自然語言或流程圖描述。

3. 某班的期末考試結(jié)束了，班主任要計算全班同學(xué)的語文、數(shù)學(xué)、英語的三科總分，然后按照總分（Score）的降序排列并準(zhǔn)備獎勵排名前10的同學(xué)，要求排序不改變總分相同的同學(xué)原來的排列順序（比如：張三排在趙六的前面且總分相同，排序后仍保持張三排在趙六的前面）。假設(shè)如下所示的成績表采用順序存儲結(jié)構(gòu)，如果班主任委托你完成該項任務(wù)，請回答以下問題：

No

1

2

3

4

……

Name

張三

李四

王五

趙六

……

Chine

78.5

85.0

96.5

82.5

……

Maths

95.0

90.5

93.0

87.0

……

English

86.5

80.5

89.5

90.5

……

Score

260.0

256.0

279.0

260.0

……

（1）請寫出該成績表的順序存儲結(jié)構(gòu)的表示。（3分）

（2）要滿足排序要求，你認(rèn)為應(yīng)采取什么排序方法？請說明理由。（3分）

（3）根據(jù)你定義的存儲結(jié)構(gòu)，設(shè)計算法ScoreSort( )實現(xiàn)如下功能：假設(shè)每位同學(xué)的單科成績已經(jīng)錄入，先求出三科成績的相加和Score，再根據(jù)你選擇的排序方法按照Score的非遞增順序排序。（12分）

（4）在按總分排序后的成績表中按給定的總分進(jìn)行檢索，你認(rèn)為用什么查找方法效率較高，請說明理由。設(shè)計算法Search( )實現(xiàn)按總分檢索的功能，如果找到則返回該記錄全部信息，未找到則給出“未找到相應(yīng)記錄”的提示信息。（12分）

溫馨提示：算法首選用類C或其他語言的偽代碼描述，也可用自然語言或流程圖描述。

4

-