[IT认证]全国计算机等级考试二级公共基础知识.pptVIP

[IT认证]全国计算机等级考试二级公共基础知识;考点;计算机二级考试公共基础之

《数据结构与算法》;1．4算法与算法分析;

1、正确性：

(1)没有语法错误；

(2)对于几组输入数据能够得出满足要求的结果；

(3)对于精心选择的典型而苛刻的几组输入数据能够得到满足要求的结果。

(4)对于一切合法的输入数据都能产生满足要求的结果。

2、可读性：便于阅读、理解、调试、修改；

3、健壮性：对不合法的输入能作出正确的反映与处理；

4、高效性：执行时间短（时间复杂度）、

需求存储空间省（空间复杂度）;

1时间复杂度T（n）

以求解问题的基本操作的执行次数作为算法时间的度量。;数据结构中常用的时间复杂度频率计数有7个：

O(1)常数型O(n)线性型O(n2)平方型

O(n3)立方型O(2n)指数型

O(log2n)对数型O(nlog2n)二维型;2算法空间复杂度

用执行算法所需的内存空间的大小作为算法所需空间的度量。

设执行算法所需的内存空间是问题规模n的某个函数g(n),则算法空间复杂度记作：S（n）=O(g(n));(1)在计算机中，算法是指（）。

A.查询方法B.加工方法

C.解题方案的准确而完整的描述D.排序方法

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

A)算法的效率只与问题的规模有关，而与数据的存储结构无关

B)算法的时间复杂度是指执行算法所需要的计算工作量

C)数据的逻辑结构与存储结构是一一对应的

D)算法的时间复杂度与空间复杂度一定相关

(3)算法的有穷性是指（）。

A）算法程序的运行时间是有限的

B）算法程序所处理的数据量是有限的

C）算法程序的长度是有限的

D）算法只能被有限的用户使用;(4)算法的时间复杂度是指()

A)算法的执行时间

B)算法所处理的数据量

C)算法程序中的语句或指令条数

D)算法在执行过程中所需要的基本运算次数

(5)算法的空间复杂度是指()

A）算法在执行过程中所需要的计算机存储空间

B）算法所处理的数据量

C）算法程序中的语句或指令条数

D）算法在执行过程中所需要的临时工作??元数

(6)下列叙述中正确的是()

A）一个算法的空间复杂度大，则其时间复杂度也必定大

B）一个算法的空间复杂度大，则其时间复杂度必定小

C）一个算法的时间复杂度大，则其空间复杂度必定小

D）上述三种说法都不对;数据结构;1.逻辑结构

数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。

数据的逻辑结构包含：

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

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

例：

1.一年四季的数据结构

B=(D,R)

D={春，夏，秋，冬}

R={(春，夏),(夏，秋),(秋，冬)}

2.家庭成员的数据结构

B=(D,R)

D={父亲，儿子，女儿}

R={(父亲，儿子),(父亲，女儿)}

;常见的逻辑结构有：

线性结构、树形结构和图形结构。;2.存储结构（物理结构）

计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计算机的存储空间中，并且，各数据元素在计算机存储空间中的位置与它们的逻辑关系不一定是相同的，而且一般也不可能相同。

如：一年四季

家庭成员计算机存储空间怎样存放？

存储结构指数据结构在计算机存储空间中的具体实现。

常见的存储结构有：

顺序存储结构链式存储结构索引存储结构;3.数据的运算

检索

插入

删除

更新

排序;常见的数据结构;１．线性表（LinearList）;线性表的概念;用一组连续的内存单元依次存放线性表的数据元素。;线性表的顺序存储和实现;线性表的顺序存储和实现;由此可见

在顺序表中插入一个元素，平均要移动表的一半元素。

表长为n的顺序表，插入算法的时间复杂度为O（n）;删除算法时间复杂度分析;线性表的顺序存储和实现;线性表的链式存储和实现;一线性链表的概念

1线性链表;结点：数据元素及直接后继的存储位置（地址）组成一个数据元素的存储结构，称为一个结点；

结点的数据域：保存数据元素;

结点的指针域：