2016年下半年软件设计师考试上午真题（上午题）(5)

醉狼峰

56.下列查询B=“大数据”且F=“开发平台”，结果集属性列为A．B．C．F的关系代数表达式中，查询效率最高的是（ ）。

A． π1,2,3,8 （σ2='大数据' ?1=5 ?3=6 ?8='开发平台'（R×S）） B．πl,2,3,8 （σ1=5?3=6?8='开发平台't（σ2='大数据'（R）×s）） C． π1，2，3，8（σ2='大数据'?1=5?3=6（R×σ4='开发平台'（S）） D．π1,2,3,8（σ1=5^3=6（σ2='大数据'（R）×a4='开发平台'（S）））

57.拓扑序列是有向无环图中所有顶点的一个线性序列，若有向图中存在弧或存在从顶点v到w的路径，则在该有向图的任一拓扑序列中，V一定在w之前。下面有向图的拓扑序列是（ ）

A．41235 B．43125 C．42135 D．41=325

设有一个包含n个元素的有序线性表。在等概率情况下删除其中的一个元素，若采用顺序存储结构，则平均需要移动（ 58 ）个元素；若采用单链表存储，则平均需要移动（ 59 ）个元素。

58： A．1

醉狼峰 B． （n-l）/2 C．logn D． N 59： A．O B． 1 B． （n-l）/ D． n/2

60.具有3个 节点的二叉树有（ ）种形态。 A．2 B．3 C．5 D．7

61.以下关于二叉排序树（或二叉查找树、二叉搜索树）的叙述中，正确的是（ ）

A．对二叉排序树进行先序、中序和后序遍历，都得到结点关键字的有序序列

B．含有N个结点的二叉排序树高度为【log2n】+1

C．从根到任意二个叶子结点的路径上，结点的关键字呈现有序排列的特点 D．从左到右排列同层次的结点，’其关键字呈现有序排列的特点

醉狼峰

下表为某文件中字符的出现频率，采用霍夫曼编码对下列字符编码，则字符序列“bee”的编码为（ 62 ）；编码：:“110001001101”的对应的字符序列（ 63 ）

62：

A．10111011101 B．10111001100 C．001100100 D．110011011 63： A．bad B．bee C．face D．Bace

两个矩阵Am*n和Bn*p相乘，用基本的方法进行，则需要的乘法次数为m*n*p 多个矩阵相乘满足结合律，不同的乘法顺序所需要的乘法次数不同。考虑采用动态规划方法确定Mi,M{i+i），…，Mj多个矩阵连乘的最优顺序，即所需要的乘法次数最少。最少乘法次数用m[i，j]表示，其递归式定义为：

醉狼峰

其中i、j和k为矩阵下标，矩阵序列中Mi的维度为（Pi-i.）*Pi采用自底向上的方法:实现该算法来确定n个矩阵相乘的顺序，其时间复杂度为（ 64 ）。若四个矩阵M1. M2、M3.，M4相乘的维度序列为2、6、3、10.3，采用上述算法求解，则乘法次数为（ 65 ）。

64： A．O（N2） B．O（N2Lgn） C．O（N3） D．O（n3lgn） 65： A．156 B．144 C．180 D． 360

以下协议中属于应用层协议的是（66 ），该协议的报文封装在（66： A．SNMP B．ARP C．ICMP D．X．25 67：

67 ）。 醉狼峰

A．TCP B．IP C．UDP D．ICMP

68.某公司内部使用wB．xyz．com.cn作为访问某服务器的地址，其中WB是（ ）。

A．主机名 B．协议名 C．目录名 D．文件名

69.如果路由器收到了多个路由协议转发的关于某个目标的多条路由，那么决定采用哪条路由的策略是（ ）。

A．选择与自己路由协议相同的 B．选择路由费用最小的 C．比较各个路由的管理距离 D．比较各个路由协议的版本

70.与地址220.112.179.92匹配的路由表的表项是（ ）。 A． 220.112.145.32/22 B． 220.112.145.64/22