软件水平考试中级软件设计师上午(基础知识)历年真题试卷汇编9(.pdfVIP

软件水平考试中级软件设计师上午（基础知识）历年真题试卷汇编9

(题后含答案及解析)

题型有：1.选择题

选择题（每小题1分，共75分）下列各题A、B、C、D四个选项中，只有

一个选项是正确的，请将此选项涂写在答题卡相应位置上，答在试卷上不得分。

(2013年上半年上午试题62、63)给定n个整数构成的数组A={a1，a2，……，

an}和整数x，判断A中是否存在两个元素ai和aj，使得ai+aj=x。为了求解问题，

首先用归并排序算法对数组A进行从大到小排序；然后判断是否存在ai+aj=x，

具体的方法如下列伪代码所示。则求解该问题时排序算法应用了________(62)算

法设计策略，整个算法的时间复杂度为_____(63)。i=1；j=nwhilei＜jIfai+aj=x

returntrueElseifai+aj＞xJ--；ElseI++；Returnfalse；

1．(62)

A．分治

B．贪心

C．动态规划

D．回溯

正确答案：A

解析：分治算法的基本思想是将一个规模为n的问题分解为k个规模较小的

子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到

原问题的解。知识模块：算法设计和分析

2．(63)

A．O(n)

B．O(nlgn)

C．O(n2)

D．O(nlg2n)

正确答案：B涉及知识点：算法设计和分析

(2012年下半年上午试题62、63)将数组{1，1，2，4，7，5}从小到大排序，

若采用________(62)排序算法，则元素之间需要进行的比较次数最少，共需要进

行_________(63)次元素之间的比较。

3．(62)

A．直接插入

B．归并

C．堆

D．快速

正确答案：A

解析：直接插入排序算法的基本思想是将待排序数组分为两个部分：已排好

序部分和未排序部分。其主要步骤为：开始时，第一个元素在已排好序部分中，

其余部分在未排序部分。然后依次从未排序部分中取出第一个元素，从后向前与

排好序部分的元素进行比较并将其插入已排好序部分的正确位置，直到所有元素

排好序。当序列基本有序时，直接插入排序过程中元素比较的次数较少；当序列

为逆序时，元素的比较次数最多。使用直接插入排序算法，数组{1，1，2，4，7，

5}需要比较6次，依次为：1与1比较、2与1比较、4与2比较、7与4比较、

5与7比较、5与4比较。归并排序的基本思想是将待排序数组划分为子问

题，对子问题求解，然后合并解。其主要步骤为：将数组分为两个相同规模的子

数组，分别包含前n／2个元素和后n／2个元素；递归地排序这两个子数组；合

并排好序的两个子数组，依次比较两个排好序的子数组的元素，得到整个数组的

排好序的序列。使用归并排序算法，数组{1，1，2，4，7，5}需要比较8次。知

识模块：算法设计和分析

4．(63)

A．5

B．6

C．7

D．8

正确答案：B涉及知识点：算法设计和分析

(2012年下半年上午试题64、65)哈夫曼编码将频繁出现的字符采用短编码，

出现频率较低的字符采用长编码。具体的操作过程为：i)以每个字符的出现频率

作为关键字构建最小优先级队列；ii)取出关键字最小的两个节点生成子树，根节

点的关键字为孩子节点关键字之和，并将根节点插入最小优先级队列中，直至得

到一棵最优编码树。哈夫曼编码方案是基于_______(64)策略的，用该方案对包

含a到f六个字符的文件进行编码，文件包含100000个字符，每个字符的出现

频率(用百分比表示)如表9．3所示，则与固定长度编码相比，该编码方案节省

了_______(65)存储空间。

5．(64)

A．分治

B．贪心

C．动态规划

D．回溯

正确答案：B

解析：贪心算法在解决最优化问题上是仅根据当前已有的信息做出选择，即

不是从整体最