软件设计师考试复习笔记
（一）下午部分
一．数据流图设计
1. 逻辑数据流图与物理数据流图的区别：
逻辑数据流图说明应该具有那些加工而不关心这些加工是如何实现的；物理数据流图则要说明这些加工是如何实现的。
2.补充和完善数据流：
根据数据流平衡原则，即父图和子图的输入和输出流一致
每个加工至少有一个输入输出流
3.找出多余的文件：
如果一个文件仅仅作用于一个加工，即和该文件有关的输入和输出只涉及到一个加工，那么该文件可以作为局部文件出现在该加工的子图中，在父图中可以省略。如果没有细化图（子图），则不能省略。
普度鹿
二．数据库设计
1．SQL语句
exists （sql 返回结果集为真）
not exists (sql 不返回结果集为真）
如下：
表A
ID NAME
1 A1
2 A2
3 A3
表B
ID AID NAME
1 1 B1
2 2 B2
带两的成语
3 2 B3
表A和表B是１对多的关系 A.ID => B.AID
SELECT ID,NAME FROM A WHERE EXIST (SELECT * FROM B WHERE A.ID=B.AID) 执行结果为
1 A1
2 A2
原因可以按照如下分析
SELECT ID,NAME FROM A WHERE EXISTS (SELECT * FROM B WHERE B.AID=１) --->SELECT * FROM B WHERE B.AID=１有值返回真所以有数据
八只小狗抬花轿
SELECT ID,NAME FROM A WHERE EXISTS (SELECT * FROM B WHERE B.AID=2) --->SELECT * FROM B WHERE B.AID=２有值返回真所以有数据
SELECT ID,NAME FROM A WHERE EXISTS (SELECT * FROM B WHERE B.AID=3) --->SELECT * FROM B WHERE B.AID=３无值返回真所以没有数据
NOT EXISTS 就是反过来
SELECT ID,NAME FROM A WHERE NOT EXIST (SELECT * FROM B WHERE A.ID=B.AID)
执行结果为
3 A3
=====================================================================
======
EXISTS = IN，意思相同不过语法上有点点区别，好像使用IN效率要差点，应该是不会执行索引的原因
SELECT ID,NAME FROM A WHERE ID IN (SELECT AID FROM B)
NOT EXISTS = NOT IN ，意思相同不过语法上有点点区别
SELECT ID,NAME FROM A WHERE ID NOT IN (SELECT AID FROM B)
下面是普通的用法：
SQL中IN,NOT IN,EXISTS,NOT EXISTS的用法和差别:
刻骨相思IN：确定给定的值是否与子查询或列表中的值相匹配。
IN 关键字使您得以选择与列表中的任意一个值匹配的行。
当要获得居住在 California、Indiana 或 Maryland 州的所有作者的姓名和州的列表时，就需要下列查询：
SELECT ProductID, ProductName FROM Northwind.dbo.Products WHERE CategoryID = 1 OR CategoryID = 4 OR CategoryID = 5
然而，如果使用 IN，少键入一些字符也可以得到同样的结果：
SELECT ProductID, ProductName FROM Northwind.dbo.Products WHERE CategoryID IN (1, 4, 5)
IN 关键字之后的项目必须用逗号隔开，并且括在括号中。
下列查询在 titleauthor 表中查找在任一种书中得到的版税少于 50% 的所有作者的 au_id，然后从 authors 表中选择 au_id 与
titleauthor 查询结果匹配的所有作者的姓名：
SELECT au_lname, au_fname FROM authors WHERE au_id IN (SELECT au_id FROM titleauthor WHERE royaltyper <50)
结果显示有一些作者属于少于 50% 的一类。
NOT IN：通过 NOT IN 关键字引入的子查询也返回一列零值或更多值。
以下查询查找没有出版过商业书籍的出版商的名称。
SELECT pub_name FROM publishers WHERE pub_id NOT IN (SELECT pub_id FROM titles WHERE type = 'business')
使用 EXISTS 和 NOT EXISTS 引入的子查询可用于两种集合原理的操作：交集与差集。
两个集合的交集包含同时属于两个原集合的所有元素。
差集包含只属于两个集合中的第一个集合的元素。
EXISTS：指定一个子查询，检测行的存在。
本示例所示查询查找由位于以字母 B 开头的城市中的任一出版商出版的书名：
SELECT DISTINCT pub_name FROM publishers WHERE EXISTS (SELECT * FROM titles WHERE pub_id = publishers.pub_id AND type =
'business')
SELECT distinct pub_name FROM publishers WHERE pub_id IN (SELECT pub_id FROM titles WHERE type = 'business')
两者的区别:
EXISTS：后面可以是整句的查询语句如:SELECT * FROM titles
IN：后面只能是对单列:SELECT pub_id FROM titles
NOT EXISTS:
例如，要查找不出版商业书籍的出版商的名称：
SELECT pub_name FROM publishers WHERE NOT EXISTS (SELECT * FROM titles WHERE pub_id = publishers.pub_id AND type =
'business')
下面的查询查找已经不销售的书的名称:
SELECT title FROM titles WHERE NOT EXISTS (SELECT title_id FROM sales WHERE title_id = titles.title_id)
B. 比较使用 EXISTS 和 IN 的查询
这个例子比较了两个语义类似的查询。第一个查询使用 EXISTS 而第二个查询使用 IN。注意两个查询返回相同的信息。
USE pubs
GO
SELECT DISTINCT pub_name
FROM publishers
WHERE EXISTS
(SELECT *
FROM titles
WHERE pub_id = publishers.pub_id
AND type = \'business\')
GO
-- Or, using the IN clau:
USE pubs
GO
SELECT distinct pub_name
FROM publishers
WHERE pub_id IN
(SELECT pub_id
FROM titles
WHERE type = \'business\')
GO
下面是任一查询的结果集：
pub_name
-
---------------------------------------
Algodata Infosystems
New Moon Books
E. 使用 NOT EXISTS
圣节NOT EXISTS 的作用与 EXISTS 正相反。如果子查询没有返回行，则满足 NOT EXISTS 中的 WHERE 子句。本示例查找不出版商业书籍的出版商的名称：
USE pubs
GO
SELECT pub_name
FROM publishers
WHERE NOT EXISTS
(SELECT *
FROM titles
WHERE pub_id = publishers.pub_id
AND type = \'business\')
ORDER BY pub_name
GO
2. 范式
A．1NF：满足二维表的的关系模式
B：2NF：满足1NF，且不存在非主属性对于候选码的部分依赖
分解方法：用候选码的每个非空子集作为新的候选码构造子表
再将依赖于新候选码的属性放置到该码所在的表中
C：3NF：不存在传递依赖
分解方法：删除传递依赖于别人的属性，将被删除的属性与其直接依赖的决定因子放置在一起组成新表
D：BCNF：每个决定因子都是候选码（满足1，2，3范式）
三．UML设计金黄色葡萄球菌是什么病
1．用例图间关系：包含，扩展
2．类图间关系： 依赖表示类之间的使用关系 虚线+箭头
泛化表示一般与特殊的关系 直线+空心三角
聚集是特殊的关联，表示整体与部分的关系 直线+空心菱形
组合是很强的关联，而且整体与部分的生存周期是一致的
直线+实心菱形
实现 接口 虚线+空心三角
四．程序流程图（可不用复习）
五．算法设计
1.指针：一个存储地址的变量：一个存储地址的变量
2.数组名存储的是，的是，
数组在申请空间时数组名存储该存储空间的首地址，因此也是指针。当直接输出数组名是，其实是输出的是数组的首地址。可以用指针的方式访问数组。
3.C 语言中，当形参是普通变量时，传递的是实参的值，当形参是指针时，传递的是指针变量的值，但自身的改变不会传递给实参。量的值，但自身的改变不会传递给实参。
4.线性表：
除第一个外，集合中每个数据元素均有且仅有一个前驱，除最后一个外，集合中每一个元素都有且仅有一个后继。线性表的节点一定是同一类型的数据。
森林防火责任书5.顺序存储：
曾子杀猪逻辑关系上相邻的两个元素在物理位置上也是相邻。
A 的存储位置计算公式：loc(ai)=loc(a1)+(i-1)*1
顺序存储的缺点：
线性表的大小固定，浪费大量的存储空间，不利于节点的增加或减少；执行线性表的插入和删除操作要移动其他元素，不够方便。 6.链式存储：单链表 循环链表 双向链表双向链表
线性表链式存储用链表存储线性表，头指针指向第一个节点。
缺点：由于要存储地址指针，浪费空间
7.队列：
一种先进先出(FIFO)的线性表，队列只允许在一端（对尾）进行插入，另一端（对首）进行删除运算的线性表。
8．栈：
仅在表尾进行插入或删除的一种LIFO 线性表。表尾是栈顶，表头是栈底。
9.构造哈夫曼树：
定义：
树的带权路径最短的树（树中所有叶子节点的带权路径长度之和） 构造方法：
每次挑选两个根节点最小的树作为左右子树构造一棵新的二叉树，且设树的根节点的权为左右子树根节点的权的和，新形成的二叉树又参与下一轮的挑选（挑选两个根节点最小的树）。
10.哈夫曼编码：
