备战选择题问题求解ppt课件

1、1;.2v初赛：初赛全部为笔试，满分初赛：初赛全部为笔试，满分100分。分。v试题由四部分组成：试题由四部分组成： v1、选择题：共、选择题：共20题，每题题，每题1.5分，共计分，共计30分。分。(普及组全为单选题普及组全为单选题;提高组提高组10个单选，个单选，10个个不定项选择不定项选择)v2、问题求解题：共、问题求解题：共2题，每题题，每题5分分,共计共计10分分 v3、程序阅读理解题、程序阅读理解题:共共4题，每题题，每题8分分,共计共计32分。分。 v4、程序完善题：共、程序完善题：共2题，每题题，每题14分，共计分，共计28分。分。3v计算机基本常识：计算机基本常识： IT文化、

2、微机原理、信息安全、基本应用文化、微机原理、信息安全、基本应用v与奥赛活动有关的知识与奥赛活动有关的知识v程序语言及算法基础程序语言及算法基础v数据结构数据结构(串、栈、队、树、图串、栈、队、树、图)v离散数学：排列组合、数理逻辑离散数学：排列组合、数理逻辑4v重点考查：在重点考查：在IT领域中的杰出人物及重要事项领域中的杰出人物及重要事项v范围较广，准备较困难范围较广，准备较困难v关注关注IT界发展动态界发展动态5v1-1. 在下面各世界顶级的奖项中，为计算机科学与技术领域做出杰出贡献的科学家设立的在下面各世界顶级的奖项中，为计算机科学与技术领域做出杰出贡献的科学家设立的奖项是（奖项是（ ）

3、。）。 v A. 沃尔夫奖沃尔夫奖 B. 诺贝尔奖诺贝尔奖v C. 菲尔兹奖菲尔兹奖 D. 图灵奖图灵奖 v答案：答案：D6v1-2、Google 是万维网上最大的搜索引擎，使用户能够访问一个包含超过是万维网上最大的搜索引擎，使用户能够访问一个包含超过 80 亿个网址的亿个网址的索引。索引。Google 坚持不懈地对其搜索功能进行革新，始终保持着自己在搜索领域的领先地坚持不懈地对其搜索功能进行革新，始终保持着自己在搜索领域的领先地位。位。 Google的创始人是（的创始人是（ ）vA、Sergey Brin 、 Larry PagevB、陈天桥、陈天桥vC、Bill Gates vD、 Ala

4、n M. Turingv答案：答案：A (塞奇塞奇布林布林 、拉里拉里佩奇佩奇 )7v微机系统（硬件系统、软件系统）微机系统（硬件系统、软件系统）v病毒、杀毒软件、防火墙等病毒、杀毒软件、防火墙等v信息的存储（多媒体存储容量的计算）信息的存储（多媒体存储容量的计算）v电子邮件相关电子邮件相关v网络知识网络知识vLINUX 系统系统8v2-1. 我们平时所说的内存条是指（我们平时所说的内存条是指（ ）。）。 vA. 寄存器寄存器 B. ROM C. RAM D. 高速缓存高速缓存v答案：答案：C9v2-2、通常所说的、通常所说的32位计算机是指（位计算机是指（ ）vA、是由、是由32个运算器组成

5、的个运算器组成的 vB、通用寄存器数目为、通用寄存器数目为32个个vC、CPU一次可处理的数据为一次可处理的数据为32位位vD、地址总线的宽度为、地址总线的宽度为32位位vE、数据总线的宽度为、数据总线的宽度为32位位v答案：答案：C10v2-3Linux是一种是一种( )。 vA.单用户、单任务的操作系统单用户、单任务的操作系统vB.单用户、多任务的操作系统单用户、多任务的操作系统vC.多用户、单任务的操作系统多用户、单任务的操作系统vD.多用户、多任务的操作系统多用户、多任务的操作系统v答案：答案：D11v2-4、Linux下的超级用户的名字是（下的超级用户的名字是（ ）vA. root

6、B.supervisor C.administrator D.managerv答案：答案：A12v2-5、下列说法中不正确的是（、下列说法中不正确的是（ ）vA、在同一台、在同一台PC机上可以安装多个操作系统机上可以安装多个操作系统vB、在同一台、在同一台PC机上可以安装多个网卡机上可以安装多个网卡vC、在、在PC机的一个网卡上可以同时绑定多个机的一个网卡上可以同时绑定多个IP地址地址vD、一个、一个IP地址可以同时绑定到多个网卡上地址可以同时绑定到多个网卡上vE、同一个局域网上不同的、同一个局域网上不同的PC机不能使用同一个机不能使用同一个IP地址地址v答案：答案：D13v2-6在编程时（使

7、用任一种高级语言，不一定是在编程时（使用任一种高级语言，不一定是Pascal），如果需要从磁盘文件中输入），如果需要从磁盘文件中输入一个很大的二维数组（例如一个很大的二维数组（例如1000*1000的的double型数组），按行读（即外层循环是关于行型数组），按行读（即外层循环是关于行的）与按列读（即外层循环是关于列的）相比，在输入效率上（的）与按列读（即外层循环是关于列的）相比，在输入效率上（ ）。）。 vA. 没有区别没有区别 vB. 按行读的方式要高一些按行读的方式要高一些 vC. 按列读的方式要高一些按列读的方式要高一些 vD. 取决于数组的存储方式。取决于数组的存储方式。 v答案：答

8、案：D14v2-7、如果、如果pascal系统只允许变量使用系统只允许变量使用64KB的内存，现在让你定义一个值为整型的一维数的内存，现在让你定义一个值为整型的一维数组，这个数组的下标为组，这个数组的下标为1.max，那么，那么max最大可能的值为最大可能的值为( )vA.64 B.64000 C.32000 D.32768v64KB=64*1024Bv整型占整型占2个字节个字节v所以所以,max=64*1024/2v答案选答案选D15v2-8、数组、数组A0.5,0.6的每个元素占的每个元素占5个单元，将其按列优先次序存储在起始地址为个单元，将其按列优先次序存储在起始地址为1000的的连续的

9、内存单元中，则元素连续的内存单元中，则元素A5，5的地址为（的地址为（ ）vA.1175 B.1180 C.1205 D.1210 E.1190v分析：分析：v1、搞清楚列优先的含义、搞清楚列优先的含义v2、A5，5前面有前面有0,1,2,3,4共共5列，每列有列，每列有0.5共共6个元素个元素,第第5列前面有列前面有0.4五个元素，共有五个元素，共有5*6+5=35v3、地址、地址： （5*6+5）*5+1000=117516v2-9、. 在计算机中，防火墙的作用是（在计算机中，防火墙的作用是（ ）。）。 vA、防止火灾蔓延防止火灾蔓延 B、防止网络攻击防止网络攻击 vC、 防止计算机死机防

10、止计算机死机 D、防止使用者误删除数据防止使用者误删除数据 v答案选答案选B17noip初赛（初赛（10月中下旬）月中下旬）noip复赛（复赛（11月中下旬）月中下旬）省队选拔赛（由各省自行组织）省队选拔赛（由各省自行组织）noi决赛（次年暑假）决赛（次年暑假）全国冬令营（次年年底）全国冬令营（次年年底）国家队选拔赛国家队选拔赛ctsc（次次年（次次年5月）月）国际比赛国际比赛ioi（次次年（次次年910月）月）18v3-1、 在下列各软件中，不属于在下列各软件中，不属于NOIP竞赛（复赛）推荐使用的语言环境有（竞赛（复赛）推荐使用的语言环境有（ ）。）。 vA. gcc/g+ B. Turb

11、o Pascal vC. RHIDE D. free pascal E、Lazarusv答案选答案选B推荐的：推荐的： pascal: free pascal、 Lazarus c 及及c+、 Dev C+、 gcc/g+、 RHIDE不推荐的不推荐的: TP7(turbo pascal 7) 、TC(turbo C) 、Visual C+ 194、程序语言及算法基础、程序语言及算法基础v了解算法的五大特征：了解算法的五大特征： 有穷性、确定性、可行性、有穷性、确定性、可行性、0或多个输入、有一个或多个输出或多个输入、有一个或多个输出v要求掌握的排序有：要求掌握的排序有： 冒泡法、插入排序、合

12、并排序、快速排序冒泡法、插入排序、合并排序、快速排序v理解每种排序的算法思想理解每种排序的算法思想v了解每种排序的时间复杂度及其稳定性了解每种排序的时间复杂度及其稳定性20v4-1、在下列关于计算机语言的说法中，不正确的是（在下列关于计算机语言的说法中，不正确的是（ ）。）。 vA. Pascal和和C都是编译执行的高级语言都是编译执行的高级语言 vB. 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上 vC. C+是历史上的第一个支持面向对象的计算机语言是历史上的第一个支持面向对象的计算机语言 vD. 与汇编语言

13、相比，高级语言程序更容易阅读与汇编语言相比，高级语言程序更容易阅读v答案选答案选C21v4-2、 在下列关于计算机算法的说法中，不正确的是（在下列关于计算机算法的说法中，不正确的是（ ）。）。 vA. 一个正确的算法至少要有一个输入一个正确的算法至少要有一个输入 vB. 算法的改进，在很大程度上推动了计算机科学与技术的进步算法的改进，在很大程度上推动了计算机科学与技术的进步 vC. 判断一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性判断一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性 vD. 目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有目前仍然存在许

14、多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法效算法v答案选答案选A22v4-3、 在下列各种排序算法中，不是以在下列各种排序算法中，不是以“比较比较”作为主要操作的算法是（作为主要操作的算法是（ ）。）。 A. 选择排序选择排序 B. 冒泡排序冒泡排序 C. 插入排序插入排序 D. 基数排序基数排序 v1、基数排序是基于、基数排序是基于“分配分配”和和“收集收集”的排序的排序v2、技巧：用排除法做，前、技巧：用排除法做，前3者都是通过比较来排序的。者都是通过比较来排序的。23v4-4、某数列有、某数列有1000个各不相同的单元个各不相同的单元,由低到高按序排列由低到高按序

15、排列,现要对该数列进行二分法检索现要对该数列进行二分法检索,在最坏的情况下在最坏的情况下,需要检索需要检索( )个单元。个单元。vA.1000 B.10 C.100 D.500v分析：二分法的检索次数为分析：二分法的检索次数为log21000+1v答案：答案：B24v4-5、在在Pascal语言中，判断语言中，判断a不等于不等于0且且b不等于不等于0的正确的条件表达式是（的正确的条件表达式是（ ）vA. not a=0 or not b=0 vB. not(a=0)and(b=0) vC. not(a=0 and b=0) vD. (a0)and (b0) v答案选答案选D25v4-6、将将5

16、个数的序列排序，不论原先的顺序如何，最少都可以通过（个数的序列排序，不论原先的顺序如何，最少都可以通过（ ）次比较，完成从）次比较，完成从小到大的排序。小到大的排序。 vA. 6 B. 7 C. 8 D. 9 26分析v1、既然是追求最少比较次数，必定不会用、既然是追求最少比较次数，必定不会用n2的算法排序。的算法排序。v2、排序本质可说是循环查找各个位置上数、排序本质可说是循环查找各个位置上数v（1）用二分查找）用二分查找v（2）总次数）总次数322727v4-7、下列序列中，（、下列序列中，（ ）是执行第一趟快速排序后得到的序列（排序的关键字类型是字）是执行第一趟快速排序后得到的序列（排序

17、的关键字类型是字符串）。符串）。vA.da,ax,eb,de,bb ff ha,gcvB.cd,eb,ax,da ff ha,gc,bbvC.gc,ax,eb,cd,bb ff da,havD.ax,bb,cd,da ff eb,gc,hav答案：答案：A28v4-8、递归算法的执行过程，一般来说，可先后分成递推和、递归算法的执行过程，一般来说，可先后分成递推和( )两个阶段。两个阶段。A.回溯回溯B.回归回归C.返回返回D.合成合成 v答案：答案：B 29v位逻辑运算：位逻辑运算： （与）（与） 、（或）、（或）、Xor(异或异或)、（非）（非）v位移运算位移运算: shl（左移位）左移位）

18、 、 shr（右移位）右移位）301、（与）、（与）、（或）、（或）、（非）（非） 运算：对应位都为运算：对应位都为1 1时为时为1 1，否则为，否则为0 0。如下：。如下： 110111 110111 001101 001101 - 000101000101运算：对应位只要有一个运算：对应位只要有一个1 1就为就为1 1。如下：。如下： 110111 110111 001101 001101 - 111111111111运算：对每个上的值按位求反：运算：对每个上的值按位求反：1变为变为0；0变为变为1312、Xor(异或)v1、Xor(异或异或)：对应位相同为：对应位相同为“0”，不同为，不

19、同为“1”v 10101v 00111v -v 10010323 3、shlshl（左移）、左移）、shrshr（右移）右移）Shl nShl n（左移位）左移位）: :所有位向左移动所有位向左移动n位位(00001)2 shl 1 =(00010)2(00101)2 shl 2 =(10100)2 小结：小结：二进制每左移一位相当于乘以一个二进制每左移一位相当于乘以一个2Shr nShr n（右移位）右移位）所有位向右移动所有位向右移动n位位(00010)2 shr 1 =(00001)2(00100)2 shr 2 =(00001)2 小结：小结：二进制每右移一位相当于二进制每右移一位相当

20、于除除以一个以一个233v5-1、已知、已知A=35H，则则A 0505H H A A 3030H H的结果是（的结果是（ ） A A、30H B30H B、05H C05H C、35H D35H D、53H E53H E、00H00H分析：分析：1 1、运算优于运算优于运算运算2 2、化为二进制后再做运算化为二进制后再做运算34v5-2、在在Pascal语言中，表达式语言中，表达式 (21 xor 2)的值是（的值是（ ） A. 441 B. 42 C.23 D.24 分析：分析： 10101 (21) 00010 (2) - 10111 (23)356、进制数的运算、进制数的运算v十进制（

21、十进制（0-9）v二进制（二进制（0、1）、）、v八进制（八进制（0-8）v十六进制（十六进制（0-9，A-F）v掌握不同进制数之间的相互转换掌握不同进制数之间的相互转换v注意技巧，节省时间注意技巧，节省时间36v1、十进制数、十进制数 N进制数进制数 方法：除N取余倒序法v2、N进制数进制数 十进制数（带小数）十进制数（带小数）v方法：整数部分：kNi求和法v 小数部分：小数部分*N取整v3、十六进制数与二进制数间的关系、十六进制数与二进制数间的关系v每位十六进制数相当于4位二进制数v如（215）16=（1）2v4、八进制数与二进制数间的关系、八进制数与二进制数间的关系v每位八进制位相当于3

22、位二进制数v如（215）8=（010001101）237v例例1：将：将(1011010.10)2转换成八进制和十六进制数转换成八进制和十六进制数 v001 011 010. 100 (1011010.10)2=(132.4)8v 1 3 2 . 4v0101 1010. 1000 (1011010.10)2=(5A.8)16v 5 A . 8v例例2、将十六进制数、将十六进制数F7.28变为二进制数变为二进制数vF 7 . 2 8 (F7.28)16=(11110111.00101)21111 0111.0010 1000 v例例3、将八进制数、将八进制数25.63转换为二进制数转换为二进制

23、数v2 5 6 3 (25.63)8(10101.110011)2 10 101. 110 011 38v6-1 与十进制数与十进制数1770 对应的八进制数是（对应的八进制数是（ ）。）。 vA. 3350 B. 3351 C. 3352 D. 3540v技巧：只需口算最低位的数字即可技巧：只需口算最低位的数字即可39v6-2、 (2010)16 + (32)8的结果是（的结果是（ ）。）。 vA. (8234)10 B. (202B)16 vC. (20056)8 D. (1)240一、线性结构：串、栈、队一、线性结构：串、栈、队二、非线性结构：树、图二、非线性结构：树、图41v栈特点：先

24、进后出（栈特点：先进后出（FILO、LIFO）v队特点：先进先出（队特点：先进先出（FIFO、LILO）v注意：有些题中还规定了栈或队的空间注意：有些题中还规定了栈或队的空间42v树：普通二叉树、满二叉树、完全二叉树树：普通二叉树、满二叉树、完全二叉树v二叉树的特点：二叉树的特点：v1 1、第、第i i层的结点最多为层的结点最多为2 2i-1i-1（i=1i=1）个结点，深度为个结点，深度为K K（K=1K=1）的二叉树最多有的二叉树最多有2 2k k-1-1个结点。个结点。v2 2、在二叉树中，如果其叶子结点数为、在二叉树中，如果其叶子结点数为n0n0，则其度为则其度为2 2的结点数为的结点

25、数为n2=n0-1n2=n0-1。v完全二叉树的特点：完全二叉树的特点：v1 1、树叶只可能在层次最大的两层上出现。、树叶只可能在层次最大的两层上出现。v2 2、对任一结点，左子树的深度或者比右子树的深度多、对任一结点，左子树的深度或者比右子树的深度多1 1，或者与右子树深度相等。，或者与右子树深度相等。v3 3、具有、具有n n个结点的完全二叉树的深度为个结点的完全二叉树的深度为K=logK=log2 2n +1n +143v前序遍历（前序遍历（DLR）v根根左子树左子树右子树右子树v中序遍历（中序遍历（LDR）v左子树左子树根根右子树右子树v后序遍历（后序遍历（LRD）v左子树左子树右子树

26、右子树根根v已知前序遍历（或后序遍历）和中序遍历，就能唯一确定其他一种遍历已知前序遍历（或后序遍历）和中序遍历，就能唯一确定其他一种遍历v已知前序遍历和后序遍历，不能唯一确定中序遍历已知前序遍历和后序遍历，不能唯一确定中序遍历44v图的遍历：从图中某一顶点出发访问图中其余的顶点，使每个顶点都被访问且仅访问一次。图的遍历：从图中某一顶点出发访问图中其余的顶点，使每个顶点都被访问且仅访问一次。v深度优先搜索（深度优先搜索（DFS）v广度优先搜索（广度优先搜索（BFS）45v7-1、某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车、某个车站呈狭长形，宽度只能容下一台车，并且只

27、有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出，进，进，进，出，出，进，进，进，出进，出,出出”。假设车辆入站的顺序为。假设车辆入站的顺序为1，2，3，则车辆出站的顺序为（，则车辆出站的顺序为（ ）。）。 vA. 1, 2, 3, 4, 5 vB. 1, 2, 4, 5, 7 vC. 1, 4, 3, 7, 6 vD. 1, 4, 3, 7, 2 46v7-2、下列叙述中，正确的是（）、下列叙述中，正确的是（）A.线性表的线性存贮结构优于链表存贮结构线性表的线性存贮结构优于链表存贮结构B.

28、队列的操作方式是先进后出队列的操作方式是先进后出C.栈的操作方式是先进先出栈的操作方式是先进先出D. 二维数组是指它的每个数据元素为一个线性表的线性表二维数组是指它的每个数据元素为一个线性表的线性表 47v7-3、一棵二叉树的中序遍历序列为：、一棵二叉树的中序遍历序列为：DGBAECHF，后序遍历序列为：，后序遍历序列为：GDBEHFCA，则，则前序遍历的序列是前序遍历的序列是( )。A. ABCDFGHEB. ABDGCEFHC. ACBGDHEFD. ACEFHBGDv答案：答案：B487-4、在有、在有N个叶子节点的哈夫曼树中，其节点总数为（）个叶子节点的哈夫曼树中，其节点总数为（） A

29、.不确定不确定 B. 2N-1 C. 2N+1 D. 2N1、在哈夫曼树（也叫最优树）中，只有两种类型的结点：度为、在哈夫曼树（也叫最优树）中，只有两种类型的结点：度为0或或N，即最优二叉树中只有度为，即最优二叉树中只有度为0或或2的结点，最优三叉树中只有度为的结点，最优三叉树中只有度为0或或3的结点的结点2、在二叉树中，叶子总比度为、在二叉树中，叶子总比度为2的结点大的结点大1，即，即N=N2+1，又因为没有度为，又因为没有度为1的结点，所以总结的结点，所以总结点数为点数为N+N2=N+N-1=2N-1497-5、高度为、高度为n的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为

30、的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为n-1的满的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为0，如果某个均衡的二叉树，如果某个均衡的二叉树共有共有2381个结点，则该树的树高为（个结点，则该树的树高为（ ）。）。 vA. 10 B. 11 C. 12 D. 13 50注：此题规定根结点的深度为注：此题规定根结点的深度为0v1、满二叉树指的是：对于第、满二叉树指的是：对于第i层，节点数必定是层，节点数必定是2i。v2、有、有i层的满二叉树的节点总数为层的满二叉树的节点总数为2(i+1)-1v3、假定均

31、衡树的层数为、假定均衡树的层数为x，那么该均衡树对应的满二叉树（比均衡树小，那么该均衡树对应的满二叉树（比均衡树小1层）节点数为层）节点数为2x-1,则必定有：则必定有：v2x-12381=3)个顶点的无向图是连通的，这个图至少要有（个顶点的无向图是连通的，这个图至少要有（ ）条边）条边vA.(n-1)*(n-2)/2+1vB.n*(n-1)/2-(n+2)vC.(n-2)*(n-1)/2vD.(n/2+1)*(n-1)v答案：答案：A55v7-10、下列有关树的叙述中、下列有关树的叙述中,叙述正确的是叙述正确的是( )vA、在含有、在含有n个结点的树中，边数只能是个结点的树中，边数只能是n-

32、1条条vB、在哈夫曼树中，外部结点的个数比内部结点个数多、在哈夫曼树中，外部结点的个数比内部结点个数多1vC、完全二叉树一定是平衡二叉树、完全二叉树一定是平衡二叉树vD、在二叉树的前序遍序列中，若结点、在二叉树的前序遍序列中，若结点U在结点在结点V之前，则之前，则U一定是一定是V的祖先的祖先vE、在查找树中插入一个新结点，总是插入到叶结点下面、在查找树中插入一个新结点，总是插入到叶结点下面v分析：分析：v1、前序遍历是根、前序遍历是根左左右，显然右，显然D是错误的是错误的v2、插入结点可以插在一个只有一个儿子的结点下方、插入结点可以插在一个只有一个儿子的结点下方56v7-11、以下数据结构中哪

33、些不是线性结构、以下数据结构中哪些不是线性结构?A、有向图、有向图 B、栈、栈 C、二叉树、二叉树vD、B树树 E、队列、队列57v排列排列v组合组合v数理逻辑数理逻辑58v8-1、 设设A=B=D=true，C=false，以下逻辑运算表达式值为，以下逻辑运算表达式值为真真(假假)的有（的有（ ）。）。 vA. (AB)(CD) B. (ABD)C) vC. A(BCD) D. (ABC)D 59总结v1、进制转换是必考的（二、八、十六进制）、进制转换是必考的（二、八、十六进制）v2、堆栈是必考的、堆栈是必考的,可关注队列的操作可关注队列的操作v3、二叉树性质、遍历必考的、二叉树性质、遍历必

34、考的v4、微机原理必考的（、微机原理必考的（CPU、ROM等）等）v5、排序算法的分析，概率较大、排序算法的分析，概率较大v6、新动向：和信息学奥赛的知识、新动向：和信息学奥赛的知识v7、信息安全，概率较大、信息安全，概率较大v8、网络有关知识，今年估计会出现、网络有关知识，今年估计会出现60v1、数据结构、数据结构(树、图树、图)v2、算法设计（构造类算法）、算法设计（构造类算法）v3、数学知识（初中不多，高中较多）、数学知识（初中不多，高中较多）61v1（寻找假币） 现有80枚硬币，其中有一枚是假币，其重量稍轻，所有真币的重量都相同，如果使用不带砝码的天平称重，最少需要称几次，就可以找出假

35、币？你还要指出第1次的称重方法。请写出你的结果：_。 62v1、该题的原型是用、该题的原型是用“二分法二分法”编程求解。二分法至少需要编程求解。二分法至少需要log(80）次，大约是）次，大约是7。v2、二分法的优越在于每次判断时可以排除一半。进一步思考是否分成的部分越多，每次、二分法的优越在于每次判断时可以排除一半。进一步思考是否分成的部分越多，每次判断可以排除的数量越多？判断可以排除的数量越多？v3、平均分成、平均分成3份来判断，每次可以排除份来判断，每次可以排除2/3数量。（思考分成更多份是否效果更好？）数量。（思考分成更多份是否效果更好？）63v1、平均分成、平均分成3份，如果不能被份

36、，如果不能被3整除，那么尽量让两份相同并且相同的两分应该比其他一整除，那么尽量让两份相同并且相同的两分应该比其他一份大份大1（每次判断可以排除更多的数量）（每次判断可以排除更多的数量）v2、每次称相同的两份。直到最后相同的两分是、每次称相同的两份。直到最后相同的两分是1。64实例27，27，269，9，91，1，13，3，39，9，81，1，13，3，21，165v2（取石子游戏）（取石子游戏） 现有现有5堆石子堆石子,石子数依次为石子数依次为3，5，7，19，50，甲乙两人轮流从任一堆，甲乙两人轮流从任一堆中任取（每次只能取自一堆，不能不取）中任取（每次只能取自一堆，不能不取）, 取最后一颗

37、石子的一方获胜。甲先取，问甲有没取最后一颗石子的一方获胜。甲先取，问甲有没有获胜策略（即无论乙怎样取，甲只要不失误，都能获胜）？如果有，甲第一步应该在哪有获胜策略（即无论乙怎样取，甲只要不失误，都能获胜）？如果有，甲第一步应该在哪一堆里取多少？请写出你的结果：一堆里取多少？请写出你的结果： v_。 66题2：xor操作v1、异或结果非、异或结果非0，必胜，否则必输。，必胜，否则必输。v2、根据下面列式，只要让、根据下面列式，只要让50对应的最高位对应的最高位1去掉，去掉，xor结果就是结果就是0，而这个最高位的，而这个最高位的1对应是对应是32。v000011（3）v000101（5）v000

38、111（7）v010011（19）v110010（50）67v3、10名划船运动员中，名划船运动员中，3人只会划左舷，人只会划左舷，2人只会划右舷，人只会划右舷，5人左右舷都会划，从中选人左右舷都会划，从中选6人，人，平均分在左、右舷，共有多少种不同的选法？平均分在左、右舷，共有多少种不同的选法？68题3：组合问题组合问题v采用穷举划左舷的所有情况进行分析采用穷举划左舷的所有情况进行分析v1 1、会划左舷的全划左舷。左舷一共只有、会划左舷的全划左舷。左舷一共只有1 1种，右舷为种，右舷为7 7选选3 3，方法共有：，方法共有：vC C（3 3，3 3）* *C C（7 7，3 3）=35=35

39、v2 2、派一个全能的划左舷、派一个全能的划左舷, ,共有方法共有方法: :vC(5C(5，1)1)* *C(3C(3，2)2)* *C(6C(6，3)=53)=5* *3 3* *20=30020=300v3 3、派二个全能的划左舷、派二个全能的划左舷, ,共有方法共有方法: :vC(5C(5，2)2)* *C(3C(3，1)1)* *C(5C(5，3)=103)=10* *3 3* *10=30010=300v4 4、派三个全能的划左舷、派三个全能的划左舷, ,共有方法共有方法: :vC(5C(5，3)3)* *C(3C(3，3)3)* *C(4C(4，3)=103)=10* *1 1*

40、*4=404=40v因此，方法数共有：因此，方法数共有：35+300+300+40=67569v4 4、设树、设树T T有有1717条边，条边，1212片树叶，片树叶，4 4个个4 4度内部结点，度内部结点，1 1个个3 3度内部结点。求度内部结点。求T T的树根的度数。的树根的度数。 注意：本题中度数定义均为图的度数定义。注意：本题中度数定义均为图的度数定义。70题题4：数据结构题：数据结构题v图中结点的度指的是什么？如何计算？图中结点的度指的是什么？如何计算？v是指结点的出度和入度。度是指结点的出度和入度。度=出度出度+入度入度v已知已知17条边，可知结点为条边，可知结点为18个。个。v设

41、根的度为设根的度为X，则所有结点的度之和为：则所有结点的度之和为：x+4*4+3*1+12v度与边有关系吗？度与边有关系吗？v显然，总度数应是边的两倍，显然，总度数应是边的两倍， 即即 x+4*4+3*1+12=17*2 =x=371v5、光明中学开设数学、英语和信息学三个兴趣学习小组，其中数学小组、光明中学开设数学、英语和信息学三个兴趣学习小组，其中数学小组30人，英语小组人，英语小组15人，信息学小组人，信息学小组18人，参加三个小组总人数为人，参加三个小组总人数为50人，其中有人，其中有3人同时参加人同时参加3个小组，那个小组，那么同时只参加两个小组的同学有多少人么同时只参加两个小组的同

42、学有多少人 ?723XYZ数学英语信息学301518总人数：总人数：50题题5：集合问题：集合问题分析：分析：1、将题目转化为左图所示、将题目转化为左图所示2、x+y+z即为只参加两个小组的同学即为只参加两个小组的同学3、30+15+18-2*3-（X+Y+Z）=50=x+y+z=773v6、十位数、十位数abcdefghij，其中不同的字母表示不同的数字。，其中不同的字母表示不同的数字。a是是1的倍数，两位数的倍数，两位数ab是是2的的倍数，三位数倍数，三位数abc是是3的倍数，四位数的倍数，四位数abcd是是4的倍数，的倍数，,十位数十位数abcdefghij是是10的倍的倍数，则这个十位

43、数是数，则这个十位数是_。74分析v第一步：第一步：j为为0；(十位数十位数abcdefghij是是10的倍数的倍数)v第二步：第二步：e为为5；(五位数五位数abcde是是5的倍数，但的倍数，但e可能为可能为0或或5，但，但0已被已被j占用占用)v第三步：第三步：a、c、g、i为奇数，为奇数，b、d、f、h为偶数；为偶数；(余下余下2、4、6、8的倍数尾数为偶数的倍数尾数为偶数) v第四步：试八位数第四步：试八位数abcdefgh是是8的倍数的倍数 fgh可为可为216、296、416、432、472、496、632、672、816、832、872、896，h可为可为2或或6；v第五步：试六位数第五步：试六位数abcdef是是6的倍数的倍数def可为可为258、456、654、852；75v第六步：合以上第四、五步，第六步：合以上第四、五步，defgh可为可为25816、25896、45632、45672、65432、65472、85216、85296；v第七步：合四位数第七步：合四位数abcd是是