北京自考教材07013算法与数据结构考试大纲下载

北京市高等教育自学考试课程考试大纲
课程名称：算法与数据结构 课程代码：07013（笔试） 2021年6月版
07014（实践）
第一部分 课程性质与设置目的
一、课程性质与特点
《算法与数据结构》是信息管理与信息系统(专升本）专业的核心基础选考课程。本课程主要讲述数据结构的基本概念、基本原理和基本应用，主要包括各种常用数据结构的逻辑结构、存储结构及有关操作的算法等。
通过本课程学习，使考生提高数据抽象能力、数学建模能力和程序设计的能力，在掌握计算机的典型数据结构的特性的基础上，能够为应用涉及的数据选择合适的数据结构和算法，并初步掌握对算法的时间分析和空间分析技术。通过本课程的学习和编程实践，进一步提高软件设计和编程能力，为后续课程的学习打好必要的理论基础。
二、课程目标与基本要求
本课程的目标是全面贯彻落实立德树人根本任务，通过本课程的学习，考生应掌握数据组织、存储和运算的基本原理和方法，具备对各类数据结构和相关算法的分析和设计的能力，能够编写出正确、清晰和较高质量的算法和程序。学生应比较系统地从数据结构的逻辑结构、存储结构和运算三个方面去掌握线性表、栈、队列、数组、广义表、树和图常用的数据结构；并且掌握在各种常用的数据结构上实现的排序和查找等算法，同时对算法的时间和空间复杂性有一定的分析能力；针对简单的应用问题，应能选择合适的数据结构，并设计有效的解决算法。这对于培养考生运用数据结构解决实际问题能力的培养有着重要的意义。
本课程的考核章节为第1章、第2章1-3节、第3章第1-2节第4节、第5章第1-5节、第6章第1-4节第6节、第7章、第9章、第10章，重点章节是：第 2章第1-3节、第3章第1-2节第4节、第5章第1-5节、第6章第1-4节第6节、第7章、第9章、第10章 ，不考核章节为第2章第4节、第3章第3节第5节、第4章、第5章第6-7节、第6章第5节第7-8节、 第8章、第11章、第12章 。实践部分的考核章节为第 2章、第3章、第5章、第6章、第7章、第9章、第10章 。
三、与本专业其他课程的关系
《算法与数据结构》是信息管理与信息系统等专业的核心基础课程。本课程的先修课程为计算机科学导论和高级程序设计语言。本课程的大部分实例都是C语言实现，故要求学生熟悉并掌握C语言程序设计。
本课程的重点是掌握各种数据结构的逻辑结构，该逻辑结构对应的存储结构及其运算。难点是对算法进行时间和空间复杂性的分析。
考生在学习本课程时，要善于把每种逻辑结构相关的基本理论与算法实现过程结合起来，这样对算法的实现和掌握有一个深刻地理解，从中得到启迪和借鉴，提高分析思维能力。同时，为了较好地理解和掌握各种逻辑结构和存储结构，要勤于思考、联系实际。

第二部分 考核内容与考核目标
第1章 绪 论
一、学习目的与要求
通过本章的学习，要求考生掌握数据结构的基本概念、术语以及学习数据结构的意义；了解数据的抽象类型定义；理解算法在实际问题中的应用，算法和算法的量度，算法描述和分析的方法。
二、考核知识点与考核目标
（一）数据结构基本概念和术语
识记：数据、数据元素、数据对项、数据结构等基本概念。
（二）抽象数据类型的表示与实现
识记：数据结构的四种逻辑结构和两种存储结构表示方法。
理解：抽象数据类型的表示和实现。
（三）算法和算法分析
识记：算法的五个特点，算法、算法的时间复杂度和空间复杂度、最坏的和平均的时间复杂度等概念。
理解：算法描述和算法分析的方法，对于一般算法能分析出算法的时间复杂度和空间复杂度、最坏的和平均的时间复杂度。
第2章 线性表
一、学习目的与要求
通过本章的学习，要求考生掌握线性表的逻辑结构和各种存储表示方法，定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。要求在熟悉这些内容的基础上，能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。
本章重点是熟练掌握顺序表和单链表上实现的各种基本运算及相关的时间性能分析，难点是在循环链表和双向链表存储结构中各种基本运算的实现。
二、考核知识点与考核目标
（一）线性表的类型定义
识记：线性表的逻辑结构特征。
理解：线性表上定义的基本运算，利用基本运算构造出较复杂的运算。
（二）线性表的顺序表示和实现
识记：顺序表的含义及特点。
理解：顺序表上的插入、删除操作及其平均时间性能分析。
（三）线性表的链式表示和实现
识记：单链表、双链表、循环链表的概念。
理解：单链表、双链表、循环链表链接方式上的区别；单链表、双链表、循环链表上的插入、删除操作及其平均时间性能分析；顺序表和链表的比较，各自的优缺点；针对线性表上所需要执行的主要操作，知道选择顺序表还是链表作为其存储结构才能取得较优的时空性能；双链表的定义和相关算法。
（四）线性表应用实例
应用：针对相关应用问题，能够合理选择顺序表和链表，具有设计线性问题和迭代、贪心问题求解算法的能力。
第3章 栈和队列
一、学习目的与要求
通过本章的学习，要求考生掌握栈和队列的逻辑结构定义及在两种存储结构上如何实现栈和队列的基本运算。要求在掌握栈和队列的特点的基础上，根据实际应用问题正确的选择使用栈或队列。
本章重点是掌握栈和队列在两种存储结构上实现的基本运算，难点是循环队列中对边界条件的处理。
二、考核知识点与考核目标
（一）栈
理解：栈的抽象数据类型的定义、特点，栈的表示和实现，基本操作的实现。
（二）栈的应用举例
理解：栈的简单应用。
应用：栈的逻辑结构特点，栈与线性表的异同；顺序栈和链栈上实现进栈、退栈等基本算法；利用栈解决简单的实际问题。
（三）队列
理解：队列的抽象数据类型的定义、特点，队列的表示和实现，基本操作的实现。
理解：队列的简单应用。
应用：队列的逻辑结构特点，队列与线性表的异同；顺序队列和链队列上实现的入队、出队等基本算法；利用队列解决简单的实际问题。
第5章 数组和广义表
一、学习目的与要求
通过本章的学习，要求考生掌握多维数组的逻辑结构特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念，要求熟悉这些内容。
本章重点是熟悉多维数组的存储方式、矩阵的压缩存储方式、广义表的定义及其表头表尾的运算，难点是稀疏矩阵的压缩存储表示下转置运算。
二、考核知识点与考核目标
（一）数组的定义
理解：数组的概念及逻辑关系。
（二）数组的顺序表示和实现
理解：掌握数组的顺序存储结构；多维数组的逻辑结构特征；多维数组的顺序存储结构及其地址计算方式。
应用：理解稀疏数组的概念和压缩存储的方法。
（三）矩阵的压缩存储
识记：特殊矩阵和稀疏矩阵的概念。
理解：矩阵的压缩存储、特殊矩阵的表示；稀疏矩阵的压缩存储方式——三元组表，稀疏矩阵的两种转置运算算法；稀疏矩阵的十字链表存储结构。
（四）广义表的定义
理解：广义表的概念及逻辑关系。
（五）广义表的存储结构
理解：广义表的存储结构和操作特点。
第6章 树和二叉树
一、学习目的与要求
通过本章的学习，要求考生掌握二叉树的定义、性质、存储结构、遍历、线索化，树的定义、存储结构、遍历、树和森林的转换及赫夫曼树及其赫夫曼编码等内容。本章重点是掌握二叉树及其二叉树的遍历。难点是掌握与树有关的简单应用。
二、考核知识点与考核目标
（一）树的定义和基本术语
识记：树的定义、常用术语及含义。
理解：树的逻辑结构特征，树的不同表示方法。
（二）二叉树
识记：二叉树的定义及树与二叉树的差别。
理解：二叉树的性质及证明；二叉树的两种存储结构、特点及适用范围；二叉树（完全二叉树、满二叉树）的定义和性质。
（三）遍历二叉树和线索二叉树
理解：二叉树的三种遍历算法，其执行过程；根据给定的叶结点及其权值构造出相应的最优二叉树；最优二叉树和前缀编码的概念及特点；二叉树线索化的目的及实质，在中序线索树中查找给定结点的中序前驱和中序后继的方法。
应用：根据不同的遍历方法，应能得出其相应的结点访问次序；以遍历算法为基础，设计有关算法解决简单的应用问题。
（四）树和森林
理解：树和森林及二叉树的转换方法；树和森林的遍历；树的路径长度、树的带权路径长度。
（五）赫夫曼树及其应用
理解：赫夫曼算法的思想；赫夫曼编码方法；根据最优二叉树构造对应的赫夫曼编码。
第7章 图
一、学习目的与要求
通过本章的学习，要求考生掌握图的基本概念、两种常用的存储结构、两种遍历方法以及图的应用算法。本章重点是掌握图的两种存储结构上实现的遍历算法。难点是图的应用算法：最小生成树，求最短路径以及拓扑排序。要求掌握这些算法的基本思想及时间性能。
二、考核知识点与考核目标
（一）图的定义和术语
识记：图的逻辑结构及特征；图的常用术语及含义；生成树和最小生成树的概念。
（二）图的存储结构
理解：图的邻接矩阵表示法存储结构；邻接表表示法。
应用：根据应用问题的特点选择合适的图的存储结构。
（三）图的遍历
理解：图的深度优先遍历；图的广度优先遍历；对给定的图进行遍历，画出深度优先和广度优先生成树或森林。
应用：连通图及非连通图的深度优先搜索和广度优先搜索两种遍历算法；确定两种遍历的顶点访问序列；图的两种遍历和树的遍历之间的关系；两种遍历算法分别使用的数据结构（栈和队列）；利用图的遍历解决简单的应用问题。
（四）图的连通性问题
理解：生成树和最小生成树；构造最小生成树的PRIM算法思想和时间性能；构造最小生成树的Kruskal算法思想和时间性能；根据Prim和Kruskal算法构造最小生成树。
（五）有向无环图及其应用
理解：拓扑排序的基本思想和步骤；拓扑排序不成功的原因；对给定的有向图，若拓扑序列存在，则要求写出一个或多个拓扑序列。
（六）最短路径
识记：最短路径的含义。
理解：最短路径的Dijkstra算法思想和时间性能，最短路径的Floyd算法思想和时间性能。
第9章 查找
一、学习目的与要求
通过本章的学习，要求考生掌握线性表、树和哈希表的查找方法、算法实现以及各种查找方法的时间性能（平均查找长度）分析。重点掌握顺序查找、折半查找、二叉排序树和哈希表查找的基本思想和算法实现。难点是二叉排序树上的删除算法。
二、考核知识点与考核目标
（一）静态查找表
识记：查找成功、不成功的含义。
理解：顺序查找、折半查找、分块查找的基本思想、算法实现和查找效率分析；顺序查找中“监视哨”的作用。
应用：比较线性表上三种查找方法的优缺点，能根据实际问题的要求和特点，选择出合适的查找方法。
（二）动态查找表
理解：二叉排序树和二叉平衡树的定义、特点；二叉排序树的插入、删除、建树和查找算法及时间性能；建立一棵二叉排序树的过程就是对输入序列的排序过程，输入序列对所建立的二叉排序树形态的影响。
应用：构造二叉排序树。
（三）哈希表
理解：哈希表、哈希函数、哈希地址（散列地址）、装填因子等有关概念；哈希法的特点；哈希函数的构造方法和解决冲突的方法；哈希表和其它表的本质区别。
应用：使用哈希表解决实际的数据查找问题。
第10章 内部排序
一、学习目的与要求
通过本章的学习，要求考生掌握四类内部排序方法的基本思想、排序过程、算法实现、时间和空间性能的分析以及各种排序方法的比较和选择。重点掌握快速排序、堆排序、归并排序和基数排序的基本思想和排序过程。难点是这四类排序算法的实现。
二、考核知识点与考核目标
（一）概述
识记：排序方法稳定性的含义；排序方法的分类及算法好坏的评判标准。
理解：冒泡排序的基本思想。
（二）插入排序
理解：直接插入排序的算法、折半插入排序的算法、希尔排序的思想；直接插入排序的基本思想和算法实现，以及在最好、最坏和平均情况下的时间性能分析；直接插入排序中“监视哨”的作用。
应用：针对给定的输入序列，要能写出直接插入排序和希尔排序的排序过程。
（三）快速排序
理解：快速排序的基本思想和算法实现，以及在最好、最坏和平均情况下的时间性能分析，排序算法的稳定性；枢轴元素的选择对排序的影响。
应用：针对给定的输入序列，能写出快速排序的排序过程。
（四）选择排序
理解：选择排序的思想；堆、最小堆、最大堆、堆顶等有关概念和定义；堆的性质及堆与完全二叉树的关系。
应用：直接选择排序和堆排序的基本思想和算法实现，以及时间性能分析；针对给定的输入序列，能写出直接选择排序和堆排序的排序过程。
（五）归并排序
理解：归并排序的基本思想和算法实现，以及时间性能分析。
应用：针对给定的输入序列，能写出归并排序的排序过程。
（六）基数排序
理解：基数排序的基本思想和特点。
应用：针对给定的输入序列，能写出基数排序的排序过程。
（七）各种内部排序方法的比较讨论
理解：比较各种排序算法的优缺点；根据实际问题的特点和要求选择合适的排序方法。

第三部分 实践环节
第2章 线性表
一、考核的目的与要求
考核考生对线性表的构造、分析和应用能力。
二、考核的内容
1.利用C语言实现顺序表和链表的应用问题。
2.提交程序及程序说明书。程序说明书重点介绍所编写的软件功能及实现步骤。
第3章 栈和队列
一、考核的目的与要求
考核考生对栈和队列的构造、分析和应用能力。
二、考核的内容
1.利用C语言实现栈和队列的应用问题。
2.提交程序及程序说明书。程序说明书重点介绍所编写的软件功能及实现步骤。

第5章 数组和广义表
一、考核的目的与要求
考核考生对广义表的构造、分析和应用能力。
二、考核的内容
1. 利用C语言实现广义表的基本操作和应用问题。
2.提交程序及程序说明书。程序说明书重点介绍所编写的软件功能及实现步骤。

第6章 树和二叉树
一、考核的目的与要求
考核考生对树和二叉树的构造、分析和应用能力。
二、考核的内容
1. 利用C语言实现树的基本操作和二叉树应用问题。
2.提交程序及程序说明书。程序说明书重点介绍所编写的软件功能及实现步骤。

第7章 图
一、考核的目的与要求
考核考生对图的构造、分析和应用能力。
二、考核的内容
1. 利用C语言实现图的基本操作和应用问题。
2.提交程序及程序说明书。程序说明书重点介绍所编写的软件功能及实现步骤。

第9章 查找
一、考核的目的与要求
考核考生对各种不同的查找算法的实现、分析和应用能力。
二、考核的内容
1. 利用C语言实现不同查找算法和应用问题。
2.提交程序及程序说明书。程序说明书重点介绍所编写的软件功能及实现步骤。

第10章 内部排序
一、考核的目的与要求
考核考生对各种排序算法的分析和应用能力。
二、考核的内容
1. 利用C语言实现各种排序算法的比较分析。
2.提交程序及程序说明书。程序说明书重点介绍所编写的软件功能及实现步骤。

第四部分 有关说明与实施要求
一、考核目标的能力层次表述
本大纲在考核目标中，按“识记”、“理解”、“应用”三个能力层次规定考生应达到的能力要求，各能力层次为递进等级关系，后者必须建立在前者的基础上，其含义为：
识记：能了解相关的名词、概念、知识的含义，并能正确认识和表述。
理解：在识记的基础上，能全面把握基本概念、基本原理、基本方法，能掌握有关概念、原理、方法的区别与联系。
应用：在理解的基础上，能运用基本概念、基本原理、基本方法及技能，分析和解决有关的理论和实际问题，并能够运用多个知识点进行综合分析，解决问题。
二、教材
教材：《数据结构（C语言版）》，严蔚敏,吴伟民编，清华大学出版社, 1997年版
参考书：《数据结构（C语言描述）》，殷人昆编，清华大学出版社, 2012年版
三、自学方法指导
1．在开始学习指定教材每一章之前，应先阅读大纲中有关这一章考核知识点及对知识点的能力层次要求和考核目标，以便在阅读教材时做到心中有数，有的放矢。
2．阅读教材时，要仔细阅读，逐句推敲，吃透每一个知识点，深刻理解基本概念、基本理论，牢固把握基本方法与技能。
3．自学过程中，既要思考问题，也要做好阅读笔记，把教材中的基本概念、原理、方法加以梳理，注意所学内容纵向和横向的联系，这样可从中加深对问题的认知、理解和记忆，以利于突出重点，并涵盖整个学习内容。
4．完成教材中大纲要求学习的各章的考试复习题，这是理解、消化和巩固所学知识的重要环节。在做练习之前，应认真阅读教材，按考核目标所要求的不同层次，掌握教材内容，解题时应注意培养逻辑性，针对问题围绕相关知识点进行层次（步骤）分明的论述，明确各层次（步骤）间的逻辑关系。
四、对社会助学的要求
1．应熟知考试大纲对课程提出的目标总要求和各章掌握的知识点。
2．应熟知各知识点要求达到的能力层次，并深刻理解各知识点的考核目标。
3．辅导时，应以考试大纲为准，指定教材为基础，避免随意超纲，以免与大纲脱节。
4．辅导时，应对考生学习方法进行指导，宜提倡“认真阅读教材，刻苦钻研教材，勤于提问，依靠自己学通”的方法。
5．辅导时，要注重考生自学能力、观察和思维理解能力、分析解决问题能力及创新意识的培养。要引导考生逐步学会独立学习，在自学过程中善于提出问题，分析问题，做出判断，解决问题。
6．辅导时，要注意突出重点，对考生要启发引导，不可让考生死记硬背；对考生提出的问题，不要有问必答，要积极启发引导。
7．辅导时，协助考生理解知识点的能力层次，不可将试题难易与能力层次直接挂钩。
8．助学学时：本课程共5学分，理论课4学分，学时72；实践课1学分，学时18；总课时90学时，建议助学课时分配如下：
章次
内 容
学时
理论课

第1章
绪论
4
第2章
线性表
8
第3章
栈和队列
8
第5章
数组和广义表
6
第6章
树和二叉树
14
第7章
图
12
第9章
查找
8
第10章
内部排序
12
合计
72
实践课

第2章
线性表
2
第3章
栈和队列
2
第5章
数组和广义表
2
第6章
树和二叉树
3
第7章
图
3
第9章
查找
3
第10章
内部排序
3
合计
18
总计
90
五、关于命题考试的若干规定
1．本大纲各章所提到的考核内容和考核目标都是考试内容。试题覆盖到章，适当突出重点，试题内容不超纲。
2．试卷中试题比例一般为识记占30%、理解占50%、应用占20%。
3．反映不同难易度的试题分数比例一般为较易、中等难度共占80%、较难占20%。
4．试题类型：
笔试部分：单项选择题、填空题、简答题、综合题。
5. 考核方式：
（1）笔试部分考核方式：采用闭卷笔试，考试时间为150分钟，采用百分制评分，60分合格。
（2）实践部分考核方式：
① 考核环境
考核的软件： Devcpp
考核的环境：Devcpp 是一个免费的C语言IDE环境。
计算机硬件配置的建议：
Windows 7版本以上，要求能兼容Devcpp安装即可，硬盘预留20G以上数据空间。
② 考核方式
考核采取现场实际操作和笔试、面试、口答相结合方式，采用终结性考核。
程序实验环境自备，并带黑色签字笔。
考核时间60-90分钟。课程采用四级制记分，合格线为“及格”。
六、题型示例
A.笔试题
（一）单项选择题
下面关于算法的叙述中，正确的是
A．在相同的规模n下，复杂度为O(n)的算法在时间上总是优于复杂度为O(n^2)的算法
B．算法的优劣与算法描述语言无关，但与所用计算机有关
C．同一个算法，实现语言的级别越高，执行效率就越低
D．健壮的算法不会因非法的输入数据而出现莫名其妙的状态
（二）填空题
若用一个大小为9的数组（0…8）来实现循环队列，当前rear和front的值分别为7和0，当从队列中删除一个元素，再加入两个元素后，rear的值为 。
（三）简答题
已知一棵二叉树的中序遍历序列是C, B, E, A, F, G,D和按照层次顺序遍历序列是A, B, D, C, E, F, G。
（1）请画出该二叉树；
（2）请画出该树进行后序序列线索化树。
（四）综合题
假设二叉树T每条边的代价都为1，请写一个递归算法，求出从根节点到达所有叶子节点的路径中最长路径的长度。假设二叉树采用二叉链表表示，其定义如下：
typedef struct BiTNode { // 结点结构
TElemType data;
struct BiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode, *BiTree;

B.实践题
利用C语言设计并模拟实现服务台前的排队现象问题。
问题描述：
某银行有一个客户办理业务站，在单位时间内随机地有客户到达，设每位客户的业务办理时间是某个范围内的随机值。设只有一个窗口，一位业务人员，要求程序模拟统计在设定时间内，业务人员的总空闲时间和客户的平均等待时间。假定模拟数据已按客户到达的先后顺序依次存于某个正文数据文件中。对应每位客户有两个数据，到达时间和需要办理业务的时间。
2