全国计算机二级vb公共基础知识.ppt

，第二次公共基础知识咨询，演示者：符文，知识点分布，第一章数据结构和算法第二章编程基础第三章软件工程基础第四章数据库设计基础，第一章数据结构和算法，第一，算法对问题解决方案进行了准确完整的说明。换句话说，算法是对特定故障诊断步骤的一种描述。*算法不等于程序，不等于计算方法。2、算法的基本特征、1.1算法、可行性、确定性、贫困、具有足够的信息、08年4月选择题5问题算法的贫乏是AA)算法程序运行时间有限的b)算法程序处理的数据量有限的c)算法程序长度有限的d)算法只能用于有限的用户，3、算法复杂性主要是时间复杂性和(1)算法时间复杂度是运行算法所需的计算工作量，可以通过运行算法时所需的基本运算的执行次数来测量。(2)算法空间复杂性表示运行此算法所需的内存空间。06年9月选择题7下讨论的是DA)一个算法具有较大的空间复杂性，时间复杂性也必须很大b)一个算法具有较大的空间复杂性，时间复杂性必须很小c)一个算法具有较大的时间复杂性，空间复杂性必须很小d)三个都错了。1.1算法，1，数据结构是彼此相关的数据元素的集合。2、数据结构主要研究和讨论(1)数据的逻辑结构，即数据集中数据元素之间固有的逻辑关系。(2)处理数据时，每个数据元素存储在计算机上的关系，即数据的存储结构。数据的存储结构包括顺序、链接、索引等。*:数据的逻辑结构反映了数据元素之间的逻辑关系，数据的存储结构(也称为数据的物理结构)是数据的逻辑结构在计算机存储空间中的存档形式。相同逻辑结构中的数据可以采用不同的存储结构，但会影响数据处理效率。1.2数据结构的基本概念是将逻辑相邻节点存储在与物理位置相邻的存储设备中，节点之间的逻辑关系由存储设备的相邻关系实现。结果存储表示法称为顺序存储结构。逻辑相邻节点不必在物理位置相邻，节点之间的逻辑关系显示为附加指针字段。生成的存储表示称为链存储结构。除了设置存储节点信息外，还创建其他索引表以标识节点的地址。如07年4月选择题1问题下所述，准确地说，BA)算法的效率与数据的存储结构无关，b)算法的时间复杂度与运行算法所需的计算工作量c)数据的逻辑结构与存储结构一一对应d)算法的时间复杂性和空间复杂性分为3，数据结构分为线性结构和非线性结构两种主要类型。(1)有线性结构(非空数据结构)条件：1)，只有一个根节点；2)每个节点最多有一个前端和一个后端项目。*:典型的线性结构包括线性表格、堆叠、伫列和线性连结表格。(2)非线性结构：不符合线性结构条件的数据结构。*:典型的非线性结构是树、二叉树和图形。1.2数据结构的基本概念，07年9月选择题6下讨论的是DA)数据的逻辑结构和存储结构是一对一的b)计算机存储空间是基于矢量的存储结构，因此数据的存储结构通常是线性结构c)编程语言的数组是顺序存储结构，因此只能使用数组处理线性结构d。1.2数据结构的基本概念，1，堆栈和基本运算堆栈仅限于一端插入和删除的线表。除非堆栈允许插入和删除，否则端点称为堆栈顶部，而不允许插入和删除的其他端点称为堆栈底部。堆栈顶部元素始终是最后插入的元素，堆栈底部元素始终是第一个插入的元素。堆栈按“先进先出”或“后进先出”原则组织数据。堆栈具有内存效果。06年9月，空问题4“先进先出”原则组织数据的数据结构是堆栈。1.3堆栈和队列、2、队列及其默认运算队列是线性表，其中一端(队列末端)允许插入，另一端(队列头)允许删除。尾部指针(Rear)指向团队尾部元素，头部指针(front)指向行头元素的先前位置(团队头)。队列是先进先出或后进先出的线性表。06年9月，填空5号问题数据结构分为线性结构和非线性结构，带链的队列属于线性结构。07年4月，在选择题5下，队列的描述正确DA)队列是非线性的表b)队列按照“先进先出”原则组织数据c)队列在末尾删除数据d)队列按照“先进先出”原则组织数据，1.3堆栈和队列，循环队列及其计算：将队列存储空间的最后一个位置绕过第一个位置*:循环队列中的元素数=rear-front。08年4月，填空3题循环对的列容量50，头指针front=5(指向相对元素的以前位置)，尾指针rear=29(指向团队结束元素)，循环队列有24个元素。07年9月，空标题3号信息行的存储结构主要分为顺序存储结构和链存储结构。队列是特殊的线性表，是队列的顺序存储结构。1.3堆栈和队列，1，树的基本概念树是简单的非线性结构。只有一个节点没有前面部分，树的根节点，简称为树的根节点。没有后缀的节点称为叶节点。树结构中一个节点拥有的项目数称为该节点的度，所有节点中最大的程度称为树的度。树的最大级别称为树的深度。06年9月，空标题1下的软件系统结构图为宽度3。1.4树和二进制树、2、二进制树及其基本特征(1)二进制树是非常有用的非线性结构，具有以下两个特征：1)非空的二进制树只有一个根节点。2)每个节点最多有两个子树，分别称为该节点的左侧和右侧子树。*:根据二进制树的概念，二进制树的度可以是0(叶节点)、1(仅一个子树)或2(具有两个子树)。(2)二叉树的基本特征1在二叉树的k层中具有最大节点。特性2深度为m的二进制树包含最大节点。特性3在任意二叉树中，角度为零的节点(即叶节点)总是比度为2的节点多一个。属性4具有具有最小深度的n个节点的二进制树。其中表示导入的整数部分。1.4树和二进制树，07年4月选择题7 .二进制树中的n也有2个节点，则该二进制树的叶节点数为aa) n-1c) n/207 9月选择问题8 .二进制树中有70个叶节点和80度1个节点，则该二进制树的摘要点为aa) 219b) 221c) 229c最后一层仅缺少右侧的部分节点。2008年4月，空蔡第2问题深度5的完整二进制树包含16个叶节点。*:可以根据完整二进制树的定义获得。度为1的节点数为0或1。1.4树和二叉树，4，二叉树的遍历二叉树遍历意味着不重复访问二叉树中的所有节点。二进制树遍历可以分为三种类型：1.4树和二进制树，(1) DLR (presequence transverse)。如果二叉树为空，结束返回结束。否则，首先访问根节点，然后通过左侧子树，最后通过右侧子树。在左侧和右侧子树中导航时，访问根节点，通过左侧子树，通过右侧子树。(2)中间顺序遍历(LDR):如果二进制树为空，则结束返回。否则，请依次导航到左侧的子树、根节点和右侧的子树。在左侧和右侧子树中导航时，浏览左侧子树以访问根节点，然后遍历右侧子树。(3) LRD:如果二进制树为空，则退出返回。否则，首先访问左侧子树、右侧子树、根节点，然后在左侧和右侧子树中导航，同时依次导航到左侧子树、右侧子树和根节点。2007年4月对选择题6的下一个二进制树的预遍历结果是：ca)dybeafczxb)ydebfzxcac)abdyecfxzd)abcdefxyz，1.4树和二进制树，1.5查找技术查找：根据指定的值标识查找表中关键字等于指定值的数据元素2006年9月，选择题8号在长度为64的有序选择表中依次查找，最坏的情况下需要比较的次数是b。(A)63B)64C)6D)71.6排序技术排序是将未排序序列调整为值未按降序排序的顺序，即，将未排序记录序列调整为已排序记录序列的操作。1、交换类排序方法(方法：气泡排序，快速排序)。2、插入类排序方法(方法：简单插入排序，定位台阶排序)。3、选择类排序方法(方法：简单选择排序、堆排序)。摘要：比较各种排序方法：2008年4月选择题6号，排序长度为n的宣叙调，最坏情况下比较次数为n(n-1)/2的排序方法为DA)快速排序b)冒泡排序c)直接插入排序d)堆栈排序本章测试点：返回，第二章编程基础，编程风格主要强调“明确第一，效率第二”。以下因素(1)应重点考虑源代码文档：符号名称的名称。符号名称能反映它所代表的实际物品，并具有一定的实际意义。关于程序的注释。分为序言注释和功能注释。前言注意事项：位于程序开头，包括程序标题、程序功能说明、主要算法、界面说明、程序位置、开发简历、程序员、审阅者、审阅日期和修改日期。功能注释：嵌入在源代码中，用于说明以下语句或程序的主要功能：视觉组织。使用空格、空行、缩进等技术明确程序层次结构。(2)输入和输出。输入数据检查数据的合法性；当作为交互式输入/输出输入时，必须在屏幕上使用提示明确输入请求，同时在数据输入期间和输入结束时在屏幕上提供状态信息。2.1编程风格，06年9月选择题1问题以下选项中不符合良好编程风格的是D. A .源代码文件b)标准化数据说明顺序c)防止goto语句滥用d)模块设计高耦合，gonelson 07年9月选择题4问题以下选项中不符合良好编程风格的是AA)程序的效率第一，明确由上而下，逐步细化，模块化，限制使用goto语句。(1)从上到下。编程时，首先要考虑整体，然后考虑细节。首先考虑全局目标，然后考虑本地目标。不要一开始就过分追求很多细节，先从最高综合目标开始设计，逐步完善问题。(2)逐步精炼。(。对于复杂的问题，必须设计一些子目标，进行转换，逐步细化。(3)模块化。一个复杂的问题，确实由几个简单的问题组成。模块化是将程序要解决的总目标分解为子目标，然后将每个小目标进一步分解为称为一个模块的具体小目标。*模块设计需要高凝聚力、低耦合。(4)限制使用goto语句。2008年4月选择题2问题结构化编程基本原则AA)多态b)自上而下c)模块化d)逐步细化2)结构化程序的基本结构：顺序结构、选择结构、重复结构。2.2结构化编程(面向过程的编程方法)，面向对象方法的主要优点：(1)与人类习惯的思维方法相匹配；(2)稳定性好。(3)可重用性好。(4)大型软件产品的轻松开发；维护性好。*:面向对象的编程主要考虑提高软件的可重用性。对象是属性和方法的包。*:对象由三部分组成：对象名称、属性和操作。面向对象的基本特征：继承、多态、封装。(1)继承。这意味着您可以直接获取现有特性和要素，而无需重复定义它们。*:类的继承是在类之间共享属性和操作的机制，可以提高软件的可重用性。(2)多态性。指示同一操作可以是其他对象的行为。(3)套装性。在外部，只能查看对象的外部特性。也就是说，您只需要知道数据的值范围以及适用于该数据的操作。不需要知道数据的具体结构和实现操作的算法。个体的内部，即处理能力的实现和内部状态，是不对外可见的。不能在外部直接使用对象的处理能力，也不能直接修改对象的内部状态，只能将对象的内部状态更改为其本身。*:信息隐藏是通过封装对象实现的。2.3面向对象编程，软件重用是指在不同软件开发过程中重复使用相同或相似软件的过程。07年4月可选问题4在下面的选项中，属于面向对象编程功能的CA)继承b)多态c)多态d)包7年9月可选问题3在面向对象方法中，信息隐藏是CA)对象的多态c)对象的包d)对象的分类类是具有公共属性、公共方法的对象的集合。因此，类是对象的抽象，对象是该类的实例。消息是在一个实例和另一个实例之间传递的信息。*:在面向对象的方法中，一个对象向另一个对象请求服务的方法是通过发送消息。本章的试题：本章考试出了大约一个问题，出了大约二分之一的分数，出题量少的章节。这一章内容比较少，简单，掌握基本概念，考试就容易应付，所以在这一部分失去分数更可惜。2.2结构化编程(面向流程的编程方法)、返回、第三章软件工程基础、1、软件相关概念计算机软件是包含程序、数据和相关文档的完整集合。07年9月选择题1问题软件是DA)计划b)计划和文档c)算法数据结构d)计划、数据和相关文档的完整集合2、软件危机和软件工程软件工程源于软件危机。软件危机是指计算机软件开发和维护过程中出现的一系列严重问题。软件工程的主要思想是将工程原则应用于软件开发过程。这包括三个因素：方法、工具和进程。方法是完成软件工程项目的技术手段。工具是支持软件开发、管理和文档生成。过程支持软件开发各个方面的控制和管理。3.1软件工程基本概念，3，软件生命周期软件生命周期：软件产品从建议、实施、使用维护到淘汰流程使用。软件生命周期分为三个阶段：软件定义、软件开发和软件操作维护1)软件定义阶段：计划和需求分析。计划制定：总体目标确定可行性研究；制定解决方案导航开发计划。需求分析：分析开发软件提出的需求，并提供详细的定义。2)软件开发阶段：软件设计：摘要设计和详细设计两个部分。软件实现：将软件设计转换为计算机可接受的程序代码。软件测试：根据设计测试案例验证软件的各种组件。3)软件执行维护阶段：软件启动并在使用过程中持续维护，所需的扩展和删除。*:软件生命周期中成本最高的阶段是软件执行维护阶段。3.1软件工程基本概念，200