2 0 1 3 年 下 半 年 软 件 设 计 师 上 午
答案为：C
●以下关于哈夫曼树的叙述，正确的是(60)。
(60)A 哈夫曼树一定是满二叉树，其每层结点数都达到最大值
B 哈夫曼树一定是平衡二叉树，其每个结点左右子树的高度差为-1、0、1 C.哈夫曼树中左孩子结点的权值小于父结点、右孩子结点的权值大于父结点 D、哈夫曼树中叶子结点的权值越小则距离树根越远、叶子结点的权值越大 则距离树根越近 答案为：D
● 其哈希表（散列表）的长度为 N，设散列函数为 H（Key）=Key mod p ,采用 线性探测法解决冲突。以下关于 P 值的所述中，正确是（61） （61）A．P 的值一般为不大于 n 且最接近 n 的质数
B. P 的值一般为大于 n 的任意整数 C. P 的值必须为小于 n 的合数 D. P 的值必须等于 n 答案为：A?
● 对 n 个基本有序的整数进行排序，若采用插入排序算法，则时间和空间复杂 度分(62) ；若采用快速排序算法，则时间和空间复杂度分别为(63)。 (62）A.O(n2）和 O(n)
B．O(n)和 O(n) C. O(n2）和 0(1) D．O(n)和 0(1)
(63) A.O(n2）和 O(n) B．O(nlgn)和 O(n) C.0(n)和 0(1) D．O(nlgn)和 O(1)
希赛网的分析：此题答案应该是62：D 63：A。因为整数是基本有序的。另外从给的选择中，快速排序算法的空间复杂度只有O（1） O（N） 2个选择，没有O(lgn) 说明是要考虑有序这个问题。
● 在求解某问题时，经过分析发现该问题具有最优子结构性质，求解过程中子问题被重复求解，则采用（64）算法设计策略，以深度优先的方法是搜索解 空间，则采用（65）算法设计策略。
（64）A.分治 B.动态规划 C.贪心 D. 回溯 （65）A动态规划 B贪心 C.回溯 D.分治限界 答案为：64： B 65：C
动态规划算法总体思想：如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法
从根开始计算，到找到位于某个节点的解，回溯法（深度优先搜索）作为最基本的搜索算法，其采用了一种“一只向下走，走不通就掉头”的思想（体会“回溯”二字），相当于采用了先根遍历的方法来构造搜索树。
●某单位的局域网配置如下图所示，PC2发送到Interet上的源IP地址为（66）
13
PC1 192.168.0.3／24
2 0 1 3 年 下 半 年 软 件 设 计 师 上 午
PC2 192.168.O.2／24
PC3 192.168.0.4／24
(66)A．192．168．0．2 B． 192．168．O．1
C．202．117．112．1 D．202．117．112．2 参考答案： D
解释：在Internet上仅能有公网IP地址，也就是代理服务器的公网IP地址 来源：2013年下半年网络工程师试题40
●在 IPv4 向 IPv6 过渡期间，如果要使得两个 IPv6 结点可以通过现有的 IPv4 网络进行通则应该使用(67)；如果要使得纯 IPv6 结点可以与纯 IPv4 结点进行 通信，则需要使用(68) 。
(67)A．堆栈技术 B．双协议栈技术 C．隧道技术 D．翻译技术
(68)A 堆栈技术 B．双协议栈技术 C．隧道技术 D．翻译技术
答案为：67：B 68：C 双栈方式是过渡阶段的一种主要的方式。双栈方式是指主机同时运行IPv4和IPv6两套协议栈，同时支持两个版本的网络层IP协议标准。主机和路由器都可以通过双栈方式来获得和IPv4及IPv6结点的通信能力
随着IPv6网络的发展，出现了许多局部的IPv6网络，但是这些IPv6网络需要通过IPv4骨干网络相连。将这些孤立的“IPv6岛”相互联通必须使 用隧道技术。隧道策略是IPv4/v6综合组网技术中经常用到的一种机制。隧道利用一种协议来传输另一种协议的数据。它包括隧道入口和隧道出口（隧道终 点），这些隧道端点通常都是双栈节点。在隧道入口，以一种协议的形式来对另外一种协议的数据进行封装并发送；在隧道出口，对接收到的协议数据解封装，并做 相应的处理。通常，在隧道入口还要维护一些与隧道相关的信息，如记录隧道MTU等参数；在隧道出口，出于安全性考虑，要对封装的数据进行过滤，以防止来自 外部的恶意攻击
●POP3 协议采用(69)模式进行通信，当客户机需要服务时，客户端软件与 POP3
服务器建立_(70)连接。 (69) A．Browser/Server
B．Client/Server C.Peer to Peer D．Peer to Server
(70)A．TCP B.UDP C.php D.IP
答案为：69：B 70:A POP适用于C/S结构的脱机模型的电子邮件协议，目前已发展到第三版，称POP3。脱机 模型即不能在线操作，不像IMAP4（netscape支持IMAP4）
14
2 0 1 3 年 下 半 年 软 件 设 计 师 上 午
POP3邮件服务器通过侦听TCP端口110提供POP3服务。客户端软件读取邮件之前，需要事先
与服务器建立TCP连接。连接成功后，POP3服务器会向该客户端发送确认消息。然后客户端根据服务器回送的信息决定下一步的操作。
客 户端每次向POP3服务器发送命令后，都要等待服务器响应，并处理接收的信息，然后再接着发送下一个命令，如此往复多次，一直持续到连接终止。这个过程经 历了三个状态：授权（AUTHORIZATION）状态、操作（TRANSACTION）状态和更新（UPDATE）状态。
15
2 0 1 3 年 下 半 年 软 件 设 计 师 上 午
●<
T h e r e i s n o t h i n g i n t h i s w o r l d c o n s t a n t ,
b u t i n c o n s t a n c y . — — J . S w i f t >
Project after project designs a set of algorithms and then plunges intoconstruction of customer-deliverable software on a schedule that demands delivery of the first thing built.
In most projects, the first system built is (71) usable. It may be too slow, too big , awkward to use, or all three. There is no (72 ) but to start again, smarting but smarter and build a redesigned version in which these problems are solved. The discard and (73) may be done in one lump, or it may be done piece-by-piece. But all large-system experience shows that it will be done. Where a new system concept or new technology is used, one has to build a syste m to throw away, for even the best
planning is not so omniscient (全知的) as to get it fight the first time.
the management question, therefore, is not whether to build a pilot system and throw it away. You will do that. The only question is whether to plan in advance to build a (74). or to promise to deliver the throwaway to customers. Seen this way, the answer is much clearer. Delivering that throwaway to customers buys time, but it does so only at the (75) of agony (极大痛苦) for the user, distraction for the builders while they do the redesign, and a bad..reputation for the product that the best redesign will find hard to live down.
Hence plan to throw one away; you will, anyhow.
在大多数项目中，第一个系统是几乎无法使用。它可能是太慢，太大，不好用，或所有三。没有办法，但再次开始，但更为，并建立一个重新设计的版本中，这些问题都解决了。丢弃或重新设计可能是一次性完成的，或者可能是由片做了件。但所有的大型系统的经验表明，它会做的。?
管理问题，因此，不在于是否建立一个试验系统，扔掉它。你会这样做。唯一的问题是，是否要提前建立一次性计划，或承诺提供一次性客户。这样看来，答案是很清晰。提供一次性客户赢得了时间，但它只有在用户的痛苦成本，分心的建设者而他们做了重新设计，并对最佳的重新设计将难以活下来的产品一个坏名声。
(71) A. almost (73) A. design (74) A. throwaway (75) A. worth
B. often B. redesign B. system
C. usually C. plan C. software
D. barely D. build D. product
(72) A. alternative B. need C. possibility D. solution B. value C. cost D. invaluable
16
相关推荐：
loading