单项选择题

第1题、设n是描述问题规模的非负整数，下列程序段的时间复杂度是 x=0; while(n>=(x+l)*(x+l)) x=x+l;

A.O(log n)

B.O(n1/2)

C.O(n)

D.O(n2)

参考答案：B

第2题、若将一棵树T转化为对应的二又树BT，则下列对BT的遍历中，其遍历序列与T的后根遍历序列相同的是

A.先序遍历

B.中序遍历

C.后序遍历

D.按层遍历

参考答案：B

第3题、对n个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有115个结点，则n的值是

A.56

B.57

C.58

D.60

参考答案：C

第4题、在任意一棵非空平衡二又树(AVL树)T1中，删除某结点v之后形成平衡二又树T2，再将w插入T2形成平衡二又树T3。下列关于T1与T3的叙述中，正确的是 I.若v是T1的叶结点，则T1与T3可能不相同 Ⅱ.若v不是T1的叶结点，则T1与T3一定不相同 Ⅲ.若v不是T1的叶结点，则T1与T3一定相同

A.仅I

B.仅II

C.仅I、Ⅱ

D.仅I、Ⅲ

参考答案：A

第5题、下图所示的AOE网表示一项包含8个活动的工程。活动d的最早开始时间和最迟开始时间分别是

A.3和7

B.12和12

……此处隐藏18261个字…… 4KB，所以虚拟地址的高20位为虚拟页号。第1行指令和第30行指令的虚拟地址高20位都是00401H，因此两条指令在同一页中。 Cache组数为64/4=16，因此，主存地址划分中，低6位为块内地址、中间4位为组号(组索引)、高22位为标记。 读取第16行call指令时，只可能在指令Cache第0组中命中。 因为页大小为4KB，所以虚拟地址和物理地址的最低12位完全相同，因而call 指令虚拟地址0040 1025H中的025H=0000 0010 0101B=00 0000 100101B为物理地址的低12位，故对应Cache组号为0。

第47题、(9分)某网络拓扑如题47图所示，其中R为路由器，主机H1~H4的IP地址配置以及R的各接口IP地址配置如图中所示。现有若干台以太网交换机(无VLAN功能)和路由器两类网络互连设备可供选择。 请回答下列问题： (1)设备1、设备2和设备3分别应选择什么类型网络设备? (2)设备1、设备2和设备3中，哪几个设备的接口需要配置IP地址?并为对应的接口配置正确的IP地址。 (3)为确保主机H1~H4能够访问Internet，R需要提供什么服务? (4)若主机H3发送一个目的地址为192.168.1.127的IP数据报，网络中哪几个主机会接收该数据报?________________

参考答案：

(1)设备1：路由器，设备2：以太网交换机，设备3：以太网交换机 (2)设备1的接口需要配置IP地址;设备1的IFl、IF2和IF3接口的IP地址分别是：192.168.1.254、192.168.1.1和192.168.1.65。 (3)R需要提供NAT服务 (4)主机H4会接收该数据报。