全国计算机二级基础知识
一.算法与数据结构
算法四个基本特征
1.可行性
2.确定性(明确的定义)
3.有穷性(有限的时间)
4.拥有足够的情报
时空复杂度
1.时间复杂度:需要计算工作量。
2.空间复杂度:执行过程中需要存储空间。
数据结构的基本概念:数据元素之间关系的元素集合,提高数据处理的效率。
数据结构的三方面:1.逻辑结构{线性结构{线性表,栈,队列},非线性结构{树,图}}
2.数据的存储结构:{顺序存储,连式存储}3.数据运算:检索,排序,插入,删除,修改。
数据逻辑结构:反映元素之间逻辑关系的数据及结构。
B=(D,R)B:数据结构 D:数据元素集合 R:数据之间前后件关系。
图形表示
数据元素:用中间标有元素值方框表示称为节点。
逻辑关系:用有向线段从前件指向后件,没有前件的是根节点,没有后件的是终端节点(叶子节
点)
B=(D,R) D={di|1<=i<=7}={d1,d2,d3,d4,d5,d6,d7} R=[(d1,d3)(d1,d7)(d2,d4)(d3,d6)
(d4,d5)]
数据流图中带有箭头的线段表示的是数据流
数据存储结构 逻辑存储结构与数据存储结构不一定相同。一种数据结构可以表示多种存
储结构。不同的存储结构,处理效率不同。
数据的存储结构有顺序,链接,索引等。
线性结构(线性表)节点个数 n 称为线性表长度。N=0 表示空表。
常见线性表:栈,队列,循环队列。
空的数据结构可能属于线性结构,也可能属于非线性结构。
顺序存储结构的特点:
线性表中所有元素所占存储空间是连续的,各数据元素在存储空间中按逻辑顺序依次存放。
ADR(a1)=ADR(a1)+(i-1)k,ADR(a1)为第一个元素地址,k 代表每个元素所占的字
节数。
数据的逻辑结构是指反映数据元素之间的逻辑关系的数据结构。
数据的逻辑结构有两个要素:1.数据元素的集合,记作 D 2 .各元素的前后件关系记作 R
数据结构 B=(D,R)
线性表的基本概念:线性表是由一组数据构成,数据元素的位置只取决于自己的序号,元素之间的
相对位置是线性的。
在复杂的线性表中,由若干数据元素组成的数据元素称为记录,由多个记录构成的线性表称为文件。
1