2020兰州文理学院专升本软件工程专业考试大纲（试行）(2)

【导读】华图甘肃医疗人才网提供以下社会招聘考试信息：兰州文理学院招生信息网发布：2020兰州文理学院专升本软件工程专业考试大纲（试行）(2),关注公众号：甘肃华图(gshtjy),获取更多资讯！

　　(一)数据结构　部分(100分)

　　一、考试目的

　　全面考核普通高校专科(含高职)应届毕业生《数据结构》课程是否达到教学大纲所规定的目标。数据结构部分主要考核对数据结构中基本概念和原理的掌握情况;要求考生具有抽象思维能力、逻辑推理能力、综合运用所学的知识分析问题和解决问题的能力，以及基本程序设计和编程能力。

　　二、考试范围

　　主要涵盖陈元春主编《实用数据结构》(中国铁道出版社2011年第三版)中所选定的内容，重点考核数据结构中线性表、栈、队列、树、图、查找、排序等内容的基本概念、原理及其应用能力。考试不追求偏题怪题，以基础知识为出题的核心内容。所有试题都严格选自课本内容。

　　三、考试内容

　　考试内容包括七个部分：基础知识、线性表、栈、队列、串、多维数组、广义表、树、二叉树、图、查找、排序等内容的掌握，以及对相关简单算法的掌握和应用。

　　第一部分：基础知识，共5分。

　　该部分考察学生对数据结构基本概念和术语，算法的概念、描述方法以及算法分析的理解和掌握情况。

　　(1)理解数据、数据元素、数据对象、数据结构和数据类型等概念的定义。

　　(2)掌握数据的逻辑结构和存储结构及其种类，算法的重要特征。

　　(3)了解算法的时间复杂度和空间复杂度的概念。

　　第二部分：线性表，共10分。

　　该部分考察学生对线性表的定义、逻辑结构、顺序存储结构和链式存储结构方式，单向链表、循环链表和双向链表的概念和表示，一元多项式的表示及相加等内容的理解和掌握情况。

　　(1)了解线性表的定义和线性结构的特点。

　　(2)理解线性表的顺序存储和链式存储方式，理解顺序和链式存储方式的优缺点。

　　(3)掌握线性顺序表中数据元素的存储位置的计算。

　　(4)掌握顺序表、单向链表、循环链表和双向链表的插入、删除等有关操作。

　　(5)会用单链表编写插入、删除等有关算法。

　　第三部分：栈和队列，共10分。

　　该部分考察学生对栈的定义、表示和实现，队列的定义、表示和实现，链队列，循环队列，栈的应用等内容的理解和掌握情况。

　　(1)了解栈和队列的定义。

　　(2)理解线性表、栈和队列特点及区别，栈对实现递归过程的作用。

　　(3)掌握顺序栈、链栈的入栈和出栈操作，顺序队列、链队列的入队和出队操作，循环队列的队空和队满的判断条件。

　　(4)会编写入栈和出栈，入队和出队的有关算法。

　　(5)了解栈的相关应用，数制转换、表达式求值、子程序调用、递归调用等算法。

　　第四部分：串、多维数组和广义表，共10分。

　　该部分考察学生对串的有关定义、逻辑结构、静态存储结构、动态存储结构以及基本操作及应用，数组的定义和运算、顺序存储结构，特殊矩阵、稀疏矩阵的定义、压缩存储，广义表的定义、存储结构等内容的理解和掌握情况。

　　(1)了解串的有关定义。

　　(2)理解串的逻辑结构和定长顺序存储结构、链接存储以及堆分配存储结构。

　　(3)掌握串的模式匹配传统方法。

　　(4)了解多维数组、特殊矩阵和稀疏矩阵的定义，广义表的概念和链表表示。

　　(5)理解特殊矩阵的压缩存储的概念。

　　(6)掌握矩阵的压缩存储的有关计算方法。

　　(7)掌握广义表的首尾存储法。

　　第五部分：树和二叉树，共20分。

　　该部分考察学生对树的结构定义和基本操作，二叉树的定义、性质、存储结构、遍历二叉树和线索二叉树，树的存储结构，森林与二叉树的转换，树的遍历，标识符树和哈夫曼树及其编码等内容的理解和掌握情况。

　　(1)了解树的定义和二叉树的定义。

　　(2)理解二叉树的性质、二叉树的存储结构。

　　(3)掌握遍历二叉树的方法、线索二叉树的构造，森林与二叉树的转换，最优二叉树和哈夫曼编码方法。

　　(4)会利用二叉树的先根、中根和后根遍历解决有关二叉树的应用问题，会编写与二叉树有关的算法。

　　 （编辑：华图_潇潇）