软技术基础程复习PPT课件.ppt

软件技术基础总复习 串讲 1 数据的逻辑结构 数据的操作 遍历 查找 删除 插入 数据结构 操作系统 软件工程 软件技术基础 算法与数据结构概述 操作系统的五大管理功能 瀑布模型 2 第一章知识点 计算机软件的概念程序 数据和文档的集合软件 程序 数据 文档软件分类 系统软件和应用软件操作系统 不需要其他软件支持 语言处理 服务和数据库管理 软件设计方法面向数据流面向数据结构面向对象 3 第二章知识点 数据 数据元素 数据对象 数据项关系数据元素是数据的基本单位数据项是数据的最小单位数据对象是相同属性的数据元素的集合数据结构 DS D R 数据结构包括数据的逻辑结构和物理结构逻辑结构 线性结构和非线性结构 物理结构 顺序存储和链式存储 算法的特征有穷性 确切性 输入 输出 可行性算法的时间复杂度问题规模n的函数 频度最大的语句来度量 4 算法 程序和数据结构算法是一系列解决问题的指令集合程序是指一组指示计算机每一步动作的指令 通常用某种程序设计语言编写 运行于某种目标体系结构上 数据结构是指同一数据对象中各数据元素间存在的一种或几种关系 程序 算法 数据结构 第二章知识点 5 分析算法的时间复杂度i 1 while i n i i 2 x为循环次数 6 第三章知识点 线性表 最多有一个直接前驱和一个直接后继 即一对一 线性特点 同一性 有穷性 有序性 线性表的存储 顺序表 物理地址连续 链表 物理地址不一定连续 单链表 带头结点和不带头结点堆栈 LIFO 操作在一端 作用队列 FIFO 操作在两端 作用 7 顺序表 内存中地址连续 长度不可变更 支持随机查找 可以在O 1 内查找元素适用于需要大量访问元素的 而少量增添 删除元素的程序链表 内存中地址可能不连续 长度可以实时变化 不支持随机查找 查找元素时间复杂度O n 适用于需要进行大量增添 删除元素操作 而对访问元素无要求的程序 顺序表与链表的优缺点 何时选用 8 voidlnsert LinkedList L intx inti i i 1 LinkedList p L intj 0 while p NULL 不带头结点的链表的第i个元素前插入一个元素x ai 1 ai ai 1 x q p 9 intdelete LinkList h inti i 1 LinkList p h q intj 0 while p NULL 删除第i个结点的算法 ai 1 ai ai 1 p free q q 10 空链表 h next NULL堆栈的操作 IIOOOIOI IOOIOIIO IIIOOIOO IOIIOIOO 操作规则 先进后出 输出的数目小于等于输入的数目循环队列 操作方便 避免浪费存储单元队满 rear 1 M front 队空 rear front 入队 A rear x rear rear 1 M 12 第四章知识点 树 前驱唯一 后继不唯一 空树 n 0 术语 结点的度 叶子结点 双亲 兄弟 孩子 结点的层数 树的深度 树的度 有序树 无序树 二叉树 树的度不大于2 有序树 子树分左右 树与二叉树的区别与联系 都有仅有一个根 根无前驱 叶子无后继 二叉树的每个结点的度小于等于2 二叉树的子树有左右之分 二叉树五种基本形态 0 D DL DR DLR满二叉树 有2h 1个结点 h为树的度完全二叉树 结点都在该层最左边 13 第i层上至多有2i 1 i 1 个结点 叶子结点数n0 度2结点数n2 满足n0 n2 1二叉树的遍历 DLRLDRLRDHuffman树 最优树 取最小和次小概率合并 从根到叶子编码 14 练习题 已知 LRD DEACB LDR DEABC 求DLR遍历 并画出二叉树 DLR BAEDC 15 1 00 0 19 0 21 0 40 0 60 0 28 0 17 0 11 0 05 0 02 0 03 0 06 0 07 0 10 0 32 0 1 0 0 0 0 0 0 1 1 1 1 1 1 b c f d a h e 0 07 0 19 0 02 0 06 0 32 0 03 0 21 0 10 abcdefgh g 1010001000010011110001011011 0 32 0 21 0 19 0 07 0 06 0 03 0 02 0 10 16 第五章知识点 任意两个结点都可能相关 即邻接关系任意 概念 G V E 无向图 有向图 完全图无向安全图 n n 1 2有向完全图 n n 1 顶点的度 入度和出度边的权 网图 路径 路径长度 回路 子图 连通图 连通分量 17 邻接矩阵 判定顶点的度 无向 有向图 邻接表 表头结点 表结点 图的遍历 DFS BFS 图 矩阵 邻接表 最小生成树 网图的权值总和最小 Prim 扩充顶点 Kruskal 扩充边 拓扑排序 18 第八章知识点 操作系统 定义 五大功能 四个特征进程与程序 区别 定义 三个状态 状态转换死锁 定义 原因 必要