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