2021年武昌首义学院专升本《数据结构》考试大纲

　　《数据结构》考试大纲

　　一、考试性质

　　数据结构是计算机学科的重要骨干基础课程，所有计算机系统软件和应用软件都要用到各种类型的数据结构以及一些典型的算法设计和分析技巧。课程教学应达到的目标是使学生掌握数据的逻辑结构、存储结构和数据运算的基本理论、基本知识和基本技能，并具有利用计算机解决实际应用问题的能力。数据结构课程既是对以往课程的深入和扩展，也是为将来更加深入地学习后续专业课程打下基础。课程所涉及基本的树、图等数据结构，是计算机科学的基本功。树结构、图结构等数据结构，是数据库、操作系统、编译原理等后续课程的基础。

　　本考试是为在计算机专科毕业生中招收本科生，实施的具有选拔功能的水平考试，指导思想是既有利于国家对高层次人才的选拔，又利于促进高等学校课程教学质量的提高。

　　二、考试的基本要求

　　要求学生比较系统地掌握数据结构的基本知识和基本技能，初步具有在明确所要解决的问题的基础上，经过对问题的深入分析和抽象，为其在计算机中建立一个模型，然后确定恰当的数据结构表示该模型，再在此基础上设计合适的算法，最后根据设计的数据结构和算法进行相应的程序设计来模拟和解决实际问题，为后继专业课程学习提供基础。

　　三、考试方法和考试时间

　　考试方法为闭卷笔试，考试时间为90分钟，满分为100分。

　　四、考试内容和要求

　　第1 章 数据结构基础

　　1、考试内容

　　数据结构的基本概念和基本术语，算法的描述和算法分析。

　　2、基本要求

　　1)数据、数据元素、数据对象、数据结构等基本概念。

　　2)数据的逻辑结构、存储结构、算法的概念。

　　3)数据类型、抽象数据类型的概念。

　　4)时间复杂度、空间复杂度的概念以及简单算法时间复杂度的计算。

　　5)数据结构二元组的概念。S=(D,R)

　　第2 章 线性表

　　1、考试内容

　　线性表的定义、线性表的逻辑结构、线性表的顺序存储结构和链式存储结构，单向链表、循环链表。

　　2、基本要求

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

　　2)线性表的顺序存储结构及其运算的实现。

　　3)线性表的链式存储结构及其运算的实现。

　　4)单链表、循环链表的特点。

　　第3 章 栈和队列

　　1、考试内容

　　栈和队列的定义、表示方法和实现。

　　2、基本要求

　　1)栈和队列的定义、基本运算。

　　2)栈和队列的顺序实现及其运算的实现。

　　3)栈和队列的链式实现及其运算的实现。

　　4)栈和队列的应用。

　　5)理解递归的概念。

　　第4 章 串

　　1、考试内容

　　串的定义及其基本操作。

　　2、基本要求

　　1)串的定义。

　　2)串的几种表示方法。

　　3)串的基本操作。

　　第5 章 数组和广义表

　　1、考试内容

　　数组的定义、运算和存储、稀疏矩阵的压缩存储、广义表的定义和操作。

　　2、基本要求

　　1)数组的定义。

　　2)稀疏矩阵的存储。

　　3)广义表的概念。

　　第6 章 树

　　1、考试内容

　　树的定义、基本术语和存储结构，二叉树的定义和性质、二叉树的存储结构及其各种操作，哈夫曼树及编码。

　　2、基本要求

　　1)树的定义及其存储结构。

　　2)二叉树的定义和性质。

　　3)二叉树的存储结构，包括顺序和链式存储。

　　4)二叉树的遍历、递归算法及其应用。

　　5)哈夫曼树及哈夫曼编码。

　　第7章 图

　　1、考试内容

　　图的定义和术语、图的存储结构及其各种操作。

　　2、基本要求

　　1)图的基本概念。

　　2)图的存储结构(邻接矩阵、邻接表)。

　　3)图的遍历方法(深度优先遍历、广度优先遍历)。

　　4)图的最小生成树的算法(prim 算法、kruskal 算法)。

　　第8章查找

　　1、考试内容

　　各种查找方法的算法、适用范围及时间复杂度的分析。

　　2、基本要求

　　1)各种静态查找技术和算法(顺序查找、折半查找)。

　　2)动态查找的概念(二叉查找树、AVL树)。

　　3)散列表的概念。

　　4)散列函数构造方法以及处理冲突的办法

　　第9章排序

　　1、考试内容

　　多种排序算法的基本思想和算法的时间复杂度分析，不同排序方法的比较。

　　2、基本要求

　　1)排序的基本概念(关键字、内外排序、稳定性等)

　　2)选择排序的方法(简单选择排序)

　　3)插入排序的方法(直接插入排序)

　　4)交换排序的方法(冒泡排序)

　　5)各种排序方法的优缺点。

　　五、命题要求

　　本课程命题范围应涵盖课程的所有章节，试题难易程度分为，较易占50%，中等难度占30%，较难占20%。在题型结构上，主要包括客观题和主观题。

　　1)选择题：20%

　　2)填空题：15%

　　3)判断题： 10%

　　4)简答题：15%

　　5)应用题： 30%

　　6)编程题：10%

　　六、主要参考书目

　　1、程海英.数据结构(C语言版).北京：清华大学出版社，2014.

　　2、严蔚敏，李冬梅，吴伟民.数据结构(C语言版).第2版.北京：人民邮电出版社，2016.

　　3、程海英，彭文艺.数据结构案例教程(C语言版).北京：电子工业出版社，2019.

（编辑：trh）