组合数学
一、用逻辑符号表达下列语句（共 3 分，第 1 题 1 分，第 2 题 2 分）
1.有些人勤奋，但并非有些人都勤奋
答：设 M(x):x 是人；R(x):x 勤奋；N(x, y)：x 与 y 不相同
∃x∃y (N(x,y)∧M(x)∧M(y)∧R(x)∧¬R(y))
2.不管白猫黑猫，抓住老鼠就是好猫
答：P(x):x是猫 Q(x)：x是白猫 M(x):黑猫 N(x):抓老鼠的猫 Z(x):好猫
二、填空题
1 、 设 A={a,b,c}，B={1,2,3,4}，从 A 到 B 不同的二元关系共有( )个
2 、 设 A={a,b,c}，B={1,2,3,4}，从 A 到 B 不同的函数共有（ ）个
3、设集合A的基数|A|为n，在A上有( )个自反关系
三、证明（共 6 分，每题 3 分）
1、下列等值式是否正确，如正确请证明，如错误请举出反例
(∃𝐱)(𝐏(𝐱) → 𝐐(𝐱)) = (∀𝐱)𝐏(𝐱) → (∃𝐱)𝐐(𝐱)
2、用等势定义证明(1,2]≈(a,b], (a,b∈R,a为实数集)。
答：y=kx+l 过点（1，a）（2，b）
k=b-a l=2a-b
所以： y = (b-a)x+2a-b
四、（6 分）设 H 是群 G 的正规子群，且[G : H]=m，则对任意 x ∈G，均有 𝒙𝒎 ∈G
五、（6 分）证明 5 个顶点的完全图𝑲𝟓是不可平面的。
六、（6 分）求字母集{a,b,c,d}上含偶数个 a 的 K 元字的个数（用生成函数方法）
解：设这种字的个数为,那么
的指数生成函数为：
=
=
七、（5 分）证明边长为 1 的正三角形内任取 个点，必有两点的距离不超过
八、（5 分）如下图是一个用钢丝折成的六点对称图，现在要将这 6 个点分别染上红色或蓝色问有多少种染色法？
计算机网路
一、单项选择题（共 8 分，每题 1 分）在每小题的四个备选答案中选出一个正确
的答案。
1、一条线路每 1/16 秒采样一次，传输信号共有 16 种状态，问传输速率是（C ）
A. 16bps B. 48bps C. 64bps D. 256bps
解析：16 种状态可以用 4bit 二进制数表示，每秒采样 16 次，所以每秒需要传的数据量就是 64bit。如果不考虑信道 编码需要增加的冗余比特，传输速率就是64bit/s。（每次采样 4 比特，每秒采样 16 次，传输速率为 64bps。）
2、RS-232C 的电气特性规定逻辑“ 1”的电平范围为（B）。
A. +5~+15V B. -5~-15V C. 0~+5V D. 0~ -5V
解析：RS-232-C 关于电气信号特性的要求，规定逻辑“1”的电平为低于-3V，为了表示一个逻辑 1 或 MARK 条件，驱动器必须提供-5~-15V 之间的电压。为了表示一个逻辑 0 或 SPACE 条件，驱动器必须给出+5 至+15V 之间的电压。这就说明，标准留出了 2V 的余地，以防噪声和传输衰减。
3、对于选择重传 ARQ 协议，若序号位数为 3，则最大发送窗口 Wt 为（A）。
A 7 B. 8 C. 4 D. 5
解析：当使用有限范围的编号时，模 n 的编号是从 0 到 n-1，后随（n-1）号 PDU 的 PDU 编号又是 0，考虑到超时重发射机制，窗口机制必须能在接收端分辨序 列中预期新发来的 PDU 编号和那些重发射的老的 PDU 编号。HDLC 采用可二中 择一的编号方案：一个是模 8，另一个是模 128；对应的窗口值分别是 7 和 127。
4、若 HDLC 帧的数据域中出现比特串“ 010111110101”，为解决透明传输，则比特填充后的输出为：（A）。
A. 0100111110101 B. 010111110101 C. 01001111010101 D. 0101111100101
解析：HDLC 完全独立于被传送的数据，它把数据看成一个透明的位流。所有的帧都必须以标志段开头和结尾。标志序列由 01111110 构成。为了保证标志序列的惟一性，发送站将不断监视正在被发送的除标志段以外的位流，每当有 5 个连续的 1 被发送时，就插入一个附加的 0（位充填)
5、访问 Internet 的每台主机都需要分配 IP 地址（假定采用缺省子网掩码），IP 地址（A）分配给主机是正确的。
A. 192.46.10.0 B. 110.47.10.0 C. 127.10.10.17 D. 211.60.256.21
解析：A 是 C 类网络号，不是主机地址。C 是为回环测试保留的地址。D 是语法 错误的地址，不允许有 256。选项 B 可以分配给主机，其 A 类网络号是 110，主机号是 47.10.0。
6、协议（C）采用无连接方式进行工作。
A. FTP B. Telnet C. SNMP D. SMTP
解析：SNMP 是无连接的协议,它使用的运输层协议 UDP 也是无连接的。FTP、 Telnet 和 SMTP 都是因特网上面向连接的应用协议。
7、一个 B 类地址的子网掩码是 255.255.255.224，可以得出（D）个子网？（不考虑特殊地址）。
A. 8 B. 32 C. 1024 D. 2048
224:11100000 （8+3）=11 =2048
8、TCP 报文中，确认号为 1000 表示（A）。
A. 已收到 999 字节 B. 已收到 1000 字节 C. 报文段 999 已收到 D. 报文段 1000 已收到
解析：确认号为 1000 表示期待接收的下一个字节号是 1000，因此已收到 999 号字节。
二、名词解释（共 6 分，每小题 2 分）
1、ARP 协议
1.答：地址解析协议（ARP）用来在局域网上从目的地 IP 地址得到目的地 MAC 地址。为了说明 ARP 的主要思想，假定主机 1 要发送一个 IP 分组给主机 3，但不知道主机 3 的 MAC 地址。主机 1 先广播一个 ARP 请求分组要求目的地主机（以主机 3 的 IP 地址标识）回答。在网络中的所有主机都接收该分组，但仅仅被请求的主机（主机 3）对主机 1 作出应 答。ARP 响应分组包含主机 3 的 MAC地址和 IP 地址。从现在开始，主机 1 就知道主机 3 的 MAC 地址了。为了避免主机 1 每次给主机 3 发送都必须发送一个 ARP 请求分组，主机 1 把主机 3 的 IP和 MAC 地址缓存在自己的 ARP 表中，从而以 后的使用可以简单地在该表中查找主机 3 的 MAC 地址。为了适应网络中主机 MAC 地址可能的动态变化，ARP还采取超时和定期更新机制，保持 ARP 表中信息的准确性。
2、数字签名
2. 答：数字签名所要解决的问题必须保证以下 3 点：
接收者能够核实发送者
发送者事后不能抵赖对报文的签名
接收者不能伪造对报文的签名
加密和解密算法除了具备通常的 D（E（M））=M 特性外，还要具备 E（D（M））= M 特性。假设是这种情况，A 可以通过传输 EB（DA（M））来发送一个签名的明文报文到 B。注意，A 知道他自己的（保密的）解密密钥 DA 和 B 的公开密钥 EB。当 B 收到此报文时，他用自己的私有密钥将报文转换，产生出 DA（M）。 B 把它存放到安全的地方，然后用 EA 将其解密，从而得到最初的明文 M。
3、OSPF
答：开放的最短通路优先（OSPF）协议是一个内部网关协议，它让路由器获悉整个网络拓扑的信息。每个 OSPF 路 由器监视到它的每个邻居的链路的代价 （称作链路状态），并且把链路状态信息洪泛到在网络中的其它路由器。由于这 一原因，OSPF 通常被称作链路状态协议。链路状态信息的洪泛允许每个路由器都建立一个相同的链路状态 数据库（或拓扑数据库），该数据库描述整个网络的拓扑结构。在稳定状态，这些路由器将具有同样的链路状态数据库，因此它们知道在网络中有多少个路由器，知道在它们之间的接口和链路，以及跟每条链路相关的代价。在链路状态数据库中的信息允许一个路由器建立以自己为根的最短通路树。最短通路的计算通常使用 Dijkstra 算法执行。因为链路状态信息提供比距离向量信息要多的信息，当在网络中发生一个故障时，OSPF 典型地比 RIP 收敛得快。
三、问答和计算题（共 16 分）
1、（3 分）简述 TCP/IP 网络体系结构，并说明各层的主要协议和各层的主要功能。
1、答：TCP/IP 网络体系结构如下图所示，包括应用层、运输层、互连网络层和网络接口层。网络接口层负责从主机或节点接收 IP 分组，并把它们发送到指定的物理网络上，物理网络通常包括 OSI 的物理层和数据链路层。互连网络层定义了标准的分组格式和协议，即 IP 协议。互连网络层的功能就是把 IP 分组发送到应该去的地方。选择分组路由和避免阻塞是这里主要的设计问题。运输层在 TCP/IP 模型中位于互连网络层之上，它的功能相当于 OSI 的运输层。这里定义了两个端到端的协议。第一个是传输控制协议 TCP。它是一个面向连接的协议，允许从一台机器发出的字节流无差错地发往互联网上的其他机器。
TCP 还要处理流量控制，以避免快速发送方向低速接收方发送过多报文而使接收方无法处理。第二个协议是 用户数据报协议 UDP（User Datagram Protocol ）。 它是一个不可靠的、无连接协议，用于不需要 TCP 的排序和流 量控制能力而是自己完成这些功能的应用程序。应用层包含所有的高层协议（相当于 OSI 的应 用层、表示层和会话 层）。最早引入的是虚拟终端协议（TELNET）、文件传输协议（FTP）和简单邮件传输协议（SMTP）。再后来的 发展又增加了不少协议，例如域名系统服务 DNS（domain name service）用于把主机名映射到网络地址，HTTP 协议用于在万维网（WWW）上获取主页等。
2、（3 分）简述 HTTP 协议的特点和工作过程。
答：HTTP 是传送信息的协议，从层次的角度看，HTTP 是面向事务的应用层协议。虽然 HTTP 使用了 TCP，但 HTTP 协议是无连接的，也是无状态的，这样可使读取网页信息完成得较迅速。从 HTTP 的观点来看，万维网浏览器就是一个 HTTP 客户，而在万维网服务器等待 HTTP 请求的进程常称为 HTTP 守护程序。HTTP 守护程序在收到 HTTP 客户的请求后，经过一些必要的处理，将所需的文件返回给 HTTP 客户。简单的情况就是用户代理与服务器直接建立一个TCP 连接。客户先发起 TCP 连接，在和服务器建立了 TCP 连接后就发送 HTTP请求。这个请求包括一个特定的命令，一个 URL，和一个“类 MIME”报文，它包括一些请求参数和客户自身的信息。当服务器收到请求后，就试图完成所请求的动作，接着就返回 HTTP 响应。响应包括状态信息，成功或出错代码，一个类MIME 报文，包括有关服务器的信息和响应信息。接着就释放 TCP 连接。
3、（3 分）一个以太网速率从 10Mbps 升级到 100Mbps，满足 CSMA/CD 冲突域条件，为使正常工作,需做哪些调整？为什么？
答：由于 10BASE-T 证明比 10BASE2 和 10BASE5 具有更明显的优越性，因此所有的快速以太网系统都使用集线器（Hub），而不采用同轴电缆。100BASE-TMAC 与 10Mbps 经典以太网 MAC 几乎完全一样，唯一不同的参数就是帧 际间隙时间，10Mbps 是 9.6μs（最小值），快速以太网（100Mbps）是 0.96μs （最小值）。另外为了维持最小分组尺寸不变，需要减少最大冲突域直径。所有这些调整的主要原因是因为速率提高到了原来的以太网的 10 倍。
4、（3 分）设 TCP 使用的最大窗口为 64KB（64*1024 字节），假定信道平均带宽为 1Mbps，报文段的平均往返时延为 80ms，并且不考虑误码、确认帧长、头部和处理时间等开销，问该 TCP 连接所能得到的最大吞吐量是多少？此时传输效率是多少？
)=524288bit 由于6.5536Mbps>1Mbps。所以TCP连接得到的最大吞吐量为1Mbps.此时传输速率为100%。事实上
。即最大窗口发送时间大于往返时延，发送方可以不间断发送，最大吞吐量与宽带相等。
5、假定卫星信道的数据率为 100kbps，卫星信道的单程(发送方通过卫星到接受方)传播延时为 250ms，每个 数据帧长均为 2000bit，并且不考虑误码、确认帧长、头部和处理时间等开销，为达到传输的最大效率，试问帧的 顺序号应为多少位？此时信道利用率是多少？
解 ： RRT=250*2 毫 秒 =0.5 秒 一 个 帧 发 送 时 间 等 于 2000bit /100kbit/s=20 *10^3 秒 设 窗 口 值 为 x. 令 2000 比特 x 100k bit/s=20 *10^3 秒 +RRT=20*10^3秒+0.5 秒=0.52 秒 X=26 当得到最大信道利用率，窗口值为 26。此时会不间断发送帧。发送速率持续 100kbps.由于 16<26<32。帧得顺序号为 5 位。 在使用回退 N 式 ARQ 的情况下。最大窗口值位 31，大于 26.此时不间断的发送帧,信道利用率为100%。
软件工程
一、单项选择题（每小题 1 分，共 5 分）
1. 软件可用性是指（ B）。
A．用户界面友好的程度 B．软件结构，实现及文档为用户可用的程度
C．修改软件错误的难易程度 D．符合用户使用习惯的程度
解：B 软件工程目标：生产具有正确性、可用性以及开销合宜的产品。正确性指软件产品达到预期功能的程度。可用性指软件基本结构、实现及文档为用户可用的程度。开销合宜是指软件开发、运行的整个开销满足用户要求的程度。
2. 设计阶段的主要任务是（A ）。
A．给出软件解决方案 B．给出系统模块结构
C．定义需求并建立系统模型 D．定义模块算法
3. 演化模型与增量模型的主要区别是（D ）。
A．软件工程活动不同 B．针对的项目大小不同
C．针对不同的软件开发方法 D．针对的需求完整性不同
3.解：D 增量模型与演化模型的相同点是：基本思想都是非整体开发，以渐增方式开发系统。不同点：增量模型：产生结果给客户使用；演化模型：多次迭代，产生结果给测试。
4.飞机和发动机都是类，它们之间是一种（C ）关系。
A．分类结构 B. is a C．聚合结构 D．一般-特殊结构
5．按不同人员的工作内容来分类软件过程，组织过程包括（C ）。
A．维护过程和改进过程等 B．确认过程和审计过程等
C．管理过程和改进过程等 D．配置管理过程和裁剪过程等
按照不同人员的工作内容来分，将软件生存周期过程分为三类：基本过程、支持过程、组织过程：．
基本过程是指那些与软件生产直接相关的过程（5 个）：获取过程、供应过程、 开发过程、运行过程、维护过程．
支持过程是有关各方按他们的支持目标所从事的一系列相关活动集（9 个）：文档过程、配置管理过程、质量保证过程、验证过程、确认过程、联合评审过程、审计过程、问题解决过程、易用性过程等。
组织过程是指那些与软件生产组织有关的过程（8 个）： 管理过程、基础设施过程、改进过程、人力资源过程、资产管理过程、复用程序管理过程、领域软件工程过程、培训过程。
二、判断题（每小题 1 分，共 5 分。如果正确，用“√”表示，否则，用“×”表示）
1. 软件就是计算机系统中的程序。（X ）
解：× 软件是指计算机系统中的程序及其文档，程序是计算任务的处理对象和处理规则的描述；文档是为了便于了解 程序所需的阐明性资料。
2. 一个软件模型的控制范围应该在其作用范围之内。（X ）
解：× 在软件设计阶段，划分模块的原则是，一个模块的作用范围应该在其控制范围之内
3.测试用例时，只需检查程序是否做了它应该做的事情。（X ）
解：× 测试用例应由测试的输入数据和预期的输出结果两部分组成。
4. COAD-YOURDON 分析方法是“模型驱动的方法”。（ ✔️）
解：√ Coad 和 Yourdon 的方法是建立在信息模型化技术、面向对象的程序设计和知识库系统的基础之上的，方法分为 面向对象的分析(OOA)和面向对象的设计(OOD)。Coad 和 Yourdon 认为面向对象的分析主要应该考虑：一个与特定应用有 关的对象，对象与对象在结构和相互作用上的关系。在面向对象的分析中，需要建立分析模型来描述系统的功能。
5.软件开发环境中最主要的组成部分是软件工具。（✔️ ）
三、问答题（共 12 分，每小题 4 分）
1. 给出软件测试过程模型。
答：五种测试模型分别为：V 模型，W 模型，H 模型，X 模型和前置测试模型
V 模型：V 模型是软件开发瀑布模型的变种，主要反映测试活动与分析和设计的关系，从左到右，描述了基本的开发过程和测试行为。它非常明确地标明了测试过程中存在的不同级别，强调了在整个软件项目开发中需要经历的若干个测试级别，并与每一个开发级别对应。
W 模型：我们可以认为，W 模型，测试与开发是同步进行的，从而有利于今早的发现问题。强调了测试计划等工作的先行和对系统需求和系统设计的测试；H 模型：软件测试是一个独立的流程，贯穿于产品的整个生命周期，与其他流程并发的进行。软件测试原则“尽早准备，尽早执行”；强调测试是独立的，只要测试准备完成，就可以执行测试。
X 模型：探索性测试，能够帮助有经验的测试人员在测试计划之外发现更多的软件错误。
前置测试模型：前置测试能给需要使用测试技术的开发人员、测试人员、项目经理和用户等带来很多不同于传统方法的 内在的价值。与以前的方法中很少划分优先级所不同的是，前置测试用较低的成本来及早发现错误，并且充分强调了测 试对确保系统的高质量的重要意义。它不仅能节省时间，而且可以减少那些令开发人员十分厌恶的重复工作。
2.将下面给出的伪码转换成 N-S 图和 PAD 图。
3、COAD-YOURDON 的 OOD 模型包括哪几部分？这几部分各自的任务是什么？
答：OOD 模型包括：设计数据管理子系统、设计任务管理子系统、构建问题域子系统、设计人机交互子系统。
1）数据管理子系统的任务是，将一个系统的实现和它所需的具体数据存储分离开来，建立完善的数据存储管理体 系；主要针对系统中涉及的数据，采用独立管理方式，即保证数据的安全又方便对数据进行操作；包括选择数据管 理模式7和数据管理子系统的设计。
2）任务管理子系统的任务是，对系统各种任务进行选择和调整；任务管理明确任务的类型并设计处理过程。
3）问题域子系统的任务是，通过对问题的详细分析，已初步得到了问题域的基本模型，但进入设计阶段，要根据 应用环境、编程环境对分析模型进行细化和晚上，进入详细设计阶段需要对问题域模型进行补充修改。
4）人机交互子系统的任务是，根据具体实现环境，用户界面部分是在分析应用的基础上，确定人机交互的细节
四、建模题（共 8 分）
问题陈述：在一简化的图书管理系统中：
图书管理员负责：
●录入每一入库的图书（书名，图书编号，图书种类，作者，单价，入库数量）；
●当图书出现丢失时，修改该图书的库存数量；如果图书库存数量小于库存下限，
则将购书通知（书名，购书量）发给采购员。
采购员负责：
●将图书管理员发来的购书通知（书名，购书量）存入购书目录文件（{书名，购书量}）；
●每月末，根据购书目录文件，制定购书计划（{书名，购书量}），并将购书计划提交馆长审批；
●馆长审批通过购书计划后，开始购书，并清除购书目录文件中的相应记录。
馆长负责：审批采购员提交的购书计划，并返回审批意见（同意或不同意）。
图书馆主任负责：
●随时查询某类图书的库存情况（图书种类，库存量，库存金额）；
●在每月末，按图书种类统计库存情况（图书种类，库存量，库存金额）。
1.（3 分）用结构化分析方法给出该系统的顶层 DFD（系统环境图）；
2.（2 分）给出上述顶层 DFD 的数据字典；
3.（3 分）定义一个交互，并以顺序图给出该交互的描述
