数据库期末
第六章 关系模式表示 五元组 R(U,D,DOM,F) R是元组名（学生） U为属性（学号，姓名，专业） D为属性的域（整数，字符串，字符串） DOM为属性到域的映射（001，李明，计算机） F为属性上的数据依赖 数据依赖： 函数依赖（FD） 有R(U)，设X，Y为U的子集，若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上属性值相同，而在Y上属性值不同，称X->Y（X决定Y，Y依赖于X） 下表不属于函数依赖，因为两个元组学号相同但是姓名不同 学号 姓名 001 张三 001 李四 函数依赖类型： 非平凡函数依赖 X->Y，但Y⊊X，则称X->Y是非平凡函数依赖（本身推其他） 平凡函数依赖 X->Y，但Y⊆X，则称X->Y是平凡函数依赖（本身推本身） 完全函数依赖 如果X->Y，并且对于X的任意真子集X’，都有X’-/->Y，则称Y对X完全函数依赖，写做X-F>Y（若不存在子集则一定是完全函数依赖） 部分函数依赖 ...
����ϵͳ�����㷨
������������Ϊʹϵͳ������������������������ҪΪ���ٸ� 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...
计算机组成原理
第一章 计算机系统层次结构 第五级 高级语言级 第四级 汇编语言级 第三级 操作系统级 第二级 一般机器级 第一级 微程序设计级/逻辑电路级 第二章 原码补码反码移码 符号位 0为正...
数据结构-排序
冒泡排序 时间复杂度为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=n+12\frac{n+1}{2}2n+1 查找失败ASL=n+1 n+1 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...
