计算机水平考试-软件设计师分类模拟题常用算法设计方法

《计算机水平考试-软件设计师分类模拟题常用算法设计方法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、软件设计师分类模拟题常用算法设计方法K设某算法的计算吋间可用递推关系式T(n)=2T(n/2)+n表示，则该算法的时间复杂度为(1)。A.O(lgn)B・O(n].gn)C.O(n)D.O(n2)2、下而的程序段违反了算法的(2)原则。Voidsam(){intn=2；while(!odd(n))n+=2printf(n)；}A.有穷性B.确定性C.可行性D.健壮性3、拉斯维加斯(LasVegas)算法是一种常用的_Q)_算法。A.确定性B.近似C.概率D.加密4、在分支-限界算法设计策略中，通常采用(4)_搜索问题的解空间。A.深度优先B.广度优先C.自

2、底向上D.拓扑序列5、算法是对问题求解过程的一类精确描述，算法中描述的操作都是可以通过已经实现的基本操作在限定吋间内执行有限次来实现的，这句话说明算法具有(5)特性。A.正确性B.确定性C.可行性D.健壮性6、用迭代法求解方程x5-x-l=0,下列迭代公式不可能IE确的是_(6)。A・Xtfi=x*—1B.Xjt+i=xf1C・xjt+i=y/l+xjt以+i以下不屈于算法的基本特征的是一7。穷举法的适用范围是_8。7、A.有确切定义的B.可行的C.可描述的D.不能有二义性8、A.—切问题B.解的个数极多的问题C.解的个数不太多的问题D.不适合设计算法设求

3、解某问题的递归算法如F：F(intn){ifn=l{Move11}else{F(n-l);Move(n)；F(n-l)；}}求解该算法的计算时间时，仅考虑算法Move所做的计算为主要计算，且Move为常数级算法。则算法F的计算时间T(n)的递推关系式为_9_；设算法Move的计算时间为k,当”4时，算法F的计算时间为10。9、A.T(n)=T(n-1)+1B・T(n)=2T(n-1)C.T(n)=2T(n-1)+1D・T(n)=2T(n+l)+110、A.14kB.15kC・16kD.17kIK用递归算法实现n个相异元素构成的有序序列的二分查找，采用一个递

4、归工作栈时，该栈的最小容量应为(11)。A.nB・[n/2]C・[log2n]D.[log.(n+1)]递归算法的执行过程，一般来说，可先后分成12和13两个阶段。12、A.试探B.递推C.枚举D.分析13、A.回溯B.冋归C.返冋D.合成若一个问题的求解既口J以用递归算法，也口J以用递推算法，则往往用14算法,因为15。14、A.先递归后递推B.先递推后递归C.递归D.递推15、4.递推的效率比递归高B.递归宜于问题分解C.递归的效率比递推高D.递推宜于问题分解在下列算法设让方法中，16在求解问题的过程中并不从整休最优上加以考虑,而是作岀在当前看来是最好

5、的选择。利用该设计方法可以解决17问题。丄6、A.分治法B.贪心法C.动态规划法D.回溯法17、4.排序B.检索C.背包D.0/1背包在数据压缩编码的应用中，哈夫曼(Huffman)算法可以用来构造具有18的二叉树,这是一种采用了19的算法。18、A.前缀码B.最优丽缀码C.后缀码D.最优后缀码丄9、A.贪心B.分治C.递推D.回溯20、贪婪法是一种(20)的算法。A.不求最优，只求满意B.只求最优C.求取全部可行解D.求取全部最优解以关键字比较为基础的排序算法在最坏情况卜•的计算时间卜•界为0(nlogn)o卜•面的排序算法屮，最坏情况下计算时间可以达到

6、O(nlogn)的是一21,该算法采用的设计方法是一22。21、A.归并排序B.插入排序C.选择排序D.冒泡排序22、A.分治法B.贪心法C.动态规划方法D.冋溯法23、快速排序算法采用的设计方法是一(23)。A.动态规划法(DynamicProgramming)B.分治法(Divid巳andConquer)C.回丫朔法(Backtracking)D・分枝定界法(BranchandBound)对于求取两个长度为n的字符串的最长公共子序列(LCS)问题，利用24策略可以有效地避免子串最长公共子序列的重复计算，得到吋间复杂度为0(&)的正确算法。串＜1,0,0

7、,1,O,1,0,1＞和＜0,1,0,1,lz0zl,1＞的最长公共子序列的长度为25。24、A.分治B.贪心C.动态规划D.分支一限界25、A.3B・4C.5D・6利用贪心法求解0/1背包问题时，26能够确保获得最优解。用动态规划方求解0/1背包问题时，将''用前i个物品来装容量是x的背包〃的0/1背包问题记为KNAP(1,i,X)设G(X)是KNAP(1,i,X)最优解的效益值，第j个物品的重量和放入背包后取得效益值分别为W和p(j=l〜n),则依次求解f0(X),fT(X),fn(X)的过程中使用的递推关系式为27。26、A.优先选取重量最小的物品B

8、.优先选取效益最大的物品C.优先选取单位重量效益最大的物品D.没冇