一、用逻辑符号形式化下列语句
1．每个人的指纹都不相同。
设M(x):x是人 N(x,y):x≠y,即x与y时不同的人；E(x,y):x与y的指纹相同
2．自然数不是奇数就是偶数，且奇数不能被2整除。
设 P(x)：x 是自然数，Q(x)：x 是奇数，R(x)：x 是偶数，D(x)：x 能被2整除
二、填空题
1．设 A、B 均为有穷集合，A 和 B 的基数分别是 m 和 n（m>0,n>0）。
（1）当 m 和 n 满足 m=n 时，存在从 A 到 B 的双射函数。此时共可生成（n!）个不同的双射函数。
（2）当 m 和 n 满足 m≤n 时，存在从 A 到 B 的单射函数。此时共可生成（）个不同的单射函数。
2．已知 5 位老师和 3 位学生围圆桌就座,如果要求学生两两不相邻,则有（1440）种就座方案。
3．整除 2310 的正奇数有（）个。
的形式，其中a,b,c,d=0,1
4. 设 图 G 的 顶 点 集 合 为 V(G)={ V1,V2,V3,V4 } ， 边 集 合 为 E(G)={ V1V2,V2V3,V3V4 ,V4V1,V1V3 }。则 G 的生成树有（8）棵。
解析：该题先画图，接着用破圈法变成生成树，删除可以分为两个部分一部分包含边
，另一部分不包含。包含该边的有,不包含的有
,因此总共有8棵树。
三、解答题（本大题共 3 小题，第 1、2 小题每题 4 分，第 3 小题 8 分，共16分）
1．设 P↓Q = ¬(P∨Q)，仅用联结词↓分别表示出¬P，P∧Q，P∨Q。
2．设 T 是一棵有 13 个顶点的树，称树中度为 1 的顶点为叶子。如果 T 的顶点的度只可能是 1,2,5 且 T 恰好有 3 个度为 2 的顶点，那么，T 中有多少个叶子？
解析：设T 中有 x 个叶子，则T 中有 13 - 3 - x = 10-x 个度为 5 的顶点，
由于树中的边数等于顶点个数减去 1，即边数为 12
由顶点度数之和等于边数的两倍得 x + 3*2 + 5*(10-x) = 12 * 2 = 24
解得 x = 8，故 中有8个叶子。
3．求 1,4,5,8,9 这五个数字组成的位数的个数，要求 4,8 出现的次数均为偶数,而1,5,9 出现的次数不加限制。
解析：设满足条件的 i 位数的个数为 ，则序列
对应的指数型母函数为
==
故
四、证明题（本大题共 2 小题，第 1 小题 4 分，第 2 小题 6 分，共 10 分）
1．设R 是非空集合 A 上的二元关系，R 满足条件：
（1）R 是自反的；
（2）若<a，b>∈R ∧<a，c>∈R，则<b，c>∈R；
试证明 R 是 A 上的等价关系
证明：由条件（1），R已满足自反性，需证明R满足对称性和传递性
1）对于任意的且由条件（1）
由条件（2）
所以，R满足对称性
2）对于任意的
由对称性
由条件（2）
所以，R满足传递性。综合1），2）可得，R是A上的等价关系
2．随意地把一个 9×3 棋盘的每个方格涂成红色或蓝色， 求证：必有两行方格的涂色是一样的。
第一列9个格，用红蓝两色染可以有2*2*2=8种染法，意思是如果有8列可以做到每列染色方式都不同，但是它有9列，鸽笼原理，必有两列染色法是一样的。
计算机网络
一、单项选择题（本大题共 10 小题，每小题 1 分，共 10 分）
1．下面对计算机网络体系结构中协议所做的描述，（C ）是错误的。
A．网络协议的三要素是语法、语义和同步
B．协议是控制两个对等层实体之间通信的规则的集合
C．在 OSI 参考模型中，要实现第 N 层的协议，需要使用 N＋1 层提供的服务
D．协议规定了对等层实体之间所交换的信息的格式和含义
2．若数据链路层采用回退 N（go-back-N）滑动窗口协议，发送帧的序号用 7bit表示，发送窗口的最大值为（ C）。
A．7
B．64
C．127
D．128
3．以太网中采用二进制指数后退算法处理发送冲突问题，下列数据帧中重传时再次发生冲突概率最低的是（ D）。
A．首次重传的帧
B．发生两次冲突的帧
C．发生三次冲突的帧
D．发生四次冲突的帧
解：根据 IEEE802．3 标准的规定，以太网采用二进制指数后退算法处理冲突问题。在由于检测到冲突而停止发送后，一个站必须等待一个随机时间段，才能重新尝试 发送。这一随机等待时间是为了减少再次发生冲突的可能性。等待的时间长度按下列步骤计算：
1)取均匀分布在 0 至 2min(km)之间的一个随机整数 r、k 是冲突发生的次数。
2)发送站等待 r×2t 长度的时间才能尝试重新发送，其中 t 为以太网的端到端延迟。
从这个计算步骤可以看出，k 值越大，帧重传时再次发生冲突的概率越低。
4．采用二层以太网交换机扩展局域网，（B ）是错误的。
A.二层以太网交换机的各个端口可以支持不同的速率
B.二层以太网交换机可以隔离广播帧
C.二层以太网交换机需要对收到的数据帧进行处理，增加了传输时延
D.二层以太网交换机在转发帧时不改变帧的源地址
5．在采用（ C）的传输方式下，由网络负责差错控制和流量控制，分组按顺序被交付。
A．电路交换26
B．报文交换
C．虚电路分组交换
D．数据报分组交换
6．对于 IP 分组的分段和重组，（ B）是正确的。
A.IP 分组可以被源主机分段，并在中间路由器进行重组
B.IP 分组可以被路径中的路由器分段，并在目的主机进行重组
C.IP 分组可以被路径中的路由器分段，并在中间路由器上进行重组
D.IP 分组可以被路径中的路由器分段，并在最后一跳的路由器进行重组
7．假定一台主机的 IP 地址是 180.120.74.56，子网掩码为 255.255.240.0，则该子网地址为（B）。
A．180.120.0.0
B．180.120.64.0
C．180.120.72.0
D．180.120.74.0
解：74 =01001010
240=11110000
64 =01000000
8．在 Internet 上，主机采用（ ）标识，运行在主机上的应用程序用（D）标识。
A．端口号主机地址
B．主机地址 IP 地址
C．IP 地址主机地址
D．IP 地址端口号
9．当客户端请求域名解析时，如果本地 DNS 服务器不能完成解析，就把请求发送给其他服务器，依次进行查询， 直到把域名解析结果返回给请求的客户端。 这种方式称为（B ）。
A．迭代解析
B．递归解析
C．迭代与递归相结合的解析
D．高速缓存解析
10．在信息安全领域，使用（A）方法可以使通信的接收方验证收到报文是否受到篡改和伪造。
A．数字签名
B．数据加密
C．防火墙
D．身份认证
二、名词解释（本大题共 2 小题，每小题 3 分，共 6 分）
1．自治系统 AS（autonomous system）
指具有单一管理权限（或独立行政单位管辖下）的网络和路由器；
采用AS 内部网关协议（域内路由选择协议）确定分组在 AS 内的路由；
采用外部网关协议（域间路由选择协议）处理分组在 AS 之间的路由
2．慢启动（slow start）
答：TCP 进行拥塞控制的一种方法；使拥塞窗口在初始时大小为 1（1 个最大报文段长度），每收到一个 ACK 应答（对新报文段的确认），拥塞窗口增 1，逐步增加拥塞窗口大小。
三、问答和计算题（本大题共 4 小题，共 14 分）
1．试说明以太网规定的最短帧长是多少？为什么要限制最短帧长？
答：以太网定义最短帧长为 64 字节。最短长度的限制与以太网 MAC 层的CSMA/CD 协议有关。以太网在发送数据帧时能够检测到冲突并停止发送。如果帧长度过短，在检测到冲突之前帧已经发送完毕，则协议无法进行有效冲突检测
2．试说明 TCP 协议是如何提供端到端可靠的传输服务的？
答：TCP 协议是面向连接的协议；可靠建立连接（也可答三次握手建立连接）和终止连接；采用滑动窗口协议进行流量控制和差错控制。
3．考虑一条带宽为 1.6Mbps 的链路，往返传播时延为 45ms，假设数据帧的大小为1KB。若采用滑动窗口协议来保证链路的利用率，允许发送方在收到应答之前尽量连续发送多帧。那么，至少需要多少位作为序号？（忽略确认帧大小和接收处理开销）
答：发送一帧所需时间 t1 = 1KB*8/1.6Mbps = 5ms RTT=45ms 若使用滑动窗口协议，可连续发送帧数：1＋45/5=10 帧，24>10>23，因此，至少使用 4 位序号
4．如下图所示的网络中，采用距离向量路由算法进行路由选择。假设路由器 C 在启动时，测得与相邻路由器 A、B 的时延分别为 7，14。此后，路由器 C 分别收到来自相邻路由器发出的路由向量：B(15，0，4，6)，A(0，3，12，16)。上述向量表示发送该向量的路由器分别与网络中路由器 A、B、C、D 之间的时延。 计算路由器 C 在收到相邻路由器发出的向量后，更新的路由表是什么？
答：收到路由向量：A（0，3，12，16） B（15，0，4，6）， C 更新后的路由表（分别到 A,B,C,D 的路由向量）：（（7，A），（10，A），（ 0，－），（20，B））
第三部分 软件工程
一、单项选择题（本大题共 5 小题，每小题 1 分，共 5 分）
1．软件开发的需求活动，其主要任务是（ D）。
A．给出软件解决方案
B．给出系统模块结构
C．定义模块算法
D．定义需求并建立系统模型
2．软件总体设计结束后得到（ B）。
A．初始化的软件结构图
B．优化的软件结构图
C．模块的算法
D．程序编码
3．面向对象分析方法与结构化分析方法的区别之一是（B ）。
A．一个使用了“抽象”，而另一个没有使用“抽象”
B．一个以问题域的成分为基点来构造一个模块，而另一个不是
C．一个目标明确，而另一个目标不明确
D．一个需要考虑数据结构，而另一个不需要考虑数据结构
4．确定测试的计划是在（A）阶段制定的。
A．需求分析
B．详细设计
C．编码
D．测试
5．按不同人员的工作内容来分类软件过程，基本过程包括（ C）。
A．维护过程和改进过程等
B．开发过程和改进过程等
C．获取过程和供应过程等
D．改进过程和裁减过程等
二、判断题（本大题共 5 小题，每小题 1 分，共 5 分。如果正确，用“√”表示， 否则，用“×”表示）
1．在软件开发方法中，结构化方法总的指导原则是自顶向下、逐步求精。（√ ）
2．当一个模块直接修改另一个模块的数据时，模块间的这种耦合称为数据耦合（ ×）
模块间通过参数传递基本类型的数据，模块间的这种耦合称为数据耦合
3．测试用例只需选用合理的输入数据。（× ）
S 解：测试用例要包括 欲测试的功能、应输入的数据和预期的输出结果。测试数据应该选用少量、高效的测试数据进行尽可能完备的测试
4．边界值分析法是一种白盒测试法。（ ）
S 解：七种黑盒测试方法：等价类划分法、边界值法、错误推测法、因果图法、判定表法、状态迁移法、正交实验法
5．关联是建立类之间关系的一种手段。（ √ ）
S 解：UML 图中类之间的关系：依赖，泛化，关联，聚合，组合，实现
三、简答题（本大题共 3 小题，每小题 4 分，共 12 分）
1．给出模块耦合的定义，并举例说明 3 种模块耦合
答：耦合是对不同模块之间相互依赖程度的度量。一般地，模块耦合可分为：
1）内容耦合：当一个模块直接修改或操作另一个模块的数据时，模块间的这种耦合称为内容耦合。
2）公共耦合：当两个以上的模块共同引用一个全局数据项时，模块间的这种耦合称为公共耦合。
3）控制耦合：一个模块在界面上传递一个信号控制另一个模块，接收信号的模块的动作根据信号值进行调整，模块间的这种耦合称为控制耦合。
4）标记耦合：当两个模块至少有一个通过界面传递的公共参数时，模块间的这种耦合称为标记耦合。
5）数据耦合：当模块间通过参数传递基本类型的数据时，模块间的这种耦合称为数据耦合。
（给出任意 3 种模块耦合，得 3 分，其中每种耦合 1 分）
2．将下面的伪码转换成 N-S 图和 PAD 图。
3．给出 CMM 的 5 级模型，并以其中一个 CMM 等级为例，列出该等级包含的关键过程域。
初始级 可重复级 已定义级 已管理级 持续优化级
（1） 可重复级的关键过程域包括（6 个）：
软件配置管理，软件质量保证，软件子合同管理，软件项目跟踪和监督，软件项目规划，需求管理。
（2） 已定义级的关键过程域包括（7 个）：
同行复审，组间协作，软件产品工程，集成的软件管理，培训计划，组织过程定义，组织过程焦点。
（3）已管理级的关键过程域包括（2 个）：软件质量管理，量化的过程管理。
（4）持续优化级的关键过程域包括（3 个）：过程变化管理，技术变化管理，缺陷预防
四、建模题（本大题共 3 小题，共 8 分）
问题陈述：在一简化的某学校图书管理系统中，
库房管理员职责：
根据各系的要求负责购买图书，并为新书编制图书卡片（分类目录号、流水号、 书名、作者、价格、购书日期）， 写入图书目录文件。
图书管理员职责：
根据借还书的要求负责借还图书处理：
（1）当没有要借的图书时，向借阅人发无书通知；
（2）当借阅人将图书丢失时，以图书丢失单的形式报告图书管理员，由图书管理员下罚款单给借阅人；同时图书管理员负责修改图书目录文件，并通知库房管理员。
图书馆主任职责：
每月末根据分类目录号查看某种图书库存量，当库存量低于库存下限时，通知库房管理员购书。
1．（ 3 分）用结构化分析方法给出该系统的顶层 DFD（系统环境图）；
2．（ 2 分）给出顶层 DFD 的数据字典；
入库单＝分类目录号＋流水号＋书名＋作者＋价格＋购书日期
借还书的要求＝[借书信息|还书信息]
借书信息＝[书名|作者]＋借书日期
还书信息＝书名＋还书日期
图书丢失单＝图书流水号＋借阅人
图书证号丢失报告单＝书名＋分类目录号＋图书流水号
无书通知单＝借阅人图书证号＋无书信息
罚款单＝借阅人图书证号＋罚款金额
查看要求＝分类目录号
月末库存量＝{分类目录号＋书名＋库存量}
购书通知＝分类目录号＋书名＋购买量
3．（ 3 分）选择该图书管理系统中的一个交互，并用顺序图来描述
