计算机系统基础第一章 计算机系统概述1. 计算机基本执行过程1.1 冯·诺依曼机基本结构绝大部分通用计算机的硬件基本组成仍然就有冯·诺依曼结构特征 图解： 主存储器（主存，内存）：存放指令和数据 算术逻辑部件（ALU）：进行算术逻辑运算的核心部件，可以对输入端A和B进行不同的运算，得到结果F 控制部件（CU，控制器）：自动逐条取出指令并进行译码（将二进制的操作码翻译成对应的操作） 通用寄存器（

二叉搜索树&AVL树&红黑树二叉搜索树性质 二叉搜索树，顾名思义，就是便于进行搜索的二叉树，对于每一个子树来说，其左子树的值必定小于根节点的值，其右子树的值必定大于根节点的值，二叉搜索树的性质如下： 左子树关键字 < 根节点关键字 < 右子树关键字 查找元素的平均时间复杂度是O(log n)，但最坏时间复杂度可以达到O(n)，也就是所有子树只有一个分支。 对二叉搜索树

二叉树的路径和问题描述给定一个二叉树和一个整数sum，求二叉树中的一条连续的路径，使该路径上结点的和等于sum。 解决思路这题和前面的一个题“和等于K的子数组”非常相似，因为他们都是采用哈希表来存储数据，然后通过间接的方法求得一段连续的值的和。 思路如下： 因为所求的结果是一段连续的路径，因此可以通过求差值的方法来判断该路径是否符合要求。因此，在先序遍历二叉树的时候，记录下每个路径的和出现的次数

队列和广度优先搜索队列队列是一种特殊的线性表，因为它只能从一端插入，一端删除，即先进先出的效果，类似于现实中的排队。 性质 先进先出 一般从队头入队，队尾出队 空队列：front = rear 循环队列由于队列中的元素只能从队头出，队尾进，因此如果不是特殊情况，采用顺序数组队列会浪费很多空间，并且它的使用也是有限制的（出队以后，队头之前的位置无法再被利用，而如果一直进队的话，数组总

堆排序&优先队列堆排序堆排序原理 堆是一颗具有特定性质的二叉树。堆的性质： 堆中所有结点的值必须大于或者等于(或小于等于)其孩子结点的值； 堆是一颗完全二叉树。 二叉堆：在二叉堆中，每个结点最多有两个孩子结点，二叉堆一般分为 二叉最小堆 和 二叉最大堆 堆排序函数下面以最小堆为例列举实现二叉堆需要的函数 变量声明123456789101112//头文件#include <st

递增矩阵搜索动态规划 题目描述 写一个高效地算法来查找递增矩阵中的一个值。 这个矩阵有以下特性： 从左到右数值是递增的 从上到下数值也是递增的 例如： 1 2 4 5 3 6 7 8 9 10 13 14 11 12 15 16 当待查找数值为11时，函数返回true 当待查找数值为17时，函数返回false 解题思路由于右上角的元素有很好的性质，其左边的元素都小于

层次结构存储系统按存取方式分类RAM（随机存取存储器） SAM（顺序存取存储器），如磁带 DAM（直接存取存储器），如磁盘 CAM（相联存储器）：按照内容访问，如快表 主存储器结构 层次结构 SDRAM芯片技术该芯片读写受到外部系统时钟（即前端总线时钟CLK）控制，因此与CPU之间采用同步方式交换数据。他将CPU或者其他主设备发出的地址和控制信息锁存起来，经过确定的几个时钟周期后给出响应。 支持突

操作系统-虚拟内存管理CPU访存虚拟地址空间：不同的可执行文件所映射的虚拟地址空间大小一样，地址空间中的区域划分结构也相同 页可以分为3种状态： 未分配页：没有任何内容相关联的页 缓存页：已调入主存而被缓存在DRAM中的页面 未缓存页：未调入主存而存在硬盘上的页面 操作系统使用页表将虚拟页转换成物理页，页表具有一下属性： 装入位：该页是否存在DRAM中 存放位置：指向物理页号，若为0，则没有被

不相交集结构描述顾名思义，不相交集数据结构的集合之间是没有交集的，这种结构常常需要实现两种运算： Find(x): 查找元素x所在的集合的名字 Union(x, y): 包含元素x和y的两个集合用他们的并集替换 实现数据结构以上两种算法都要求能够找到元素所在的集合的名字，因此可以构造树结构，将该树的根作为集合的名字，树上的结点都有一个指向父节点的指针，这样每个结点都能够找到该集合的名字。 12

标签划分问题描述给定一个字符串，将该字符串划分成尽可能多的部分，使得这些每个字母最多只能出现在这些部分中的一个 解决办法首先获得每个字符最后出现的下标，然后从头开始遍历每一个字符，如果某个字符的范围超出当前划分的右边界，则扩展右边界，这是当前的最优解。直到遍历指针到达右边界，此时说明划分里的字符都是只出现在这个划分里的，将该划分放入答案中，然后把下一个下标作为下一个划分的起点，直到字符串遍历完。