2017年韩山师范学院本科插班生考试《数据结构》考试大纲.pdfVIP

2017 年韩山师范学院本科插班生考试 《数据结构》考试大纲 I 考试的性质与目的 本科插班生考试是由专科毕业生参加的选拔性考试。 《数据结构》是计算机科学与技术专业（本科）的 一门专业基础课程，考试主要检查考生对常用基本数据结构（顺序表、链表、栈、队列、树、二叉树、图等） 的逻辑结构、存储结构和相应算法的掌握程度，以保证后续课程的学习。 II 考试的内容 一、考试基本要求 1、基本理论知识 （l ）、数据结构的基本概念和基本术语，算法的描述方法和算法分析的基本概念。 （2 ）、线性表的基本概念、线性表的基本操作以及这些操作分别在顺序存储和链式存储结构下的实现及 复杂度分析。 （3）、栈和队列的定义、存储结构、实现和典型应用。 （4 ）、串的定义及其基本操作。 （5）、数组的定义、运算和存储，稀疏矩阵的压缩存储。 （6）、树的定义、基本术语和存储结构，二叉树的定义和性质、二叉树的存储结构及其各种操作，哈夫 曼树的概念和应用。 （7）、图的定义和术语、图的存储结构及其各种操作。 （8）、各种查找方法的算法、适用范围及时间复杂度的分析。 （9）、多种内排算法的基本思想和算法的时间复杂度分析，不同排序方法的比较。 2、基本技能 （1）、能阅读用类 C 语言编写的算法。 （2 ）、能分析算法所完成的功能、运行结果和时间复杂度。 （3）、能根据要求用类 C 语言编写算法。 二、考核知识点及考核要求 第一章 绪论 一、考核知识点 1.数据、数据元素、数据项、数据对象、数据结构、逻辑结构、物理结构、元素、结点等基本概念。抽 象数据类型的定义、表示和实现方法。 2.算法、算法的特性、如何用类 C 语言来描述算法。 3.算法设计的基本要求以及计算语句频度和估算算法时间复杂度的方法。 二、考核要求 1.识记：有关数据结构的基本概念，四种基本数据结构的特点。 2.理解：四种基本数据结构的基本运算，算法复杂度度量的基本概念。 3.应用：用类 C 语言描述算法 1 第二章 线性表 一、 考核知识点 1.线性表的定义和基本操作。 2.线性表顺序存储结构的表示和基本运算。 3.线性表链式存储，带有附加表头结点和不带附加表头结点的单链表、循环链表和双向链表的表示和查 找、插入、删除等基本操作。 二、考核要求 1.识记：线性表基本概念、基本运算，各种链表的表示。 2.理解：顺序存储和链式存储的比较，各种链表的基本操作算法 第三章 栈和队列 一、考核知识点 1.栈和队列的定义及其存储结构、循环队列。 2.栈和队列的主要运算。 3.栈的应用举例，如：数制转换、表达式求值等。 二、考核要求 1.识记：栈和队列的概念、功能、操作特点、主要运算。 2.理解：栈和队列与一般线性表对比的特殊性，栈和队列的顺序存储和链式存储，循环队列。 3.应用：栈和队列的常见的使用场合。 第四章 串 一、考核知识点 1.串的定义、空串的概念。 2. 串的基本操作。 3. 串的顺序存储结构及在顺序存储结构下基本操作的实现。 4. 串的模式匹配算法。 二、考核要求 1.识记：串的有关概念。 2.理解：串的基本操作，串的顺序存储结构及其基本操作。 3.应用：串的基本操作函数的使用。 第五章 数组和广义表 一、考核知识点 1.数组的顺序存储