第1题
若有两位候选人参选,并争夺n·51个选举人团(50个州和1个特区)的共计2m=538张选举人票,是否可能因两人恰好各得m=269张,而不得不重新选举?
a)试设计并实现一个对应的算法,并分析其时间复杂度;
b)若没有其它(诸如限定整数取值范围等)附加条件,该问题可否在多项式时间内求解?
第4题
问题描述;设S是正整数集合.S是一个无和集,当且仅当蕴含.对于任意正整数k,如果可将{1.2,...,k}划分为n个无和子集,则称正整数k是n可分的.记F(n)=max{k|k是n可分的}.试设计一个算法,对任意给定的n,计算F(n)的值.
算法设计:对任意给定的n,计算F(n)的值.
数据输入:由文件input.txt给出输入数据.第I行有1个正整数n.
结果输出:将计算的F(n)的值以及{1,2,F(n)}的一个n划分输出到文件output.txt.文件的第1行是F(n)的值.接下来的n行,每行是一个无和子集Si.
第5题
A.可以由多项式时间算法求解的问题是难处理的
B.需要超过多项式时间算法求解的问题是易处理的
C.可以由多项式时间算法求解的问题是易处理的
D.需要超过多项式时间算法求解的问题是不能处理的
第9题
算法设计:设计一个算法,找出给定序列x和y的包含s为其子串的最长公共子序列.
数据输入:由文件input.txt提供输入数据.文件的第1行中给出正整数,分别表示给定序列x、y和约束字符串s的长度.接下来的3行分别给出序列x、y和约束字符串s.
结果输出:将计算出的x和y的包含s为其子串的最长公共子序列的长度输出到文件output.txt中.
第10题
A.分治法的基本思想是把一个规模为n的问题划分为若干个规模较小、且与原问题相似的子问题,因此和通归问题相同
B.递归法是利用函数直接或间接地调自身来完成某个计算过程
C.迭代法是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题
D.回溯法先选择某一种可能情况向前探索,当发现所选用的试探性操作不是最佳选择,需回一步(回溯),重新选择继续进行试探,直到找到问题的解或证明问题无解
第11题
计算一元n次多项式的值:输出多项式P(x,n)的值。设计算法求解,请选择合适的输入、输出格式,要求算法具有较好的时间性能。