电子科技大学中山学院2018年专插本数据结构考试大纲
2017-12-20 17:45
感兴趣的有：
人
电子科技大学中山学院2018年本科插班生招生考试
数据结构 课程考试大纲
一、考试方式及题型
1.1考试形式
闭卷笔试
1.2考试题型：
（1）选择题、填空题、判断：占总分的40%左右，内容为概念和基本原理，覆盖本门课程的各部分知识点。
（2）简答题、应用题：占总分的60%左右，主要为各部分的重要简答题或应用计算题。
二、考试内容
2.1 绪论
（1）数据结构的基本概念和基本术语；数据逻辑结构和存储结构；
（2）算法特点、描述方法和复杂度分析方法，抽象数据类型的结构描述。
2.2线性表
（1）线性表抽象数据类型描述
（2）顺序表的定义和操作实现
（3）单链表的定义和操作实现
（4）线性表的应用方法。
（5）单向循环链表；双向循环链表。
2.3栈和队列
（1）栈的定义和基本运算；顺序栈类的定义和实现；链栈类的定义和实现
（2）队列的定义和运算，循环队列类的定义和实现，链队列类的定义和实现
（3）栈的应用，队列的应用
2.4串
（1）串的基本概念和相关术语；
（2）串处理库函数的使用，串的模式匹配算法
2.5数组
（1）数组的定义和基本运算，数组中元素的地址计算。
（2）特殊矩阵的压缩、存储和处理与稀疏矩阵的三元组表示，稀疏矩阵在三元组存储结构下的转置运算。
2.6树
（1）树结构基本概念、基本术语和基本操作
（2）二叉树的基本概念、基本术语、性质；完全二叉树、满二叉树的定义和性质；二叉树的顺序存储、二叉链表、仿真指针的孩子双亲存储结构。
（3）二叉树的遍历；二叉链表的构造、打印、求高度等基本算法；二叉树的线索化；
（4）树的存储；树与二叉树的转换；树的遍历。
（5）二叉树的带权路径长度；哈夫曼树和哈夫曼编码
2.7图 （8学时）
（1）图的定义和基本术语
（2）图的邻接矩阵和邻接表存储结构
（3）图的深度优先和广度优先遍历算法
（4）图的最小生成树算法
（5）图的最短路径算法
（6）有向无环图的应用
2.8查找
（1）查找的基本思想及查找成功和不成功的概念；
（2）顺序、折半和分块索引查找算法，及其平均长度的计算；
（3）二叉排序树的构造，及其平均长度的计算；
（4）哈希表的定义、哈希函数的常用构造方法、冲突处理的常用方法，及其平均长度的计算。
2.9排序
（1）排序的基本思想和基本概念，排序的稳定性
（2）直接插入排序、希尔排序；冒泡排序、快速排序等、简单选择排序、堆排序、归并排序、基数排序等算法的算法思想、性能分析。。
三、考试要求
3.1绪论
（1）掌握数据结构基本概念、术语：数据表、数据项、数据元素、逻辑结构（线性结构、树结构、图结构）、物理结构（顺序存储、链式存储）等感念；
（2）掌握简单程序的时间复杂度的分析（基本操作的执行次数）。
第2章：线性表
（1）掌握顺序表中结点的插入和删除涉及的操作，两者操作涉及的数据移动次数及时间复杂度；
（2）掌握单链表的插入和删除结点的操作实现、算法时间复杂度分析；理解单向循环链表和双向链表的结点插入和删除；
（3）掌握顺序存储结构和链式存储结构优缺点的比较
第3章：栈和队列
（1）掌握栈的先进后出的操作特性；
（2）掌握顺序存储结构和链式存储结构下的进栈和出栈操作的实现，及其时间复杂度的分析；
（3）掌握队列的先进后出的操作特性；
（4）掌握顺序队列的假溢出现象和循环队列的空或满的条件判定以，以及进队和出队操的实现和时间复杂度的分析；掌握链式队列的入队和出队操作的实现，和时间复杂度的分析。
（5）掌握栈再括号匹配中的应用、掌握队列在杨辉三角的打印中的应用。
第4、5章：串、数组
（1）掌握串的含义，空串与空格的概念
（2）掌握串的处理库函数的使用（如求长度、求子串、串比较、串连接等）
（3）掌握数组元素的存储地址计算（按行优先存储，按列优先存储）
（4）掌握对称矩阵的下三角压缩存储时元素的存储位置计算
（5）掌握稀疏矩阵的三元组表的存储方法，和转置等操作。
第6章：树
（1）掌握树的基本概念（深度，结点的度，树的度等），树的广义表表示法，树的存储（双亲表示法，孩子表示法，孩子兄弟表示法、双亲孩子表示法）；
（2）掌握满二叉树或完全二叉树中序号为i的结点的双亲结点、左孩子、右孩子、层次等的计算；
（3）掌握二叉树的顺序存储结构、二叉链表存储结构、仿真指针的双亲孩子表示法存储结构
（4）掌握求二叉树的先序、中序、后序遍历、层序遍历结果，以及有先序+中序（或后序+中序）遍历结果还原二叉树；
（5）理解先、中、后序遍历的递归算法实现及应用；
（6）掌握带权路径长度（WPL）的计算，哈夫曼树的创建及哈夫曼编码；
（7）掌握树转换为二叉树，树的遍历。
第7章：图
（1）掌握图的概念（如入度、出度、度的计算）、邻接矩阵表示和存储，邻接表的表示，能够通过邻接矩阵或邻接表画出图，无向图的度与边的关系，有向图入度、出度及边的关系；
（2）掌握求图的深度优先（递归算法或利用栈）和广度优先遍历（利用队列）结果的方法；
（3）掌握最小生成树的概念及最小生成树的代价（如生成树包含的顶点，包含的边数）利用Prim算法、Kruskal算法最小生成树的过程；
（4）掌握AOV、AOE网的先关概念，求拓扑序列和关键路径长度
（5）掌握利用Dijkstra算法求单源点最短路径的方法。
第8章：查找
（1）掌握查找的基本概念（ASL）；
（2）掌握顺序查找，折半查找和索引查找方式的查找效率以及查找长度的计算；
（3）掌握散列表（Hash表）的建立（冲突主要掌握线性探测法、拉链法）以及平均查找长度的计算；
（4）掌握二叉排序树的判定及创建二叉排序树并计算平均查找长度。
第9章：排序
（1）掌握排序的基本概念；
（2）掌握直接插入排序，希尔排序，简单选择排序，堆排序，冒泡排序，快速排序，归并排序算法思想；
（3）掌握直接插入排序，希尔排序，简单选择排序，冒泡排序和归并排序各趟排序结果；
（4）掌握快速排序中分区处理；
（5）掌握各类排序算法的时间复杂度，空间复杂度和稳定性。
四、推荐参考资源
《数据结构——用C语言描述》，耿国华 编著，高等教育出版社，2015年7月第二版
华南师范大学上课专插本培训招生简章
分享到：
报名方式
1.直接来我校咨询、报名。报名时带好身份证及正反面复印件2张、1寸蓝底彩照4张2寸蓝底彩照4张 。 （专升本在校生由学校开具证明，毕业生应交毕业证复印件）
2.学生选择网上或电话报名，学员可以电话、QQ、电子邮件报名或者索取招生简章，在指定时间内来校报到入学。
3.业余自考学生准备好个人资料和第一年学费，直接过来学校报名。
4.咨询电话：020-85517608 或 13316047870 李老师(微信同号)
5.咨询QQ：点击咨询
6.广州招生网在线报名地址：点击进入网上报名系统
7.报名地址：广州天河中山大道西8号天河商贸大厦602A招生办(地铁3号线岗顶站；公交站师大暨大站)
（特别提醒：我校没有在各车站路口设立接待点，请广大考生自行来校，严防路人以指路带领为名上当受骗，中途勿受陌生人接待，以免误导，造成不必要的财产损失。）
