数据结构

{
    绪论【8.16】
    线性表【8.16】
    {
        逻辑结构与物理结构
        静态分配与动态分配
        头插、尾插、赋值前插
    }
    栈、队列和数组【8.19】
    {
        n种元素进栈,出栈不同序列个数，卡特兰数
        循环队列长度//(rear + maxsize - front) % maxsize
        3种队满//牺牲一个单元 sum tag
        双端队列
        括号匹配
        表达式求值
        中缀转后缀
        {
            若为数字，加入表达式
            若为'('，入栈
            若为')'，依次把栈中的运算符加入表达式，直到出现'(',从栈删除'('
            若为其他运算符
            {
            其优先级高于栈顶，则入栈
            否则出栈比当前运算符优先级高或相等的运算符
            直到一个优先级比他低或'('为止
            }
            扫描中缀表达式结束，栈中所有运算符依次出栈加入表达式
        }
        递归算法转换为非递归通常(非必定)借助栈
        数组和特殊矩阵//有些模糊，全靠硬推，最好再听听课研究研究
    }
    串
    树与二叉树
    图
    查找
    排序
}

组成原理

{
    概述
    数据运算表示
    存储系统
    指令系统
    CPU
    总线
    IO
}

操作系统

{
    概述
    进程线程
    内存管理
    文件管理
    IO管理【8.17】【8.18】【8.19】
    {
        IO端口接口
        IO控制方式
        {
            直接
            中断
            DMA
            通道
        }
        IO软件层次
        应用程序IO接口
        高速缓存与缓冲区
        {
            单双缓冲区//max(处理，输出)+传送 max(传送+处理，输入)
            循环缓冲
            缓冲池//3个队列、4种缓冲区
        }
        设备分配与回收
        {
            独占、分时共享、SPOOLing虚拟设备
            设备分配数据结构//设备控制表DCT 控制器控制表COCT 通道控制表CHCT 系统设备表SDT p298 p302
            分配策略
            安全分配 不安全分配//IO之后是否进入阻塞
            逻辑设备名到物理设备名的映射//逻辑设备表LUT 整个系统一张LUT或每个用户一张LUT放入PCB
        }
        SPOOLing技术//假脱机 必须有多道程序技术支持 空间换时间 预输入程序 井管理程序 缓输出程序
        {
            输入井 输出井//磁盘上开辟出的存储区域
            输入缓冲区 输出缓冲区//内存中开辟
            输入进程 输出进程//模拟脱机IO的外围控制机
        }
        设备驱动程序接口
        {
        要求每个设备驱动程序与操作系统之间都有着相同或相近的接口
        操作系统要定义一组驱动程序必须支持的函数
        驱动程序包含一张表格，具有针对这些函数指向驱动程序自身的指针
        }
        磁盘//柱面号 盘面号 扇区号 固定头活动头固定盘可换盘
        磁盘管理
        {
            磁盘初始化//低级格式化:划分扇区，每个扇区的数据结构由头部、数据区域、尾部组成
            分区//1.将磁盘分为C盘等分区，每个分区起始扇区和大小记录在磁盘主引导记录的分区表中 2.对物理分区进行逻辑格式化(创建文件系统)，操作系统将初始文件系统数据结构存到磁盘上
            引导块//p316 p29
            坏块//简单磁盘:手动 不透明，复杂磁盘:坏块链表 透明
        }
        磁盘调度算法//磁盘读写时间: 寻找时间 + 旋转延迟 + 传输时间，寻找时间包括启动磁臂时间，旋转延迟转半圈
        {
            FCFS
            SSTF//最段寻找时间优先
            SCAN//扫描算法或电梯调度算法 移到最外才往内，移到最内才往外 到头回到起点为LOOK
            C-SCAN//循环扫描算法 到头回到最靠前的请求为C—LOOK
            ***无特别说明。SCAN C-SCAN就是LOOK C—LOOK***
        }
        固态硬盘SSD//电可擦ROM，即EEPROM 基于闪存技术的存储器 由闪存芯片和闪存翻译层(逻辑块号翻译成页)组成
        {
            以页为单位读写
            以块为单位擦除
            擦干净的块可写一次 读无限次
            没有移动部件 无噪声震动 能耗低 抗震性好 安全性高
            磨损均衡//动态磨损均衡 静态磨损均衡(更先进)
        }

    }
}

计算机网络

{
    体系结构
    物理层
    数据链路层
    {
        随机访问介质访问控制【8.22】
        {
            ALOHA
            CSMA载波侦听多路访问
            CSMA/CD载波侦听多路访问/碰撞检测//有线 总线型以太网 电压变化
            {
                先听后发，边听边发，冲突停发，随机重发
                指数退避算法//16次
                半双工通信
                2t争用期 冲突窗口 碰撞窗口
                以太网最小帧长64B
            }
            CSMA/CA载波侦听多路访问/碰撞避免//无线局域网 能量检测载波检测能量载波混合检测 1.预约信道 2.ACK帧 3.RTS/CTS帧(可选)
        }
    }
    网络层
    传输层
    应用层
}