四川轻化工大学2024年考研初试大纲：816数据结构与算法

考研专业课大纲对备考具有重要价值。大纲可以帮助考生了解考试的整体结构和考查重点，在备考过程中起到明确方向的作用。大纲所列出的考试范围和知识要点，可以帮助考生建立知识体系，明确重难点，有针对性地进行备考。同时，弄清大纲要求可以让考生事先了解复习的时间分配和备考要求，避免在备考过程中盲目浪费时间和精力。以下是四川轻化工大学2024年硕士研究生招生考试《816数据结构与算法》考试大纲具体内容，报考该校计算机专业相关方向的考生可以根据考试大纲备考。

四川轻化工大学硕士研究生招生考试大纲

《数据结构与算法》

一、考试要求说明

科目名称：816数据结构与算法

适用专业：085404计算机技术、085411大数据技术与工程（计算机科学与工程学院）、085412网络与信息安全

题型结构：选择题（45分）、填空题（30分）、算法编程题（35分）、应用题（40分）

考试方式：闭卷、笔试

考试时间：3小时

参考书目：《数据结构（C语言版）》，清华大学出版社，2016.8

二、考试范围和内容

第一章 数据结构相关概念和术语

1.掌握数据、数据元素、数据项、数据结构等基本概念；理解逻辑结构、存储结构及数据结构在各种软件系统中所起的作用。

2.理解逻辑结构、存储结构及数据运算的含义及其相互关系；了解抽象数据类型的定义、表示和实现方法；能熟练使用C或C++语言进行的算法描述和编程。

3.理解算法的定义、基本特性和设计要求，算法分析的基本概念；掌握计算语句频度和估算算法时间复杂度的方法；了解算法空间复杂度。

第二章 线性表

1.掌握线性表的概念，线性表抽象数据类型定义方法；理解线性表的逻辑结构的特性；理解线性表的逻辑结构与物理结构对应关系。

2.理解顺序表和链表（如：单链表/循环链表/双向链表）的基本操作的算法设计和编程实现，如：初始化、查找、插入、删除、归并等算法，并能对各类算法的时间复杂度进行分析，能根据实际应用选择适当的线性表结构。

3.掌握利用各类线性表并设计相关算法解决一些实际问题。

第三章 栈和队列

1.掌握栈和队列的基本概念。

2.理解栈和队列相关存储结构（顺序栈/链栈/循环队列/链队列）的基本操作的算法设计和编程实现；掌握不同结构判断空/满的方法。

3.掌握利用栈和队列并设计相关算法解决一些实际问题。

4.熟悉递归结构实现的方法和过程，能分析递归结构的性能。

第四章 串

1.熟悉串的定义、性质、存储和特点；串的基本操作的算法设计和编程实现。

2.理解串的朴素模式匹配算法、KMP算法等匹配算法及优化。

3.了解串的实际应用。

第五章 数组与广义表

1.掌握数组的两种存储表示方法。

2.理解广义表概念，能够进行广义表运算；理解广义表存储表示方法。

3.了解数组与广义表的实际应用。

第六章 树和二叉树

1.掌握树和二叉树相关基本概念和术语。

2.掌握二叉树的性质及证明过程；掌握二叉树的存储结构（顺序/链式）的特性及应用。

3.掌握各种方式（先序/中序/后序/层次）遍历二叉树的递归和非递归算法设计和编程实现；理解前/中/后缀表达式、线索二叉树的基本概念。

4.理解树(森林)的各类存储结构，树(森林)和二叉树相互转换方法；了解树(森林)的遍历；掌握哈夫曼(Huffman)树的构建算法及哈夫曼编码方法。

5.掌握利用树或二叉树结构并设计相关算法解决一些实际问题。

第七章 图

1.掌握图的基本概念和术语；掌握图的各类存储结构（邻接矩阵/邻接表/逆邻接表）的特性及应用。

2.理解图结构遍历的逻辑定义；掌握深度优先搜索的两种形式（递归和非递归）和广度优先搜索的算法设计和编程实现；

3.掌握两种构造最小生成树的算法，并能分析算法时间复杂度和应用场景；了解各种简单路径及最短路径的求解。

4.了解图的其他应用方法及程序实现。

第八章 查找

1.掌握静态查找表概念，运算方法；掌握顺序表、有序表查找方法的算法设计和编程实现，并能对算法性能进行分析；了解索引顺序表的查找算法。

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

3.掌握哈希表特点、各种哈希函数构造方法、各种处理冲突的方法，能对哈希查找的性能分析。

第九章 排序

1.掌握内部排序概念及作用；理解常见内部排序，如：插入排序（直接/折半/希尔）、交换排序（冒泡/快排）、选择排序（简单/堆排序）、归并排序及其优化算法的原理、算法设计和编程实现，并能对算法复杂度进行分析；了解基数排序的思路。

2.理解给定排序算法进行分析比较，包含移动次数、平时/最坏时间复杂度、辅助存储空间复杂度、稳定性等等。

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

四川轻化工大学2024年研究生招生考试业务课样卷

（满分：150分，所有答案一律写在答题纸上）

招生专业：085404计算机技术、085411大数据技术与工程、085412网络与信息安全

考试科目：816数据结构与算法

考试时间：3小时

一、选择题（每题3分，共45分）

1.下面关于算法说法错误的是()。

A．算法不一定要用高级语言描述

B．算法最终必须由计算机程序实现

C．一个算法可以没有输入

D．算法的确定性是指指令不能有二义性

2.下述各项中属于链式存储结构优点的是()。

A．插入运算方便

B．提取某位置元素方便

C．存储密度大

D．存储完全二叉树操作效率高

3.设线性表有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时，经过的栈操作为()。

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．ab/c-d+e*

B．abc/-de+*

C．abcde*+-/

D．abc-/de*+

7.数据序列{8，4，9，5，6，1，2，10，20}只能是下列排序算法中的()两

趟排序后的结果。

A．简单选择排序

B．冒泡排序

C．直接插入排序

D．二路归并排序

8.以下排序算法中，()不能保证每趟排序至少能将一个元素放在其最终位置上。

A．快速排序

B．希尔排序

C．堆排序

D．冒泡排序

9.设有一个二维数组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．abcd

B．bcda

C．cbda

D．dcba

11.如果一棵二叉树的先序和中序遍历恰好相同，则该二叉树的特点是()。

A．只有根结点

B．只有左孩子

C．只有右孩子

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

12.一个有N个顶点和N条边的无向图，一定是()。

A．连通的

B．不连通的

C．无环的

D．有环的

13.在建立邻接表时，若输入的顶点信息即为顶点编号，则建立邻接表的时间复

杂度为()。

A．O(n+e)

B．O(n*e)

C．O(n)

D．O(e)

14.构建哈希表过程中，假设有k个关键字互为同义词，若用线性探查法把这k

个关键字存入，至少要进行的探查次数是()。

A．k-1

B．k

C．k+1

D．k(k+1)/2

15.二叉排序树的查找效率与二叉树的树型有关，在()时其查找效率最低。

A．呈单支树形态

B．左右对称

C．完全二叉树时

D．满二叉树时

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

1.以下代码的时间复杂度为_________。

voidfun(intn){

inti=1;

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

2.给定数值大小无序的n个元素的一维数组，建立一个有序单链表的最低时间复杂度是________。

3.将长度为n的单链表链接在长度为m的单链表的第5个元素之后，其算法的时间复杂度是________。

4.表达式3+2*3/(5-2+8*3)求值过程中当描到8时，操作数栈内容为____________。(从栈底依次写)

5.在循环队列中，若front与rear分别表示对头元素和队尾元素的位置，则判断循环队列空的条件是__________。

6.字符串S长度是m，模式串P的长度是n，则经典字符串匹配算法(BF算法)的时间复杂度是__________。

7.广义表A=(a,b,(c,d),e)，写出得到字符d的操作(取表头用H，表尾用T表示)__________。

8.已知一棵完全二叉树的第7层(设根为第1层)有8个叶子结点，则该完全二叉树的结点个数最多有__________个。

9.设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是__________。

10.设有5个结点的权值分别为{3,4,5,6,7}，根据这些权值构造一棵Huffman树，则该树的带权路径长度WPL为__________。

三、算法编程题（共35分）

1．（10分）已知：btTree为二叉树结点类型，其左右孩子指针域分别为lchild、rchild，数据域为data，使用递归结构求二叉树的高度。

请在depth函数中编写代码，实现上述功能，注意要求采用递归结构。

intdepth(btTree*t){

inth,lh,rh;//分别为树、左子树、右子树的高度变量

//请在此处编写代码，实现本题的功能（每行一条语句，本题<14行）

}

2．（10分）编程实现将顺序表L中所有负数元素删除，返回被删除的元素个数。

请在deln函数中编写代码，实现上述功能，注意本题要求时间复杂度为O（n）

已知顺序表结点类型为：

typedefstruct{

intelem[100];

intlength;

}SQ;

intdeln(SQ*L){

//请在此处编写代码，实现本题的功能（每行一条语句，本题<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函数中编写代码，实现上述功能，本题要求：

（1）直接在单链表A上做操作，不能额外申请存储空间，并保持元素的递增有序性。（2）时间复杂度为O(m+n)。

已知单链表结点类型为：

typedefstructLNode{

ElemTypedata;//数据域

structLNode*next;//指针域

}LNode;

voidDifference(LNode*A,LNode*B){

//请在此处编写代码，实现本题的功能（每行一条语句，本题<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出发进行深度优先遍历所得的遍历序列是：_______________，

（2）自顶点2出发进行广度优先遍历所得的遍历序列是：_______________。

(注：(1)(2)两小题采用小序号优先原则，无需任何分隔符)

（3）顶点1到顶点6的最短路径长度是：_______________。

（4）请绘制该图的逆邻接表。

5．(共11分)根据以下元素建立一棵排序二叉树，{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