2011年11月软考软件设计师-上午试题（标准参考答案版）

●Extreme Programming (XP) is a discipline ofsoftware development with   (71)   of simplicity, communication, feedback and courage. Successful software development is a team effort - not just the development team, but the larger team consisting of customer, management and developers. XP is a simple process that brings these people together and helps them to succeed together. XP is aimed primarily at object-oriented projects using teams of a dozen or fewer programmers in one location. The principles of XP apply to any   (72)   project that needs to deliver quality software rapidly and flexibly.

●在Windows系统中，为排除DNS域名解析故障，需要刷新DNS解析器缓存，应使

用的命令是(70) 。

(70)

●TCP是互联网中的(68)协议，使用 (69)次握手协议建立连接。

(68)

 ●A类网络是很大的网络，每个A类网络中可以有(66)个网络地址。实际使用中必须把A类网络划分为子网，如果指定的子网掩码为255.255.192.0，则该网络被划分为(67)个子网。

(66)

(65)

 ●在有n个无序无重复元素值的数组中查找第i小的数的算法描述如下：任意取一个 元素r，用划分操作确定其在数组中的位置，假设元素r为第k小的数。若i等于k，则返回该元素值；若i小于k，则在划分的前半部分递归进行划分操作找第i小的数；否则在划分的后半部分递归进行划分操作找第k-i小的数。该算法是一种基于(63)策略的算法。

(63)

●对n个元素值分别为-1、0或1的整型数组A进行升序排序的算法描述如下：统计A中-1、0和1的个数，设分别为n₁、n₂和n₃，然后将A中的前n₁个元素赋值为-1，第n₁+l到n_l+n₂个元素赋值为0，最后n₃个元素赋值为1。该算法的时间复杂度和空间复杂度分别为(64)。

● (61)一是由权值集合{8，5，6，2）构造的哈夫曼树（最优二叉树）。

(61)A．   B．   C．   D．

●迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径，本质上说，该算法是一种基于(62)策略的算法。

(62)

●无向图中一个顶点的度是指图中与该顶点相邻接的顶点数。若无向图G中的顶点数为n，边数为e，则所有顶点的度数之和为(59)。

(59)