计算机二级考试公共基础知识要点.doc

《计算机二级考试公共基础知识要点.doc》由会员分享，可在线阅读，更多相关《计算机二级考试公共基础知识要点.doc（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机二级考试公共基础知识要点.txt老子忽悠孩子叫教育，孩子忽悠老子叫欺骗，互相忽悠叫代沟。男人这花花世界，我要用什么颜色来吸引你。 本文由伊然880贡献 doc文档可能在WAP端浏览体验不佳。建议您优先选择TXT，或下载源文件到本机查看。 第一章 数据结构与算法 一、学习目标与要求 1了解算法的基本概念和一些常用的算法，学会计算算法的时间复杂度； 2掌握数据结构的基本概念，并了解数据的逻辑结构和存储结构，学会利 用图形的方式表示数据结构； 3了解线性表的基本概念，并掌握线性表的顺序存储结构以及顺序存储的 线性表的基本运算； 4了解栈和队列的基本概念，并掌握它们的基本运算； 5了解线性链表的

2、基本概念，并掌握线性链表的基本运算，同时，了解循 环链表的基本概念和基本操作； 6理解树的概念，尤其是二叉树的基本概念和相关性质，掌握二叉树的存 储结构和遍历技术； 7 掌握查找技术， 学会利用顺序查找和二分查找在数列中查找指定的数据； 8学会利用相关的排序技术实现无序数列的排序操作。 二、内容要点 （一）算法 1算法的基本概念 算法是指解题方案的准确而完整的描述。 即是一组严谨地定义运算顺序的规 则，并且每一个规则都是有效的，且是明确的，没有二义性，同时该规则将在有 限次运算后可终止。 1）算法的基本特征 （1）可行性 由于算法的设计是为了在某一个特定的计算工具上解决某一个实际的问题 而设计

3、的，因此，它总是受到计算工具的限制，使执行产生偏差。 如：计算机的数值有效位是有限的，当大数和小数进行运算时，往往会因为 有效位数的影响而使小数丢失，因此，在算法设计时，应该考虑到这一点。 （2）确定性 算法的设计必须是每一个步骤都有明确的定义，不允许有模糊的解释，也不 能有多义性。 例如，一个实际的问题，小宝和萍萍共有 12 个苹果，小宝比萍萍多 4 个， 请问小宝和萍萍各有几个苹果？这个问题，我们可以立一个方程 来求解，要求 x 和 y 的值，公式是正确的，但如何让计算能够进行计算，我们的 算法不能把公式直接输进去，而应该设计出解题的步骤和过程。 即设计的算法是计算工具所能够正常解决问题的

4、过程。 （3）有穷性 算法的有穷性，即在一定的时间是能够完成的，即算法应该在计算有限个步 骤后能够正常结束。 例如，在数学中的无穷级数，在计算机中只能求有限项，即计算的过程是有 穷的。 （4）拥有足够的情报 算法的执行与输入的数据和提供的初始条件相关， 不同的输入或初始条件会 有不同的输出结果，提供准确的初始条件和数据，才能使算法正确执行。 2）算法的基本要素 一是数据对象的运算和操作，二是算法的控制结构。 （1）算法中对数据的运算和操作 算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组 成的一组指令序列。即算法是计算机所能够处理的操作所组成的指令序列。 （2）算法的控制结构

5、算法的功能不仅取决于所选用的操作，而且还与各操作之间的顺序有关。 在算法中，操作的执行顺序又称算法的控制结构，一般的算法控制结构有三 种：顺序结构、选择结构和循环结构。 在算法描述是，有相关的工具对这三种结构进行描述，常用的描述工具有： 流程图、N-S 结构图和算法描述语言等。 3）算法设计的基本方法 为用计算机解决实际问题而设计的算法，即是计算机算法。 通常的算法设计有如下几种： （1）列举法 列举法的基本思想是，根据提出的问题，列举出所有可能的情况，并用问题 中给定的条件检验哪些是满足条件的，哪些是不满足条件的。列举法通常用于解 决“是否存在”或“有哪些可能”等问题。 例如，我国古代的趣味

6、数学题：“百钱买百鸡”、“鸡兔同笼”等，均可采 用列举法进行解决。 使用列举法时，要对问题进行详细的分析，将与问题有关的知识条理化、完 备化、系统化，从中找出规律。 （2）归纳法 归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般 的关系。归纳是一种抽象，即从特殊现象中找出一般规律。但由于在归纳法中不 可能对所有的情况进行列举，因此，该方法得到的结论只是一种猜测，还需要进 行证明。 （3）递推 递推，即是从已知的初始条件出发，逐次推出所要求的各个中间环节和最后 结果。 其中初始条件或问题本身已经给定， 或是通过对问题的分析与化简而确定。 递推的本质也是一种归纳，递推关系式通常是

7、归纳的结果。 例如，裴波那契数列，是采用递推的方法解决问题的。 （4）递归 在解决一些复杂问题时， 为了降低问题的复杂程序， 通常是将问题逐层分解， 最后归结为一些最简单的问题。这种将问题逐层分解的过程，并没有对问题进行 求解，而只是当解决了最后的问题那些最简单的问题后，再沿着原来分解的逆过 程逐步进行综合，这就是递归的方法。 递归分为直接递归和间接递归两种方法。如果一个算法直接调用自己，称为 直接递归调用；如果一个算法 A 调用另一个算法 B，而算法 B 又调用算法 A，则 此种递归称为间接递归调用。 （5）减半递推技术 减半递推即将问题的规模减半，然后，重复相同的递推操作。 例如，一元二次

8、方程的求解。 （6）回溯法 有些实际的问题很难归纳出一组简单的递推公式或直观的求解步骤， 也不能 使用无限的列举。对于这类问题，只能采用试探的方法，通过对问题的分析，找 出解决问题的线索，然后沿着这个线索进行试探，如果试探成功，就得到问题的 解， 如果不成功， 再逐步回退， 换别的路线进行试探。 这种方法， 即称为回溯法。 如人工智能中的机器人下棋。 2算法复杂度 算法的复杂度包括时间复杂度和空间复杂度。 1）时间复杂度 即实现该算法需要的计算工作量。 算法的工作量用算法所执行的基本运算次 数来计算。 同一个问题规模下， 如果算法执行所需要的基本次数取决于某一特定输入时， 可以用以下两种方法来

9、分析算法的工作量： 算法工作量=f(n) （1）平均性态 用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。 设 x 是某个可能输入中的某个特定输入，p(x)是 x 出现的概率，t(x)是算法 在输入为 x 时所执行的基本运算次数，则算法的平均性态定义为： Dn 表示当规模为 n 时，算法执行时所有可能输入的集合。 （2）最坏情况复杂度 指在规模为 n 时，算法所执行的基本运算的最大次数。它定义为： 第二章 程序设计基础 一、学习目标与要求 1了解程序设计的方法，以及程序设计风格确立的一些因素，掌握程序设 计的基本规则； 2了解结构化程序设计的基本原则，掌握结构化程序设计的基本结构

10、与特 点； 3了解面向对象的程序设计方法，并理解面向对象方法的一些基本概念。 二、内容要点 （一）程序设计方法与风格 程序设计方法： 主要经过了面向过程的结构化程序设计和面向对象的程序设 计方法。 程序设计风格， 是指编写程序时所表现出来的特点、 习惯和逻辑思路。 通常， 要求程序设计的风格应强调简单和清晰，必须是可以读的，可以理解的。 要形成良好的程序设计的风格，应考虑如下因素： 1源程序文档化 （1）符号名的命名：符号名的命名要具有一定的实际含义，便于对程序的 理解，即通常说的见名思义； （2）程序注释：正确的程序注释能够帮助他人理解程序。注释一般包括序 言性注释和功能性注释； （3）视觉

11、组织：为了使程序一目了然，可以对程序的格式进行设置，适当 地通过空格、空行、缩进等使程序层次清晰。 2数据说明方法 （1）数据说明的次序规范化； （2）说明语句中变量安排有序化； （3）使用注释来说明复杂的数据结构。 3语句的结构 （1）在一行内只写一条语句； （2）程序的编写应该优先考虑清晰性； （3）除非对效率有特殊的要求，否则，应做到清晰第一，效率第二； （4）首先保证程序的正确，然后再要求速度； （5）避免使用临时变量使程序的可读性下降； （7）尽量使用库函数，即尽量使用系统提供的资源； （8）避免采用复杂的条件语句； （9）尽量减少使用“否定”条件的条件语句； （10）数据结构要有利

12、于程序的简化； （11）要模块化，使模块功能尽可能单一化； （12）利用信息隐蔽，确保每一个模块的独立性； （13）从数据出发去构造程序； （14）不要修补不好的程序，要重新编写。 4输入和输出 （1）对所有的输入输出数据都要检验数据的合法性； （2）检查输入项的各种重要组合的合理性； （3）输入格式要简单，以使得输入的步骤和操作尽可能简单； （4）输入数据时，应允许自由格式； （5）应允许缺省值； （6）输入一批数据时，最好使用输入结束标志； （7）以交互式输入输出方式进行输入时，要在屏幕上使用提示符明确输入 的请求，同时在数据输入过程中和输入结束时，应在屏幕上给出状态信息； （8）当程序设

13、计语言对输入格式有严格要求时，应保持输入格式与输入语 句的一致性；给所有的输出加注释，并设计输出报表格式。 （二）结构化程序设计 1结构化程序设计的原则 结构化程序设计方法的主要原则：自顶而下、逐步求精，模块化，限制使用 goto 语句。 1）自顶而下 程序设计时，应先考虑总体，后考虑细节；先考虑全局，后考虑局部目标。 即先从最上层总目标开始设计，逐步使问题具体化。 2）逐步求精 对复杂问题，应设计一些子目标作为过渡，逐步细化。 3）模块化 一个复杂问题，都是由若干个稍简单的问题构成的。模块化即是将复杂问题 进行分解，即将解决问题的总目标分解成若干个分目标，再进一步分解为具体的 小目标，把每一

14、个小目标称作一个模块。 4）限制使用 goto 语句 goto 语句可以提高效率，但对程序的可读性、维护性都造成影响，因此应 尽量不用 goto 语句。 2结构化程序设计的基本结构与特点 结构化程序设计是程序设计的先进方法和工具， 采用结构化程序设计可以使 程序结构良好、易读、易理解、易维护。 1）顺序结构 顺序结构即是顺序执行的结构，是按照程序语句行的自然顺序，一条一条语 句地执行程序。 2）选择结构 选择结构又称分支结构，它包括简单选择和多分支选择结构。程序的执行是 根据给定的条件，选择相应的分支来执行。 3）重复结构 重复结构又称循环结构，根据给定的条件，决定是否重复执行某一相同的或 类

15、似的程序段。利用重复结构可以大量简化程序行。 3结构化程序设计原则和方法的应用 1使用程序设计语言中的顺序、选择、循环等有限的控制结构表示程序的 控制逻辑； 2选用的控制结构只允许有一个入口和一个出口； 3程序语句组成容易识别的块，每块只有一个入口和一个出口； 4复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现； 5语言中所有没有的控制结构，应该采用前后一致的方法来模拟； 6严格控制 goto 语句的使用： （1）用一个非结构化的程序设计语言去实现一个结构化的构造； （2）若不使用 goto 语句会使功能模糊； （3）在某种可以改善而不是损害程序可读性的情况下。 第三章 软件工程基础 一、学

16、习目标与要求 1了解软件工程的基本概念； 2了解软件工程过程与软件的生命周期，以及软件工程的目标和原则； 3了解利用结构化分析法进行软件工程中的需求分析的方法，并了解需求 分析的方法和需要完成的任务； 4了解数据流图的使用方法； 5了解如何利用结构化设计方法进行软件设计，并了解软件设计的一些常 用用工具； 6了解软件测试的目的和方法，以及软件测试的准则，了解常用的软件测 试方法的区别和各自的功能与特点； 7了解程序调试的方法和原则。 二、内容要点 （一）软件工程基本概念 1软件定义与软件特点 1）软件的定义 与计算机系统的操作有关的计算机程序、规程、规则，以及可能有的文件、 文档及数据。 2）

17、软件的特点 （1）软件是一种逻辑实体，而不是物理实体，具有抽象性； （2）软件的生产与硬件不同，它没有明显的制作过程； （3）软件在运行、使用期间不存在磨损、老化问题；但为了适应硬件、环 境以及需求的变化要进行修改，会导致一些错误的引入，导致软件失效率升高， 从而使得软件退化； （4） 软件的开发、 运行对计算机系统具有依赖性， 受到计算机系统的限制， 这导致了软件移植的问题； （5）软件复杂性高，成本昂贵。软件开发需要投入大量、高强度的脑力劳 动，成本高，风险大； （6）软件开发涉及诸多的社会因素。许多软件的开发和运行涉及软件用户 的机构设置，体制问题以及管理方式等，甚至涉及到人们的观念和心

18、理，软件知 识产权及法律等问题。 3）软件的分类 按功能分，可分为： 应用软件：为解决特定领域的应用而开发的软件 系统软件：是计算机管理自身资源，提高计算机使用效率并为计算机用户提 供各种服务的软件 支撑软件（或工具软件）：介于系统软件和应用软件之间，协助用户开发软 件的工具性软件，包括辅助和支持开发和维护应用软件的工具软件 2软件危机与软件工程 1）软件危机 泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题。 它主要表 现在： （1）软件需求的增长得不到满足，用户对系统不满意的情况经常发生； （2）软件开发成本和进度无法控制。开发的成本超预算和开发周期的超期 经常出现； （3）软件质

19、量难以保证； （4）软件不可维护或维护程度非常低； （5）软件成本不断提高； （6）软件开发生产率的提高赶不上硬件的发展和应用需求的增长。 2）软件工程 软件工程的定义：是应用于计算机软件的定义、开发和维护的一整套方法、 工具、文档、实践标准和工序。 软件工程包括 3 个要素：方法、工具和过程。 方法：完成软件工程项目的技术手段； 工具：支持软件的开发、管理、文档生成； 过程：支持软件开发的各个环节的控制、管理。 3软件工程过程与软件生命周期 1）软件工程过程 软件工程过程把输入转化为输出的一组彼此相关的资源和活动。 支持软件工 程过程的两方面内涵： （1）软件工程过程是指为获得软件产品，在软

20、件工具支持下由软件工程师 完成的一系列软件工程活动。它包括 4 种基本活动： P软件规格说明。规定软件的功能及其运行时的限制； D软件开发。产生满足规格说明的软件； C软件确认。确认软件能够满足客户提出的要求； A软件演进过程。 为满足客户的变更要求， 软件必须在使用的过程中演进。 （2）使用适当的资源（包括人员、硬软件工具、时间等），为开发软件进 行的一组开发活动， 在过程结束时将输入 （用户要求） 转化为输出 （软件产品） 。 软件工程过程是将软件工程的方法和工具综合起来，以达到合理、及时地进 行计算机软件开发的目的。 2）软件生命周期 将软件产品从提出、实现、使用维护到停止使用退役的过程

21、称为软件生命周 期。即软件的生命周期就是软件产品从开始考虑其概念开始，到软件产品不能使 用为止的整个时期都属于软件生命周期。 一般包括可行性研究与需求分析、 设计、 实现、测试、交付使用以及维护等活动。这些活动可以有重复，执行时也可以有 迭代。 生命周期的主要阶段： 软件定义 软件开发 软件维护 软件生命周期的主要活动阶段是： （1） 可行性研究与计划制定： 确定待开发软件系统的开发目标和总的要求， 给出它的功能、性能、可靠性以及接口等方面的可能方案，制定完成开发任务的 实话计划； （2）需要分析。对待开发软件提出的需求进行分析并给出详细的定义； （3）软件设计。系统设计人员和程序设计人员给出

22、软件的结构、模块的划 分、功能的分配以及处理流程； （4）软件实现。把软件设计转换成计算机可以接受的程序代码。即完成源 程序的编码，编写用户手册、操作手册等面向用户的文档，编写单元测试计划； （5）软件测试。在设计测试用例的基础上，检验软件的各个组成部分，编 写测试分析报告； （6） 运行和维护。 将已交付的软件投入运行， 并在运行使用中不断地维护， 根据新提出的需求进行必要且可能的扩充和删改。 4软件工程的目标与原则 1）软件工程的目标 软件工程的目标： 在给定成本、 进度的情况下， 开发出具有有效性、 可靠性、 可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性 且满足

23、用户需求的产品。 软件工程需要达到的基本目标： 付出较低的开发成本 达到要求的软件功能 取得较好的软件性能 开发的软件易于移植 需要较低的维护费用 能按时完成开发，及时交付使用 软件工程的理论和技术性研究的内容包括：软件开发技术和软件工程管理。 （1）软件开发技术 软件开发方法学、开发过程、开发工具和软件工程环境，其主体内容是软件 开发方法学。软件开发方法学是根据不同的软件类型，按不同的观点和原则，对 软件开发中应遵循的策略、原则、步骤和必须产生的文档资料都做出规定，从而 使软件开发能够进入规范化和工程化的阶段。 （2）软件工程管理 软件工程管理：软件管理学、软件工程经济学、软件心理学等内容。

24、 软件工程管理学包括：人员组织、进度安排、质量保证、配置管理、项目计 划等。 软件工程经济学：是研究软件开发中成本的估算、成本效益分析的方法和技 术，用经济学的基本原理事研究软件工程开发中的经济效益问题。 软件心理学：从个体心理、人类行为、组织行为和企业文化等角度来研究软 件管理和软件工程。 第四章 数据库设计基础 一、学习目标与要求 1了解数据库系统的基本概念，以及数据库系统的发展； 2了解数据模型的基本概念，并对 E-R 模型、层次模型、网状模型和关系 模型进行了解，并掌握关系模型的数据结构、关系的操作和数据约束等知识； 3了解关系模型的基本操作，掌握关系模型的基本运算及扩充运算； 4了解

25、数据库的设计与管理，掌握数据库设计的几个阶段的方法和特点。 二、内容要点 （一）数据库系统的基本概念 1数据、数据库、数据库管理系统 1）数据 数据是指存储在某一种媒体上能够被识别的物理符号， 即描述事物的符号记 录。 数据是有结构的。首先，数据有型与值的区别，型即类型，值是符合指定类 型的值。 数据的概念在数据处理领域中已经大大地拓宽了。 数据不仅包括数字、 字母、 文字和其他特殊字符组成的文本形式的数据，而且还包括图形、图像、动画、影 像、声音等多媒体数据。但是使用最多、最基本的仍然是文字数据。 2）数据库 数据库（DataBase，DB），是存储在计算机存储设备上，结构化的相互关联 的数

26、据的集合。它不仅包括描述事物的数据本身，而且还包括相关事物之间的联 系。 它用综合的方法组织和管理数据， 具有较小的数据冗余， 可供多个用户共享， 具有较高的数据独立性，具有安全机制，能够保证数据的安全、可靠，允许并发 地使用数据库，能有效、及时地处理数据，并能保证数据的一致性和完整性。 例如，某个学校的相关数据，如学生基本情况、选课情况、学籍管理等所涉 及的相关数据的集合。 3）数据库管理系统 数据库管理系统（DataBase Management System，DBMS）是对数据库进行管 理的系统软件，它的职能是有效地组织和存储数据、获取和管理数据，接受和完 成用户提出的访问数据的各种请求

27、。同时还能保证数据的安全性、可靠性、完整 性、一致性，还要保证数据的高度独立性。 数据库管理系统主要功能包括以下几个方面： （1）数据模式定义 数据库管理系统负责为数据库构建模式，也为数据库构建其数据框架。 （2）数据存取的物理构建 数据库管理系统负责为数据模式的物理存取及构建提供有效的存取方法和 手段。 （3）数据操纵 数据库管理系统为用户使用数据库中的数据提供方便， 一般提供查询、 插入、 修改和删除数据的功能，此外，还具有简单的算术运算和统计功能，还具有专长 强大的程序控制功能。 （4）数据的完整性、安全性定义与检查 数据库中的数据具有内存语义上的关联性与一致性，即数据的完整性。数据 的

28、完整性是保证数据库中数据正确的必要条件。 （5）数据的并发控制与故障恢复 数据库是一个集成、共享的数据集合体，它能为多个应用程序服务，因此， 当多个应用程序对数据库并发操作时，要保证数据不被破坏。 （6）数据的服务 数据库管理系统提供了对数据库中数据的多种服务，如数据拷贝、转存、重 组、性能监测、分析等。 数据库管理系统提供的相应的数据语言包括如下： 1）数据定义语言（Data Definition Language，DDL） D 用户通过它可以方便地对数据库中的相关内容进行定义。 例如， 对数据库、 表、索引进行定义。 2）数据操纵语言（Data Manipulation Language，

29、DML） 用户通过它可以实现对数据库的基本操作。 例如， 对表中数据的查询、 插入、 删除和修改。 3）数据控制语言（Data Control Language，DCL） 负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等功能，包 括系统初启程序、文件读写与维护程序、存取路径管理程序、缓冲区管理程序、 安全性控制程序、完整性检查程序、并发控制程序、事务管理程序、运行日志管 理程序、数据库恢复程序等。 目前流行的 DBMS 均为关系型数据库系统，发 ORACLE、Sybase 的 PowerBuilder 及 IBM 的 DB2、微软件的 SQLServer 等。还有一些小型的数据库， 如 Visual FoxPro 和 Access 等。 4）数据库管理员 数据库的管理员（DataBase Administrator，DBA）：对数据库的规划、设 计、维护、监视等进行管理。 主要工作如下： （1）数据库设计 （2）数据库维护 （3）改善系统性能，提高系统效率 5）数据库系统 数据库系统（DataBase System，DBS）由如下几个部分组成： 数据库（数据） 数据库管理系统（软件） 数据库管理员（人员） 系统平台（硬件平台和软件平台） 硬件平台包括： 计算机 网络 软件平台包括： 操作系统 数据库系统开发工具 接口软件1