2023年山东工程职业技术大学专升本数据结构（C语言版）考试大纲

一、考试基本要求及适用范围概述

本《数据结构（C语言版）》考试大纲适用于山东工程职业技术大学2023年专升本专业测试考试。

《数据结构》课程是计算机科学与技术专业的必修专业基础课。这门课程的主要特点是实践性很强,不仅要学习基本理论知识,更要注重实践能力,通过实践验证算法的正确性,掌握和巩固所学理论知识。设立本门课程的目的是通过学习，使学生学会分析研究数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步了解对算法的时间分析和空间分析技术。另一方面，通过对本课程算法设计和实践的训练，还应培养学生的数据抽象能力和程序设计的能力，为后续课程，特别是软件开发设计课程打下坚实的知识基础。

二、考试方法和考试时间

专升本专业测试《数据结构（C语言）》考试为闭卷，线上考试，试卷满分100分，考试时间为60分钟。

三、考试内容和考试要求

1．数据结构与算法的概述

考试内容

数据结构中常用的基本概念和术语以及学习数据结构的意义。

数据的抽象类型定义。

算法在实际问题中的应用。重点掌握各种基本概念和术语、算法描述和分析的方法

考核要求：

识记：运算的概念、存储结构和运算实现、算法分析

掌握：数据、数据元素、数据项、数据类型、数据结构、抽象数据类型

应用：算法及其描述

2.线性表

考试内容

线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。

要求在熟悉这些内容的基础上，能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。

考核要求：

识记：线性结构的概念、线性表的概念

掌握：线性表的链式存储结构、顺序表与链表的比较

应用：线性表的顺序存储结构，插入、删除和定位运算在单链表上的实现

3.栈和队列

考试内容

栈和队列的逻辑结构定义及在两种存储结构上如何实现栈和队列的基本运算。

栈和队列的特点的基础上，懂得在什么样的情况下使用栈或队列。

考核要求：

识记：栈的定义、队列的定义

掌握：栈的顺序实现、栈的链接实现、队列的顺序实现

应用：循环队的组织方法及在其上进行人队、出队运算的方法和队满、队空的条件。

4.串

考试内容

串的逻辑结构、存储结构及其串上的基本运算。

串的基本概念和三种表示方法。

考核要求：

识记：串的定义

掌握：串的定长顺序实现

5.数组

考试内容

多维数组的逻辑结构特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法的概念。

考核要求：

识记：数组元素地址的计算

掌握：特殊矩阵的压缩存储

6.树和二叉树

考试内容

二叉树的定义、性质、存储结构、遍历、线索化，树的定义、存储结构、遍历、树和森林的转换及赫夫曼树及其赫夫曼编码等内容。

考核要求：

识记：树形结构的基本概念和术语、树和森林、二叉树的定义、二叉树的顺序存储结构

掌握：二叉树的链式存储结构、哈夫曼树的概念、构造哈夫曼树的方法

应用：二叉树的遍历

7.图

考试内容

图的基本概念、两种常用的存储结构、两种遍历方法以及图的应用算法。

图的两种存储结构上实现的遍历算法。

最小生成树，求最短路径以及拓扑排序。

考核要求：

识记：树形结构的基本概念和术语、树和森林

掌握：图的遍历，拓扑排序、关键路径、图的概念、图的存储结构最小生成树

应用：Prime算法、迪杰斯特拉方法的基本思想

8.查找

考试内容

线性表、树和哈希表的查找方法、算法实现以及各种查找方法的时间性能（平均查找长度）分析。

顺序查找、折半查找、二叉排序树和哈希表查找的基本思想和算法实现。

考核要求：

识记：查找表的基本概念

掌握：静态查找表的实现、二叉排序树的查找算法及其基本思想

应用：哈希表、在开散列表上实现查找、插入和删除运算的思想和算法

9.排序

考试内容

五类内部排序方法的基本思想、排序过程、算法实现、时间和空间性能的分析以及各种排序方法的比较和选择。

考核要求：

识记：排序的基本概念、归并排序

掌握：堆的定义、堆的调整方法和“筛选”过程，建堆的方法、冒泡排序算法、直接选择排序基本思想

应用：直接插入排序的算法和性能、折半插入排序算法、快速排序的算法和性能

四、主要参考教材

1.《数据结构》 汤庄园  东北师范大学出版社  2020.01

2.《数据结构（C语言版）》 严蔚敏  清华大学出版社  2022.10