计算机考研

计算机考研833组成原理和数据结构思维逻辑框图

计算机专业

• 组成原理
  • 第一章 计算机系统概述
    • 1.1计算机的发展历程
      • 1.1.1 计算机硬件的发展
        • 1.计算机的发展历程
          • 第一代计算机
            • 电子管
            • 1946~1957年
          • 第二代计算机
            • 晶体管
            • 1958~1964年
          • 第三代计算机
            • 中小规模集成电路
            • 1965~1971年
          • 第四代计算机
            • 超大规模集成电路
            • 1972~至今
          • 第五代计算机
            • 智能计算机
          • 第六代计算机
            • 生物计算机与量子计算机
        • 2.计算机的分类
          • 按用途
            • 专用计算机
            • 通用计算机
              • 巨型机
              • 大型机
              • 中型机
              • 小型机
              • 微型机
              • 单片机
          • 按指令和数据流
            • 单指令流单数据流SISD
              • 传统的冯诺依曼结构
            • 单指令流多数据流SIMD
              • 阵列处理器和向量处理器系统
            • 多指令流单数据流MISD
              • 实际上不存在
            • 多指令流多数据流MIMD
              • 多处理器和多计算机系统
        • 3.计算机硬件的更新换代
          • 摩尔定律
          • 半导体存储器的发展
          • 微处理器的发展
      • 1.1.2 计算机软件的发展
        • 计算机软件
          • 程序
          • 文档
        • 操作系统
          • DOS
          • UNIX
          • LINUX
          • WINDOWS
    • 1.2 计算机系统层次结构
      • 1.2.1 计算机系统的基本组成
        • 计算机系统
          • 硬件系统
            • CPU
            • 存储器
            • 外部设备
          • 软件系统
            • 计算机运行程序和相应的文档
      • 1.2.2 计算机硬件的基本组成
        • 硬件
          • 存储器
            • 主存（内存，内存储器）
              • CPU直接访问
                • 主存储器有许多存储单元组成，每个存储单元包括多个存储元，每个存储元存储一位二进制代码。存储单元可存储一串二进制代码，称这串代码为存储字，这串代码的位数成为存储字长
                • 许多存储单元共同构成存储体
                  • 地址寄存器
                    • 存放访存地址
                  • 数据寄存器
                    • 暂存从主存中读或写的信息
            • 辅助存储器（辅存，外存储器）
              • 必须调入主存，才能被CPU访问
          • 运算器
            • 包括若干通用寄存器
              • 用于暂存操作数和中间结果
                • 累加器ACC
                • 乘商寄存器MQ
                • 操作数寄存器X
                • 变址寄存器IX
                • 基址寄存器BR
                • 程序状态字寄存器PSW
                  • 保留各类运算指令或测试指令的结果的各类状态信息
          • 控制器
            • 计算机有两种信息流动
              • 控制信息
              • 数据信息
            • 包括
              • 程序计数器PC
                • 用来存放当前预执行指令的地址，可以自动+1形成下一条指令的地址，与主存的MAR之间有一条直接通路
              • 指令寄存器IR
                • 用于存放当前的指令，其内容来自主存的MDR
              • 控制单元CU
                • 指令中的操作码字段OP（IR）送至CU，用以分析指令并发出各种微操作命令序列
                • 指令中的地址码字段Ad(IR) 送往MAR来取操作数
                • 一条指令可分为
                  • 取指阶段
                    • 在取指阶段访问存储器取出的二进制代码是指令
                  • 执行阶段
                    • 在执行阶段访问存储器取出的二进制代码是数据
          • I/O设备
            • 输入设备
            • 输出设备
        • 其中，运算器+控制器=CPU ，CPU+主存储器=主机 ，I/O设备又称为外部设备
        • 1945年，冯诺依曼提出“存储程序”的概念，称为冯诺依曼机
          • 1.计算机有运算器、控制器、存储器、输入设备、输出设备组成
          • 2. 指令和数据以同等地位保存在存储器内，并可按地址访问存储器
          • 3 指令和数据均用二进制代码表示
          • 4 指令由
            • 操作码
              • 表示操作的性质
            • 地址码
              • 表示操作数在存储器中的位置
          • 5 指令在存储器中按顺序存放。通常指令是顺序执行，在特定条件下，可根据运算结果或设定的条件改变执行顺序
          • 6 机器以运算器为中心，输入\输出设备与存储器之间的数据传送通过运算器完成
      • 1.2.3 计算机软件的分类
        • 计算机软件
          • 系统软件（系统程序）
          • 应用软件（应用程序）
        • 计算机编程语言
          • 机器语言
            • 用0和1描述不同的指令
          • 汇编语言
            • 直接对硬件操作
          • 高级语言
            • 需要经过编译程序编译成汇编语言程序，然后经过汇编操作得到机器语言程序，或者直接由高级语言程序翻译成机器语言程序。
            • 高级语言翻译程序
              • 编译执行方式
                • “用手来编译”
                • 产生目标代码
              • 解释执行方式
                • “用嘴来解释”
                • 不产生目标代码
      • 1.2.4 计算机的工作过程
        • 就是不断从存储器中逐条取出指令，然后送至存储器，经分析后由CPU发出各种操作命令，指挥各部件完成各种操作，直至程序中全部指令执行结束
      • 1.2.5 计算机系统的层次结构
        • 第1级 微程序机器级
        • 第2级 传统机器级
        • 第3级 操作系统级
        • 第4级 汇编语言机器级
        • 第5级 高级语言机器级
    • 1.3 计算机性能指标
      • 吞吐量
        • 主要取决于主存的存取周期
      • 响应时间
        • 响应时间越短，吞吐量越大
      • 主频
      • CPU周期（机器周期）
        • 指令周期>CPU周期（机器周期）>时钟周期
      • CPU时钟周期
        • 主频的倒数，是CPU最小的时间单位
          • 时钟周期数*时钟周期=时钟周期数/时钟频率
      • CPI、MIPS、FLOPS（衡量运算速度）
        • CPI
          • 执行一条指令所需要的时钟周期数
        • MIPS
          • 每秒可执行百万条指令数
        • FLOPS
          • 每秒执行的浮点运算次数
      • CPU执行时间
  • 第二章 数据的表示和运算
• 数据结构
  • 第一章 绪论
    • 1.1 C与C++语言基础
    • 1.2 算法时间复杂度和空间复杂度
      • 时间复杂度
      • 空间复杂度
    • 1.3 数据结构和算法的基本概念
      • 1.3.1 数据结构的基本概念
        • 1. 数据
        • 2. 数据元素
          • 数据的基本单位
            • 最小单位
        • 3 数据对象
          • 是性质相同的数据元素的集合，是数据的一个子集
        • 4 数据结构
          • 逻辑结构
          • 存储结构
          • 对数据的运算
        • 5 数据的逻辑结构
          • 线性结构
            • 有序
              • 前驱后继
          • 非线性结构
            • 一对一
              • 树形结构
              • 图形结构
        • 6 数据的物理结构（存储结构）
          • 当数据元素是由若干数据项构成的时候，数据项的表示称为数据域
          • 常用存储方法
            • 顺序存储方法
            • 链式存储方法
            • 索引存储方法
            • 散列存储方法
      • 1.3.2 算法的基本概念
        • 1 算法
        • 2 算法的特性
          • 有穷性
            • 一个算法必须保证执行有限步之后结束
          • 确定性
            • 算法的每一步骤必须有确定的含义
          • 输入
            • 一个算法有0个或多个输入
          • 输出
            • 一个算法有一个或多个输出
          • 可行性
        • 3 算法的设计目标
          • 正确性
          • 可读性
          • 健壮性
          • 高效率与低存储量需求
  • 第二章 线性表
    • 2.1 线性表的基本概念与实现
      • 1 线性表的定义
        • 线性表是具有相同特性数据元素的一个有限序列
        • 该序列所含元素个数叫做线性表的长度（n)
        • n 可以等于零，表示线性表是一个空表
      • 2 线性表的逻辑特性
        • 只有一个表头元素，只有一个表尾元素
        • 除表头和表尾外，其他元素只有一个直接前驱，也只有一个直接后继
      • 3 线性表的存储结构
        • 1 顺序表
        • 2 链表
        • 3 两种存储结构的比较
          • 顺序表
            • 随机访问
            • 连续的占用一片空间
            • 顺序表做插入操作的时候需要移动多个元素
          • 链表
            • 不支持随机访问
              • 进行插入操作时无需移动元素
            • 链表的5种形式
              • 1 单链表
                • 每个结点中除了包含数据域外，还包含一个指针域
                • 有无头结点
                  • 带头结点
                    • 头指针head指向头结点
                    • head->next==NULL时，链表为空
                  • 不带头结点
                    • 头指针head直接指向开始结点
                    • head==NULL时，链表为空
                  • 两者区别
                    • 带头结点的单链表中有一个结点不存储信息
                    • 不带头结点的单链表的所有结点都存储信息
              • 2 双链表
                • 单链表只能由开始结点走到终端结点，而不能由终端节点反向走向走到开始结点
                • 双链表在单链表结点上增添一个指针域，指向当前结点的前驱
                • 有无头结点
                  • 带头结点
                    • head->next==NULL时，链表为空
                  • 不带头结点
                    • head==NULL时，链表为空
              • 3 循环单链表
                • 只要将单链表的最后一个指针域（空指针）指向链表的第一个结点即可
                  • 带头结点
                    • 指向头结点
                  • 不带头结点
                    • 指向开始结点
                • 有无头结点
                  • 带头结点
                    • head->next==NULL时，链表为空
                  • 不带头结点
                    • head==NULL时，链表为空
              • 4 循环双链表
                • 类似与双链表
                • 有无头结点
                  • 带头结点
                    • 因为带头结点的循环双链表中没有空指针
                      • head->next==head
                      • head->prior==head
                      • head->next==head&&head->prior==head
                      • head->next==head || head->prior==head
                  • 不带头结点
                    • head==NULL时，链表为空
              • 5 静态链表
                • 静态链表借助一维数组来表示
                  • 每个结点含有两个分量
                    • 一个是数据元素分量data
                    • 另一个是指针分量
          • 顺序表和链表的比较
            • 基于空间的比较
              • 1 存储分配的方式
                • 顺序表的存储空间是一次性分配的
                • 链表的存储空间是多次分配的
              • 2 存储密度（存储密度=结点值域所占的存储量/结点结构所占的存储量）
                • 顺序表的存储密度=1
                • 链表的存储密度<1（因为结点中有指针域）
            • 基于时间的比较
              • 1 存取方式
                • 顺序表可以随机存取，也可以顺序存取
                • 链表只能顺序存取
              • 2 插入/删除时移动元素的个数
                • 顺序表平均需要移动一半元素（移动元素的期望E为 E=n-1/2）
                • 链表不需要移动元素，只需要修改指针
    • 2.2 线性表的结构体定义和基本操作
      • 2.2.1 线性表的结构体定义
        • #define maxsize 100//这里定义一个整型变量maxsize，值为100
          • 1 顺序表的结构体定义
            • typedef sturct { int data[maxsize] // int length }sqlist;
              • int A[maxsize]； int n;
                • 常用
          • 2 单链表结点定义
            • typedef struct LNode { int data; struct LNode *next; }LNode;
          • 3 双链表结点定义
            • typedef struct DLNode { int data; struct DLNode *prior; stuct DLNode *next; }DLNode;
      • 2.2.2 顺序表的操作
        • 例2.1 已知一个顺序表L，其中的元素递增有序排列，设计一个算法， 插入一个元素x(x为int型)后保持该顺序表仍然递增有序排列 （假设插入操作总能成功）
          • 本函数返回第一个比x大的元素的位置
            • int findElem(Sqlist L，int x) { int i; for(i=0;i<L.length;++i) { if(x<L.data[i] ) { return i; } } return i；
          • 移动并插入元素
            • void insertElem(Sqlist &L,int x) { int p,i; p=findElem(L,x)； for(i=L.length-1;i>=p;--i） L.data[i+1]=L.data[i]； L.data[p]=x； ++(L.length)； }
        • 例2.2 删除顺序表L中下标为P（0<=P<=lenrth-1）的元素，成功返回1，否则返回0，并将被删除元素的值赋给e
          • int deletElem(Sqlist &L,int P,int &e) { int i； if(P<0||P>L.length-1) return 0; e=L.data[P]; for(i=P;i<L.length-1;++i) L.data[i]=L.data[i+1}; --(L.length); return 1; }
      • 2.2.3 单链表的操作