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

推荐等级：
发布时间：2021-12-15 10:37
卷面总分：59分
答题时间：240分钟
试卷题量：59题
练习次数：2次
试卷分类：中级软件设计师
试卷类型：历年真题

开始做题

试卷预览

单选题

在Windows系统中，为排除DNS域名解析故障，需要刷新DNS解析器缓存，应使用的命令是（　　）。

查看答案开始考试

正确答案：B

本题解析：

ipconfig/renew的含义是更新所有适配器的 DHCP 配置。该命令仅在具有配置为自动获取 IP 地址的适配器的计算机上可用。

ipconfig/flushdns的含义是刷新并重设DNS解析器缓存。

netstat –r用于显示核心路由表。

arp –a用于查看ARP高速缓存中的内容。

单选题

设算法A的时间复杂度可用递归式中级软件设计师,历年真题,2011年下半年（上午）《软件设计师》真题表示，算法B的时间复杂度可用递归式表示，若要使得算法B渐进地快于算法A，则a的最大整数为（　　）。

查看答案开始考试

正确答案：A

本题解析：

题目要求使得算法B渐进地快于算法A，即B的时间复杂度小于A的时间复杂度。

对算法A进行简单的化简，令n=n/2，我们可以得到算法A的T(n)=49T(n/4)+11/4n2；

而算法B的T(n)=aT(n/4)+n2，而根据渐进的规则，算法A的时间复杂度应该为49T(n/4)，而算法B的时间复杂度应该为aT(n/4)，因此a的取值应该要小于49，本题只有A选项符合。

单选题

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

查看答案开始考试

正确答案：A

本题解析：

分治法：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决；否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。本题的算法思想是分治法的思想。

动态规划法：这种算法也用到了分治思想，它的做法是将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题。

贪心算法：它是一种不追求最优解，只希望得到较为满意解的方法。贪心算法一般可以快速得到满意的解，因为它省去了为找到最优解而穷尽所有可能所必须耗费的大量时间。贪心算法常以当前情况为基础做最优选择，而不考虑各种可能的整体情况，所以贪心算法不要回溯。

回溯算法（试探法）：它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。其实现一般要用到递归和堆栈。

单选题

一棵满二叉树，其每一层结点个数都达到最大值，对其中的结点从l开始顺序编号，即根结点编号为1，其左、右孩子结点编号分别为2和3，再下一层从左到右的编号为4、5、6、7，依此类推，每一层都从左到右依次编号，直到最后的叶子结点层为止，则用（　　）可判定编号为m和n的两个结点是否在同一层。

中级软件设计师,历年真题,2011年下半年（上午）《软件设计师》真题

查看答案开始考试

正确答案：B

本题解析：

如果是满二叉树，那么其第n层的结点数应该是第n-1层结点数的两倍，从根（第一层）开始，各层的结点数应分别是2n-1个，其中n为当前的层次，因此一颗x层的满二叉树，其总的结点数位2x-1个。而如果知道结点编号m，我们可以用log2m+1来求取该结点属于那一层，同样，对于编号为n的结点，所属层次为log2n+1，两者属于同一层次则应该满足log2m+1=log2n+1，因此B选项log2m=log2n符合要求。

单选题

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

查看答案开始考试

正确答案：D

本题解析：

在无向图中，一条边连接两个顶点，即如果存在一条边，那么与这条边相关的两个顶点的度都为加1，那么总的度就应该加2，因此，如果图中有n条边，那么所有顶点的度数之和就应该为2e。

单选题

对于线性表（由n个同类元素构成的线性序列），采用单向循环链表存储的特点之一是（　　）。

查看答案开始考试

正确答案：A

本题解析：

采用单向循环链表存储的特点之一是从表中任意结点出发都能遍历整个链表，另外便于元素的元素节点的删除与插入。如需要对表中的任意节点进行随机访问需采用顺序存储结构。