noip2016备战初赛

1、LOGO备战初赛(2016NOIP)1 初赛内容及分值分布初赛：初赛全部为笔试，满分100分。试题由四部分组成： 1、选择题：共20题，每题1.5分，共计30分。(普及组全为单选题;提高组10个单选，10个不定项选择)2、问题求解题：共2题，每题5分,共计10分 3、程序阅读理解题:共4题，每题8分,共计32分。 4、程序完善题：共2题，每题14分，共计28分。2 选择题知识范围计算机基本常识： IT文化、微机原理信息安全、基本应用与奥赛活动有关的知识程序语言及算法基础数据结构(串、栈、队、树、图)离散数学：排列组合、数理逻辑5、离散数学什么是逻辑运算逻辑运算用来判断一件事情是“对”的还是“错

2、”的，或者说是“成立”还是“不成立”，判断的结果是二值的。 逻辑运算基本逻辑运算1.“与”运算(AND) “与”运算又称逻辑乘，用符号“ ”、“ ”或者 “and ”来表示。运算规则如下： 0 0 = 0 0 1 = 0 1 0 = 0 1 1 = 1 即当两个参与运算的数中有一个数为0，则运算结果为0；若都为1，则结果为1。练习11001与11011的逻辑与运算结果是? 2.“或”运算(OR) “或”运算又称逻辑加，用符号“+ ”、“”或者“or”表示。运算规则如下: 00 = 0 01 = 1 10 = 1 11 = 1 即当两个参与运算的数中有一个数为1，则运算结果为1；若都为0，则结果

3、为0 。练习11001与11011的逻辑或运算结果是? 3.“非”运算(NOT) 如果变量为A，则它的非运算结果用 A 表示。其运算符号为其运算符号为“-”，有时也用，有时也用“”或或“not”表示表示 运算规则如下: 0=11=0 练习11001逻辑非运算结果是?4.“异或”运算(XOR) “异或”运算用符号“-”或者“xor ”来表示。其运算规则如下: - 00 = 0 - 01 = 1 - 10 = 1 - 11 = 0 即当两个参与运算的数取值相异时，运算结果为1，否则为0. 练习11001与11011的逻辑异或运算结果是?逻辑运算练习10111001=100010 101001=-1

4、1101 11010=10101=小结:逻辑常量运算与运算或运算非运算异或运算0 0=00 1=01 0=01 1=10+0=00+1=11+0=01+1=1_1 = 0_0= 1- 00 = 0 - 01 = 1- 10 = 1- 11 = 0 基本概念把分散的人或事物聚集到一起叫做集合。其中各事物叫做集合的元素。例如：26个英文字母的集合。空集是不含任何元素的集合。 集合集合的基本运算有并、交、补、减等。 集合的运算假设有集合A=a,b,c，B=c,d，C=b并运算：AB=a,b,c,d， BC=b,c,dAC=a,b,c并集：以属于A或属于B的元素为元素的集合称为A与B的并（集），记作A

5、B（或BA），读作“A并B”（或“B并A”）即AB=x|xA,或xB。练习有两个集合 A=2,3 、B=2,3,5,7 ， ，请请问问AB=？有三个集合 A=1,3 、B=2,3,5,7 ， ，B=3,5，请问请问AB=？， AC=？， CB=？假设有集合A=a,b,c，B=c,d，C=b交运算：AB=c， AC=bAC=b交集： 以属于A且属于B的元素为元素的集合称为A与B的交（集），记作AB（或BA），读作“A交B”（或“B交A”），即AB=x|xA,且xB练习有两个集合 A=2,3 、B=2,3,5,7 ， ，请问请问A B=？有三个集合 A=1,3 、B=2,3,5,7 ， ，B=3,

6、5，请问请问A B=？， A C=？， C B=？7、数据结构数据结构是计算机存储、组织数据的方式。数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。需要掌握的数据结构形式：一维数组、堆栈、二叉树栈是一种数据结构，它按照先进后出的原则存储数据。栈栈的示意图计算原则：先进入的数据被压入栈底，最后的数据在栈顶。需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈的示意图栈顶栈底进栈有集合A=a1，a2，a3，a4，a5，按照a1至a5的顺序进栈。栈顶栈底栈a1a2a3a4a5进栈(Push)出栈顺序：栈顶栈底栈a1a2a3a4a5 出栈(Pop)规则：

7、先进后出，后进先出！ 有有XYZ三个元素依次入栈三个元素依次入栈,不可能的出栈不可能的出栈顺序是顺序是?()A:ZYXB:ZXYC:YXZD:XYZ为什么为什么?设栈设栈S和队列和队列Q的初始状态为空，元素的初始状态为空，元素a1、a2、a3、a4、a5、a6依次通过栈依次通过栈S，一个元素出栈后即进入队列，一个元素出栈后即进入队列Q，若，若6个元素出队的序列是个元素出队的序列是a2、a4、a3、a6、a5、a1，则栈，则栈S的容量至少有的容量至少有（）。）。A.2B.3C.4D.5E.6一个栈的入栈序列是一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是则栈的不可能的输出序列是A

8、3，5，4，2，1B3，2，4，5，1C1，2，3，4，5D5，4，3，1，2若让元素若让元素1,2,3依次进栈，若元素可随依次进栈，若元素可随时出栈，则下列出栈次序不可能出现时出栈，则下列出栈次序不可能出现的是（的是（）。）。A.3,2,1B.2,1,3C.3,1,2D.1,3,2栈底至栈顶依次存放元素 ABCD,第五个元素入栈前,栈中元素可以出栈,则出栈的序列可能是_ A. ABCED B. DBCEA C. CDABE D. DCBEA 树：是一种重要的非线性数据结构，它是由n（n=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，

9、而叶朝下的。 二叉树必有一个特定的称为根(ROOT)的结点；剩下的结点被分成=0个互不相交的集合T1、T2、.Tn，而且， 这些集合的每一个又都是树。树T1、T2、.Tn被称作根的子树(Subtree)。根T1T2T3（某一个结点）的（儿子结点）的个数称为该结点的度。一棵树的度是指该树中结点的最大度数。例如在图中，结点A，B和E的度分别为3，2，0，树的度为3。 在一棵树中，度为零的结点称为叶结点或终端结点。图中，E，I，J，C，G，H均为叶结点。 从树根到任一结点n有唯一的一条路径，我们称这条路径的长度为结点的深度或层数。例如，在图中，结点A的深度为0；结点B，C和D的深度为1；结点E，F，

10、G，H的深度为2；结点I和J的深度为3。二叉树 (binary tree) 是另一种树型结构特点：每个结点至多只有二棵子树 (即二叉树中不存在度大于2的结点 )，并且，二叉树的子树有左右之分，其次序不能任意颠倒 。逻辑上二叉树有五种基本形态 ：(1)空二叉树(a)；(2)只有一个根结点的二叉树(b)；(3)右子树为空的二叉树(c)；(4)左子树为空的二叉树(d)；(5)完全二叉树(e) (a)(b)(c)(d)(e)二叉树的性质（1）在二叉树中，第i层的结点最多有2i-1个； 例：二叉树中，第3层最多有23-1=22=4个123456i=1i=2i=357（2）深度为h的二叉树最多有2h-1个

11、结点(h=1)，最少有h个结点； 12345657h=3，最多有（23-1）个结点，最少有3个结点（3）在任意二叉树中，如果叶子数为n0，度为2的结点数为n2，则n0=n2+1; 证明证明:设设n1为二叉树为二叉树T中度为中度为1的结点数。的结点数。二叉树中所有结点的度均小于或等于二叉树中所有结点的度均小于或等于2n=n0+n1+n2(1)设设B为分支总数，则为分支总数，则n=B+1这些分支是由度为这些分支是由度为1或或2的结点射出的的结点射出的B=n1+2n2n=n1+2n2+1(2)由式由式(1)和和(2)得得n0=n2+1 二叉树的特殊形态满二叉树12345 67一棵深度为k，而且有2k

12、-1个结点的二叉树，称为满二叉树12345满二叉树非满二叉树完全二叉树二叉树的特殊形态123456当每一个结点都与深度为k的满二叉树中编号的结点一 一对应时，称为完全二叉树一个深度为k的二叉树，如果k-1层为满二叉数且第k层结点按从左至右的顺序满插入的话，这棵树称为完全二叉树。二叉树的遍历所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。 设L、D、R分别表示遍历左子树、访问根结点和遍历右子树， 则对一棵二叉树的遍历有三种情况：DLR（根左右，称为先序遍历）LDR（左根右，称为中序遍历）LRD（左右根，称为后序遍历）(1)先序遍历（以根结点

13、为参照）访问根结点；先序遍历左子树；先序遍历右子树(2)中序遍历（以根结点为参照）中序遍历左子树；访问根结点；中序遍历右子树(3)后序遍历（以根结点为参照）后序遍历左子树；后序遍历右子树；访问根结点遍历二叉树先序遍历上图所示的二叉树时，得到的先序序列为：A B D C E F中序遍历上图所示的二叉树时，得到的中序序列为： D B A E C F 后序遍历上图所示的二叉树时，得到的后序序列为：D B E F C A由二叉树的前序序列和中序序列建立该二叉树 1.用前序序列的第一个结点作为根结点;2.在中序序列中查找根结点的位置，并以此为界将中序序列划分为左、右两个序列(左、右子树);3.根据左、右

14、子树的中序序列中的结点个数，将前序序列去掉根结点后的序列划分为左、右两个序列，它们分别是左、右子树的前序序列;4.对左、右子树的前序序列和中序序列递归地实施同样方法，直到所得左、右子树为空。假设前序序列为ABDGHCEFI， 中序序列为GDHBAECIF，则得到的二叉树如下所示 1。 。A为为根根结结点点A BDGH CEFI GDHB A ECIF 2.B为为左子左子树树的根的根结结点点B DGHGDH B 3.D为为左子左子树树的左子的左子树树的根的根结结点点 4.C为为右子右子树树的根的根结结点点C E FIE C IF 5.F为为右子右子树树的右子的右子树树的根的根结结点点 表达式二叉

15、树-+/a*eb-cdf请写出该二叉树对应的表达式!前缀表达式(波兰式):-+a*b-cd/ef中缀表达式:a+b*c-d-e/f后缀表达式(逆波兰式):abcd-*+ef/-基本算法 什么是算法?算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。算法常常含有重复的步骤和一些比较或逻辑判断。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。算法排序算法查找算法回溯算法排序排序(Sorting)是计算机程序设计中的一种重要操作

16、，其功能是对一个数据元素集合或序列重新排列成一个按数据元素某个项值有序的序列。以比较为基础的排序算法的基本操作 大多数排序算法都有两个基本的操作：(1) 比较两个关键字的大小；(2) 改变指向记录的游标或移动记录本身。需要学习的排序算法： 冒泡排序、直接插入排序、归并排序、快速排序冒泡排序（借助“交换”进行排序）基本思想： 两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。排序方法： 依次比较相邻的两个数，将大数放在前面，小数放在后面。 即首先比较第1个和第2个数，将大数放前，小数放后。然后比较第2个数和第3个数，将大数放前，小数放后，如此继续，直至比较最

17、后两个数，将大数放前，小数放后，此时第一趟结束，在最后的数必是所有数中的最小数。 重复以上过程，仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再大于第2个数），将大数放前，小数放后，一直比较到最小数前的一对相邻数，将大数放前，小数放后，第二趟结束，在倒数第二个数中得到一个新的最小数。如此下去，直至最终完成排序。示例对序列2,38,65,13,27 排序382651327386521327386513227第一趟排序，结果：选出最小的数386513272第二趟排序，结果：选出第二小的数653813272653813272653827132第三趟排序，结果：选出第三小的

18、数653827132653827132第四趟排序，结果：选出第四小的数653827132【效率分析】空间效率：仅用了一个辅助交换单元。时间效率：总共要进行n-1趟冒泡，对n个记录的表进行一趟冒泡需要n-1次数值大小比较。移动次数：最好情况下，待排序列已有序，不需移动。冒泡排序最好的时间复杂度为O(n)。冒泡排序的最坏时间复杂度为O(n2)。冒泡排序的平均时间复杂度为O(n2)。冒泡排序是就地排序，且它是稳定的。 平均时间性能比直接插入排序要差得多。 直接插入排序基本思想： 依次将每个记录插入到一个有序中去。就是说，第i遍整理时，A1,A2,.,Ai-1已经是排好序的子序列；取出第i个元素Ai,

19、在已排好序的子序列为Ai找到一个合适的位置，并将它插到该位置上。易知上述排序当i=1时实际上为空操作，故可直接从i=2开始。 排序方法： 每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当位置，直到全部记录插入完毕为止。示例对序列49,38,65,13,27排序 演示初始: 49 38 65 13 27第一次 38 49 65 13 27第二次 38 49 65 13 27第三次 13 38 49 65 27第四次 13 27 38 49 65【效率分析】空间效率：仅用了一个辅助单元。时间效率：向有序表中逐个插入记录的操作，进行了n-1趟，每趟操作分为比较关键码和移动记录，而

20、比较的次数和移动记录的次数取决于待排序列按关键码的初始排列。直接插入排序的时间复杂度为O(n2)。是一个稳定的排序方法。归并排序基本思想： 将两个或两个以上的有序(大小关系)序列组合成一个新的有序序列。排序步骤：1、将序列每相邻两个数字进行归并操作，形成n / 2个序列，排序后每个序列包含两个元素 。2、将上述序列再次归并，形成n / 4个序列，每个序列包含四个元素。 3、重复步骤2，直到所有元素排序完毕。示例对序列49,38,65,97,76,13,27排序 演示初始 49,38,65,97,76,13,27一趟归并：38,49,65,97,13,76,27二趟归并：38,49,65,97,

21、13,27,76三趟归并：13,27,38,49,65,76,97各种排序的讨论简单排序中插入排序最好，当序列为正序时，直接插入和冒泡均最佳。排序方法平均时间稳定性冒泡排序、直接插入排序 O(n2) 稳定归并排序 O(nlgn) 稳定不同条件下，排序方法的选择 ：1)若n较小(如n50)，可采用直接插入或直接选择排序。(2)若序列初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；(3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：归并排序。练习具有具有12个个记录记录的序列，采用冒泡排序的序列，采用冒泡排序最少的比最少的比较较次数是次数是()A 1B 144C

22、11D 66 下列关于排序的说法不正确的是（ ）。A.直接插入排序和冒泡排序都是稳定的排序算法。B.直接插入排序的平均时间复杂度为O(n2)。C. 归并排序的平均时间复杂度是O(nlog2n)。数组 在程序设计中，为了处理方便， 把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组。 在语言中， 一个数组可以分解为多个数组元素，这些数组元素可以是基本数据类型或是构造类型。因此按数组元素的类型不同，数组又可分为数值型数组（例如int）、字符数组（例如char）、指针数组、结构数组等各种类别。 在语言中使用数组必须先进行类型说明，和使用变量相同！ 数组说明的一般形

23、式为： 类型说明符 数组名 常量表达式，；例如：int n 999，char c23一、定义数组类型说明符是任一种基本数据类型;数组名是用户定义的数组标识符; 方括号中的常量表达式表示数据元素的个数，也称为数组的长度。 char c23int a10; 说明整型数组a，有10个元素。float b10,c20; 说明实型数组b，有10个元素，实型数组c，有20个元素。char ch20; 说明字符数组ch，有20个元素。 思考：1、同一个数组，其所有元素的数据类型都是相同的吗？2、数组名的书写规则有什么要求 ？ A5; 93; b+56; *_8答：数组名的书写规则应符合标识符的书写规定。3、

24、数组名是否能与其它变量名相同？例如：有一段程序，定义了整形变量a,实型数组a，这样的定义对吗？void main()int a;float a10;记住：在你的程序里一定不要出现数组名和变量名相同的情况！4、数组元素的个数怎么数？方括号中常量表达式表示数组元素的个数，如a5表示数组a有5个元素。但是其下标从0开始计算。因此5个元素分别为a0,a1,a2,a3,a4。千万注意，数组的第一个元素下标从0开始！ 5.申明数组的时候不能在方括号中用变量来表示元素的个数，必须是符号常数或常量表达式！调用数组元素的时候，方括号内可以使用变量！ void main()int n=5;int an;错误 in

25、t offset5+3;float count5*2+3;正确main()inti,n10;for(i=0;i=0;i-)printf(%d,ni);printf(n);正确6、允许在同一个类型说明中，说明多个数组和多个变量。例如： int a,b,c,d,k110,k220; 请正确使用下标访问数组元素 例如，定义数组：int num10;表明该数组是一维数组，里面有10个数，它们分别为num 0, num1,num 9； 二、访问数组int main() int a5，i; i = 0; if (i 5) ai = 9; Else printf(“%d”, a0);Return 0;读程序

26、，a0的值是多少？三、数组的初始化在定义数组时，可以用放在一对大括号中的初始化表对其进行初始化。初始化值的个数可以和数组元素个数一样多。形式：类型说明符 数组名常量表达式=值，值值； 例如：int array5=1,2,3,4,5; float fl3=1.2,2.4,6.5;读程序，写结果int main() int a5 = 1,2,3,4,5； int i = 0; printf(“%dn”, a0); i +; printf(“%dn”, ai); i +; printf(“%dn”, ai); i +; printf(“%dn”, ai);Return 0;int main() in

27、t a5 = 1,2,3,4,5； int i = 0; ai = a0+a1+a3; i +; ai = a2+a4; i +; printf(“%d,%dn”, i, ai); Return 0;读程序，写结果int main() int a5 = 1,2,3,4,5； int i = 4; ai = a0+a1+a3; i -; ai = a2+a4; i -; printf(“%d,%dn”, i, ai); Return 0;读程序，写结果数组初始化的几点说明: 1. 可以只给部分元素赋初值。当 中值的个数少于元素个数时，只给前面部分元素赋值。 读程序，写结果intmain()int

28、a5=1,2；inti=0;i+;ai=a0+a1;i+;ai=a1+a2;i+;ai=a2+a3;printf(“%dn”,ai);Return0;2.只能给元素逐个赋值，不能给数组整体赋值。 例如给十个元素全部赋1值：int a10=1,1,1,1,1,1,1,1,1,1; int a10=1;3.如不给可初始化的数组赋初值，则各元素的值为一个随机的数。 intmain()inta5；inti=0;i+;ai=a0+a1;i+;ai=a1+a2;printf(“%dn”,ai);return0;4.如给全部元素赋值，则在数组说明中， 可以不给出数组元素的个数。intmain()inta=1

29、，3，5；inti=0;i+;ai=a0+a1;i+;ai=a1+a2;printf(“%dn”,ai);return0;上机练习初始化一个含有4个整型元素的数组，再求这四个数的和，平均值。四个数为：6545，35416，157，874循环(while，for)练习#includeintmain()intn,sum;sum=0;for(n=1;n=5;n+)sum+=n;printf(“sum=%dn,sum); 结果：sum=?#includeintmain()inti=1,sum=0;while(i10)sum+=i;i+;printf(“sum=%dn,sum); 结果：sum=?#in

30、cludeintmain()inti=0,sum=0;while(i10)sum+=i;i+=2;printf(“sum=%dn,sum);结果：sum=?上机练习，请你用while循环求10以内的奇数和。找出所有的“水仙花数”。水仙花数的特点：它是一个3位数，其各位数字立方和等于该数。例如：153 = 13+53+33#include#includeintmain()inti,a,b;/定定义义三个整型三个整型变变量量intf3;/定定义义一个含有三个元素的数一个含有三个元素的数组组for(i=0;i3;i+)/设设置置i3，循，循环环三次三次scanf(“%d”,&fi);/获获取

31、从取从键盘输键盘输入的三个整数入的三个整数a=f0+f1+f2;/把数把数组组的和附的和附值给变值给变量量ab=f0+f2;/把把f0+f2的和附值给变量的和附值给变量bprintf(“%dn”,a+b);/输输出出a+b的的值值return0;输入：输入：123输出：输出：_ #include#includeintmain()inti,a,b;/定义三个整型变量定义三个整型变量intf3;/定义一个含有三个元素的数组定义一个含有三个元素的数组for(i=0;i3;i+)/设置设置i3，循环三次，循环三次scanf(“%d”,&fi);/获取从键盘输入的三个整数获取从键盘输入的三个整数

32、a=f0+f1+f2;/把数组的和附值给变量把数组的和附值给变量aa=a/f0;b=f0+f2;/把把f0+f2的和附值给变量的和附值给变量bb=b/a;printf(“%dn”,a+b);/输出输出a+b的值的值return0;输入：输入：123输出：输出：_ #include#includeintmain()inti,a,b;/定义三个整型变量定义三个整型变量intf3;/定义一个含有三个元素的数组定义一个含有三个元素的数组for(i=0;i3;i+)/设置设置ib)/判断判断a是否大于是否大于bprintf(“%dn”,a); /输出输出a的值的值elseprintf(“%dn”,b);

33、 /输出输出b的值的值return0;输入：输入：123输出：输出：_ 上机练习初始化一个有3个元素的数组，利用键盘输入的数赋值，计算他们的和与平均数，再输出结果。上机练习1、把5个从键盘输入的数,按逆序重新输出。例如,输入的顺序是:1 2 3 4 5输出的结果变为:5 4 3 2 1 For(.)Printf(“%d”,xxx);字符数组用来存放字符量的数组称为字符数组。用来存放字符量的数组称为字符数组。语言中没有专门的字符串变量，通常是用字符数组来存放字符串。字符数组的定义字符数组的定义形式与前面介绍的数值数组相同。形式与前面介绍的数值数组相同。例如：例如：charc10;可用字符常量或字

34、符串常量作为初值的形式对字符数组进行初始化。以下四种形式等价： char s7=H, e, l, l, o, !, 0; char s7=H, e, l, l, o ,!; /*不完全赋值，自动补0*/ char s7=Hello!; char s7= Hello!; 注意：用字符串常量会自动加结束符0，用字符常量则不会。字符数组初始化当对全体元素赋初值时也可以省去长度说明。例如：例如：charc=c,p,r,o,g,r,a,m;可写为：可写为：charc=Cprogram;或去掉或去掉写为：写为：charc=Cprogram;用字符串方式赋值比用字符逐个赋值用字符串方式赋值比用字符逐个赋值要

35、多占一个字节，用于存放字符串结要多占一个字节，用于存放字符串结束标志束标志0。上面的数组。上面的数组c在内存中的实在内存中的实际存放情况为：际存放情况为： 0是由是由C编译编译系系统统自自动动加上的。加上的。由于采由于采用了用了 0标标志，所以在用字符串志，所以在用字符串赋赋初初值值时时一般无一般无须须指定数指定数组组的的长长度，度，而由系而由系统统自行自行处处理。理。字符数组的引用字符数组的引用【 【例例7.8】 】main()intj;/定定义变义变量量jchara5=H,e,l,I,o;/定定义义并初始化并初始化数数组组for(j=0;j=4;j+)printf(“%c”,aj);/输输

36、出数出数组组元素，以字符的元素，以字符的格式格式输输出出printf(n);上机练习1、用用”emoclew”初始化字符数组，然后逆序输出为： welcome 。#includeintmain()inti;/定定义变义变量量ichara=.;/定定义义并初始化数并初始化数组组for(.)printf(.);/输输出数出数组组元素，以字符的格式元素，以字符的格式输输出出printf(n);return0;字符串的字符串的输输入和入和输输出出一、逐个输入和输出字符1. 用“%c”格式控制符。 例 1：字符串的输入和输出。 main ( ) /*限定有限的长度*/ char a16; /定义字符数组

37、 int i;for (i=0; i=15; i+) scanf (“%c”, &ai); /接受从键盘输入的字符 printf (n); for (i=0; i=15; i+) 运行结果： printf (%c, ai ); I am a student. I am a student.Iam a student0a0a1a2a3a4a5a6a7a8a9a10a11a12a13a14上机练习：编制程序，把从键盘输入的字符串截取，只保留前面5个字符，然后输出。例如：输入：I am a boy. 输入：Today is Thursday. 输出：I am 输出: Today#includ

38、eint main ( ) /*限定有限的长度*/ char a16; /定义字符数组 int i;for () scanf (); /接受从键盘输入的字符 printf (n); for () printf (); 1、IT文化重点考查：在IT领域中的杰出人物及重要事项范围较广，准备较困难关注IT界发展动态杰出人物及重大科技研究冯诺依曼（美国） 阿兰图灵（英国） 冯诺依曼 体系图灵奖 “图灵奖” ：专门奖励那些对计算机科学研究与推动计算机技术发展有卓越贡献的杰出科学家。 计算机发展史第一代第一代电子管电子管计算机（计算机（1946-19581946-1958） 第二代第二代晶体管晶体管计算机

39、计算机 （1959-19641959-1964）第三代第三代集成电路集成电路计算机计算机 （1965-19701965-1970）第四代第四代超大规模电路超大规模电路计算机计算机 （19711971至今）至今）第一台计算机的诞生！ 1946年2月，在美国宾夕法尼亚大学诞生了世界上第一台电子计算机ENIAC（Electronic Numerical Integrator And Computer），这台计算机占地170平方米，重30吨，用了18000多个电子管，每秒能进行5000次加法运算。 我国的计算机发展情况1983年每秒运行一亿次的银河巨型计算机在国防科技大学诞生；1992年研制成功每秒运

40、行10亿次的“银河”巨型计算机；1997年又研制成功每秒运行130亿次的“银河”巨型计算机；2002年9月28日 中科院计算所宣布中国第一个可以批量投产的通用CPU“龙芯1号”芯片研制成功。 2005年，“龙芯二号”正式亮相。2005年，联想完成并购IBM PC 。20092009年最值得期待年最值得期待7 7大大ITIT收购事件收购事件1 1、戴尔并购、戴尔并购EMCEMC 2 2、思科收购、思科收购VMwareVMware 3 3、IBMIBM收购收购Red HatRed Hat 4 4、微软收购、微软收购PalmPalm 5 5、谷歌收购、谷歌收购SkypeSkype 6 6、甲骨文收购

41、、甲骨文收购SS 7 7、苹果收购、苹果收购AdobeAdobe 2、计算机原理冯诺依曼 体系结构输入设备存储器输出设备运算器控制器控制流方向数据流方向程序数据处理结果冯诺依曼体系结构的基本思想：存储程序 程序控制特点：特点：(1) (1) 采用二进制形式表示数据和指令采用二进制形式表示数据和指令 (2)(2)计算机应该按照程序计算机应该按照程序顺序执行。顺序执行。 (3) (3) 由由运算器运算器、存储器存储器、控制器控制器、输输入设备入设备和和输出设备输出设备五大部件组成计算五大部件组成计算机系统，并规定了这五部分的基本功机系统，并规定了这五部分的基本功能。能。 中央处理器部分CPU (中

42、央处理器)控制器(CU)运算器(ALU)寄存器（cache)功能：执行定点或浮点的功能：执行定点或浮点的算术运算算术运算操作、移位操作以及逻辑操作，也操作、移位操作以及逻辑操作，也可执行地址的运算和转换可执行地址的运算和转换 。运算器(ALU)控制器(CU)功能：主要负责对指令译码，并且功能：主要负责对指令译码，并且发出为完成每条指令所要执行的各发出为完成每条指令所要执行的各个操作的控制信号。个操作的控制信号。 目前市场上常见的桌面计算机CPU：IntelIntel：酷睿：酷睿2 2处理器处理器 奔腾处理器奔腾处理器 赛扬处理器赛扬处理器 AMDAMD：羿龙处理器系列：羿龙处理器系列 （Ath

43、lonAthlon）速龙）速龙6464处理器处理器 （SempronSempron）闪龙处理器）闪龙处理器 CPUCPU的主要性能指标的主要性能指标接口类型：LGA 775 生产工艺：45纳米 主频：2.8GHz 二级缓存：L2 3072K 前端总线频率：1066MHz CPU的接口：针脚式接口，对应到主板上就有相应的插槽类型。常见：Socket LGA775 Socket LGA940 主频也叫时钟频率，用来表示CPU的运算速度。例如：Inter Core 2 Quad Q8200 主频：2.6GHz主频CPU缓存（Cache Memory）位于CPU与内存之间的临时存储器 。缓存对CPU的

44、性能影响很大，主要是因为CPU的数据交换顺序和CPU与缓存间的带宽引起的。 缓存字长字长字长：CPU在单位时间内(同一时间)能一次处理的二进制数的位数。目前桌面计算机的字长以32位为主，小型机、网络服务器和大中型机以64位为主。32位CPU：一次能处理32位，即4个字节的数据 64位CPU：一次能处理64位，即8个字节的数据 存储器内部存储器外部存储器内存储器只读存储器（ROM)随机存储器(RAM)特点：只能读，不能用普通方法写入，通常由厂家生产时写入，写入后数据不容易丢失，也可以用特殊方法（如紫外线擦除（EPROM)或电擦除(EEPROM_)存储器)。断电后信息不会丢失。只读存储器(ROM)

45、随机存储器(RAM)特点：可读可写，断电后内容全部丢失内存容量：为计算机系统配置的主存内存容量：为计算机系统配置的主存（RAMRAM）总字节数，是）总字节数，是CPUCPU可以直接访可以直接访问的存储空间。问的存储空间。目前，计算机的内存容量多为目前，计算机的内存容量多为1GB-4GB1GB-4GB。对于内存容量一般应指明装机对于内存容量一般应指明装机( (基本内基本内存存) )是多少，能否加以扩充，最大容量是多少，能否加以扩充，最大容量是多少是多少 。内存容量外存容量：以硬盘和光盘为主。目前，计算机的外存容量多为320GB-1TB。对于外存容量一般应根据需要配置。外部存储器外存储器磁性存储器

46、-硬盘光电存储器-光盘存储器的两个重要技术指标：存取速度和存储容量。存储器的存取速度：其他部件速度比较内存 硬盘 光盘CPU高速缓存内存硬盘U盘光盘软盘存储容量是指存储的信息量，它用字节存储容量是指存储的信息量，它用字节(Byte)(Byte)作为基本单位，缩写为作为基本单位，缩写为B B。容量换算关系：容量换算关系：1KB=1024B1KB=1024B 1MB=1024KB1MB=1024KB1GB=1024MB1GB=1024MB1TB= 1TB= ？GBGB 计算机存储信息的最小单位，称之为位（计算机存储信息的最小单位，称之为位（bit，又称比特又称比特） ，缩写为b，8b=1B计算机连

47、接各种设备外部设备的可能性、灵活性和适应性。外部设备输入设备鼠标键盘其他设备（手写板、扫描仪等）输出设备显示器打印机其他设备（绘图仪 、音箱等）硬件系统主机部分外部设备中央处理器内存储器运算器控制器随机存储器RAM只读存储器ROM输入设备输出设备辅助存储器鼠标 键盘 其他输入设备 显示器 打印机 其他输出设备 光盘 硬盘 其他辅助存储器 软件系统系统软件应用软件操作系统服务性程序数据库系统用户程序应用软件语言处理程序功能：对计算机硬件直接控制及管理的系统软件 如 Windows XP、 Windows 2003、Vista、Windows 7， Linux、Unix、Netware、Mac O

48、S等 操作系统机器的调试、故障检查和诊断程序等服务性程序如SQL Sever、Oracle、Foxpro、Access、Sybase等等 。数据库系统如C、C+语言、汇编程序、编译程序、解释程序等。 语言处理程序有OFFICE 系列、金山词霸、即时通讯软件、财务管理软件、游戏软件、CAD/CAM等 应用软件 计算机特点运算速度快运算精度高具有记忆和逻辑判断功能具有自动运行能力目前的微型计算机大约在百万次、千万次级；大型计算机在亿次，万亿次级。如我国“银河”为130亿次。在美国已运行1000亿，2000亿次的计算机，近年又出现了万亿次的计算机。 运算速度快一般在科学和工程计算课题中对精确度的要求

49、特别强烈。如，利用计算机可以计算出精确到小数200万位的值。 运算精度高计算机的逻辑判断能力是计算机智能化必备的基本条件。如果计算机不具备逻辑判断能力，也就不能称之为计算机了。 具有记忆和逻辑判断功能只要人预先把处理要求，处理步骤，处理对象等必备元素存储在计算机系统内，计算机启动工作后就可以不在人参与的条件下自动完成预定的全部处理任务。这是计算机区别于其它工具的本质特点。具有自动运行能力计算机的应用数值计算信息管理过程控制辅助工程网络应用人工智能例如：人造卫星轨道计算、天气预报、高能物理等等。 数值计算用于工农业生产计划的制定、科技资料的管理、财务管理、人事档案管理、火车调度管理、飞机订票等。

50、当前我国服务于信息处理的计算机约占整个计算机应用的左右，而有些国家达以上。 信息管理如用计算机控制发电，对锅炉水位、温度、压力等参数进行优化控制，可使锅炉内燃料充分燃烧，提高发电效率。同时计算机可完成超限报警，使锅炉安全运行。计算机的过程控制已广泛应用于大型电站、火箭发射、雷达跟踪、炼钢等各个方面。过程控制计算机辅助工程计算机辅助工程计算机辅助设计（） 计算机辅助制造（）计算机辅助教学计算机辅助教学（）（） 3、信息安全 计算机程序中，破坏计算机功计算机程序中，破坏计算机功能或者破坏数据，影响计算机使用并能或者破坏数据，影响计算机使用并且能够自我复制的计算机指令或者程且能够自我复制的计算机指令

51、或者程序代码。序代码。 计算机病毒（）寄生性（）寄生性 计算机病毒寄生在其他程序之中，当计算机病毒寄生在其他程序之中，当执行这个程序时，病毒就起破坏作用，执行这个程序时，病毒就起破坏作用，而在未启动这个程序之前，它是不易而在未启动这个程序之前，它是不易被人发觉的。被人发觉的。 计算机病毒特点（）传染性（）传染性计算机病毒不但本身具有破坏性，更计算机病毒不但本身具有破坏性，更有害的是具有传染性，一旦病毒被复有害的是具有传染性，一旦病毒被复制或产生变种，其速度之快令人难以制或产生变种，其速度之快令人难以预防。预防。 （）潜伏性（）潜伏性有些病毒像定时炸弹一样，让它什么有些病毒像定时炸弹一样，让它什

52、么时间发作是预先设计好的。时间发作是预先设计好的。 （）隐蔽性（）隐蔽性计算机病毒具有很强的隐蔽性，有的可以通计算机病毒具有很强的隐蔽性，有的可以通过病毒软件检查出来，有的根本就查不出来，过病毒软件检查出来，有的根本就查不出来，有的时隐时现、变化无常，这类病毒处理起有的时隐时现、变化无常，这类病毒处理起来通常很困难。来通常很困难。（5 5）破坏性）破坏性 计算机中毒后，可能会导致正常的程计算机中毒后，可能会导致正常的程序无法运行，把计算机内的文件删除序无法运行，把计算机内的文件删除或受到不同程度的损坏或受到不同程度的损坏 。通常表现为：。通常表现为：增、删、改、移。增、删、改、移。 可触发性可

53、触发性 病毒因某个事件或数值的出现，诱使病毒因某个事件或数值的出现，诱使病毒实施感染或进行攻击的特性称为病毒实施感染或进行攻击的特性称为可触发性。可触发性。 破坏文件或数据，造成用户数据丢失或毁损（熊猫烧香）；抢占系统网络资源，造成网络阻塞或系统瘫痪（arp病毒）；破坏操作系统等软件或计算机主板等硬件，造成计算机无法启动（CIH）。 计算机病毒危害（1 1） 机器不能正常启动机器不能正常启动 加电后机器根本不能启动，或者可以启动，加电后机器根本不能启动，或者可以启动，但所需要的时间比原来的启动时间变长了。但所需要的时间比原来的启动时间变长了。有时会突然出现黑屏现象。有时会突然出现黑屏现象。 （

54、2 2） 运行速度降低运行速度降低 如果发现在运行某个程序时，读取数据的时如果发现在运行某个程序时，读取数据的时间比原来长，存文件或调文件的时间都增加间比原来长，存文件或调文件的时间都增加了，那就可能是由于病毒造成的。了，那就可能是由于病毒造成的。 如何判断计算机病毒？（3） 磁盘空间迅速变小 由于病毒程序要进驻内存，而且又能繁殖，因此使内存空间变小甚至变为“0”，用户什么信息也进不去。 （4） 文件内容和长度有所改变 由于病毒的干扰，文件长度可能改变，文件内容也可能出现乱码。有时文件内容无法显示或显示后又消失了。 （5 5） 经常出现经常出现“死机死机”现象现象 如果机器经常死机，那可能是由

55、于系如果机器经常死机，那可能是由于系统被病毒感染了。统被病毒感染了。 （6 6） 外部设备工作异常外部设备工作异常 如果机器中有病毒，外部设备在工作如果机器中有病毒，外部设备在工作时可能会出现一些异常情况，出现一时可能会出现一些异常情况，出现一些用理论或经验说不清道不明的现象。些用理论或经验说不清道不明的现象。1 1、为操作系统的各种漏洞打上最新的补丁、为操作系统的各种漏洞打上最新的补丁2 2、安装防病毒产品并保证更新最新的病毒、安装防病毒产品并保证更新最新的病毒定义码。定义码。 3 3、不要从任何不可靠的渠道下载任何软件。、不要从任何不可靠的渠道下载任何软件。4 4、确保计算机对插入光盘、可

56、插拔介质（、确保计算机对插入光盘、可插拔介质（U U盘）、电子邮件和互联网文件都会做自动的盘）、电子邮件和互联网文件都会做自动的病毒检查。病毒检查。5 5、不去浏览不良站点。、不去浏览不良站点。防范计算机病毒！ 将多台地理位置不同的具有独立将多台地理位置不同的具有独立功能的计算机通过通信设备和传输介功能的计算机通过通信设备和传输介质互联，在网络操作系统管理和网络质互联，在网络操作系统管理和网络协议支持下进行网络资源共享及信息协议支持下进行网络资源共享及信息通信。通信。计算机网络1、 资源共享：（1） 共享硬件：大容量磁盘，打印机，绘图仪，扫描仪（可以节约资源，提高利用率）（2） 数据共享：减低

57、纸张和软盘传递量（3） 软件共享：网络会议等网络提供给我们的便利？2、 信息通信：（即传递数据)局域网互联网：传输文件，信息，电子商务等 。根据网络覆盖范围分：（1）局城网（LAN）：几米至几千米。所属为一个机房，单位等。（2）城城网（MAN）：几千米至几十千米。所属为一个城市。（3）广城网（WAN）：几十千米以上。其所属为城市与城市，省和省，国家与国家之间。（Internet）学会划分网络根据网络拓扑结构分：总线型拓扑结构 环型拓扑结构 网状拓扑结构 星型拓扑结构 网络传输介质：同轴电缆双绞线光纤卫星网络通信协议 网络中计算机与计算机之间的通信依靠协议进行。协议是计算机收、发数据的规则。网络

58、常见协议 TCP/IPTCP/IPTCP/IP协议是协议是InternetInternet网中进行通信的标准网中进行通信的标准协议协议! !它是由两个协议它是由两个协议“传输控制协议传输控制协议”(TCP)(TCP)和和“互联网协议互联网协议”(IP)(IP)组成，由于这两个协议组成，由于这两个协议通常连接在一起使用，因此叫做通常连接在一起使用，因此叫做TCP/IPTCP/IP协议。协议。 TCP/IP(传输控制协议/互联网协议 )TCP/IPTCP/IP通讯协议采用了通讯协议采用了4 4层层的层级结构，这的层级结构，这4 4层分别为：层分别为： 应用层应用层：应用程序间沟通的层，如简单电子：

59、应用程序间沟通的层，如简单电子邮件传输（邮件传输（SMTPSMTP）、文件传输协议（）、文件传输协议（FTPFTP）、）、网络远程访问协议（网络远程访问协议（TelnetTelnet）等。）等。 传输层传输层 互连网络层互连网络层 网络接口层网络接口层TCP/IP协议使用一组由十进制数组成的4段数字(最大为255)来确定计算机的地址，每段数字之间用小数点隔开，例如，习惯上把这种识别计算机的数字称为IP地址 。IP地址规定：IP地址用二进制来表示，每个IP地址长32bit，比特换算成字节，就是4个字节。例如：一个采用二进制形式的IP地址是“00001010000000000

60、000000000000001” IP地址经常被写成十进制的形式，中间使用符号“.”分开不同的字节。于是，上面的IP地址可以表示为“”。IP地址分类A类地址B类地址C类地址A类IP地址由1字节的网络地址和3字节主机地址组成，网络地址的最高位必须是“0”， 地址范围-54可用的A类网络有126个，每个网络能容纳1亿多个主机。 A类地址一个一个B B类类IPIP地址由地址由2 2个字节的网络地址个字节的网络地址和和2 2个字节的主机地址组成，网络地址个字节的主机地址组成，网络地址的最高位必须是的最高位必须是“1010”，地址范围，地址范围-191