《计算机二级考试公共基础知识点》由会员分享，可在线阅读，更多相关《计算机二级考试公共基础知识点（4页珍藏版）》请在金锄头文库上搜索。
1、第一章数据结构与算法1. 所谓算法是解题方案的准确而完整的描述。是一组严谨地定义运算顺序的规则，此顺序将在有限的次数下终止。2. 算法的基本特征 ：可行性、确定性、有穷性、拥有足够的情报。3. 一个算法由两种基本要素组成：一是对数据对象的运算和操作，二是算法的控制结构。4. 指令系统： 一个计算机系统能执行的所有指令的集合。5. 在一般的计算机系统中，基本的运算和操作有以下四类：算术运算、逻辑运算、关系运算、数据传输。6. 一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。7. 计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法 。8. 常用的几种算法方法：列举法、归纳
2、法、递推、递归、减半递推技术、回溯法。9. 算法的复杂度主要包括：时间复杂度和空间复杂度。10.所谓算法的 时间复杂度 ，是指执行算法所需要的计算工作量。11.算法的工作量 用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数。12.在同一个问题规模下，如果算法执行所需要的基本运算次数取决于某一特定输入时，可以用以下两种方法来分析算法的工作量：平均性态、最坏情况复杂性。13.一个算法的 空间复杂度 ，一般是指执行这个算法所需要的内存空间。14.数据结构作为计算机的一门科学，主要研究和讨论以下三个方面的问题： 、数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；
3、、在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；、对各种数据结构进行的运算。讨论以上问题的主要目的是为了提高数据处理的效率。所谓提高数据处理的效率，主要包括两方面：一是提高数据处理的速度，二是尽量节省在数据处理过程中所占用的计算机存储空间。15.数据元素具有广泛的含义。一般来说，现实世界中客观存在的一切个体都可以是数据元素。16.在数据处理领域中，每一个需要处理的对象都可以抽象成数据元素 。数据元素一般简称为元素。17. 一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系（即联系），这种关系反映了该集合中的数据元素所固有的一种结构。在数据处理领域
4、中，通常把数据元素之间这种固有的关系简单地用前后件关系（或直接前驱与直接后继关系）来描述。18.前后件关系 是数据元素之间的一个基本的关系，但前后件关系所表示的实际意义随具体对象的不同而不同。一般来说，数据元素之间的任何关系都可以用前后件关系来描述。19.一个数据结构应饱含以下两方面的信息：、表示数据元素的信息、表示各数据元素之间的前后件关系。20.所谓的数据的 逻辑结构 ，是指反映数据元素之间逻辑关系的数据结构。21.数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构 ） 。22.一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、
5、链接、索引等存储结构。23.如果一个非空的数据结构满足下列两个条件：、有且只有一个根结点、每一个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构（线性结构又称为线性表）24.线性表是由n（n0）个数据元素a1，a1，a2,， an组成的一个有限序列，表中的每一个数据元素，除了第一个，有且只有一个前件，除了最后一个外，有且只有一个后件。即线性表或是一个空表，或可以表示为（a1，a1，a2,， ai，,，an）其中 ai（I=1,2, ,，n）是属于数据对象的元素，通常也称其为线性表中的一个结点。25.非线性表有如下一些结构特征：、有且只有一个根结点a1，它无前件；、有且只有一个终端
6、结点an，它无后件；、除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数为n 称为线性表的长度。当地时间 n=0 时，称为空表。26.线性表的顺序存储结构具有以下两个基本特点：、线性表中所有元素所占的存储空间是连续的；、线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。27.栈是限定在一端进行插入与删除的线性表。是按照“先进后出”（FILO）或“后进先出”（LIFO）的原则组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。28.栈的基本运算有三种：入栈、退栈、与读栈顶元素。29.队列 （queue）是指允许在一端进行插入、而在另一端进行删除
7、的线性表。30.在实际应用中，队列的顺序存储结构一般采用循环队列的形式。31.所谓循环队列 ，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。32.线性表顺序存储结构存在以下几方面的缺点：、在一般情况下，要在顺序存储的线性表中插入一个新元素或删除一个元素时，为了保证插入或删除后的线性表仍然为顺序存储，则在插入或删除过程中需要移动大量的数据元素。、当为一个线性表分配顺序存储空间后，如果出现线性表的存储空间已满时，就会发生“上溢”错误。、在实际应用中，往往是同时有多个线性表共享计算机的存储空间。33.在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数
8、据元素的值，称为数据域 ；另一部分用于存放指针，称为指针域 。其中指针用于指向该结点的前一个结点或后一个结点（即前件或后件）。34.线性表的链式存储结构称为线性链表。35.一般来说，在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致。36.二叉树具有以下两个特点:非空二叉树只有一个根结点; 每一个结点最多有两棵子树, 且分别称为该结点的左子树与右子树. 37.二叉树具有以下几个性质: （1）在二叉树的第K层上 , 最多有 2K-1(K1) 个结点 . 深度为 m的二叉树最多有2 m-1个结点。（2）在任意一棵二叉树中，度为0 的结点（即
9、叶子结点）总是比度为2的结点多一个。（3）具有 n 个结点的二叉树，其深度至少为log2n+1 ，其中 log2n 的整数部分。（4）具有 n 个结点的完全二叉树的深度为log2n+1 。38.设完全二叉树共有n 个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，,，N给结点进行编号，则对于编号为 K（K=1，2，,，n）的结点有以下结论：若 K=1，则该结点为根结点，它没有你结点；若K1，则该结点的你结点编号为INT（K/2） 。若 2KN，则编号为 K 的结点的左子结点编号为2K；否则该结点无左子结点（显然也没有右子结点）。若 2K+1n，则编号为 K 的结点的右子结点编号
10、为2K+1；否则该结点无右子结点。39.二叉树通常采用 链式存储结构 。40.二叉树的遍历是指不重复地访问二叉树中的所有结点。41.二叉树的遍历可以分为三种：前序遍历、中序遍历、后序遍历。42.所谓 前序遍历 是指在访问根结点、 遍历左子树与遍历右子树这三者中，首先访问根结点， 然后遍历左子树， 最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。43.所谓 中序遍历 是指在访问根结点、 遍历左子树与遍历右子树这三者中，首先遍历左子树， 然后访问根结点， 最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。44.所
11、谓 后序遍历 是指在访问根结点、 遍历左子树与遍历右子树这三者中，首先遍历左子树， 然后遍历右子树， 最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。45.所谓 查找 是指在一个给定的数据结构中查找某个指定的元素。46.二分法查找只适用于顺序存储的有序表。47.对于长度为n 的有序线性表，在最坏情况下，二分查找只需要比较log2n 次，而顺序查找需要比较n 次。48.所谓交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。49.假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2 遍的从前往后的扫描和n/2 遍的从后往前的扫描，需要
12、的比较次数为n（n-1）/2 。50.插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中。51.在最坏情况下，简单插入排序需要n（n-1）/2 次比较。52.最坏情况下，希尔排序所需要的比较次数为O（n 0.5 ） 。53.简单选择排序在最坏情况下需要比较n（n-1）/2 次。54.在最坏情况下，堆排序需要比较的次数为O（nlog2n ） 。第二章程序设计基础1. 一般来讲，程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路。著名的“清晰第一，效率第二”的论点已成为当今主导的程序设计风格。2. 注释一般分为 序言性注释和功能性注释。3. 结构化程序设计方法的主要原则可以概括为
13、自顶向下，逐步求精，模块化，限制使用goto 语句。4.1966 年，Boehm和 Jacopini证明了程序设计语言仅仅使用顺序、选择和重复 三种基本控制结构就足以表达出各种其他形式结构的程序设计方法。5. 对象可以用来表示客观世界中的任何实体，6. 对象有如下一些基本特点：标识惟一性、分类性、多态性、封装性、模块独立性好。7. 将属性、操作相似的对象归为类，也就是说：类是具有共同属性、共同方法的对象的集合。类是对象的抽象，它描述了属于该对象类型的所有对象的性质，而一个对象则是其对应类的一个实例。8. 面向对象的世界是通过对象与对象间彼此的相互合作来推动的，对象间的这种相互合作需要一个机制协
14、助进行，这样的机制称为“消息”。9. 通常，一个消息由下述三部分组成：接收消息的对象的名称、消息标识符、零个或多个参数。10.继承 是使用已有的类定义作为基础建立新类的定义技术。11.广义地说， 继承是指能够直接获得已有的性质和特征，而不必重复定义他们。12.继承分为单继承与多重继承。单继承是指，一个类只允许有一个父类，即类等级为树形结构。13.对象根据所接受的消息而做出动作，同样的消息被不同的对象接受时可导致完全不同的行动，该现象称为多态性 。第三章软件工程基础1. 计算机软件 （Software ）是计算机系统与硬件相互依存的另一部分，是包括程序、数据及相关文档的完整集合。2.1968 年
15、在北大西洋公约组织会议（NATO会议）上，讨论摆脱软件危机的办法，软件工程（softwareengineering）作为一个概念首次被提出，这在软件技术发展史上是一件大事。3. 将系统化的、规范的、可度量的方法应用于软件的开发、运行和维护的过程，即将工程化应用于软件中。4. 软件工程主要思想都是强调在软件开发过程中需要应用工程化原则。5. 软件工程包括3 个要素 ，即方法、工具和过程。方法是完成软件工程项目的技术手段；工具支持软件的开发、管理、文档生成；过程支持软件开发的各个环节的控制、管理。6. 软件工程的核心思想是把软件产品（就像其他工业产品一样）看作一个工程产品来处理。7. 软件工程通常
16、包括4 种基本活动： P（Plan）-软件规格说明、 D（DO ）-软件开发、C（Check）-软件确认、 A（Action ）-软件演进8. 软件周期 的主要活动阶段是：可行性研究与计划制定、需求分析、软件设计、软件实现、软件测试、运行和维护。9. 软件工程需要达到的基本目标 是：付出较低的开发成本，达到要求的软件功能，取得较好的软件性能，开发的软件易于移植，需要较低的维护费用，能按时开发，及时交付使用10.软件工程的理论和技术性研究的内容主要包括：软件开发技术和软件工程管理。11.软件开发技术包括：软件开发方法学，开发过程，开发工具和软件工程环境，其主体内容是软件开发方法学。12.软件工程管理 包括：软件管理学，软件工程经济学，软件心里学等内容13.软件工程的原则包括抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性可验证性。14.软件需求 是指用户对目标软件系统在功能、行为、性能、设计约束等方面的期望。15.需求分析的任务是发展需求、求精、建模和定义需求的过程。需求分析将创建所需的数据模型、功能模型和控制模型。16 需求分析阶段工作，可以概括为四个方面: 需求获取、需求分析、
