2015年广东专插本本科计算机科学与技术插班生数据结构考试大纲
2014-12-10 15:23
感兴趣的有：
人
2015年本科插班生考试大纲
（考试科目：数据结构）
Ⅰ考试性质
普通高等学校本科插班生（又称专插本）招生考试是由专科毕业生参加的选拔性考试。高等学校根据考生的成绩，按照已确定的招生计划，德、智、体全面衡量，择优录取。因此，本科插班生考试应有较高信度、效度、必要的区分度和适当的难度。
Ⅱ考试内容
总体要求：理解数据结构的基本概念；把握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。把握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。能够选择合适的数据结构和方法进行问题求解。
绪论
⒈ 考试内容
⑴ 数据结构等相关基本概念。
⑵ 算法的定义、特征与设计要求。
⑶ 时空复杂度分析。
⒉ 考试要求
⑴ 了解数据结构等相关基本概念。
⑵ 了解算法的定义、特征与设计要求。
⑶ 掌握算法的时空复杂度分析方法。
第一章 线性表
⒈ 考试内容
⑴线性表的定义和基本操作。
⑵线性表的实现：1.顺序存储结构；2.链式存储结构；
⑶线性表的应用。
⒉ 考试要求
⑴ 掌握线性表的定义和基本操作。
⑵ 掌握线性表的顺序存储与链式存储实现。
第二章 栈和队列
⒈考试内容
⑴栈的基本概念。
⑵栈的表示和实现。
⑶栈的应用。
⑷队列的基本概念。
⑸队列的表示和实现。
⑹循环队列和链式队列。
⒉考试要求
⑴ 掌握栈的基本概念、表示、实现和应用。
⑵ 掌握队列的基本概念、表示和实现。
⑶ 掌握循环队列的实现。
第三章 串、数组和广义表
⒈ 考试内容
⑴串的定义、表示和实现。
⑵串的基本操作。
⑶数组的定义、表示和实现。
⑷矩阵的概念、特殊矩阵和稀疏矩阵。
⑸广义表的定义、存储结构。
⒉ 考试要求
⑴ 掌握串的定义、表示和基本操作的实现，特别是模式匹配算法。
⑵ 掌握数组的定义、表示和实现及与矩阵的关系，掌握特殊矩阵和稀疏矩阵压缩方法。
⑵ 了解广义表的定义、存储结构。
第四章 树与二叉树
⒈ 考试内容
⑴树的基本概念及存储结构。
⑵二叉树的基本概念、二叉树的存储结构、二叉树的遍历。
⑶森林的概念、存储结构。
⑷树、森林与二叉树的转换。
⑸树和森林的遍历。
⑹哈夫曼树的概念和应用。
⒉考试要求
⑴ 了解树的基本概念及存储结构、森林的概念及存储结构。
⑵ 掌握二叉树的基本概念、二叉树的存储结构、二叉树的遍历。
⑶ 掌握树、森林与二叉树的转换方法。
⑷ 了解树和森林的遍历。
⑸掌握哈夫曼树的概念、求解方法和应用。
第五章 图
⒈考试内容
⑴图的定义和概念、图的存储结构。
⑵图的遍历。
⑶图的应用：最小生成树、拓扑排序、关键路径、最短路径问题。
⒉考试要求
⑴ 了解图的相关定义。
⑵ 掌握图的存储结构、图的遍历方法。
⑶ 掌握图的最小生成树、拓扑排序、关键路径、最短路径的应用。
第六章 查找
⒈考试内容
⑴静态查找表、动态查找表与哈希表的基本概念。
⑵顺序表、有序表、静态树表、索引顺序表的查找。
⑶二叉排序树和平衡二叉树的基本概念与实现。
⑷B_树和B+树的基本概念。
⑸哈希函数的构造方法、冲突处理的方法。
⑹哈希表的查找和分析。
⒉考试要求
⑴ 了解静态查找表、动态查找表与哈希表的基本概念，了解B_树和B+树的基本概念。
⑵ 掌握顺序表、有序表、静态树表、索引顺序表的查找。
⑶ 掌握二叉排序树和平衡二叉树的基本概念与实现。
⑷ 掌握哈希函数的构造方法、冲突处理的方法，查找和分析方法。
第七章 排序
⒈考试内容
⑴ 排序的相关概念
⑵ 插入排序、交换排序、选择排序、归并排序、基数排序的概念和实现方法
⑶ 排序方法的比较
⒉考试要求
⑴ 了解排序的相关概念。
⑵ 掌握插入排序、交换排序、选择排序、归并排序、基数排序的概念和实现方法。
⑶ 了解不同排序算法的特点与适用范围。
Ⅲ.考试形式及试卷结构
一、考试形式
闭卷、笔试。试卷满分为100分，考试时间为120分钟。
二、试卷题型比例
填空题：约占10%；
简答题与应用题：约占40%；
选择题：约占40%；
程序题：约占10%。
二、试卷题型示例及答案
A．填空题：（着重考查学生对知识的理解程度）
例：时间复杂度为O(nlogn)的排序算法有＿＿＿＿、＿＿＿＿和＿＿＿＿。
B．单选题：（着重考查学生对知识的了解和掌握程度）
例：铁路转轨网络进行车厢调度，且两侧铁道均为单向行驶道。若进站的车厢序列为123，则不可能得到的出站车厢序列是（ ）。
a） 123 b） 231 c） 312 d） 213 e） 132 f） 321
C．简答题与应用题：（着重考查学生对知识的理解、掌握程度）
例1：试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。
例2：试列出下图中全部可能的拓扑有序序列。
D．程序题：（着重考查学生对知识的掌握程度）
例：已知L是带头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。删除P结点的直接后续结点的语句序列是：
例：2-路归并排序的另一策略是，先对待排序序列扫描一遍，找出并划分为若干个最大有序子列，将这些子列作为初始归并段。试写一个算法在链表结构上实现这一策略。
Ⅳ. 参考书目
①《数据结构》（C语言版）严蔚敏主编，2012，清华大学出版社。
分享到：
报名方式
1.直接来我校参观、报名。报名时带好身份证及正反面复印件2张、1寸蓝底彩照4张2寸蓝底彩照4张 。 （专升本在校生由学校开具证明，毕业生应交毕业证复印件）
2.学生选择网上或电话报名，学员可以电话、QQ、电子邮件报名或者索取招生简章，在指定时间内来校报到入学。
3.业余自考学生准备好个人资料和第一年学费，直接过来学校报名。
4.电话：020-85517608 或 13316047870 李老师(微信同号)
5.QQ：
6.广州招生网在线报名地址：点击进入网上报名系统
7.报名地址：广州天河中山大道西8号天河商贸大厦2203招生办(地铁3号线岗顶站；公交站师大暨大站)
（特别提醒：我校没有在各车站路口设立接待点，请广大考生自行来校，严防路人以指路带领为名上当受骗，中途勿受陌生人接待，以免误导，造成不必要的财产损失。）
