计算机导论复习.ppt

1 计算机导论 复习 考试范围 1 11 15 16章考试题型 简答 12选10 考试时带2B铅笔 橡皮 钢笔或圆珠笔 不准使用计算器 2 第一章全景图 1936年 英国科学家阿兰 图灵提出图灵机模型 把人在计算时所做的工作分解成简单的机械化动作交给机器去执行 经过足够的时间和有限次机械步骤求得解答 理论上可以计算任何可计算函数 1946年2月由宾夕法尼亚大学研制成功的ENIAC是第一台电子数字计算机 3 美籍匈牙利数学家冯 诺依曼提出现代计算机基本结构 冯 诺依曼计算机 计算机应由运算器 控制器 存储器 输入设备和输出设备五大部件组成 应采用二进制简化机器的电路设计 采用 存储程序 以便计算机能保存指令和数据以及能够自动依次执行指令 4 第一代计算机 电子管 第二代计算机 晶体管 第三代计算机 集成电路 第四代计算机 大规模 超大集成电路 计算硬件发展的新趋势 并行计算 连网 5 第一代软件 机器语言 汇编语言 第二代软件 高级语言 第三代软件 操作系统 第四代软件 结构化程序设计方法 UNIX C DOS 鼠标 图形界面 第五代软件 面向对象程序设计 Windows Java WWW 6 第二章二进制数值和记数系统 数制 按进位原则进行计数 逢R进一 基数 数制中所需的数字字符个数 R进制的基数 R位权 是一个与数字位置有关的常数 位权 Rn其中n取值 以小数点为界 向左0 1 2 3 向右 1 2 3 例 275 8 10 2 102 7 101 5 100 8 10 1 7 8 9 位权相加法 各位数码乘位权 再相加 例 1011 1 2 1 23 0 22 1 21 1 20 1 2 1 8 0 2 1 0 5 11 5 10 整数部分从右向左 小数部分从左向右 每3位二进制一组 变为1位八进制 不足3位时分别在最左端和最右端补0凑够3位 例 1100101001011 1101 2 14513 64 8 二进制十六进制 整数部分从右向左 小数部分从左向右 每4位二进制一组 变为1位十六进制 不足4位时分别在最左端和最右端补0凑够4位 例 11010111101 1010001 2 6BD A2 16 10 位 bit 计算机存储数据的最小单位 0 1 字节 Byte 处理数据的基本单位 8bit Byte 11 第三章数据表示法 模拟信号和数字信号无符号数和有符号数符号位 二进制数的最高位表示 正 负 0为正 1为负 12 原码 正号为0 负号为1 数值部分为二进制绝对值 补码 正数的补码和原码相同 负数的补码是将其原码除符号位外各位取反 末位加1 5的原码 补码都是00000101 为了运算方便 机器数采用原码 补码表示 13 小数点位置固定的数称为定点数 定点整数 小数点固定在数值部分最右端 定点小数 小数点固定在数值部分最左端 小数点位置不固定的数称为浮点数 分为阶码 指数 和尾数两部分 例 将十进制数 55以浮点数格式存放 55 10 110111 2 0 110111 26 14 西文字符的编码 ASCII码 AmericanStandardCodeforInformationInterchange 128个常用字符 用7位二进制编码 占一个字节 最高位0 其中 控制字符 0 32 127 普通字符 94个 15 和汉字有关的编码 汉字输入码 操作人员通过键盘输入的汉字编码 2 汉字国标码 GB2312 80 每个汉字占两个字节的编码 所有汉字分区 每个区94个汉字 区号和位号各加32构成国标码 4 汉字字形码 点阵 汉字字形点阵的代码 16 差错校验码 奇偶校验码 为一个字节补充1bit 校验位 设置校验位的值为0或1 使字节中的8bit和该校验位含有1值的个数为奇数 奇校验 或偶数 偶校验 17 关键字编码 关键字编码是用单个字符代替常用单词或前后缀 如 the and that 文本压缩方法 行程长度编码 在一些数据流中 某个字符可能连续地反复出现 因此 重复字符序列被替换为 标志字符 该字符 出现次数 18 文本压缩方法 哈夫曼编码 1 计算信源符号出现的概率 p 0 125 a 0 25 s 0 375 g 0 125 e 0 1252 概率最小的两个符号概率相加合成一个概率 3 将合成概率看成一个新组合符号概率 重复上述做法 直到最后只剩下两个符号概率为止 4 反过来逐步向前编码 每一步有两个分支各赋予一个二进制码 可以对概率大的编码为1 19 采样频率 每秒钟的采样次数 量化位数 采样精度 存放采样点振幅值的二进制位数 通常量化位数有8位 16位等 音频信息的数字化 捕捉声音时用固定的时间间隔对声波进行采样 离散化处理 例如44 1kHz 采样 将每个采样点的振幅值转换为二进制数值 例如用8位或16位二进制表示 量化 把量化后的信号数据编成一个二进制码组输出 编码 20 图像信息的数字化 用 m行 n列 个像素点来离散化一幅图像 例如1024 768分辨率 采样 将每个像素点的三基色强度转换为二进制值 例如用8位 16位 24位 32位二进制表示 量化 数字化图像的数据量很大 所以需要采用编码技术来压缩信息 减少数据量 编码 分辨率 图像中的行数和列数 每个行与列的交点就是一个像素 例如1024 768 颜色深度 每个像素点颜色值的存储位数 21 视频信息的数字化 连续动态的视频由多帧静态图像组成 采样频率 每秒捕捉的画面帧数 采样精度 经采样后每帧所包含的颜色位 色彩值 如8位 32位 必须对海量的视频数据及其伴音进行压缩和编码 22 23 第四章门和电路 门电路 接受一个或多个输入信号 生成一个输出信号 每种类型的门执行一个特殊的逻辑函数 非门 与门 或门 异或门 与非门 或非门等 24 非门 与门 25 或门 异或门 两个输入相同时 输出是0 否则输出1 26 与非门 让与门的结果再经过一个非门 或非门 让或门的结果再经过一个非门 27 用晶体管构造门 28 29 半加器halfadder 计算两个数位的和并生成正确进位的电路 和 A B进位 AB 30 全加器fulladder 计算两个数位的和并考虑进位输入的电路 和 A B C进位输出 AB C A B 31 加法器adder 8bit相加需要复制8次全加器电路 一个bit位的进位输出将作为下一个bit位的进位输入 最右边bit的进位输入是0 最左边bit的进位输出被舍弃 溢出 4位加法器例子 32 S R锁存器 S Rlatch S 0 R 1时 X 1 R 0 S 1时 X 0 S 1 R 1时 X保持不变 S和R不能同时为0 33 第五章计算部件 内存单元 存储信息的单位 字节 内存中有大量的内存单元 内存单元的地址 每个内存单元都有唯一的地址 34 CPU的主要性能指标 主频 CPU内核运算电路的运行频率 CPU外频 CPU总线频率 外频提高则与内存交换数据的速度越快 主频 外频 倍频系数 数据总线宽度 即字长 如32位 64位 CPU 算术和逻辑运算单元ALU 控制器和寄存器组 CPU可执行的一组指令称为指令集 精简指令集和复杂指令集 35 运算器ALU 执行算术 逻辑运算寄存器组 存源 中间数据标志寄存器 保存标志信息 控制器PC 存放下一条指令的地址IR 存放正执行指令的内容译码器 区分指令执行的步骤产生控制信号 向其它各部件发出控制信号 保证各部件协调一致地工作 36 总线按所传输的内容分 有 数据总线 传送数据 如 奔腾 CPU有32条数据线 表示每次可和内存并行交换32位二进制数 地址总线 用于传送CPU发出的地址信息 即指明数据总线上的数据的源地址或目的地址 地址总线的宽度决定了CPU的最大寻址能力 即所允许的最大内存容量 控制总线 传送控制信号 37 指令执行周期 指令格式 38 内存 直接与CPU交换信息的存储设备 用来存放计算机运行期间所需的信息 如 指令 程序 文档 外存 内存的延伸 长期存放暂时不用的数据 如系统文件 应用程序 用户文档等 39 非vonNeumann结构 不采用 线性的读取 执行周期 40 流水线技术 Pipeline 指令1指令2指令3指令4 将每条指令分解成多个阶段 几条指令的不同阶段重叠运行 使控制器 运算器 存储器等同时工作 如Pentium的6级流水线结构 41 计算机问题求解三阶段 不断反复的过程算法开发 得到问题的通用解决方案分析问题 提出并测试算法算法实现 得到计算机可运行的程序编码和测试程序维护 在实践中检验实际运转 修改维护程序 第六章问题求解和算法设计 42 两种程序设计方法 自顶向下方法 Top downMethodology 程序设计模式 数据结构 算法 在软件功能说明书中 动词是重点 面向对象程序设计 ObjectOrientedProgramming 程序设计模式 对象 消息 在软件功能说明书中 名词是重点 43 自顶向下程序设计方法 自顶向下 逐步求精 逐层分解复杂任务 把任务细节推延到下层模块中实现 模块化 每个模块完成特定的 相对简单的功能 流程控制结构化 程序通过顺序 分支 循环三种基本控制结构来实现 44 面向对象的程序设计方法 面向对象 类 对象 继承 消息 通信 对一组具有相同属性和行为的对象的抽象描述 对象是类的实例 具有属性和方法 子类可以继承父类的属性和方法 实现代码重用 45 继承inheritance 子类得到父类的全部属性和方法 还可以扩充和覆盖父类的成员 多态polymorphism 也称重载 不同子类中同一方法名可定义成不同代码 所以它们在收到同一消息时做出的响应行为也不同 封装encapsulation 将属性和行为隐藏起来 外部通过特定的接口访问对象成员 好处是保护成员 修改程序时只涉及类的内部 46 第七章低级程序设计语言 机器语言 由二进制代码组成 能被计算机直接理解和执行 但编程困难 可移植性差 把机器指令中的操作码和操作数用英文助记符和符号地址来表示 称为汇编语言 依赖于机器 可移植性同样较差 47 第八章高级程序设计语言 编译器对整个源程序经过编译处理 产生一个与源程序等价的目标程序 通过连接程序将目标程序和有关的程序库组合成一个完整的可执行程序 执行速度快 修改源程序后都必须重新编译 同一种高级语言在不同CPU平台上需要不同的编译器 48 解释程序对源程序进行逐句分析 若没有错误 将该语句翻译成一个或多个机器语言指令 然后立即执行这些指令 若解释时发现错误 则立即停止 报错并提醒用户更正代码 解释方式不生成目标程序 执行速度慢 49 Java源程序先经过编译生成Java字节码 然后由JVM JavaVirtualMachine Java虚拟机 解释执行 Java字节码相当于是 标准的机器语言 速度快 唯一 只要有相应的JVM解释器 Java字节码可在任何环境下运行 如 PC UNIX工作站 Macintosh等 在浏览器中运行的Java字节码为JavaApplet Java小程序 50 程序设计时的控制结构 顺序 分支 循环结构 顺序结构 按照语句出现的先后顺序依次执行 分支结构 根据给定条件判断 决定程序执行的顺序 循环结构 重复多次执行语句集合 51 第九章抽象数据类型和算法 52 数组 Array 按 行优先 或 列优先 方式顺序存储数组元素 插入删除元素时需移动大量元素 在一个有n个元素的数组A中的第i个元素之前插入一个元素x时 将第i个元素及其后的元素后移 for j n j i j A j 1 A j A i x n 在一个有n个元素的数组A中删除第i个元素时 将第i个元素之后的元素前移 for j i j n j A j A j 1 n 53 链式存储时以节点为单位 一个节点由数据项和指针组成 指针中存放该节点的后续节点所对应的内存地址 节点数无限制 插入删除元素时方便 把节点s插入到节点p之后时的操作 首先从链首head开始 顺序查找到节点p 然后s next p next p next s 删除节点p时的操作 首先从链首head开始 顺序查找到节点q和它的后继节点p 该删除的节点 然后q next p next 54 线性表是由n n 0 个数据元素a1 a2 an组成的有限序列 栈 Stack 只允许在表的一端进行插入和删除的线性表 队列 Queue 限制在表的一端插入 在表的另一端删除 数组 Array 是同类型数据元素构成的集合 通过数组名和下标访问数组元素 按行优先顺序存储 55 折半查找 要求线性表事先按关键字大小排好顺序并且线性表采用顺序存储 即数组 方式 先取表的中间位置的结点关键字与所给定的关键字进行比较 如果相等 则查找成功 如果给定值比该结点的关键字大 则所找结点在表的后半部分 否则所找结点在表的前半部分 然后再把选定的部分表的中间结点的关键字与给定关键字进行比较 如此反复 直到查找成功或者查找失败为止 选择排序 冒泡排序 快速排序 56 二叉排序树 二叉树中的每个节点的关键字均大于其左子树上所有节点的关键字 且小于等于其右子树上所有节点的关键字 例如 给出K 10 18 3 8 19 2 7 8 构造二叉排序树 第1个数就是树根 树的形状由数插入树的顺序决定 57 第十章操作系统 操作系统 计算机硬件和软件资源的管理者 58 操作系统构成 进程管理 内存管理 文件管理 输入输出系统管理 作业管理 操作系统主要类别 59 分时操作系统 分时 的含义 时间片轮转 轮流占用CPU人机交互性好 程序的运行由用户自己操作 共享主机 多个用户同时使用同一台计算机 对每个用户而言好象独占主机 60 内存分配方案 连续内存分配 在可用内存中找到足够大的一块连续内存 如100KB 切出要求长度的内存 如70KB 分配 剩余内存 如30KB 作为新空闲区留待以后分配或合并 61 虚拟内存 当一个用户程序要调入内存运行时 不是将该程序的所有页面都装入内存 而是只装入部分的页面 就可启动程序运行 在运行的过程中 如果发现要运行的程序或要访问数据不在内存 则向系统发出缺页中断请求 系统在处理这个中断时 将磁盘上相应的页面调入内存 使得该程序能够继续运行 62 进程是程序对某个数据集的一次执行过程 程序是静态概念 建立与删除 进程是动态概念 一个进程由三部分组成 进程控制块PCB 程序段 数据集 63 CPU调度 把CPU分配给某个就绪进程去运行 不可抢占式 当前运行进程完成或阻塞或时间片到时 才再分配处理机 抢占式 将正运行进程强行撤下 处理机分配给其它进程 例如当有一个优先权更高的进程进入就绪队列时 先到先服务 FCFS First Come First Served 最短作业优先 SJF Shortest Job First 轮转 RR Round Robin 时间片轮转 64 第十一章文件系统和目录 文件 存储在外存上具有标识名的一组相关字符流或记录的集合 透明存放和按名存取文件的命名 文件名 扩展名 65 OS将每个目录看成一张表 表中是该目录下所有文件的信息 其实目录本身也是一个文件 创建文件时 先在磁盘上为新文件分配一个空闲块 然后在目录表中添加一新条目 66 访问方式 顺序访问