《2014韩山师范学院专插本《数据结构》考试大纲》由会员分享，可在线阅读，更多相关《2014韩山师范学院专插本《数据结构》考试大纲（7页珍藏版）》请在金锄头文库上搜索。
1、数据结构考试大纲I 考试的性质与目的 本科插班生考试是由专科毕业生参加的选拔性考试。数据结构是计算机科学与技术专业(本科)的 一门专业基础课程，考试主要检查考生对常用基本数据结构(顺序表、链表、栈、队列、树、二叉树、图等) 的逻辑结构、存储结构和相应算法的掌握程度，以保证后续课程的学习。II 考试的内容一、考试基本要求1、基本理论知识(1) 、数据结构的基本概念和基本术语，算法的描述方法和算法分析的基本概念。( 2 )、线性表的基本概念、线性表的基本操作以及这些操作分别在顺序存储和链式存储结构下的实现及复杂度分析。(3)、栈和队列的定义、存储结构、实现和典型应用。( 4)、串的定义及其基本操作
2、。(5) 、数组的定义、运算和存储，稀疏矩阵的压缩存储。(6) 、树的定义、基本术语和存储结构，二叉树的定义和性质、二叉树的存储结构及其各种操作，哈夫 曼树的概念和应用。(7) 、图的定义和术语、图的存储结构及其各种操作。(8) 、各种查找方法的算法、适用范围及时间复杂度的分析。(9) 、多种内排算法的基本思想和算法的时间复杂度分析，不同排序方法的比较。2、基本技能(1) 、能阅读用类 C 语言编写的算法。(2) 、能分析算法所完成的功能、运行结果和时间复杂度。(3) 、能根据要求用类C语言编写算法。二、考核知识点及考核要求第一章 绪论一、考核知识点1. 数据、数据元素、数据项、数据对象、数据
3、结构、逻辑结构、物理结构、元素、结点等基本概念。抽 象数据类型的定义、表示和实现方法。2算法、算法的特性、如何用类C语言来描述算法。3. 算法设计的基本要求以及计算语句频度和估算算法时间复杂度的方法。二、考核要求1识记：有关数据结构的基本概念，四种基本数据结构的特点。2. 理解：四种基本数据结构的基本运算，算法复杂度度量的基本概念。3应用：用类C语言描述算法第二章 线性表一、 考核知识点1. 线性表的定义和基本操作。2. 线性表顺序存储结构的表示和基本运算。3. 线性表链式存储，带有附加表头结点和不带附加表头结点的单链表、循环链表和双向链表的表示和查 找、插入、删除等基本操作。二、考核要求1.
4、 识记：线性表基本概念、基本运算，各种链表的表示。2. 理解：顺序存储和链式存储的比较，各种链表的基本操作算法第三章 栈和队列一、考核知识点1. 栈和队列的定义及其存储结构、循环队列。2. 栈和队列的主要运算。3. 栈的应用举例，如：数制转换、表达式求值等。二、考核要求1. 识记：栈和队列的概念、功能、操作特点、主要运算。2. 理解：栈和队列与一般线性表对比的特殊性，栈和队列的顺序存储和链式存储，循环队列。3. 应用：栈和队列的常见的使用场合。第四章 串一、考核知识点1. 串的定义、空串的概念。2. 串的基本操作。3. 串的顺序存储结构及在顺序存储结构下基本操作的实现。4. 串的模式匹配算法。
5、二、考核要求1. 识记：串的有关概念。2. 理解：串的基本操作，串的顺序存储结构及其基本操作。3. 应用：串的基本操作函数的使用。第五章 数组和广义表一、考核知识点1. 数组的顺序存储结构。2. 二维数组的按行存储及按列存储和计算数组元素的地址计算公式。3. 矩阵的压缩存储、三元组表的概念和基本操作。4. 广义表的定义。二、考核要求1. 识记：数组的顺序存储结构，广义表的定义。2. 理解：二维数组的地址计算，三元组表的表示。3. 应用：用三元组表解决稀疏矩阵的存储问题。第六章 树和二叉树一、考核知识点1. 树的定义和术语。2. 二叉树（完全二叉树、满二叉树）的定义和性质、二叉树的存储结构（顺序
6、表示法和二叉链表表示法）3. 二叉树遍历算法（先序、中序、后序、层次）。4. 树和森林转换为二叉树的方法（孩子兄弟表示法）。5. 树的路径长度、树的带权路径长度、Huffman树的构造方法。二、考核要求1. 识记：树的基本概念2. 理解：二叉树的存储结构、遍历算法，孩子兄弟表示法，树的路径长度，哈夫曼树的构造方法3. 应用：利用哈夫曼树解决一些最优化问题第七章 图一、考核知识点1. 图的定义。2. 图的基本术语。（1）图及无向图、有向图、网、子图、连通图、强连通图。（2）顶点的度、入度、出度。（3）顶点间路径、路径长度、环。3. 图的存储结构邻接矩阵（2）邻接表（含逆邻接表）4. 遍历图深度优
7、先搜索遍历图的算法及其时间复杂度。（2）广度优先搜索遍历图的思想及其时间复杂度。5. 生成树、最小生成树的概念。6. 拓扑排序的方法7. 求最短路径的算法。二、考核要求1. 识记：图的基本概念和术语，最小生成树、拓扑排序、最短路径的概念。2. 理解：图的存储方式和基于该存储方式的基本操作（求入度、出度、下一条边等）3. 应用：求拓扑序列的方法，求最短路径的方法第八章 动态存储管理（不要求）第九章 查找一、考核知识点1. 查找、关键字、平均查找长度等概念。2. 静态查找表的查找算法及其效率(最坏和平均查找长度)。(1)顺序查找(2)折半查找(3)分块查找3. 动态查找表 (1)二叉排序树定义、构
8、造过程及其查找算法和效率。(2)平衡二叉树的定义。4. 哈希表 (1)哈希表的特点。(2)构造哈希函数的方法(除留余数法等)。(3)处理冲突的方法。二、考核要求1. 识记：有关查找的基本概念，静态查找表和动态查找表的概念，哈希表的概念2. 理解：各种静态查找算法的比较次数分析，二叉排序树定义的构造过程和查找算法，哈希函数的选择 冲突处理的方法。3. 应用：分析各种查找算法的比较次数。第十章 内部排序一、考核知识点1. 排序的目的、分类和排序方法的稳定性的定义。2. 直接插入排序的思想3. 快速排序(1)冒泡排序的算法。 (2)快速排序的思想。4. 选择排序(1) 简单的选择排序的算法。(2)
9、堆的定义、堆排序的思想。5. 归并排序的思想。二、考核要求1、识记：直接插入排序、冒泡排序、简单选择排序的思想2、理解：快速排序、堆排序、归并排序的思想，各种排序方法的稳定性、平均比较次数、平均移动次数3应用：用类C或者C语言编写直接插入排序、冒泡排序、简单选择排序等排序算法。第十一章 外部排序(不要求)第十二章 文件(不要求)III 考试的形式及试卷结构1、考试的形式：采用闭卷笔试的形式。考试时间120 分钟，全卷100 分。2、试卷中各章所占的比例：第一章约占8%，第二、三、四、五章共约占40%，第六章约占 20%，第七 章约占 15%，第九章约占12，第十章约占5% 。3、试题对不同能力
10、层次要求的分数比例：识记约占30%，理解约占 40%，应用约占 30%。4、试题难易占分比例：易约占30%，中约占 50%，难约占 20%。5、考卷的结构：试题分为客观题和主观题。客观题一般有填空题、选择题、名词解释、程序填空题等类型；主观题一般有简答题、算法设计题等类型。IV 参考书目主要参考书：数据结构（C语言版）严蔚敏吴伟民编著，清华大学出版社。V 题型示例一、填空题1、 一棵深度为 8（根的层次号为 1）的满二叉树有个叶子结点。2、 串的长度是指。二、选择题1、一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是A .e d c b a B. d e c b a C. d c
11、 e a b D. a b c d e2、 对于栈操作数据的原则是。A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序三、名词解释1 、连通图2、完全二叉树四、程序填空题)ElemType定义如下：struct ElemTypeKeyType key; /咲键字 */*其他数据项*/；下面的程序段是在一棵二叉排序树中查找给定的关键字，找到返回 1，找不到返回 0。请把该程序补充 完整。Tree定义如下：struct TreeElemType data;/* 存放数据*/struct Tree *left; / * 扌旨向左子树 */ struct Tree *right; /* 扌
12、旨向右子树 */；int Find(Tree * boot, ElemType item) Tree *p=boot;while (if (item.key data.key) else if (item.key p-data.key) elsereturn(0);五、简答题1、试比较链式存储和顺序存储的优缺点。2、已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA,试写出其先序序列。六、算法设计题设计一算法，实现将一个递减的数组AO.n-l和一个带头结点的递增单链表B合并成一个带头结点的递 增链表C。已知单链表的数据定义为：struct SingleLinkElemType data;SingleLink *next;请用函数原型：SingleLink *LinkAAndB( ElemType A, int n, SingleLink *B);数组A和要链接的单链表B通过函数参数传递，n是数组的规模。函数返回值是生成的链表。
