全国计算机二级基础重点知识点解析

全国计算机二级基础

§1基本数据结构和算法

1.1算法

算法概念：是对一个问题求解步骤的一种描述，是求解问题的方法，它是指令的有限序列，其中每条指令表示一个或者多个操作。

算法不等于程序，也不等于计算机方法，程序的编制不可能优于算法的设计。

(2011.9)（1）下列叙述中正确的是（）

A)算法就是程序 B)设计算法时只要考虑数据结构的设计

C)设计算法时只需要考虑结果的可靠性 D）以上说法都不对

算法的基本特征：

（1）可行性；

（2）确定性，算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性；

（3）有穷性，算法必须能在有限的时间内做完，取能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）输入(>=0)和输出性（>=1）。

例一个算法应该具有“确定性”等5个特性，下面对另外4个特性的描述中错误的是（）。 A．有零个或多个输入 B．有零个或多个输出

C．有穷性 D．可行性

答案：B

算法的基本要素：

（1）算法中对数据的运算和操作

在一般的计算机系统中，基本的运算和操作有以下4类：算术运算、逻辑运算、关系运算和数据传输。

（2）算法的控制结构

一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。

算法的复杂度：算法时间复杂和算法空间复杂度。

（1）算法时间复杂度是指执行算法所需要的计算工作量。

（2）算法空间复杂度是指执行这个算法所需要的内存空间。

程序设计语言是用于书写计算机程序的语言，其基本成分有以下4种，数据成分：用来描述程序中的数据。运算成分：描述程序中所需的运算。控制成分：用来构造程序的逻辑控制结构。传输成分：定义数据传输成分，如输入输出语言。

例：程序设计语言的基本成分是数据成分、运算成分、控制成分和（）。

A) 对象成分 B) 变量成分

C) 语句成分 D) 传输成分

1.2数据结构的基本概念

数据结构研究的三个方面：

（1）数据集合中和数元素之间所固有的逻辑关系，即数据的逻辑结构；

（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；

（3）对各种数据结构进行的运算。(基于逻辑结构)

数据的逻辑结构包含：

（1）表示数据元素的信息；

（2）表示各数据元素之间的前后件关系。

数据的存储结构有顺序、链接、索引等。

线性结构条件：

（1）有且只有一个根结点；

（2）每一个结点最多有一个前件，也最多有一个后件。

非线性结构：不满足线性结构条件的数据结构。

(2011.3)（2）下列叙述中正确的是（）

Ａ）有一个以上根结点的数据结构不一定是非线性结构

Ｂ）只有一个根结点的数据结构不一定是线性结构

Ｃ）循环链表是非线性结构Ｄ）双向链表是非线性结构

1.3 线性表及其顺序存储结构

线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。

在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。

非空线性表的结构特征：

（1）且只有一个根结点a1，它无前件；

（2）有且只有一个终端结点an，它无后件；

（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。

线性表的顺序存储结构具有以下两个基本特点：

（1）线性表中所有元素的所占的存储空间是连续的；

（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)×k,，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。

(2011.9)（2）长度为n的顺序存储的线性表中插入一个元素，最坏情况下需要移动表中【2】元素。

(2010.9)（1）下列叙述中正确的是

A）线性表的链式存储结构与顺序存储结构所需要的空间是相同的

B）线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构

C）线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构

D)上述三种说法都不对

1.4 栈和队列

栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。

(2011.9)（1）数据结构分为线性结构与非线性结构，带链的栈属于【1】。

(2011.3)（1）下列关于栈叙述正确的是（）

A)栈顶元素最先能被删除 B)栈顶元素最后才能被删除

C)栈底元素永远不能被删除 D）以上三种说法都不对

栈按照“先进后出”（FILO）或“后进先出”（LIFO）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。

(2010.9)（2）下列叙述中正确的是

A)在栈中，栈中元素随栈底指针不变与栈顶指针的变化而动态变化

B）在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化

C）在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化

D)上述三种说法都不对

(2010.9)（1）一个栈的初始状态为空。首先将元素5、4、3、2、1依次入栈，然后退栈一次，再将元素A，B，C，D依次入栈，之后将所有元素全部退栈，则所有元素退栈（包括中间退栈的元素）的顺序为【1】。

队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear指针指向队尾，指针指向队头。front

队列是“先进行出”（FIFO）或“后进后出”（LILO）的线性表。

队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。

循环队列：s=0表示队列空，s=1且front=rear表示队列满

1.5 线性链表

数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。

结点由两部分组成：（1）用于存储数据元素值，称为数据域；（2）用于存放指针，称为指针域，用于指向前一个或后一个结点。

在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。

(2011.9)（2）下列关于线性链表的叙述中，正确是（）

A)各数据结点的存储空间可以不连续，但他们的存储顺序与逻辑顺序必须一致

B)各数据结点的存储顺序与逻辑顺序可以不一致，但他们的存储空间必须连续

C)进行插入与删除时，不需要移动表中的元素 D）以上三种说法都不对

1.6 树与二叉树

树是一种简单的非线性结构，所有元素之间具有明显的层次特性。

在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。

二叉树的特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。

二叉树的基本性质：

1）在二叉树的第k层上，最多有2(k≥1)个结点；

k-1（

2）深度为m的二叉树最多有2-1个结点；

m（

（3）度为0的结点（即叶子结点）总是比度为2的结点多一个；

（4）具有n个结点的二叉树，其深度至少为[logn]+1,其中[logn]表示取logn的整数部分；222（5）具有n个结点的完全二叉树的深度为[logn]+1；2(2011.3)（３）某二叉树共有７个结点，其中叶子结点只有１个，则该二叉树的深度为（假设根结点在第１层）

Ａ）３Ｂ）４Ｃ）６ D)7

(2010.9)（3）一棵二叉树有10个度为1的结点，7个度为2的结点，则该二叉树共有【3】个结点。

(2011.9)（3）以下关于二叉树的叙述中，正确的是（）

A)叶子结点总是比度为2的结点少一个B)叶子结点总是比度为2的结点多一个

C)叶子结点数是度为2的结点数的两倍 D）度为2的结点数是度为1的结点数的两倍

是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2个结点，深度k-1满二叉树

为m的m满二叉树有2-1个结点。

完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。

二叉树存储结构采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行存储。

二叉树的遍历：

（1）前序遍历（DLR）:首先访问根结点，然后遍历左子树，最后遍历右子树；

（2）中序遍历（LDR）:首先遍历左子树，然后访问根结点，最后遍历右子树；

（3）后序遍历（LRD）: 首先遍历左子树，然后遍历右子树, 最后访问根结点.

。】2，则后序遍历结果为【ABDECF，前序遍历结果为DBEAFC）一棵二叉树的中序遍历结果为2（(2011.3)

1.7查找技术顺序查找的使用情况：）表采用链式存储结构。（2（1）线性表为无序表；对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较logn次，而顺序查找需要比较n-12次。

(2011.3)（1）有序线性表能进行二分差找的前提是该线性表必须是【1】存储的。

(2010.9)（2）在长度为n的线性表中，寻找最大项至少需要比较【2】次。

1.8排序技术

交换类排序法：（1）冒泡排序法，需要比较的次数为n(n-1)/2；（2）快速排序法。

2。）nO（O（nnlog），而快速排序法的平均执行时间是冒泡排序法的平均执行时间是2插入类排序法：（1）简单

插入排序法，最坏情况需要n(n-1)/2次比较；（2）希尔排序法，最坏情况需要O（n ）次比较。选择类排序法：（1）简单选择排序法，最坏情况需要n(n-1)/2次比较；（2）堆排序法，最坏情况需要O（nlog n）次比较。21.9 例题详解

一、选择题

【例1】算法的时间复杂度取决于_______。

A）问题的规模B）待处理的数据的初态

C）问题的难度D）A）和B）

解析：算法的时间复杂度不仅与问题的规模有关，在同一个问题规模下，而且与输入数据有关。即与输入数据所有的可能取值范围、输入各种数据或数据集的概率有关。

答案：D）

【例2】在数据结构中，从逻辑上可以把数据结构分成_______。

A）内部结构和外部结构B）线性结构和非线性结构

C）紧凑结构和非紧凑结构D）动态结构和静态结构

解析：逻辑结构反映数据元素之间的逻辑关系，线性结构表示数据元素之间为一对一的关系，非线性结构表示数据元素之间为一对多或者多对一的关系，所以答案为B）。

答案：B）

【例3】以下_______不是栈的基本运算。

A）判断栈是否为空B）将栈置为空栈

C）删除栈顶元素D）删除栈底元素

解析：栈的基本运算有：入栈，出栈（删除栈顶元素），初始化、置空、判断栈是否为空或满、提取栈顶元素等，对栈的操作都是在栈顶进行的。

答案：D）

【例4】链表不具备的特点是_______。

A）可随机访问任意一个结点B）插入和删除不需要移动任何元素

C）不必事先估计存储空间D）所需空间与其长度成正比

解析：顺序表可以随机访问任意一个结点，而链表必须从第一个数据结点出发，逐一查找每个结点。所以答案为A）。

答案：A）

【例5】已知某二叉树的后序遍历序列是DACBE，中序遍历序列是DEBAC，则它的前序遍历序列是_______。

DEABC

）B ACBED ）A．

C）DECAB D）EDBAC

解析：后序遍历的顺序是左子树－右子树－根结点；中序遍历顺序是左子树－根结点－右子树；前序遍历顺序是根结点－左子树－右子树。根据各种遍历算法，不难得出前序遍历序列是EDBAC。所以答案为D）。

答案：D）

【例6】设有一个已按各元素的值排好序的线性表（长度大于2），对给定的值k，分别用顺序查找法和二分查找法查找一个与k相等的元素，比较的次数分别是s和b，在查找不成功的情况下，

s和b的关系是_______。

A）s=b B）s>b C）s

解析：对于顺序查找，查找不成功时和给定关键字比较的次数为n+1。二分查找查找不成功的关键字比较次数为［logn］+1。当n≥2时，显然n+1>［logn］+1。22答案：B）

【例7】在快速排序过程中，每次划分，将被划分的表（或子表）分成左、右两个子表，考虑这两个子表，下列结论一定正确的是_______。

A）左、右两个子表都已各自排好序

B）左边子表中的元素都不大于右边子表中的元素

C）左边子表的长度小于右边子表的长度

D）左、右两个子表中元素的平均值相等

解析：快速排序基本思想是：任取待排序表中的某个元素作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子表，左子表元素的排序码均小于或等于基准元素的排序码，

右子表的排序码则大于基准元素的排序码，然后分别对两个子表继续进行排序，直至整个表有序。答案：B）

二、填空题

【例1】问题处理方案的正确而完整的描述称为_______。

解析：计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。

答案：算法

【例2】一个空的数据结构是按线性结构处理的，则属于_______。

解析：一个空的数据结构是线性结构或是非线性结构，要根据具体情况而定。如果对数据结构的运算是按线性结构来处理的，则属于线性结构，否则属于非线性结构。

答案：线性结构

【例3】设树Ｔ的度为４，其中度为１、２、３和４的结点的个数分别为４、２、１、１，则Ｔ中叶子结点的个数为_______。

解析：根据树的性质：树的结点数等于所有结点的度与对应的结点个数乘积之和加１。

因此树的结点数为１×４＋２×２＋３×１＋４×１＋１＝16。叶子结点数目等于树结点总数减去度不为０的结点数之和，即16－（４＋２＋１＋１）＝８。

答案：8

【例4】二分法查找的存储结构仅限于_______且是有序的。

解析：二分查找，也称折半查找，它是一种高效率的查找方法。但二分查找有条件限制：要求表必须用顺序存储结构，且表中元素必须按关键字有序(升序或降序均可）。

答案：顺序存储结构

§2程序设计基础

程序设计设计方法和风格2.1．

如何形成良好的程序设计风格：1、源程序文档化； 2、数据说明的方法； 3、语句的结构； 4、输入和输出

注释分序言性注释和功能性注释，语言结构清晰第一、效率第二。

2.2结构化程序设计

结构化程序设计方法的四条原则是：1、自顶向下；2、逐步求精；3、模块化； 4、限制使用goto语句。

结构化程序的基本的特点：

（1）顺序结构：一种简单的程序设计，最基本、最常用的结构；

（2）选择结构：又称分支结构，包括简单选择和多分支选择结构，可根据条件，判断应该选择哪一条分支来执行相应的语句序列；

（3）重复结构：又称循环结构，可根据给定条件，判断是否需要重复执行某一相同程序段。(2011.3)（5）结构化程序所要求的基本结构不包括（）

A)顺序结构 B)GOTO跳转 C)选择（分支）结构Ｄ）重复（循环）结构

2.3面向对象的程序设计

面向对象的程序设计方法中，最基本的概念是对象和类，类具有以下特点：封装性、继承性、多态性；对象有如下一些基本特点，即标识惟一性、分类性、多态性、封装性和模块独立性。

类的继承性优点：相似的对象可以共享程序代码和数据结构，从而大大减少了程序中的冗余，提高软件的可重用性。

例如：在面向对象方法中，类之间共享属性和操作的机制称为继承性.

(2010.9)（6）面向对象方法中，继承是指

A)一组对象多具有的相似性质 B)一个对象具有另一个对象的性质

C)各对象之间的共同性质 D）类之间共享属性和操作的机制

(2011.9)（10）下列选项中属于面向对象设计方法主要特征的是（）

Ａ)继承Ｂ自顶向下Ｃ)模块化Ｄ)逐步求精

多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。

类是指具有共同属性、共同方法的对象的集合。所以类是对象的抽象，对象是对应类的一个实例。

(2011.3)（10）定义无符号整数类为UInt，下面可以作为类UInt实例化值的是（）

A)-369 B)369 C)0.369 D)整数集合{1,2,3,4,5}

2.4 例题详解

【例1】面向对象的开发方法中，类与对象的关系是_______。

A）抽象与具体B）具体与抽象

C）部分与整体D）整体与部分

解析：现实世界中的很多事物都具有相似的性质，把具有相似的属性和操作的对象归为类，也就是说类是具有共同属性、共同方法的对象的集合，是对对象的抽象。它描述了该对象类型的所有对象的性质，而一个对象则是对应类的一个具体实例。所以本题正确答案为A）项。

答案：A）

【例2】在面向对象方法中，使用已经存在的类定义作为基础建立新的类定义，这样的技术叫做_______。

解析：继承是面向对象方法的一个主要特征。继承是使用已有的类定义作为基础建立新类的定义技术。已有的类可当作基类来引用，则新类相应地可当作派生类来引用。

答案：继承

【例3】对象的基本特点包括_______、分类性、多态性、封装性和模块独立性好等5个特点。解析：对象具有如下的基本特点：

（1）标识惟一性。对象是可区分的，并且由对象的内在本质来区分；

（2）分类性。可以将具有相同属性和操作的对象抽象成类；

（3）多态性。同一个操作可以是不同对象的行为；

（4）封装性。只能看到对象的外部特征，无需知道数据的具体结构以及实现操作的算法；（5）模块独立性。面向对象是由数据及可以对这些数据施加的操作所组成的统一体。

答案：标识惟一性

【例4】对象根据所接收的消息而做出动作，同样的消息被不同的对象所接收时可能导致完全不同的行为，这种现象称为_______。

解析：对象根据所接收的消息而做出动作，同样的消息被不同的对象接收时可导致完全不同的行为，该现象称为多态性。

答案：多态性

§3软件工程基础

详细重点学习知识点：

1．软件的概念、软件生命周期的概念及各阶段所包含的活动

2．概要设计与详细设计的概念、模块独立性及其度量的标准、详细设计常用的工具

3．软件测试的目的、软件测试的4个步骤

4．软件调试的任务

3.1软件工程基本概念