广东石油化工学院2014年专插本信息与计算科学（企业信息化）专业考试大纲
《数据结构》考试大纲
一、考试对象 信息与计算科学专业本科插班生
二、考试目的 使学生掌握计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构，从而使建立在其上的解决问题的算法达到最优。 本门课程考核要求由低到高共分为“了解”、“掌握”、“熟练掌握”三个层次。其含义：了解，指学生能懂得所学知识，能在有关问题中认识或再现它们；掌握，指学生清楚地理解所学知识；熟练掌握，指学生能较为深刻理解所学知识，在此基础上能够准确、熟练地分析解决较为简单的实际问题。
三、考试方法和考试时间 1、考试方法：闭卷、笔试 2、记分方式：百分制，满分为100分 3、考试时间：120分钟 4、试题总数：26题 5、命题的指导思想和原则 命题的总的指导思想是：全面考查学生对本课程的基本原理、基本概念和主要知识点学习、理解和掌握的情况。命题的原则是：题目数量多、份量小，范围广，最基本的知识一般要占60%左右，稍微灵活一点的题目要占20%左右，较难的题目要占20%左右。其中绝大多数是中小题目，即使大题目也不应占分太多，应适当压缩大题目在总的考分中所占的比例。客观性的题目应占比较重的份量。 6、题目类型 （1）选择题（在下列各小题的备选答案中，请把你认为正确答案的题号填入题干的括号内。少选、多选不给分。每题1分，共10分） （2）填空题（每空1.5分，共30分） （3）简述分析题（每题5--10分，共20分） （4）算法分析与实现（每题10--15分，共40分）
四、考试内容、要求 第一章 数据结构基本概念 1、基本概念：理解什么是数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、数据结构的抽象层次。 2、算法的概念和算法的时间复杂度分析 要点：Ø 利用大O规则计算时间复杂性，对于一般算法能分析出时间复杂度。 1、线性表 1．1 线性表的逻辑结构 1．2 线性表的数组实现 1．3 线性表的指针实现——链表 1．4 特殊链表 要点： Ø 掌握数组实现的特点 Ø 掌握链表的实现方法，如单链表的搜索算法与插入、删除算法 第三章 栈与队列 1、栈：栈的特性、栈的基本运算 要点： Ø 栈的数组实现、栈的链表实现 Ø 栈满及栈空条件 2、队列：队列的特性、队列的基本运算 要点： Ø 队列的数组实现：循环队列中队头与队尾指针的表示，队满及 队空条件 Ø 队列的链表实现：链式队列中的队头与队尾指针的表示、 3、算术表达式计算：用后缀表示计算表达式，中缀表示改后缀表示 第四章 树 1、树：树的定义、树的基本运算 要点： Ø 树的分层定义是递归的 Ø 树的一些常用术语，如结点，树根，度，树叶，树的深度等 Ø 树中结点个数与高度的关系 Ø 树的几种存储形式 2、二叉树：二叉树定义、二叉树的基本运算 要点： Ø 二叉树性质、二叉树中结点个数与高度的关系、不同种类的二 叉树棵数 Ø 有序树和二叉树的转化 Ø 二叉树的前序·中序·后序遍历的递归算法 3、二叉排序树：二叉排序树的定义及操作 要点： Ø 二叉排序树的查找算法 4、穿线二叉树：概念，存储形式 要点： Ø 用游标实现穿线二叉排序树 5、哈夫曼树：哈夫曼树的构造方法、哈夫曼编码、带权路径长度的计算 要点： Ø 哈夫曼树是带权路径长度最小的扩充二叉树 Ø 构造哈夫曼树时，按构造算法，每次具最小关键码的子树是根的左子树，具次小关键码的子树是根的右子树 Ø 在构造过程中，新二叉树按根的权值加入到森林的最后 6、堆：堆的定义 要点： Ø 堆的顺序存储、堆中结点的双亲、子女和兄弟的位置 第五章 图 1、图：图的定义与图的存储表示 要点： Ø 邻接/代价邻接矩阵表示 Ø 邻接表表示 Ø 邻接多重表表示 Ø 边表表示 2、深度优先遍历与广度优先遍历 要点： Ø 深度优先搜索算法和广度优先搜索算法 Ø 深度优先搜索是个递归的过程，而广度优先搜索是个非递归的过程 Ø 为防止重复访问已经访问过的顶点，需要设置一个访问标志数组visited 3、图的连通性 要点： Ø 深度优先搜索可以遍历一个连通分量上的所有顶点 Ø 对非连通图进行遍历，可以建立一个生成森林 4、最小生成树 要点： Ø 对于连通网络、可用不会构成环路的权值最小的n-1条边构成最小生成树 Ø 会画出用Kruskal算法及Prim算法构造最小生成树的过程 第六章 查找 1、集合 要点： Ø 用位向量实现集合的操作 2、查找表 要点： Ø 对有序顺序表的顺序搜索算法 Ø 对有序顺序表的折半搜索算法 3、散列技术 要点： Ø 散列的概念 Ø 哈希函数的选择 Ø 两类解决冲突的方法及其优缺点 第七章 排序 1、基本概念：关键字、关键字比较次数、数据移动次数、稳定性 2、熟悉常用排序算法的稳定性、算法的复杂度 3、简单排序方法 3．1 插入排序 要点： Ø 直接插入、折半插入算法的原理和实现方法 3．2 选择排序 要点： Ø 算法的原理和实现方法 3．3 冒泡排序 要点： Ø 算法的原理和实现方法 4、分治法排序 4．1 合并排序 要点： Ø 算法的原理和实现方法 Ø 针对给定的输入实例，写出排序过程 4．2 快速排序 要点： Ø 算法的原理和实现方法 Ø 快速排序是一个递归的排序方法 Ø 当待排序关键码序列已经基本有序时，快速排序显著变慢 Ø 针对给定的输入实例，写出排序过程 5、比较型排序方法 5．1 堆排序 要点： Ø 算法的原理 5．2 希尔排序 要点： Ø 算法的原理 6、各种排序方法的比较（时间复杂性、稳定性方面）
五、试题结构（内容、题型、分数分配）
六、考试要求 本课程为闭卷考试，考生不得携带任何纸张、教材、笔记本、作业本、参考资料、电子读物、电子器具和工具书等进入考场。 七、指定参考书 《数据结构（C语言版）》严蔚敏、吴伟民编，清华大学出版社
《数据库系统原理》考试大纲
一、考试对象 信息与计算科学专业本科插班生
二、考试目的 学生应该掌握关系数据库的基本原理，关系数据库的设计理论以及数据库设计的步骤和方法。 三、考试方法和考试时间
1、记分方式：百分制，满分为100分 2、命题的指导思想和原则 命题的总的指导思想是：全面考查学生对本课程的基本原理、基本概念和主要知识点学习、理解和掌握的情况。命题的原则是：题目数量多、份量小，范围广，最基本的知识一般要占60%左右，稍微灵活一点的题目要占20%左右，较难的题目要占20%左右。 四、 考试内容要求： （一）数据库系统概述数据管理技术的发展历程（人工管理方式阶段、文件管理方式阶段、数据库管理方式阶段）；数据库与数据库管理系统的基本概念（数据库基本概念、数据库管理系统、数据库语言）；数据模型（数据模型的概念和种类、概念数据模型、结构数据模型）；数据库的体系结构（数据库系统的三级模式结构、数据库的二级映像功能、两级数据独立性、数据库操作过程）；数据库系统（硬件、软件、数据库、人员）。 （二）关系运算理论 (三)数据库设计和规范化 （四）数据库基础--SQL语言 （五）数据库的保护 （六）数据库的发展方向
五、指定参考书 1.《数据库系统原理与设计》，黄义宏、黄文钰编，清华大学出版社 2.《数据库技术与应用》冯凤娟编，清华大学出版社 (责任编辑：admin) |
||||||||||||||||||||||||||||||||
