阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的-考网

阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】假币问题：有n枚硬币，其中有一枚是假币，已知假币的重量较轻。现只有一个天平，要求用尽量少的比较次数找出这枚假币。【分析问题】将n枚硬币分成相等的两部分：（1）当n为偶数时，将前后两部分，即1…n/2和n/2+1…0，放在天平的两端，较轻的一端里有假币，继续在较轻的这部分硬币中用同样的方法找出假币：（2）当n为奇数时，将前后两部分，即1…(n -1)/2和(n+1)/2+1…0，放在天平的两端，较轻的一端里有假币，继续在较轻的这部分硬币中用同样的方法找出假币；若两端重量相等，则中间的硬币，即第 (n+1)/2枚硬币是假币。【C代码】下面是算法的C语言实现，其中：

coins[]：硬币数组first，last：当前考虑的硬币数组中的第一个和最后一个下标

#include ＜stdio.h>

int getCounterfeitCoin(int coins[]， int first，int last){int firstSum = 0，lastSum = 0;int ì;If(first==last-1){ /*只剩两枚硬币*/if(coins[first] ＜ coins[last])return first;return last;}

if((last - first + 1) % 2 ==0){ /*偶数枚硬币*/for(i = first;i ＜( 1 );i++){firstSum+= coins[i];}for(i=first + (last-first) / 2 + 1;i ＜ last +1;i++){lastSum += coins[i];}if( 2 ){Return getCounterfeitCoin(coins,first,first+(last-first)/2;)}else{Return getCounterfeitCoin(coins,first+(last-first)/2+1,last;)}}else{ /*奇数枚硬币*/For(i=first;i＜first+(last-first)/2;i++){firstSum+=coins[i];}For(i=first+(last-first)/2+1;i＜last+1;i++){lastSum+=coins[i];}If(firstSum＜lastSum){return getCounterfeitCoin(coins,first,first+(last-first)/2-1);}else if(firstSum>lastSum){return getCounterfeitCoin(coins,first+(last-first)/2-1,last);}else{Return( 3 )}}}

【问题一】（6分）根据题干说明，填充C代码中的空（1）-（3）【问题二】（4分）根据题干说明和C代码，算法采用了（）设计策略。函数getCounterfeitCoin的时间复杂度为（）（用O表示）。【问题三】（5分）若输入的硬币数为30，则最少的比较次数为（），最多的比较次数为（）。

查看答案纠错

答案：

本题解析：

【问题一】答案：（1）first+(last-first)/2 +1或(first+last)/2+1 （2）firstSum＜lastSum（3）first+(last-first)/2 或(first+last)/2【问题二】答案：分治法、O（nlogn）【问题三】答案：2、4

包含此试题的试卷

2021年程序员模拟题4

你可能感兴趣的试题

问答题

【说明】利用ASP+access开发网站管理系统，设计以下两个网页Add_form.asp 和Add.asp，通过它们将网站信息添加到数据库test.mdb 中website表中。下图是Add_form.asp 浏览页面，在其上输入需要添加页面内容后，单击"确定"按钮，执行Add.asp 页面完成相应内容添加到数据库test.mdb 中。

中级网络工程师,章节练习,基础复习,中级网络工程师计算机

问题1：完成程序中空白处填空。

＜% Option Eplicit%>＜Html>＜head>＜title>添加记录示例＜/title>＜/head>(1)align="center">添加新网站＜/h2>＜center>＜table border="1" width="90%">＜form name ="form1"method="（2）"action=（3）">＜tr>＜td>网站名称＜/td>＜td>＜input type="（4）"name="name" size=20>＜/td>＜/tr>＜tr>＜td>网站地址＜/td>＜td>＜input type="text"name="URL" size=40>＜/td>＜/tr>＜tr>＜td>网站简介＜/td>＜td>（5） name ="into" row="2"cols="40"wrap="solf ">＜/textarea>＜/td>＜/tr>＜tr>＜td> ＜/td>＜td>＜input type=(6)" "value="确定">＜input type=(7)" "value="（8）"＜/td>＜/tr>＜/from>＜/table>＜/center>＜/body>＜/html>

添加数据记录执行程序add.asp:

＜% Otion Eplicit>＜% '如果上面信息已经填全了，就添加记录，否则给出错误提示信息Dim connSet conn=server.（9）("ADODB.Connection")conn.Open "Dbq="&Server,mappath("（10）")&";Driver={Microsoft Access Driver(*.mdb)};"Dim strSql,varName,varURL,varlntro,rs '定义变量VarName=Request.Form("（11）")VarURL=Request.Form(" URL")VarIntro =Request.Form("Intro")（12）="Insert into website (name,URL.intro,submit_date)Values( "&varName &","&_varURL&","& varIntro &",# "&Date（）&" # )" 'Date（）表示取服务器时间Set rs=conn.(13) (strSql)index.asp" '添加成功，则返回首页index.asp…response.（14） "请将所有信息填写完整"response. (15)"add_form.asp"%>

备选答案

(1).A.b3 B. h2 C.h3 D.空白

（2）A. get B. post C.put D.pull

(3）A.add.asp B.add C.add_form.asp D.continue

(4)A.submit B.option C.radio D.text

(5)A. textarea B.text C.select D.option

(6)A.submit B.reset C.radio D.text

(7)A.submit B.reset C.radio D.text

(8)A.submit B.确定 C.reset D.重写

(9)A.mappath B.cereateobject C.application D.server

(10)A.test B.test.mdb C.website D.website.table

(11)A.name B.text C.requesto D.response