云南省普高专升本专业课《数据结构》考试大纲

一、考试内容概述

（一）基本理论知识

1．数据结构的基本概念和基本术语，算法的描述，算法的时间复杂度和空间复杂度分析。

2．线性表的定义，在线性表上常进行的基本操作，这些操作在顺序和链式存储结构下的实现及复杂度分析。

3．栈和队列的定义、特点、表示方法和实现。

4．串的定义及其基本操作。

5．数组的定义、运算和存储、稀疏矩阵的压缩存储、广义表的定义和基本操作。

6．树德定义、基本术语和存储结构，二叉树的定义和性质、二叉树的存储结构及其各种操作，Huffman和Huffman编码。

7．图的定义和常用术语、图的存储结构及其遍历操作，求最小生成树、最短路径的算法，拓扑排序。

8．各种查找方法的算法、使用范围及时间复杂度的分析。

9．各种内排序算法的基本思想和算法的时间复杂度分析，不同排序方法的比较。

（二）基本技能

1．能阅读用类C语言编写的算法。

2．能分析算法所实现的功能、运行结果和时间、空间复杂度。

3．能根据要求用类C语言编写一些经典、常用算法。

二、考试形式

考试采用闭卷、答卷的考试方式。

满分：150分（单科成绩）

考试时间：120分钟。

变更，从2015年开始

考试形式：

考试采用局域网计算机化考试（机考）。

满分：150分（单科成绩）。

考试时间：120分钟。

三、试题难易程度分布

较易试题：约占50%

中等试题：约占30%

较难试题：约占20%

四、题型及题型分值分布

单选题：约占20%

多选题：约占10%

取消：填空题：约占15%

算法阅读题：约占10%

综合题：约占30%

程序设计题：约占15%

变更：从2015年开始，考试采用局域网计算机化考试（机考），取消填空题，分值将在要考的题型中作适当调整，可参考历年真题

五、内容比例

第一章 绪论：约占5%

第二章 线性表：约占10%

第三章 栈和队列：约占15%

第四章 串：约占5%

第五章 数组和广义表：约占5%

第六章 树和二叉树：约占15%

第七章 图：约占15%

第八章 查找：约占15%

第九章 内部排序：约占15%

考试内容及要求

第一章 绪论

1．了解数据、数据元素、数据项、数据对象、数据结构、逻辑结构、物理结构、元素、结点等基本概念。2．理解抽象数据类型的定义、表示和实现方法。3．理解算法的定义、算法的特性，掌握加何用类C语言来描述算法。4．理解算法设计的基本要求，掌握计算语句频度和估算算法时间复杂度的方法。

第二章 线性表

1．了解线性表的定义和操作。2．掌握顺序存储线性表的实现和常用运算：结点的插入、删除等，并掌握其效率分析方法。3．掌握链式存储线性表，带表头结点和不带表头结点的单链表的结点插入、删除操作，建立单链表的方法。4．理解循环链表和双向链表的实现方法，了解其插入，删除等基本操作。

第三章 栈和队列

1．了解栈和认列的定义，理解各自的特点，掌握栈的项序存储结构，理解循环队列存储方法。2．掌握栈和队列的主要运算：入栈、出栈、入队、出对。3．能运用栈和对列解决一些经典问题，如：数制转换、表达式求值、树的按层次遍历、图的广度优先遍历等。

第四章 串

1．了解串的定义、空串、空格串的概念。2．了解串的基本操作。3．了解串的顺序存储结构及在顺序存储结构下基本操作的实现。4．理解串的模式匹配算法。

第五章 数组和广义表

1．理解数组的项序存储结构。2．理解二维数组的按行存储和数组元素的地址计算公式。3．理解矩阵的压缩存储、特殊矩阵的表示。4．了解广义表的定义和基本操作。

第六章 树和二叉树

1．了解树的定义和基本术语口2．掌握二叉树（完全二叉树、满二叉树）的定义和性质，理解二叉树的顺序存储结构，掌握二叉树的二叉链表表示法。3．掌握二叉树遍历的递归算法，理解二叉树中序遍历的非递归算法，掌握根据先序遍历序列建立二叉树的递归算法。4．了解二叉树索化的实质及线索化的过程。5．了解树的存储结构，理解树和森林转换为二叉树的方法。6．掌握树的路径长度和树的带权路径长度的计算方法，Huffman树的构造方法和Huffman编码。

第七章 图

1．了解图的定义。2．了解图的基本术语：图及无向图、有向图、网、子图、连通图、强连通图、顶点的度、入度、出度、顶点间路径、路径长度、环。3．理解图的两种存储结构：邻接矩阵和邻接表（含逆邻接表）。4．掌握遍历图的两种方法：深度优先搜索和广度优先搜索遍历图的算法及其时间复杂度。5．理解生成树、最小生成树的概念，掌握最小生成树的构造过程（Prim的算法和Kruskal算法）及其时间复杂度。6．掌握拓扑排序的方法及最短路径的计算。7．掌握求最短路径问题的Dijkstra算法，了解F1oyd算法.

第八章 查找

1．了解查找、关键字、平均查找长度等概念。2．静态查找表：掌握顺序查找（设哨兵）、折半查找算法及其效率（最坏和平均查找长度）分析，了解分块查找算法及其效率分析。3．动态查找表：掌握二叉排序树的定义、构造过程及其查找算法和效率分析，掌握平衡二叉树的定义和其构造过程。4．了解哈希表的特点，掌握构造哈希函数的方法（除留余数法等），掌握处理冲突的方法及效率分析。

第九章 内部排序

1．了解排序的目的、分类和排序方法的稳定性的定义。2．插入排序：掌握直接插入、折半插入排序算法和希尔排序的思想。

3．快速排序：掌握起泡排序的算法和快速排序的思想。4．选择排序：掌握简单的选择排序的算法和堆的定义，堆排序的思想。5．理解归并排序的思想、基数排序的思想及特点。6．了解各种内部排序方法的比较。