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

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

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

《數(shù)據(jù)結(jié)構(gòu)與算法》

一、考試要求說明

科目名稱：816數(shù)據(jù)結(jié)構(gòu)與算法

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

題型結(jié)構(gòu)：選擇題（45分）、填空題（30分）、算法編程題（35分）、應(yīng)用題（40分）

考試方式：閉卷、筆試

考試時(shí)間：3小時(shí)

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

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

第一章 數(shù)據(jù)結(jié)構(gòu)相關(guān)概念和術(shù)語

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

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

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

第二章 線性表

1.掌握線性表的概念，線性表抽象數(shù)據(jù)類型定義方法；理解線性表的邏輯結(jié)構(gòu)的特性；理解線性表的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)對(duì)應(yīng)關(guān)系。

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

3.掌握利用各類線性表并設(shè)計(jì)相關(guān)算法解決一些實(shí)際問題。

第三章 棧和隊(duì)列

1.掌握棧和隊(duì)列的基本概念。

2.理解棧和隊(duì)列相關(guān)存儲(chǔ)結(jié)構(gòu)（順序棧/鏈棧/循環(huán)隊(duì)列/鏈隊(duì)列）的基本操作的算法設(shè)計(jì)和編程實(shí)現(xiàn)；掌握不同結(jié)構(gòu)判斷空/滿的方法。

3.掌握利用棧和隊(duì)列并設(shè)計(jì)相關(guān)算法解決一些實(shí)際問題。

4.熟悉遞歸結(jié)構(gòu)實(shí)現(xiàn)的方法和過程，能分析遞歸結(jié)構(gòu)的性能。

第四章 串

1.熟悉串的定義、性質(zhì)、存儲(chǔ)和特點(diǎn)；串的基本操作的算法設(shè)計(jì)和編程實(shí)現(xiàn)。

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

3.了解串的實(shí)際應(yīng)用。

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

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

2.理解廣義表概念，能夠進(jìn)行廣義表運(yùn)算；理解廣義表存儲(chǔ)表示方法。

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

第六章 樹和二叉樹

1.掌握樹和二叉樹相關(guān)基本概念和術(shù)語。

2.掌握二叉樹的性質(zhì)及證明過程；掌握二叉樹的存儲(chǔ)結(jié)構(gòu)（順序/鏈?zhǔn)剑┑奶匦约皯?yīng)用。

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

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

5.掌握利用樹或二叉樹結(jié)構(gòu)并設(shè)計(jì)相關(guān)算法解決一些實(shí)際問題。

第七章 圖

1.掌握?qǐng)D的基本概念和術(shù)語；掌握?qǐng)D的各類存儲(chǔ)結(jié)構(gòu)（鄰接矩陣/鄰接表/逆鄰接表）的特性及應(yīng)用。

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

3.掌握兩種構(gòu)造最小生成樹的算法，并能分析算法時(shí)間復(fù)雜度和應(yīng)用場(chǎng)景；了解各種簡(jiǎn)單路徑及最短路徑的求解。

4.了解圖的其他應(yīng)用方法及程序?qū)崿F(xiàn)。

第八章 查找

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

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

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

第九章 排序

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

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

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

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

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

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

考試科目：816數(shù)據(jù)結(jié)構(gòu)與算法

考試時(shí)間：3小時(shí)

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

1.下面關(guān)于算法說法錯(cuò)誤的是()。

A．算法不一定要用高級(jí)語言描述

B．算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)

C．一個(gè)算法可以沒有輸入

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

2.下述各項(xiàng)中屬于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)點(diǎn)的是()。

A．插入運(yùn)算方便

B．提取某位置元素方便

C．存儲(chǔ)密度大

D．存儲(chǔ)完全二叉樹操作效率高

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

效率更高。

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

B．交換第1個(gè)元素與第2個(gè)元素的值

C．順序輸出這n個(gè)元素的值

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

4.對(duì)于順序表，訪問第i個(gè)位置的元素和在第i個(gè)位置插入一個(gè)元素的時(shí)間復(fù)

雜度為()。

A．O(1)，O(1)

B．O(n)，O(1)

C．O(1)，O(n)

D．O(n)，O(n)

5.入棧序列為ABC，出棧序列為BAC時(shí)，經(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.表達(dá)式a/(b-c)+d*e的后綴表達(dá)式是()。

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}只能是下列排序算法中的()兩

趟排序后的結(jié)果。

A．簡(jiǎn)單選擇排序

B．冒泡排序

C．直接插入排序

D．二路歸并排序

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

A．快速排序

B．希爾排序

C．堆排序

D．冒泡排序

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

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

A．692

B．693

C．689

D．690

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

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

A．a(chǎn)bcd

B．bcda

C．cbda

D．dcba

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

A．只有根結(jié)點(diǎn)

B．只有左孩子

C．只有右孩子

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

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

A．連通的

B．不連通的

C．無環(huán)的

D．有環(huán)的

13.在建立鄰接表時(shí)，若輸入的頂點(diǎn)信息即為頂點(diǎn)編號(hào)，則建立鄰接表的時(shí)間復(fù)

雜度為()。

A．O(n+e)

B．O(n*e)

C．O(n)

D．O(e)

14.構(gòu)建哈希表過程中，假設(shè)有k個(gè)關(guān)鍵字互為同義詞，若用線性探查法把這k

個(gè)關(guān)鍵字存入，至少要進(jìn)行的探查次數(shù)是()。

A．k-1

B．k

C．k+1

D．k(k+1)/2

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

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

B．左右對(duì)稱

C．完全二叉樹時(shí)

D．滿二叉樹時(shí)

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

1.以下代碼的時(shí)間復(fù)雜度為_________。

voidfun(intn){

inti=1;

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

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

3.將長(zhǎng)度為n的單鏈表鏈接在長(zhǎng)度為m的單鏈表的第5個(gè)元素之后，其算法的時(shí)間復(fù)雜度是________。

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

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

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

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

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

9.設(shè)森林F中有三棵樹，第一、第二、第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為M1、M2和M3。與森林F對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是__________。

10.設(shè)有5個(gè)結(jié)點(diǎn)的權(quán)值分別為{3,4,5,6,7}，根據(jù)這些權(quán)值構(gòu)造一棵Huffman樹，則該樹的帶權(quán)路徑長(zhǎng)度WPL為__________。

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

1．（10分）已知：btTree為二叉樹結(jié)點(diǎn)類型，其左右孩子指針域分別為lchild、rchild，數(shù)據(jù)域?yàn)閐ata，使用遞歸結(jié)構(gòu)求二叉樹的高度。

請(qǐng)?jiān)赿epth函數(shù)中編寫代碼，實(shí)現(xiàn)上述功能，注意要求采用遞歸結(jié)構(gòu)。

intdepth(btTree*t){

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

//請(qǐng)?jiān)诖颂幘帉懘a，實(shí)現(xiàn)本題的功能（每行一條語句，本題<14行）

}

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

請(qǐng)?jiān)赿eln函數(shù)中編寫代碼，實(shí)現(xiàn)上述功能，注意本題要求時(shí)間復(fù)雜度為O（n）

已知順序表結(jié)點(diǎn)類型為：

typedefstruct{

intelem[100];

intlength;

}SQ;

intdeln(SQ*L){

//請(qǐng)?jiān)诖颂幘帉懘a，實(shí)現(xiàn)本題的功能（每行一條語句，本題<12行）

}

3．（15分）已知遞增有序的帶頭結(jié)點(diǎn)單鏈表A、B(A、B的長(zhǎng)度分別為m、n，A中可能存在重復(fù)元素)，請(qǐng)?jiān)O(shè)計(jì)算法，以求出兩個(gè)單鏈表A和B的差集A-B，

結(jié)果示例如下：

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

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

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

請(qǐng)?jiān)贒ifference函數(shù)中編寫代碼，實(shí)現(xiàn)上述功能，本題要求：

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

已知單鏈表結(jié)點(diǎn)類型為：

typedefstructLNode{

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

structLNode*next;//指針域

}LNode;

voidDifference(LNode*A,LNode*B){

//請(qǐng)?jiān)诖颂幘帉懘a，實(shí)現(xiàn)本題的功能（每行一條語句，本題<18行）

}

四、應(yīng)用題（共40分）

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

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

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

以5為基準(zhǔn)，快速排序第一輪結(jié)果是：_______________；

二路歸并排序第一輪結(jié)果是：_______________。

3．(共7分)已知一個(gè)無向圖如下圖所示，用Prim算法生成最小樹(假設(shè)以②為起點(diǎn)，請(qǐng)?jiān)诶L制構(gòu)造過程)

所生成的最小生成樹的權(quán)值和為_______________。

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

123456

10080218

2000010

3000004

4213000

5004200

6000000

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

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

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

（3）頂點(diǎn)1到頂點(diǎn)6的最短路徑長(zhǎng)度是：_______________。

（4）請(qǐng)繪制該圖的逆鄰接表。

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

（1）請(qǐng)繪制該排序二叉樹。

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

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

（4）計(jì)算查找成功的平均查找長(zhǎng)度和查找不成功的平均查找長(zhǎng)度。

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