计算机软件技术——复习.ppt

计算机软件技术基础 复习 * 第二章 常用数据结构及其运算 l算法分析算法复杂度 l算法、数据结构（逻辑结构、存储结构） * 例题 下面程序段的时间复杂度为（ ）。 for( int i=0 ; im ; i+ ) for( int j=0 ; jn ; j+) aij=i*j ; A.O(m2) B.O(n2) C.O(m+n) D.O(m*n) * 线性表的顺序存储结构 l1. 顺序存储结构 l2. 顺序存储结构的插入运算 l3. 顺序存储结构的删除运算 * 线性表的链式存储结构 l链式存储结构 l基本运算 1、前插 2、后插 3、删除 * 特殊线性表栈和队 l栈的定义和基本操作 l判断栈空、队满的条件 l有三个元素的进栈序列 是1，2，3，举出此三个 元素可能的出栈序列， 并写出相应的进栈和出 栈操作序列如图所示(假 设以I和O表示进栈和出 栈操作)。 * 队队 l l 队队的定义 l访问算法 l顺序队 1、基本操作： 出队：front 入队：rear 2、循环队列的结构及判断队空、队满的条件 3、基本运算 * 循环队列 队列为空 frontrear front= rear+1 队列已满 * 数组 l数组的两种顺序存储方式 l l 顺序存储地址公式顺序存储地址公式 Loc(aij)= Loc(a11)+ (i-1)* n +(j-1) 按行优先储存 按列优先储存 Loc(aij)= Loc(a11)+ (j-1)* m +(i-1) * 数 组 J有一个NN的下三角矩阵A，若采用行优先进行顺序 存储，每个元素占用4个字节，则 Aij(1iN,1ji)元素的相对字节地址（相对 首元素地址而言）为 。 A.（i（i+1）/2+j-1）4 B.（ii/2+j）4 C.（i（i-1）/2+j-1）4 D.（i（i-1）/2+j）4 A= a11 0 0 a21 a22 0 an1 an2 ann C 非线性数据结构 树与二叉树 l树及其基本概念 l二叉树的定义 l三种特殊形态的二叉树 l满二叉树、完全二叉树的编号 * 二叉树的基本性质 l性质1：二叉树的第 i 层最多有 2i-1 个结点。 (i 1) l性质2：深度为k的二叉树最多有 个结点。 l性质3：对一棵二叉树，如果叶子结点数为n0， 度为2的结点数为n2，则n0=n2+1。 设一棵完全二叉树有1000个结点，试问 1)有多少个叶子结点， 2)有多少个度为2的结点； 3)有多少个结点只有非空左子树。 二叉树的基本性质 l二叉树的遍历 先序、中序、后序 l二叉排序树 性质、生成 l 哈夫曼树 带权路径长度、哈夫曼树的生成 * 有如图所示的一棵二叉树，则该二叉树 的先序、中序、后序遍历序列为 。 CBDAEGF ABCDEFG CDBGFEA 先序 中序 后序 二叉树的遍历 给定序列52，8，5，16，78，19，画出产生一棵二叉 排序树的过程。 * * u 字符： S、C、T、A、空格 u 权值： 6，2， 4，5， 3 以字符权值作为叶子结点的权值构造一棵哈夫曼 树，并求出其带权路径长度。 试对电文“1000100”进行翻译 20 9 4 5 11 5 6 2 3 0 1 0 101 01 T A C S 答案：CAT 二叉树的应用 * 图 顶点的度 l 在无向图中，顶点的度就是和该顶点相关联 的边的数目。 l 在有向图中：顶点的度= 入度 + 出度 l两种最常用的表示方法：邻接矩阵 邻接表 图的存储结构 查 找 l评价查找算法好坏的依据 平均查找长度 l顺序查找 l对分查找 l分块查找 l二叉排序树查找 * l已知长度为6的线性表： l(45，24，53，13，30，85) 1）按顺序依次插入，二叉排序树； 2）试分别求出在等概率情况下二叉排序树查找 成功的平均查找长度。 * 树的平均查找长度为 ASL(a)= 1/6 1+2+2+3+3+3 = 14/6 * 排 序 l 选择排序 l 插入排序 l 冒泡排序 l 快速排序 初始状态初始状态46 46747453531414262638388686656527273434 第一趟第一趟46 46535314142626383874746565272734348686 第二趟第二趟46 46141426263838535365652727343474748686 第三趟第三趟14 14262638384646535327273434656574748686 第四趟第四趟14 14262638384646272734345353656574748686 第五趟第五趟14 14262638382727343446465353656574748686 第六趟第六趟14 14262627273434383846465353656574748686 第七趟第七趟14 14262627273434383846465353656574748686 冒泡 第3章 操 作 系 统 l操作系统的类型：特点 多道批处理系统、分时系统、实时系统 * 存储管理存储管理 l存储管理的功能 内存分配 地址转换：静、动态地址重定位的区别 存储保护 内存扩充 * 实存储管理实存储管理 l l 分区分配分区分配 固定分区 可变分区： 寻找空闲区的算法 最先、最佳、最差适应算法 * 虚拟存储管理 l分页存储管理 地址转换 * 例 页号01234 页架 号 64320 状态11110 每页长为32字，现有逻辑地址为：68， 180，若能翻译成相应的物理地址 * 处理器管理处理器管理 l l 进程进程调度：调度算法 进程的状态及转换 * 进程的同步与互斥 l进程的同步 l进程互斥 l临界区 lP-V操作 * * * 双向制约 l 设两个信号量S1和S2，且赋予它们的初值 S1为1，S2为0， L1:进程A L2: 进程B P（S1） P（S2） 把信息送入缓冲区 从缓冲区取走信息 V（S2） V（S1） GOTOL1 GOTOL2 * 死锁 l死锁的定义 l必要条件 l死锁的预防 * 设备管理设备管理 l设备分类 按使用方法：绝对设备号、相对设备号 l缓冲技术 l假脱机系统的目的 * 1）循环测试I/O方式: I/O测试指令不断对该设备进行 测试，直到设备空闲为止。 2）程序中断I/O方式: 中断技术及中断处理机构的引入 ，使得CPU与外围设备的工作有了相对独立性。 3）通道I/O方式: 引入通道技术，使主机不再干预I/O 操作。 I/O控制方式的改进 * * 文件管理 文件目录 * 实体间的联系 两个实体型之间的联系可以分为三类： 一对一联系 一对多联系 多对多联系 * 概念模型 表示方法：实体联系方法 ER图：提供了表示实体型、属性和联系的方法。 * 数据模型数据模型 层次模型 网状模