《二年级Access数据库程序设计专用教材》由会员分享，可在线阅读，更多相关《二年级Access数据库程序设计专用教材（312页珍藏版）》请在金锄头文库上搜索。
1、 Revised as of 23 November 2020二年级Access数据库程序设计专用教材目录第一部分公共基础知识第1章数据结构与算法考纲分析1算法的基本概念，算法复杂度的概念和意义（时间复杂度与空间复杂度）。2数据结构的定义，数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。3线性表的定义，线性表的顺序存储结构及其插入与删除运算。4栈和队列的定义，栈和队列的顺序存储结构及其基本运算。5线性单链表、双向链表与循环链表的结构及其基本运算。6树的基本概念，二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。7顺序查找与二分法查找算法，基本排序算法（交换类排序
2、，选择类排序，插入类排序）。考点精讲算法考点1算法的基本概念（1）算法的定义算法是指解题方案的准确而完整的描述，即算法是对特定问题求解步骤的一种描述。它是一组严谨定义运算顺序的规则，且每个规则都是明确有效的，此顺序将在有限的次数下终止。需要注意的是：算法不等于程序，也不等于计算方法。（2）算法的基本特征可行性a算法中的每一步骤都必须能够实现；b算法执行的结果要能够达到预期的目的。确定性确定性是指算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释，也不允许有多义性。有穷性有穷性是指算法必须能在有限的时间内做完，即必须能在执行有限个步骤之后终止，且必须有合理的执行时间。拥有足够的情报算法
3、是否有效，取决于为算法所提供的情报是否足够。一般而言，当算法有足够的情报时，此算法有效，而当提供的情报不够时，算法可能无效。【真题演练】算法的有穷性是指（ ）。2013年9月真题A算法程序的运行时间是有限的B算法程序所处理的数据量是有限的C算法程序的长度是有限的D算法只能被有限的用户使用【答案】A【解析】算法设计有穷性要求操作步骤有限且必须在有限时间内完成，耗费太长时间得到的正确结果是没有意义的。考点2算法设计基本方法（1）列举法基本思想根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。常用于解决“是否存在”或“有多少种可能”等类型的问题。主要特点算法比
4、较简单，但列举情况较多时，算法工作量很大。注意事项例举算法时，通过对实际问题进行详细分析，将与问题有关的知识条理化、完备化、系统化，并从中找出规律，或对所有可能的情况进行分类，从而引出一些有用的信息，减少列举量。（2）归纳法基本思想通过列举少量的特殊情况，经过分析，最后找出一般的关系。主要特点a比列举法更能反映问题的本质，可解决列举量为无限的问题；b可操作性低，不易归纳出一个具体数学模型；c归纳得出的结论只是一种猜测，须对这种猜测加以必要的证明。（3）递推基本思想 从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。主要特点a初始条件或问题本身已给定，或通过对问题的分析化简得到；b递推
5、本质上属于归纳法，递推关系式往往是归纳的结果；c数值型递推算法计算过程中必须注意数值计算的稳定性问题。（4）递归基本思想将复杂问题逐层分解，归结为一些简单的问题，将简单问题解决掉，再沿着原来分解的逆过程逐步进行综合。主要特点a递归的基础是归纳，对问题逐层分解的过程实际上并没有对问题进行求解；b在可计算性理论和算法设计中占有重要地位；c递归算法比递推算法清晰易读，结构简练；d设计递归算法比递推算法容易，但是其执行效率较低。分类a直接递归。一个算法P显式地调用自己。b间接递归。算法P调用另一个算法Q，而算法Q又调用算法P。递归与递推的区别递归与递推的区别主要在于二者实现方法的不同，表现为：a递归是
6、从算法本身到达递归的边界的；b递推是从初始条件出发，逐次推出所需求的结果。（5）减半递推技术减半递推技术是工程上常用的分治法，其中，“减半”指将问题的规模减半，而问题的性质不变；“递推”指重复“减半”的过程。（6）回溯法回溯法是指通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，若试探成功，则问题得到解决，若试探失败，则逐步回退换别的路线再进行试探。【真题演练】1下列叙述中正确的是（ ）。2013年9月真题A所谓算法就是计算方法B程序可以作为算法的一种描述方法C算法设计只需考虑得到计算结果D算法设计可以忽略算法的运算时间【答案】B【解析】程序可以作为算法的一种描述方法,算法在
7、实现时需要用具体的程序设计语言描述。A项错误，算法并不等同于计算方法，是指对解题方案的准确而完整的描述；C项错误，算法设计需要考虑可行性、确定性、有穷性与足够的情报；D项错误，算法设计有穷性要求操作步骤有限且必须在有限时间内完成，耗费太长时间得到的正确结果是没有意义的。2下列关于算法的描述中错误的是（ ）。2014年3月真题A算法强调动态的执行过程，不同于静态的计算公式B算法必须能在有限个步骤之后终止C算法设计必须考虑算法的复杂度D算法的优劣取决于运行算法程序的环境【答案】D【解析】算法是指对解题方案的准确而完整的描述。A项正确，算法强调实现，不同于数学上的计算方法；B项正确，算法的有穷性是指
8、，算法中的操作步骤为有限个，且每个步骤都能在有限时间内完成；C项正确，算法设计必须考虑执行算法所需要的资源，即时间复杂度与空间复杂度；D项错误，算法的优劣取决于算法复杂度，只有当算法被编程实现运行时才会受到运行环境影响。考点3算法复杂度（1）时间复杂度定义算法的时间复杂度是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量f（n）其中，n是问题的规模。算法工作量的分析方法在同一问题规模下，若算法的基本运算次数取决于某一特定输入，可用以下两种方法来分析算法的工作量：a平均性态平均性态分析是指用各种特定输入下的基本
9、运算次数的加权平均值来度量算法的工作量。算法的平均性态定义为：其中，x是所有可能输入中的某个特定输入，p（x）是x出现的概率，即输入为x的概率，t（x）是算法在输入为x时所执行的基本运算次数，Dn表示当规模为n时，算法执行时所有可能输入的集合。b最坏情况复杂性最坏情况分析是指规模为n时，算法所执行的基本运算的最大次数。其定义为：（2）空间复杂度定义算法的空间复杂度一般是指执行这个算法所需要的内存空间。存储空间组成一个算法的存储空间包括以下几种：a算法程序占用的空间；b输入的初始数据占用的存储空间；c算法执行过程中所需要的额外空间。额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的
10、附加存储空间，若额外空间相对于问题规模来说是常数，则称该算法是原地工作的。【真题演练】1下列叙述中正确的是（ ）。2015年3月真题A算法的效率只与问题的规模有关，而与数据的存储结构无关B算法的时间复杂度是指执行算法所需要的计算工作量C数据的逻辑结构与存储结构是一一对应的D算法的时间复杂度与空间复杂度一定相关【答案】B【解析】算法的时间复杂度是指算法在计算机内执行时所需时间的度量；与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。2算法的空间复杂度是指（ ）。2013年9月真题A算法在执行过程中所需要的计算机存储空间B算法所处理的数据量C算法程序中的语句或指令条数D算法在
11、执行过程中所需要的临时工作单元数【答案】A【解析】空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。3算法空间复杂度的度量方法是（ ）。2014年9月真题A算法程序的长度B算法所处理的数据量C执行算法所需要的工作单元D执行算法所需要的存储空间【答案】D【解析】算法的空间复杂度包括：输入数据所占的存储空间；程序本身所占的存储空间；算法执行过程中所需要的额外空间，是指执行这个算法所需要的内存空间，数据结构的基本概念考点1概述（1）数据处理概述定义数据处理是指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，也包括对数据元素进行分析。关键问题大量数据元素在计算机中
12、如何组织，以便提高数据处理的效率，从而节省计算机的存储空间，这是进行数据结构处理的关键问题。（2）数据结构研究概述研究问题a数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；b在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；c对各种数据结构进行的运算。研究目的数据结构研究和讨论上述3个问题的主要目的在于提高数据处理效率，包括：a提高数据处理的速度；b尽量节省在数据处理过程中所占用的计算机存储空间。考点2数据结构的概念（1）数据结构的定义数据结构是指相互有关联的数据元素的集合，即它是反映数据元素之间关系的数据元素集合的表示。简言之，数据结构是指带有结构的数据元素的
13、集合，这里的“结构”指数据元素之间的前后件关系。一个数据结构应包含以下两方面内容：表述数据元素的信息；表示各数据元素之间的前后件关系。（2）数据的逻辑结构定义数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。要素a数据元素的集合，通常记为D；bD上的关系，通常记为R，它反映了D中各数据元素之间的前后件关系。表示一个数据结构B可表示为：B（D，R）为反映D中各数据元素之间的前后件关系，一般用二元组来表示。（3）数据的存储结构定义数据的存储结构，也称数据的物理结构，是指数据逻辑结构在计算机存储空间中的存放形式。在数据的存储结构中，不仅要存放各数据元素的信息，而且要存放各数据元素之间的前后件信息。常用的存储结构a顺序；b链接；c索引。采用不同的存储结构，数据处理的效率是不同的。【真题演练】下列叙述中正确的是（ ）。2014年3月真题A有且只有一个根结点的数据结构一定是线性结构B每一个结点最多有一个前件也最多有一个后件的数据结构一定是线性结构C有且只有一个根结点的数据结构一定是非线性结构D有且只有一个根结点的数据结构可能是线性结构，也可能是非线性结构【答案】D【解析】逻辑结构分为线性结构和非线性结构，线性结构的特征有：集合中必存在唯一的一个“第一个元素”；集合中必存在唯一的一个“最后的元素”；除第一元素之外，其它数据元素均有唯一的
