肇庆学院2014年专插本数据结构考试大纲
2014年肇庆学院本科插班生考试大纲 (数据结构)
Ⅰ 考试性质 普通高等学校本科插班生(又称专插本)招生考试是由专科毕业生参加的选拔性考试。高等学校根据考生的成绩,按照已确定的招生计划,德、智、体全面衡量,择优录取。因此,本科插班生考试应有较高信度、效度、必要的区分度和适当的难度。 Ⅱ 考试内容及要求 一、考试基本要求 主要测试考生对数据结构各项内容的掌握程度。要求考生熟悉计算机处理数据的基本方法,掌握计算机加工的数据结构的特性,熟悉为实际应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法,并掌握算法的时间分析和空间分析技术。考试中相关算法要求用类C语言描述。 二、考试知识点 1.数据结构的基本概念 数据 数据元素 数据结构 数据类型 算法 算法的描述和算法分析 算法描述方法 算法效率的判断标准 算法的时间复杂度、空间复杂度计算 2.线性表 线性表、单链表、循环链表和双向链表的概念; 线性表的存储结构实现及应用。 3.堆栈和队列 堆栈和队列的基本概念; 堆栈和队列的存储实现; 堆栈和队列的基本运算的实现; 堆栈和队列的基本应用。 4.串 串的基本概念及其存储结构实现。 5.数组 数组、特殊矩阵和稀疏矩阵的概念; 三元组表。 6.树和二叉树 树、森林和二叉树的概念; 二叉树的存储结构; 树或森林与二叉树的相互转化; 树和二叉树的遍历算法; 哈夫曼树的构造和应用。 7.图 图的概念及存储实现; 图的遍历:深度优先搜索与广度优先搜索; 最小生成树的构造;最短路径。 8.排序 插入(直接和希尔)、选择(直接和堆)、交换(冒泡和快速)、归并、基数等排序算法的基本思想; 各排序算法的实现、时间复杂度和稳定性。 9.查找 查找的基本概念;静态查找表;动态查找表;哈希表; 各种查找算法的实现。 Ⅲ 考试形式及试卷结构 一、考试形式: 闭卷,笔试,考试时间为120分钟,试卷满分为100分。考生使用答题卡答题。 二、试题题型及赋分: 1、选择题………………………………约占30% 2、判断题………………………………约占15% 3、填空题………………………………约占15% 4、概念与术语解释题…………………约占10% 5、分析简答及应用题…………………约占20% 6、算法设计与分析题…………………约占10% Ⅳ 题型示例 一、单项选择题 1. 从逻辑上可以把数据结构分为( )两大类。 A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造型结构 2. 线性表是( )。 A.一个有限序列,可以为空 B.一个有限序列,不能为空 C.一个无限序列,可以为空 D.一个无限序列,不能为空 二、判断题(正确的在括号内填√,错识的填×) ( )1. 算法必须有输出,但可以没有输入。 ( )2.顺序表的插入和删除操作不需要付出很大的时间代价,因为每次操作平均只有近一半的元素需要移动。 三、填空题
1.已知指针p指向单链表L中的某结点,则删除其后继结点的语句序列是: ; ; 。 四、概念与术语解释 1. 算法的时间复杂度 2. 查找表 五、分析简答及应用题 1. 请分别写出线性表的链式存储结构、二叉树的二叉链表存储结构的类C语言描述。 六、算法设计与分析题(请加适当的注释) 单链表L是一个递减有序表,试编写高效算法,删除表中值大于min且小于max的结点,同时释放被删结点的空间,这里min和max是两个给定的参数。请分析你的算法的时间复杂度。 Ⅴ 参考书目 《数据结构与算法》(第2版),张晓莉、王苗等编著,北京,机械工业出版社,2008年。 (责任编辑:admin) |