公共基础知识

计算机二级 基础知识 计算机 考试 数据结构 算法

数据结构与算法

算法（步骤）

定义：是指解决方案的准确而完整的描述。 算法≠程序

特征

可行性

确定性

有穷性：有限步骤，有限时间内完成。

拥有足够情报

算法复杂度（衡量算法的优劣）

时间复杂度：即所需要计算的工作量，≠具体时间，即不受很多细节的影响

空间复杂度：即内存空间

采用压缩技术来降低空间复杂度

输入

程序本身

额外空间

数据结构

定义：指相互有关联的数据元素的集合。

包含两要素

数据：集合

结构：关系

表示

数学形式定义：二元组

图形

分类

逻辑结构：反映数据元素之间的逻辑关系（即前后件关系）

线性结构 1.有且只有一个根节点 2.每个节点最多只有一个前件， 最多只有一个后件

线性表 最常用也是最简单的一种数据结构

顺序存储（顺序表）

特征

存储空间连续

按逻辑顺序依次存放

可以随机访问

不便于插入和删除元素

特殊情况

栈：在限定的一端插入和删除

原则：先进后出

特点

运算

队列：是指允许在一端进行插入在另一端进行删除

原则：先进先出

特点

循环队列

链接存储（线性链表，链表，单链表）

特点

双向链表

循环链表

非空线性表

非线性结构

树：是n个元素的有限集合

父节点

子节点

根节点

叶子结点

节点的度

树的度

树的深度

子树

二叉树：是一个有限节点的集合，该集合或者为空，或者有一个根节点及其两课不相交的左右二叉树所组成。

特点

状态

特殊二叉树

性质

遍历

存储结构（物理结构）：逻辑结构在计算机中的存放方式。

查找技术

顺序查找

二分查找

排序

交换类

插入类

选择类

与问题规模有关也与输入有关

用基本运算次数来度量

根节点：无前件 终端节点（叶子节点）：无后件 内部节点：除以上两种外的节点