2019年上半年软件设计师上午下午试题及答案

D.分布性

57.某n阶的三对角矩阵A如下图所示,按行将元素存储在一维数组M中,设a1,1存储在M[l],那么ai,j (l<=i,j<=n且ai,j位于三条对角线中)存储在M( )。

A.i+2j B.2i+j C.i+2j-2 D.2i+j-2

58.具有3个结点的二叉树有5种,可推测出具有4个结点的二叉树有( )种。 A.10 B.11 C.14 D.15

59.双端队列是指在队列的两个端口都可以加入和删除元素,如下图所示。现在要求元素进队列和出队列必须在同一端口,即从A端进队的元素必须从A端出、从B端进队 的元素必须从B端出,则对于4个元素的序列a、b、c、d,若要求前2个元素(a、b)从 A端口按次序全部进入队列,后两个元素(c、d)从B端口按次序全部进入队列,则不可能得到的出队序列是( )。

A.d、a、b、c B.d、c、b、a C.b、a、d、c D.b、d、c、a

60.设散列函数为 H(key)=key%ll,对于关键碍序列(23,40, 91, 17, 19, 10, 31, 65, 26), 用线件探杳法解决冲突构造的哈希表为( B )。

61.对于有序表(8, 15, 19, 23, 26,31,40, 65,91),用二分法进行查找时,可能的关键 字比较顺序为( )。 A.26,23, 19 B.26,8, 19

C.26,40,65 D.26,31,40

62-65.已知矩阵Am*n和Bn*p相乘的时间复杂度为O(mnp)。矩阵相乘满足结合律,如三个矩阵A、B、C相乘的顺序可以是(A*B)*C也可以是A*(B*C)。不同的相乘顺序所需进行的乘法次数可能有很大的差别。因此确定n个矩阵相乘的最优计算顺序是一个非常重要的问题。已知确定n个矩阵A,A2......An相乘的计算顺序具有最优子结构,即A1A2......An的最优计算顺序包含其子问题A1A2......Ak和Ak+1Ak+2……An (l<=k

其中,Ai的维度为pi-1*pi m[i,j]表示AiAi+1……Aj最优计算顺序的相乘次数。

先采用自底向上的方法求n个矩阵相乘的最优计算顺序。则求解该问题的算法设计策

略为( )。算法的时间复杂度为( ),空间复杂度为( )。

给定一个实例,(POPi……P5)=(20,15,4,10,20,25),最优计算顺序为( )。 A.分治法 B.动态规划法 C.贪心法 D.回溯法 A.O(n2) B. O(n2lgn)

C.O(n3) D. O(2n) A.O(n2) B. O(n2lgn) C.O(n3) D. O(2n)

A.(((A1*A2)*A3)*A4)*A5 B. A1*(A2*(A3*(A4*A5))) C.((A1*A2)*A3)* (A4*A5) D. (A1*A2) *( (A3*A4)*A5)

66.浏览器开启了无痕浏览模式后,( )依然会被保存下来 A.浏览历史 B.搜索历史 C. 下载文件 D.临时文件

67.下面是HTTP的一次请求过程,正确的顺序是( )。 ①浏览器向DNS服务器发出域名解析请求并获得结果 ②在浏览器中输入URL,并按下回车键 ③服务器将网页数据发送给浏览器

④根据目的IP地址和端口号,与服务器建立TCP连接

联系客服:779662525#qq.com(#替换为@)