算法设计与分析章节练习(2020.02.08)

多项选择题
素数是只能被1和它本身整除的整数，那么下面不是素数的是（）。
A.13
B.15
C.27
D.34
填空题
阅读下列程序，写出运行结果程序运行后输出结果是（）
答案：30
填空题
已知包含25项的数列：1，2/3，3/5，…，24/47，25/49。问题1：写出该数列的通项公式f（n）=（）问题2：以下是计算s=1+2/3+3/5+……+24/47+25/49的程序，请补充完整。（）
答案：n/(2*n-1)；i/(2*i-1)
问答题
请解释什么是P问题，NP问题。
答案：如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。P是英文单词多项式的第一个字母。
单项选择题
定义二维数组intarr[3][3]则输出全部元素，共需要输出（）个。.
A.6
B.9
C.5
D.无法统计
问答题
试用分治法对一个有序表实现二分搜索算法。
答案：
单项选择题
数据结构与算法里，哈希表的处理冲突方式中的线性探测再散列方法，（）。
A.容易产生“聚集”
B.不容易产生“聚集”
C.不会产生“聚集”
D.一定会产生大量的“聚集”
问答题
在美国有一个连锁店叫7-11店，因为这个商店以前是早晨7点开门，晚上11点关门。有一天，一个顾客在这个店挑选了四样东西，然后到付款处去交钱。营业员拿起计算器，按了一些键，然后说：“总共是$7.11。”这个顾客开了个玩笑说：“哦？难道因为你们的店名叫7-11，所以我就要付$7.11吗？”营业员没有听出这是个玩笑，回答说：“当然不是，我已经把这四样东西的价格相乘才得出这个结果的！”顾客一听非常吃惊，“你怎么把他们相乘呢？你应该把他们相加才对！”营业员答道：“噢，对不起，我今天非常头疼，所以把键按错了。”然后，营业员将结果重算了一遍，将这四样东西的价格加在一起，然而，令他俩更为吃惊的是总和也是$7.11。设计蛮力算法找出这四样东西的价格各是多少？
答案：
问答题
使用prim算法构造出如下图的一棵最小生成树。
答案：