全国计算机二级基础

全国计算机二级考试基础部分:考点1算法的定义和数据结构算法是对一个问题求解步骤的一种描述，是求解问题的方法， 它是指令的有限序列， 其中每条指令表示一个或者多个操作。一般来说，一个算法具有以下5个主要的特征。（1）有穷性：一个算法（对任何合法的输入）在执行有穷步后能够结束，并且在有限的 时间内完成。（2）确定性：算法中的每一步都有确切的含义。（3）可行性：算法中的操作能够用已经实现的基本运算执行有限次来实现。（4）输入：一个算法有零个或者多个输入，零个输入就是算法本身缺定了初始条件。（5）输出：一个算法有一个或者多个输出，以反映出数据加工的结果。算法的复杂度：主要包括算法的时间复杂度和算法的空间复杂度。所谓算法的时间复杂 度是指执行算法所需要的计算工作量；算法的空间复杂度一般是指执行这个算法所需要的内存空间。例 问题处理方案的正确而完整的描述称为 。2005年4月 填空第5题答案：算法例一个算法应该具有 确定性”等5个特性，下面对另外 4个特性的描述中错误的是（）。A .有零个或多个输入B .有零个或多个输出C.有穷性D .可行性答案：B例 算法具有5个特性，以下选项中不属于算法特性的是（）。A .有穷性 B.简洁性 C .可行性 D .确定性答案：B例 以下叙述中错误的是（）。2005年9月 选择第11题A 用户所定义的标识符允许使用关键字B 用户所定义的标识符应尽量做到见名知意”C.用户所定义的标识符必须以字母或下划线开头D .用户定义的标识符中，大、小写字母代表不同标识答案：A例 算法的空间复杂度是指A）算法程序的长度B）算法程序中的指令条数C）算法程序所占的存储空间D）执行过程中所需要的存储空间例 算法的时间复杂度是指A）执行算法程序所需要的时间B）算法程序的长度C）算法执行过程中所需要的基本运算次数D）算法程序中的指令条数程序设计语言是用于书写计算机程序的语言，其基本成分有以下 4种，数据成分：用来描述程序中的数据。 运算成分：描述程序中所需的运算。 控制成分：用来构造程序的逻辑控 制结构。传输成分：定义数据传输成分，如输入输出语言。例：程序设计语言的基本成分是数据成分、运算成分、控制成分和A）对象成分B）变量成分C）语句成分D）传输成分对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较logzn次，而顺序查找需要比较n次。数据结构概念一般包括 3个方面的内容，数据的逻辑结构、存储结构及数据上的运算集合。数据的逻辑结构只抽象的反映数据元素之间的逻辑关系，而不管它在计算机中的存储表示形式。结构化程序设计方法的主要原则可以概括为自顶向下、逐步求精、模块化及限制使用 goto语句，总的来说可使程序结构良好、易读、易理解、易维护。数据的逻辑结构有线性结构和非线性结构两大类。常用的存储表示方法有 4种，顺序存储、链式存储、索引存储、散列存储。其中，顺序 存储方法是把逻辑上相邻的结点存储在物理位置也相邻的存储单元中。链表采用的是链式存储结构，它克服了顺序存储结构的缺点：它的结点空间可以动态申请和释放；它的数据元素的逻辑次序靠结点的指针来指示，不需要移动数据元素。但是链式存储结构也有不足之处： 每个结点中的指针域需额外占用存储空间； 链式存储结构是一种非随机存储结构。例如：链表不具有的特点是A）不必事先估计存储空间B）可随机访问任一元素C）插入删除不需要移动元素D）所需空间与线性表长度成正比面向对象的程序设计方法中，最基本的概念是对象和类，类具有以下特点：封装性、继承性、多态性；对象有如下一些基本特点，即标识惟一性、分类性、多态性、封装性和模块 独立性。类的继承性优点：相似的对象可以共享程序代码和数据结构，从而大大减少了程序中的冗余，提高软件的 可重用性。例如：在面向对象方法中，类之间共享属性和操作的机制称为 继承性栈和队列都是一种特殊的操作受限的线性表，只允许在端点处进行插入和删除。二者的区别是：栈只允许在表的一端进行插入或删除操作，是一种”后进先出”的线性表；而队列只允许在表的一端进行插入操作，在另一端进行删除操作，是一种”先进先出”的线性表。例：栈和队列的共同特点是A）都是先进先出B）都是先进后出C）只允许在端点处插入和删除元素D）没有共同点例：已知二叉树后序遍历序列是 dabec,中序遍历序列是debac,它的前序遍历序列是A）acbedB）decabC）deabcD）cedba解析：依据后序遍历序列可确定根结点为c;再依据中序遍历序列可知其左子树由deba构成，右子树为空；又由左子树的后序遍历序列可知其根结点为e,由中序遍历序列可知其左子树为d，右子树由ba构成，如下图所示。求得该二叉树的前序遍历序列为选项D)。例如：已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为A) GEDHFBCAB) DGEBHFCAC) ABCDEFGHD) ACBFEDHG例：如果进栈序列为e1,e2,e3,e4,则可能的出栈序列是A) e3,e1,e4,e2B) e2,e4,e3,e1C) e3,e4,e1,e2D) 任意顺序考点2:软件与软件工程概述1.软件的定义软件是程序、数据与相关文档的集合，相对于计算机硬件而言，软件是逻辑产品而不是物理产品，是计算机的无形部分。软件包括系统软件和应用软件。与硬件相比，软件的特点包括：(1) 软件是一种逻辑实体；(2) 软件的生产与硬件不同，它没有明显的制作过程；(3) 软件在运行、使用期间不存在磨损、老化问题；(4) 软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制，这导致了软件 存在移植的问题；(5) 软件复杂性高，成本昂贵；(6) 软件开发涉及诸多的社会因素。例：下列描述中正确的是()。2005年4月 选择第8题A 程序就是软件B 软件开发不受计算机系统的限制C.软件既是逻辑实体，又是物理实体D 是程序、数据与相关文档的集合答案：D2 .软件工程的定义软件工程是采用工程化的方法开发和维护软件的工程学科。把经过时间考验而证明正 确的管理技术和当前能够得到的最好的技术和方法结合起来，以便经济地开发出高质量的软件并有效地维护它。软件工程包括3个要素，分别是方法、工具和过程。软件工程的基本思想是在软件开发过程中需要应用工程化原则进行软件开发，并将这个思想贯穿到软件开发的整个过程中。软件工程的目标是在给定成本、进度的前提下，利用工程化原则，开发出具有可修改性、 有效性、可靠性、可理解性、可维护性、可重用性、可适用性、可移植性、可追踪性和可互 操作性并满足用户需求的软件产品。软件工程研究的内容主要包括：软件开发 技术和软件工程管理。软件生命周期分为软件 定义、软件开发及软件运行维护3个阶段。详细设计、软件编码 和软件测试都属于软件开发阶段；维护是软件生命周期的最后一个阶段，也是持续时间最长，花费代价最大的一个阶段，软件工程学的一个目的就是提高软件的可维护性，降低维护的代价。例：开发软件所需高成本和产品的低质量之间有着尖锐的矛盾，这种现象称作A）软件投机B）软件危机C）软件工程D）软件产生例：将软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期例：软件生命周期中所花费用最多的阶段是A详细设计B）软件编码C）软件测试D）软件维护例：下列不属于软件工程的 3个要素的是A）工具B ）过程C ）方法D）环境 例：下列描述中正确的是（）。2005年9月 选择第5题A 软件工程只是解决软件项目的管理问题B .软件工程主要解决软件产品的生产率问题C 软件工程的主要思想是强调在软件开发过程中需要应用工程化原则D 软件工程只是解决软件开发中的技术问题答案：C例：开发软件时对提高开发人员工作效率至关重要的是A）操作系统的资源管理功能B）先进的软件开发工具和环境C）程序人员的数量D）计算机的并行处理能力软件设计包括软件结构设计、数据设计、接口设计和过程设计。其中结构设计是定义软 件系统各主要部件之间的关系；数据设计是将分析时创建的模型转化为数据结构的定义；接口设计是描述软件内部、软件和操作系统之间及软件与人之间如何通信；过程设计则是把系统结构部件转换成软件的过程性描述。例 软件设计包括软件的结构、数据接口和过程设计，其中软件的过程设计是指A模块间的关系B）系统结构部件转换成软件的过程描述C）软件层次结构D）软件开发过程软件测试：确认测试的任务是验证软件的功能和性能，以及其他特性是否满足需求规格说明中确定的各种需求；集成测试的主要目的是发现与接口有关的错误。测试的目的是发现软件中的错误 。经验表明，程序中存在错误的概率与该程序中已发现 的错误数成正比。这一现象说明，为了提高测试效率，测试人员应该集中对付那些错误群集 的程序。例：为了提高测试的效率，应该A随机选取测试数据B）取一切可能的输入数据作为测试数据C）在完成编码以后制定软件的测试计划D）集中对付那些错误群集的程序例；检查软件产品是否符合需求定义的过程称为A）确认测试B ）集成测试C ）验证测试D）验收测试 例；下面不属于软件设计原则的是A）抽象B ）模块化C ）自底向上D）信息隐蔽解析： 软件设计遵循软件工程的基本目标和原则，建立了适用于在软件设计中应该遵 循的基本原理和与软件设计有关的概念，它们是抽象、模块化、信息隐蔽和数据独立性。自底向上是集成测试中增量测试的一种。考点3:数据库数据库（Database, DB）可以看成是长期存储在计算机内的、大量的、有结构的和可共享的数据集合。数据是描述现实世界中各种具体事物和抽象概念的可存储并有明确意义的信 息。数据库管理系统是位于用户与操作系统之间的一层系统管理软件，是一种系统软件，是用户与数据库之间的一个标准接口。其总是基于某种数据模型，可以分为层次模型、网状模型和关系模型。数据库可以被直观地理解为存放数据的仓库，只不过这个仓库是在计算机的大容量存储器上，例如，硬盘就是一种最常见的计算机大容量存储设备。数据必须按一定的格式存放，因 为它不仅需要存放，而且还要便于查找。数据库的特点如下（1）数据按一定的数据模型组织、描述和储存。（2）冗余度较小。数据共享大大减少了数据冗余。（3）数据独立性较高。数据独立性是数据库领域中一个常用的术语，也是数据库技术的重要特点之一。数据独立性是指数据的组织结构和存储方法与应用程序互不依赖、彼此独立。它包括数据的物理独立性和数据的逻辑独立性。物理独立性是指用户的应用程序与存储在磁盘上的数据库中的数据是相互独立的，也就是当数据的物理存储改变了，用户程序也可以不变。逻辑独立性是指用户的应用程序与数据库的逻辑结构是相互独立的，也就是说，数据的逻辑结构改变了，用户程序也可以不变。（4）易扩展。（5）可为各种用户共享。不同的用户可以使用同一个数据库，可以取出他们所需要的子集，而且容许子集任意重叠。数据库设计分为以下 6个设计阶段：需求分析阶段、概念模型设计阶段、逻辑设计阶段、 物理设计阶段、实施阶段、运行和维护阶段。例数据独立性是数据库技术的重要特点之一。所谓数据独立性，是指（）。2005年4月选择第9题A 数据与程序独立存放B不同的数据被存放在不同的文件中C. 不同的数据只能被对应的应用程序所使用D. 以上三种说法都不对答案：D例 数据库设计的根本目标是要解决（）。2005年9月 选择第8题A 数据共享问题B .数据安全问题C.大量数据存储问题D 简化数据维护答案：A例 下列叙述中正确的是（）。2004年9月 选择第9题A .数据库系统是一个独立的系统，不需要操作系统的支持B 数据库设计是指设计数据库管理系统C.数据库技术的根本目标是要解决数据共享的问题D 数据库系统中，数据的物理结构必须与逻辑结构一致答案：C例在数据库设计中，将 E-R图转换成关系数据模型的过程属于A）需求分析阶段B）逻辑设计阶段C）概念设计阶段D）物理设计阶段例在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。其中数据独立性最高的阶段是A）数据库系统B ）文件系统C ）人工管理D）数据项管理