2023年廣東財經大學研究生自主命題考試真題 809 數據結構

2023年12月2日發(作者：輪的組詞)

-

廣東財經大學碩士研究生入學考試試卷

考試年度：2023年 考試科目代碼及名稱：809-數據結構

適用專業：085404計算機技術

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

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

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

A.問題的規模 B.待處理數據的初態 C.計算機的配置 D.A和B

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

A．單鏈表 B．僅有頭指針的單循環鏈表

C．雙鏈表 D．僅有尾指針的單循環鏈表

3. 設一個棧的輸入序列是 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的數組來實現循環隊列，且當前rear和front的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為( )。

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

5. 下面關于串的的敘述中，（ ）是不正確的。

A．串是字符的有限序列 B．空串是由空格構成的串

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

6. 設給定權值總數有n個，其哈夫曼樹的結點總數為( ) 個。

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

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

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

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

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

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

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

10. 下列幾種排序方法中，（ ）是穩定的排序方法。

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

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

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

1. 以下是二叉鏈表存儲結構的表示，s是初值為0的全局變量。假設已經用二叉鏈表實現了如圖1所示的二叉樹的存儲，指針root 指向其根結點。函數func( )的代碼如圖2所示：

1

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;

圖2 函數func( )的代碼

}//if

}//func

圖2 函數function()的偽代碼

根據以上描述回答問題：

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

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

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

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

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

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

（3）將這棵二叉樹轉換為對應的樹（或森林）。 （4分）

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

V4

V6

圖3 圖G的拓撲結構

V5

V1

V2

V3

根據上圖的拓撲結構和頂點順序，回答以下問題：

（1）畫出該圖的鄰接表存儲結構。 （4分）

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

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

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

（1）如果沖突處理方法為開放地址法，增量序列di=12，-12，22，-22，32，-32……，請畫出相應的散列表，并計算等概率下查找成功時的平均查找長度ASLsucc。 （5分）

（2）如果沖突處理方法為鏈地址法，請畫出對應的散列表，并計算等概率下查找失敗

2 時的平均查找長度ASLunsucc。 （5分）

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

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

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

（3）為避免最壞情況的出現可采取什么優化措施？寫出其基本思想。（3分）

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

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

Number(in型)

220501

220502

220503

220504

……

Name(char型)

張三

李四

王五

趙六

……

Telephone(int型)

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

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

（1）你認為該通訊錄在內存中處理時應采用何種存儲結構？請說明理由。（4分）

（2）根據你所采用的存儲結構，寫出記錄的結構定義和通訊錄的存儲表示。（6分）

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

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

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

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

城市1

A

A

A

B

B

C

C

C

D

E

城市2

B

C

D

C

E

D

E

F

F

F

3

預計費用（億元）

5

2

4

7

3

5

8

3

6

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

（1）你認為用什么數據結構描述該問題？請根據上表信息畫出拓撲結構圖并標出權值。

（3分）

（2）寫出你打算采用的存儲結構表示，并設計Create( )算法創建基于該存儲結構之上的相應數據結構。（12分）

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

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

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

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

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）請寫出該成績表的順序存儲結構的表示。（3分）

（2）要滿足排序要求，你認為應采取什么排序方法？請說明理由。（3分）

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

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

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

4

-