2016年下半年软件设计师真题+答案解析(上午选择+下午案例完整版)全国计算机软考

若用顺序表存储，则最好情况是删除最后一个元素，此时不用移动任何元素，直接删除，最差的情况是删除第一个元素，此时需要移动n-1个元素，所以平均状态是移动(n-1)/2。

若用链表存储，直接将需要删除元素的前趋next指针指向后继元素即可，不需要移动元素，所以移动元素个数为0。 59、设有一个包含n个元素的有序线性表。在等概率情况下删除其中的一个元素，若采用顺序存储结构，则平均需要移动（58）个元素；若采用单链表存储，则平均需要移动（59）个元素。

A. 0

B. 1

C. (n-1)/2

D. n/2

答案： A

若用顺序表存储，则最好情况是删除最后一个元素，此时不用移动任何元素，直接删除，最差的情况是删除第一个元素，此时需要移动n-1个元素，所以平均状态是移动(n-1)/2。

若用链表存储，直接将需要删除元素的前趋next指针指向后继元素即可，不需要移动元素，所以移动元素个数为0。

60、具有3个节点的二叉树有（ ）种形态。

A. 2

B. 3

C. 5

D. 7

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

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

B. 含有n个结点的二叉排序树高度为（log2n）+1

C. 从根到任意一个叶子结点的路径上，结点的关键字呈现有序排列的特点

D. 从左到右排列同层次的结点，其关键字呈现有序排列的特点

答案： D

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

A. 10111011101

B. 10111001100

C. 001100100

D. 110011011

答案： A

63、 A. bad

B. bee

C. face

D. bace

答案： C

110001001101 中：f(1100) a(0) c(100) e(1101)。

64、两个矩阵Am*n和Bn*p相乘，用基本的方法进行，则需要的乘法次数为m*n*p。多个矩阵相乘满足结合律，不同的乘法顺序所需要的乘法次数不同。考虑采用动态规划方法确定Mi，M(i+1)，?，Mj多个矩阵连乘的最优顺序，即所

需要的乘法次数最少。最少乘法次数用m[i,j]表示，其递归式定义为：

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

A. O（n2）

B. O（n2lgn）

C. O（n3）

D. O（n3lgn）

答案： C

四个矩阵分别为： 2*6 6*3 3*10 10*3

先计算：M1*M2  及M3*M4，计算次数分别为： 2*6*3=36，3*10*3=90。

然后结果相乘，计算次数为： 2*3*3=18。

36+90+18=144。

65、 A. 156

B. 144

C. 180

D. 360

答案： B

四个矩阵分别为： 2*6 6*3 3*10 10*3

先计算：M1*M2  及M3*M4，计算次数分别为： 2*6*3=36，3*10*3=90。

然后结果相乘，计算次数为： 2*3*3=18。

36+90+18=144。

66、以下协议中属于应用层协议的是（66），该协议的报文封装在（67）。

A. SNMP

B. ARP

C. ICMP

D. X.25

答案： A

ARP和ICMP是网络层协议，X.25是数据链路层协议，只有SNMP是应用层协议。 SNMP协议的报文是封装在UDP协议中传送。

67、以下协议中属于应用层协议的是（66），该协议的报文封装在（67）。

A. TCP

B. IP

C. UDP

D. ICMP

答案： C

ARP和ICMP是网络层协议，X.25是数据链路层协议，只有SNMP是应用层协议。 SNMP协议的报文是封装在UDP协议中传送。

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

A. 主机名

B. 协议名

C. 目录名

D. 文件名