2010年下半年（上午）《软件设计师》真题

试卷预览

1 单选题 1分

帧中继作为一种远程接入方式有许多优点，下面的选项中错误的是（　　）。

查看答案 开始考试

正确答案：C

本题解析：

帧中继是在X.25协议的基础上发展起来的面向可变长度帧的数据传输技术，它减少X.25的一些流量和差错控制过程，相对X.25来说，通信开销少，传输速度更快。

DDN是数字数据网的简称，是一种我们平时所说的专线上网方式，它将数万、数十万条以光缆为主体的数字电路，通过数字电路管理设备，构成一个传输速率高、质量好，网络延时小，全透明、高流量的数据传输基础网络。

帧中继提供面向连接的虚电路服务，因而比DDN专线更能提高通信线路利用率，用户负担的通信费用也更低廉。

相对DDN来说，帧中继具有更灵活的方式来支持突发式通信。

2 单选题 1分

（　　）不能保证求得0-1背包问题的最优解。

查看答案 开始考试

正确答案：B

本题解析：

分支限界法一般以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间，那么肯定能找出最优解。

贪心算法的思想是：总是做出在当前来说是最好的选择，而并不从整体上加以考虑，它所做的每步选择只是当前步骤的局部最优选择，但从整体来说不一定是最优的选择。所以用该算法并不能保证求得0-1背包问题的最优解。

回溯法的思想是：按选优条件向前搜索，以达到目标。但当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。它其实是遍历了整个解空间，所以肯定能找到最优解。

动态规划法的思想是：在求解问题中，对于每一步决策，列出各种可能的局部解，再依据某种判定条件，舍弃那些肯定不能得到最优解的局部解，在每一步都经过筛选，以每一步都是最优解来保证全局是最优解。它能求得0-1背包问题的最优解。

3 单选题 1分

下面C程序段中count++语句执行的次数为（　　）。

for（inti=1；i＜=11；i*=2）

for（intj=1；j＜=i；j++）

count++；

查看答案 开始考试

正确答案：A

本题解析：

本题中给出的是一个双重循环结构，循环体就是count++。第一层循环的循环次数为4次，分别为i=1，2，4，8的情况。而当i=1时，第二层循环循环1次；当i=2时，第二层循环2次；当i=4时，第二层循环4次；当i=8时，第二层循环8次。那么可知循环体一共执行了1+2+4+8=15次。

4 单选题 1分

用动态规划策略求解矩阵连乘问题M1*M2*M3*M4，其中M1（20*5）、M2（5*35）、M3（35*4）和M4（4*25），则最优的计算次序为（　　）。

查看答案 开始考试

正确答案：C

本题解析：

这个题目的关键是要求最优的计算次序，也就是要求计算过程中，乘法的次数最小。如果用选项A的次序来计算，需要计算的乘法次数为：20*5*35+20*35*4+20*4*25。同样我们可以求出其它三种方法所需的乘法次数。其中最小的是选项C的5*35*4+20*5*4+20*4*25。

5 单选题 1分

（　　）是右图的合法拓扑序列。

查看答案 开始考试

正确答案：A

本题解析：

本题主要考查拓扑序列。

在给出拓扑图求拓扑序列时，我们应该掌握一个关键因素，那就是箭头的画出节点在箭头指向节点前，如果一个节点被很多箭头所指，那么应该要在所有这些箭头的画出节点之后才是本节点。拓扑序列的开始节点应该是没有箭头所指的节点，在本题中应该是5或6，这里需要注意它们谁在最前面都可以。那么按照这个原则我们就可以知道本题的拓扑序列应该为654321或者564321。

6 单选题 1分

下面关于哈夫曼树的叙述中，正确的是（　　）。

查看答案 开始考试

正确答案：C

本题解析：

哈夫曼树是一种特殊的二叉树，但它不是完全二叉树，也不是平衡二叉树，给出n个权值{w1，w2，…，wn}构造一棵具有n个叶子结点的哈夫曼树的方法如下：

第一步，构造n个只有根结点的二叉树集合F={T1，T2，…，Tn}，其中每棵二叉树Ti的根结点带权为Wi（1≤k≤n）；

第二步，在集合F中选取两棵根结点的权值最小的二叉树作为左右子树，构造一棵新的二叉树，令新二叉树根结点的权值为其左、右子树上根结点的权值之和；

第三步，在F中删除这两棵二叉树，同时将新得到的二叉树加入到F中；

第四步，重复第二步和第三步，直到F只含有一棵二叉树为止，这棵二叉树便是哈夫曼树。

综上所述，我们可以知道哈夫曼树中权值最小的两个结点互为兄弟结点。

7 单选题 1分

设循环队列Q的定义中有rear和len两个域变量，其中rear表示队尾元素的指针，len表示队列的长度，如下图所示（队列长度为3，队头元素为e）。设队列的存储空间容量为M，则队头元素的指针为（　　）。

查看答案 开始考试

正确答案：D

本题解析：

对于循环队列，求队头元素的指针的计算公式为：（rear-len+1+M）%M。

求队列中元素个数公式为：（rear-fear+M）%M。其中fear表示队列的对头指针。

8 单选题 1分

以下关于汇编语言的叙述中，错误的是（　　）。

查看答案 开始考试

正确答案：B

本题解析：

面向机器的程序设计语言，使用汇编语言编写的程序，机器不能直接识别，要由一种程序将汇编语言翻译成机器语言，这种起翻译作用的程序叫汇编程序。汇编程序输入的是用汇编语言书写的源程序，输出的是用机器语言表示的目标程序。

9 单选题 1分

以下关于可视化程序设计的叙述中，错误的是（　　）。

查看答案 开始考试

正确答案：A

本题解析：

可视化程序设计主要是让程序设计入员利用软件本身所提供的各种控件，像搭积木式地构造应用程序的各种界面。可视化程序设计最大的优点是设计入员可以不用编写或只需编写很少的程序代码，就能完成应用程序的设计，这样就能极大地提高设计入员的工作效率。在可视化程序设计中，可随时查看程序的运行效果。

10 单选题 1分

下图所示为两个有限自动机Ml和M2（A是初态、C是终态），（　　）。

查看答案 开始考试

正确答案：D

本题解析：

本题主要考查确定有限自动机与非确定有限自动机的判断。

非确定有限状态自动机与确定有限状态自动机的最大区别是它们的转移函数不同。确定有限状态自动机对每一个可能的输入只有一个状态的转移。非确定有限状态自动机对每一个可能的输入可以有多个状态转移，接受到输入时从这多个状态转移中非确定地选择一个。

在本题中给出的图M1中，我们可以看到当在状态A输入0时，它可以转移到它自己，也可以转移到状态B，所以M1是非确定的。而M2中不存在这样的情况，因此是确定的有限自动机。