单项选择题

第1题、下列程序段的时间复杂度是______。int sum=0;for(int i=1; i

A.O(logn)

B.O(n)

C.O(nlogn)

D.O(n2 )

参考答案：B

题中程序经分析可知共有两层循环，外层循环中，每次i都乘2，当i≥n时，即程序执行log2 n次后，不再执行原来的循环。内循环次数i=2k (k=0，1，2，3，…，n-1)，k为外循环执行次数。外循环执行一次时，此时内循环执行1次;外循环执行两次时，内循环执行次数为2次，当外循环执行第三次时，内循环执行的次数为22 ，外循环执行第四次时，内循环执行23 。依次类推发现执行的次数即为有关2的等比数列，所求总循环次数即为求等比数列的和，即求1+2+4+8+…+2n-1 ，这n个数据的和。代入等比数列公式求和公式计算结果得到2n -1，时间复杂度为O(n)。

第2题、给定有限符号集S，in和out均为S中所有元素的任意排列。对于初始为空的栈ST，下列叙述中，正确的是______。

A.若in是ST的入栈序列，则不能判断out是否为其可能的出栈序列

B.若out是ST的出栈序列，则不能判断in是否为其可能的入栈序列

C.若in是ST的入栈序列，out是对应in的出栈序列，则in与out一定不同

D.若in是ST的入栈序列，out是对应in的出栈序列，则in与out可能互为倒序

参考答案：D

由入栈序列可以找到出栈序列，A错误;已知i ……此处隐藏40843个字…… times;数据传输速率=以太网的最小帧长，以及题目中条件可得：设最远距离为L，则[1.51μs+L/(2×108 m/s)]×100Mb/s×2，解得L=210m。

第60题、在H4通过DHCP动态获取IP地址过程中，H4首先发送了DHCP报文M，M是哪种DHCP报文?路由器E0接口能否收到封装M的以太网帧?S向DHCP服务器转发的封装M的以太网帧的目的MAC地址是什么?

参考答案：

已知H4与H5已接入网络，且通过DHCP动态获取IP地址。在通过DHCP动态获取IP地址过程中，H4先以广播形式发送DHCP DISCOVER报文(DHCP发现报文)。由图可知，H5、路由器R的接口E0、DHCP服务器与H4都在一个网络区域，所以H4发送的报文，它们都可以接收到。而广播地址：FF-FF-FF-FF-FF-FF，即为S转发出的封装该报文的以太网帧的MAC地址。

第61题、若H4向H5发送一个IP分组P，则H5收到的封装P的802.11帧的地址1、地址2和地址3分别是什么?

参考答案：

H4向H5发送一个IP分组过程中，该IP分组被封装在其中一个802.11帧中发送给AP，AP将其解封后重新封装在另一个802.11帧，然后发送给H5。这两个802.11帧的首部与题中相关取值分别如下：