计算机水平考试-初级程序员下午试题模拟46

《计算机水平考试-初级程序员下午试题模拟46》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、初级程序员下午试题模拟46试题一阅读以下算法说明和问题模型图，根据要求回答下列问题。[说明]某大学城图书馆需要在无线阅览厅的某些位置上放置无线接入点AP(AccessPoin)o假设每个无线AP覆盖范围的半径是6米，因此必须使得每台笔记本计算机上的无线网卡到某个无线AP的直线距离不超过6米。为了简化问题，假设所冇无线网卡都在同一直线卜，并但无线AP沿该直线放置。该问题可以建模为如图87所示，其中直线表示无线网卡所在的直线，实心正方形表示无线网卡。现采用贪心策略来实现用尽可能少的无线AP覆盖所有的

2、无线网卡。无磯甩卡分布模鬼图基于贪心算法实现以上应用需求的基本思想是：问题的规模为N,从第丄个无线网卡(最左端)开始布局无线AP,把第1个无线AP放置在该无线网卡右方的6米处，此时该无线AP会覆盖从第丄个无线网卡到该无线网卡右方直线长度为12米的所有无线网卡，假设覆盖了N1个无线网卡。此时间题规模变成了N-N1,接着把第1个无线AP覆盖的无线网卡去掉，再从N-N1中选择第1个(最左端)无线网卡开始布局无线AP,将第2个无线AP放置在该无线网卡右方的6米处。依此布局，•育到覆盖所有的无线网卡为止。

3、图8-2是问题解的模型，其中，直线表示无线网卡所在的直线，实心正方形表示无线网卡,实心圆形表示无线AP,虚线圆对应无线AP为圆心，虚线圆的直径为相应无线AP的覆盖范围(12米)。实现以上贪心算法的流程如图8・3所示。其中，①d[i](lWiWN)表示第i张无线网卡到通道A端的距离，N表示无线网卡的总数，无线网卡的编号按照无线网卡到通道A端的距离从小到大进行编号；②s[k]表示第k(k^l)个无线AP到通道A端的距离。算法结束后，k的值为无线AP的总数。1、请填补图8-3流程图中空缺处的内容。2、

4、该贪心算法的时间复杂度为o试题二阅读以下说明和C函数，根据要求回答下列问题。3、［说明1］卜•面［C程序代码丄］的设计意图是：计算1〜丄00各数的平方。运行该段代码后，没有得到应有的运算结果。［C程序代码1］行号1fdefineSQUARE(a)2inti=L;3intresult*0;-45resulc=SQUARE(i++);6a=i;7printftUx,esult=%d，，＞^result);8)while;以上［C程序代码1］中共有3处错误。请在表8-1中指出这些错误所在代码的行号

5、，并在不增加和删除代码行的情况下进行修改，写出修改正确后的完整代码行，使之符合上述设计意图。虽敎铅误修改裘[岀借杼号怅改正确盾的完整代码行1[说明2]有两个进程(编号分别为0和丄)需要访问同一个共享资源。为了解决竞争条件(racecondition)的问题，需耍实现一•种互斥机制，使得在任何时刻只能有一个进程访问该共享资源。以下[C程序代码2]给出了一种实现方法。[C程序代码2]intflag[2]；/*flaq数组，初始化为FALSE*/EnterCriticalSection(intmyta

6、skid,intothertaskid){while(flag[other_task_id]==TRUE.；/*空循环l吾令J*/flag[mytaskid]=TRUE；}■■Exit_Critical_Section(intmy_task_id,intother_task_id){flag[my_taskid]=FALSE；当一个进程要访问临界资源时，就可以调用[C程序代码2]给出的这两个函数。[C程序代码3]给出了进程0的一个例子。[C程序代码3]Enter_Critical_Section

7、(0,1);…使用应个资源•••■Exit_Critical_Section(0,1);・・•做箕彳也的事情・・・~4、[C程序代码2]所示的方法实现共享资源的互斥访问。A.能够B.不能5、[C程序代码2]采用了一种繁忙等待(busywaiting)的策略，这种策略的主要缺点是什么？请用丄00字以内的文字简要说明。6、如果将Enterl_Critical_Section()函数屮的两条语句互换一下位置，则可能会出现什么情况？请用100字以丙的文字简要说明。试题三阅读以下应用程序说明和C程序，将C

8、程序段中空缺处的语句填写完整。7、[说明]某超市集团为发展业务向社会公开招聘N个工种的工作人员，每个工种各有不同的编号(1〜M)和计划招聘人数。每位应聘者需申报两个工种，并参加集团组织的考试。该集团公司将按应聘者的成绩从高分至低分的顺序进行排队录取。貝体录取原则是：从高分到低分依次对每位应聘者先按其第一志愿录取；当不能按其第一志愿录取时，便将他的成绩扣去5分后，重新排队，并按其第二志愿考虑录取。以下C程序为输出各工种实际招聘的应聘人员，每个工种都保留一个录取者的有序队列。录取处理循环直至招聘额满