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

试卷预览

1 单选题 1分

要使4个连续的C类网络汇聚成一个超网，则子网掩码应该为（　　）。

查看答案 开始考试

正确答案：C

本题解析：

本题主要考查网络汇聚的相关知识。

我们可以知道C类地址的子网掩码为255.255.255.0，而四个子网需要用2位来表示，因此如果要将4个连续的C类网络汇聚成一个超网，只需将子网掩码第3个字节的最后两位都变成0即可，因此超网的子网掩码是255.255.252.0。

2 单选题 1分

某算法的时间复杂度可用递归式表示，若用表示，则正确的是（　　）。

查看答案 开始考试

正确答案：A

本题解析：

【《软件设计师教程（第5版）》--P422页】

根据主定理（定理8.1）进行推导。

此递归式中，a=6，b=5，其中f（n）=O（nlogba-ε）=O（n），其中log56-ε=1，所以ε>0，因此本题符合规则（1）。

因此对于递归式的时间复杂度，T（n）=O（nlogba），因此本题选择A选项。

3 单选题 1分

对于关键字序列（26，25，72，38，8，18，59），采用散列函数H（Key）=Keymod13构造散列表（哈希表）。若采用线性探测的开放定址法解决冲突（顺序地探查可用存储单元），则关键字59所在散列表中的地址为（　　）。

查看答案 开始考试

正确答案：D

本题解析：

根据题目给出的散列函数我们可以分别计算出关键字（26，25，72，38，8，18，59）对应的散列地址分别为（0，12，7，12，8，5，7）。

开放定址处理冲突的基本思路是为发生冲突的关键字在散列表中寻找另一个尚未占用的位置，其解决冲突能力的关键取决于探测序列，在本题中，题目告诉我们采用顺序探查法，即增量为1的线性探测法，在该线性探测法中，设Hi（1≤i＜m）为第i次在散列表中探测的位置，其中增量序列为{1，2，3，4，5，…，m-1}则有：

Hi=（H（Key）+i）%m

其中H（Key）为散列函数，m为散列表长度，i为增量序列。而本题中m=13。因此本题的散列表构造过程如下：

（1）关键字26，25，72由散列函数H（key）得到没有冲突的散列地址而直接存入散列表中。

（2）计算关键38的散列地址为12，发生冲突（与关键字25冲突），其第一次线性探测地址为（12+1）%13=0，但仍然发生冲突（与关键字26冲突），因此需要进行第二次线性探测，其地址为（12+2）%13=1，这时没有发生冲突，即将38存入地址为1的空间。

（3）接着将关键字8，18计算其散列地址，由于没有冲突，即分别存入散列地址为8和5的空间中。

（4）计算关键59的散列地址为7，发生冲突（与关键字72冲突），其第一次线性探测地址（7+1）%13=8，但仍然发生冲突（与关键字8冲突），因此需要进行第二次线性探测，其地址为（7+2）%13=9，这时没有发生冲突，即将59存入地址为9的存储空间。

因此本题的答案选D。

4 单选题 1分

设一个包含N个顶点、E条边的简单无向图采用邻接矩阵存储结构（矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有／无边），则该矩阵中的非零元素数目为（　　）。

查看答案 开始考试

正确答案：C

本题解析：

本题主要考查图的邻接矩阵存储结构。

设G=（V，E）是具有n个顶点的图，其中V是顶点的集合，E是边的集合，那么邻接矩阵中的每个元素的定义如下：

从这个定义我们可以知道，一条边在矩阵中有个1表示，比如顶点1和顶点2之间有一条边，那么矩阵元素A[1，2]和A[2，1]的值都是1.

在本题中，题目告诉我们有E条边，那么其邻接矩阵中的非零元素数目应该为2E。

5 单选题 1分

在（　　）中，任意一个结点的左、右子树的高度之差的绝对值不超过1。

查看答案 开始考试

正确答案：A

本题解析：

本题主要考查一些特殊二叉树的性质。

若二叉树中最多只有最下面两层的结点度数可以小于2，并且最下面一层的叶子结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树，因此在完全二叉树中，任意一个结点的左、右子树的高度之差的绝对值不超过1。

二叉排序树的递归定义如下：二叉排序树或者是一棵空树；或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于根结点的值；

（3）左右子树也都是二叉排序树。

在n个结点的二叉树链式存储中存在n+1个空指针，造成了巨大的空间浪费，为了充分利用存储资源，可以将这些空链域存放指向结点在遍历过程中的直接前驱或直接后继的指针，这种空链域就称为线索，含有线索的二叉树就是线索二叉树。

最优二叉树即哈夫曼树。

6 单选题 1分

对n个元素的有序表A[1．．n]进行顺序查找，其成功查找的平均查找长度（即在查找表中找到指定关键码的元素时，所进行比较的表中元素个数的期望值）为（　　）。

查看答案 开始考试

正确答案：B

本题解析：

本题主要考查顺序查找。

对于n个数据元素的表，若给定值key与表中第i个元素的关键字相等，则需进行n-i+1次关键字比较，即Ci=n-i+1。例如，当第n个元素的关键字为key时，需要比较1次（n-n+1=1），又如，当第1个元素为所求时，需要比较n次（n-1+1=n）。因此，查找成功时，顺序查找的平均查找长度为：

；

其中Pi为每个元素的查找概率，假设所有元素的查找概率均相等，即，则在等概率情况下有：

7 单选题 1分

传值与传地址是函数调用时常采用的信息传递方式，（　　）。

查看答案 开始考试

正确答案：C

本题解析：

在函数调用时，系统为形参准备空间，并把实参的值赋值到形参空间中，在调用结束后，形参空间将被释放，而实参的值保持不变，这就是传值传递方式。传值传递方式中实参与形参之间的数据传递是单向的，只能由实参传递给形参，因而即使形参的值在函数执行过程中发生了变化，也不会影响到实参值。在C语言中，当参数类型是非指针类型和非数组类型时，均采用传值方式。

传地址方式把实参的地址赋值给形参，这样形参就可以根据地址值访问和更改实参的内容，从而实现双向传递。当参数类型是指针类型或数组类型时，均采用传地址方式。

区别于参数传值方式和返回值传递方式，传地址方式具有以下明显的优势。

（1）参数传值方式是主调函数与被调函数之间的单向数据传递方式，而参数的传地址方式则实现了二者之间的双向数据传递。

（2）函数的返回值每次只能把一个数据项从被调函数传递到主调函数，而参数的传地址方式却可一次性地传递多个数据项到主调函数。

8 单选题 1分

下图所示为一个有限自动机（其中，A是初态、C是终态），该自动机可识别（　　）。

查看答案 开始考试

正确答案：C

本题解析：

本题主要考查有限自动机。

在本题中，A是初始状态，C是终止状态，通过选项中的字符串可以从初始状态到达终止状态，则说明该字符串能被题目中的自动机识别。也可以理解为依次输入选项中的字符串，可以在该自动机中找到相应的路径。

对于选项A的字符串0000，在输入0后，从初始状态A转移到状态B，然后接着输入3个0，状态然后停留在B，而无法到达终态C，因此选项A不能被该自动机识别。

同样的道理，我们可以找到字符串0101能被该自动机识别，在输入0后，状态跳转到B，输入1则由B转至C，再输入0，又由C转至B，最后输入1，由B转至终态C。

9 单选题 1分

以下关于高级程序设计语言翻译的叙述中，正确的是（　　）。

查看答案 开始考试

正确答案：D

本题解析：

在对用高级程序设计语言编写的程序进行执行时，首先是将源代码翻译成目标代码，然后在连接成可执行的二进制代码。因此在翻译阶段，目标代码生成阶段的工作与目标机器的体系结构密切相关。

10 单选题 1分

在面向对象软件开发过程中，采用设计模式（　　）。

查看答案 开始考试

正确答案：A

本题解析：

模式是一种问题的解决思路，它已经适用于一个实践环境，并且可以适用于其它环境。设计模式通常是对于某一类软件设计问题的可重用的解决方案，将设计模式引入软件设计和开发过程，其目的就在于要重用成功的软件开发经验。