算法设计与分析真题精选.docx
- 文档编号:8824756
- 上传时间:2023-05-15
- 格式:DOCX
- 页数:22
- 大小:12.32KB
算法设计与分析真题精选.docx
《算法设计与分析真题精选.docx》由会员分享,可在线阅读,更多相关《算法设计与分析真题精选.docx(22页珍藏版)》请在冰点文库上搜索。
算法设计与分析真题精选
[单项选择题]
1、二分搜索算法是利用()实现的算法。
A.分治策略
B.动态规划法
C.贪心法
D.回溯法
参考答案:
A
[单项选择题]
2、最大效益优先是()的一搜索方式。
A.分支界限法
B.动态规划法
C.贪心法
D.回溯法
参考答案:
A
[判断题]
3、小明的烦恼问题要用二维字符串数组存储代表电话号码的字母。
参考答案:
对
[单项选择题]
4、回溯法解旅行售货员问题时的解空间树是()。
A.子集树
B.排列树
C.深度优先生成树
D.广度优先生成树
参考答案:
B
[单项选择题]
5、数据结构与算法中,折纸问题、修公路、剪绳子、蜗牛爬井问题是一类()算法解决的问题。
A.递归
B.穷举
C.迭代
D.分治
参考答案:
C
[单项选择题]
6、下列算法中通常以自底向上的方式求解最优解的是()。
A.备忘录法
B.动态规划法
C.贪心法
D.回溯法
参考答案:
B
[单项选择题]
7、鸡与兔共有35只,脚共94只,问鸡有()只
A.23
B.12
C.22
D.13
参考答案:
A
[单项选择题]
8、以下不可以使用分治法求解的是()。
A.棋盘覆盖问题
B.选择问题
C.归并排序
D.0/1背包问题
参考答案:
D
[单项选择题]
9、整数7和9的最小公倍数是()。
A.7
B.9
C.21
D.63
参考答案:
D
[单项选择题]
10、下列随机算法中运行时有时候成功有时候失败的是()
A.数值概率算法
B.舍伍德算法
C.拉斯维加斯算法
D.蒙特卡罗算法
参考答案:
C
[单项选择题]
11、数据结构与算法内,从时间复杂度的角度来看,快速排序的时间复杂度是()。
A.O(n*n)
B.O(nlog2n)
C.O
(1)
D.都不对
参考答案:
B
[单项选择题]
12、下面不是分支界限法搜索方式的是()。
A.广度优先
B.最小耗费优先
C.最大效益优先
D.深度优先
参考答案:
D
[单项选择题]
13、整数5和10的最大公约数是()。
A.10
B.5
C.30
D.50
参考答案:
B
[单项选择题]
14、备忘录方法是那种算法的变形。
()
A.分治法
B.动态规划法
C.贪心法
D.回溯法
参考答案:
B
[单项选择题]
15、素数是只能被1和它本身整除的是,以下是素数的是()。
A.12
B.7
C.27
D.99
参考答案:
B
[单项选择题]
16、分支限界法解最大团问题时,活结点表的组织形式是()。
A.最小堆
B.最大堆
C.栈
D.数组
参考答案:
B
[单项选择题]
17、荷兰国旗问题,需要使用一维数组存储0,1,2;那么一维数组的元素在内存中()。
A.占有一片连续的存储空间
B.是不连续的存储空间
C.可能是连续的也可能是不连续的
D.都不对
参考答案:
A
[单项选择题]
18、最长公共子序列算法利用的算法是()。
A.分支界限法
B.动态规划法
C.贪心法
D.回溯法
参考答案:
B
[单项选择题]
19、数据结构与算法内,就性能而言,希尔排序的时间复杂度是()。
A.O(n*n)
B.O(nlog2n)
C.O(n)
D.O(n3/2)
参考答案:
D[单项选择题]
20、下面是贪心算法的基本要素的是()
A.重叠子问题
B.构造最优解
C.贪心选择性质
D.定义最优解
参考答案:
C
[单项选择题]
21、数据结构与算法内,二叉排序树的第5层多有多少个结点()。
A.4
B.16
C.32
D.8
参考答案:
B更多内容请访问《睦霖题库》微信公众号
[单项选择题]
22、下面哪种函数是回溯法中为避免无效搜索采取的策略()
A.递归函数
B.剪枝函数
C.随机数函数
D.搜索函数
参考答案:
B
[单项选择题]
23、数据结构与算法内,折半查找的时间复杂度是()。
A.O
(1)
B.O(log2n)
C.O(n*n)
D.O(n)
参考答案:
B
[单项选择题]
24、蒙特卡罗算法是()的一种。
A.分支界限算法
B.概率算法
C.贪心算法
D.回溯算法
参考答案:
B[单项选择题]
25、以下英文字符串中是回文字符串的应该是()。
A.123321
B.11223311
C.123213
D.123123
参考答案:
A
[单项选择题]
26、数据结构中,查询(Searching)特定元素是否在表中,是()的概念。
A.查找
B.查看
C.分页
D.添加
参考答案:
A
[单项选择题]
27、下列哪一种算法不是随机化算法()
A.蒙特卡罗算法
B.拉斯维加斯算法
C.动态规划算法
D.舍伍德算法
参考答案:
C
[单项选择题]
28、若有说明:
inta[3]
[4];,则对a数组元素的非法引用是:
()
A.a[0]
[2*1]
B.a[1]
[3]
C.a[4-2]
[0]
D.a[0]
[4]
参考答案:
D
[单项选择题]
29、矩阵连乘问题的算法可由()设计实现。
A.分支界限算法
B.动态规划算法
C.贪心算法
D.回溯算法
参考答案:
B
[单项选择题]
30、数据结构中,下列选项中是折半查找的时间复杂度的是()。
A.O
(1)
B.O(log2n)
C.O(n*n)
D.O(n)
参考答案:
B
[单项选择题]
31、以下能正确定义数组并赋初值正确的语句是:
()。
A.intN=5,b[N]
[N];
B.inta[1]
[2]={{1},{3}};
C.intc[2]
[]={{1,2},{3,4}};
D.intd[3]
[2]={{1,2},{3,4}};
参考答案:
D
[单项选择题]
32、Strassen矩阵乘法是利用()实现的算法。
A.分治策略
B.动态规划法
C.贪心法
D.回溯法
参考答案:
A
[单项选择题]
33、数据结构中,关于查找表的逻辑结构,下列选项中说法正确的是()。
A.查找表是集合类型的逻辑结构
B.查找表是线性的逻辑结构
C.查找表是树形的逻辑结构
D.查找表是图形的逻辑结构
参考答案:
A
[单项选择题]
34、使用分治法求解不需要满足的条件是()。
A.子问题必须是一样的
B.子问题不能够重复
C.子问题的解可以合并
D.原问题和子问题使用相同的方法解
参考答案:
A
[单项选择题]
35、小明的烦恼算法的时间复杂度是()。
A.O
(1)
B.O(n)
C.O(nlog2n)
D.O(n*n)
参考答案:
D
[单项选择题]
36、下列算法中不能解决0/1背包问题的是()
A.贪心法
B.动态规划
C.回溯法
D.分支限界法
参考答案:
A
[单项选择题]
37、Hanoi塔问题如下图所示。
现要求将塔座A上的的所有圆盘移到塔座B上,并仍按同样顺序叠置。
移动圆盘时遵守Hanoi塔问题的移动规则。
由此设
计出解Hanoi塔问题的递归算法正确的为:
()
A.B.
C.
D.
参考答案:
B
[单项选择题]
38、数据结构与算法里,荷兰国旗算法的时间复杂度是()级别的。
A.线性
B.对数
C.指数
D.平方
参考答案:
A
[单项选择题]
39、实现合并排序利用的算法是()。
A.分治策略
B.动态规划法
C.贪心法
D.回溯法
参考答案:
A[填空题]
40已知非齐次递归方程:
,其中,
b、c是常数,g(n)是n
的某一个函数。
则f(n)的非递归表达式为:
现有Hanoi塔
问题的递归方程为:
,求h(n)的非递归表达式。
参考答案:
利用给出的关系式,此时有:
b=2,c=1,g(n)=1,从n递推到
1,有:
[单项选择题]
41、荷兰国旗问题,定义交换两个元素的函数,参数为指针,请问当参数为指针类型的函数,其传递属于()。
A.值传递
B.地址传递
C.形参传递
D.实参传递
参考答案:
B
[单项选择题]
42、下列不是动态规划算法基本要素的是()。
A.定义最优解
B.构造最优解
C.算出最优解
D.子问题重叠性质
参考答案:
D
[填空题]43请写出用回溯法解装载问题的函数。
装载问题:
有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船,其中集装箱i的重量为wi。
装载问题要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。
如果有,找出一种装载方案。
参考答案:
[判断题]
44、数据结构与算法里,可以使用两个下标定义的数组,称为二维数组。
参考答案:
对
[单项选择题]
45、采用广度优先策略搜索的算法是()。
A.分支界限法
B.动态规划法
C.贪心法
D.回溯法
参考答案:
A
[填空题]46编写计算斐波那契(Fibonacci)数列的第n项函数fib(n)。
参考答案:
[判断题]
47、可以通过赋初值的方式确定数组元素的个数。
参考答案:
对
[单项选择题]
48、在下列算法中得到的解未必正确的是()。
A.蒙特卡罗算法
B.拉斯维加斯算法
C.舍伍德算法
D.数值概率算法
参考答案:
B
[填空题]49设G=(V,E)是一个赋权有向图,其顶点集V被划分成k>2个不相交的子集Vi:
1≤i≤k,其中,V1和Vk分别只有一个顶点s(称为源)和一个顶点t(称为汇),图中所有的边(u,v),u∈Vi,v∈Vi+1。
求由s到t的最小成本路径。
a)给出使用动态规划算法求解多段图问题的基本思想。
b)使用上述方法求解如下多段图问题。
参考答案:
(1)基本思想:
设P(i,j)是从Vi中的节点j到汇点t的最小成本路径,Cost(i,j)是其成本。
则Cost(i,j)=min{c(j,h)+Cost(i+1,h)
H.Vi+1,(j,h)∈E}。
边界条件是若h=t,则Cost(h,t)=0;Cost(k-1,j)=c(j,t)。
(2)求解过程可以表示为:
其中每个节点标示的序偶(p,q)中,p表示节点到t的成本,q表示后继节点的编号。
从而,最优路径为:
1→2→7→10→12和1→3→6→10→12,成本为16。
[判断题]
50、定义二维数组intarr[4]
[2]如果全部元素输出,共需要输出6个元素
参考答案:
错
[单项选择题]
51、背包问题的贪心算法所需的计算时间为()
A.O(n2n)
B.O(nlogn)
C.O(2n)
D.O(n)
参考答案:
B
[判断题]
52、数据结构与算法里,字符串和字符数组是一回事。
参考答案:
错
[单项选择题]
53、0-1背包问题的回溯算法所需的计算时间为()
A.O(n2n)
B.O(nlogn)
C.O(2n)
D.O(n)
参考答案:
A
[填空题]54分别用贪心算法、动态规划法、回溯法设计0-1背包问题。
要求:
说明所使用的算法策略;写出算法实现的主要步骤;分析算法的时间。
参考答案:
(1)贪心算法O(nlog(n))首先计算每种物品单位重量的价值Vi/Wi,然后,依贪心选择策略,将尽可能多的单位重量价值最高的物品装入背包。
若将这种物品全部装入背包后,背包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包。
依此策略一直地进行下去,直到背包装满为止。
具体算法可描述如下:
(2)动态规划法O(nc)M(i,j)是背包容量为j,可选择物品为i,i+1,…,n时0-1背包问题的最优值。
由0-1背包问题的最优子结构性质,可以建立计算m(i,j)的递归式如下。
(3)回溯法O(2n)
[判断题]
55、可以用两个下标定义的数组,称为二维数组。
参考答案:
对[单项选择题]
56、贪心算法与动态规划算法的主要区别是()。
A.最优子结构
B.贪心选择性质
C.构造最优解
D.定义最优解
参考答案:
B
[填空题]57Dijkstra算法求单源最短路径。
参考答案:
[判断题]
58、在C语言中,strcat(字符数组,字符串)连接前两个字符串都有结束标志’/0’,连接后“字符数组”中存储的字符串的结束标志’/0’被舍弃,只在目标串的最后保留一个’/0’。
参考答案:
对
[单项选择题]
59、优先队列式分支限界法选取扩展结点的原则是()
A.先进先出
B.后进先出
C.结点的优先级
D.随机
参考答案:
C
[多项选择题]
60、数据结构与算法里,小明的烦恼问题的算法使用下列哪些技术项()。
A.二维数组
B.循环嵌套
C.分支判断
D.递归
参考答案:
A,B,C
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 设计 分析 精选