《数据结构》考试大纲

《《数据结构》考试大纲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》考试大纲I考试的性质与目的本科插班生考试是由专科毕业生参加的选拔性考试。《数据结构》是计算机科学与技术专业（本科）的一门专业基础课程，考试主要检查考生对常用基本数据结构（顺序表、链表、栈、队列、树、二叉树、图等）的逻辑结构、存储结构和相应算法的掌握程度，以保证后续课程的学习。II考试的内容一、考试基本要求1、基本理论知识（l）、数据结构的基本概念和基本术语，算法的描述方法和算法分析的基本概念。（2）、线性表的基本概念、线性表的基本操作以及这些操作分别在顺序存储和链式存储结构下的实现及复杂度分析。（3）、栈和队列的定义、存储结构、实现和典型应用。（4）、串的定义及其基本操作

2、。（5）、数组的定义、运算和存储，稀疏矩阵的压缩存储。（6）、树的定义、基本术语和存储结构，二叉树的定义和性质、二叉树的存储结构及其各种操作，哈夫曼树的概念和应用。（7）、图的定义和术语、图的存储结构及其各种操作。（8）、各种查找方法的算法、适用范围及时间复杂度的分析。（9）、多种内排算法的基本思想和算法的时间复杂度分析，不同排序方法的比较。2、基本技能（1）、能阅读用类C语言编写的算法。（2）、能分析算法所完成的功能、运行结果和时间复杂度。（3）、能根据要求用类C语言编写算法。二、考核知识点及考核要求第一章绪论一、考核知识点1.数据、数据元素、数据项、数据对象、数据结构、逻辑结构、

3、物理结构、元素、结点等基本概念。抽象数据类型的定义、表示和实现方法。2.算法、算法的特性、如何用类C语言来描述算法。3.算法设计的基本要求以及计算语句频度和估算算法时间复杂度的方法。二、考核要求1.识记：有关数据结构的基本概念，四种基本数据结构的特点。2.理解：四种基本数据结构的基本运算，算法复杂度度量的基本概念。3.应用：用类C语言描述算法第二章线性表一、考核知识点61.线性表的定义和基本操作。2.线性表顺序存储结构的表示和基本运算。3.线性表链式存储，带有附加表头结点和不带附加表头结点的单链表、循环链表和双向链表的表示和查找、插入、删除等基本操作。二、考核要求1.识记：线性表基本

4、概念、基本运算，各种链表的表示。2.理解：顺序存储和链式存储的比较，各种链表的基本操作算法第三章栈和队列一、考核知识点1.栈和队列的定义及其存储结构、循环队列。2.栈和队列的主要运算。3.栈的应用举例，如：数制转换、表达式求值等。二、考核要求1.识记：栈和队列的概念、功能、操作特点、主要运算。2.理解：栈和队列与一般线性表对比的特殊性，栈和队列的顺序存储和链式存储，循环队列。3.应用：栈和队列的常见的使用场合。第四章串一、考核知识点1.串的定义、空串的概念。2.串的基本操作。3.串的顺序存储结构及在顺序存储结构下基本操作的实现。4.串的模式匹配算法。二、考核要求1.识记：串的有关概念

5、。2.理解：串的基本操作，串的顺序存储结构及其基本操作。3.应用：串的基本操作函数的使用。第五章数组和广义表一、考核知识点1.数组的顺序存储结构。2.二维数组的按行存储及按列存储和计算数组元素的地址计算公式。3.矩阵的压缩存储、三元组表的概念和基本操作。4.广义表的定义。二、考核要求1.识记：数组的顺序存储结构，广义表的定义。2.理解：二维数组的地址计算，三元组表的表示。63.应用：用三元组表解决稀疏矩阵的存储问题。第六章树和二叉树一、考核知识点1.树的定义和术语。2.二叉树(完全二叉树、满二叉树)的定义和性质、二叉树的存储结构（顺序表示法和二叉链表表示法）。3.二叉树遍历算法（先序

6、、中序、后序、层次）。4.树和森林转换为二叉树的方法（孩子兄弟表示法）。5.树的路径长度、树的带权路径长度、Huffman树的构造方法。二、考核要求1.识记：树的基本概念2.理解：二叉树的存储结构、遍历算法，孩子兄弟表示法，树的路径长度，哈夫曼树的构造方法3.应用：利用哈夫曼树解决一些最优化问题第七章图一、考核知识点1.图的定义。2.图的基本术语。(1)图及无向图、有向图、网、子图、连通图、强连通图。(2)顶点的度、入度、出度。(3)顶点间路径、路径长度、环。3.图的存储结构(l)邻接矩阵(2)邻接表(含逆邻接表)4.遍历图 (l)深度优先搜索遍历图的算法及其时间复杂度。(2)广度优

7、先搜索遍历图的思想及其时间复杂度。5.生成树、最小生成树的概念。6.拓扑排序的方法7.求最短路径的算法。二、考核要求1.识记：图的基本概念和术语，最小生成树、拓扑排序、最短路径的概念。2.理解：图的存储方式和基于该存储方式的基本操作（求入度、出度、下一条边等）3.应用：求拓扑序列的方法，求最短路径的方法第八章动态存储管理（不要求）第九章查找一、考核知识点61.查找、关键字、平均查找长度等概念。2.静态查找表的查找算法及其效率(最坏和平均查找长度)。(l)顺