最新2015计算机二级公共基础题库与解答

12015计算机二级公共基础题库与答案2015年6月第一章数据结构与算法1.1算法的概念：是指解题方案的准确而完整的描述。算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。算法的基本特征：（1）可行性：算法必须可以得到满意的结果；（2）确定性：算法中每一步都有明确定义，不允许有多义性（3）有穷性：算法必须能在有限的时间内或在执行有限个步骤后终止；（4）拥有足够的情报。算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。算法的控制结构：顺序结构、选择结构、循环结构。算法复杂度：算法时间复杂度和算法空间复杂度。算法时间复杂度是指执行算法所需要的计算工作量。算法空间复杂度是指执行这个算法所需要的内存空间。1.2数据结构的基本基本概念数据结构是指相互有关联的数据元素的集合，主要研究的以下三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构；（2）各数据元素在计算机中的存储关系,即数据的存储结构,也称为物理结构；包括顺序、链接、索引等结构。（3）对各种数据结构进行的运算。线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。1．3线性表及其顺序存储结构线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。线性表的顺序存储结构具有以下两个基本特点：（1）表中元素的所占的存储空间是连续的；（2）表中各数据元素在存储空间中按逻辑顺序依次存放。1．4栈和队列栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。栈按照“先进后出”（FILO）或“后进先出”（LIFO）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。栈的基本运算：（1）入栈；（2）退栈；（3）读栈顶元素，此时指针无变化。队列是指允许在一端（队尾）进行插入，而在另一端（队头）进行删除的线性表。Rear指针指向队尾，front指针指向队头。队列是“先进行出”（FIFO）或“后进后出”（LILO）的线性表。队列运算包括（1）入队运算；（2）退队运算。循环队列元素数量的计算：（1）RearFront,数量为Rear-Front（2）RearFront,数量为N+(Rear-Front)N为容量1．5线性链表数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。结点由两部分组成：（1）数据域，用于存储数据；（2）指针域，用于指向前一个或后一个结点。在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。链式存储方式即可用于表示线性结构，也可用于表示非线性结构。1．6树与二叉树树是一种简单的非线性结构，所有元素之间具有明显的层次特性。树中的重要概念：父结点，根结点（简称树的根）、子结点、叶子结点、结点的度、树的度、树的深度、宽度二叉树的特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。满二叉树是指除最后一层外，每一层上的所有结点有两个子结点。完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。二叉树的基本性质：（1）在二叉树的第k层上，最多有2k-1(k≥1)个结点；（2）深度为m的二叉树最多有2m-1个结点；（3）度为0的结点（即叶子结点）总是比度为2的结点多一个；（4）有n个结点的二叉树，其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分；（5）设完全二叉树共有n个结点。有以下结论：①结点编号为k，则该结点的父结点编号为INT(k/2)；②编号为k的结点的左子结点编号为2k；右子结点编号为2k+1二叉树存储结构采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行顺序存储。二叉树的遍历：（1）前序遍历（DLR）顺序：根结点，左子树，历右子树；（2）中序遍历（LDR）：左子树，根结点，右子树；（3）后序遍历（LRD）：左子树，右子树，根结点。1．7查找技术顺序查找的使用情况：（1）线性表为无序表；（2）表采用链式存储结构。二分法查找只适用于顺序存储的有序表，对于长度为n的有序线性表，最坏情况只需比较log2n次。1．8排序技术排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。交换类排序法：（1）冒泡排序法，最坏需要比较的次数为n(n-1)/2；（2）快速排序法n(n-1)/2。插入类排序法：（1）简单插入排序法，最坏情况需要n(n-1)/2次比较；（2）希尔排序法，最坏情况需要O(n1.5)次比较。2选择类排序法：（1）简单选择排序法,最坏情况需要n(n-1)/2次比较；（2）堆排序法，最坏情况需要O(nlog2n)次比较。顺序存储链式存储60第二章程序设计基础2．1程序设计设计方法和风格如何形成良好的程序设计风格：1、源程序文档化；2、数据说明的方法；3、语句的结构；4、输入和输出。注释分序言性注释和功能性注释，语句结构清晰第一、效率第二。2．2结构化程序设计结构化程序设计方法的四条原则是：1.自顶向下；2.逐步求精；3.模块化；4.限制使用goto语句。结构化程序的基本结构和特点：（1）顺序结构；（2）选择结构：又称分支结构；（3）重复结构：又称循环结构。2．3面向对象的程序设计面向对象方法的优点：1）与人类习惯的思维一致；2）稳定性好；3）重用性好；4）易于开发大型软件；5）可维护性好。对象是面向对象方法中最基本的概念，表示客观世界中的任何实体，对象是实体的抽象，由一组静态特征的属性和它可执行的一组操作组成；属性即对象所包含的信息，操作描述了对象执行的功能，操作也称为方法或服务。对象的基本特点：（1）标识惟一性；（2）分类性；（3）多态性；（4）封装性；（5）模块独立性好。类是指具有共同属性、共同方法的对象的集合。所以类是对象的抽象，对象是对应类的一个实例。消息是一个实例与另一个实例之间传递的信息。继承是指能够直接获得已有的性质和特征，而不必重复定义他们。多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。第三章软件工程基础3．1软件工程基本概念计算机软件是包括程序、数据及相关文档的完整集合。特点包括：（1）软件是一种逻辑实体；（2）软件的生产与硬件不同，没有明显的制作过程；（3）软件复杂性高，成本昂贵；（4）软件在运行、使用期间不存在磨损、老化问题；（5）软件对计算机系统具有依赖性；软件按功能分为应用软件、系统软件、支撑软件（或工具软件）。软件危机主要表现在成本、质量、生产率等问题。软件工程是应用于软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序，包括3个要素：方法、工具和过程。软件周期：软件产品从提出、实现、使用维护到停止使用退役的过程。1070A20H……C30C50E40B50E80H6070A3080B20A30C50E80B20H……70F1070305080203软件生命周期三个阶段:软件定义、软件开发、运行维护，主要活动阶段是：（1）可行性研究与计划制定；（2）需求分析；（3）软件设计；（4）软件实现；（5）软件测试；（6）运行和维护。3．2结构化分析方法结构化分析方法：着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具,建立系统的逻辑模型。常用工具是（1）数据流图DFD；（2）数据字典DD；（3）判定树；（4）判定表。数据流图：描述数据处理过程的工具，是需求理解的逻辑模型的图形表示，它直接支持系统功能建模。数据字典：对数据元素的一个有组织的列表并做精确、严格的定义，使得所有使用人员对结果有共同理解，作用是对DFD中图形元素做确切解释。数据字典是结构化分析的核心。软件需求规格说明书的特点：（1）无岐义性；（2）正确性；（3）完整性；（4）可验证性；（5）一致性；（6）可理解性；软件需求规格说明书可以作为软件开发工作的基础和依据，也是确认测试和验收测试的依据。3．3结构化设计方法软件设计是确定系统的物理模型。软件设计是将需求准确地转化为完整的软件产品或系统的唯一途径。从技术观点来看，软件设计包括：结构设计：定义软件系统各主要部件之间的关系。接口设计：描述软件内部和系统、软件与人之间如何通信。数据设计：将分析时创建的模型转化为数据结构的定义。过程设计：把系统结构部件转换成软件的过程描述。从工程管理角度来看：概要设计和详细设计。概要设计的基本任务是：（1）设计软件系统结构；（2）数据结构及数据库设计；（3）编写概要设计文档；（4）概要设计文档评审。详细设计：为每一个模块确定算法和局部数据结构，用某种选定的表达工具表示算法和数据结构的细节。衡量软件模块独立性使用耦合性和内聚性两个定性的度量标准。优秀软件应高内聚，低耦合。内聚性：一个模块内部元素彼此结合的紧密程度。耦合性：模块间联系的紧密程度。模块用一个矩形表示，箭头表示模块间的调用关系，带注释的箭头表示模块调用过程中来回传递的信息。用带实心圆的箭头表示传递的是控制信息空心圆箭心表示传递的是数据。典型的数据流类型有两种：变换型和事务型。变换型系统结构图由输入、中心变换、输出三部分组成。常见的过程设计工具有：图形工具（程序流程图）、表格工具（判定表）、语言工具（PDL）。3．4软件测试其目的在于检验它是否满足规定的需求或是弄清预期结果与实际结果之间的差别。软件测试的目的：发现错误而执行程序的过程。软件测试方法：静态测试和动态测试。静态测试包括代码检查、静态结构分析、代码质量度量。不实际运行软件，主要通过人工进行。动态测试：是基本计算机的测试，主要包括白盒测试方法和黑盒测试方法。白盒测试：在程序内部进行，主要用于完成软件内部操作的验证。方法有逻辑覆盖、基本基路径测试。又称为结构测试或逻辑驱动测试黑盒测试：主要诊断功能不对或遗漏、界面错误、数据结构或外部数据库访问错误、性能错误、初始化和终止条件错，用于软件确认。主要方法有等价类划分法、边界值分析法、错误推测法、因果图等。又称功能测试或数据驱动测试软件测试过程一般按4个步骤进行：单元测试、集成测试、验收测试（确认测试）和系统测试。3．5程序的调试调试的任务是诊断和改正程序中的错误，主要在开发阶段进行，方法有：1）强行排错法；2）回溯法；3）原因排除法。程序调试的基本步骤：（1）错误定位；（2）修改设计和代码，以排除错误；（3）进行回归测试，防止引进新的错误。第四章数据库设计基础4．1数据库系统的基本概念数据库存放数据是按数据所提供的数据模式存放的，具有集成与共享的特点。数据库管理系统：一种系统软件，负责数据库中的数据的组织、操纵、维护、保护和数据服务等，是数据库的核心。数据库管理系统提供以下的数据语言：（1）数据定义语言：负责数据的模式定义与数据的物理存取构建；（2）数据操纵语言：负责数据的操纵，如查询与增、删、改等；（3）数据控制语言：负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等。4数据库管理员：对数据库进行规划、设计、维护、监视等的专业管理人员。数据库系统：由数据库、数据库管理系统（软件）、数据库管理员、硬件平台、软件平台五部分构成的运行实体。数据库应用系统：由数据库系统、应用软件及应用界面三者组成。数据库系统的三级模式：（1）概念模式：数据库系统中全局数据逻辑结构的描述，全体用户公共数据视图；（2）外模式：也称子模式与用户模式。是用户的数据视图，也就是用户所见到的数据模式；（3）内模式：又称物理模式，它给出了数据库物理存储结构与物理存取方法。数据库系统的两级映射：（1）概念模式到内模式的映射；（2）外模式到概念模式的映射。4.2数据模型数据模型的概念：是数据特征的抽象，从抽象层次上描述了系统的静态特征、动态行为和约束条件，为数据库系统的信息表与操作提供一个抽象的框架。描述了数据结构、数据操作