计组基础算法
进程死锁 r-每个进程请求的最大资源 n-进程数 m-R1资源总数 公式： (r-1)* n+1>m 若每个进程都请求r-1个且总资源剩余1个及以上就不会发生死锁 动态分区分配 M-用户区初始空间 M1-第一次分配 M2-第二次分配 F1-第一次释放 F2-第二次释放 M3-第三次分配 M4-第四次分配 F-最后主存中最大空闲分区 公式： 依次执行 F1=M1;F2=M-M1-M2 if(F1>=F2) F1=F1-M3 else F2=F2-M3; if(F1>=F2) F1=F1-M4 else F2=F2-M4; if(F1>=F2) F=F1 else F=F2; 分页地址变换 A-逻辑/虚拟地址 L-页长 P-页号 d-页内地址offset F-物理块号 MA-物理地址 公式： P=A/L d=A%L A=P* L+d P->查页表->F MA=F* L...
3.29一些感想
...
数据库系统概论
第六章 关系模式表示 五元组...
计算机组成原理
第一章 计算机系统层次结构 第五级 高级语言级 第四级 汇编语言级 第三级 操作系统级 第二级 一般机器级 第一级 微程序设计级/逻辑电路级 第二章 原码补码反码移码 符号位 0为正...
操作系统
进程同步 生产者-消费者问题 分析： 生产者消费者共享一个初始为空，大小为n的缓冲区 缓冲区没满时，生产者才能将产品放入缓冲区，否则等待 缓冲区不为空时，消费者才能取出产品，否则等待 缓冲区是临界资源，进程必须互斥访问（wait(mutex)和signal(mutex)成队出现） 多个P操作的顺序不能颠倒，应先执行对资源信号量的P操作，再执行对互斥信号量的P操作，否则可能会引起进程死锁，V操作可以颠倒 123456789101112131415161718192021222324252627282930313233//生产者-消费者 伪代码semophore empty = n; //空闲缓冲区的数量semophore full = 0; //产品数量、非空缓冲区的数量semophore mutex = 1; //互斥信号量，确保同时只有一个进程运行producer { while( true ) { 生产产品 P( empty ); // 等待缓冲区有空闲位置， 在使用PV操作时，条件变量需要在互斥锁之前 ...
数据结构-排序
冒泡排序 时间复杂度为O(n^2) 123456789for(int i=0;i<n-1;i++){ for(int j=0;j<n-1-i;j++){ if(a[j]>a[j+1]){ int temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } }} 插入排序 时间复杂度：O(n^2) 12345678910111213141516void InsertSort(int arr[], int n) { int i, j, temp; // temp 用于暂存待插入元素 for (i = 1; i < n; i++) { // 从第二个元素开始（数组下标从0开始） if (arr[i] < arr[i-1]) { // 若当前元素小于前驱，需要插入 temp = arr[i]; // 暂存待插入元素 ...
数据结构-查找
查找 查找表——用于查找的数据集合，由同一类型的数据元素组成 关键字——数据元素中唯一标识该元素的某个数据项的值，查找结果应该是唯一的 操作 查找 静态查找表——仅关注查找速度就可以 插入删除 动态查找表——出了查找速度，也要方便实现插删操作 评价指标 查找长度——在查找运算中，需要对比的关键字次数称为查找长度 平局查找长度(ASL)——所有查找过程中进行关键字比较的次数 查找成功ASL=$$\frac{n+1}{2}$$ 查找失败ASL=$$ n+1 $$ 顺序查找 1234567891011typedef struct{ ElemType *elem; int length;}SSTable;int Search_seq(SSTable ST,ElemType key){ int i; for(int i=0;i<ST.length && ST.elem[i]!=key;i++){ return i==ST.length ? -1:i;...
数据结构-图
图 无向图 无向图---->无向边(边) (v,w)=(w,v) E={(A，B),(B,C),(C,D),(D,E)} 度：依附于顶点的边的条数 TD(v) 无向图全部顶点的度的和为边数的二倍 无向完全图有n(n-1)/2条边 有向图 有向图---->有向边(弧) <v,w>!=<w,v> E={<A,B>,<B,C>,<C,D>} 入度：以顶点为终点的弧 ID(v) 出度：以顶点为起点的弧OD(v) 度：入度和出度的和TD(v) 在有n顶点，e条边的有向图中，所有顶点的ID和OD的和等于e 有向完全图有n(n-1)条弧 简单图 1.不存在重复边 2.不存在顶点到自身的边 多重图 1.图中某两个节点间的边数多于一条(有向图互相指不算，需要为同向的) 2.顶点与自己相关联 顶点和顶点间的关系 1.路径：从点A到点D的顶点序列 eg.A-B-C-D...
数据结构-树
基础概念 子树，孩子双亲，兄弟，度，叶子，分支节点，层次，深度（最大层次）有序树，无序树 二叉树简介 斜树 所有节点都只有左或右子树 满二叉树 所有节点同时具有左子树和右子树，同样深度的的二叉树中满二叉树的节点最多，叶子最多 完全二叉树 对一棵具有n个节点的二叉树按层序从左到右排序，二叉树某个节点的排序与同样位置的满二叉树节点的排序相同如果所有节点都满足这个条件，则二叉树为完全二叉树 若存在度为1的节点的话，有且只有一个，并且只有左孩子 二叉树性质 在二叉树的第i层上最多有2^{i-1}个节点 深度为i的二叉树最多有2^i-1个节点 对任何一棵二叉树来说，如果叶子节点数目为n0，度为2的节点数目为n2，则n0=n2+1 具有n个节点的完全二叉树的高度为至少为log2(n+1) 如果对一棵有n个节点的完全二叉树的节点按层序编号（从第一层开始到最下一层，每一层从左到右编号），对任一节点i有: 如果i=1 ，则节点为根节点，没有双亲。 如果2i > n ，则节点i没有左孩子 ；否则其左孩子节点为2i .（n为节点总数） 如果2i+1>n...
