湖南财政经济学院2022年专升本《数据结构》课程考试大纲

一、考试的基本要求

本课程应达到知识和技能两方面的目标：

1．知识方面：从数据的结构关系及其操作实现这两个层次，系统地掌握常用基本数据结构(线性表、栈、队列、二叉树、图)及其不同的实现(包括不同的存储结构和算法)，学习并掌握典型的查找和排序算法，识记并掌握分析、比较和选择不同数据结构及不同存储结构、不同运算实现(即算法)的原则和方法。

2．技能方面：掌握在不同存储结构上实现的不同算法及其设计思想，掌握结构选择和算法设计的思维方式及技巧。

二、考试的范围和内容

考核知识点一：数据和数据结构的概念，算法描述及分析

考核要求：

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

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

应用：算法及其描述

考核知识点二：线性结构的概念

考核要求：

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

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

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

考核知识点三：栈的定义和实现，队列的定义和实现

考核要求：

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

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

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

考核知识点四：串的定义和串的定长顺序实现

考核要求：

识记：串的定义

掌握：串的定长顺序实现

考核知识点五：数组元素地址的计算、广义表、特殊矩阵

考核要求：

识记：数组元素地址的计算、广义表的特点和结构

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

考核知识点六：树、二叉树、树的应用

考核要求：

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

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

应用：二叉树的遍历

考核知识点七：图、最小生成树、最短路径、拓扑排序

考核要求：

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

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

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

考核知识点八：查找表、二叉排序表、哈希表

考核要求：

识记：查找表的基本概念

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

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

考核知识点九：排序的基本概念、各类排序算法

考核要求：

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

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

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

三、考试题型和分値结构（100分）

1、填空题 （10分）

2、选择题 （30分）

3、判断题 （10分）

4、简答题 （20分） 

5、应用分析题 （30分）

四、考试形式

笔试（闭卷）

五、考试时间

90分钟

六、主要参考书目

1、数据结构教程（第5版），李春葆等，北京：清华大学出版社，2017

2、数据结构教程（第5版）学习指导，李春葆等，北京：清华大学出版社，2017

3、数据结构教程（第5版）上机实验指导，李春葆等，北京：清华大学出版社，2017