2006年解析.doc

2006年解析普及组一、1、选DA. 1976年1月1日，R.沃尔夫（Ricardo Wolf）及其家族损献一千万美元成立了沃尔夫基金会，其宗旨主要是为了促进全世界科学、艺术的发展。B. 诺贝尔奖是以瑞典著名化学家、硝化甘油炸药发明人阿尔弗雷德贝恩哈德诺贝尔的部分遗产作为基金创立的。诺贝尔奖包括金质奖章、证书和奖金支票。在遗嘱中他提出，将部分遗产（920万美元）作为基金，以其利息分设物理、化学、生理或医学、文学及和平（后添加了经济奖）种奖金，授予世界各国在这些领域对人类作出重大贡献的学者。C. 菲尔兹奖（Fields Medal，全名The International Medals for Outstanding Discoveries in Mathematics）是一个在国际数学联盟的国际数学家大会上颁发的奖项。每四年颁奖一次，颁给有卓越贡献的年轻数学家，每次最多四人得奖。得奖者须在该年元旦前未满四十岁。它是据加拿大数学家约翰查尔斯菲尔兹的要求设立的。菲尔兹奖被视为数学界的诺贝尔奖。2、选BAgcc 和 g+分别是GNU的c 和 c+编译器Gnu 是一个组织：1983年，由理查德马修斯托曼（Richard Stallman）创立，目标：为了发展一个完全免费自由的Unix-like操作系统（也就是现在的linux系统）。GUN C应该是在linux 系统下的CCRHIDE(Robert H.hne s IDE)就是Linux Console下的C/C+集成开发环境，界面与Turbo C+ 3.0几乎一模一样。rhide集成了gcc编译器以及gdb调试工具DFree Pascal是个由国际组织开发的完全的win32的pascal语言编译器，类似delphi，可编写windows程序。此前被广泛使用的PASCAL编译器普遍为Turbo Pascal & Borland pascal。但是它们可用的空间十分有限。而Free Pascal理论上可以使用4GB内存。所以在利用Free Pascal编程的时候，可以改变原有思路，将大量时间转嫁给空间，提高效率。虽然Free Pascal尽量设计得和Turbo Pascal接近，但是由于以下的两个原因，两者之间还是有一些区别的：1）Free Pascal是一个32位的编译器，而Turbo Pascal只是16 Free Pascal位编译器； 2）Free Pascal是一个跨平台的编译器，而Turbo Pascal只在windows和DOS上使用。3、选B4、选CLinux是一种自由和开放源码的类Unix操作系统。目前存在着许多不同的Linux,但它们都使用了Linux内核。Linux可安装在各种计算机硬件设备中，从手机、平板电脑、路由器和视频游戏控制台，到台式计算机、大型机和超级计算机。Linux是一个领先的操作系统，世界上运算最快的10台超级计算机运行的都是Linux操作系统。严格来讲，Linux这个词本身只表示Linux内核，但实际上人们已经习惯了用Linux来形容整个基于Linux内核，并且使用GNU 工程各种工具和数据库的操作系统。Linux 操作系统是UNIX 操作系统的一个克隆版本。UNIX 操作系统是美国贝尔实验室的肯汤普逊Ken.Thompson和丹尼斯里奇Dennis Ritchie 于1969 年夏在DEC PDP-7 小型计算机上开发的一个分时操作系统。5、选BAhard diskBcentral processing unitDRegister寄存器是中央处理器内的组成部分。寄存器是有限存贮容量的高速存贮部件，它们可用来暂存指令、数据和位址。在中央处理器的控制部件中，包含的寄存器有指令寄存器(IR，Instruction register)和程序计数器(PC)。在中央处理器的算术及逻辑部件中，包含的寄存器有累加器(ACC，accumulator)。6、选B防火墙(英文：firewall)是一项协助确保信息安全的设备，会依照特定的规则，允许或是限制传输的数据通过。防火墙可以是一台专属的硬件也可以是架设在一般硬件上的一套软件。7、选C高级语言是面向开发人员的，所以看起来很容易明白，但是机器就只懂机器语言(0101之类的二进制数字)不懂了，就需要把这种语言转化为机器语言，由于是面对开发人员，所以转化起来，通常会占用很大的内存。汇编通常是针对芯片来的，也需要转化为机器语言后，机器才能识别，但是它占用的内存很低，执行的稳定性高。高级语言和低级语言的区别：如果两者都是32位应用程序的话，汇编程序是由CPU指令直接汇编而成，且指令助记符与机器码之间是一一对应，故而精简。高级语言需要先通过编译器将高级语言源程序编译成汇编层程序，然后再由汇编器和连接器生成最终程序，编译时高级语言将被转化为数倍于自身的汇编语言，虽然有编译器的优化，还是没有手动写出的汇编程序精简，这就造成了代码量（容量）的扩大，更多的代码通常意为着要消耗更多的CPU周期去执行，这样单位时间内的执行速率也就被相应延缓。汇编只适合开发小型软件，接口程序，不怡用来开发大型软件，反之高级程序适用于大型软件的开发。CSimula 67被认为是最早的面向对象程序设计语言。1967年5月20日，在挪威奥斯陆郊外的小镇莉沙布举行的IFIP TC-2 工作会议上，挪威科学家Ole-Johan Dahl和Kristen Nygaard正式发布了Simula 67语言。Simula 67被认为是最早的面向对象程序设计语言，它引入了所有后来面向对象程序设计语言所遵循的基础概念：对象、类、继承。Smalltalk是历史上第二个面向对象的程序设计语言8、选A算法（algorithm）是在有限步骤内求解某一问题所使用的一组定义明确的规则。一个算法应该具有以下五个重要的特征： l 有穷性： 一个算法必须保证执行有限步之后结束； l 确切性： 算法的每一步骤必须有确切的定义； l 输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件； l 输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的； l 可行性： 算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。算法可以人工实现9、选D1）插入排序：每次将一个待排的记录插入到前面的已经排好的队列中的适当位置。.直接插入排序直接排序法在最好情况下（待排序列已按关键码有序），每趟排序只需作1次比较而不需要移动元素。所以n个元素比较次数为n-1，移动次数0。最差的情况下（逆序），其中第i个元素必须和前面的元素进行比较i次，移动个数i+1，所以总共的比较次数 比较多，就不写出来了总结：是一种稳定的排序方法，时间复杂度O(n2)，排序过程中只要一个辅助空间，所以空间复杂度O(1).希尔排序缩小增量排序，对直接插入排序的一种改进分组插入方法。总结：是一种不稳定的排序方法，时间复杂度O(n1.25)，空间复杂度O(1)2）交换排序.冒泡排序最好的情况下，就是正序，所以只要比较一次就行了，复杂度O(n)最坏的情况下，就是逆序，要比较n2次才行，复杂度O(n2)总结：稳定的排序方法，时间复杂度O(n2)，空间复杂度O(1)，当待排序列有序时，效果比较好。.快速排序通过一趟排序将待排的记录分割成独立的两部分，其中一部分记录的关键字均比另一个部分的关键字小，然后再分别对这两个部分记录继续进行排序，以达到整个序列有效。总结：在所有同数量级O(nlogn)的排序方法中，快速排序是性能最好的一种方法，在待排序列无序时最好。算法的时间复杂度是O(nlogn)，最坏的时间复杂度O(n2)，空间复杂度O(nlogn)3.选择排序.直接选择排序和序列的初始状态无关总结：时间复杂度O(n2)，无论最好还是最坏.堆排序直接选择排序的改进总结：时间复杂度O(nlogn)，无论在最好还是最坏情况下都是O(nlogn)4）归并排序总结：时间复杂度O(nlogn)，空间复杂度O(n)5.基数排序按组成关键字的各个数位的值进行排序，是分配排序的一种。不需要进行排码值间的比较就能够进行排序。总结：时间复杂度O(d(n+rd)总总结：l n比较小的时候，适合 插入排序和选择排序l 基本有序的时候，适合 直接插入排序和冒泡排序l n很大但是关键字的位数较少时，适合 链式基数排序l n很大的时候，适合 快速排序 堆排序 归并排序l 无序的时候，适合 快速排序l 稳定的排序：冒泡排序 插入排序 归并排序 基数排序l 复杂度是O(nlogn)：快速排序 堆排序 归并排序l 辅助空间（大 次大）：归并排序 快速排序l 好坏情况一样：简单选择（n2），堆排序（nlogn），归并排序（nlogn）l 最好是O(n)的：插入排序 冒泡排序10、选D数组的顺序存储结构在计算机中，表示数组最普通的方式是采用一组连续的存储单元顺序地存放数组元素。除了顺序存储结构，还可以使用链式存储结构顺序存储需要开辟一个定长的空间，读写速度快，缺点不可扩充容量(如果要扩充需要开辟一个新的足够大的空间把原来的数据重写进去) 链式存储无需担心容量问题，读写速度相对慢些，由于要存储下一个数据的地址所以需要的存储空间比顺序存储大。 综上所述，如果元素个数已知，且插入删除较少的可以使用顺序结构，而对于频繁有插入删除操作，元素个数未知的，最好使用链式结构，编程时可结合要处理的数据的特点设计数据结构的。11、选C请查阅xor相关介绍12、选D13、选C栈的操作14、均衡二叉树就是：任意两个度不为2的节点的深度之差不大于1例如：123451234567左图是均衡二叉树，而右图就不是，2和7的深度差2.因为211 = 2048；所以一颗满二叉树从深度为0（根节点）到深度10的总节点数是2047，剩下2381-2047 = 334个节点，这剩下的节点的深度都是11。二叉树具有下列重要性质： 性质1二叉树的第i层上至多有2i-1个结点(i=1) 对于这个问题可就i=1和i1两种情况进行讨论： 当i=1时，2i-1=20=1,因为二叉树的第一层上只有一个结点（即根结点），故命题成立。 当i1时，假定第i-1层上的结点至多有2(i-1)-1=2i-1个，根据二叉树的定义，每个结点至多有两个孩子，所以第i层上的结点数至多为第i-1层上的2倍，即22i-2=2i-1,得到第i层上的结点数至多为2i-1，命题成立。 性质2 深度为h的二叉树至多有2h-1个结点。 显然，当深度为h的二叉树上每一层都达到最多结点数时，它们的和才能最大，即整个二叉树才具有最多结点数。 故命题正确。 在一棵二叉树中，当第i层的结点数为2i-1个时，侧称此层的结点数是满的，当树中的每一层都满时，则称此树为满二叉树。有性质2可知，深度为h的满二叉树中的结点数为2h-1个。在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是右边缺少连续若干个结点，则称此树为完全二叉树。由此可见，满二叉树是完全二叉树的特例。性质3 对完全二叉树中编号为h的结点(1in，n1,n为结点数）有： (1) 若in/2,即2in，则编号为i的结点为分支结点，否则为叶子结点。 (2) 若n为奇数，则每个分支结点都既有左孩子又有右孩子；若n为偶数，则编号最大的分支结点(编号为n/2),只有左孩子，没有右孩子，其余分支结点左右孩子都有。 (3) 若编号为i的结点有左孩子，则左孩子结点的编号为2i；若编号为i的结点有右孩子，则右孩子结点的编号为2i+1。 (4) 除跟结点外，若一个结点的编号为i，则它的双亲结点的编号为i/2,也就是说，当i为偶数时，对应为左孩子，其双亲结点的编号为i/2,当i为奇数时，对应为右孩子，其双亲结点的编号为(i-1)/2。 性质4 具有n个(n0)结点的完全二叉树的深度为log2(n+1)或log2n+1。 证明1 设所求完全二叉树的深度为h，有完全二叉树的定义可知，它的前h-1层都是满的，最后一层可以满，也可以不满，由此得到如下不等式： 2h-1-1 n 2h-1 可变换为： 2h-1 n+1 2h 取对数后得到: h-1 log2(n+1)h 即 log2(n+1) hlog2n+1 因h只能取整数，所以h=log2(n+1) 证明2 完全二叉树的深度h和结点数n的关系，可以表示为： 2h-1 n 2h 取对数后得到: h-1 log2n h 即 log2n h log2n+1 得h=log2n+1 在一棵二叉树中，若除最后一层外，其余层都是满的，则称此数为理想平衡树。显然理想平衡树包含满二叉树和完全二叉树。完全二叉树中深度h和结点数n之间的关系，在理想平衡树中同样成立。下左图，就是一棵理想平衡树，但它不是完全二叉树；下图不是一棵理想平衡二叉树，因它的最后两层都未满。 (a)(b)理想平衡树和非理想平衡树性质5、n0=n2+1，二叉树的所有结点数=分支数+115、选C进制计算16、5个数7次搞定，具体如下： 假设5个数分别编号1，2，3，4，5， 1v2，3v4-2次，假设12，34；1v3，-1次，假设13,则134；把5插入1，3，4中，需要2次，结果有4种： 5134，则把2插入3，4中，需2次 1534，则把2插入5，3，4中，需2次1354，同上 1345，同上 这样一共2+1+2+27次！ 假设a,b,c,d,e5个数，: 先堆排序，a,b比较，c,d比较，e落单: 假设ab,cd: 再a,e比较，c,e比较: 因为我们肯定是假设这5个数不可能有相等的情况，: 所以再假设ae,cd,ce,所以只需比较b,e就得出第二大的数，: 剩下3个数一下就更好看出来了17、选B逻辑运算18、选A19、选C20、选B二、1、共次。三分法：第一次分成（27，27，26），第一次称27和27，如果一样重说明假币在26中，如果有一边轻在轻的一边，然后第二次称有假币的，方法和第一次一样，依次类推。2、只有一堆时，无论有多少，先取者都可以一次性全部取走，所以必胜。 (1,1)时，显然先取者必败。 (1,2)时，先取者必胜，他可以在2那一堆中取1个，于是变成(1,1)，但这成为上一种情况了，于是接下来取的人必败，亦即先取者必胜。 (1,3)时，先取者必胜。他可以在3那一堆中取2个，于是变成(1,1)。 (2,2)时，先取者必败。他在任何一堆中取1个，对方随即在另一堆中取1个，即变成(1,1)；如果他取走一堆中的全部石子，对方即取走另一堆中的全部石子。 (2,3)时，先取者必胜。他可以在3那一堆中取1个，于是变成(2,2)。 (3,3)时，先取者必败。他取走任一堆中的1,2或3个，就变成了以上讨论过的情形。 (1,1,1)时，先取者必胜。他取走任一堆，就变成了(1,1)。 (1,1,2)时，先取者必胜。他取走2那一堆，就变成了(1,1)。 (1,1,3)时，先取者必胜。他取走3那一堆，就变成了(1,1)。 (1,2,2)时，先取者必胜。他取走1那一堆，就变成了(2,2)。 (1,2,3)时，先取者必败。分析如下： 他先取1那一堆，则变为(2,3)，由上面的分析，对手必胜。 他从2那一堆中取1个，就变成了(1,1,3)，对手可以将3那一堆全部取走，变成了(1,1)，于是必胜。 他将2那一堆全部取走，就变成了(1,3)，对手必胜。 他从3那一堆中取1个，就变成了(1,2,2)，对手必胜。 他从3那一堆中取2个，就变成了(1,2,1)，对手必胜。 他将3那一堆全部取走，就变成了(1,2)，对手必胜。 这些胜负有什么规律呢？我们可以将每堆的数转换成二进制，然后看每一位上所有堆里的1的个数总和： 必胜情况：(n) (1,2)(1,3)(2,3) (1,1,1)(1,1,2)(1,2,2) 必败情况： (1,1)(2,2)(3,3) (1,2,3) 化为二进制： 必胜情况： (n)：（反正每位只要有1肯定只有1个） (1,2)：1,10 列成竖式： 01 10 个位上只有1个1，“十位”（因为是二进制所以叫十位不妥，这里为了方便说明暂且使用，下同）上也只有1个1。 (1,3)：1,11 列成竖式： 01 11 个位上有2个1（1的1个，3的1个），十位上有1个1。 (2,3)：10,11 个位上有1个1，十位上有2个1。 (1,1,1)：1,1,1 个位上有3个1。 (1,1,2)：1,1,10 个位上有2个1，十位上有1个1。 (1,1,3)：1,1,11 个位上有3个1，十位上有1个1。 (1,2,2)：1,10,10 个位上有1个1，十位上有2个1。 必败情况： (1,1)：1,1 个位上有2个1。 (2,2)：10,10 十位上有2个1。 (3,3)：11,11 个位上有2个1，十位上也有2个1。 (1,2,3)：1,10,11 个位上有2个1，十位上也有2个1。 下面分析一下这些情况。 先看必败情形。容易发现，所有的必败情形，都是所有的数位上都有偶数个1。 下看必胜情形。我们发现，出现了两种情况： 1.只有1位上有奇数个1，如(1,3)(2,3)(1,1,1)(1,1,2)(1,2,2)。而先取者取走该位上的1，所有的位上就都变成了偶数个1，而这时后取者变成了先取者。 2.有若干位上都是奇数个1，如(n)(1,2)(1,1,3)。先取者取（不一定取走哪位）后，所有的位上也都变成了偶数个1。后取者变成了先取者。 以上两种情况，都是将后取者逼至必败情况从而取胜。 由以上分析我们可以得到结论：将所有的堆的石子数化为二