一、用逻辑符号表达下列语句

1．(1 分)没有不犯错误的人。

答：设 M（x）：x 是人。Q（x）：x 犯错误

(∀x)(M(x) −> Q(x)) 

2．(2 分)虚数既不是有理数也不是无理数。

答：设 W(x）：x 是虚数。P(x）：x 是有理数。Q（x）：x 是无理数。

(∀ x)(W(x) ∧¬P(x) ∧¬Q(x)) 

二、填空题(共 9 分) 

1、（3 分）设集合 A={a,b,c}, 为 A 上的恒等关系， 为 A 上全域关系。

1）设写出 -  = {<a,b>,<a,c>,<b,a>,<b,c>,<c,a>,<c,b>}

解析：

={<a,a>,<a,b>,<a,c>,<b,a>,<b,b>,<b,c>,<c,a>,<c,b>,<c,c>},

 ={<a,a>,<b,b>,<c,c>}。

2）A 上含有序对个数为 (4 或 5) 的二元关系数目最多，这样的二元关系数目为 C(9,4)=C(9,5)=126 

2.（2 分）把 6 个人分成两组，每组至少 2 人，共有 (25 )种不同的分组方式。

解析：有两种分组方案，①一组 2 人，一组 4 人，②两组都是 3 人，故共有𝐶(6,2) + 𝐶(6,3)/2 = 25 种不同的分组方式。

3.（2 分) 展开式经过合并同类项之后，xyzw 的系数为 4!*2*3*4=576 

解析：由多项式定理

3

4.（2 分）从 1 到 30 的正整数中任意选取三个不同的数，使得它们的和能被 3 整除，则共有(1360) 种不同的选取方法。

解析：1，2,…，30 这 30 个数可以分成三组：被 3 整除者为一组，除以 3 余 1 者为一组，除以 3 余 2 者为一组，显然

每组有 10 个整数。如果三个整数都选自同一组，其和必能被 3 整除，如果每组选取一个整数，其和也必能被 3 整除。

因此选取方法总数为：C(10，3）+ C(10，3）+ C(10，3）+ =1360 

三、解答题（共 11 分）

1.(3 分）设 P↑Q=﹁（P∧Q）,试将﹁P，P∧Q，P∨Q 仅用联结词↑表示出来。解析：P↑Q 表示 P 

和 Q 进行先与后非的操作。

┒P= P↑P

 p∧Q = (P↑Q)↑(P↑Q) 

p∨Q = ┒P ↑ ┒Q = (P↑P)↑(Q↑Q) 

2.（8 分）在信道上传输仅由上而下个字母 a,b,c,d,e 组成并且长度为 n 的词，规定连续出现两个 a 的词不允许传输，用 h(n)表示这个信道上允许传输的长为 n 的词的个数。

1）求 h(1),h(2); 

h(1)=5，h(2)=5*5-1=24，

2）建立关于 h(n)的递归关系；

3）求 h(n)的通项公式。

h(n)表示信道上允许传输的长为 n 的词的个数,则 h(1)=5，h(2)=5*5-1=24，令n>=2,如果单词第一个字母是 b 或 c,d,e，则余下长度 n-1 的位置上仍然是在相同限制条件下对 a,b,c,d,e 这 5 类字母的排列，排列方法为 h(n-1).如果单词第一个字母是a,那么第二个字母就是b或c,d,e。如果第二个字母是b,则该单词可以有h(n-2) 种方法构成，如果第二个字母是 c 或 d,e,同样该单词也可以有 h(n-2)种方法构成。于是有h(n)=4h(n-1)+4h(n-2)n>=2。该递推关系的特征方程的根为即利用h(2)=5*5-1=24可解得

四、证明题（共 17 分）

1、（3 分）设 A={<a,b>︱a,b 为任意正整数}，A 上的二元关系，R={<<a,b>,<c,d>>︱ad=bc},证明 R 是 A 上的等价关系。

1

2、（4 分）设 G 是一个简单图，G 的每个顶点的度数至少是 3。证明图 G 中一定存在长度为偶数的图。

解析：对简单图 G 的结点个数 n 进行数学归纳证明：当 n=4 时，G 为完全图，结论显然成立所得的圈的长度为 4. 设当 n=k 时结论成立，长度为偶数的圈为 C。则当 n=k+1 时，长度为偶数的圈 C 也在结点数为 k+1 的图中，因此结论成立。

3.(4 分）设 G 是一个简单图，G是G’的子图，而且|V(G')|< |V(G)|,证明 G 中必存在这样一条边e,e的一个端点属于G',另一个端点不属于G'

解析：用反证法，由于︱V(G’)︱<︱V(G)︳,不妨设点集 V(S）=V(G）-V(G'），假设 G 中不存在一个端点属于 G'，另一个端点不属于 G'的边 e，那么图 G 可分成两个互补连通的子图 S 和 G'，这与 G 是简单连通图相矛盾。因此假设不成立，G 中必然存在这样一条边 e, e 的一个端点属于 G'，另一个端点不属于 G'

4、（6 分）设 H，K 是有限群 G 的两个子群，e 是 G 的单位元，这两个子群的阶分别为|H|=m,|K|=n. 如果 m 与 n 互素，那么 H∩K={e}。

解析：因为 H,K 是有限群 G 的子群，那么必有 G 的单位元 e∈H 且 e∈K，即 e∈H∩K。 不妨设存在与 e 相异的元素 a 也属于 H∩K，令|H∩K|=t>=2，由于 H∩K 是 H 和 K 的子群，根据拉格郎日定理 t|m 且 t|n，这与条件 m 与 n 互素相矛盾。故元素 a 不存在。|H∩K|=1，即 H∩K={e}。

计算机网络

一、单项选择题(共 10 分，每小题 1 分)

1．用 PCM 对语音进行数字化，如果将声音分为 128 个量化级，采样频率为8000 次/秒。那么一路话音需要的数据传输率为( A )Kbit/s。 

A．56 

B．64 

C．128 

D．1024 

解：PCM 代表 Pulse Code Modulation(脉冲编码调制)。它通常用在电话系统，对模拟数据进行采样。一般都把 PCM 采样时间设置成 125 微秒，125µs 的采样时间对应于每秒 8000 次采样。一个典型的电话通道是 4KHz。根据奈奎斯特定理，为获取在一个 4KHz 通道中的全部信息需要每秒 8000 次的采样频率。由于2^7=128，每个信号需要 7bit 表示，采样率为 8K/s。数据传输率为 56Kbit/s.

2．集线器(HUB)和路由器分别工作于 OSI 参考模型的(B )层。 

A．第一和第二 

B．第一和第三 

C．第二和第三 

D．第二和第四 

解：集线器（HUB）是物理层连网设备，路由器是网络层连网设备

3．两个网段在物理层进行互连时要求( B)。 

A．数据传输率和数据链路层协议都不相同 

B．数据传输率和数据链路层协议都相同 

C．数据传输率相同，数据链路层协议可不同 

D．数据传输率可不同，数据链路层协议相同 

解：在 N 层互连，为了让在两个网段上的计算机能够正常通信，要求 N 层以上的协议也相同。所以在本题中要求 数据传输率和数据链路层协议都相同。传输速率和窗口大小必须相等。

4．数据链路层采用 go-back—N 方式进行流量和差错控制，发送方已经发送了编号 0～6 的帧。当计时器超时，除 1 号帧外，其他各帧的确认均已返回时，发送方需要重发(D)帧。 

A.1      B.2      C.5      D.6 

解：1 号帧尚未返回确认，当计时器超时，1 号帧及其后面的帧都要重发。因此共有 6 个帧需要重发。

5．要控制网络上的广播风暴，可以采用的手段为( C ) 

A．用集线器将网络分段 

B．用网桥将网络分段 

C．用路由器将网络分段 

D．用交换机将网络分段 

解：集线器、网桥和 LAN 交换机都不隔离广播，路由器可以隔离广播，所以要 

控制网络上的广播风暴，可以采用 的手段为用路由器将网络分段

6．一个 16 端口的二层以太网交换机，冲突域和广播域的个数分别是( D)

A．1，1 

B．16，16 

C．1，16 

D．16，1 

解：2 层以太网交换机的每个端口都是冲突域的终止点，但 LAN 交换机都不隔离广播，所以本题中，冲突域和广播域的个数分别是 16 和 1。 

7．一个网段的网络号为 198．90．10．0/27，子网掩码固定为 255．255．255.224， 最多可以分成( )个子网， 而每个子网最多具有( A)个有效的 IP 地址。 

A．8，30 

B．4．62 

C．16．14 

D．32，6 

解：198．90．10．0 为 C 类地址，前 24 位形成网络号，由于十进制 224 的二进制编码为 11100000，因此最多可以划分 23=8 个子网，每个子网有 25个 IP 地址，除去全 0 和全 1 的两个 IP 地址，还有 30 个有效的 IP 地址。

8. FTP 协议在使用时需要建立两个连接：控制连接和数据传输连接，并用不同的端口号标识两个连接，其中用于数据传输连接的端口号是(D )。 

A．25 

B．23 

C．21 

D．20 

解：21 端口是状态连接端口，20 端口是数据传输连接端口。注：FTP 服务中： 20 端口用于数据连接，21 端口用于状态连接。

9．在采用TCP连接的数据传输阶段，如果发送端的发送窗口值由1000变为2000， 那么发送端在收到一个确认之前可以发送( B). 

A.2000 个 TCP 报文段 

B.2000 个字节 

C.1000 个字节 

D.1000 个 TCP 报文段 

解：TCP 的 WINDOW SIZE 是以字节数为单位的，窗口值是 2000，因此可以发送 2000 字节。

注：TCP 发送窗口以字节单位

10．防火墙的安全架构基于( C)技术. 

A.用户管理和认证 

B.数据加密 

C.访问控制 

D.流量控制 

解析：防火墙是一个或一组系统，它在网络之间执行访问控制策略。 注：防火墙基于访问控制的原理。

二、名词解释(共 5 分，每小题 2.5 分) 

1．IEEE802.5 令牌环网

解：令牌环网由 IBM 公司于 1969 年推出，后来被列为 IEEE 802.5 标准协议，它在物理和逻辑上均基于环结构，传输速率可以达到 4 或 16Mbps。令牌环网使用双绞线或同轴电缆作为传输介质，并将与各个站相连的接口逐个连接起来组成 一个闭合的环路，环上的每个环接口均有两种工作方式：发送方式与收转方式。 该网络通过一个很小的自由令牌(Free Token，一种有别与数据信号帧的特殊信号帧)在环上单向循环来控制和管理传输介质的使用，以保证 整个环路最多只有一 个站处于发送方式，其他的站都处于收转方式

2．ICMP 协议 

解：ICMP 是“Internet Control Message Protocol”（Internet 控制消息协议）的缩写。它是 TCP/IP 协议族的一个子协议，用于在 IP 主机、路由器之间传递控制消息。控制消息是指网络通不通、主机是否可达、路由是否可用等网络本身的消息。这些控制消息虽然并不传输用户数据，但是对于用户数据的传递起着重要的作用。

三、问答和计算题(共 15 分，每小题 3 分) 

1. 在 OSI 参考模型中，数据链路层和网络层的协议数据单元(PDU)分别是什么? 它们之间的封装关系是什么? 

解：“分组”(packet)也就是“包”，它是一个不太严格的名词，意思是将若干个比特加上首部的控制信息就封装在一起，组成一个在网络上传输的数据单元。在数据链路层这样的数据单元叫做“帧”。而在 IP 层（即网络层）这样的数据单元就叫做“IP 数据报”。IP 数据报在数据链路层被封装成数据帧进行传输。OSI 为了使数据单元的名词准确，就创造了“协议数据单元”（PDU）这一名词。在数据链路层的 PDU 叫做 DLPDU，即“数据链路协议数据单元”。在网络层的 PDU 叫做“网络协议数据单元”（NPDU）。

注：PDU 是指将若干比特加上首部的控制信息封装在一起，组成一个在网络上传输的数据单元，数据链路层的 PDU 是帧，网络 层是 IP 数据报（分组）；IP 数据报在数据链路层被封装成数据帧进行传输。

2．简述同步传输与异步传输的区别以及各自的适用环境。 

解析：异步传输时，被传送的数据编码成一串脉冲。传送一个 ASCII 字符（每个字符有 7 位）的格式如图 9.1 所示，首先发送起始位，接着是数据位、奇或偶校验位，最后为停止位。

其中，第 1 位为起始位（低电平“0”），第 2～8 位为 7 位数据（字符），第 9 位为数据位的奇或偶校验位，第 10～11 位为停止位（高电平“1”）。停止位可以用 1 位、1.5 位或 2 位脉宽来表示。因此，一帧信息由 10 位、 10.5 位或 11 位构成。异步传输就是按照上述约定好的固定格式，一帧一帧地传送。由于每个字符都要用起始位和停止位作为字符开始和结束的标志，因而传送效率低，主要用于中、低速通信的场合。

同步传输时，用 1 个或 2 个同步字符表示传送过程的开始，接着是 n 个字符的数据块，字符之间不允许有空隙。发送端发送时，首先对欲发送的原始数据进行编码，如采用曼彻斯特编码或差动曼彻斯特编码，形成编码数据后再向外发送。由于发送端发出的编码自带时钟，实现了收、发双方的自同步功能。接收端经过解码，便可以得到原始数据。在同步传输的一帧信息中，多个要传送的字符放在同步字符后面，这样,每个字符的起始、停止位就不需要了，额外开销大大减少，故数据传输效率高于异步传输，常用于高速通信的场合。但同步传输的硬件比异步传输复杂。

注：异步传输：被传送的数据编码成一串脉冲，传送一个 ASCII 字符的格式时，首先发送起始位，接着是数据位、奇偶校验位，停止位。异步传输就是按照这种约定好的固定格式，一帧一帧的传送， 由于每个字符都要用起始位、停止位，因而传送效率低，主要用于中低通信的场合；同步传输：用 1 个或 2 个同步字符表示传送过程的开始,接着是 n 个字符的数据块，字符之间不允许有空隙,发送端发送时，首先对欲发送的原始数据进行编码再向外发送。 由于发送端发出的编码自带时钟，实现了收、发双方的自同步功能。接收端经过解码，便可以得到原始数据。这时每个字符的起始、停止位不需要了，额外开销大大减少，故数据传输效率高于异步传输，常用于高速通信的场合。但硬件也相对复杂。

3．简单网络管理协议 SNMP 采用的传输层协议是什么?为什么采用该传输层协议? 

解析：SNMP 的通信基础是 TCP/IP 协议,它利用了传输层上的用户数据报协议(UDP). SNMP 定义为依赖于UDP 数据报服务的应用层协议,SNMP 实体向管理应用程序提供服务,它的作用是把管理应用程序的服务调用变成对应的 SNMP 协议数据单元,并利用 UDP 数据报文发送出去。之所以选择 UDP 协议而不是 TCP 协议,是因为 UDP 效率较高,这样实现网络管理不会太多地增加网络负载。但由于 UDP 不可靠,所以 SNMP 报文容易丢失,为此,对 SNMP 实现是将每个管理信息装配成单独的数据报独立发送,而且报文较短,不超过 484 字节. 

解答：SNMP 使用 UDP 传送报文。由于与 TCP 相比，UDP 协议简单，在每个系统中运行时网络负载很轻，故有利于数据的高速传送，并减少管理交通对网络带宽的消耗。另一方面，尽管 UDP 不保证传输的可靠性，但由于 SNMP 协议通常都结合进轮询机制，即使偶尔有报文传输错误发生，下一次命令不久又会到达，错误能够被纠正。

注：SNMP 的通信基础是 TCP/IP 协议，它利用了传输层上的 UDP 协议。SNMP 实体向管理应用程序提供服务，并利用 UDP 数据报文发送出去，选择 UDP，是因为 UDP 数据传送效率较高，这样实现网络管理不会太多增加网络负载，但由于 UDP 不可靠，所以 SNMP 容易丢失，为此，对 SNMP 实现是将每个管理信息装配成单独的数据报独立发送，且报文较短，不超过 484 字节

4．长度为 200 字节的应用层数据交给传输层传送，需加上 20 字节的 TCP 头部。 再交给网络层传送，需加上 20 字节的 IP 头部。最后交给数据链路层的以太网传送，还需加上 18 字节的头部和尾部。假设不计其他开销，试求该数据的传输效率。

长度为 200 字节的应用层数据交给传输层传送，需加上 20 字节的 TCP 头部。再交给网络层传送，需加上20 字节的 IP 头部。最后交给数据链路层的以太网传送，还需加上 18 字节的头部和尾部。假设不计其他开销，试求该数据的传输效率。

解析：数据传输效率为 200/（200+20+20+18）=77.5% 

5.某一网络的一台主机产生了一个 IP 数据报，头部长度为 20 字节，数据部分长度为 2000 字节。该数据报需要经过两个网络到达目的主机，这两个网络所允许的最大传输单元 MTU 分别为 1500 字节和 576 字节。请问原 IP 数据报到达目的主机时分成了几个 IP 小报文?每个报文的数据部分长度分别是多少? 

解：因为第一个网络的 MTU 为 1500 字节<2000+20 字节,因此在第一个网络传输时 IP 数据报被分成两个 IP 小报文，第一个小报文的数据部分长度为 1480，第二个小报文数据部分长度为 520 字节。当传输到第二个网络时，由于其MTU=576<1480，因此第一个小报文还要再分成三片，第一片和第二片的数据部分长度为 556，第三片的数据 部分长度为 1480-556*2=368。当原 IP 数据报到达目的主机时分成了四个 IP 小报文，第一个第二个小报文数据部分长度为 556，第三个数据部分长度为 368，第四个数据部分长度为 520 字节

软件工程 

一、在每小题的四个备选答案中选出一个正确的答案。 

1．软件工程的基本目标可概括为(A )。 

A．可用性、正确性、合算性 

B．可用性、正确性、可靠性 

C．有效性、正确性、鲁棒性 

D．可用性、可靠性、方便性 

解：软件工程目标—包括可用性、正确性和合算性，规定了软件工程实践的结果 （即软件）应具有的基本性质

2．模块 A 直接访问模块 B 的数据，属于( A )。 

A．内容耦合 

B．数据耦合 

C．公共耦合 

D．控制耦合 

解：内容耦合：两个模块间发生下面情形: 

(1)一个模块直接访问另一个模块的内部数据; 

(2)一个模块不通过正常入口转到另一个模块内部; 

(3)两个模块有一部分程序代码重叠(只可能程序在汇编语言中); 

(4)一个模块有多个入口

3．螺旋模型相比演化模型主要增加了( B)。 

A．制定计划 

B．风险分析

C．客户评估 

D．工程实施 

解：螺旋模型将瀑布模型与演化模型结合起来，并且加入两种模型均忽略了的风险分析。

4．需求规约的最主要结果为(C )。 

A．用户需求描述文档 

B．数据流图和数据字典 

C．需求规格说明书 

D．可行性分析报告 

5．OOA 阶段建立的最主要模型是( B)。 

A．用况图 

B．类图 

C．顺序图 

D．对象图 

解：用况图-用来建立需求模型；类图-面向对象建模，显示类内部结构及类之间关系；对象图-是类图的实例，显示对象和对象之间的关系。顺序图-是用来描述对象自身及对象间信息传递顺序的视图

二、判断题(共 5 分，每小题 1 分) 判断以下每句话是否正确。如果正确，用“√” 表示，否则，用“×”表示。 

1．“我们是否完成了正确的产品?” 解释了验证(verification)的概念。(X ) 

解：错误。为把握软件开发各个环节的正确性，需要进行各种确认和验证工作。验证(Verification)，是保证软件正确地实现了某一功能的一系列活动。验证： “我们是否正确地完成了产品？”（过程正确）确认(Validation)，是保证软件的实现满足了用户需求的一系列活动。确认：“我们是否完成了正确的产品？

2．软件质量保证过程是软件开发过程的一部分。(√ ) 

3．α测试是在受控环境中进行的。(√ ) 

正确。α测试由用户在开发者的场所进行，并且在开发者的指导下进行测试。 开发者负责纪录发现的错误和使用中遇到的问题，也就是说 α 测试是在受控的环境中进行的。（α版：受控版 β 版：用户直接测试）

4．软件配置管理是 CMM2 级的一个关键过程域。(√  ) 

正确。CMM 第 2 级（可重复级）有 6 个关键过程域，主要涉及建立软件项目管理控制方面的内容。需求管理，软件项目计划，软件项目跟踪与监控，软件子合同管理，软件质量保证，软件配置管理

5．接口是面向对象方法中必不可少的概念。(√  ) 

三、简答题(共 9 分，每小题 3 分) 

1．简述白盒测试中的覆盖类型，并说明哪种最强，哪种最弱? 

解：白盒测试有六种覆盖类型：语句覆盖、判定覆盖、条件覆盖、判定/条件覆盖、条件组合覆盖和路径覆盖，发现错误的能力呈由弱至强的变化。

语句覆盖每条语句至少执行一次。

判定覆盖每个判定的每个分支至少执行一次。

条件覆盖每个判定的每个条件应取到各种可能的值。

判定/条件覆盖同时满足判定覆盖条件覆盖。

条件组合覆盖每个判定中各条件的每一种组合至少出现一次。

路径覆盖使程序中每一条可能的路径至少执行一次

2.CMM5 级(持续优化级)相对 4 级(已管理级)增加了哪些关键过程域? 

解：第 5 级（持续优化级）相对 4 级(已管理级)增加了 3 个关键过程域，主要涉及的内容是软件组织和项目中如何实现持续不断的过程改进问题。包括缺陷预防，技术变更管理，过程变更管理。

3 需求阶段的主要任务是什么?

解：需求分析是指理解用户需求，就软件功能与客户达成一致，估计软件风险和评估项目代价，最终形成开发计划的一个复杂过程。在这个过程中，用户的确是处在主导地位，需求分析工程师和项目经理要负责整理用户需求，为之后的软件设计打下基础。简言之,需求分析的任务是确定待开发的软件系统"做什么"。 具体任务包括确定软件系统的功能需求，性能需求和运行环境约束,编制软件需求规格说明书，软件系统的验收测试准则和初步的用户手册。

四、建模题(共 11 分) 

1．(3 分)某公司人员管理系统问题陈述：人员分为业务员、程序员和经理；随着时间的变化，人员会变换工作岗位，如业务员升任经理，经理出任程序员等等。 请建立该系统的类图，以有效应对人员职责变化的情况。 

2．(3 分)将下面的 N—S 图转换为 PAD 图

3．(5 分)根据你熟悉的一个业务问题建模，要求： 

(1)用自然语言给出该问题的简单陈述；

解析：（1）学籍管理系统用于学校对每一位学生的入学、毕业、每学年考试成绩、升留级处理等，该系统具备录入、存储学生的基本情况、各科成绩；查询学生各科成绩、单科成绩；打印成绩；统计班平均成绩、各科平均成绩；根据分数进行升留级处理等功能。

(2)用结构化方法建立该问题的 DFD(至少要给出 2 层，即顶层和 0 层)，并给出顶层数据字典。

数据字典数据流项目：

（1） 学生信息=姓名+性别+年龄+系别+专业+班级

（2） 成绩单=姓名+专业+{科目+考试时间+成绩} 数据项条目：成绩：别名：本次考试成绩、学生历次考试成绩、学生成绩类型：实型长度：6 位，小数点后 1 位加工条目：加工名：学籍管理系统编号：无输入：学生信息、本次考试成绩、学生记录输出：统计表、成绩单