991“数据结构与C语言程序设计”考试大纲（2020版）

2020年“数据结构与C语言程序设计”考试内容包括“数据结构”与“C语言程序设计”两门课程的内容，各占比例50%。试卷满分为150分。

“数据结构”部分

一、概述

1．数据的逻辑结构与存储结构的基本概念；

2．算法的定义、基本性质以及算法分析的基本概念，包括采用大O形式表示时间复杂度和空间复杂度。

二、线性表

1．线性关系、线性表的定义，线性表的基本操作；

2．线性表的顺序存储结构与链式存储结构(包括单(向)链表、循环链表和双向链表)的构造原理；

3．在以上两种存储结构的基础上对线性表实施的基本操作，包括顺序表的插入与删除、链表的建立、插入与删除、查找等操作对应的算法设计(含递归算法的设计)。

三、数组

1．一维数组和二维数组的存储；

2．矩阵的压缩存储的基本概念；

3．对称矩阵、对角矩阵以及三角矩阵的压缩存储。

四、堆栈与队列

1．堆栈与队列的基本概念与基本操作；

2．堆栈与队列的顺序存储结构与链式存储结构的构造原理；

3．在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作的算法设计；

4．堆栈和队列在解决实际问题中应用。

五、树与二叉树

1．树与二叉树的基本概念，基本特征、名词术语；

2．完全二叉树与满二叉树的基本概念，二叉树的基本性质及其应用；

3．二叉树的顺序存储结构与二叉链表存储结的基本原理；

4．二叉树的前序遍历、中序遍历、后序遍历和按层次遍历，重点是二叉树在以二叉链表作为存储结构基础上各种遍历算法(包括非递归算法)的设计与应用；

5．二叉排序树的基本概念、建立(插入)、查找以及平均查找长度ASL的计算。

六、图

1．图的基本概念、名词术语；

2．图的邻接矩阵存储方法和邻接表(含逆邻接表)存储方法的构造原理及特点；

3．图的深度优先搜索与广度优先搜索；

4．最小(代价)生成树、最短路径、AOV网与拓扑排序的基本概念。

七、文件及查找

1．顺序查找法以及平均查找长度(ASL)的计算；

2．折半查找法以及平均查找长度(ASL)的计算，包括查找过程对应的“判定树”的构造；

3．散列(Hash)表的构造、散列函数的构造，散列冲突的基本概念、处理散列冲突的基本方法以及散列表的查找和平均查找长度的计算。

八、内排序

1．排序的基本概念，各种内排序方法的基本原理和特点，包括排序过程中进行的元素之间的比较次数，排序总趟数、排序稳定性以及时间复杂度与空间复杂度计算；

2．插入排序法(含折半插入排序法)；

3．选择排序法；

4．(起)泡排序法；

5．谢尔(Shell)排序法；

6．快速排序法；

7．堆积(Heap)排序法，包括堆积的定义与构造；

“C语言程序设计”部分

一、C程序的基本结构

1. C语言的特点以及C程序的基本组成

二、常量、变量和表达式

1. 常量：数字常量、字符常量和字符串字面量

2. 变量：变量名和变量类型，变量的赋值和类型转换

3. 算术表达式：算术运算符、增量（自增）和减量（自减）运算符、位运算和复合赋值运算符

4. 强制类型转换

5. 数据输入/输出函数

6. 常量的符号表示方法：常量宏、枚举常量

三、条件语句和开关语句

1. 关系运算符和逻辑运算符

2. 运算符的优先级

3. 逻辑表达式

4. 条件语句：条件、复合语句、条件语句的嵌套和级联、条件运算符和条件表达式

5. switch语句

四、循环语句和goto语句

1. while语句、for语句和do while语句

2. 循环语句的选择和使用

3. 逗号表达式

4. 循环语句的嵌套

5. 循环中的非常规控制（break和contiunue）、goto语句

五、函数

1. 函数的基本概念

2. 函数的调用、结构和定义

3. 函数的调用关系和返回值

4. 局部变量和全局变量

5. 函数参数的传递

6. 标准库函数

7. 递归函数

六、数组

1. 一维数组：定义和初始化、复制、数组参数

2. 字符串和字符数组

3. 标准字符串函数

4. 二维数组：定义、引用、访问、数组参数

七、指针

1. 地址与指针