资源描述：
《计算机水平考试-软件设计师分类模拟题算法设计和分析(一)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、软件设计师分类模拟题算法设计和分析(-)一、综合知识试题1>给定一组长度为n的无序序列，将其存储在一维数组a[0..n-1]中。现采用如下方法找出其中的最大元素和最小元素：比较a[0]和a[n-l],若a[0]较大，则将二者的值进行交换；再比较a[1]和a[n-2],若a[丄]较大，则交换二者的值；然后依次比较a[2]和a[n-3].a[3]和a[n-4]...使得每一对元素屮的较小者被交换到低下标端。重复上述方法，在数组的前n/2个元素小查找最小元索，在后n/2个元索查找最人元索，从而得到整个序列的最小元索和最大元索。上述方法采用的算法设计策略是oA
2、.动态规划法B.贪心法C.分治法D.回溯法2、设某算法的计算时间表示为递推关系式T(n)=T(n-l)+n(n>0)及T(0)=1,则该算法的时间复杂度为OA.O(lgn)B.O(nlgn)C.O(n))D・O(r?)3、一个算法是对某类给定问题求解过程的精确描述，算法中描述的操作都可以通过将已经实现的基本操作执行冇限次来实现，这句话说明算法具冇特性。4.有穷性B.可行性C.确定性D.健壮性斐波那契(Fibonacci)数列可以递归地定义为：I廿=0I«=1F(f?-l)+F(n-2)w>t用递归算法求解F5时需要执行丄次''+〃运算，该方法采用的算法
3、策略是丄。4、A・5B.6C.7D・85、A・动态规划B.分治C.回溯D.分支限界6、若总是以待排序列的第一个元素作为基准元素进行快速排序，那么最好情况下的时间复杂度为仏1)"=
4、2心四十让％心1表示，若用◎表示该算法的渐进时间A・O(]og2：n)B.O(n)C・O(nlog2：n)D.O(n2)r(»o=7、某算法的时间复杂度可用递归式复朵度的紧致界，则正确的是oA.0(川齐)a€)(/)8、用动态规划策略求解矩阵连乘问题M/M2*M3*M4,其中M】(20*5)、M2(5*35)>M3(35*4)和M4(4*25),则最优的计算次序为。A.((M
5、/M2)*M3)*M4B.(M/M2)*(M3*M4)C.(M/(M2*M3))*M4D.Mx*(M2*(M3*M4)9、下面C程序段中count++语句执行的次数为ofor(inti=l；i<=ll；i*=2)for(intj=1；j<=i；j++)count++；A-15B-16C-31D-32丄0、不能保证求得0-1背包问题的最优解。A.分支限界法B.贪心算法C.冋溯法D.动态规划策略11＞若某算法在问题规模为n吋，其基木操作的重复次数可由下式表示，则该算法的吋间复杂度为”In>A.O(n)B・O(r?)C・Odoggii)D・0(nlog2：
6、n)12.若对一个链表最常用的操作是在末尾插入结点和删除尾结点，则采用仅设尾指针的单向循环链表(不含头结点)时，OA.插入和删除操作的时间复杂度都为0(丄)B.插入和删除操作的时间复杂度都为O(n)C.插入操作的吋间复杂度为0(1),删除操作的吋间复杂度为0(n)D.插入操作的吋间复杂度为0(H),删除操作的时间复杂度为0(1)13、某算法的时间复杂度表达式为T(n)=an2+bnlgn+cn+d,其中，n为问题的规模，a、b、c和d为常数，用0表示其渐近时间复杂度为oA・0(i?)B・0(n)C・0(nlgn)D・0(1)14、现有16枚外形相同的硬
7、币，其屮有一枚比真币的重量轻的假币，若采用分治法找出这枚假币，至少比较次才能够找出该假币。A.3B.4C・5D・615.以下的算法设计方法中，以获取问题最优解为目标。A.冋溯方法B.分治法C.动态规划D.递推16、归并排序采用的算法设计方法属于oA.归纳法B.分治法C.贪心法D.回溯方法二、案例分析试题17.阅读下列说明，回答问题。[说明]某餐厅供应各种标准的营养套餐。假设菜单上共有n项食物口，％,...,叫，每项食物m；的营养价值为S，价格为P,,其中i=2...,n,套餐中每项食物至多出现一次。客人常需要一个療法来求解总价格不超过M营养价值最大的套
8、餐。[问题1]下面是用动态规划策略求解该问题的伪代码，请填充其中的空缺(1)、(2)和(3)处。伪代码中的主要变量说明如下。m总食物项数。v：营养价值组，下标从1〜m对应第1到第n页食物的营养价值。P：价格数组，下标从1〜m对应第1到n项食物的价格。M：总标准即套餐的价格不超过M。x：解向量(数组)，下标从1〜n,其元素值为0或1,其屮元素值为0表示对应的食物不出现在套餐中，元索值为1表示对应的食物出现在套餐中。nv：n+l行M+1列的二维数组，其中行和列的下标均从0开始，nv[i][j]表示由前i项食物组合R价格不超过项j套餐的最大营养价值。问题最终
9、耍求的套餐的最大营养价值为nv[n][M]o伪代码如下：MaxNutrientValue(n,
