资源描述
第一章1.算法的基本要素：一是要做哪些事（算法对数据的操作） 二是决定做这些事情的先后顺序（控制结构）2.算法的基本特征：（1）能行性（2）确定性（3）有穷性（4）拥有足够的情报3.算法评价的标准（算法的复杂度主要包括）：时间复杂度和空间复杂度 4.算法的时间复杂度：执行算法所需要的计算工作量 算法的空间复杂度：执行这个算法所需要的内存空间5.用算法在执行过程中所需基本运算的执行次数来度量算法的工作量6.算法所执行的基本运算次数与问题规模相关7.对于一个固定规模，算法所执行的基本运算次数可能与特定的输入有关 用平均性态（平均时间复杂度）最坏情况复杂性（最坏时间复杂度）来描述第二章1.数据结构研究的主要问题：分析数据的特征选择逻辑结构和物理存储结构在存储结构的基础上实现对数据的操作2.数据逻辑结构指数据元素前后件的关系，与它们在计算机中的存储位置无关；数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）3.常用的存储结构有顺序、链接、索引等存储结构顺序存储结构连续存放；逻辑上相邻，物理上也相邻结构简单，易实现插入、删除操作不便（需大量移动元素）链式存储结构非连续存放，借助指针来表示元素间关系结构较复杂，需要额外存储空间插入、删除操作简单，只要修改指针即可索引存储结构非连续存放检索速度快增、删操作简单散列存储结构散列存储结构数据元素无内在联系存储形式不定 哈希表就是这样结构4.5.数据运算是指对存放在物理结构上的数据，按定义的逻辑结构进行的各种操作（输入、检索、插入、删除、修改、排序）6.线性表：n（n0）个数据元素的有限序列 线性表特点：均匀性 有序性 除了第一个元素，每一个元素都有一个前驱，除了最后一个元素每个元素都有一个后继7.线性表中所有元素所占的存储空间是连续的 线性表中的各数据元素在存储空间中是按逻辑顺序依次存放8.顺序表：将线性表中的元素相继存放在一个连续的存储空间中； 存储结构：数组； 特点：线性表的顺序存储方式。逻辑上相邻，物理上相邻；存取方式：随机存取。9.栈是限定仅在表尾进行插入和删除运算的线性表，表尾称为栈顶（top），表头称为栈底（bottom）。10.栈的物理存储可以用顺序存储结构，也可以用链式存储结构。11.队列：一种特殊的线性表，遵守FIFO（First In First Out）规则。队列的数据元素重视从表末尾加入，从表头取出。队列的物理存储可以用顺序存储结构，也可用链式存储结构。12. front Rear13.循环队列区分队空队满长采用两种方法 增加一个标志位S；S=0 队空S=1且rear=front 队满14.程序中 front=（rear+1）%MAXSIZE来判断队满15.二叉树的性质：在二叉树的第i层上至多有2(i-1)个结点（i1）深度为k的二叉树至多有2k -1个结点（k1）对任何一颗二叉树T，如果其叶结点数为n0，度为2的结点数为n2，则n0=n2+1具有n个结点的二叉树，其深度至少为log2 n+1在编号完全的完全二叉树中，编号为i的结点，若存在做孩子，则其编号为2i；若存在有孩子，则其编号为2i+1；若存在父结点，则其编号为i/216.图是对结点的前驱和后继个数不加限制的数据结构。有向图：图中每条边都是顶点的有序对。无向图：图中每条边都是顶点的无序对。17顶点间的关系边可描述为顶点的偶对，边是无序的。弧：顶点间的边是有序的。弧头：弧的终点（方向前方）。弧尾：弧的起始点称为弧尾（方向后方）。Vx（弧尾）Vy弧头18.无向图中：顶点的度是以该顶点为一个端点的边的条数。有向图中有入度和出度。19.路径：从顶点Vx到顶点Vy的顶点序列称为从Vx到Vy的路径。路径的长度是该路径上边或弧的数目。20.连通图：在无向图中，若每一对顶点间都有路径，称此图是连通图。第三章1.平均查找长度（ASL）：与关键字进行比较的平均次数。它是用来评价一个算法好坏的一个依据。顺序查找优点对结点的逻辑次序和存储结构无要求；缺点ASL较长。2.二分查找的先决条件是查找表中的数据元素必须有序。优点：ASLlog2 n；缺点：因要求有序，所以对所有数据元素按大小排序是非常费时的操作。3.分块查找又称索引顺序查找，这是顺序查找的一种改进方法。优点：插入、删除操作方便；只要找到对应的块，在块中任意位置操作均可。缺点：索引表增加了辅助存储空间。4.哈希查找也成为散列查找，哈希查找则是通过计算存储地址的方法进行查找的。在哈希元素（地址）求解过程中，不同关键字值对应到同一个存储地址的现象称为冲突。即关键字K1K2，但哈希函数值H(K1)=H(K2)。处理冲突的方法：开放定址法Hi=(H(key)+di) MOD m，再哈希法，链地址法。线性探测再散列di=1,2，m-1 二次探测再散列di=12,-12,22,+k2,-k2(km/2)5.快速排序法又被称为“分区交换排序”。按某种方法选取一个元素K，以它为分界点，用交换的方法将序列分为两个部分：比该值小的放在左边，否则在右边。形成左子序列K右子序列再分别对左右两部分实施上述分解过程。6.插入排序基本思想：边插入边排序，保证子序列中是排好序的。每次处理将无需数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。插入算法比较次数和交换次数约为n2/2,因此其时间复杂度为O(n2)，该算法基本稳定，数据基本有序，插入排序速度块。7.希尔排序是对直接插入排序的改进方法。排序间隔n/2k k=1,2，8.选择排序：每次从待排序的记录中选出关键字最小（或最大）的记录，顺序放在已有序的记录序列的最后（或最前）面，直到全部数列有序。9.堆定义：hih2i，hih2i+1 hih2i hi小于等于h2i+1从最后一个非终端结点开始往前逐步调整，让每个双亲不大于（或不小于）子女，直到根结点为止。10二分法查找效率高，顺序法可以采用链表存储结构，操作灵活，最好是既有二分法的高效率，又有链表灵活性的查找方法。解决之道：二叉排序树。11.二叉排序树：二叉树为空，或者是具有下列性质的二叉树：如根结点的左子树不空，则左子树所有结点是值均小于根结点值；如根结点的右子树不空，则右子树所有结点是值均小于根结点值；根结点的左右子树也分别是二叉排序树。第四章1.操作系统是控制和管理计算机硬件和软件资源、合理组织计算机工作流程、方便用户使用计算机响应速度而设计的一套程序的集合。功能：文件管理，进程管理，存储器管理，设备管理，作业管理。2.程序是为解决某个问题用计算机语言或命令设计、编写的一系列指令的有序集合。3.进程就是程序的一次执行过程，是系统进行资源分配和调度的一个独立单元。进程的状态运行状态、就绪状态、等待状态。处于就绪状态的进程一旦分配到CPU，就转为运行状态。处于等待状态的进程，当需要等待某个时间发生才能继续运行时，则转为等待状态；或者由于分配给它的时间片用完，就让出CPU而转为就绪状态。处于等待状态的进程，如果它等待的时间已经发生，即条件得到满足，就转为就绪状态。4.线程是一个程序内部的顺序控制流（独立执行的流）。但线程并不是程序，它自己并不能运行，必须在程序中才能运行。5.存储器（Memory）能接收数据、保存数据、并能根据命令提供这些数据的装置。第五章1.数据库：长期存储在计算机内的、有组织的、可共享的数据集合。特点：数据按一定的数据模型组织、描述和存储；具有较小的冗余度；较高的数据独立性和易扩展性；可为各种用户共享。2.数据结构是对实体类型和实体间联系的表达和实现，描述系统的静态特性；数据操作是在数据结构之上允许执行的操作集合，包括对数据库的检索和更新（插入、删除、修改）操作，描述系统的动态特性；数据完整性约束是数据及其联系所具有的制约和依赖规则，以保证数据库中数据的正确性、有效性和相容性。3.ER图中的四个基本成分:矩形框，表示实体类型;菱形框，表示联系类型;椭圆形框，表示实体类型和联系类型的属性(下划线表示键);直线，联系类型与其涉及的实体类型之间以直线连接，并在直线端部标上联系的种类(1:1, 1:N, M:N)4.关系的三类完整性约束：实体完整性、参照完整性和用户定义完整性。完整约束条件是数据模型的一个重要组成部分，它保证数据库中数据与现实世界的一致性；实体完整性：元组在组成主键的属性上不能有空值；参照完整性（引用完整性）：不允许引用不存在的元组；用户定义的完整性（域完整性）5.视图的作用？视图能够简化用户的操作视图使用户能以多种角度看待同一数据视图对重构数据库提供了一定程度的逻辑独立性视图能够对机密数据提供安全保护6.数据库设计步骤？需求分析概念结构的设计逻辑结构的设计物理结构的设计7.sql语言建立一个“学生选课”表SC，它由学号Sno、课程号Cno，修课成绩G组成，其中(Sno, Cno)为主码。CREATE TABLE SC( Sno CHAR(5) , Cno CHAR(3) , G int, Primary key (Sno, Cno);增加列基本格式ALTER TABLE 表名 ADD 列名 类型；ALTER TABLE S ADD ADDRESS VARCHAR (30)修改列基本格式 ALTER TABLE 表名 MODIFY 列名 类型；ALTER TABLE S MODIFY SA SMALLINT；删除列基本格式 ALTER TABLE 表名 DROP 列名；ALTER TABLE S DROP UNIQUE(Sn)；DISTINCT短语的作用范围是所有目标列查询选修课程的各种成绩SELECT DISTINCT Cno，Grade FROM SC;查询所有（不）姓刘学生的姓名、学号和性别。 SELECT Sname，Sno，Ssex FROM Student WHERE Sname （NOT）LIKE 刘%；使用谓词 IS NULL 或 IS NOT NULL，“IS NULL” 不能用 “= NULL” 代替查询缺少成绩的学生的学号和相应的课程号。 SELECT Sno，Cno FROM SC WHERE Grade IS NULL；使用ORDER BY子句 可以按一个或多个属性列排序 升序：ASC；降序：DESC；缺省值为升序查询选修了3号课程的学生的学号及其成绩，查询结果按分数降序排列。 SELECT Sno，Grade FROM SC WHERE Cno= 3 ORDER BY Grade DESC； 查询有3门以上课程是90分以上的 学生的学号及（90分以上的）课程数 SELECT Sno, COUNT(*) FROM SC WHERE Grade=90 WHERE是选择记录的条件； GROUP BY Sno HAVING是选择分组的条件，且 HAVING COUNT(*)=3; 必须和GROUP BY一起使用求学生学号、姓名、选修课程名、成绩。SELECT Student.Sno，Sname，Cname，GradeFROM Student，Course，SCWHERE Student.Sno=SC.Sno AND SC.Cno=Course.Cno;实验三：复杂查询（1）连接查询a等值连接：求s表和j表的相同城市的等值连接。select s.*,j.*from s,jwhere s.city=j.cityb自然连接：查询所有的供应明细，要求显示供应商、零件和工程的名称，并按照供应、工程、零件排序。select sname,jname,pnamefrom s,p,j,spjwhere s.sno=spj.sno and p.pno=spj.pno and j.jno=spj.jno order by s.sno,j.jno,p.pnoc、笛卡尔积：求s和p表的笛卡尔积select s.*,p.*from s,pd、左连接：求j表和spj表的左连接。法一：select j.*,sno,pno,qtyfrom j,spjwhere j.jno*=spj.jno法二：select j.*,sno,pno,qtyfrom j left outer join spj on j.jno=spj.jnoe、右连接：求spj表和j表的右连接。法一：select j.*,sno,pno,qtyfrom j,spjwhere spj.jno=*j.jno法二：select j.*,sno,pno,qtyfrom spj right outer join j on spj.jno=j.jnof、 自连接：s表的自连接select s1.sno,s2.sname,s2.cityfrom s s1,s s2where s1.sno=s2.sno and s2.city=天津（2） 嵌套查询：a、 in连接谓词查询：查询没有使用天津供应商供应的红色零件的工程名称。 对工程表J中的每一个JNO进行如下判断：检查SPJ中是否存在这样的元组，其JNO=J.JNO，并且所用的零件是天津供应商供应的，且是红色零件。如果SPJ中不存在这样的元组，则该工程号JNO满足条件，放入结果表中；如果SPJ中存在这样的元组，则该工程号JNO不满足条件，不放入结果表中。检查工程表中下一个JNO，直到所有JNO检查完毕。可以将ALPHA语言转化为相应的SQL语句：select jno,jnamefrom jwhere not exists (select * from spj where spj.jno=j.jno and sno in (select sno from s where city=天津 )and pno in (select pno from p where color=红)另一种解法：不用in也可以实现：select jno,jnamefrom jwhere not exists (select * from s,p,spj where j.jno=spj.jno and s.sno=spj.sno and p.pno=spj.pno and city=天津 and color=红) 查询供应了1000个以上零件的供应商名称。(having)select sno,snamefrom swhere sno in (select sno from spj group by spj.sno having sum(qty)1000)b、 比较运算符：求重量大于所有零件平均重量的零件名称。select pnamefrom pwhere weight (select avg(weight) from p)c、 Exists连接谓词： 查询供应J1的所有的零件都是红色的供应商名称。即对spj中的每一个供应商做这样的检查：不存在这样的供应记录，该供应商给J1供应了某种零件，而这种零件不是红色的。满足这样条件的供应商输出。select sno,snamefrom swhere sno in(select distinct snofrom spj xwhere not exists (select * from spj y where y.sno=x.sno and y.jno=j1and not exists (select * from p where p.pno=y.pno and color=红) 至少用了供应商S1所供应的全部零件的工程号JNO。即对spj中的每一个工程做这样的检查：不存在零件使得供应商s1供应了该零件，而工程j没有选用该零件。select distinct jnofrom spj spjxwhere not exists (select * from spj spjy where sno=s1 and not exists (select * from spj spjz where spjz.pno=spjy.pno and spjz.jno=spjx.jno)（3） 分组查询：a、 求各种颜色零件的平均重量select color,AVG(weight)from pgroup by colorb、 求北京供应商和天津供应商的总个数select city, count(*) as numberfrom swhere city=北京 or city=天津group by cityc、 求各供应商供应的零件总数select sno, sum(qty)from spjgroup by snod、 求各供应商供应给各工程的零件总数select sno,jno, sum(qty) as qtyfrom spjgroup by sno,jnoe、 求使用了100个以上P1零件的工程名称。 select jno,sum(qty)as qty from spj where pno=p1 group by jno having sum(qty)100select jno,jnamefrom jwhere jno in (select jno from spj where pno=p1 group by jno having sum(qty)100)f、 求各工程使用的各城市供应的零件总数。select spj.jno,s.city,sum(qty)from spj,swhere s.sno=spj.snogroup by spj.jno,s.city实验四：视图的定义与使用（1） 定义如下视图：a、 查询北京的供应商的编号、名称和城市。create view s_bj(sno,sname,city) as (select sno,sname,city from s where city=北京)b、 查询S1供应商的所有供应明细。create view s1_spjas select sno,pno,jno,qty from spj where sno=s1c、 查询各工程名称使用的各种颜色零件的个数。create view jno_pcolor_qty(jno,color,qty)as select spj.jno,color,sum(qty)from p,j,spjwhere p.pno=spj.pno and j.jno=spj.jno group by spj.jno,colorcreate view jname_pcolor_qty(jname,color,qty)as select jname,color,qtyfrom j,jno_pcolor_qtywhere j.jno=jno_pcolor_qty.jno（2） 查询上面定义的视图。思考：上述哪些视图可以用来更新记录？select *from s_bjselect *from s1_spjselect *from jname_pcolor_qty实验五：触发器为S表的删除操作定义一个触发器，在删除一个供应商记录时，将这个供应商的所有供应情况从spj表中删除。思考：如何通过系统的设置实现类似的功能，而不需触发器？create trigger t_delSSpj on sfor deleteas begin delete from spj where spj.sno=(select sno from deleted)end思考：通过设置外键约束，并设置级联删除。实验六：编写一个存储过程，定义四个参数接收供应商的四个属性的值，然后插入S表中。创建：create proc p_insertS p_sno char(3), p_sname char(10), p_status int, p_city char(10)as insert into s(sno,sname,status,city) values(p_sno,p_sname,p_status,p_city)执行：exec p_insertS s10,耐火厂,20,洛阳删除：drop proc p_insertS
展开阅读全文