软件设计师真题2007年下半年上午题及答案十一

软件设计师考试大纲

软考软件设计师在线辅导班招生

软件设计师考试培训面授班全国招生

● 设栈S和队列Q的初始状态为空，元素按照a、b、c、d、e的次序进入栈S,当一个元素从栈中出来后立即进入队列Q.若队列的输出元素序列是c、d、b、a、e,则元素的出栈顺序是  （58）  ,栈S的容量至少为  （59）  .

（58）A. a、b、c、d、eB. e、d、c、b、a  C. c、d、b、a、e  D. e、a、b、d、c

（59）A. 2  B. 3 C. 4  D. 5

● 对于n（n≥0）个元素构成的线性序列L,在  （60）  时适合采用链式存储结构。

（60）A. 需要频繁修改L中元素的值B. 需要频繁地对L进行随机查找

C. 需要频繁地对L进行删除和插入操作D. 要求L存储密度高

● 对于二叉查找树（Binary Search Tree），若其左子树非空，则左子树上所有结点的值均小于根结点的值；若其右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树本身就是两棵二叉查找树。因此，对任意一棵二叉查找树进行  （61）  遍历可以得到一个结点元素的递增序列。在具有n个结点的二叉查找树上进行查找运算，最坏情况下的算法复杂度为  （62）  .

（61） A. 先序B. 中序C. 后序D. 层序

（62） A. O（n2）B. O（nlog2n）C. O（log2n）D. O（n）

● 迪杰斯特拉（Dijkstra）算法按照路径长度递增的方式求解单源点最短路径问题，该算法运用了 （63） 算法策略。

（63）A. 贪心 B. 分而治之C. 动态规划D. 试探+回溯

● 关于算法与数据结构的关系， （64） 是正确的。

　　参考答案：（58-63）C B C B D A

返回目录：软件设计师考试真题2007-2012年真题汇总

编辑推荐：软件设计师考试系统开发和运行知识习题汇总

软件设计师考试知识点总结