文档介绍：等级考试公共基础知识
目录
数据结构与算法
程序设计基础
软件工程基础
数据库设计基础
第一讲数据结构与算法
算法: 指解题方案的准确而完整的描述
算法的基本特征:
可行性
确定性:
是算法中的每一个步骤都必须是有明确定义的,不允许有模棱两可的解释,也不允许有多义性。
有穷性
是指算法必须能在有限的时间内做完,即算法必须能在执行有限个步骤之后终止。
拥有足够的情报
算法的复杂度
算法的复杂度主要包括时间复杂度和空间复杂度(填空)
算法的时间复杂度(选择)
--执行算法所需要的计算工作量,即所需基本运算的执行次数
算法的空间复杂度(选择)
--执行算法所需要的内存空间
数据结构
数据集合中各数据的逻辑关系,即逻辑结构
数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构
或者数据的存储结构是指数据的逻辑结构在计算机中的表示
数据结构的图形表示:如一年四季的数据结构
春
夏
秋
冬
线性结构(线性表)
1 有且只有一个根结点
2 每一个结点最多有一个前件,也最多有一个后件
如果一个非空的数据结构满足以上两点,则它为线性结构
不是线性结构的则称为非线性结构
考点需记:常见的线性结构:栈、队列、循环队列、带链队列、带链表
常见的非线性结构:二叉树
线性表的顺序存储结构
线性表中的所有元素所占的存储空间是连续的
线性表中的各数据元素在存储空间中按逻辑顺序依次存放的
顺序表的操作
优点:读取方便
缺点:插入、删除操作
时需要移动
1
2
3
4
5
6
7
栈
6
F
5
E
4
D
3
C
2
B
1
A
bottom
top
栈是限定在一端进行插入和删除的线性表
栈是按照“先进后出(FILO—First In Last out)”或者“后进先出”(LIFO)
队列
A
B
C
D
E
退队
入队
front
rear
队列也是线性表
队列也称为“先进先出”(FIFO)或者“后进后出”(LILO)