1、Google的创始人是（）A、Sergey Brin、Larry PageB、陈天桥C、Bill Gates D、Alan M.Turing答案：A（塞奇布林、拉里佩奇）,2、微机原理、信息安全、基本应用,微机系统（硬件系统、软件系统）病毒、杀毒软件、防火墙等信息的存储（多媒体存储容量的计算）电子邮件相关网络知识LINUX 系统,2-1.我们平时所说的内存条是指（）。A.寄存器 B.ROM C.RAM D.高速缓存答案：C,2-2、通常所说的32位计算机是指（）A、是由32个运算器组成的 B、通用寄存器数目为32个C、CPU一次可处理的数据为32位D、地址总线的宽度为32位E、数据总线的宽度为
2、32位答案：C,2-3Linux是一种（）。A.单用户、单任务的操作系统B.单用户、多任务的操作系统C.多用户、单任务的操作系统D.多用户、多任务的操作系统答案：D,2-4、Linux下的超级用户的名字是（）A.root B.supervisor C.administrator D.manager答案：A,2-5、下列说法中不正确的是（）A、在同一台PC机上可以安装多个操作系统B、在同一台PC机上可以安装多个网卡C、在PC机的一个网卡上可以同时绑定多个IP地址D、一个IP地址可以同时绑定到多个网卡上E、同一个局域网上不同的PC机不能使用同一个IP地址答案：D,2-6在编程时（使用任一种高级语言
3、，不一定是Pascal），如果需要从磁盘文件中输入一个很大的二维数组（例如1000*1000的double型数组），按行读（即外层循环是关于行的）与按列读（即外层循环是关于列的）相比，在输入效率上（）。A.没有区别 B.按行读的方式要高一些 C.按列读的方式要高一些 D.取决于数组的存储方式。答案：D,2-7、如果pascal系统只允许变量使用64KB的内存，现在让你定义一个值为整型的一维数组，这个数组的下标为1.max，那么max最大可能的值为（）A.64 B.64000 C.32000 D.3276864KB=64*1024B整型占2个字节所以,max=64*1024/2答案选D,2-8、
4、数组A0.5,0.6的每个元素占5个单元，将其按列优先次序存储在起始地址为1000的连续的内存单元中，则元素A5，5的地址为（）A.1175 B.1180 C.1205 D.1210 E.1190分析：1、搞清楚列优先的含义2、A5，5前面有0,1,2,3,4共5列，每列有0.5共6个元素,第5列前面有0.4五个元素，共有5*6+5=353、地址：（5*6+5）*5+1000=1175,2-9、.在计算机中，防火墙的作用是（）。A、防止火灾蔓延 B、防止网络攻击 C、防止计算机死机 D、防止使用者误删除数据 答案选B,3、与奥赛活活动相关,noip初赛（10月中下旬）noip复赛（11月中下旬
5、）省队选拔赛（由各省自行组织）noi决赛（次年暑假）全国冬令营（次年年底）国家队选拔赛ctsc（次次年5月）国际比赛ioi（次次年910月）,3-1、在下列各软件中，不属于NOIP竞赛（复赛）推荐使用的语言环境有（）。A.gcc/g+B.Turbo Pascal C.RHIDE D.free pascal E、Lazarus答案选B,推荐的：pascal:free pascal、Lazarus c 及c+、Dev C+、gcc/g+、RHIDE不推荐的:TP7（turbo pascal 7）、TC（turbo C）、Visual C+,4、程序语言及算法基础,了解算法的五大特征：有穷性、确定性
6、、可行性、0或多个输入、有一个或多个输出要求掌握的排序有：冒泡法、插入排序、合并排序、快速排序理解每种排序的算法思想了解每种排序的时间复杂度及其稳定性,4-1、在下列关于计算机语言的说法中，不正确的是（）。A.Pascal和C都是编译执行的高级语言 B.高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上 C.C+是历史上的第一个支持面向对象的计算机语言 D.与汇编语言相比，高级语言程序更容易阅读答案选C,4-2、在下列关于计算机算法的说法中，不正确的是（）。A.一个正确的算法至少要有一个输入 B.算法的改进，在很大程度上推动了计算机科学与技术的进步 C.判断一个算法的好坏的主要标
7、准是算法的时间复杂性与空间复杂性 D.目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法答案选A,4-3、在下列各种排序算法中，不是以“比较”作为主要操作的算法是（）。A.选择排序 B.冒泡排序 C.插入排序 D.基数排序 1、基数排序是基于“分配”和“收集”的排序2、技巧：用排除法做，前3者都是通过比较来排序的。,4-4、某数列有1000个各不相同的单元,由低到高按序排列,现要对该数列进行二分法检索,在最坏的情况下,需要检索（）个单元。A.1000 B.10 C.100 D.500分析：二分法的检索次数为log21000+1答案：B,4-5、在Pascal语言中
8、，判断a不等于0且b不等于0的正确的条件表达式是（）A.not a=0 or not b=0 B.not（a=0）and（b=0）C.not（a=0 and b=0）D.（a0）and（b0）答案选D,4-6、将5个数的序列排序，不论原先的顺序如何，最少都可以通过（）次比较，完成从小到大的排序。A.6 B.7 C.8 D.9,分析,1、既然是追求最少比较次数，必定不会用n2的算法排序。2、排序本质可说是循环查找各个位置上数（1）用二分查找（2）总次数3227,4-7、下列序列中，（）是执行第一趟快速排序后得到的序列（排序的关键字类型是字符串）。A.da,ax,eb,de,bb ff ha,gc
9、B.cd,eb,ax,da ff ha,gc,bbC.gc,ax,eb,cd,bb ff da,haD.ax,bb,cd,da ff eb,gc,ha答案：A,4-8、递归算法的执行过程，一般来说，可先后分成递推和（）两个阶段。A.回溯B.回归C.返回D.合成 答案：B,5、位运算,位逻辑运算：（与）、（或）、Xor（异或）、（非）位移运算:shl（左移位）、shr（右移位）,1、（与）、（或）、（非）,运算：对应位都为1时为1，否则为0。如下：110111 001101-000101,运算：对应位只要有一个1就为1。110111 001101-111111,运算：对每个上的值按位求反：1变为
10、0；0变为1,2、Xor（异或）,1、Xor（异或）：对应位相同为“0”，不同为“1”10101 00111-10010,3、shl（左移）、shr（右移）,Shl n（左移位）:所有位向左移动n位（00001）2 shl 1=（00010）2（00101）2 shl 2=（10100）2 小结：二进制每左移一位相当于乘以一个2,Shr n（右移位）所有位向右移动n位（00010）2 shr 1=（00001）2（00100）2 shr 2=（00001）2 小结：二进制每右移一位相当于除以一个2,5-1、已知A=35H，则A 05H A 30H的结果是（）A、30H B、05H C、35H
11、D、53H E、00H分析：1、运算优于运算2、化为二进制后再做运算,5-2、在Pascal语言中，表达式（21 xor 2）的值是（）A.441 B.42 C.23 D.24 分析：10101（21）00010（2）-10111（23）,6、进制数的运算,十进制（0-9）二进制（0、1）、八进制（0-8）十六进制（0-9，A-F）掌握不同进制数之间的相互转换注意技巧，节省时间,1、十进制数 N进制数 方法：除N取余倒序法2、N进制数 十进制数（带小数）方法：整数部分：kNi求和法 小数部分：小数部分*N取整3、十六进制数与二进制数间的关系每位十六进制数相当于4位二进制数如（215）16=（0
12、01000010101）24、八进制数与二进制数间的关系每位八进制位相当于3位二进制数如（215）8=（010001101）2,例1：将（1011010.10）2转换成八进制和十六进制数 001 011 010.100（1011010.10）2=（132.4）8 1 3 2.40101 1010.1000（1011010.10）2=（5A.8）16 5 A.8例2、将十六进制数F7.28变为二进制数F 7.2 8（F7.28）16=（11110111.00101）21111 0111.0010 1000 例3、将八进制数25.63转换为二进制数2 5 6 3（25.63）8（10101.110
13、011）2 10 101.110 011,6-1 与十进制数1770 对应的八进制数是（）。A.3350 B.3351 C.3352 D.3540技巧：只需口算最低位的数字即可,6-2、（2010）16+（32）8的结果是（）。A.（8234）10 B.（202B）16 C.（20056）8 D.（100000000110）2,7、数据结构知识,一、线性结构：串、栈、队二、非线性结构：树、图,栈与队,栈特点：先进后出（FILO、LIFO）队特点：先进先出（FIFO、LILO）注意：有些题中还规定了栈或队的空间,二叉树,树：普通二叉树、满二叉树、完全二叉树二叉树的特点：1、第i层的结点最多为2i
14、-1（i=1）个结点，深度为K（K=1）的二叉树最多有2k-1个结点。2、在二叉树中，如果其叶子结点数为n0，则其度为2的结点数为n2=n0-1。完全二叉树的特点：1、树叶只可能在层次最大的两层上出现。2、对任一结点，左子树的深度或者比右子树的深度多1，或者与右子树深度相等。3、具有n个结点的完全二叉树的深度为K=log2n+1,二叉树的遍历,前序遍历（DLR）根左子树右子树中序遍历（LDR）左子树根右子树后序遍历（LRD）左子树右子树根已知前序遍历（或后序遍历）和中序遍历，就能唯一确定其他一种遍历已知前序遍历和后序遍历，不能唯一确定中序遍历,图,图的遍历：从图中某一顶点出发访问图中其余的顶点
15、，使每个顶点都被访问且仅访问一次。深度优先搜索（DFS）广度优先搜索（BFS）,7-1、某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出”。假设车辆入站的顺序为1，2，3，则车辆出站的顺序为（）。A.1,2,3,4,5 B.1,2,4,5,7 C.1,4,3,7,6 D.1,4,3,7,2,7-2、下列叙述中，正确的是（）A.线性表的线性存贮结构优于链表存贮结构B.队列的操作方式是先进后出C.栈的操作方式是先进先出D.二维数组是指它的每个数据元素为一个线性表的线性表,7-3、一棵二叉
16、树的中序遍历序列为：DGBAECHF，后序遍历序列为：GDBEHFCA，则前序遍历的序列是（）。A.ABCDFGHEB.ABDGCEFHC.ACBGDHEFD.ACEFHBGD答案：B,7-4、在有N个叶子节点的哈夫曼树中，其节点总数为（）A.不确定 B.2N-1 C.2N+1 D.2N,1、在哈夫曼树（也叫最优树）中，只有两种类型的结点：度为0或N，即最优二叉树中只有度为0或2的结点，最优三叉树中只有度为0或3的结点,2、在二叉树中，叶子总比度为2的结点大1，即N=N2+1，又因为没有度为1的结点，所以总结点数为N+N2=N+N-1=2N-1,7-5、高度为n的均衡的二叉树是指：如果去掉叶结
17、点及相应的树枝，它应该是高度为n-1的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为0，如果某个均衡的二叉树共有2381个结点，则该树的树高为（）。A.10 B.11 C.12 D.13,注：此题规定根结点的深度为0,1、满二叉树指的是：对于第i层，节点数必定是2i。2、有i层的满二叉树的节点总数为2（i+1）-13、假定均衡树的层数为x，那么该均衡树对应的满二叉树（比均衡树小1层）节点数为2x-1,则必定有：2x-123812（x+1）-1X=11。,7-6、设栈S的初始状态为空，元素a,b,c,d,e 依次入栈，以下出栈序列不可能出现的有（）。A.a,b,c,e,d B.b,c
18、,a,e,d C.a,e,c,b,d D.d,c,e,b,a,7-7、已知6个结点的二叉树的先根遍历是1 2 3 4 5 6（数字为结点的编号，以下同），后根遍历是3 2 5 6 4 1，则该二叉树的可能的中根遍历是（）A.3 2 1 4 6 5 B.3 2 1 5 4 6 C.2 1 3 5 4 6 D.2 3 1 4 6 5 分析：可根据前根遍历和中根遍历，求出后根遍历，再看求出的后序遍历是否与题目中给出的相同,7-8、将一棵有100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点进行编号，根结点的编号1，则编号为49的结点的左孩子编号为（）A.98 B.99 C.50 D.48
19、分析：对于完全二叉树中编号为i的结点，它的左儿子编号为2i，右儿子编号为2i+1答案：A,7-9、为了保证一个有n（n=3）个顶点的无向图是连通的，这个图至少要有（）条边A.（n-1）*（n-2）/2+1B.n*（n-1）/2-（n+2）C.（n-2）*（n-1）/2D.（n/2+1）*（n-1）答案：A,7-10、下列有关树的叙述中,叙述正确的是（）A、在含有n个结点的树中，边数只能是n-1条B、在哈夫曼树中，外部结点的个数比内部结点个数多1C、完全二叉树一定是平衡二叉树D、在二叉树的前序遍序列中，若结点U在结点V之前，则U一定是V的祖先E、在查找树中插入一个新结点，总是插入到叶结点下面分析
20、：1、前序遍历是根左右，显然D是错误的2、插入结点可以插在一个只有一个儿子的结点下方,7-11、以下数据结构中哪些不是线性结构?A、有向图 B、栈 C、二叉树D、B树 E、队列,8、离散数学,排列组合数理逻辑,8-1、设A=B=D=true，C=false，以下逻辑运算表达式值为真（假）的有（）。A.（AB）（CD）B.（ABD）C）C.A（BCD）D.（ABC）D,总结,1、进制转换是必考的（二、八、十六进制）2、堆栈是必考的,可关注队列的操作3、二叉树性质、遍历必考的4、微机原理必考的（CPU、ROM等）5、排序算法的分析，概率较大6、新动向：和信息学奥赛的知识7、信息安全，概率较大8、网
21、络有关知识，今年估计会出现,问题求解,1、数据结构（树、图）2、算法设计（构造类算法）3、数学知识（初中不多，高中较多）,1（寻找假币）现有80枚硬币，其中有一枚是假币，其重量稍轻，所有真币的重量都相同，如果使用不带砝码的天平称重，最少需要称几次，就可以找出假币？你还要指出第1次的称重方法。请写出你的结果：_。,题1考察算法：分治法,1、该题的原型是用“二分法”编程求解。二分法至少需要log（80）次，大约是7。2、二分法的优越在于每次判断时可以排除一半。进一步思考是否分成的部分越多，每次判断可以排除的数量越多？3、平均分成3份来判断，每次可以排除2/3数量。（思考分成更多份是否效果更好？）,
22、具体算法,1、平均分成3份，如果不能被3整除，那么尽量让两份相同并且相同的两分应该比其他一份大1（每次判断可以排除更多的数量）2、每次称相同的两份。直到最后相同的两分是1。,实例,27，27，26,9，9，9,1，1，1,3，3，3,9，9，8,1，1，1,3，3，2,1，1,2（取石子游戏）现有5堆石子,石子数依次为3，5，7，19，50，甲乙两人轮流从任一堆中任取（每次只能取自一堆，不能不取）,取最后一颗石子的一方获胜。甲先取，问甲有没有获胜策略（即无论乙怎样取，甲只要不失误，都能获胜）？如果有，甲第一步应该在哪一堆里取多少？,题2：xor操作,1、异或结果非0，必胜，否则必输。2、根据下
23、面列式，只要让50对应的最高位1去掉，xor结果就是0，而这个最高位的1对应是32。000011（3）000101（5）000111（7）010011（19）110010（50）,3、10名划船运动员中，3人只会划左舷，2人只会划右舷，5人左右舷都会划，从中选6人，平均分在左、右舷，共有多少种不同的选法？,题3：组合问题,采用穷举划左舷的所有情况进行分析1、会划左舷的全划左舷。左舷一共只有1种，右舷为7选3，方法共有：C（3，3）*C（7，3）=352、派一个全能的划左舷,共有方法:C（5，1）*C（3，2）*C（6，3）=5*3*20=3003、派二个全能的划左舷,共有方法:C（5，2）*C
24、（3，1）*C（5，3）=10*3*10=3004、派三个全能的划左舷,共有方法:C（5，3）*C（3，3）*C（4，3）=10*1*4=40因此，方法数共有：35+300+300+40=675,4、设树T有17条边，12片树叶，4个4度内部结点，1个3度内部结点。求T的树根的度数。注意：本题中度数定义均为图的度数定义。,题4：数据结构题,图中结点的度指的是什么？如何计算？是指结点的出度和入度。度=出度+入度已知17条边，可知结点为18个。设根的度为X，则所有结点的度之和为：x+4*4+3*1+12度与边有关系吗？显然，总度数应是边的两倍，即 x+4*4+3*1+12=17*2=x=3,5、光
25、明中学开设数学、英语和信息学三个兴趣学习小组，其中数学小组30人，英语小组15人，信息学小组18人，参加三个小组总人数为50人，其中有3人同时参加3个小组，那么同时只参加两个小组的同学有多少人?,3,X,Y,Z,题5：集合问题,分析：1、将题目转化为左图所示2、x+y+z即为只参加两个小组的同学3、30+15+18-2*3-（X+Y+Z）=50=x+y+z=7,6、十位数abcdefghij，其中不同的字母表示不同的数字。a是1的倍数，两位数ab是2的倍数，三位数abc是3的倍数，四位数abcd是4的倍数，,十位数abcdefghij是10的倍数，则这个十位数是_。,分析,第一步：j为0；（十
26、位数abcdefghij是10的倍数）第二步：e为5；（五位数abcde是5的倍数，但e可能为0或5，但0已被j占用）第三步：a、c、g、i为奇数，b、d、f、h为偶数；（余下2、4、6、8的倍数尾数为偶数）第四步：试八位数abcdefgh是8的倍数 fgh可为216、296、416、432、472、496、632、672、816、832、872、896，h可为2或6；第五步：试六位数abcdef是6的倍数def可为258、456、654、852；,第六步：合以上第四、五步，defgh可为25816、25896、45632、45672、65432、65472、85216、85296；第七步：合
27、四位数abcd是4的倍数及第三、六步结果，defgh可为25816、25896、65432、65472；第八步：合两位数ab是2的倍数，三位数abc是3的倍数及第七步结果，abcdefgh可为14725896、74125896、18965432、78965432、98165432、98765432、18365472、18965472、38165472、98165472；第九步：合七位数abcdefg是7的倍数及第八步结果，abcdefgh可为38165472；即得出全十位数为3816547290即得出全十位数为3816547290,7、银条 一位银矿勘探员无力预付3月份的房租。他有一根长31英
28、寸的纯银条，因此他和女房东达成如下协议。他说，他将把银条切成小段。3月份的第一天，他给女房东1英寸长的一段，然后每天给她增加1英寸，以此作为抵押。勘探员预期到3月份的最后一天，他能全数付清租金，而届时女房东将把银条小段全部还给他。3月份有31天，一种办法是把银条切成31段，每段长1英寸。可是这处花很多功夫。勘探员希望既履行协议，又能使银条的分段数目尽量减少。例如，他可以第一天给女房东1英寸的一段，第二天再给1英寸的一段，第三开他取回这两段1英寸的而给她3英寸的一段。假设银条的各段是按照这种方式来回倒换的话，勘探员至少需要把他的银条切成_段？,31/2=15.5 即只要用最少的数组成1至15的所
29、有组合就行了,因为16至31都可以通过前面的数与16来组成,得到必有数值16 16/2=8 同理，只要用最少的数组成1至8的所有组合就可以了,因为9-15都可以通过前面的数与8来组成,得到必有数值8 同理可得，8/2=4 4/2=2 又因为1也是必有数值,所以银条最少的组合为5，分别是：1,2,4,8,16,9、在圆周上有N个点（N=6），在任意两个点之间连一条弦，假设任何3条弦在圆的内部都没有公共点，问这些弦彼此相交能在圆内构成多少个三角形（只要求写出三角形总数的表示式而无需化简）？_C（N,3）+4*C（N,4）+5*C（N,5）+6*C（N,6）,10、如果一棵m度树中有n1个度为1的结点，n2个度为2的结点，有nm个度为m的结点，则该树中叶结点的的个数=_n2+2n3+（m-1）nm+1,
