数据结构考试要求大纲.docVIP

《数据结构》考试大纲 一、课程基本信息 1.课程代码： 104012141 2.课程类别：专业基础课 3.学分：4 4.适用专业： 计算机科学与技术 二、课程考试内容与要求 第1章概论 （一）课程内容 1.1基本概念和术语 1.2学习数据结构的意义 1.3算法的描述和分析 （二）学习目的与要求 本章的目的是介绍数据结构中常用的基本概念和术语以及学习数据结构的意义，要求了解本章介绍的各种基本概念和术语，掌握算法描述和分析的方法。本章重点是了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念及相互关系，难点是算法复杂度的分析方法。 （三）考核知识点与考核要求 1.数据结构的基本概念和术语、要求达到“识记”层次。 1.1数据、数据元素、数据项、数据结构等基本概念。 1.2数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。 1.3数据结构的两大类逻辑结构和四种常用的存储表示方法。 2.数据结构在软件系统中的作用，要求达到“识记”层次。 2.1数据结构在各种软件系统中所起的作用。 2.2选择合适的数据结构是解决应用问题的关键步骤。 3.算法的描述和分析，要求达到“领会”层次。 3.1算法、算法的时间复杂度和空间复杂度、最坏的和平均的时间复杂度等概念。 3.2算法的时间复杂度不仅仅依赖于问题的规模，也取决于输入实例的初始状态。 3.3算法描述和算法分析的方法，对于一般算法能分析出时间复杂度。 第2章线性表 （一）课程内容 2.1线性表的逻辑结构 2.2线性表的顺序存储结构 2.3线性表的链式存储结构 2.4顺序表和链表的比较 （二）学习目的与要求 本章目的是介绍线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。要求在熟悉这些内容的基础上，能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。本章重点是熟练掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析，难点是能够使用本章所学到的基本知识设计有效算法解决与线性表相关的应用问题。 （三）考核知识与考核要求 1.线性表的逻辑结构，要求达到“识记”层次。 1.1线性表的逻辑结构特征。 1.2线性表上定义的基本运算，并能利用基本运算构造出较复杂的运算。 2.线性表的顺序存储结构，要求达到“综合利用”层次。 2.1顺序表的含义及特点，即顺序表如何反映线性表中元素之间的逻辑关系。 2.2顺序表上的插入、删除操作及其平均时间性能分析。 2.3利用顺序表设计算法解决简单的应用问题。 3.线性表的链式存储结构，要求达到“综合应用”层次。 3.1链表如何表示线性表中元素之间的逻辑关系。 3.2链表中头指针和头结点的使用。 3.3单链表、双链表、循环链表链接方式上的区别。 3.4单链表上实现的建表、查找、插入和删除等基本算法，并分析其时间复杂度。 3.5循环链表上尾指针取代头指针的作用，以及单循环链表上的算法与单链表上相应算法的异同点。 3.6双链表的定义及其相关的算法。 3.7利用链表设计算法解决简单的应用问题。 4.顺序表和链表的比较，要求达到“领会”层次。 4.1顺序表和链表的主要优缺点。 4.2针对线性表上所需要执行的主要操作，知道选择顺序表还是链表作为其存储结构才能取得较优的时空性能。 第3章栈和队列 （一）课程内容 3.1栈 3.2队列 3.3栈和队列的应用 （二）学习目的与要求 本章目的是介绍栈和队列的逻辑结构定义及在两种存储结构上如何实现栈和队列的基本运算。要求在掌握栈和队列的特点的基础上，懂得在什么样的情况下能够使用栈或队列。本章重点是掌握栈和队列在两种存储结构上实现的基本运算，难点是循环队列中对边界条件的处理。 （三）考核知识与考核要求 1.栈的逻辑结构、存储结构及其相关算法，要求达到“综合应用”层次。 1.1栈的逻辑结构特点，栈与线性表的异同。 1.2顺序栈和链栈上实现的进栈、退栈等基本算法。 1.3栈的“上溢”和“下溢”的概念及其判别条件。 1.4利用栈设计算法解决简单的应用问题。 2.队列的逻辑结构、存储结构及其相关算法，要求达到“综合应用”层次。 2.1队列的逻辑结构特点，队列与线性表的异同。 2.2顺序队列（主要是循环队列）和链队列上实现的入队、出队等基本算法。 2.3队列的“上溢”和“下溢”的概念及其判别条件。 2.4使用数组实现的循环队列取代普通的顺序队列的原因。 2.5循环队列中对边界条件的处理方法。 2.6利用队列设计算法解决简单的应用问题。 3.栈和队列的应用，要求达到“领会”层次。 栈和队列的特点，什么样的情况下能够使用栈或队列。 第4章串 （一）课程内容 4.1串及其运算 4.2串的存储结构 （二）学习目的与要求 本章目的是介绍串的逻辑结构