计算机基础学科

0x00 数据结构与算法分析

0x00 基础数据结构

1.1 数据结构概念小结 本文共585字,阅读大约需要3分钟

本文详细讲述了数据结构中一些通用的基本概念,主要涉及各种存储方式的阐述及相同点和不同点。

1.2 链表 本文共4508字,阅读大约需要23分钟

本文详细讲述了单向链表的增删改查操作并附及相关代码,阐述了双向链表、循环链表的基本概念及增删改查操作的示例代码,并附以几道相关的、具有代表性的LeetCode题目进行阐述和解题过程、代码及对比其他网友代码后综合评选出的最优化代码。

1.3 栈和队列 本文共2946字,阅读大约需要11分钟

本文详细讲述了栈和队列两种抽象数据类型的基本原理,并给出了栈的顺序存储实现及链式存储实现的代码及相关分析,以及顺序存储实现循环队列和双端队列的相关代码和分析,同时给出了两道经典程序员笔试面试题--2个栈实现1个队列和2个队列实现1个栈--的解题思路及相关代码,同时佐以几道具有代表性的LeetCode题目进行阐述和解题过程及代码。

1.4 树 本文共14459字,阅读大约需要85分钟

本文极长而且覆盖面较广,建议以根据目录进行查阅的方式观看。

本文详细讲述了有关树的算法及相关分析及其代码,以及部分相关LeetCode题目的解题思路代码和具体分析,包括二叉树的4种遍历方式(先序、中序、后序、层序)、二叉树的建立(唯一确定法、中序及先序或后序建立唯一二叉树)、线索二叉树(基本概念、中序和后序线索二叉树的建立)、树-森林-二叉树三者之间的相互转换、二叉排序树(基本概念、建立、删除、查找、判定)、平衡二叉树(基本概念、建立、插入、查找、判定)、B树(基本概念、查找、插入、删除)、B+树(基本概念)、哈夫曼树(基本概念、构造、哈夫曼编码)、二叉树特性相关算法(最大高度、最小高度、最大宽度)。

1.5 图 本文共9540字,阅读大约需要46分钟

本文极长而且覆盖面较广,建议以根据目录进行查阅的方式观看。

本文详细讲述了图的相关概念以及图的种类及其判别,以及图的4种基本存储方式(邻接矩阵、邻接表、十字链表、邻接多重表)的基本概念及相关实现,给出了图的广度优先及深度优先两种搜索算法相关的实现代码及其复杂度分析,并给定了由BFS和DFS延伸出来的题目(判断图中是否有环)的相关代码实现,同时给定了2中最小生成树生成算法(Prim算法和Kruskal算法)以及2种最短路径的算法(Dijkstra算法和Floyd算法),同时给出了拓扑排序和关键路径算法的相关流程及分析。

0x01 基本算法

2.1 排序算法 本文共7091字,阅读大约需要31分钟

本文极长而且覆盖面较广,建议以根据目录进行查阅的方式观看。

本文详细讲述了排序中的基本概念(稳定与否、内部排序与外部排序、比较型和非比较型),以及10种内部排序算法的代码实现、原理总结、复杂度分析、相关比较以及部分LeetCode题目及相关衍生题目的解法等,它们分别是:插入排序、选择排序、归并排序、堆排序、快速排序、冒泡排序、希尔排序、梳排序、计数排序、桶排序。以及外部归并排序这一种外部排序算法的相关概念及总结。

2.2 查找算法 本文共8055字,阅读大约需要44分钟

本文极长而且覆盖面较广,建议以根据目录进行查阅的方式观看。

本文详细介绍了针对顺序存储结构的顺序查找、二分查找和分块查找算法的相关原理、实现代码及复杂度分析。给出了哈希表的构造及查找方法,同时给出了5种散列函数的构造方法,它们分别是:直接定址法、除留余数法、平方取中法、数字分析法以及折叠法,以及给出了2种哈希函数的冲突处理方法(开放定址法和拉链法)的基本原理及性能分析。以及针对字符串匹配的暴力破解算法和KMP算法,其中讲述了2种KMP算法中next数组的生成算法,因为此算法较为难以理解,故文章中给出了KMP算法的手工模拟流程及其代码讲解。

0x01 操作系统

1.1 基本概念 本文共3876字,阅读大约需要16分钟

本文详细讲述了操作系统的5大基本特征及分类,以及阐述了操作系统的运行机制、内核构成等,同时详细阐述了操作系统的中断(外中断)及异常(内中断)机制以及中断程序的执行过程。

1.2 进程管理 本文共8592字,阅读大约需要35分钟

本文较长且带有较多概念及算法,建议根据目录或以检索的形式进行查阅。

本文讲述了操作系统的进程控制机制及其相关的组成部分,同时介绍了处理机调度的方式、原理、评价的准则及6种处理机调度算法的流程即优缺点分析,即:先来先服务(FCFS)、短进程优先(SJF)、优先级调度算法、高响应比优先(HRRN)、时间片轮转调度(RR)、多级反馈队列算法。同时描述了进程同步的基本概念以及使用信号量机制和管程机制实现的进程同步。同时阐述了死锁的原因、预防机制、避免机制(包括系统安全状态和银行家算法)、以及死锁的检测与解除。

1.3 内存管理 本文共14193字,阅读大约需要60分钟

本文较长且带有较多概念及算法,建议根据目录或以检索的形式进行查阅。

本文详细阐述了操作系统中内存管理的基本算法和分配方式,包括基于单一连续分配、固定分区分配或动态分区分配方式的连续内存分配管理策略。以及基于基本分页、基本分段和段页式的非连续内存分配管理方式。同时对于部分分配管理方式给出了相关的地址变换机构图。同时描述了虚拟内存的管理机制以及缺页中断机构的实现及4种页面置换算法(最佳置换算法OPT、先进先出页面置换算法FIFO、最近最久未使用置换算法LRU及时钟置换算法CLOCK)的描述及流程。

1.4 文件管理 本文共9683字,阅读大约需要41分钟

本文较长且带有较多概念及算法,建议根据目录或以检索的形式进行查阅。

本文详细讲述了文件的逻辑结构、目录结构等相关概念,以及介绍了基于索引结点以及利用符号链机制实现的文件共享方法。同时给出了文件系统的实现原理,以及文件的连续分配、链接分配和索引分配这些文件分配方法及其相关比较。同时相关的阐述了磁盘组织与管理机制以及文件的存储空间管理(空闲表法、空闲链表法、位示图法、成组链接法)。

1.5 输入输出管理 本文共1315字,阅读大约需要6分钟

本文阐述了操作系统进行I/O操作时的一些基本的控制方式及方法,包括直接控制法、中断驱动方式、DMA方式、通道控制方式等。

0x02 计算机网络

2.1 体系结构 本文共1168字,阅读大约需要5分钟

本文详细介绍了OSI七层和TCP/IP体系结构对互联网体系所划分的4层,以及相关的比较等。

2.2 物理层 本文共2685字,阅读大约需要12分钟

本文详细介绍了计算机网络中物理层的相关概念以及物理层的信息交互方式、编码以及数字信号与模拟信号的相互转换等基本概念,同时给出了比特率-波特率、奈奎斯特定理和香农定理等一些公式及其相关计算。

2.3 数据链路层 本文共6532字,阅读大约需要28分钟

本文讲述了数据链路层的相关功能及具体功能的实现方式和基本算法协议等,具体有差错控制、流量控制(包括后退N帧协议GBN、选择重传协议SR)以及介质访问控制方法,包括各种信道复用模式、以及CSMA系列的介质访问控制协议的基本原理。

2.4 网络层 本文共5550字,阅读大约需要23分钟

本文主要介绍了网络层的相关协议的基本原理、功能以及相关的路由算法,协议主要包括IPv4、ICMP、ARP、DHCP、IPv6等。同时给出了路由选择中的相关计算,最长前缀匹配原则、同一子网判断、IP地址的划分、有效子网数的相关计算等。

2.5 传输层 本文共2702字,阅读大约需要12分钟

本文主要描述了传输层的TCP和UDP协议的基本原理,以及两者之间的比较,着重讲述了TCP协议的重传控制和拥塞控制,说明了其中的慢开始算法和拥塞避免算法,拥塞处理算法的相关流程等信息。

2.6 应用层 本文共1209字,阅读大约需要6分钟

本文以域名解析协议DNS、文件传输协议FTP、电子邮件协议(包括POP3和SMTP)、HTTP协议为例介绍了应用层的基本功能及信息。

2.7 计算题总结 本文共1930字,阅读大约需要9分钟

本文是对前几篇文章有关计算题部分的总结,包括物理层的比特率-波特率换算、奈奎斯特定理和香农定理的有关计算,数据链路层的最小帧长计算、链路利用率计算以及CSMA/CD协议的二进制指数退避算法以及检测到冲突发生的最大时间和最小时间计算等,传输层的最大吞吐量计算以及TCP传输中TCP头部确认号的确定机制,网络层协议中IP数据报分片总长度的计算、路由表的撰写等。