计科专业基础课学习框架
2021-03-16 09:44:00 0 举报AI智能生成
如果你想系统的学习计科专业的四大基础课：计算机网络、操作系统、计算机组成原理和数据结构，那你可以根据这张思维导图来学习。这张思维导图基本涵盖了所有知识点。跟着导图学习，你一定会对计算机的理解更加深入。
作者其他创作
大纲/内容
DS
逻辑结构
数据集合
元素之间没有关系
堆
元素之间有关系
线性结构
线性表
基本概念
逻辑结构概念
常用概念
直接前驱
直接后继
大小
容量
长度
已经使用的量
基本操作
初始化
Initiate(L)
求表长度
Length(L)
取表元素
Get(L,i)
定位
Locate(L,x)
插入
Insert(L,x,i)
删除
Delete(L,i)
分类
受限线性表
栈
基本概念
应用
进制转换的除K取余法中用来保存余数
括号匹配用来保存括号
队列
应用
用作缓存存储非即时操作
分类
双向队列
单向队列
非受限线性表
一维数组
特殊矩阵压缩存储
非线性结构
树（具有层次关系）
基本概念
没有节点称为空树
有节点是根节点唯一
度
说明
节点拥有子节点的个数
树的度是树中各个节点度的最大值
分类节点
度为0
终端节点
度不为0
分支节点
分类树
度为2
二叉树
定义
主要特征
在二叉树的第i层上至多有2i-1个结点（i>=1）
深度为k的二叉树至多有2k-1个结点（k>=1）
对任何一棵二叉树T，如果其终端结点个数为n0，度为2的结点数为n2，则n0 = n2 + 1
具有n个结点的完全二叉树的深度为「log2n」+ 1（「x」表示不大于x的最大整数）
如果对一棵有n个结点的完全二叉树的结点按层序编号（从第一层到第「log2n」+ 1层，每层从左到右），对任一结点i（1≤i≤n）有：
若i=1，则结点i是二叉树的根，无双亲；如i>1，则其双亲是结点「i/2」。
如2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。
若2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1。
若i=1，则结点i是二叉树的根，无双亲；如i>1，则其双亲是结点「i/2」。
如2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。
若2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1。
存储
顺序
结点的存储位置反映了它们之间的逻辑关系：位置k的结点的双亲结点的位置为「k/2」，它的两个孩子结点的位置分别为2k和2k+1
链式
二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域即可
二叉树遍历（归结为父子节点的遍历）
前序
先访问根结点，然后遍历左子树，最后遍历右子树
中序
后序
层序
子主题
线索二叉树的遍历和构造
分类
斜树/单边树
斜树即为线性表
满二叉树
退化
完全二叉树
平衡二叉树
子主题
度大于2
树、森林
树的存储结构
森林和二叉树的转换
树和森林的遍历
表示方法
双亲表示法
使用Node[]存储所有节点，并且class Node{int parent;}
孩子表示法
多重链表法
class Node{Node[] children}
使用Node[]存储所有节点，并且class Node{int selfIndex;LinkList<Node> children;}
双亲孩子表示法
使用Node[]存储所有节点，并且class Node{int selfIndex;int parentIndex;;LinkList<Node> children;}
孩子兄弟表示法
class Node() {E data;Node firstChild;Node rightSib;}
层
根节点为第一层
应用
二叉搜索树
平衡二叉树
哈弗曼树和哈弗曼编码
图
基本概念
存储及基本操作
邻接矩阵
邻接表
邻接多重表
十字链表
搜索
深度优先
广度优先
基本应用
最小生成树
最短路径
拓扑排序
关键路径
多维数组
存储结构
顺序存储
链式存储
索引存储
索引表
以关键信息代表整个记录
散列存储
构成
散列函数
存在取余操作
导致扩容不易
散列表
连续存储空间
查找
基本概念
方法
顺序
分块
折半
B树及其基本操作、B+树的基本概念
散列表
字符串模式匹配
分析及应用
排序
概念
方法
外部排序
基数排序
二路归并
堆
快速
希尔
简单选择
冒泡
插排
直接插排
折半插排
应用
Computer Organization Principle
计算机系统概述
系统层次结构
系统的基本组成
硬件的基本组成
软件和硬件的关系
计算机的工作过程
系统性能指标
吞吐量
响应时间
CPU时钟周期
主频
CPI
CPU执行时间
MIPS
MFLOPS
GFLOPS
TFLOPS
PFLOPS
EFLOPS
ZFLOPS
数据的表示和计算
数制及编码
进位计数制及其相互转换
真值和机器数
字符与字符串
定点数的表示与计算
表示
无符号树的表示
有符号整数的表示
计算
定点数的位移计算
原码定点数的加减运算
补码定点数的加减运算
定点数的乘除运算
溢出概念和判别方法
浮点数的表示和运算
表示
IEEE754标准
子主题
运算
加法
减法
算数逻辑单元
串型加法器
并行加法器
功能
结构
存储器层次结构
存储器
分类
层次化结构
半导体随机存取存储器
SRAM
DRAM
只读存储器
Flash存储器
主存与CPU的连接
双口RAM和多模块存储器
高速缓冲Cashe
基本工作原理
与主存的映射方式
替换算法
写策略
虚拟存储器
基本概念
段式存储
页式存储
段页式存储
TLB（快表）
指令系统
指令格式
基本格式
定长操作码
扩展操作码
寻址方式
有效地址的概念
数据寻址和指令寻址
常见寻址方式
中央处理器
功能
基本结构
指令执行过程
数据通路
功能
基本结构
控制器
功能
工作原理
分类
硬布线控制器
微程序控制器
基本概念
微程序
微指令
微命令
格式
编码方式
微地址的形式方式
指令流水线
基本概念
基本实现
超标量和动态流水线的概念
总线
概述
基本概念
分类
组成及性能指标
操作和定时
同步定时
异步定时
总线标准
I/O系统
I/O系统基本概念
外部设备
输入设备
输出设备
外存储器
I/O接口
功能和基本结构
端口及其编址
I/O方式
程序查询方式和
程序中断方式
中断基本概念
中断响应
中断处理
多重中断和中断屏蔽
DMA方式
DMA控制器的构成
DMA传送过程
Operation System
操作系统概述
概念
特征
功能
服务
发展
分类
运行环境
内核态与用户态
中断、异常
系统调用
体系结构
进程管理
进程
概念
状态与转换
控制
组织
通信
共享存储系统
消息传递系统
管道通信
线程
线程概念
多线程模型
处理机调度
基本概念
时机
切换
过程
基本准则
方式
典型调度算法
先来先服务
短作业（短进程、短线程）优先调度算法
时间片轮转
优先级
高响应比
多级反馈队列
同步与互斥
同步概念
实现互斥的基本方法
软件方法
硬件方法
信号量
管程
经典同步问题
生产者-消费者
读者写者
哲学家进餐
死锁
概念
处理策略
预防
避免
系统安全状态
银行家算法
检测和解除
内存管理
基础
概念
程序装入与链接
逻辑地址与物理空间
内存保护
连续分配管理方式
非连续分配管理方式
分页管理方式
分段管理方式
段页式管理方式
虚拟内存管理
概念
请求分页管理方式
页面置换算法
最佳置换算法(OPT)
先进先出置换算法(FIFO)
最近最少使用置换算法(LRU)
时钟置换算法(CLOCK)
页面分配策略
工作集
抖动
文件管理
基础
文件概念
逻辑结构
顺序文件
索引文件
索引顺序文件
目录结构
文件控制块和索引节点
单级目录和两级目录
树形目录结构
图形目录结构
文件共享
文件保护
访问类型
访问控制
实现
文件系统层次结构
目录实现
文件实现
磁盘组织和管理
磁盘的结构
磁盘调度算法
磁盘的管理
输入输出管理
I/O管理概述
I/O控制方式
I/O软件层次结构
I/O核心子系统
调度概念
高速缓存与缓冲区
设备分配与回收
假脱机技术
Computer Network
计算机网络体系结构
概述
概念
组成
功能
分类
体系结构
分层结构
网络协议、接口、服务等概念
参考模型
ISO/OSI
TCP/IP
物理层
通信基础
信道、信号、宽带、码元、波特、速率、信源、信宿等基本概念
奈奎斯特定理和香农定理
编码与调制
电路交换、报文交换、分组交换
数据报、虚电路
传输介质
常见介质
双绞线
同轴电缆
光纤
无线传输介质
物理层接口特性
物理层设备
中继器
集线器
数据链路层
数据链路层的功能
组帧
差错控制
检错编码
纠错编码
流量控制与可靠传输机制
基本
流量控制
可靠传输
滑轮窗口机制
停止-等待协议
后退N帧协议(GBN)
选择重传协议(SR)
介质访问控制子层
信道划分
子主题
随机访问
轮询访问
网络层
传输层
应用层
收藏
收藏
0 条评论
下一页
