I/O设备的基本概念和分类 I/O就是输入/输出I/O设备就是可以将数据输入到计算机，或者可以接收计算机输出数据的外部设备，属于计算机中的硬件部件。I/O设备按使用特性分类 人机交互类外部设备 存储设备 网络通信设备 I/O设备按传输速率分类 低速设备 中速设备 高速设备 I/O设备按信息交换的单位分类 块设备 字符设备 I/O控制器 I/O设备的机械部件主要用来执行具体I/O操作 如我们看得见摸得着的鼠标/键盘的按钮；显示器的LED屏；移动硬盘的磁臂、磁盘盘面。 I/O设备的电子部件通常是一块插入主板扩充槽的印刷电路板。 CPU无法直接控制I/O设备的机械部件，因此I/O设备还...

基本概念 查找–在数据集合中寻找满足某种条件的数据元素的过程称为查找 查找表（查找结构）–用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录）组成 关键字–数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的 对查找表的常见操作 1、查找符合条件的数据元素 2、插入、删除某个数据元素 只需进行操作1–静态查找表（仅关注查找速度即可） 也要进行操作2–动态查找表（除了查找速度，也要关注插入删除操作是否方便实现） 查找算法的评价指标 查找长度–在查找运算中，需要对比关键字的次数称为查找长度 平均查找长度（ASL,AverageSearchLength）-...

二叉排序树（BST） 二叉排序树，又称二叉查找树（BST，BinarySearchTree）一颗二叉树或者是空二叉树，或者是具有如下性质的二叉树：左子树上所有结点的关键字均小于根结点的关键字；右子树上所有结点的关键字均大于根结点的关键字；左子树和右子树又各是一颗二叉排序树 左子树结点值<根结点值<右子树结点值进行中序遍历，可以得到一个递增的有序序列二叉排序树的查找 BSTNodeBST_Search(BSTreeT,intkey){ while(T!=NULL&&key!=T->key){ //若树空或等于根结点值，则结束循环 if(key<T-&...

列表（HashTable），又称哈希表，是一种数据结构，特点是：数据元素的关键字与其存储地址直接相关 例：有一堆数据元素，关键字分别为｛19，14，23，1，68，20，84，27，55，11，10，79｝，散列函数H(key)=key%13 若不同的关键字通过散列函数映射到同一个值，则称它们为“同义词” 通过散列函数确定的位置已经存放了其他元素，则称这种情况为“冲突” 用拉链法（又称链接法、链地址法）解决‘冲突’：把所有“同义词”存储在一个链表中 散列查找 常见的散列函数 设计目标–让不同关键字的冲突尽可能地少 除留余数法—H(key)=key%p 散列表表...

顺序查找的算法思想 顺序查找，又叫“线性查找”，通常用于线性表算法思想：从头到脚挨个找顺序查找的实现 typedefstruct{ //查找表的数据结构（顺序表） ElemTypeelem; //动态数组基址 intTableLen; //表的长度 }SSTable; //顺序查找 intSearch_Seq(SSTableST,ElemTypekey){ inti; for(i=0;i<ST.TableLen&&ST.elem[i]!=key;i); //查找成功，则返回元素下标；查找失败，则返回-1 returni=ST.TableLen?-1:i; } ...

现代计算机的结构 计算机的工作过程 指令的定义 指令（又称机器指令）：是指示计算机执行某种操作的命令，是计算机运行的最小功能单位。一台计算机的所有指令的集合构成改机指令系统，也称为指令集。注意：一台计算机只能执行自己指令系统中的指令，不能执行其他系统的指令。x86架构、ARM架构 指令格式 一条指令是机器语言的一个语句，它是一组有意义的二进制代码 一条指令通常要包括操作码字段和地址字段两部分： 一条指令可能包含0个、1个、2个、3个、4个地址码… 根据地址码数目不同，可以将指令分为零地址指令、一地址指令、二地址指令… 零地址指令OP 不需要操作数，如空操作、停机、关中断等指令 堆栈...

B树 B树，又称多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。一颗m阶B树或为空树，或为满足如下特征的m叉树。 树中每个结点至多有m棵子树，即至多含有m-1个关键字 若根结点不是终端结点，则至少有两颗子树 除根结点外的所有非叶结点至少有[m/2]棵子树，即至少含有[m/2]-1个关键字 所有的叶结点都出现同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空） 所有非叶结点的结构如下： B树的高度 B树的插入 新元素一定是插入到最底层“终端节点”，用...

广度优先遍历（BFS） 树的遍历：不存在“回路”，搜索相邻的结点时，不可能搜到已经访问过的结点图的遍历：搜索相邻的顶点时，有可能搜到已经访问过的顶点要点： 找到与一个顶点相邻的所有顶点 标记哪些顶点被访问过 需要一个辅助队列 FirstNeighbor(G,x)：求图G中顶点x的第一个邻接点，若有则返回顶点号，若x没有邻接点或图中不存在x，则返回-1 NextNeighbor(G,x,y)：假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1 boolvisited[MAX_VERTEX_NUM];//访问标记数组 b...

最小生成树（最小代价树） 对于一个带权连通无向图G=(V,E)，生成树不同，每棵树的权（即树中所有边上的权值之和)也可能不同。设R为G的所有生成树的集合，若T为R中边的权值之和最小的生成树，则T称为G的最小生成树(Minimum-Spanning-Tree,MST)。 最小生成树可能有多个，但边的权值之和总是唯一且最小的 最小生成树的边数=顶点数一1。砍掉一条则不连通，增加一条边则会出现回路 如果一个连通图本身就是―棵树，则其最小生成树就是它本身 只有连通图才有生成树，非连通图只有生成森林 Prim算法（普里姆） Prim算法（普里姆): 从某一个顶点开始构建生成树; 每次将代价最小的...

基本操作 Adjacent(G,x,y):判断图G是否存在边<x,y>或(x,y) Neighbors(G,x):列出图G中与结点x邻接的边 InsertVertex(G,x):在图G中插入顶点x DeleteVertex(G,x):从图G中删除顶点x AddEdge(G,x,y):若无向边(x,y)或有向边<x,y>不存在，则向图G中添加该边 RemoveEdge(G,x,y):若无向边(x,y)或有向边<x,y>存在，则从图G中删除该边 FirstNeighbor(G,x):求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x...

基本的半导体元件及原理 存储元： 注意：MOS管可理解为一种电控开关，输入电压达到某个阈值 存储器芯片的基本原理 寻址 SRAM和DRAM StaticRandomAccessMemory，即静态RAMDynamicRandomAccessMemory，即动态RAMSRAM用于Cache、DRAM用于主存 DRAM芯片：使用栅极电容存储信息 SRAM芯片：使用双稳态触发器存储信息 栅极电容 电容放带你信息被破坏，是破坏性读出。读出后应有重写操作，也称“再生” 读写速度更慢 每个存储元制造成本更低，集成度高，功耗低 双稳态触发器 双稳态 1：A高B低 0：A低B...

Cache基本原理、基本概念 Cache工作原理 局部性原理 空间局部性：在最近的未来要用到的信息（指令和数据），很可能与现在正在使用的信息在存储空间上是邻近的（数组元素、顺序执行的指令代码） 时间局部性：在最近的未来要用到的信息，很可能是现在正在使用的信息（循环结构的指令代码）基于局部性原理，不难想到，可以把CPU目前访问的地址“周围”的部分数据放到Cache中 程序B按“列优先”访问二维数组，空间局部性更差 性能分析 如何区分Cache与主存的数据块对应关系？ Cache和主存的映射方式 Cache很小，主存很大。如果Cache满了怎么办？ 替换算法 CPU修...