一、用逻辑符号表达下列语句（共 3 分，第 1 题 1 分，第 2 题 2 分）
1.（1 分）有且有一个太阳
全域：全部天体 P(x)表示 x 为太阳；Q(x,y)表示 x 与 y 相等，则：
∃x∀y(P(x)∧(P(y)→Q(x,y)))
2.（2 分）任意两个相异实数 x,y 之间必可找到另一个实数 z.
全域：全体实数 R(x): x 为实数 则原句可形式化为：∀x∀y(R(x)∧R(y) ∧ x ≠ y→∃z(R(z) ∧ (x<z<y∨y<z<x))或设R(x): x为实数N（x,y):x≠y G(x,z,y):x<z<y则原句可形式化为：∀x∀y(R(x)∧R(y)∧N(x,y) →∃ z(R(z) ∧ (G(x,z,y)∨G(y<z<x)))
二、填空题（共 9 分）
1、（2 分）设 A=[1，2，3，4]，则在 A 上的二元关系共有（ ）个；其中有（ 15 ）个是等价关系。
2、（1 分）设︱A︱=n (即集合 A 的基数为 n), 则在 A 上有() 个不同的对称关系。
3、（2 分） 的展开式经过合并同类项后有 (15) 项。C(6,2)
4、（2 分）标有 1、2、3、4 的四张数字卡片，要求数 1 不排在千位上，数 2 不排在百位上，数 3 不排在十位上，数 4 不排在个位上，那么用这四张卡片组成的满足要求的四位数共( 9 )个
完全错排= 9
5、（2 分）以三种不同的颜色来给某房间的四个墙壁着色， 房间的地面为长方形（如下图所示）， 每个墙壁只着一种颜色，任何相邻的两个墙壁的颜色都不同，共有 （18 ）种着色方案。
容斥原理
：|A̅∩B̅∩C̅∩D̅|= |S|-|A∪B∪C∪D|
=|S|-|A|-|B|-|C|-|D|+|A∩B|+|A∩C|+|A∩D|+|B∩C|+|B∩D|+|C∩D|-|A∩B∩C|-|A∩B∩D|-|A∩C∩D|-|B∩C∩D|+|A∩B∩C∩D|
=
= 18
三、问答题（6 分）
有 r 个正方形排成一行，今用红、黄、白、蓝四种颜色给这个 r 个正方形染色，每个正方形只能染一种颜色，如果要求染红、黄、白色的正方形分别至少出现一个，问有多少种不同的染法？
解：指数型母函数
四、证明（共 22 分）
1、（3 分）下列等值式是否正确，如正确请证明，如错误请举出反例
(∀x)(∀y)(P(x) ∧ P(y) → Q(x, y)) = ¬(∃ x)(∃ y)(P(x) ∧ P( y) ∧ ¬Q(x, y))
解：(∀x) (∀y) (P(x)∧P(y) →Q(x,y))
=((∃x) (∃y) (P(x)∧P(y))) →Q(x,y)) 量词辖域收缩等值式
=¬((∃x) (∃y) (P(x)∧P(y))) ∨Q(x,y)) 蕴含等值式
=¬((∃x) (∃y) (P(x)∧P(y))) ∨¬¬Q(x,y))
=¬((∃x) (∃y) (P(x)∧P(y))) ∧¬Q(x,y)) 德摩根等值式
2、（3 分）设 f: R×R→R , f(x,y)=x+y; g: R×R→R, g (x,y)=x×y
证明：(1) f 是满射的，但不是单射的。
(2) g 是满射的，但不是单射的。
证 ：(1)对于任意的 b∈R，存在<0,b>∈R×R，满足 f(0,b)=0+b=b 因此 f 是满射的。但由于 f(0,1)= f(1,0)=1，因此 f 不是单射的。
(2)对于任意的 b∈R，存在<1,b>∈R×R，满足 g(1,b)=1×b=b 因此 g 是满射的。但由于 g(0,1)=g(1,0)=0，因此 f 不是单射的。
3、（4 分）设 G 是一个有 n 个结点 m 条边的连通简单平面图，若 n≥3, 则 m≤3n－6
证明：设 G 有 k(k 1)个连通分支,若 G 为树或森林,则 m=n-k
3n-6(n
3)，若G 不是树也不是森林，则 G 中必含圈，又因为 G 是简单图,所以各圈的长度均大于或等于 3，因各面次数至少为 l(l≥3),又
在 l =3 时达到最大值。
4、（4 分）证明：任何连通简单平面图至少有一个结点的度数不超过5
证 ：假设每个结点度数都大于6，则∑𝑑(𝑣𝑖) >= 6n，由握手定理可知：2m = ∑𝑑(𝑣𝑖) >= 6n。因而 m≥3n，G 是简单平面图 m≤3n－6 即m+6≤3n，与上题结论矛盾，问题得证
计算机网络
一、单项选择题（共 8 分，每小题 1 分）
1、网络协议的三要素为（ C）
A.数据格式、编码、信号电平
B.数据格式、流量控制、拥塞控制
C.语法、语义、同步
D.编码、控制信息、同步
2、下列功能中，属于表示层提供的功能是（C）
A．拥塞控制
B．透明传输
C．死锁处理
D．文本压缩
3、下一代互联网核心协议 Ipv6 的地址长度为（D）比特。
A．32
B．48
C．64
D．128
4、采用 8 种相位，每种相位各有两种幅度的 QAM 调制方法，在 2400Baud 的信
号传输速率下能达到的数据传输速率为（C）bit/s
A．2400
B．4800
C．9600
D．19200
本题中有 8 种相位，每种相位各有两种幅度，共 16 个状态，所以也是 4 位/波特。由于
是 2400Baud 的信号传输速率，因此数 据传输速率为 9600bit/s。
5、ARP 协议通过广播方式完成（C）的映射。
A ．从域名到 IP 地址
B．从网卡地址到 IP 地址
C．从 IP 地址到网卡地址
D．从 IP 地址到域名
6、在因特网电子邮件系统中，电子邮件应用程序（B ）。
A．发送邮件和接受邮件通常都使用 SMTP 协议
B．发送邮件通常使用 SMTP 协议，而接收邮件通常使用 POP3 协议
C．发送邮件通常使用 POP3 协议，而接收邮件通常使用 SMTP 协议
D．发送邮件和接受邮件通常都使用 POP3 协议
7、以下各项中，数据报服务是（B ）。
A．面向连接的、可靠的、保证分组顺利到达的网络服务
B．面向无连接的、不可靠的、不保证分组顺利到达的网络服务
C．面向连接的、不可靠的、保证分组顺利到达的网络服务
D．面向无连接的、可靠的、不保证分组顺利到达的网络服务
8 、 在 某 一 个 子 网 中 给 以 下 四 台 主 机 分 配 IP 地 址 （ 子 网 掩 码 均 为 255.255.255.244） ,其中一台因 IP 地址分配不当 而存在通信故障，这台主机 IP 地址为（ A）
A． 200.10.1.60
B． 200.10.1.65
C． 200.10.1.70
D． 200.10.1.75
244:1111
60:0011
65:0111
75:0111
二、名词解释（共 6 分，每小题 2 分）
1、路由协议 RIP
路由信息协议 RIP 是一种分布式的基于距离向量的路由选择协议，是因特网的标准协议，其最大优点就是简单。但 RIP 只能允许一条路径包含 15 个路由器， 因此只适用于小型互联网
2、虚拟局域网 VLAN
VLAN（Virtual Local Area Network ）又称虚拟局域网，是指在交换局域网的基础上，采用网络管理软件构建的可跨越不同网段、不同网络的端到端的逻辑网络。一个 VLAN 组成一个逻辑子网，即一个逻辑广播域，它可以覆盖多个网络设备，允许处于不同地理位置的网络用户加入到一个逻辑子网中。 VLAN是建立在物理网络基础上的一种逻辑子网，因此建立 VLAN 需要相应的支持VLAN 技术的网络设备。当网络中 的不同 VLAN 间进行相互通信时，需要路由的支持，这时就需要增加路由设备——要实现路由功能，既可采用路由器，也可采用三层交换机来完成。使用 VLAN 具有以下优点：①控制广播风暴； ②提高网络整体安全性；③网络管理简单、直观。
3、防火墙
防火墙是一种网络安全的防范措施，其工作方式是将内联网络与因特网之间或与其他外联网络之间互相隔离，通过访问 控制的方式来保护内联网络。设置防火墙的目的是为了在内联网与外联网之间设立唯一的通道， 简化网络的安全管理
三、简答和计算题（共 16 分）
1、简述以太网设备二层交换机与三层交换机的区别。
二层交换技术是发展比较成熟，二层交换机属数据链路层设备，可以识别数据包中的 MAC 地址信息，根据 MAC 地址 进行转发，并将这些 MAC 地址与对应的端口记录在自己内部的一个地址表中。二层交换机用于小型的局域网络。 在小型局域网中，广播包影响不大，二层交换机的快速交换功能、多个接入端口和低谦价格为小型网络用户提供 了很完善的解决方案。三层交换机的最重要的功能是加快大型局域网络内部的数据的快速转发，加入路由功能也是为这个目的服务的。如果把大型网络按照部门，地域等等因素划分成一个个小局域网，这将导致大量的网际互访，单纯的使用二层交换机不能实现网际互访；如单纯的使用路由器，由于接口数量有限和路由转发速度慢，将限制网络的速度和网络规模,采用具有路由功能的快速转发的三层交换机就成为首选
2、说明传输层协议 TCP 在建立连接时为什么要使用三次握手。
为确保连接的建立和终止都是可靠的，TCP 使用三次握手的方式，科学家们已证明三次握手是在包丢失、重复 和延迟的情况下确保非模糊协定的充要条件
3、长度为 1 公里、数据传输率为 10Mbps 的 CSMA/CD 以太网，信号传播速度为 200m/us.试求能够使该网络正常运行的最小帧长。
对于 1 公里电缆，单程传播时间为 。往返传播时间为
为了能够按照 CSMA/CD 工作，最小帧的发射时间不能小于 10。帧长=速率*时间，故以 10Mbps 速率工作，10us 可以发送的比特数等于：
比特
4、使用电话线拨号方式传输 1M 字节大小的文件，其中 Moden 的数据传输率为2400bps.若以异步方式传送，采用 1 位起始位和 1 位停止位，则最少需要多少时间（以秒为单位）才能将该文件传输完毕？（假设线路传播延迟、误码率、网络层以上开销均忽略不计）
4. 答：信息传输速率：2400*(8+1+1)=24000b/s
传输 1M 字节大小的文件需要的时间为：=43.69
5、（4 分）某单位内有 4 个局域网通过一台四个端口的路由器（支持可变长子网掩码 VLSM）连接，一个端口连接一个局域网，每个局域网的主机数分别是 120 台、60 台、26 台、25 台。
每个部门分配一个子网，名义上部门 A、B、C、D 的子网大小分别是： IP 地址的最高位是 0 表示子网 A，
最高两位是 10 表示子网 B，最高三位是 110 表示子网 C，最高三位是 111 表示子 网 D 。 显 然 这 里 采 用 了 可 变 长 子 网 掩 码 , 涉 及 3 种 子 网 掩 码 , 分 别 是255.255.255.128;255.255.255.192; 255.255.255.224
因此 IP 地址范围和子网掩码分配方式如下：
192.101.116.1~126/255.255.255.128
192.101.116.129~190/255.255.255.192
192.101.116.193~222 /255.255.255.224
192.101.116.225~254 /255.255.255.224
软件工程
一、单项选择题（每小题 1 分，共 5 分）
1、软件的正确性是指（B ）
A．软件产品能正常运行
B．软件产品达到预期功能的程度
C．软件产品符合用户的要求
D．软件产品运行中不出现任何错误
2、软件开发模型是（B ）
A．瀑布开发方法
B．以活动对软件开发的一种分解
C．瀑布模型
D．一种软件过程
3、结构化分析方法中的主要概念有（D ）
A．摸块内聚和耦合
B．对像及类
C．摸块和信息隐蔽
D．加工、数据流和数据源等
4、软件测试目标是（B ）
A．证明软件是正确的
B．发现错误，降低错误带来的风险
C．排除软件中的所有错误
D．与软件调试相同
5、软件过程是（D ）
A．特定的开发模型
B．一种软件求解的计算逻辑
C．活动的集合
D．软件生存周期模型
二、判断题（如果正确，用”√”表示；否则，用”×”表示。每题 1 分，共 5 分）
1、在软件生命周期中的软件工程活动包括性能优化。（√ ）
2、两个模块共同引用一个全局数据项，模块间的这种耦合称为数据耦合。（×）
3、白盒测试技术和黑盒测试技术都基于程序的逻辑结构。（× ）
4、ISO9000-3 是 ISO9003 的一个子集。（ ×）
解：ISO9001 质量体系是在软件设计、开发、生产、安装和维护时的质量保证的参考文件。此标准应用于所有软件产品 和满足各种技术需求的软件维护活动中。它是评价软件质量的首要标准。ISO9000-3 是对 ISO90001 进行改造后，将其应 用到软件工业中对软件开发、供应和维护活动的知道文件。ISO9003:1994 《质量体系最终检验和试验的质量保证模式》适用于汇编及测试运行情况的标准。 目前已经不再使用。
5、在对象的整个生命周期中，不同的对象可以具有相同的标识。（ × ）
解：每个对象都有自身唯一的标识，通过这种标识，可找到相应的对象。在对象
的整个生命期中，它的标识都不改变，不同的对象不能有相同的标识。
三、简答题（每小题 4 分，共 12 分）
1、给出模块内聚的定义，并举例说明 3 种模块内聚。
答：内聚按强度从低到高有以下几种类型：
（1）偶然内聚。如果一个模块的各成分之间毫无关系，则称为偶然内聚。
（2）逻辑内聚。几个逻辑上相关的功能被放在同一模块中，则称为逻辑内聚。如一个模块读取各种不同类型外设的输入。 尽管逻辑内聚比偶然内聚合理一些，但逻辑内聚的模块各成分在功能上并无关系， 即使局部功能的修改有时也会影响全局，因此这类模块的修改也比较困难。
（3）时间内聚。如果一个模块完成的功能必须在同一时间内执行（如系统初始化）， 但这些功能只是因为时间因素关联在一起，则称为时间内聚。
（4）过程内聚。如果一个模块内部的处理成分是相关的，而且这些处理必须以特定的次序执行，则
称为过程内聚。
（5）通信内聚。如果一个模块的所有成分都操作同一数据集或生成同一数据集，则称为通信内聚。
（6）顺序内聚。如果一个模块的各个成分和同一个功能密切相关，而且一个成分的输出作为另一个成分的输入，则称为顺序内聚。
（7）功能内聚。模块的所有成分对于完成单一的功能都是必须的，则称为功能内聚。
2、将下面给出的伪码转换为 N-S 图和 PAD 图。
Begin 输入 10 个数到 a[1] a[10]；
sum=0;
max=0;
n=1;
while n＜＝10 do
begin
sum=sum+a[n];
n=n+1 end;
输出 sum 和 max end;
3、给出 CMM 中关键过程域的定义，并举例说明两个关键过程域。
关键过程域：指明组织改善软件过程能力应关注的区域，并指出为了达到某个成熟度等级所要着手解决的问题。达到一个成熟度等级，必须实现该等级上的全部关键过程域。每个关键过程域包含了一系列的相关活动，当这些活动全部完成时，就能够达到一组评价过程能力的成熟度目标。要实现一个关键过程域，就必须达到该关键过程域的所有目标
可重复级：软件配置管理，软件质量保证，软件子合同管理，软件项目跟踪和监督，软件项目规划，需求管理
已定义级：对等复审，组间协作，软件产品工程，集成的软件管理，培训计划，组织过程定义，组织过程焦点
已管理级：软件质量管理，量化的过程管理
持续优化级：过程变化管理，技术变化管理，缺陷预防
四、建模题（8 分）
问题陈述：已知在一个简化的教学管理信息系统中，分工如下：
教务员负责：
录入教师教学信息（姓名，工作证号，课程名，总学时，上课地点，上课时间）；
录入教师缺课情况（姓名，工作证号，缺课时间，原因）；
教学秘书负责：
录入学生各科成绩（姓名，学号， [课程名，成绩]）。
教学主任负责：
每学期统计每一个教师的工作量（姓名，工作证号，上课学时数）； 每学期统计每一个学生的不及格课程（姓名，学号，﹛不及格课程名，成绩，补考时间，补考地点﹜），若大于 2 门，则给学生发降级通知（姓名，学号）。
要求完成：
1、（3 分）用结构化分析方法给出该系统的顶层 DFD（系统环境图）。
2、（2 分）给出上述顶层 DFD 的数据字典。
教师教学信息=姓名+工作证号+课程名+总学时+上课地点+上课时间
教师缺课情况=姓名+工作证号+缺课时间+原因
学生成绩=姓名+学号+课程名+成绩
学期教师工作量统计=姓名+工作证号+上课学时数
学期学生不及格课程统计=姓名+学号+不及格课程名+成绩+补考时间+补考地点
学生降级通知=姓名+学号
3、（3 分）定义一个交互，并以顺序图给出该交互的描述。
交互：教学主任通过教学管理信息系统查询每学期教师工作量
