于是，
，而
根据k的定义，必有
=0.
得证
。
从而
，故有
。
3.（4分）设G=（V，E）是简单的无向平面图，证明G中至少有一个结点的度数小于等于5.
解析：
假设G的每个结点的度数都大于等于6，则∑d（v）>=6n,由于2m=∑d（v）
所以m>=3n,其中m是边数，n是顶点数。
但是如果G是简单的无向平面图，则有m<=3n-6,矛盾。
所以G中至少有一个结点的度数小于等于5.
4.（5分）给定群
，且
定义映射
，
证明：
f是
到其自身的同构映射。
证：
对于
有
所以f是G的自同态。
任取
，则
，且满足
所以f是满射的。
假若f（x）=f（y）,即
=
，由G中的消去律必有x=y,
从而f是单射的。
综上所述，f是
到其自身同构映射。
第二部分专业知识课程
课程Ⅰ计算机系统结构
一、填空题（共6分，每空1分）
1.一个模m=32的多体存储器，其总容量为1M字，对给定的二进制地址110100*********10101，若采用低位交叉编址，则该存储单元的体号（二进制表示）为10101。
体内地址（二进制表示）为110100111101011；若采用高位交叉编址，则体号为11010，体内地址为011110110110101。
2.用互联网络互联16个处理机，编号为0~15，若互连函数为Cube2（Cube0），则7号处理器连至2号处理器，若互联函数为PM2+3，则7号处理器连至15号处理器。
计算题
二、计算题（5分）
假设某程序不计访存时间的指令执行时间都为2个时钟周期，平均每条指令访存1.33次，增设Cache后，程序访存命中Cache的概率为98%，命中Cache时指令用于访存所需时间为50个时钟周期，请分别计算不设置Cache和增设Cache两种情况下的程序的平均指令执行时间，以及增设Cache相对于不设置Cache的加速比。
解析：
不设置Cache时，平均每条指令访存所需时间为：
55*1.33=66.5时钟周期
不计访存时间的指令平均执行时间为2个时钟周期，所以，包括访存时间在内的指令平均时钟周期数
CPIm=66.5+2=68.5时钟周期
增设Cache后，平均每条指令一次访存所需时间
T=HTc+（1-H）Tm=（0.98*2+（1-0.98）*50）=2.96时钟周期
包括访存时间在内的平均时钟周期数
CPI=2.96*1.33+2=5.93时钟周期
增设Cache相对于不设置Cache的加速比为：
S=CPIm/CPI=68.5/5.93=11.6
三、设计题（9分）
一个处理机共有10条指令，各指令在程序中出现的概率如下表所示：
指令序号
出现的概率
Huffman编码法
2-4扩展编码法
Ⅰ1
0.25
11
00
Ⅰ2
0.20
01
01
Ⅰ3
0.15
101
1000
Ⅰ4
0.10
001
1001
Ⅰ5
0.08
1000
1010
Ⅰ6
0.08
1001
1011
Ⅰ7
0.05
00011
1100
Ⅰ8
0.04
00010
1101
Ⅰ9
0.03
00001
1110
Ⅰ10
0.02
00000
1111
操作码的平均长度
∑pi*li=2.99
2*0.45+4*0.55=3.1
采用Huffman编码法编写出这10条指令的操作码，并计算操作码的平均长度；
四、综合题（共10分）
分别在下面三种计算机系统上计算表达式f=
。
假设加法需要2个时间单位乘法需要4个时间单位。
从存储器取指令、取数据，译码的时间忽略不计，所有的指令和数据已经装入有关的PE或处理机中。
1.（3分）一台串行计算机，处理机中有一个加法器和一个乘法器，同一时刻这两运算部件只有一个可以使用，求f的最小计算时间。
解析：
计算表达式需要10次乘和9次加，其乘加的顺序对速度没有影响，因此最小计算时间为：
4*10+2*9=58
2.（3分）一台由8个PE（PE0，PE1，……，PE7）构成的SIMD计算机，8个PE连成单向环结构。
每个PE用一个时间单位可以将数据直接送到其相邻的PE。
操作数xi和yi最初存放在PEimod8（i=0,1,2,……9）中，每个PE可以在不同时刻执行加法或乘法运算，求f的最小计算时间。
解析：
为减少传送步距，在运算过程中应及时调整其互联关系，时空图如图所示：
由时空图可得，全部完成计算需要18拍。
3.（4分）一台流水线SISD计算机，其动态多功能流水线由4个功能段组成，如下图所示。
其中S1，S2，S3，S4组成乘法流水线，S1，S4组成加法流水线，各功能段用时均为一个时间单位。
假定该流水线的输出结果可以直接返回流水线输入端，而且设置有足够的缓冲寄存器。
试求：
（1）f的最小计算时间；
（2）功能段S4的使用效率。
F的最小计算时间乘法13拍，加法10拍，共23拍。
S4使用效率19/23=82.6%
课程Ⅱ计算机网络
一、单项选择题（共10分，每题1分）
1.能实现不同的网络层协议转换功能的互联设备是（C）。
A.集线器 B.交换机 C.路由器 D.网桥
2.快速以太网集线器按结构分为（B）。
A.总线型和星型 B.共享型和交换型
C.10M和100M网 D.全双工和半双工
3.UDP提供面向（D）的传输服务。
A.端口 B.地址 C.连接 D.无连接
4.下列不属于系统安全的是（ B ）。
A.防火墙 B.加密狗
C.认证 D.防病毒
5.（ A）是端系统之间的协议。
A.TCP B.IP
C.ICMP D.UDP
6.在下列网络中，哪个分组交换网络不是通过建立虚电路进行通信？
（C）
A.帧中继B.X.25
C、FDDID.ATM
7.建立虚拟局域网的交换技术一般包括（ D ）、帧交换、信元交换三种方式。
A.线路交换B.报文交换
C.分组交换D.端口交换
8.LANHUB交换机是（D）。
A.工作在第1层的多端口中继器。
B.工作在第2层的多端口集线器。
C.工作在第3层的多端口路由器。
D.工作在第2层的多端口网桥。
9.IEEE802规定了OSI模型的哪一层？
（B）
A．数据链路和网络层B．物理和数据链路层
C．物理层D．数据链路层
10.防火墙的作用是（B）。
A.阻止XX的数据流进/出内部网络
B.仅仅阻止XX的数据流进入内部网络
C.仅仅阻止XX的数据流从内部网络出去
D.对内部网络的安全无能为力
二、名词解释（共5分，第一题3分，第二题2分）
1.FDDI标准
解析：
FDDI（FiberDistributedDataInterface）是光纤分布数据接口。
FDDI以光纤作为传输媒体,它的逻辑拓朴结构是一个环,更确切地说是逻辑计数循环环（LogicalCounterRotatingRing）,它的物理拓朴结构可以是环形.带树形或带星形的环。
FDDI的数据传输速率可达100Mbps,覆盖的范围可达几公里.FDDI可在主机与外设之间、主机与主机之间、主干网与IEEE802低速网之间提供高带宽和通用目的的互连.FDDI采用了IEEE802的体系结构,其数据链层中的MAC子层可以在IEEE802标准定义的LLC下操作。
2.防火墙
解析：
防火墙是一种网络安全的防范措施，其工作方式是将内联网络与因特网之间或与其他外联网络之间互相隔离，通过访问控制的方式来保护内联网络。
设置防火墙的目的是为了在内联网与外联网之间设立唯一的通道，简化网络的安全管理。
三、问答和计算题（每题3分共15分）
1.画出SNMP协议模型，并简述SNMP的工作过程。
解析：
简单网络管理协议（SNMP:
SimpleNetworkManagementProtocol）定义了从网络设备那里收集网络管理信息的方法，还为设备指定向网络管理站报告故障和错误的途径。
SNMP首先考虑的是TCP/IP协议集，采用管理进程/代理进程模式，管理协议在应用层或TCP/IP模式的“处理层”上运行。
SNMP的成功主要在于它的简单性、灵活性和可扩展性。
SNMP的三个组成部分：
1）.SMI：
管理信息结构和标识，是描述管理信息的标准符号。
2）.MIB：
管理信息库，包含了待管理的各种变量。
目前的管理对象集称为MIB-II。
它为树形结构：
3）.SNMP协议：
SNMP是为网络管理服务而定义的应用协议，实现NMS和代理之间的异步请求和响应。
SNMP对设备的监视主要通过查询代理MIB中相应对象的值来完成。
代理也会发出一些陷阱来引导NMS的查询。
2.什么是服务原语？
服务原语的三要素是什么？
服务原语的类型有哪几种？
解析：
服务原语是一层对它向其相邻上层所提供的服务的描述的形式，每个原语都带有一套相关的服务参数。
服务是通过一组服务原语来执行的，原语供用户和其它实体访问该服务时调用。
它们被用来通知服务提供者采取某些行动或向其相邻上层报告某个对等实体的活动。
原语包括原语类型、被呼和主呼地址、以及用户数据三个主要元素，原语名字则包含原语类型和提供服务的层的标识，如T.CONNECT.request是由传输服务用户——即会话层——发出的一个请求原语，其目的是要跟远方用户（会话层）建立一种（逻辑的）传输连接。
S.DATA.indication是由对等（通信）会话层发给它上面的表示层的一个指示原语，并且涉及从远方表示层收到的数据。
服务原语的类型有请求原语、指示原语、响应原语和证实原语。
3.网络防病毒技术主要内容是什么？
解析：
网络防病毒技术包括预防病毒、检测病毒和消除病毒等3种技术：
网络防病毒技术的具体实现方法包括对网络服务器中的文件进行频繁地扫描和监测。
工作站上采用防病毒芯片和对网络目录及文件设置访问权限等。
防病毒必须从网络整体考虑，从方便管理人员的工作着手，通过网络环境管理网络上的所有机器，例如，利用网络唤醒功能，在夜间对全网的客户机进行扫描，检查病毒情况。
利用在线报警功能，网络上每一台机器出现故障、病毒侵入时，网络管理人员都能及时知道，从而从管理中心处予以解决。
4．假定有一个通信协议，每个分组都引入100字节的开销用于头和成帧。
现在使用这个协
议发送1M字节的数据，然而在传送的过程中有一个字节被破坏了，因而包含该字节的
那个分组被丢弃。
试对于1000、5000、10000和20000字节的分组数据大小分别计算“开
销+丢失”字节的总数目？
分组数据大小的最佳值是多少？
解析：
设D是分组数据的大小，那么所需要的分组数目N=106/D
开销=100×N（被丢弃分组的头部也已计入开销）
所以，开销+丢失=100×106/D+D
分组数据大小D开销+丢弃
1000101000
500025000
1000020000
2000025000
y=108/D+D
当D=104时，
所以，D的最佳值是10000字节。
5.一个单位有一个C类网络200.1.1。
考虑到共有四个部门，准备划分子网。
这四个部门
内的主机数目分别是：
A—72台，B—35台，C—20台，D—18台；即共有145
台主机。
（a）给出一种可能的子网掩码安排来完成划分任务
解析：
每个部门分配一个子网，名义上部门A.B.C.D的子网大小分别是：
27（=128），26（=64），25（=32）和25（=32）
IP地址的最高位是0表示子网A，最高两位是10表示子网B，最高三位是110表示子
网C，最高三位是111表示子网D。
显然这里采用了可变长子网掩码，涉及3种子网掩码，
分别是
255.255.255.128
255.255.255.192
255.255.255.224
（b）如果部门D的主机数目增长到34台，那么该单位又该怎么做？
解析：
给部门A分配两个子网01和001，名义上分别是64个地址和32个地址，共
96个地址；
部门B不变，仍然是10，名义上大小为64个地址；
部门C改为000，名义上大小是32个地址
部门D改为11，名义上大小是64个地址。
课程Ⅲ软件工程
一、单项选择题（每小题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．软件生存周期模型
二、判断题（共5分，每小题1分）
1. 详细设计是在概要设计之后进行的。
它利用概要设计的结果，对系统中的每个模块给出足够的过程性描述。
（√）
2.一笔交易、一个动作、甚至操作人员按一个按钮都可以看做是一次事物。
（√）
3.通过软件测试,可以发现软件中所有潜伏的错误.（X）
4.程序设计语言中应绝对禁止使用GOTO语句。
（X）
5.完善性维护是提高或完善软件的性能.（√）
三、简答题（共9分，每小题3分）
1．简述白盒测试中的覆盖类型，并说明哪种最强，哪种最弱?
解析：
白盒测试有六种覆盖类型：
语句覆盖、判定覆盖、条件覆盖、判定/条件覆盖、条件组合覆盖和路径覆盖，发现错误的能力呈由弱至强的变化。
语句覆盖每条语句至少执行一次。
判定覆盖每个判定的每个分支至少执行一次。
条件覆盖每个判定的每个条件应取到各种可能的值。
判定/条件覆盖同时满足判定覆盖条件覆盖。
条件组合覆盖每个判定中各条件的每一种组合至少出现一次。
路径覆盖使程序中每一条可能的路径至少执行一次。
2.CMM5级（持续优化级）相对4级（已管理级）增加了哪些关键过程域?
解析：
第5级（持续优化级）相对4级（已管理级）增加了3个关键过程域，主要涉及的内容是软件组织和项目中如何实现持续不断的过程改进问题。
包括缺陷预防，技术变更管理，过程变更管理
3．需求阶段的主要任务是什么?
解析：
需求分析是指理解用户需求，就软件功能与客户达成一致，估计软件风险和评估项目代价，最终形成开发计划的一个复杂过程。
在这个过程中，用户的确是处在主导地位，需求分析工程师和项目经理要负责整理用户需求，为之后的软件设计打下基础。
简言之，需求分析的任务是确定待开发的软件系统"做什么".具体任务包括确定软件系统的功能需求,性能需求和运行环境约束,编制软件需求规格说明书,软件系统的验收测试准则和初步的用户手册.
四、计算建模题（共11分）
1.（4分）已知一个软件项目的记录,开发人员M=3人,其代码行数=12.1KLOC,工作量E=24PM,成本S=168000美元,错误数N=29,文档页数Pd=365页.试计算开发该软件项目的生产率P,平均成本C,代码出错率EQR和文档率D.
解析:
软件开发的生产率P为:
P=L/E=12.1×103LOC/24PM=504LOC/PM
开发每行代码的平均成本C为:
C=S/L=168000美元/12100LOC=13.9美元/LOC
代码出错率EQR为:
EQR=N/L=29个/12.1KLOC=2.4个/KLOC
软件的文档率D为:
D=Pd/L=365页/12.1KLOC=30页/KLOC
2.（7分）问题陈述
学籍管理系统用于各个学校对每一位学生的入学、毕业、每学年考试成绩、升留级处理等，该系统具备录入、存储学生的基本情况、各科成绩；查询学生各科成绩、单科成绩；打印成绩；统计班平均成绩、各科平均成绩；根据分数进行升留级处理等功能。
1）用结构化分析方法给出系统的顶层DFD及数据字典
2）给出系统的0层DFD。
解析：
1）数据字典：
数据流项目：
（1）学生信息=姓名+性别+年龄+系别+专业+班级
（2）成绩单=姓名+专业+{科目+考试时间+成绩}
数据项条目：
成绩：
别名：
本次考试成绩、学生历次考试成绩、学生成绩
类型：
实型
长度：
6位，小数点后1位
加工条目：
加工名：
学籍管理系统
编号：
无
输入：
学生信息、本次考试成绩、学生记录
输出：
统计表、成绩单
顶层图
2）
课程Ⅳ人工智能原理
一、填空题（共10分，每空1分）
1、产生式系统由（规则库）、（综合数据库）和（控制系统／推理机）三部分组成。
2、语义网络是对知识的（有向图）表示方法，一个最简单的语义网络是一个形如（节点１，弧，节点２）的三元组。
3、人工神经网络是由（神经元）广泛互连构成的，不同的连接方式就构成网络的不同连接模型。
常用的连接方式有（前向网络）、（从输出层到输入层有反馈的网络）、（层内有互连的网络）和（互连网络）。
二、计算题（共5分）
化下列逻辑表达式为Skolem标准形：
～（（x）（y）P（a，x，y）（x）（～（y）Q（y，b）R（x）））
解析：
~（（x）（y）P（a,x,y）→（x）（~（y）（y,b）→R（x）））
消去“→”
~（~（x）（y）P（a,x,y）V（x）（（y）（y,b）VR（x）））
内移“~”
（x）（y）P（a,x,y）Λ（x）（（y）~（y,b）Λ~R（x））
重新命名变元名
（x）（y）P（a,x,y）Λ（z）（（u）~（u,b）Λ~R（z））
消去存在量词
（x）P（a,x,f（x））Λ（z）（~（g（z）,b）Λ~R（z））
全称量词移到公式右边
（x）（z）P（a,x,f（x））Λ~（g（z）,b）Λ~R（z））—Skolem标准型
其中f（x）,g（z）是不同的Skolem函数
三、问答题（共15分，每题5分）
1.简述遗传算法的基本原理和过程。
解析：
遗传算法的基本原理是：
模拟自然进化过程，将个体的集合──群体作为处理对象，利用遗传操作──选择、交换和突变，使群体不断进化"，直到成为满足要求的最优解。
其基本过程是：
begin
1.选择适当表示，生成初始群体；
升级会员 