普及组解答

11.1.1　普及组解析

一、单项选择题

1．D　CPU的字长指微处理器能直接处理的二进制信息的位数，它标志着计算处理信息的精度，字长越长精度越高。

2．B　计算机的基本硬件结构一直沿袭冯·诺依曼于1946年设计的框架，由运算器、控制器、存储器、输入设备和输出设备五部分组成。

3．D　ALU是Arithmetic Logic Unit的缩写，是指CPU中的算术逻辑部件即运算器。

4．A　T＝tera－，读太，1TB＝2⁴⁰B＞1GB＝2³⁰B＞1KB＝2¹⁰B。

5．D　栈是一种十分重要的数据结构，栈的操作要求“后进先出”，在日常生活中有许多这类的例子，如洗碗时，先洗完的放在最底下，把洗好的碗逐个放在其它已经洗完的碗的上面，用的时候却是从上面逐个拿出。本题给出这个的条件，栈底为1，栈顶为n，且P1＝n，由此我们可以知道这样一个序列，P1＝n, P2＝n－1, p3＝n－2, p4＝n－3，分析一下这个序列就可以知道它们中间是有规律的就是n后面减的数比P后面的数小1，现在要求Pi的值，利用规律就可以得出Pi＝n－（i－1），就是n－i＋1。DOS操作系统是一种单用户单任务磁盘操作系统，不具备网络功能。

6．D　DOS操作系统是一种单用户单任务磁盘操作系统，不具备网络功能。

7．D　前三项都是预防病毒的措施，最后一项为杀毒操作。

8．D　本题的主要知识点是分清输入设备与输出设备。在上述4个答案中，A，B是比较明显的输入设备，现在应该也比较广泛。答案C数字化仪我们平时不是经常用到，所以容易在这儿产生错误，数化板是一种重要的图形输入装置，能方便地实现图形数据的输入。在服装设计中，往往采用大型数字化仪作为服装纸样的输入工具。答案D绘图仪的作用刚好与数字仪相反，它是把存在计算机中的图纸打印出来的设备，是属于输出设备。

9．A　一个汉字的机内码目前通常用2个字节表示：第一个字节是区位码的区号加（160）₁₀；第二个字节是区位码的位码加（160）₁₀。所以区号是十进制数30、位号是十进制数63的汉字在PC机中的十六进制内码是BEDF。

10．C　我的电脑和网上邻居都隶属于桌面，资源管理器是管理工具。

11．D　FTP是File Transfer Protocol的缩写，意指文件传送协议，这里指因特网上的文件传送服务。

12．B　目前为止只有CIH病毒能破坏计算机的硬件。

13．D　目前因特网上的服务器的IP地址是用四个0～255的十进制数表示的，每个数对应一个八位二进制数，合起来构成一个32位二进制数，形成该服务器在因特网上的唯一标识。

14．C　先进后出是堆栈的最主要特征。

15．C　由补码的定义可知二进制数（1110001010000000）₂与其十进制真值X的关系为2¹⁶＋X＝（1110001010000000）₂, X＝－（2¹⁶－（1110001010000000）₂）＝－（1110110000000）₂＝－7552。

16．A　这题的答案是比较明显的，电报、电话、传真都是比较传统的通信方式。E-mail中文意思就是电子邮件，是一种比较特殊的文件，这个文件的优点是可以夹带附件，附件可以是多种形式的文件，方便交流。

17．B　递归算法的执行过程分递推与回归两个阶段。在递推阶段，把较复杂的问题的求解推到比原问题简单一些的问题的求解，在递推阶段，必须要有终止递归的情况；在回归阶段，当获得最简单情况的解后，逐级返回，依次获得稍复杂问题的解。

18．C　二叉树中，使内部路径长度总和达到最小的树称为丰满树。从丰满树的形态上看，必然是：除最低层的叶子层外，每层的节点都是满的，且最低层的叶子尽可能都在最左，这样的树必然是使内部路径长度总和达到最小的树。

19．A　此题有许多关于Windows方面的知识点。一般情况下，从硬盘上删除文件或文件夹是会送到回收站的，但从软盘上删除则肯定不会进回收站。同一文件夹中，不能存在两个同类同名的文件，这是由文件的命名规则决定的。快捷方式只是一在个对文件所在目录的指向，删除它并不会对指向的源文件有任何影响。在Windows环境中，只要内存空间允许，可以打开任意多个应用程序。

20．D　堆排序是把待排序序列看作一棵完全二叉树，对于关键码序列K₁, K₂, …, K_n，若满足K_i≤K_2i且K_i≤K_2i＋1（或者满足K_i≥K_2i且K_i≥K_2i＋1），i＝1, 2, …, n div 2，就称该序列是一个堆，此时子树根节点的关键码值K_i比它的左右子节点的关键码值K_2i和K_2i＋1都小（大）。本题四个选项中只有D满足以上定义。

二、问题求解

1．首先考虑一个砝码的情况，假设砝码的质量为K克，用一个砝码称重可以有三种方案，第一种方案是将砝码放在天平的右侧，此时可称出的质量为K克；第二种方案是将砝码放在天平的左侧，此时可称出的质量也是K克，为区别于第一种方案，不妨把这一质量记为-K克；第三种方案是不将砝码放到天平上去，此时可称出的质量为0克。根据上述分析，考虑到n个砝码的质量依次为n位三进制数的各位的数位值（权重），而每一个砝码在称重时恰好只有三种状态，与三进制的三个数字0、1、2相对应，因此可采用一个n位三进制数表示n个砝码在天平上的分布情况，用一个一维数组STATE保存。STATE［K］＝0表示该砝码在天平的左侧，STATE［K］＝1表示该砝码不放到天平上去，用STATE［K］＝2表示砝码在天平的右侧，砝码K所称出的质量为（STATE［K］－1）*3^K，其中K＝0, 1, 2, 3, …。因此这个三进制数的实际值与它表示的天平状态所称出的质量相差3ⁿ－1，反过来将待称物品的质量M加上3ⁿ－1以后转化成三进制数，即将M转化成三进制数后按三进制运算规则每位加1即得到其称重方案。

本题中所要称量的物品的质量为518克，518所对应的三进制数为（201012）₃，（201012）₃＋（1111111）₃＝（2012200）₃，得到1克、3克、243克这三个砝码应放在天平左侧，而9克、27克、729克这三个砝码应放在天平右侧，81克的砝码不放到天平上去，所以正确的答案是518＋1＋3＋243＝9＋27＋729。

2．首先对三角形的种类进行分类：分别是有3个顶点在圆周上的，2个顶点在圆周上的，1个顶点在圆周上的，0个顶点在圆周上的，如图2所示：

图2

第一种：3个顶点在圆周上的，总数为。

第二种：4个顶点在圆周上的，就是任选4个点相连，形成4个满足本条件的三角形，所以总数为4×。

第三种：5个顶点在圆周上的，就是任选5个点相连，形成5个满足本条件的三角形，所以总数为5×。

第四种：6个顶点在圆周上的，就是任选6个点相连，形成1个满足本条件的三角形，所以总数为。

综上所述本题的答案为。

三、阅读程序

1．通过观察可以看出s的变化规律为1、7、19、37……，变量n每循环一次就减去当前的s值，第一次减去1，第二次减去7，前两次共减去8，第三次减去19，前三次共减去27，第四次减去37，前四次共减去64，……，而1、8、27、64恰好等于1、2、3、4的立方数，由此猜想本程序的运行结果为1000。下面给出严格证明：

由于（k＋1）³－k³＝3×（k²＋k）＋1＝3×k×（k＋1）＋1＝6×（1＋2＋3＋…＋k）＋1＝本程序循环k次后的s值，所以程序中变量s的值一直取相邻两数的立方差，变量n前k次循环共减去k³，当循环满1000次时程序结束，所以最后的运行结果为1000。

2．本程序是根据快速排序的思想寻找数组中第m大的元素，程序每次以a［m］为基准元素将数组a划分成不重叠的相邻的前后两个部分，前半部分下标从Left到j，后半部分下标从i到Right，且前半部分元素的值一定小于等于后半部分元素的值，然后根据m的值落在哪一部分就将寻找的范围缩小到该部分，继续上述操作直至寻找的范围元素个数不大于1为止，此时a［m］大于等于它前面的所有元素，小于等于它后面的所有元素，即a［m］为从小到大排列的第m个元素。所以本程序的运行结果为69。

3．本程序用递归过程p1将n转化为二进制数，然后用秦九韶算法计算m*n的值，最终以mod 1023的形式输出程序运行的结果。所以该程序运行结果为m*n％1023＝495。

4．本程序用来计算（n×（n－1）×（n－2）×……×（r＋1））／r！中有多少个因子5，程序段

对（n×（n－1）×（n－2）×……×（r＋1））／r！进行约分，其中gcd（）函数用来求二个自然数的最大公约数。程序段

统计（n×（n－1）×（n－2）×……×（r＋1））／r！中有多少个因子5，结果存放在变量g中。统计（n×（n－1）×（n－2）×……×（r＋1））／r！中有多少个因子5的方法可以这样计算：首先（n×（n－1）×（n－2）×……×（r＋1））/r！＝n！／r！／r！，由于5是质数，所以n！中包含的因子5的个数为n／5＋n／25＋n／125＋n／625＋……，本题中n＝1000，r＝202，由此得出n！／r！／r！中包含的因子5的个数为1000／5＋1000／25＋1000／125＋1000／625＋（202／5＋202／25＋202／125）×2＝200＋40＋8＋1－（40＋8＋1）×2＝151。

四、完善程序

1．略

2．从程序段

可以看出本程序是采用循环链的方法来实现数组元素的移动，即对任一元素a［i］都存在这样一个循环链a［i］→a［（i＋n）％m］→a［（i＋2*n）］％m］→a［（i＋3*n）］％m］→…→a［i］（％和Pascal中的mod等价）。由于数组的每个元素都只要移动一次，而一个循环链上往往有许多个元素，如果对每个循环链都用上述程序段对数组元素进行右n位操作，将造成对数组元素的重复移动，为了避免发生这种情况，必须在循环链上的元素都没有移动过的前提下才对该循环链上的元素进行移动操作，而判断一个循环链上的元素有没有移动过的方法是看该循环链上的第一个元素的下标是不是所有元素中最小的，若它不是最小的，说明该元素必是前面某个循环链上的元素，该循环链上的首元素下标更小，程序会先访问到该循环链。程序段

正是实现以A［k］开始的循环链上的元素是否都未移动过的判断的。看懂了本程序采用的算法以后，只要搞明白程序中的几个关键变量的作用就能填出全部的空格了，首先不难看出变量start表示当前循环链的首元素下标，所以程序中②应填k＝＝start（Pascal中是k＝start），表示当前循环链上没有一个元素的下标小于start；而rest在赋完初值m后一直没有再出现，而m是数组元素的总数，也是要移动的元素总数，开始时所有元素都还没有移动过，所以当前余下的未移动的元素个数为m，即rest的初值，每移动一个元素rest就应当减去1，当rest为0时所有元素移动完毕，程序结束，所以程序中③应填—rest（Pascal中为dec（start）），①应填rest＞0或rest!＝（Pascal中为rest＜＞0）；④是本程序的难点，感觉这儿无需填什么内容，假如用题目中给出的例子代入程序运行一遍你就会发现在当前循环链上做的最后一次移动是错误的，因为a［start］的值已经不是原来的值了，将它赋给a［（k＋n）％m］是不正确的，所以④应填a［（k＋n）％m］＝temp或a［（start＋n）％m］＝temp（％和pascal中的mod等价）来纠正这一错误，程序至此完成对当前循环链上全部元素的移动，接下去将寻找下一个未移动过的循环链，所以⑤应填＋＋start（inc（start））。

11.1.2　普及组参考答案

一、单项选择题

1．D　2．B　3．D　4．A　5．D　6．D　7．D　8．D　9．A　10．C　11．D12．B　13．D　14．C　15．C　16．A　17．B　18．C　19．A　20．D

二、问题求解

1．518＋1＋3＋243＝9＋27＋729。

2．

三、阅读程序

（1）1000。　（2）69。　（3）495。　（4）151。

四、完善程序

1．Pascal答案

（1）len2－j＋1

（2）len1－j＋1

（3）str1［i＋p］＝str2［k＋p］

（4）p＝j

（5）j

C＋＋答案

（1）len2－j＋1

（2）len1－j＋1

（3）str1［i＋p］＝＝str2［k＋p］

（4）p＝＝j

（5）j

2．Pascal答案

（1）rest＞0或rest＜＞0

（2）k＝start

（3）dec（rest）

（4）a［（k＋n）％ m］：＝temp　或　a［（start＋n）％ m］：＝temp

（5）inc（start）

C＋＋答案

（1）rest＞0　或　rest!＝0

（2）k＝＝start

（3）－－rest

（4）a［（k＋n）％ m］＝temp　或　a［（start＋n）％ m］＝temp

（5）＋＋start