四川輕化工大學2024年考研初試大綱：816數(shù)據(jù)結構與算法

考研專業(yè)課大綱對備考具有重要價值。大綱可以幫助考生了解考試的整體結構和考查重點，在備考過程中起到明確方向的作用。大綱所列出的考試范圍和知識要點，可以幫助考生建立知識體系，明確重難點，有針對性地進行備考。同時，弄清大綱要求可以讓考生事先了解復習的時間分配和備考要求，避免在備考過程中盲目浪費時間和精力。以下是四川輕化工大學2024年碩士研究生招生考試《816數(shù)據(jù)結構與算法》考試大綱具體內(nèi)容，報考該校計算機專業(yè)相關方向的考生可以根據(jù)考試大綱備考。

四川輕化工大學碩士研究生招生考試大綱

《數(shù)據(jù)結構與算法》

一、考試要求說明

科目名稱：816數(shù)據(jù)結構與算法

適用專業(yè)：085404計算機技術、085411大數(shù)據(jù)技術與工程（計算機科學與工程學院）、085412網(wǎng)絡與信息安全

題型結構：選擇題（45分）、填空題（30分）、算法編程題（35分）、應用題（40分）

考試方式：閉卷、筆試

考試時間：3小時

參考書目：《數(shù)據(jù)結構（C語言版）》，清華大學出版社，2016.8

二、考試范圍和內(nèi)容

第一章 數(shù)據(jù)結構相關概念和術語

1.掌握數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)結構等基本概念；理解邏輯結構、存儲結構及數(shù)據(jù)結構在各種軟件系統(tǒng)中所起的作用。

2.理解邏輯結構、存儲結構及數(shù)據(jù)運算的含義及其相互關系；了解抽象數(shù)據(jù)類型的定義、表示和實現(xiàn)方法；能熟練使用C或C++語言進行的算法描述和編程。

3.理解算法的定義、基本特性和設計要求，算法分析的基本概念；掌握計算語句頻度和估算算法時間復雜度的方法；了解算法空間復雜度。

第二章 線性表

1.掌握線性表的概念，線性表抽象數(shù)據(jù)類型定義方法；理解線性表的邏輯結構的特性；理解線性表的邏輯結構與物理結構對應關系。

2.理解順序表和鏈表（如：單鏈表/循環(huán)鏈表/雙向鏈表）的基本操作的算法設計和編程實現(xiàn)，如：初始化、查找、插入、刪除、歸并等算法，并能對各類算法的時間復雜度進行分析，能根據(jù)實際應用選擇適當?shù)木€性表結構。

3.掌握利用各類線性表并設計相關算法解決一些實際問題。

第三章 棧和隊列

1.掌握棧和隊列的基本概念。

2.理解棧和隊列相關存儲結構（順序棧/鏈棧/循環(huán)隊列/鏈隊列）的基本操作的算法設計和編程實現(xiàn)；掌握不同結構判斷空/滿的方法。

3.掌握利用棧和隊列并設計相關算法解決一些實際問題。

4.熟悉遞歸結構實現(xiàn)的方法和過程，能分析遞歸結構的性能。

第四章 串

1.熟悉串的定義、性質、存儲和特點；串的基本操作的算法設計和編程實現(xiàn)。

2.理解串的樸素模式匹配算法、KMP算法等匹配算法及優(yōu)化。

3.了解串的實際應用。

第五章 數(shù)組與廣義表

1.掌握數(shù)組的兩種存儲表示方法。

2.理解廣義表概念，能夠進行廣義表運算；理解廣義表存儲表示方法。

3.了解數(shù)組與廣義表的實際應用。

第六章 樹和二叉樹

1.掌握樹和二叉樹相關基本概念和術語。

2.掌握二叉樹的性質及證明過程；掌握二叉樹的存儲結構（順序/鏈式）的特性及應用。

3.掌握各種方式（先序/中序/后序/層次）遍歷二叉樹的遞歸和非遞歸算法設計和編程實現(xiàn)；理解前/中/后綴表達式、線索二叉樹的基本概念。

4.理解樹(森林)的各類存儲結構，樹(森林)和二叉樹相互轉換方法；了解樹(森林)的遍歷；掌握哈夫曼(Huffman)樹的構建算法及哈夫曼編碼方法。

5.掌握利用樹或二叉樹結構并設計相關算法解決一些實際問題。

第七章 圖

1.掌握圖的基本概念和術語；掌握圖的各類存儲結構（鄰接矩陣/鄰接表/逆鄰接表）的特性及應用。

2.理解圖結構遍歷的邏輯定義；掌握深度優(yōu)先搜索的兩種形式（遞歸和非遞歸）和廣度優(yōu)先搜索的算法設計和編程實現(xiàn)；

3.掌握兩種構造最小生成樹的算法，并能分析算法時間復雜度和應用場景；了解各種簡單路徑及最短路徑的求解。

4.了解圖的其他應用方法及程序實現(xiàn)。

第八章 查找

1.掌握靜態(tài)查找表概念，運算方法；掌握順序表、有序表查找方法的算法設計和編程實現(xiàn)，并能對算法性能進行分析；了解索引順序表的查找算法。

2.理解二叉排序樹和平衡二叉樹的生成以及其他操作方法，并分析算法性能；了解B-樹和B+樹特點及運算方法。

3.掌握哈希表特點、各種哈希函數(shù)構造方法、各種處理沖突的方法，能對哈希查找的性能分析。

第九章 排序

1.掌握內(nèi)部排序概念及作用；理解常見內(nèi)部排序，如：插入排序（直接/折半/希爾）、交換排序（冒泡/快排）、選擇排序（簡單/堆排序）、歸并排序及其優(yōu)化算法的原理、算法設計和編程實現(xiàn)，并能對算法復雜度進行分析；了解基數(shù)排序的思路。

2.理解給定排序算法進行分析比較，包含移動次數(shù)、平時/最壞時間復雜度、輔助存儲空間復雜度、穩(wěn)定性等等。

3.了解外部排序的概念。

四川輕化工大學2024年研究生招生考試業(yè)務課樣卷

（滿分：150分，所有答案一律寫在答題紙上）

招生專業(yè)：085404計算機技術、085411大數(shù)據(jù)技術與工程、085412網(wǎng)絡與信息安全

考試科目：816數(shù)據(jù)結構與算法

考試時間：3小時

一、選擇題（每題3分，共45分）

1.下面關于算法說法錯誤的是()。

A．算法不一定要用高級語言描述

B．算法最終必須由計算機程序實現(xiàn)

C．一個算法可以沒有輸入

D．算法的確定性是指指令不能有二義性

2.下述各項中屬于鏈式存儲結構優(yōu)點的是()。

A．插入運算方便

B．提取某位置元素方便

C．存儲密度大

D．存儲完全二叉樹操作效率高

3.設線性表有n個元素，以下操作中，()在順序表上實現(xiàn)比在鏈表上實現(xiàn)

效率更高。

A．輸出第i（1<=i<=n）個元素值

B．交換第1個元素與第2個元素的值

C．順序輸出這n個元素的值

D．輸出與給定值x相等的元素在線性表中的序號

4.對于順序表，訪問第i個位置的元素和在第i個位置插入一個元素的時間復

雜度為()。

A．O(1)，O(1)

B．O(n)，O(1)

C．O(1)，O(n)

D．O(n)，O(n)

5.入棧序列為ABC，出棧序列為BAC時，經(jīng)過的棧操作為()。

A．push,pop,push,pop,push,pop

B．push,push,push,pop,pop,pop

C．push,push,pop,pop,push,pop

D．push,push,pop,push,pop,pop

6.表達式a/(b-c)+d*e的后綴表達式是()。

A．a(chǎn)b/c-d+e*

B．a(chǎn)bc/-de+*

C．a(chǎn)bcde*+-/

D．a(chǎn)bc-/de*+

7.數(shù)據(jù)序列{8，4，9，5，6，1，2，10，20}只能是下列排序算法中的()兩

趟排序后的結果。

A．簡單選擇排序

B．冒泡排序

C．直接插入排序

D．二路歸并排序

8.以下排序算法中，()不能保證每趟排序至少能將一個元素放在其最終位置上。

A．快速排序

B．希爾排序

C．堆排序

D．冒泡排序

9.設有一個二維數(shù)組A[m][n]，設A[0][0]存放位置在644，A[2][2]存放位置在

676，每個元素占一個空間，問A[3][3]存放在()位置。

A．692

B．693

C．689

D．690

10.若一棵二叉樹的前序遍歷序列和后序遍歷序列分別為acbd和dcba，則該二

叉樹的中序遍歷序列不會是()。

A．a(chǎn)bcd

B．bcda

C．cbda

D．dcba

11.如果一棵二叉樹的先序和中序遍歷恰好相同，則該二叉樹的特點是()。

A．只有根結點

B．只有左孩子

C．只有右孩子

D．后序遍歷和先序遍歷相反

12.一個有N個頂點和N條邊的無向圖，一定是()。

A．連通的

B．不連通的

C．無環(huán)的

D．有環(huán)的

13.在建立鄰接表時，若輸入的頂點信息即為頂點編號，則建立鄰接表的時間復

雜度為()。

A．O(n+e)

B．O(n*e)

C．O(n)

D．O(e)

14.構建哈希表過程中，假設有k個關鍵字互為同義詞，若用線性探查法把這k

個關鍵字存入，至少要進行的探查次數(shù)是()。

A．k-1

B．k

C．k+1

D．k(k+1)/2

15.二叉排序樹的查找效率與二叉樹的樹型有關，在()時其查找效率最低。

A．呈單支樹形態(tài)

B．左右對稱

C．完全二叉樹時

D．滿二叉樹時

二、填空題（每題3分，共30分）

1.以下代碼的時間復雜度為_________。

voidfun(intn){

inti=1;

while(i<=n)i*=2;}

2.給定數(shù)值大小無序的n個元素的一維數(shù)組，建立一個有序單鏈表的最低時間復雜度是________。

3.將長度為n的單鏈表鏈接在長度為m的單鏈表的第5個元素之后，其算法的時間復雜度是________。

4.表達式3+2*3/(5-2+8*3)求值過程中當描到8時，操作數(shù)棧內(nèi)容為____________。(從棧底依次寫)

5.在循環(huán)隊列中，若front與rear分別表示對頭元素和隊尾元素的位置，則判斷循環(huán)隊列空的條件是__________。

6.字符串S長度是m，模式串P的長度是n，則經(jīng)典字符串匹配算法(BF算法)的時間復雜度是__________。

7.廣義表A=(a,b,(c,d),e)，寫出得到字符d的操作(取表頭用H，表尾用T表示)__________。

8.已知一棵完全二叉樹的第7層(設根為第1層)有8個葉子結點，則該完全二叉樹的結點個數(shù)最多有__________個。

9.設森林F中有三棵樹，第一、第二、第三棵樹的結點個數(shù)分別為M1、M2和M3。與森林F對應的二叉樹根結點的右子樹上的結點個數(shù)是__________。

10.設有5個結點的權值分別為{3,4,5,6,7}，根據(jù)這些權值構造一棵Huffman樹，則該樹的帶權路徑長度WPL為__________。

三、算法編程題（共35分）

1．（10分）已知：btTree為二叉樹結點類型，其左右孩子指針域分別為lchild、rchild，數(shù)據(jù)域為data，使用遞歸結構求二叉樹的高度。

請在depth函數(shù)中編寫代碼，實現(xiàn)上述功能，注意要求采用遞歸結構。

intdepth(btTree*t){

inth,lh,rh;//分別為樹、左子樹、右子樹的高度變量

//請在此處編寫代碼，實現(xiàn)本題的功能（每行一條語句，本題<14行）

}

2．（10分）編程實現(xiàn)將順序表L中所有負數(shù)元素刪除，返回被刪除的元素個數(shù)。

請在deln函數(shù)中編寫代碼，實現(xiàn)上述功能，注意本題要求時間復雜度為O（n）

已知順序表結點類型為：

typedefstruct{

intelem[100];

intlength;

}SQ;

intdeln(SQ*L){

//請在此處編寫代碼，實現(xiàn)本題的功能（每行一條語句，本題<12行）

}

3．（15分）已知遞增有序的帶頭結點單鏈表A、B(A、B的長度分別為m、n，A中可能存在重復元素)，請設計算法，以求出兩個單鏈表A和B的差集A-B，

結果示例如下：

原A鏈表：1，2，2，3，4，5，5，8，10

原B鏈表：3，5，6，8，12

做差集后A鏈表：1，2，2，4，10

請在Difference函數(shù)中編寫代碼，實現(xiàn)上述功能，本題要求：

（1）直接在單鏈表A上做操作，不能額外申請存儲空間，并保持元素的遞增有序性。（2）時間復雜度為O(m+n)。

已知單鏈表結點類型為：

typedefstructLNode{

ElemTypedata;//數(shù)據(jù)域

structLNode*next;//指針域

}LNode;

voidDifference(LNode*A,LNode*B){

//請在此處編寫代碼，實現(xiàn)本題的功能（每行一條語句，本題<18行）

}

四、應用題（共40分）

1．(共7分)一顆二叉樹的先序序列是abdcefg，中序序列是adbfegc，請畫出這棵樹，并求出其后序序列。

2．(共6分)已知一個無序序列{5,3,1,7,6,9,4,8,2}，則：

希爾排序法(dk=3)排序第一輪結果是：_______________；

以5為基準，快速排序第一輪結果是：_______________；

二路歸并排序第一輪結果是：_______________。

3．(共7分)已知一個無向圖如下圖所示，用Prim算法生成最小樹(假設以②為起點，請在繪制構造過程)

所生成的最小生成樹的權值和為_______________。

4．(共9分)已知某圖的鄰接矩陣如下。

123456

10080218

2000010

3000004

4213000

5004200

6000000

（1）自頂點1出發(fā)進行深度優(yōu)先遍歷所得的遍歷序列是：_______________，

（2）自頂點2出發(fā)進行廣度優(yōu)先遍歷所得的遍歷序列是：_______________。

(注：(1)(2)兩小題采用小序號優(yōu)先原則，無需任何分隔符)

（3）頂點1到頂點6的最短路徑長度是：_______________。

（4）請繪制該圖的逆鄰接表。

5．(共11分)根據(jù)以下元素建立一棵排序二叉樹，{7，3，5，15，11，1，9，13}

（1）請繪制該排序二叉樹。

（2）該二叉樹是否為平衡二叉樹？

（3）若查找12，將依次哪些元素比較？

（4）計算查找成功的平均查找長度和查找不成功的平均查找長度。

原文鏈接：https://yjs.suse.edu.cn/p/0/?StId=st_app_news_i_x638254480786982714