中级软件设计师简单单选试卷（中级软件设计师）_9.docVIP

试卷第 PAGE 6 页共 NUMPAGES 7 页 中级软件设计师简单单选试卷（中级软件设计师） 姓名:_____________ 年级:____________ 学号:______________ 题型 选择题 填空题 解答题 判断题 计算题 附加题 总分 得分 评卷人 得分 1、若二叉树的先序遍历序列为ABDECF，中序遍历序列为DBEAFC，则其后序遍历序列为（ ）。 A.DEBAFC B.DEFBCA C.DEBCFA DEBFCA2、对于哈希表，如果将装填因子定义为表中装入的记录数与表的长度之比，那么向表中加入新记录时，（ ）。 A.装填因子的值随冲突次数的增加而递减 B.装填因子越大发生冲突的可能性就越大 C.装填因子等于1时不会再发生冲突 装填因子低于0.5时不会发生冲突3、下面关于栈和队列的叙述，错误的是（ ）。 A.栈和队列都是操作受限的线性表 B.队列采用单循环链表存储时，只需设置队尾指针就可使入队和出队操作的时间复杂度都为O(1) C.若队列的数据规模n可以确定，则采用顺序存储结构比链式存储结构效率更高 利用两个栈可以模拟一个队列的操作，反之亦可4、已知某二叉树的中序序列为CBDAEFI，先序序列为ABCDEFI，则该二叉树的高度为（ ）。 A.2 B.3 C.4 55、己知一棵度为3的树(一个结点的度是指其子树的数目，树的度是指该树中所有结点的度的最大值)中有5个度为1的结点，4个度为2的结点，2个度为3的结点，那么，该树中的叶子结点数目为（ ）。 A.10 B.9 C.8 76、斐波那契(Fibonacci)数列可以递归地定义为：用递归算法求解F(5)时需要执行 (76) 次“+”运算，该方法采用的算法策略是 (77) 。（76）处填（ ） A.5 B.6 C.7 87、斐波那契(Fibonacci)数列可以递归地定义为：用递归算法求解F(5)时需要执行 (76) 次“+”运算，该方法采用的算法策略是 (77) 。（77）处填（ ） A.动态规划 B.分治 C.回溯 分支限界8、设某算法的计算时间可用递推关系式T（n）=2T（n/2）+n表示，则该算法的时间复杂度为（ ）。 A.O(lgn) B.O(nlgn) C.O(n) O(n2)9、简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图G有n个结点，其邻接矩阵为A[1..n，1..n]，且压缩存储在B[1..k]中，则k的值至少为 (20) 。若按行压缩存储对称矩阵的上三角元素，则当n等于10时，边(V6，V3)的信息存储在B[ (21) ]中。（20）处填（ ）。 A. A.A B.B C.C D10、 简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图G有n个结点，其邻接矩阵为A[1..n，1..n]，且压缩存储在B[1..k]中，则k的值至少为 (20)。若按行压缩存储对称矩阵的上三角元素，则当n等于10时，边(V6，V3)的信息存储在B[ (21)]中。（21）处填（ ）。 A.18 B.19 C.20 2111、（ ）在其最好情况下的算法时间复杂度为O(n)。 A.插入排序 B.归并排序 C.快速排序 堆排序12、（ ）的邻接矩阵是一个对称矩阵。 A.无向图 B.AOV网 C.AOE网 有向图13、 设一个包含Ⅳ个顶点、E条边的简单有向图采用邻接矩阵存储结构(矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有/无弧)，则该矩阵的元素数目为 (73)，其中非零元素数目为 (74)。（73）处填（ ）。 A.E2 B.N2 C.N2-E2 N2+E214、 设一个包含Ⅳ个顶点、E条边的简单有向图采用邻接矩阵存储结构(矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有/无弧)，则该矩阵的元素数目为 (73)，其中非零元素数目为 (74)。（74）处填（ ）。 A.N B.N+E C.E N-E15、某双向链表中的结点如图1-4所示，删除t所指结点的操作为（ ）。 A.t-＞prior-＞next=t-＞next；t-＞next-＞prior=t-＞prior； B.t-＞prior-＞prior=t-＞prio