2008.7算法设计与分析课程期末试卷.doc

《2008.7算法设计与分析课程期末试卷.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、华南农业大学期末考试试卷（A卷）2007学年第二学期　考试科目：　算法分析与设计　考试类型：（闭卷）　　　考试时间：　120　分钟学号姓名年级专业题号一二三总分得分评阅人一、选择题（30分，每题2分）1、下面的算法段针对不同的自然数n作不同的处理，其中函数odd(n)当n是奇数时返回true，否则返回false，while(n>1)if(odd(n))n=3*n+1;elsen=n/2;请问该算法所需计算时间的下界是D。A．Ω（2n）B．Ω（nlogn）C．Ω（n！）D．Ω（logn）2、某体育馆有一羽毛球场出租，现在总共有10位客户申请租

2、用此羽毛球场，每个客户所租用的时间单元如下表所示，s（i）表示开始租用时刻，f（i）表示结束租用时刻，i12345678910s（i）0315352886f（i）65498713121110同一时刻，该羽毛球场只能租借给一位客户，请问在这10位客户里面，体育馆最多能满足B位客户的需求。P104A．3B．4C．5D．63、当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以使用B来消除或减少问题的好坏实例间的这种差别。A．数值概率算法B．舍伍德算法C．拉斯维加斯算法D．蒙特卡罗算法4、将一个正整数n表示成一系

3、列正整数之和，n=n1+n2+…+nk（其中，n1≥n2≥…≥nk≥1，k≥1）正整数n的一个这种表示称为正整数n的一个划分。正整数n的不同的划分个数总和称为正整数n的划分数，记作p（n）；另外，在正整数n的所有不同划分中，将最大加数n1不大于m的划分个数记作q（n，m）。则当n=10时，p（n）=C。A．q（8，8）B．1+q（9，9）P12C．2+q（10，8）D．A，B，C都正确5、对于含有n个元素的子集树问题，最坏情况下其解空间的叶结点数目为B。A．n!B．2nC．2n+1-1D．P1406、在棋盘覆盖问题中，对于2k×2k的特殊棋

4、盘（有一个特殊方块），所需的L型骨牌的个数是A。A．（4k–1）/3B．2k/3C．4kD．2k7、T（n）表示当输入规模为n时的算法效率，以下算法效率最优的是C。A．T（n）=T（n–1）+1，T（1）＝1B．T（n）=2n2C．T（n）=T（n/2）+1，T（1）=1D．T（n）=3nlog2n8、给出一个由n个数组成的序列A[1…n]，要求找出它的最长单调上升子序列，设m[i]（1≤i≤n），表示以A[i]结尾的最长单调上升子序列的长度，则m[1]=1，m[i]（1

5、i]，1≤k1）C．m[i]=1+max{0，m[k]（A[k]≤A[i]，1≤k

6、所要求的整个序列的最长公共子序列长度为max{f(i):1<=i<=n}例如，对于序列：4263152i1234567array4263152f(i)11221329、有9个村庄，其坐标位置如下表所示：i123456789x（i）123456789y（i）123456789现在要盖一所邮局为这9个村庄服务，请问邮局应该盖在C才能使到邮局到这9个村庄的总距离和最短。A．（4.5，0）B．（4.5，4.5）C．（5，5）D．（5，0）10、关于回溯算法和分支限界法，以下A是不正确描述。A．回溯法中【应为分支限界法】，每个活结点只有一次机会成为扩

7、展结点B．分支限界法中，活结点一旦成为扩展结点，就一次性产生其所有儿子结点，在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子加入活结点表中C．回溯法采用深度优先的结点生成策略D．分支限界法采用广度优先或最小耗费优先（最大效益优先）的结点生成策略11、一个算法应该包含如下几条性质，除了A。A．二义性B．有限性C．正确性D．可终止性12、在寻找n个元素中第k小元素问题中，如使用快速排序算法思想，运用分治算法对n个元素进行划分，应如何选择划分基准？下面D答案解释最合理。A．随机选择一个元素作为划分基准B．取子序列的第一个

8、元素作为划分基准C．用中位数的中位数方法寻找划分基准D．以上皆可行。但不同方法，算法复杂度上界可能不同13、n个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，请问他们怎样排队