2019年广东工业大学华立学院本科插班生招生考试《数据结构》考试大纲

2019年广东工业大学华立学院本科插班生招生考试

《数据结构》考试大纲

第一部分课程性质与目的

一、课程性质和特点

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

二、课程的基本要求

通过本课程的学习，学生应比较系统地从数据结构的逻辑结构、存储结构和运算三个方面去掌握线性表、栈、队列、串、数组、树、图等常用的数据结构；并且掌握在各种常用的数据结构上实现的排序和查找算法，同时对算法的时间和空间复杂性有一定得分析能力；针对简单的应用问题，应能选择合适得数据结构及设计有效的算法解决之。这对于培养学生运用数据结构解决实际问题能力的培养有着重要的意义。

三、课程与其他课程的联系

本课程的先修课程为离散数学和高级程序设计语言。本课程的大部分实例都是C语言实现得，故要求较熟悉地掌握C语言。

    本课程的重点是掌握各种数据结构的逻辑结构，该逻辑结构对应的存储结构及其运算。难点是对算法进行时间和空间复杂性的分析。

第二部分课程内容与考核标准

第1章 绪论

一、学习目的和要求

本章的目的是介绍数据结构中常用的基本概念和术语以及学习数据结构的意义。本章要了解数据的抽象类型定义。理解算法在实际问题中的应用。重点掌握各种基本概念和术语、算法描述和分析的方法。

二、考核知识点

1．数据、数据元素、数据项、数据结构等基本概念。

2．数据结构的四种逻辑结构和两种存储结构表示方法。

3．抽象数据类型的表示和实现。

4．算法的五个特点。

5．算法、算法的时间复杂度和空间复杂度等概念。

三、考核要求

1.识记

1） 数据结构的基本概念和术语。

2） 合适的数据结构在解决实际应用问题中的关键性，以及学习《数据结构》的意义。

3） 数据结构的四种逻辑结构和两种存储结构表示方法。

2.领会

算法的描述和分析：算法的时间复杂度和空间复杂度。

第2章 线性表

一、学习目的和要求

本章的目的是介绍线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。要求在熟悉这些内容的基础上，能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。

本章重点是熟练掌握顺序表和单链表上实现的各种基本运算，难点是在循环链表和双向链表存储结构中各种基本运算的实现。

二、考核知识点

1．线性表的类型定义。

2．顺序表的含义及特点，顺序表上的插入、删除操作。

3．链式表示和实现，单链表、双链表、循环链表链接方式上的区别。

4．单链表上实现的建表、查找、插入和删除等基本算法。

5．顺序表和链表的比较。

三、 考核要求

1.识记

1) 线性表的逻辑结构特征。

2) 线性表上定义的基本运算，并利用基本运算构造出较复杂的运算。

2.领会

1） 顺序表和链表的比较，各自的优缺点。

2） 针对线性表上所需要执行的主要操作，知道选择顺序表还是链表作为其存储结构才能取得较优的时空性能。

3.综合应用

1) 顺序表的含义及特点，顺序表上的插入、删除操作及其平均时间性能分析。

2) 单链表、双链表、循环链表链接方式上的区别。

3) 单链表上实现的建表、查找、插入和删除等基本算法及其时间复杂度。

4) 单循环链表上的算法与单链表上相应算法的异同点。

第3章 堆栈和队列

一、学习目的和要求

本章的目的是介绍栈和队列的逻辑结构定义及在两种存储结构上如何实现栈和队列的基本运算。要求在掌握栈和队列的特点的基础上，懂得在什么样的情况下使用栈或队列。

本章重点是掌握栈和队列在两种存储结构上实现的基本运算，难点是循环队列中对边界条件的处理。

二、考核知识点

1．栈的抽象数据类型的定义

2．栈的表示和实现

3．栈的简单应用

4．队列的链式表示和实现

5．队列的顺序表示和实现

三、考核要求

1.领会

1）栈和队列的特点，栈和队列各自的使用情况。

2.综合应用

1）栈的逻辑结构特点，栈与线性表的异同。

2） 利用栈解决简单的实际问题。

3）队列逻辑结构特点，队列与线性表的异同。

4）顺序队列（主要是循环队列）和链队列上实现的入队、出队等基本算法。

5）顺序队列的“假溢出”现象及其采用循环队列进行解决的方法。

第4章  串

一、学习目的和要求

本章的目的是介绍串的逻辑结构、存储结构及其串上的基本运算。本章重点是掌握串的基本概念和三种表示方法。

二、考核知识点

1.串的定义、空串、空格串、子串、主串、串相等。

2.串的基本操作。

3.串的顺序存储结构及在顺序存储结构下基本操作的实现。

三、考核要求

1.领会

1) 串的有关概念及其基本运算。

2.简单应用

1）串的三种存储表示。

2）使用串解决与串相关的简单的应用问题。

第5章  数组

一、学习目的和要求

本章的目的是介绍多维数组的逻辑结构特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法。

本章重点是熟悉多维数组的存储方式、矩阵的压缩存储方式，难点是稀疏矩阵的压缩存储表示下转置运算。

二、考核知识点

1．数组的顺序存储结构。

2．二维数组的按行存储及按列存储和计算数组元素的地址计算公式。

3．矩阵的压缩存储、特殊矩阵的表示。

三、考核要求

1．领会

1）多维数组的逻辑结构特征

2） 多维数组的顺序存储结构及其地址计算方式

3） 特殊矩阵和稀疏矩阵的概念

4）稀疏矩阵的压缩存储方式——三元组表

第六章、第七章不考

第8章   树和二叉树

一、学习目的和要求

本章的目的是介绍二叉树的定义、性质、存储结构、遍历，树的定义、存储结构、遍历及哈夫曼树及其哈夫曼编码等内容。本章重点是掌握二叉树及其二叉树的遍历。难点是掌握与树有关的简单应用。

二、考核知识点

1.树的定义和术语。

2.二叉树(完全二叉树、满二叉树)的定义和性质(结论)、二叉树的存储结构——顺序表示法和链表表示法。

3.二叉树的三种遍历方法及相应的递归算法。

4.树的存储表示法——孩子表示法、双亲表示法、孩子兄弟表示法。

5.树的路径长度、树的带权路径长度、哈夫曼树（优二叉树）的构造方法。

6.哈夫曼编码方法。

三、考核要求

1.领会

1) 树的逻辑结构特征

2) 树的不同表示方法

3) 树的常用术语及含义

4) 树的各种存储结构及其特点

2.简单应用

1) 二叉树的定义及树与二叉树的差别

2) 二叉树的性质

3) 二叉树的两种存储结构、特点及适用范围

4) 哈夫曼算法的思想

5) 根据给定的叶结点及其权值构造出相应的优二叉树

3.综合应用

1) 二叉树的三种遍历算法，理解其执行过程

2) 根据不同的遍历方法，应能得出其相应的结点访问次序

第9章  图

一、学习目的和要求

本章的目的是介绍图的基本概念、两种常用的存储结构、两种遍历方法以及图的应用算法。本章重点掌握图的应用算法：小生成树。

二、 考核知识点

1.图的逻辑结构特征

2.图的常用术语及含义

3.图的邻接矩阵表示法存储结构

4.生成树和小生成树

5.关于短路径的算法——Dijkstra算法思想

三、 考核要求

1、领会

1) 图的逻辑结构及特征

2) 图的常用术语及含义

3) 生成树和小生成树的概念

4) 要求对给定的连通图，根据Prim和Kruskal算法构造小生成树

5) 短路径的含义

6) 求单源点的短路径问题的Dijkstra算法的基本思想和时间性能

2.简单应用

1) 图的邻接矩阵表示法

2) 根据应用问题的特点选择合适的存储结构

第10章  排序

一、 学习目的和要求

本章的目的是介绍五类内部排序方法的基本思想、排序过程、算法实现、时间和空间性能的分析以及各种排序方法的比较和选择。重点掌握快速排序、堆排序、归并排序和基数排序的基本思想和排序过程。难点是这四类排序算法的实现。

二、 考核知识点

1.排序的目的、分类和排序方法的稳定性的定义。

2.插入排序的思想。

3.选择排序的思想。

4.交换排序的思想。

5.归并排序的思想。

6.基数排序的思想。

三、 考核要求

1.识记

1) 排序在数据处理中的重要性

2) 排序方法稳定性的含义

3) 排序方法的分类及算法好坏的评判标准

2.简单应用

1) 比较各种排序算法的优缺点

2) 根据实际问题的特点和要求选择合适的排序方法

第11章  查找

一、学习目的和要求

本章的目的是介绍线性表、树和哈希表的查找方法、算法实现以及各种查找方法的时间性能（平均查找长度）分析。重点掌握顺序查找、折半查找的基本思想和算法实现。

二、考核知识点

1.查找的定义关键字、查找、平均查找长度。

2.静态查找表的查找算法（顺序查找、折半查找、分块查找(索引顺序表的查找)）及其效率(坏和平均长度)。

3.哈希法的特点

三、考核要求

1.识记

1) 查找在数据处理中的重要性

2) 查找成功、不成功的含义

2.简单应用

1） 顺序查找、折半查找、分块查找的基本思想、算法实现和查找效率分析

1) 顺序查找中“监视哨”的作用

2) 比较线性表上三种查找方法的优缺点，能根据实际问题的要求和特点，选择出合适的查找方法

3) 哈希表和其它表的本质区别

第三部分  有关说明与实施要求

一、关于考核目标的说明

为了使考试内容和考试要求标准化，本大纲在列出考试内容的基础上，对各章节规定了考核目标。考核目标包含考核知识点和考核要求两项。学生可以通过对考核目标的阅读，进一步明确考试范围、内容和要求，从而可以更为系统地学习和把握教材。同时，考核目标还能够进一步明确考试命题范围，更正确地安排试题的知识能力层次和把握试题的难易程度。

本大纲在考核目标中，按照识记、领会、简单运用和综合运用等四个层次规定学生通过学习应该达到的能力层次要求。四个能力层次是递进等级关系。各能力层次的含义是：

1、识记：能够了解有关的名词、概念、知识的含义，并能正确认识和表述、选择和判断。

2、领会：在识记的基础上，能够比较全面地把握基本概念、基本事实、基本理论模型、基本方法，能把握有关概念、事实、理论模型、分析方法之间的区别和联系。并能根据考核的不同要求，做出正确的解释、说明和论述。

3、简单运用：在领会的基础上，能够运用本课程中规定的少量的知识点，分析和解释有关的一般的应用问题。例如，简单的算法设计和时间性能分析。

4、综合运用：指在简单运用的基础上，能够综合运用所学习过的多个知识点，分析和解决较复杂的应用问题，例如，设计较复杂的算法。

二、 参考教材

《数据结构——使用C语言》（第五版），朱站立，电子工业出版社，2014年1月

三、题型要求及分数比例

考试采用闭卷笔试，考试时间为120分钟，采用百分制评分；题型和分数比例如下：

选择题占35%-40%；填空题占15%-20%； 判断题占10%-15%； 综合题占25%-30%。

四、题型示例（样题）

1.向一个由127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（   ）个元素。

   A.8          B.63        C.63.5        D.7

2.稀疏矩阵一般采用 方法进行压缩存储。

3.关键字自身作为哈希函数，即H（k）=k，也可自身加上一个常数作为哈希函数，即H(k)=k+C这种构造哈希函数的方式叫 。

4、一个含有n个结点的完全二叉树，它的高度是ëlog₂ û＋1。（判断）

5、邻接表只能用于存储有向图，而邻接矩阵则可存储有向图和无向图。（判断）

6.采用普里姆算法，产生下图的小生成树（规定从结点A开始生成）。