logo资料库

408笔记-2019.docx

发布时间：2022-06-22 发布人：admin 分类：说明书 资料大小：2.04M 资料格式：docx 举报 版权申诉
第1页 / 共14页
第2页 / 共14页
第3页 / 共14页
第4页 / 共14页
第5页 / 共14页
第6页 / 共14页
第7页 / 共14页
第8页 / 共14页
资料共14页，剩余部分请下载后查看
    数据结构 1. 线性表相关算法思想:头尾并进，分治，双指针，空间换时间，链表头插尾插，经典有序序列的归并，快速排 序思想。 2. 链表的建立，删除，插入等相关操作。 3. 栈，出栈入栈可能序列，卡特兰数 1 1 n+ n nC 2 ，共享栈。 4. 队列，出队入队操作，循环队列队空队满的判断条件，双端队列。(输入受限队列不可能得到 4213 4231，输 出受限 4132 4231) 5. 栈和队列的应用，中缀表达式转换为后缀表达式。同级别运算符栈内大于栈外。 6. 特殊矩阵压缩存储，对称矩阵，上三角矩阵((i-1)(2n-i+2)/2+j-i 可能会考)，下三角矩阵，三对角矩阵 (k=2i+j-3)(下标都是从 0 开始)。三元组，十字链表，m 行 n 列单链表个数 m+n-1,头节点个数 max{m,n}+1。 7. 树的重要知识: o 结点数等于度数加 1，也就是说边数加 1 等于结点数 o 路径长度指路径上经过的边的个数 o 带权路径长度 8. 二叉树重要知识： N0=N2+1 o o 满二叉树,完全二叉树，结点编号后，子结点和双亲结点的关系。 o n 个结点可以组成不相似的二叉树个数，以先序序列入栈中序序列出栈组成的二叉树个数，都是 1 1 n+ n nC 2 9. 二叉树递归遍历算法，非递归遍历算法，重点掌握层次遍历算法。 o 二叉树先序遍历和中序遍历确定一棵二叉树 o 二叉树后序遍历和中序遍历确定一棵二叉树 o 二叉树层序遍历和中序遍历确定一棵二叉树 10.线索二叉树，左前驱右后继，线索二叉树的中序遍历。n 个结点有 n+1 个线索数 11.森林与树转化成对应的二叉树，规则为左孩子右兄弟。树的应用并查集。森林或树与对应二叉树有如下关系： o 森林或树中叶结点数等于对应二叉树左指针为空的结点数。 o 对应二叉树右指针为空的结点数等于结点总数加 1 减去森林或树叶结点数，一种解释如下：
    o 树、森林的遍历与对应二叉树关系： o 重点习题(选择题 3 8 9 12 大题 5 6 7) 12.二叉排序树，可以左大右小，也可以左小右大。二叉排序树的查找效率分析，插入与删除操作。平衡二叉树， 插入调整方式有 RR LL RL LR，调整步骤为，找到与插入结点最近不平衡的结点，判断其关系(例如插入结点 是最近不平衡左子树的左子树)，确定其调整方式(LL)。假设 Nh 为深度为 h 的平衡二叉树含有的最少结点数(分 支结点的平衡因子全为 1)，则满足 Nh=Nh-1+Nh-2 +1。哈夫曼树，哈夫曼树的构造，从权值集合选取两个权值最 小的结点作为左右子树，且两权值之和作为新结点并删除两权值将权值之和放入集合，重复上述过程。哈夫 曼编码，前缀编码是没有一个编码是另一个编码的前缀。 13.图由顶点集和边集构成。简单图，不存在重复边，不存在顶点到自身的边。完全图，无向图中任意两个 顶点都存在边称为无向完全图(n 个顶点 n(n-1)/2 边)，有向图中任意两个顶点存在两个方向相反的弧 称为有向完全图。连通、连通图、连通分量，若无向图中两个顶点有路径，则称这两个顶点连通；若无 向图中任意两个顶点都是连通的，则称该图为连通图；无向图中的极大连通子图称为连通分量，极大要 求该连通子图包含其所有的边。 强连通、强连通分量，有向图中两个顶点存在两个方向相反的路径称两个顶点强连通，若图中任何一对 顶点都是强连通称图是强连通图，有向图的极大强连通子图称为强连通分量。生成树，连通图的生成树 是包含图中所有顶点的一个极小连通子图。顶点的度、出度和入度，无向图的全部顶点度之和等于边数 的两倍，有向图的顶点的度等于其出度和入度。有权值的图称为带权图，也称为网。重点习题：7 10 12 17 14.图的存储方式：邻接矩阵，对于无向图第 i 行非零元素个数是其第 i 个顶点的度，对于有向图第 i 行(列) 非∞元素个数正好是第 i 个顶点的出度(入度)，A 是邻接矩阵，则 An 的元素 An[i][j]表示顶点 i 到顶点 j 长度为 n 的路径个数；邻接表，可以用 c++的向量 vector 来存储；十字链表，有向图的一种链式存储 结构；邻接多重表，无向图的一种链式存储结构(每条边只有一个结点)。图的遍历：广度优先搜索 (Breadth First Search)，借助队列实现，与树的层次遍历很相似；深度优先搜索(Depth First Search)， 递归算法，类似于树的先序遍历，可以判断有向图是不是有环。两种算法在采用邻接表存储时，时间复 杂度都是 O(n+e)；而采用邻接矩阵存储时，时间复杂度为 O(n2)。重点习题：P198 2 3 4(都是求 i 到 j 的路径相关问题) 15.最小生成树：Prim 算法，类似于 Dijkstra 算法，主要思想是，最初树顶点集为{u0}，树边集为空，然 后在树顶点集以及图的所有边集中找出最小代价的边(u0，v0)加到树边集当中，同时把 v0 并入树顶点集 中，直至顶点加入完毕。下面是 Prim 算法图示：
    ruskal 算法，主要思想是，初始时树的顶点集全都收入，树边集为空，然后把图的边按权值递增加入 树的边集中，但加入的边不能构成回路。下面是 Kruskal 算法演示： K D ijkstra 算法，主要思想，集合 S 记录已求的最短路径点，dist[]记录从源点到各个顶点的最短路径长 度，初始时 S 只包含源点，dist[]为源点到各顶点直接长度，然后从 V-S 中选出 vj 使其满足 dist[j]=min{dist[k] | vk∈V-S}将其并入 S 中，然后对加入顶点进行判断是否会改变源点到各顶点的 最短路径长度：if dist[j] + edge[j][k] < dist[k] ，dist[k] = dist[j] + edge[j][k]，重复直 至得出结果。Floyd 算法，主要思想是，递推产生一个 n 阶方阵序列 A(-1)，A(0)，…，A(k)，…，A(n)，其中 A(k)[i][j]表示顶点 i 到顶点 j，中间结点是不大于 k 的最短路径长度，A(k)[i][j] = min{ A(k-1)[i][j] ， A(k-1)[i][k]+A(k-1)[k][j] }。拓扑排序(Top sort)，算法思想简单(找入度为 0 输出)，关键是算法实现。 关键路径，具有最大路径长度的路径称为关键路径，关键路径上的活动称为关键活动，可加快关键关键 活动缩短工期，关键路径不唯一，例如下图：
    关键路径为 bdcg、bdeh、bfh，路径长度 27，加快 d 和 f 的进度可以缩短工期(加快 c、e 或者 d、c 或 者 f、h 均不行，因为它们不包含在所有的路径中，比如若加快 c、e 的进度，则 bfh 的路径长度仍然是 27，不能缩短工期)，求关键路径的算法(手工模拟算法有点恶心)。 16. 查找，顺序查找(一般线性表等概率查找的平均成功查找长度为(n+1)/2，不成功 n+1，有序表不成功 n/2+n/(n+1)，可结合顺序查找判定树理解)，折半查找。现讨论折半查找判定树，根节点是折半查找的 中间结点，每个子树的根节点也相应对应其中间结点，折半查找的过程也就造就了判定树是一个二叉搜 索树，由于二叉搜索树可以左大右小也可以左小右大，因此判定树可以有两种形态(向左斜，向右斜， 大的在哪边就往哪斜，左右子树斜的方向一致)，同时折半查找过程中有中间结点的左边结点个数小于 等于右边结点个数(奇数个总结点个数是等于，偶数个是小于)，这样也就使得判定树有这样的形态特征， 数值大那边的子树结点数大于等于数值小的那边子树结点数。折半查找的平均查找成功和不成功的 ASL， 根据判定树判断各元素所在位置计算。 分块查找，索引表有序，块内无序，索引表关键字分别是每个块内关键字最大的。 17.B 树和 B+树，B 树(多路平衡查找树)，其所有结点的孩子结点数的最大值称为 B 树的阶，B 树满足如下 特性：①树中每个结点至多有 m 棵子树(至多含有 m-1 个关键字)②若根节点不是叶结点，则至少含有两 棵子树③除根节点外所有非叶结点至少┌m/2┐棵子树(至少含有┌m/2┐-1 个关键字)④所有叶结点出现在 同一层次上，并且不带信息。对包含 n 个关键字，高度为 h、阶数为 m 的 B 树：①B 树每个结点最多有 m 棵子树，因此有 n≤(m-1)*(1+m+…+mh-1)即 h≥logm(n+1)②若使每个结点关键字个数最少，对 n 个关 键字的 B 树，查找不成功的结点为 n+1 即叶结点，则有 n+1≥2(┌m/2┐)h-1。B 树插入与删除：插入，由于 插入过程中可能导致每个结点关键字大于 m-1 个，此时以中间位置分为两部分，左部分放原结点，右部
    分放新结点，中间位置插入到父结点中；删除，分两种情况：①删除关键字不在最底层非叶结点，判断 该结点大于和小于关键字 k 的>子树中关键字个数(小于 k 的子树关键字个数>┌m/2┐-1 用前驱 k'取代 k， 递归删除 k'；大于 k 的子树关键字个数>┌m/2┐-1 用后继 k'取代 k，递归删除 k'；两部分都等于┌m/2┐ -1，直接将两子结点合并，删除 k)②删除关键字在最底层叶结点，判断删除结点的关键字个数(大于┌ m/2┐-1 的，直接删除；等于┌m/2┐-1，且相邻结点关键字个数大于等于┌m/2┐(兄弟够借)，此时调整该 结点、相邻结点以及父结点；兄弟不够借(相邻结点关键字等于┌m/2┐-1)，将关键字删除后与相邻结点 及双亲结点中关键字合并。 B +树，支持顺序查找，B+树满足如下特性：①每个分支节点最多有 m 棵子树(由于每个关键字对应一棵子 树，因此每个分支结点最多有 m 个关键字)②非根叶结点至少两棵子树，其他分支结点至少有┌m/2┐棵子 树③相邻终端结点按大小顺序通过指针相互链接起来④每个结点的关键字是其对应的子结点的关键字 最大值。注意 B 树与 B+树的区别。 18.散列表(哈希表)，散列函数(直接地址法，平方取中法，折叠法，一般用除留余数法)，处理冲突方法(开 放地址法：线性探测；平方探测，可以避免出现聚集，但是最多只能查找一半；再散列；伪随机序列。 拉链法)，散列函数的平均查找长度的计算(一般冲突次数加 1)，装填因子(装填信息的个数和表长之比)。 字符串匹配，KMP 算法，求 next 数组方法(不写了，具体看博客，注意下标从 0 还是 1 开始)。 19.排序：内部排序，外部排序。排序算法时间复杂度，算法稳定性(指在键值相同情况下，算法排序后不 改变其原来相对位置)。内部排序：直接插入排序，折半插入排序，希尔排序，；冒泡排序，快速排序； 简单选择排序，堆排序；归并排序，基数排序。熟悉各种内部排序算法的算法思想，熟练写出实现代码， 同时还行熟悉各种算法的时间复杂度以及算法稳定性。外部排序，多路平衡归并和失败者树，置换-选 择排序(生成初始归并段)，最佳归并树(哈夫曼树的推广)。 计算机组成原理 1. CPI(Clock cycle Per Instruction)， 2. 海明码检验 n+k+1≤2^k，欲传递 b4b3b2b1，则 k 为 3，位置安排如下： MIPS=主频/CPI =b4⊕b3⊕b1 C2=b4⊕b2⊕b1 C4=b3⊕b2⊕b1 Cn 取序号的二进制序列低第 n 位为 1 的信息位进行异或，因此 C1 检 C1
    测的小组包括 1、3、5、7、9 等等，而 C2 检测的小组包括 2、3、6、7、10 等等，以此类推。CRC 检验，奇偶 检验。 3. [x]补符号位取反数值位取反加 1 变成[-x]补 4. 定点数原码乘法，右移。定点数补码乘法，补码右移。定点数原码除法，余数为正，商上 1，为负，商上 0， 左移一位。定点数补码除法，余数同号，商上 1，余数不同号，商上 0，左移一位。 5. 定点数加减法溢出判断。一位符号位时，参加运算的操作数符号位相同，结果与原操作数不同，表示溢出。 根据进位与符号位判断，符号位进位与最高位进位进行异或，1 表示溢出。浮点数下溢可以当做机器零处理， 上溢必须中断来做相应处理。 6. IEEE754 阶码的 32 位单精度浮点数(1 位符号，8 位阶码和，23 位尾数)和 64 为双精度浮点数(一位符号，11 位阶码，52 位位数)的移码偏置值 127 和 1023。注意尾码第一个不是 0 的数隐藏。浮点数规格化的格式(正负 数原码补码)。 7. RAM(随机存储器)分为 DRAM(地址引脚复用技术，引脚数可减少一半)和 SRAM，ROM(只读存储器)，顺序存取存 储器(如磁带)，直接存取存储器(如磁盘)。 8. 多模块存储器，高位交叉编址(顺序方式)，低位交叉编址(交叉方式)。存取周期为 T，总线传送周期为 r，则 交叉模块数大于 m=T/r，交叉方式连续存取 m 个字所需时间 t=T+(m-1)r。 9. Cache 和主存映射方式(主存地址空间映射到 Cache 地址空间)，直接映射(主存块号 i Cache 块号 j 及总块数 Q 因此 j = i mod Q) 全相联映射 组相联映射(主存块号 i Cache 组 j 及总组数 Q 因此 j = i mod Q) C
    ache 替换算法，Cache 写策略有全写法(写直通法，Write Through，写命中同时写入 Cache 和主存，添加 Buffer 减少访存次数)、写回法(Write Back，写命中只修改 Cache，只有换出才写回主存，脏位)。 10.指令格式，零地址指令，一地址指令，二地址指令，三地址指令，四地址指令。扩展操作码指令格式，每减 少上一级指令数，下一级相应增加对应的指令数(例如 32 指令长度，地址码 12 位，有 250 条二地址指令，则 应有(256-250)*4K 条单地址指令)。指令寻址方式：隐含寻址，立即寻址，直接寻址，间接寻址，寄存器寻址， 寄存器间接寻址，相对寻址(PC 加上偏移量)，基址寻址(基址寄存器加上偏移量)，变址寻址(数组)，堆栈寻 址。CISC(指令数目多，指令字长不固定，寻址方式多，寄存器数量少，微程序控制)，RISC(指令数目少，指 令字长固定，寻址方式少，寄存器数量多，一般为组合逻辑控制)。 11.CPU 一般由数据通路和控制部件两大部分组成。通常将指令执行过程中数据经过的路径，包括路径上的部件称 为数据通路。运算器包含 ALU、ACC、通用寄存器、PSW、计数器等。控制器包含 PC、IR、指令译码器、MAR、 MDR、时序系统、微操作信号发生器。指令周期一般分为取指周期、间址周期、执行周期、中断周期(为区别 不同工作周期，在 CPU 内设置 4 个标志触发器 FE、IND、EX、INT，1 表示有效)。指令周期的数据通路分析(非 常重要，可能会考)。重点习题：P193-194 1 8 9 12.硬布线控制器(组合逻辑控制器)，控制方式(同步，异步，联合)。微程序控制器，采用存储逻辑实现，将每 条指令转化为一段微程序存入控存中，取指微程序是公共的。微指令编码方式，直接编码(每个字段都对应一 个微命令，编码简单，直观，但微指令过长)，字段直接编码(互斥指令在同一字段内，相容性微命令在不同 字段中，同时还行留出一个状态表示不发出微命令)，字段间接编码。水平型微指令(并行能力强，效率高， 灵活性强，执行时间短，微指令长但微程序短)，垂直型微指令(并行能力差，效率低，灵活性差，执行时间 短长，微指令短但微程序长)，混合型微指令。考虑形成后继地址的取指操作如下： 13.指令流水线，影响指令流水线的因素有资源冲突(多条指令同一时刻争用同一资源形成的冲突)、数据冲突(前 一条指令执行完才能执行后一条指令)、控制冲突(分支指令、异常或中断引起的)。流水线性能指标，吞吐率 (TP=n*主频/(k+n-1)，k 是流水线段数，n 是指令数)，加速比(S=kn/(k+n-1))，效率。超标量流水线，每个 时钟周期可以并发多条独立指令，只能靠编译程序解决优化问题。 14.总线(BUS)，片内总线，系统总线，通信总线。总线突发传输既要传送地址也要传送连续的数据。总线结构， 单总线结构，双总线结构，三总线结构。总线判优(仲裁)的方式有链式查询，计数器定时查询，独立请求(三 种方式区别与联系请看书)。总线定时，同步定时，异步定时(不互锁，半互锁，全互锁)。常见的总线标准有 ISA EISA VESA PCI PCI-Express AGP RS-232C USB PCMCIA IDE SCSI SATA。 15.I/O 系统，包括 I/O 软件(驱动程序、用户程序、管理程序等)和 I/O 硬件(外部设备、设备控制器、接口、总 线等)。磁盘平均存取时间包括寻道时间、旋转延迟时间、传输时间。磁盘地址格式，驱动器号、柱面号、盘 面号、扇区号。RAID 通过同时使用多个磁盘，提高传输率；通过多个磁盘并行存取来大幅提高吞吐量；通过 镜像功能，提高可靠性；通过数据检验，提高容错能力。I/O 接口(I/O 控制器)是主机和外设之间的交接界面， 主要的功能有①实现通信②地址译码和设备选择③数据缓冲④信号格式转换⑤传送控制命令和状态信息；I/O
    端口是指接口电路中能被 CPU 直接访问的寄存器，每个端口都对应一个端口地址，编址方式有统一编址(和存 储器一起编址)和独立编址。 16.I/O 控制方式：程序查询方式，CPU 查询外设状态，等待外设做好准备才执行 I/O 指令；程序中断方式，当外 设做好输入/输出准备时，向主机发中断请求；DMA 方式，外设进行数据传送，DMA 控制器向 CPU 提出总线请 求，CPU 响应后 DMA 接管总线，DMA 进行外设和存储器间的数据传送，数据传输完成后 DMA 发出中断请求，CPU 响应后转去进行相关后续工作，DMA 传送方法有①CPU 停止访问主存②存储器分时③总线周期挪用，DMA 请求 优先级高于中断请求，DMA 请求响应可以是任一机器周期结束后；通道方式，从主存中取出选中设备的通道程 序执行，向设备控制器和设备发送控制命令，完成主存和外设的数据传送，将外设和通道本身的中断请求以 及状态信息送 CPU。中断，可分为①内中断和外中断②硬中断和软中断③非屏蔽中断和可屏蔽中断；可嵌套中 断处理过程，关中断→保存断点→引出中断服务程序→保护现场和屏蔽字→开中断→执行中断服务程序→关 中断→恢复现场和屏蔽字→开中断→中断返回；多重中断，执行中断服务程序中响应新的中断请求这种中断 是多重中断又称中断嵌套；中断屏蔽字，用 1 表示屏蔽该中断，如中断源优先级 A>B>C>D，则 A 的中断屏蔽字 1111(可能考点)。 操作系统 1. 操作系统的四个基本特征:并发，共享，虚拟，异步。操作系统的接口:命令接口(联机和脱机)，程序接口(系 统调用)。系统调用一般过程位：①设置系统调用号和参数②执行相应中断指令③分析系统调用号④转入服务 程序⑤返回用户态。操作系统发展历程及各个阶段特点。操作系统运行机制(引入中断和异常，系统调用)和 体系结构(大内核和微内核)。 2. 进程的概念，特征，状态，控制，组织，通信。(PCB 包含的内容)。线程概念，实现方式(一对多，多对一， 多对多)。 3. 处理机调度，有作业调度，进程调度，三级调度，中级调度。调度方式，有剥夺式，非剥夺式。重要的评价 标准，有平均周转时间，响应比。调度算法:FIFO,SJF 等。 4. 进程同步：进程同步的概念，实现临界区互斥的方法(单标志，双标志先检查，双标志后检查，Peterson's 算 法，TestAndSet 法)。信号量，利用信号量实现进程同步和互斥(生产者和消费者，读者写者问题，哲学家就 餐，吸烟者问题，需牢记于心)。管程，是一个语言成分，实质是一个抽象类。(重点习题，7 8 9 10 11 12 13 15 17 19 20 22) 5. 死锁，死锁产生的必要条件(①互斥条件②不剥夺条件③请求和保持条件④循环等待)，死锁预防(采用预先静 态分配破坏条件③；采用顺序资源分配破坏条件④)，死锁避免(银行家算法)，死锁检测和解除(资源分配图)。 6. 程序装入与链接。链接方式有静态链接，装入时动态链接，运行时动态链接。装入方式有，绝对装入，可重 定位装入，动态运行时装入。链接阶段形成逻辑地址，装入阶段形成物理地址。连续分配管理方式：单一连 续分配，固定分区分配，动态分区分配。 动态分区的分配策略：首次适应(按地址递增顺序查找)，最佳适应(按容量递增查找)，最坏适应(按容量递减 查找)，邻近适应(循环首次适应，从上次查找结束的位置查找)。
    分享到：
    赞 收藏

    相关推荐

    资料库

    考试认证

    共收录20637份资料，累计11个分类，关注成员有19位，主要包括：真题,美赛,软考,PMP,Linux/Unix认证,思科认证,微软认证,Oracle认证,华为认证,软考等考,其它

    热门标签

    真题 美赛 软考 PMP Linux/Unix认证 思科认证 微软认证 Oracle认证 华为认证 软考等考 其它

    最新资料