2025年全国计算机等级考试二级深度攻略与实践指南 (一)

数据构造与算法

一、基本概念:

。数据（Data）：信息载体，可以被计算机识

另I」、存储和加工处理物理符号。波及文本

类型数据（如：字母、数字、中文）和多媒

体类型数据（如：声音、动画、图像）。

♦:♦数据元素（DataElement）：是数据基本单

位，有时也称为元素、结点、顶点、记录,

可以有若干个数据项（字段、域、属性）

构成。

♦:♦数据构造（DataStructure）：指是数据

之间互有关系，即数据组织形式。其波及

三个某些：

1、逻辑构造：数据元素之间逻辑关系

2、存储构造：数据元素及其关系在计算

机存储器内体现。

3、数据运算（算法）：即对数据施加操作

♦:♦数据逻辑构造有两大类：

1、线性构造：

特性是：若构造是非空集，则有且仅有一种

开始结点和一种终端结点，并且所有结点1

多只有一种直接前趋和一种直接后继。

例：一维数组、链表、栈、队列、串

2、非线性构造：

特性是：一种结点也许有多种直接前趋和直

接后继。

例：多维数组、广义表、树、图

数据存储构造有如下基本存储措施：

1、次序存储措施：

该措施是将逻辑上相邻结点存储在物理位

置上相邻存储单元里，结点间逻辑关系由存

储单元邻接关系来体现，一般通过数组来实

现。

2、链接存储措施：

该措施不规定逻辑上相邻结点在物理位置

上亦相邻，结点间逻辑关系是由附加指针字

段体现。通过指针类型来实现。

3、索引存储措施：

该措施一般是在存储结点信息同步，还建立

附加索引表，索引表中每一项称为索引项，

索引项一般形式是：关键字，地址。

4、散列存储措施:

该措施基本思想是根据结点关键字直接计

算出该结点存储地址，通过散列函数实现。

例：除余法散列函数、相乘取整法散列函数

♦:♦算法基本特性：

1、可行性(Effectiveness)：针对实际问题

而设计算法，执行后可以得到满意成果。

2、确定性(Definiteness)：算法中每一种

环节都必要有明确定义，不容许出现歧义

性。

3、有穷性(Finiteness)：算法必要在有限

时间内做完，即必要在执行有限个环节之后

终止。

。时间复杂度：该算法执行时间花费，它是

该算法所求解问题规模n函数。

♦:♦空间复杂度：该算法执行时所花费存储空

间，它也是问题规模n函数。

二线性表:

♦:♦线性表(LinearList)：是由n(n>=0)个数

据元素(结点)a],a»2>a»3,••••••,a,n构成有

限序列。对于非空线性表，有且仅有一种

开始结点al,它没有直接前趋；有且仅有

一种终端结点an,它没有直接后继；别的

结点有且仅有一种直接前趋结点和一种

直接后继结点。

♦:♦线性表存储构造：

1、次序存储(SequentialList)：将线性表

结点按逻辑次序依次存储在一组地址持续

存储单元里，用这种措施存储线性表称为次

序表。

2、链式存储(LinkedList)：逻辑上相邻结

点，物理上也相邻，存储单元可以是持续，

也可以是不持续，在存储每个结点值同步，

还存储指向其后继结点地址，用这种措施存

储线性表称为链表。

♦:♦常用运算有：

表初始化、求表长度、取表中第i个结点、

查找结点、插入新结点、删除结点。

♦:♦次序表和链表比较:

1、基于空间考虑：

A、次序表存储空间是静态分派，而链表存

储空间是动态分派。

B、次序表占存储空间必要是持续，而链表

占存储空间可以是持续，也可是不持续

C、次序表存储密度为1,而链表中每个结点,

除了数据域外，还要额外设置指针域，存储

密度不不小于1

2、基于时间考虑:

A、在链表中任何位置上进行插入和删除,

只需要修改指针，而次序表中平均将要移动

近二分之一结点。

B、次序表是随机存取构造，它存取时间为

0(1),而链表需从头结点顺着链扫描链表。

总之，当线性表长度变化不大，易于事

先确定其大小时，为了节省存储空间，宜采

用次序表作为存储构造；当线性表长度变化

较大，难以估计其存储规模时，以采用链表

作为存储构造为好。若线性表操作重要是进

行查找，很少做插入和删除操作时，采用次

序表做存储构造为宜；对于频繁进行插入和

lih

叫M除线性表，宜采用链表做存储构造。

例：有关线性表描述中，错误是（）

A、线性表是线性构造B、线性表次序

存储构造，必要占用一片持续存储单元

C、线性表是单链表D、线性表链式存

储构造，不必占用一片持续存储单元

用数组体现线性表长处是（）

A、便于插入和删除操作B、便

于随机存取

C、可以动态地分派存储空间D、不

需要占用一片持续存储空间

三、栈:

♦:♦栈（Stack）：是限制仅在表一端进行插入

和删除运算线性表，一般称插入、删除这

一端为栈顶（Top）,另一端称为栈底

（Bottom）o当表中没有元素时称为空栈。

是一种后进先出线性表，又称为LIFO表。

。栈基本运算有：

栈初始化、判栈空、判栈满、进栈、出栈

等

♦:♦栈存储：

次序存储、链式存储

例：若进栈输入序列是A、B、C、D、E,

并且在它们进栈过程中可以进行出栈操作,

则不也许出现出栈序列是()

A、EDCBAB、DECBAC、

DCEABD、ABCDE

四、队列:

。队列(Queue)：也是一种运算受限线性表,

它只容许在表一端进行插入，而在另一端

进行删除。容许删除一段称为队头

(Front),容许插入一段称为队尾(Rear)。

(类似于生活中购物排队)。是一种先进

先出线性表，又称为FIFO表。

。队列基本运算：

队列初始化、判队空、判队满、入队、出

队

♦:♦队列存储实现：

次序存储、链式存储

例：一种队列入队序列是L2,3,4,则

队列输出序列是()

A、4,3,2,1B、1,2,3,4

C、1,4,3,2D、3,2,4,1

五、是j

♦:♦串(String)：是零个或多种字符构成有限

序列。

串中所包括字符个数称为该串长度。

串中任意个持续字符构成子序列称为该

串子串，包括子串串对应地称为主串

注：空串是任意串子串，任意串是其自身

子串

串有串常量、串变量之分：

1、串常量在程序中只能被引用但不能变

化其值，即只能读不能写。

2、串变量其值是可以变化。

串基本运算：

求串长、串复制、串联接、串比较、字符

定位、

方、树(非线性构造):

♦:♦树(Tree)：是n(n>=0)个结点有限集T,

T(n=O)为空时称为空树，否则它满足如下

两个条件：

1、有且仅有一种特定称为根(Root)结点

2、别的结点可分为m(m>=0)个互不相交子

集Tl,T2,…….，Tm,其中每个子集

自身又是一棵树，并称其为根子树

(Subtree)。

♦:♦在树树形图体现中，结点一般是用园摄体

现，结点名字一般是写在圆圈旁边，有时

亦可写在圆圈内。

♦:♦度(Degree)：一种结点拥有子树数称为该

结点度。一棵树度是指该树中结点最大度

数。

♦叶子(Leaf)：度为零结点称为叶子或终端

结点

♦:♦分支结点(Node)：度不为零结点称为分支

结点。

♦:♦树中某个结点子树之根称为该结点孩子

(Child)结点或子结点，对应当结点称为

孩子结点双亲(Parents)结点或父结点。

♦同一种双亲孩子称为兄弟结点(Sibling)

♦:♦结点层数(Level)是从根起算，设根层数

为1,别的结点层数等于其双亲结点层数

加1.

。树中结点最大层数称为树高度(Height)

或深度(Depth).

♦:♦森林(Forest)：是m(m>=0)棵互不相交树

集合。删去一棵树根，就得到一种森林，

反之，加上一种结点作树根，森林就变为

一棵树。

。二叉树(BinaryTree)：是n(n>=0)个结点

有限集，它或者是空集(n=0),或者由一

种根结点及两棵互不相交、分别称作这个

根左子树和右子树二叉树构成O

二叉树中，每个结点最多只能有两棵子

树，并且有左右之分。

♦:♦二叉树五种基本形态：

例：具有3个结点二叉树有几种形态。

♦:♦满二叉树(FullBinaryTree)：一棵深度

为k且有2k-l个结点二叉树称为满二叉树

♦:♦完全二叉树(CompleteBinaryTree)：若

一棵二叉树至多只有最下面两层上结点

度数可以不不小于2,并且最下一层上结

点都集中在该层最左边若干位置上，则此

二叉树称为完全二叉树。

二叉树性质:

性质1:二叉树第i层上结点数目最多为

2i-1(i>=l)

性质2：深度为k二叉树至多有2k-l个结点

(k>=l)

性质3：在任意一棵二叉树中，若终端结点

个数为T度为2结点数为T则n0=n2+l

性质4：具有n个结点完全二叉树深度为

[lgn]+l(取下整)或[lg(n+l)取取上整)。

例：一棵二叉树结点数为18个，求它最小

高度

已知度为2结点数为15个，求叶子结点

数

二叉树遍历:

♦:♦遍历(Traversal)：是指沿着某条搜索路

线，依次对树中每个结点均做一次且仅做

一次访问。

前序遍历：（又称为先序遍历、先根遍历）

若二叉树为空，则执行空操作。否则:

1、访问根结点；

2、前序遍历左子树;

3、前序遍历右子树。

中序遍历：（又称为中根遍历）

若二叉树为空，则执行空操作。否则:

1、中序遍历左子树；

2、访问根结点；

3、中序遍历右子树。

后序遍历：（又称为后根遍历）

若二叉树为空，则执行空操作。否则:

1、后序遍历左子树;

2、后序遍历右子树;

3、访问根结点。

例：已知一棵二叉树中序遍历序列是:

FDGBACHE,其后序遍历序列是：FGDBHECA

求其前序遍历序列。

一棵二叉树前序遍历序列为ABDGCFK,中

序遍历序列为DGBAFCK,则结点后序遍历序

列是()

A、ACFKDBGB、GDBFKCAC、

KCFAGDBD、ABCDFKG

七、排序（Sort）：

♦:♦所谓排序，就是指整顿文献中记录，使之

按关键字递增（或递减）次序排列起来。

♦冒泡排序(BubbleSorting)：

通过看待排序序列从后向前或从前向后

（从下标较大元素开始），依次比较相邻元素

排序码，若发现逆序则互换，使排序码较大

元素逐渐从前部移向后部或较小元素逐渐

从后部移向前部（从下标较大单元移向下标

较小单元）。

♦:♦直接选用排序(SelectionSorting)：

扫描整个线性表，从中选出最小元素，将

它互换到表最前面；然后对剩余子表采用同

样措施，直到子表空为止。

♦:♦直接插入排序（InsertionSorting）：

每次将一种待排序记录，按其关键字大小

插入到前面已经排好序子文献中恰当位置,

直到所有记录插入完毕为止o

♦:♦迅速排序(QuickSorting)：任取待排序

序列中某个元素作为基准(一般取第一种

元素)，通过一趟排序，将待排元素分为

左右两个子序列，左子序列元素排序码均

不不小于或等于基准元素排序码，右子序

列排序码则不不不小于基准元素排序码9

然后分别对两个子序列继续进行排序，直

至整个序列有序。

多种内部排序措施比较

排时间复杂度

序空间复

最佳时平均时最坏时

措杂度

间间间

施

直

接

0(n)0(n2)0(n2)0(1)

插

入

直

接

0(n2)0(n2)0(n2)0(1)

选

用

冒0(n)0(n2)0(n2)0(1)

泡

快

O(nlgn)O(nlgn)0(n2)O(lgn)

速

堆O(nlgn)O(nlgn)O(nlgn)0(1)

例:对一种具有n个元素序列进行冒泡排序,

在最坏状况下，要进行互换次数是()

A、n(n+l)/2B、n(n-l)/2C、

n*n/2D、n(n+l)/2-l

对n个元素进行冒泡排序过程中，最佳状

况下时间复杂性为()

2

A、O(1)B>0(log2n)C>0(n)

D、0(n)

对n个元素进行迅速排序过程中，平均状

况下时间复杂性为()

A、0(1)B、0(lgn)C、

0(n2)D、O(nlgn)

查找(Searching)：

♦:♦所谓查找是指给定一种值K,在具有n个

结点表中找出关键字等于给定值K结点。

若找到，则查找成功，返回该结点信息或

该结点在表中位置；否则查找失败，返回

有关提醒信息。

。次序查找(SequentialSearch)基本思想

是：从表一端开始，次序扫描线性表，依

次将扫描到结点关键字和给定值K相比

较，若目前扫描到结点关键字与K相等，

则查找成功；若扫描结束后，仍未找到关

键字等于K结点，则查找失败。次序查找

即合用次序存储构造，又合用链式存储构

造。

查找成功平均查找长度为：(n为结点数

目)

(1+2+3+4+•••+n)/n=(n+l)/2

♦:♦二分查找(BinarySearch)又称折半查找,

它是一种效率较高查找措施，二分查找规

定线性表是有序表，即表中结点按关键字

有序，并且要用向量作为表存储构造。此

外，二分查找只合用次序存储构造，在链

式存储构造上无法实现二分查找。

查找成功时平均查找长度：(n为结点数

目)

n+1,八,

------lg(zn+l)-l

n

当n很大时,可用近似公式：1g(n+1)-1

体现

软件工程基本

~\基本概念:

。软件(Software)：软件是一种产品(逻辑

产品)，指是计算机中程序及其阐明程序

多种文档。“程序”是计算任务处理对象

和处理规则描述；“文档”是有关计算机

程序功能、设计、编制、使用文字或图形

资料。

♦:♦软件危机体现：

1、软件需求增长得不到满足

2、软件开发成本和进度无法控制

3、软件质量难以保证

4、软件不可维护或维护程度非常低

5、软件成本不停提高

6、软件开发生产效率提高赶不上硬件发

展和应用需求增长

♦:♦软件工程(SoftwareEngineering)：用工

程化措施、科学知识和技术原理来定义、

开发、维护软件一门学科。

♦:♦软件工程目的：

付出较低开发成本；到达规定软件功能；

获得很好软件性能；开发软件易于移植；

需要较低维护费用；能准时完毕开发任

务，及时交付使用；开发软件可靠性高。

♦:♦软件工程研究重要内容是软件开发技术

和软件开发管理两个方面。

♦:♦软件生存周期：是指一种软件从提出开发

规定开始直到该软件报废(停止运行)为

止整个时期。

。软件生存周期模型：是描述软件开发过程

中多种活动怎样执行模型。

♦:♦常用模型有：瀑布模型、增量模型、螺旋

模型、喷泉模型、变换模型和基于知识模

型

瀑布模型是将软件生存周期各个活动规定

为依线性次序连接若干阶段模型。重要波及

问题定义及可行性分析、项目开发筹划、需

求分析、概要设计、详细设计、编码、测试

和维护几种阶段。

例：下列描述中对的是（)

A、程序就是软件B、软件开发

不受计算机系统限制

C、软件既是逻辑实体,又是物理实体

D、软件是程序、数据与有关文

档集合

二、软件可行性研究与项目开发筹划:

♦:♦软件可行性研究目是用最小代价在尽量

短时间内确定该软件项目与否可以开发,

与否值得去开发。

♦:♦可行性研究任务：

A、技术可行性

B、经济可行性

C、社会可行性（法律可行性）

♦:♦可行性研究详细环节：

1、确定项目规模和目的

2、研究正在运行系统

3、建立新系统高层逻辑模型

4、导出和评价多种方案

5、推荐可行方案

6、编写可行性研究汇报

三、软件需求分析:

♦:♦需求分析是指开发人员要精确理解顾客

规定，进行细致调查分析，将顾客非形式

需求陈说转化为完整需求定义，再由需求

定义转换到对应形式功能规约（需求规格

阐明）过程。

♦:♦需求分析基本任务:

1、问题识别

A、功能需求

B、性能需求

C、环境需求

D、顾客界面需求

2、分析与综合，导出软件逻辑模型

3、编写文档（需求规格阐明书）

♦:♦需求分析措施:

1、构造化分析（StructuredAnalysis）：是

面向数据流进行需求分析措施。

SA措施运用图形等半形式化描述方式体

现需求，重要描述工具：

A、数据流图(DFD)：是SA措施中用于体现

系统逻辑模型一种工具，以图形方式描绘数

据在系统中流动和处理过程。

B、数据字典(DD)：用以定义数据流图中各

个成分详细含义，为系统分析、设计及维护

提供了有关元素一致定义和详细描述。

C、描述加工逻辑构造化语言、鉴定表、鉴

定树

2、IDEF措施(是ICAMDefinition缩写)：

是一种用于进行复杂系统分析和设计措

施，是在构造化分析和设计技术基本上提出

来。

3、面向对象分析措施(OOP)：

将客观世界事物抽象为对象，通过属性和

措施描述对象状态和行为，具有继承、封装

和多态性等特性。

例：软件开发构造化分析措施中，常用描述

软件功能需求工具是()

A、业务流程图、处理阐明B、

软件流程图、模块阐明

C、数据流程图、数据字典D、

系统流程图、程序编码

四、软件概要设计:

将软件需求转换为软件体现过程。

♦:♦软件概要设计基本任务：

1、设计软件系统构造

2、数据构造及数据库设计（概要设计、

逻辑设计、物理设计）：

3、编写概要设计文档:

4、评审：

♦:♦软件设计措施：

模块化：模块在程序中是数据阐明、可执

行语句等程序对象集合，或者是单独命名和

编址元素，如高档语言中过程、函数、子程

厅寺。

♦:♦模块独立性指每个模块只完毕系统规定

独立子功能，并且与其她模块联络至少且

接口简朴。其度量原则是：耦合性和内聚

性

♦:♦耦合性也称块间联络，指软件系统构造中

各模块间互相联络紧密程度一种度量。模

块之间联络越紧密，其耦合性就越强，模

块独立性则越差。

。内聚性也称块内联络，指模块功能强度度

量，即一种模块内部各个元素（语句之间、

程序段之间）彼此结合紧密程度度量。

♦:♦将软件系统划分模块时，尽量做到高内聚

低耦合。

例：为了使模块尽量独立，规定（）

A、模块内聚程序要尽量高，且各模块间耦

合程序要尽量强

B、模块内聚程序要尽量高，且各模块间耦

合程序要尽量弱

C、模块内聚程序要尽量低，且各模块间耦

合程序要尽量弱

D、模块内聚程序要尽量低，且各模块间耦

合程序要尽量强

五、软件详细设计:

重要确定每个模块详细执行过程

♦:♦软件详细设计基本任务:

1、为每个模块进行详细算法设计:

2、为模块内数据构造进行设计：

3、对数据库进行物理设计:

4、输入、输出格式设计

5、编写详细设计阐明书：

6、评审：

♦:♦详细设计常用三种工具：

图形（流程图、盒图、问题分析图PAD）、

表格（鉴定表）、

语言（过程设计语言,又称为伪码）

力、软件编码:

重要是将详细设计得到处理过程描述转

换为基于某种计算机语言程序

常用计算机语言：

Pascal、C、C++、Java等

七、软件测试:

软件测试代表了需求分析、设计、编码最

终复审。软件测试贯穿于软件开发全过程。

♦:♦软件测试目:

1、软件测试是为了尽量多地发现程序中

错误而执行程序过程。

2、一种好测试用例可以发现至今尚未发

现错误。

3、一种成功测试是发现了至今尚未发现

错误测试。

♦:♦软件测试原则：

1、测试用例应由输入数据和预期输出数

据两某些构成。

2、测试用例不仅选用合理输入数据，还

要选用不合理输入数据

3、除了检查程序与否做了它应当做事

4、应制定测试筹划并严格执行，排除随

意性

5、长期保留测试用例

6、对发现错误较多程序段，应进行更深

入测试

7、程序员防止测试自己程序

。软件测试措施：

1、静态测试：

是指被测试程序不在机器上运行，而是

采用人工检测和计算机辅助静态分析手段

对程序进行检测。

2、动态测试：是指通过运行程序发现错

误

A、黑盒测试法（功能测试）:

重要对软件接口进行测试，根据需求规格

阐明书，检查程序与否满足功能规定。常用

技术是等价类划分法、边界值分析法、错误

推测法、因果图法、综合方略法

B、白盒测试法（构造测试）：

重要测试程序内部构造和处理过程。常用

技术是语句覆盖、条件覆盖、途径覆盖、鉴

定覆盖等

。软件测试实行：

1、单元测试：

单元测试是对软件设计最小单位一一模

块（程序单元）进行对的性检查测试，重要针

对模块如下五个基本特性进行测试：

A、模块接口

B、局部数据构造：

C、重要执行途径：

D、错误处理测试：

E、边界条件：

2、集成测试：

集成测试是指在单元测试基本上，将所有

模块按照设计规定组装成一种完整系统进

行测试，故也称组装测试或联合测试。

重要措施有两种：

非渐增式测试：首先对每个模块分别进行

单元测试，然后再把所有模块按设计规定组

装在一起进行测试。

渐增式测试：逐一把未通过测试模块组装

到已通过测试模块上去，进行集成测试，每

加入一种新模块进行一次集成测试，反复此

过程直至程序组装完毕。

3、确认测试：

确认测试又称有效性测试，它任务是检查

软件功能与性能与否与需求规格阐明书中

确定指标相符合，因而需求规格阐明是确认

测试基本。

4、系统测试：

系统测试是通过测试确认软件作为整个

计算机系统一种元素，与计算机硬件、外设、

支撑软件、数据和人员等其她系统元素组合

在一起，在实际运行环境下对计算机系统进

行一系列集成测试和确认测试。

♦:♦程序调试:

调试是在进行了成功测试之后才开始工

作，目是确定错误原因和位置，并改正错

误，又称为纠错。

例：软件测试目是（）

A、证明软件对的性B、

找出软件系统中存在所有错误

C、尽量多地发现软件系统中错误D、

证明软件系统中存在错误

在软件测试措施中，黑箱测试法和白箱测

试法是常用措施，其中黑箱测试

法重要是

用于测试（）

A、构造合理性B、软件外部功能

C、程序对的性D、程序内部

逻辑

儿软件维护:

软件投入使用后进行阶段，是软件生存

周期中时间最长一种阶段，所花费精力和费

用也是最多一种阶段。重要是由于：隐含错

误要修改；新增功能要加入进去；环境变化

对程序进行变动等。

♦:♦软件维护内容有四类:

1、校正性维护：

为了识别和纠正错误，修改软件性能上缺

陷，其占整个维护工作21%

2、适应性维护：

为了使应用软件适应环境（硬件、系统软

件、数据）变化而修改软件过程称为适应性

维护，其占整个维护工作25%

3、完善性维护：

增长软件功能、增强软件性能、提高软件

运行效率而进行维护活动称为完善性维护，

其占整个维护工作50%

4、防止性维护：

为了提高软件可维护性和可靠性而对软

件进行修改称为防止性维护，其占整个维护

工作4%

例：软件维护是指（）

A、维护软件正常运行B、软件配置

更新

C、对软件改善、适应和完善D、软件开发

期一种阶段

软件生命周期中所花费用最多阶段是

()

A、详细设计B软件编

C、软件测试D、软件维护

数据库原理基本

\基本概念:

。数据处理：是指将数据转换成信息过程

♦:♦数据管理是指对数据组织、分类、编码、

存储、检索和维护提供操作手段

其经历了如下阶段：

1、人工管理

2、文献系统

3、数据库系统

4、分布式数据库系统阶段

5、向对象数据库系统阶段

♦:♦数据库(Database)：是指存储在计算机存

储设备上构造化有关数据集合，不仅波及

数据自身，还波及事物之间联络。

♦:♦数据库应用系统(DBAS)：是指系统开发人

员运用数据库系统资源开发出来，面向某

一类实际应用应用软件系统。

♦:♦数据库管理系统(DBMS)：对数据库建立、

使用和维护进行管理和配置软件系统。是数

据库系统关键

♦:♦数据库系统(DBS):由硬件系统、数据库集

合、数据库管理系统及有关软件、数据库

管理员和顾客构成。

♦:♦数据库系统特点：

实现数据共享、减少数据冗余

采用特定数据模型

具有较高数据独立性

统一数据控制功能

。实体：客观存在并且可以互相区别事物

称为实体。

。实体属性：实体所具有物性称为实体属

性。

♦:♦实体集：同类型实体集合称为实体集。

♦:♦实体型：属性集合体现一种实体类型，称

为实体型。

例：数据库管理系统能实现对数据库中数据

查询、插入、修改和删除，此类功能称为（）

A、数据定义功能B、数据管理功能

C、数据操纵功能D、数据控制功能

♦:♦联络：实体之间对应关系。

联络类型：

1、一对一联络：体现为主表中每一条记

录只与有关表中一条记录有关联。

例如：班级与班长，学