堆数据结构定义如下：
对于n个元素的关键字序列{a1，a2，...,an}，当且仅当满足下列关系时称其为堆。
在一个堆中，若堆顶元素为最大元素，则称为大顶堆；若顶堆元素为最小元素，则称为小顶堆。堆常用完全二叉树表示，图4-1是一个大顶堆的例子。
图4-1大顶堆示例
堆数据结构常用于优先队列中，以维护由一组元素构成的集合。对应于两类堆结构，优先队列也有最大优先队列和最小优先队列，其中最大优先队列采用大顶堆，最小优先队列采用小顶堆。以下考虑最大优先队列。
假设现已建好大顶堆A，且已经实现了调整堆的函数heapify（A,n,index）。
下面将C代码中需要完善的三个函数说明如下：
（1）heapMaximum(A)：返回大顶堆A中的最大元素。
（2）heapExtractMax(A)：去掉并返回大顶堆A的最大元素，将最后一个元素“提前”到堆顶位置，并将剩余元素调整成大顶堆。
（3）maxHeapInsert(A,key)：把元素key插入到大顶堆A的最后位置，再将A调整成大顶堆。
优先队列采用顺序存储方式，其存储结构定义如下：
#define PARENT(i)i/2
typedef struct array{
int*int_array;//优先队列的存储空间首地址
int array_size;//优先队列的长度
int capacity;//优先队列存储空间的容量
}ARRAY;
【C代码】
（1）函数heapMaximum
int heapMaximum(ARRAY*A){return(1);}
（2）函数heapExtractMax
int heapExtractMax(ARRAY*A){
int max;
max=A->int_array[0];
（2）;
A->array_size--;
heapify(A,A->array_size,0);//将剩余元素调整成大顶堆
return max;
}
（3）函数maxHeapInsert
int maxHeapInsert(ARRAY*A,int key){
int i,*p;
if(A->array_size==A->capacity){//存储空间的容量不够时扩充空间
p=(int*)realloc(A->int_array,A->capacity*2*sizeof(int));
if(!p)return-1;
A->int_array=p;
A->capacity=2*A->capacity;
}
A->array_size++;
i=（3）;
while(i>0&&（4）){
A->int_array[i]=A->int_array[PARENT(i)];
i=PARENT(i);
}
（5）;
return 0;
}
【问题1】（10分）
根据以上说明和C代码，填充C代码的空（1）~（5）。
【问题2】（3分）
根据以上C代码，函数heapMaximum、heapExtractMax和maxHeapInsert的时间复杂度的紧致上界分别为（6）、（7）、（8）（用O符号表示）。
【问题3】（2分）
若将元素10插入到堆A={15，13，9，5，12，8，7，4，0，6，2，1}中，调用maxHeapInsert函数进行操作，则新插入的元素在堆A中的第（9）个位置（从1开始）。
【问题1】
（1）A->int_array[0]
（2）A->int_array[0]=A->int_array[A->array_size-1]
（3）A->array_size-1
（4）A->int_array[PARENT(i)]＜key
（5）A->int_array[i]=key
【问题2】
（6）O(1)（7）O(lgn)（8）O(lgn)
【问题3】
（9）3
【问题1】
本题考查堆数据结构的相关内容。题目告诉我们函数heapMaximum（A）的功能返回大顶堆A中的最大元素；函数heapExtractMax（A）的功能是去掉并返回大顶堆A的最大元素，将最后一个元素“提前”到堆顶位置，并将剩余元素调整成大顶堆；而函数maxHeaplnsert（A，key）的功能是把元素key插入到大顶堆A的最后位置，再将A调整成大顶堆。
第（1）空在函数heapMaximum（A）中，而且从程序中可以看出，是返回的结果，那么应该是大顶堆中最大元素，就应该是A->int_array[0]。
第（2）空在函数heapExtractMax（A）中，根据该函数的功能描述，并结合程序可以看出，第（2）空是在将最大元素移出后，那么接下了来应该处理将最后一个元素“提前”到堆顶位置，那么就应该是A->int_array[0]=A->int_array[A->array_size-1]。
第（3）（4）（5）空都在函数maxHeaplnsert（A，key）中。从程序和函数的功能我们可以知道，从程序第（3）空最后，其作用是找到元素key的插入位置并插入该元素。第（3）空是给变量i赋值，从后面的程序中我们可以看出i是做为数组下标的；而查找元素插入的位置应该从后往前的顺序，因此i的初值应该为A->array_size–1，从循环中也可以看出i的值在逐渐变小。
第（4）空是循环的一个条件，而循环的作用是找到合适的插入位置，由于大顶堆的特点是根节点的值大于左右子树节点上的值，那么找到比待插入元素大的父节点时，应该就找到了它插入的合适位置，而每次操作后i的值被赋值为PARENT（i），很显然这是找到其父节点的存储位置，因此循环结束的一个条件就是找到一个比key值大的父节点，那么循环继续的条件就是父节点的值小于key的值，所以本空的答案为A->int_array[PARENT(i)]＜key。＜key。
第（5）空就是插入元素，所以应该填A->int_array[i]=key。
【问题2】
根据题目描述，heapMaximum用来返回大顶堆A中的最大元素，而且大顶堆已经建成，只需要通过一步操作就能取到。因此时间复杂度是O（1），
而对于heapExtractMax是用来去掉大顶堆A的根，然后重新建堆，当输出堆顶结点并将堆中最后一个结点设置为根结点之后，根结点将有可能不再满足堆的性质，所幸的是整个序列也只有根结点一处的堆结构可能被破坏，其余结点仍然满足堆性质，故可利用性质进行堆调整，算法的基本思想为：将新堆顶沿着其关键字较大的孩子结点向下移动，直到叶子结点或者满足堆性质为止。因此相对于有N个元素的堆，只需要log2n次比较即可完成，因此时间复杂度是O（log2n），这与书本说堆排序的算法时间复杂度是：O(nlog2n)不冲突，因为书本上是对堆中所有元素进行操作，而这里其实相当于只将一个元素入堆，因此少了一个n。同样的道理可以得到maxHeaplnsert的时间复杂度O（log2n）。
【问题3】
这个我们可以结合题目给出的那个大顶堆的图来看，首先将key插入在最后，应该是8这个节点的右子树，由于10比8大，所以应该互换，再与节点9比较，由于10仍然大于9，所以也应该互换，这个时候再与其父节点15比较，由于小于15，所以不需要再调整，那么调整后的结果就是10这个元素应该作为根节点15的右子树。那么很显然10应该是在堆A中第3个位置。
（ ）a method of obtaining early feedback on requirements by providing aworking model of the expected product before actually building it.
【说明】
某公司现有网络拓扑结构如图1-1所示。该网络中使用交换机SW1为三层交换机，SW2和SW3均为二层智能交换机。
【问题4】（4分）
为了对用户上网行为进行监管，需要在SW1与R1之间部署（9）。
（9）备选答案：
A.FW（防火墙） B.IDS（入侵检测系统） C.堡垒机 D.上网行为管理
随着公司各部门成员增加，某些时候部分员工获取到IP地址和真实DHCP分出来IP不一致，为了避免这种情况可以在交换机上开启（10）功能。
（10）备选答案：
A．dhcp snooping B. broadcast-suppression C. loopback-detect
阅读下列说明，回答问题1至问题5，将解答填入答题纸对应栏内。 【说明】 攻克要塞教育中心在部署计算机网络时采用了一款硬件防火墙，该防火墙带有三个以太网络接口，其网络拓扑如图3-1所示。
【问题1】（8分）
防火墙包过滤规则默认策略为拒绝，表3-1给出防火墙包过滤规则配置。若要求内部所有主机能使用IE浏览器访问外部IP地址202.117.118.23Web服务器，为表中（1）~（4）空缺处选择正确答案，填写在答题纸相应位置。（1）备选答案：A．允许 B．拒绝（2）备选答案：A．192.168.1.0/24 B．211.156.169.6/30 C．202.117.118.23/24（3）备选答案：A．TCP B．UDP C．ICMP（4）备选答案：A．E3E2 B．E1E3 C．E1E2
【问题2】（6分）
内部网络经由防火墙采用NAT方式与外部网络通信，表3-2中（5）~（7）空缺处选择正确答案，填写在答题纸相应位置。（5） 备选答案：A．192.168.1.0/24 B．anyC．202.117.118.23/24（6）备选答案： A．E1 B．E2 C．E3（7）备选答案： A．192.168.1.1 B．210.156.169.6C．211.156.169.6
【问题3】（2分）
图3-1中 （8）适合设置为DMZ区。（8）备选答案：A．区域A B．区域B C．区域C【问题4】（4分）防火墙上配置信息如图3-2所示。要求启动HTTP代理服务，通过HTTP缓存提高浏览速度，代理服务端口为3128，要使主机PC1使用HTTP代理服务，其中“地址”栏中内容应填写为 （9） ，“端口”栏中内容应填写为 （10） 。
【问题5】（4分）
NAT和HTTP代理分别工作在 （11） 和 （12） 。（11）备选答案：A．网络层 B．应用层 C．服务层（12）备选答案：A．网络层 B．应用层 C．服务层
阅读以下说明，回答问题1至问题4，将解答填入答题纸对应解答栏内。
【说明】
某企业采用PIX防火墙保护公司网络安全，网络结构如图4-1所示。
【问题1】（4分）
防火墙一般把网络区域划分为内部区域（trust区域）、外部区域（untrust区域）以及(1)，其中在这个网络区域内可以放置一些公开服务器，下列(2)服务器不适合放在该区域。
空(2)备选答案：
A．Web
B．FTP
C．邮件
D．办公自动化(OA)
【问题2】（2分）
衡量防火墙性能主要参数有并发连接数、用户数限制、吞吐量等，其中最重要参数是(3)，它反映出防火墙对多个连接访问控制能力和连接状态跟踪能力，这个参数大小直接影响到防火墙所能支持最大信息点数。
空(3)备选答案：
A．并发连接数
B．用户数限制
C．吞吐量
D．安全过滤带宽
【问题3】（4分）
设置防火墙接口名称，并指定安全级别，安全级别取值范围为0～100，数字越大安全级别越高。要求设置：ethemet0命名为外部接口outside，安全级别是0；ethernet1命名为内部接口inside，安全级别是100；ethernet2命名为中间接口dmz，安全级别为50。
请完成下面命令。
…
PLX#config terminal
PLX (config)#nameif ethemet0 (4) security0
PLX (config)#nameif ethernet1 inside (5)
PLX (config)#nameif ethemet2 (6) (7)
…
【问题4】（5分）
编写表4-1中规则，设置防火墙安全规则，允许外网主机133.20.10.10访问内网数据库服务器10.66.1.101，同时允许内网和外网访问DMZ区WWW服务器10.65.1.101。
阅读以下说明，回答问题一，并将解答填入答题纸对应解答栏中。 某公司用ASP 实现了用户满意度调查网页，系统几个主要文件及作用如表1所示， 网页效果如图1 所示。
用户调查数据库表info表结构如表2所示：
问题1：完成下列代码填空
备选答案：A.用户满意度调查 B. rs C. username
D. ＜/frameset> E. dbpathF.Conn G.exec H. top.html I.info J. login.asp K.searchtext L. rs.EOF M. MoveNext N.wt1 O. rowcount
阅读下列有关网络防火墙说明，回答问题1至问题4，将答案填入答题纸对应解答栏内。
【说明】
某公司网络有200台主机、一台WebServer和一台MailServer。为了保障网络安全，安装了一款防火墙，其网络结构如图4-1所示，防火墙上配置NAT转换规则如表4-1所示。
防火墙配置遵循最小特权原则（即仅允许需要数据包通过，禁止其他数据包通过），请根据题意回答以下问题。
【问题1】（6分，每空1分）
防火墙设置缺省安全策略如表4-2所示，该策略含义为：内网主机可以访问WebServer、MailServer和Internet，Intemet主机无法访问内网主机和WebServer、MailServer。
如果要给Internet主机开放WebServerWeb服务以及MaiIServer邮件服务，请补充完成表4-3策略。（注：表4-3策略在表4-2之前生效）
【问题2】（3分，每空1分）
如果要禁止内网用户访问Internet上202.10.20.30FTP服务，请补充完成表4-4策略。
（注：表4-4策略在表4-2之前生效）
问题3】（4分，每空1分）
如果要禁止除PC1以外所有内网用户访问Internet上219.16.17.18Web服务，请补充
完成表4-5策略。（注：表4-5策略在表4-2之前生效）
【问题4】（2分，每空1分）
如果要允许Intemet用户通过Ping程序对WebServer连通性进行测试，请补充完成表4-6策略。（注：表4-6策略在表4-2之前生效）
攻克要塞一个分支机构被分配了一个C类地址192.168.36.0/24，该分支机构现在需要分配IP地址有财务、人力资源、销售、审计、计划、服务六个部门，每个部门一个子网，每个部门机器数量不超过25台。请回答以下问题。
【问题1（6分）
为给这六个部门分配IP地址，请问子网掩码是多少，每个子网有多少个地址，可以分配地址有多少？
【问题2】（3分）
给六个部门分配完地址后，还有多少剩余地址，假设地址是从192.168.36.0开始分配，请列出剩余地址段？
【问题3】（3分）
请问地址192.168.36.111网络地址是多少，该网络广播地址是多少？
【问题4】（3分）
该分支机构采用VLAN实现网段划分，请问常规做法是采用什么网络设备实现VLAN划分和互通？
试题一（23分）阅读下列说明，回答问题1至问题4，将解答填入答题纸对应栏内。 【说明】 DHCP是动态主机配置协议，这个协议用于向计算机自动提供IP地址、子网掩码和路由信息。如果由网络管理员分配局域网上客户机IP地址，则会费时费力且容易出错。因此采用DHCP自动分配地址，这时局域网上客户机会向DHCP服务器请求一个IP地址，然后DHCP服务器为每个请求客户机分配一个地址，直到分配完该范围内所有IP地址为止，已经分配IP地址必须定时地延长租用期。这确保了当客户机设备在正常地释放IP地址之前，如果该客户机突然从网络断开，被分配地址就可以归还给服务器。DHCP配置文件中option（选项）如表1-1所示。
【问题1】（5分）
请根据表1-1中选项，把（1）~（5）填写完整。【问题2】（6分）在Linux系统中有如下3个语句，请分别说出它们所执行任务名称。（1）/etc/rc.d/init.d/dhcpd start。（2）/etc/rc.d/init.d/dhcpd stop。（3）/etc/rc.d/init.d/dhcpd restart。【问题3】（8分）Dhcp客户端发出第一个数据包目标MAC地址是（6），目标IP地址是（7），源MAC地址是（8），源IP地址是（9）.【问题4】（4分）简述DHCP协议分配IP地址主要过程？
试题二（13分）
阅读下列说明，回答问题1至问题5，将解答填入答题纸对应栏内。 【说明】 某一网络地址块192.168.75.0中有5台主机A、B、C、D和E，它们IP地址及子网掩码如表4-1所示。
【问题1】（5分）
5台主机A、B、C、D、E分属几个网段？哪些主机位于同一网段？【问题2】（2分）主机D网络地址为多少？【问题3】（2分）若要加入第六台主机F，使它能与主机A属于同一网段，其IP地址范围是多少？【问题4】（2分）若在网络中另加入一台主机，其IP地址设为192.168.75.164，它广播地址是多少？哪些主机能够收到？【问题5】（2分）若在该网络地址块中采用VLAN技术划分子网，何种设备能实现VLAN之间数据转发？
阅读以下说明，回答问题1至问题3，将解答填入答题纸对应解答栏内。【说明】某公司网络拓扑结构如图 3-1 所示。网络规划如表3-1所示。
【问题1】（3分，每空1分）如图3-1所示，防火墙接口GE0/0/0、GE0/0/1和GE0/0/2分属于（ 1 ）、（ 2 ）、（ 3 ）。（1）~（2）备选项：A.trust区域 B.untrust区域 C.DMZ区域 （1）（2）（3） 【问题2】（8分，每空2分）如图3-1所示，ISP1作为公司默认互联网出口。该公司拥有2条出口链路，要保证内网机器能够访问互联网，需要在路由器上配置（ 4 ），用户希望服务器网段流量都走ISP2出去，则需要在路由器上配置（ 5 ），因为服务器网段IP地址是内网地址，服务器要对Internet提供服务，需要在路由器上配置（ 6 ），生产区和办公区访问互联网默认走ISP1出去，需要在路由器上配置（ 7 ）。（4）~（7）备选项：A.策略路由 B.缺省路由 C. 源NAT D.目NAT （4）（5）（6）（7） 【问题3】（9分，每空1分）生产区和办公区用户流量默认走ISP1出口，服务器区域流量走ISP2出口。请根据描述，将下面配置代码补充完整。R1基本配置略……[R1]interface GigabitEthernet 0/0/1[R1-GigabitEthernet0/0/1]ip address 58.60.36.2 29[R1-GigabitEthernet0/0/1]quit[R1]interface GigabitEthernet 0/0/2[R1-GigabitEthernet0/0/2]ip address （ 8 ）[R1-GigabitEthernet0/0/2]quit[R1]interface GigabitEthernet 0/0/0[R1-GigabitEthernet0/0/0]ip address 192.168.200.1 24[R1-GigabitEthernet0/0/0]quit[R1]acl（ 9 ）[R1-acl-basic-2000]rule permit source 192.168.8.0 （10）[R1-acl-basic-2000]rule permit source 192.168.100.0 0.0.0.255[R1-acl-basic-2000]rule permit source 192.168.200.0 0.0.0.255[R1-acl-basic-2000]quit[R1]acl 2001[R1-acl-basic-2001]rule permit source 192.168.100.0 0.0.0.255[R1-acl-basic-2001]quit[R1]nat address-group 1 58.60.36.3 58.60.36.6[R1]interface GigabitEthernet 0/0/1[R1-GigabitEthernet0/0/1]nat outbound 2000 address-group 1[R1-GigabitEthernet0/0/1]quit[R1]interface GigabitEthernet 0/0/2[R1-GigabitEthernet0/0/2]nat outbound 2000[R1-GigabitEthernet0/0/2]quit[R1]ip route-static 192.168.8.0 22 （ 11 ）[R1]ip route-static 192.168.100.0 24 （ 12 ）[R1]ip route-static 0.0.0.0 0 58.60.36.1[R1]ip route-static 0.0.0.0 0 113.250.13.1（ 13 ）//把ISP2这条链路作为浮动路由，作为应急触发备份路径[R1]traffic classifier （14）[R1-classifier-c1]if-match acl 2001 [R1-classifier-c1]quit[R1]traffic behavior b1[R1-behavior-b1]redirect ip-nexthop 113.250.13.1[R1-behavior-b1]quit[R1]traffic policy p1[R1-trafficpolicy-p1]classifier c1 behavior b1[R1-trafficpolicy-p1]quit[R1]interface （ 15 ）[R1-GigabitEthernet0/0/0]traffic-policy p1(16) [R1-GigabitEthernet0/0/0]quit[R1]……（8）-（15） 备选答案A．113.250.13.2 30 B.192.168.200.2 C. GigabitEthernet0/0/0 D. preference 100 E. 192.168.200.3 F. 0.0.3.255 G. 2000 H. c1I. inbound （8）（9）（10）（11）（12）（13）（14）（15）（16）
