备考软考数据库 1-2 硬件 算法 数据结构

各部分重点:

1 计算机硬件:考6题左右

  1. 计算机基本组成
  2. FLynn分类法:
    SISD
    SIMD
    MISD
    MIMD
  3. RISC/CISC
  4. 码制:
    原码:第一位表示正负
    反码:原码的基础上负数符号位以外的各位取反
    补码:反码的基础上负数加1
    移妈:补码的基础上首位取反
    反码和补码可以直接用于带符号数的运算,移码适合阶码运算
  5. 寻址方式:
    立即寻址:直接给出操作数
    直接寻址:给出操作数的地址或操作数所在寄存器号
    间接寻址:给出指向操作数地址的地址
    变址寻址:给出的地址需通过计算获得操作数地址
    例:计算机字长16位,运算器16位,16个16位寄存器,8种寻址方式,主存容量64K
    则:地址码为ln8+ln16=7位,操作码为16-7=9位,可表示2^9=512种指令,每个寄存器可表示2^16个字的地址即64K
  6. 中断的响应时间:收到中断请求后,停止执行代码并保存现场的时间
  7. 主存编址:
    例:设某内存按字节编址,地址从A4000H编到CBFFFH共28000H字节,即160KB
    若用32KB的芯片,需要5片
  8. Cache平均访问时间=Cache命中率*Cache周期时间+内存周期时间*(1-Cache命中率)
    对每条指令,地址和操作都需要算
  9. 映射机制:
    直接相连:一个主存块只能复制到Cache一个特定位置
    Cache块号i=主存块号j MOD Cache块数m
    例:Cache容量16KB,每块大小16B,则主存地址最低4位为Cache块内地址,接下来10位为Cache块号
    全相联映射:主存每一页可以映射到Cache任一页
    组相联映射:Cache先分块再分组,通过直接映射确定组号,全相联映射确定块号
    主存地址:区号 组号 块号 块内地址
    Cache地址: 组号  块号  块内地址
    例:64块Cache组相联,每块128字,4块为一组。主存4096块。两种方式计算主存地址位数
    内存的块也需128字,所以内存一共4096*128字,主存地址需要19位
    内存需要分为4096/64个区,区号为ln64=6位
    Cache中4块为一组,块号为ln4=2位
    Cache可分为16组,组号为ln16=4位
    Cache块内地址为ln128=7位,主存的块内地址也为7位
    6+2+4+7=19
  10. 磁盘容量的计算:
    磁道数=(外半径-内半径)*道密度*记录面数
    非格式化容量=位密度×内周长×磁道数
    格式化容量=每道扇区数×扇区容量×磁道数
    平均传输速率=每道扇区数×扇区容量×盘片转速
    存取时间=寻道时间+等待时间
  11. 流水线:
    任务分成n个子任务,每个子任务需要时间ti,流水线方式完成这样的任务k个,完成该任务所需总时间为sum(ti)+(k-1)*max(ti)
    流水线吞吐率:单位时间内流水线完成任务数
    流水线的加速比:流水线方式所需时间/顺序方式所需时间
  12. 可靠性计算:串/并/模冗余
  13. 指令周期:
    时钟频率=主频=1/时钟周期
    一个时钟周期内,CPU仅完成一个最基本的动作
    机器周期=完成一个基本操作所需的时间
    一个指令包含多个最基本的操作,指令周期=执行指令所有操作所需时间

2 算法和数据结构 考1题左右

  1. 线性表:栈LIFO,队列FIFO,链表,多维数组,广义表
  2. 二叉树:
    性质:
    i层上最多有2^{i-1}个节点
    深度为k的二叉树至多有2^k-1个节点
    任意二叉树,叶子节点数n_0=度为2的节点数n_2+1
    完全二叉树的定义和性质
    遍历:
    前序遍历:根左右
    中序遍历:左根右
    后序遍历:左右根
    二叉排序树:中序遍历可得排序好的序列
  3. 要获得表达式的前缀、后缀、中缀表达式,现将表达式写成叉树形式,然后进行相应遍历
  4. 排序:插入、希尔、选择、堆排序、冒泡、快速、归并、基数排序
  5. 二分法查找

  6. 定义
    存储方式:邻接矩阵、邻接表
    遍历:深度优先、广度优先
    最短路径
    连通分量

 

Leave a Reply

Your email address will not be published. Required fields are marked *