Moench 的算法宝库

第一章 微型计算机概述CPU中的主要寄存器：有六类寄存器：指令寄存器（IR）、程序计数器（PC）、地址寄存器（AR）、数据寄存器（DR）、累加寄存器（AC）、程序状态字寄存器（PSW）文章源地址：https://blog.csdn.net/weibo1230123/article/details/83106141 从内存获取1个数据，对于CPU来说，是（读）操作。向内存发出1个数据，对于CPU来说，是（写）操作。某CPU是16位，则可以认为CPU内部，（ 通用寄存器 ）由16bit组成 系统总线中，数据总线是（ ），地址总线是（ ），控制总线是（ ）B. 双向，单项，双向 控制总线包括：（ ）。C. RD WR 中断 CPU在1个操作（周期）时间对（ ）个内存单元进行（ ）种操作。D. 1，1 溢出状态标志位 OF (overflow flag) 如何判断:OF = D(7ADD) ⊕(异或) D(6ADD) = 最高位的进位状态 xor 次高位的进位状态注意：从最低为开始计算，最高位 = 1项 + 2项 + 进位 第二章 8086/8088微处理器CS 、IP存相 ...

计算机系统概论若一个8位的计算机系统以16位来表示地址，则该计算机系统有（ ）个地址空间答：8位表示计算机字长为8位，即一次可以处理8位的数据，而16位表示地址码的长度，故而该机器由2^16 = 65536个地址空间 运算方法和运算器下列有关浮点数加减运算的叙述中，正确的是（ I II III IV ）I 对阶操作不会引起阶码上溢或下溢II 右规和尾数舍入都可能引起阶码上溢III 左规时可能引起阶码下溢IV 尾数溢出时结果不一定溢出解释：对阶是较小的阶码对齐至较大的阶码Ⅰ 正确。右规和尾数舍入过程，阶码加1 而可能上溢Ⅱ 正确。同理Ⅲ 正确。尾数溢出时可能仅产生误差，结果不一定溢出Ⅳ 正确。 IEEE754 ；1 8 231：符号位 0正1负，8：阶码化为二进制，1000.101 -> 1.000101 * 2^011(二进制)23：原码 去掉1，00010100…… 存储系统DRAM地址复用技术：地址线/2 相对寻址： 程序计数器PC所指的地址为起始地址 应用：转移指令 基址寻址 程序的起始地址为起始地址 应用：多道程序 变址寻址 自己决定 ...

2023/6/22 convenient : adj. 方便的 convince : v. 使信服 conventional : adj. 墨守成规的, 传统的 facilitate : v. 促进, 使便利 facility : n. 设备 rarely : adv. 少见的 barely : adv. 几乎, 仅仅 reserve : v. 预定 -> reserved : adj. 内敛的 reverse : v. 反转 subsequent : adj. 随后的, 后来的 substantial : adj. 大量的 shoot : v. 射击, 发射 shot : (shoot 过去式) n. 尝试, 注射 illusion : n. 错觉, 幻想 illustrate : v. 说明, 表明 constitute : vlink(系动词). 组成, 构成 contribute : v. 捐献, 做贡献 boost : v. 增长 boast : v. 自夸, 自吹自擂 steady : adj. 稳定的 / 坚定的 -> ste ...

栈和队列 栈的排列方式: n个不同的元素进栈, 出栈元素不同排列的个数为 $\frac{1}{n+1}C_{2n}^n$ 堆顶栈 栈满条件: top0 + 1 = top1 (无论是否从0或1开始) 循环队列判断队满的情况: (q.rear + 1) % Maxsize == q.front 栈和队列的异同点 栈和队列都是加了限制的线性表,栈是先进后出表,队列是先进先出表。栈和队列的插入和删除操作都在端点进行,栈的插入和删除在同一端点,队列的插入和删除在不同的端点进行。 首元结点, 头结点, 头指针的区别 首元结点（First Node）：链表中的首元结点是指链表中第一个实际存储数据的结点。它是链表中第一个具有数据域和指针域的结点，用来存储链表中的第一个元素。 头结点（Head Node）：头结点是在链表中添加的一个额外的结点，位于链表的前面，不存储实际的数据。头结点的作用是为了方便链表的操作和管理，它可以包含一些附加信息，如链表的长度等。 头指针（Head Pointer）：头指针是指向头结点的指针，它是链表的入口。通过头指针，可以找到整个链表的起始位置。头指 ...

第一章 概述 从多方面比较电路交换、报文交换、分组交换的优缺点； 电路交换：需要建立连接，端对端通信质量因约定了通信资源获得可靠保障，对连续传送大量数据效率高。 报文交换：无须预约传输带宽，动态逐段利用传输带宽，对突发式数据通信效率高，通信迅速。 分组交换：具有报文交换之高效、迅速的要点，且各分组小，路由灵活，网络生存性能好。 计算机网络的分类； 按照网络的作用范围进行分类: 广域网 WAN 城域网 MAN 局域网 LAN 个人区域网 PAN 按照网络地使用者进行分类: 公用网 (public network) 专用网 (private network) 用来把用户接入互联网的网络: 接入网 AN (access network) 计算机网络常用的性能指标有哪些，其中时延由哪几部分组成； 速率：速率是指连接在计算机网络上的主机在数字信道上传送数据的速率。是计算机网络中最重要的一个性能指标。当数据率较高时，就常常在 bit/s 的前面加上一个字母。速率往往是指额定速率或标称速率，并非网络上实际上运行的速率。 带宽：本意是指某个信号具有的频带宽度。在计算 ...

第一章:概念部分:数据（Data）: 数据库中存储的基本对象数据库（Database）: 长期储存在计算机内, 有组织的, 可共享的大量数据的集合数据库管理系统（DBMS）: 位于用户和操作系统之间的一层数据管理软件 是基础软件, 是一个大型的复杂的软件系统数据库系统（DBS）: 由数据库, 数据库管理系统(及其应用开发工具), 应用程序, 数据库管理员组成. 区别和联系: 数据库是计算机信息系统和应用系统的核心,是数据库管理系统处理的对象; 数据库管理系统是对计算机中所存放的大量数据进行组织、管理、查询并提供一定处理功能的大型系统软件,是用来处理数据库中的数据的软件; 数据库系统是数据库及其管理、维护和使用所需要的计算机硬件、软件和使用人员的总和,数据库和数据库管理系统属于数据库系统的一部分. 数据库管理系统的功能: 定义功能 操纵功能 控制功能 其他 市面上主流的数据库: Oracle Sql server Mysql DB2 Access 三个世界: 现实世界 信息世界 机器世界 两种模型: 概念模型: 也称信息模型, 按照用户的观点, 对数据 ...

算法杂项数论部分两个数互质则不能由 p, q 凑出来的最大的数为 (p - 1) * (q - 1) - 1;平面直角坐标系部分皮克定理：定理： 皮克定理是指一个计算点阵中顶点在格点上的多边形面积公式，该公式可以表示为 S = a + b/2 - 1，其中 a 表示多边形内部的点数，b 表示多边形落在格点边界上的点数，S 表示多边形的面积。 结论： s(面积) = a(中间的点) + b(边上的点) / 2 - 1 两点(x1, y1)(x2, y2)的连线上的整点数 ： 结论： abs(gcd(x1 - x2, y1 - y2)) 证明 将该直线其中一点移动到原点(0, 0)，另一点为(a, b)，则该直线斜率为 b’ / a’ (约分过)，则该支线上的所有点一定为 k * (b' / a')，k 可取 1, 2, 3, …… , gcd(a, b)。化为原坐标即为 gcd(x1 - x2, y1 - y2) , 因为 gcd 函数可能得负数，所以取 绝对值 abs()

拓扑排序概念： 在一个有向图中，对所有节点排序后，对于每一条边都是前面指向后面，没有由后面指向前面的边，则称新的序列为有向图的拓扑排序。若有向图存在环，必然没有拓扑排序；若有向图无环，则必然存在一个拓扑排序。 如果一个图是可以拓扑排序的，则称此图为拓扑图 == 有向无环图(DAG) 算法实现： 将所有入读为0的点入队123456789while (q 非空){ t <- q的头节点 for t 的所有出边 t -> j { -- d[j]; if (d[j] == 0) q <- j; }} 算法模板如下：如果求字典序最小的拓扑排序，将 队列换成优先队列即可。 当前队列的元素为 度数为0 的点，当前序列中的点一定为 123456789101112131415161718void topsort(){ int hh = 0, tt = -1; for (int i = 1; i <= n; i ++ ) if(!d[i]) q[ ++ ...

欧拉回路和欧拉路径引入：哥尼斯堡七桥问题 欧拉路径 == 一笔画问题 结论： 欧拉路径 起点终点 度数为奇数 中间顶 度数为偶数 对于无向图，所有边都是连通的 存在欧拉路径的充分必要条件：度数(入读 + 出度)为奇数的点只能由0或2个。 存在欧拉回路的充分必要条件：度数为奇数的点为0个。 对于有向图，所有边都是连通的 存在欧拉路径的充分必要条件：所有点的出度均等于入度 或 除了两个点以外，其余所有点出度等于入度，剩余两个点 一个满足出度比入度多1（起点），一个满足入度比出度多1（终点） 存在欧拉回路的充分必要条件：所有点的出度均等于入度 证明： 左 -> 右：已证明，右边本就是由左边推来的。 左 <- 右：构造一种方案合法，即可证明 直接 DFS ，遇到回路则进去转一圈出来，则一定可以走到终点，最终路径为一条线挂着许多环。 算法实现：seq数组保存路径，最终的路径是 seq 的逆序。 123456void dfs(int u){for 从 u 出发的所有边 dfs() // 扩展seq <- u} 欧拉回路的 dfs 遍 ...

二分图染色法时间复杂度：O(n + m)算法实现：邻接表存储，dfs一遍，没染色，则染上色 结论1： 一个图是二分图 == 图中不存在奇数环 == 染色法不存在矛盾 p -> q : p 是 q 的充分条件，q 是 p 的必要条件 假设 如上三个条件为 a == b == c 证明1： b 直接推 a 不太容易，所以 b -> c - > a b -> c ： 反证法：假设图中不存在奇数环 但 染色法出现了矛盾。 假设第一个矛盾为两个白色相连，则在该连通块(环)中其他的点一定不存在矛盾，其染色一定为 白-黑-白-黑-……-白，首尾都为白，则符合我们的假设。如此一来，此连通块一定有奇数个点与已知反证法条件相矛盾，则原结论成立。 c -> b : 反证法：如果染色的过程中不存在矛盾 但 图中存在奇数环 假设一个环的头为白色，有因为其是奇数环，则其尾一定也为白色，首尾都是白色，所以该图存在矛盾，原结论成立。 (b, c) -> a 因为染色法不存在矛盾，则 白黑 相间连接，把白色黑色分别拿出，则构成二分图。 a -> (b, c) ...