信息学奥赛初赛知识复习市公开课一等奖百校联赛获奖课件.pptx

信息学奥林匹克信息学奥林匹克分区联赛基础知识分区联赛基础知识第1页预赛试题结构预赛试题结构第一部分基础知识第二部分问题求解第三部分阅读程序第四部分完善程序第2页第一部分基础知识一、计算机产生与发展一、计算机产生与发展二、计算机系统组成二、计算机系统组成三、计算机特点及应用三、计算机特点及应用四、计算机中相关数及编码知识四、计算机中相关数及编码知识五、计算机网络基础知识五、计算机网络基础知识六、计算机信息安全知识六、计算机信息安全知识第3页一、一、计算机产生与发展计算机产生与发展计算机产生是计算机产生是20世纪最主要科学技术大事件之一。世世纪最主要科学技术大事件之一。世界上第一台计算机（界上第一台计算机（ENIAC）于）于1946年诞生在美国宾夕年诞生在美国宾夕法尼亚大学，到当前为止，计算机发展大致经历了四代：法尼亚大学，到当前为止，计算机发展大致经历了四代：第一代电子管计算机，始于第一代电子管计算机，始于1946年，结构上以年，结构上以CPU为为中心，使用计算机语言，速度慢，存放量小，主要用于数中心，使用计算机语言，速度慢，存放量小，主要用于数值计算；值计算；第二代晶体管计算机，始于第二代晶体管计算机，始于1958年，结构上以存放器年，结构上以存放器为中心，使用高级语言，应用范围扩大到数据处理和工业为中心，使用高级语言，应用范围扩大到数据处理和工业控制；控制；第三代中小规模集成电路计算机，始于第三代中小规模集成电路计算机，始于1964年，结构年，结构上仍以存放器为中心，增加了各种外部设备，软件得到了上仍以存放器为中心，增加了各种外部设备，软件得到了一定发展，文字图象处理功效加强；一定发展，文字图象处理功效加强；第四代大规模和超大规模集成电路计算机，始于第四代大规模和超大规模集成电路计算机，始于1971年，应用更广泛，很多关键部件可集成在一个或多个芯片年，应用更广泛，很多关键部件可集成在一个或多个芯片上，从而出现了微型计算机。上，从而出现了微型计算机。第4页我国计算机发展情况我国计算机发展情况1.我国从1956年开始计算机科研和教学工作；2.1960年我国第一台自行设计通用电子计算机107机诞生；3.1964年我国研制成大型通用电子计算机119机；4.1983年每秒运行一亿次银河巨型计算机在国防科技大学诞生；5.1992年研制成功每秒运行10亿次“银河”巨型计算机；6.1997年又研制成功每秒运行130亿次“银河”巨型计算机；7.我国较有名微型计算机品牌有：“联想”、“长城”、“方正”等；第5页1、国产银河型数字式电子计算机是属于以下哪种类型计算机()A微型B小型C中型D巨型2、最早计算机用途是用于()A科学计算B自动控制C辅助设计D系统仿真3、微型计算机问世是因为(C)出现。A.中小规模集成电路B.晶体管电路C.超大规模集成电路D.电子管电路第6页4、在以下关于图灵奖说法中，不正确是（、在以下关于图灵奖说法中，不正确是（）。）。A.图灵奖是美国计算机协会于图灵奖是美国计算机协会于1966年设置，专门奖励那年设置，专门奖励那些些对计算机事业作出主要贡献个人对计算机事业作出主要贡献个人B.图灵奖有图灵奖有“计算机界诺贝尔奖计算机界诺贝尔奖”之称之称C.迄今为止，还没有华裔计算机科学家获此殊荣。迄今为止，还没有华裔计算机科学家获此殊荣。D.图灵奖名称取自计算机科学先驱、英国科学家阿兰图灵奖名称取自计算机科学先驱、英国科学家阿兰图灵图灵5、关于图灵机下面说法哪个是正确：、关于图灵机下面说法哪个是正确：A.图灵机是世界上最早电子计算机。图灵机是世界上最早电子计算机。B.因为大量使用磁带操作，图灵机运行速度很慢。因为大量使用磁带操作，图灵机运行速度很慢。C.图灵机是英国人图灵创造，在二战中为破译德军密码发挥图灵机是英国人图灵创造，在二战中为破译德军密码发挥了主要作用。了主要作用。D.图灵机只是一个理论上计算模型。图灵机只是一个理论上计算模型。第7页5、全国信息学奥林匹克官方网站为参加信息、全国信息学奥林匹克官方网站为参加信息学竞赛老师同学们提供相关信息和资源，学竞赛老师同学们提供相关信息和资源，请问全国信息学奥林匹克官方网站网址是：请问全国信息学奥林匹克官方网站网址是：A)http:/ 广域网和局域网 1、广域网WAN（wide area network）是跨地域性网络系统，大多数WAN都是网络互连而成，如著名Internet网络。2、局域网LAN（Local Area Network）普通由一个部门或企业组建，地理范围仅在建筑楼内或单位内部。3、城域网：能够看成是广域网一个。第78页4.2 计算机网络拓扑结构网络中各个站点相互连接方法和形式称之为网络拓扑。把向工作站、服务器等网络单元抽象成为“点”，把网络中电缆等通信媒体抽象为“线”，从而抽象出了络系统详细结构，即为逻辑结构。网络拓扑结构有：第79页计算机网络拓扑结构第80页4.3网络协议计算机通信协议指双方在通信中所应共同恪守约定。计算机通信协议准确地定了计算机在彼此通信时全部细节。它要求每台计算机发送每条信息格式和含义，要求哪些情况下应发送那些特殊信息，以及接收方计算机所应作出什么反应等等。第81页OSI七层协议主机A主机B1应用层应用层2表示层表示层3会话层会话层4运输层运输层5网络层网络层6数据链路层数据链路层7物理层物理层应用层协议表示层协议会话层协议运输层协议网络层协议链路层协议物理层协议第82页4.4IP地址Internet中每台主机都被分配一个唯一32位地址，即IP地址。该地址由网络号和主机号两部分组成，其中网络号表示一个网络，而主机号表示这个网络中一台计算机。IP地址由4个十进制数字字段组成,字段之间用点分开,4个字段中每个数字在0255之间，如210.30.240.11。第83页IP地址类型IP地址按网络规模大小主要可分成三类:A类地址、B类地址、C类地址。A类第一个字段值在1126之间，普通用于大型网络；B类第一个字段值在128 191之间，普通用于中型网络或网络管理器，如路由器等；C类第一个字段在值在191 233之间，普通用于小型网络。网络地址数网络主机数主机总数A类12616,387,0642,064,770,064B类16,25664,5161,048,872,096C类2,064,512254524,386,048第84页域名用用IPIP地地址址标标识识主主机机既既没没有有规规律律，又又极极难难记记忆忆，用用户户极极难难用用数数字字表表示示IPIP地地址址与与计计算算机机情情况况联联络络起起来来，给给访访问问InternetInternet带带来来了了很很大大不不便便假假如如采采取取域域名名系系统统，就能够很好地处理这些问题。就能够很好地处理这些问题。域域名名系系统统是是由由TCP/IPTCP/IP提提供供一一个个服服务务，能能够够将将域域名名翻翻译译成成对对应应IPIP地地址址。域域名名系系统统采采取取层层次次结结构构，按按地地理理域域或或组组织织域域进进行行分分层层，各各层层间间用用圆圆点点“.”隔隔开开。在在主主机机域域名名表表示示中中，从从左左向向右右，域域名名依依次次从从小小到到大大，比比如如在在中中，最最高高域域名名为为cncn，次高域名为次高域名为comcom，最终一个域名为，最终一个域名为easthumaneasthuman。第85页数学相关题目1（第八届）在书架上放有编号为1，2，.nn本书。现将n本书全部取下然后再放回去，当放回去时要求每本书都不能放在原来位置上。比如：n=3时,原来位置为123,放回去时只能为：312或231这两种。问题：求当n=5时满足以上条件放法共有多少种?(不用列出每种放法)2.(第九届)某年级学生共选修6门课程，期末考试前，必须提前将这6门课程考完，每人天天只在下午至多考一门课程，设6门课程为C1，C2，C3，C4，C5，C6，S(Ci)为学习Ci学生集合。已知S(Ci)S(C6)，i=1，2，.，5，S(Ci)S(Ci+1)，i=1，2，3，4，S(C5)S(C1)，问最少安排_天才能考完这6门课程。第86页题目3(第七届)平面上有三条平行直线，每条直线上分别有7，5，6个点，且不一样直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不一样四边形?4（第十届）已知a,b,c,d,e,f,g七个人中，a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲汉语和日语；e会讲意大利语和德语；f会讲俄语、日语和法语；g会讲德语和法语。能否将他们座位安排在圆桌旁，使得每个人都能与他身边人交谈？假如能够，请以“ab”开头写出你安排方案：。第87页从n个不一样元素中,任取m个元素,按照一定次序排成一列,叫做从n个不一样元素中取出m个元素一个排列.2.2.组合定义组合定义:从n个不一样元素中,任取m个元素,并成一组,叫做从n个不一样元素中取出m个元素一个组合.3.3.排列数公式排列数公式:4.4.组合数公式组合数公式:1.1.排列定义排列定义:排列与组合区分与联络排列与组合区分与联络:与次序相关为排列问题与次序相关为排列问题,与次序无关与次序无关为组合问题为组合问题.第88页例例1 1 学校师生合影，共8个学生，4个老师，要求老师在学生中间，且老师互不相邻，共有多少种不一样合影方式？解解 先排学生共有 种排法,然后把老师插入学生之间空档，共有7个空档可插,选其中4个空档,共有 种选法.依据乘法原理,共有不一样坐法为 种.结论结论1 1 插入法插入法:对于某两个元素或者几个元素要求不相邻问题,能够用插入法.即先排好没有限制条件元素,然后将有限制条件元素按要求插入排好元素空档之中即可.分析分析 此题包括到是不相邻问题,而且是对老师有特殊要求,所以老师是特殊元素,在处理时就要特殊对待.所包括问题是排列问题.第89页解 因为女生要排在一起,所以能够将3个女生看成是一个人,与5个男生作全排列,有 种排法,其中女生内部也有 种排法,依据乘法原理,共有 种不一样排法.例2 5个男生3个女生排成一排,3个女生要排在一起,有多少种不一样排法?结论2 捆绑法捆绑法:要求某几个元素必须排在一起问题,能够用捆绑法来处理问题.即将需要相邻元素合并为一个元素,再与其它元素一起作排列,同时要注意合并元素内部也能够作排列.分析 此题包括到是排队问题,对于女生有特殊限制,所以,女生是特殊元素,而且要求她们要相邻,所以能够将她们看成是一个元素来处理问题.第90页解 把全部硬币全部取出来,将得到 0.0523+0.1010=2.15元,所以比2元多0.15元,所以剩下0.15元即剩下3个5分或1个5分与1个1角,所以共有 种取法.例3 袋中有5分硬币23个,1角硬币10个,假如从袋中取出2元钱,有多少种取法?结论3 剩下法剩下法:在组合问题中,有多少取法,就有多少种剩法,他们是一一对应,所以,当求取法困难时,可转化为求剩法.分析 此题是一个组合问题,若是直接考虑取钱问题话,情况比较多,也显得比较凌乱,难以理出头绪来.不过假如依据组合数性质考虑剩下问题话,就会很轻易处理问题.第91页例4 学校安排考试科目9门,语文要在数学之前考,有多少种不一样安排次序?解 不加任何限制条件,整个排法有 种,“语文安排在数学之前考”,与“数学安排在语文之前考”排法是相等,所以语文安排在数学之前考排法共有 种.结论4 对等法对等法:在有些题目中,它限制条件必定是否定是对等,各占全体二分之一.在求解中只要求出全体,就能够得到所求.分析 对于任何一个排列问题,就其中两个元素来讲话,他们排列次序只有两种情况,而且在整个排列中,他们出现机会是均等,所以要求其中某一个情况,能够得到全体,那么问题就能够处理了.而且也防止了问题复杂性.第92页例5 某个班级共有43位同学,从中任抽5人,正、副班长、团支部书记最少有一人在内抽法有多少种?解 43人中任抽5人方法有 种,正副班长,团支部书记都不在内抽法有 种,所以正副班长,团支部书记最少有1人在内抽法有 种.结论5 排异法排异法:有些问题,正面直接考虑比较复杂,而它反面往往比较简捷,能够先求出它反面,再从整体中排除.分析 此题若是直接去考虑话,就要将问题分成好几个情况,这么解题话,轻易造成各种情况遗漏或者重复情况.而假如从此问题相反方面去考虑话,不但轻易了解,而且在计算中也是非常简便.这么就能够简化计算过程.第93页数据结构相关题目1.(第六届)已知，按中序遍历二叉树结果为：abc问：有多少种不一样形态二叉树能够得到这一遍历结果，并画出这些二叉树。2(第七届)已知一棵二叉树结点名为大写英文字母，其中序与后序遍历次序分别为：CBGEAFHDIJ与CGEBHFJIDA，则该二叉树先序遍历次序为：_。3（第九届）无向图G有16条边，有3个4度顶点、4个3度顶点，其余顶点度均小于3，则G最少_个顶点。扩展第94页二叉树二叉树由结点有限集合组成，这个有限集合或者为空集，或者由一个根结点及两棵不相交分别成为这个根左子树和右子树二叉树（它们也是结点集合）组成。二叉树结点子树要区分左子树和右子树，即使在结点只有一棵子树情况下也要明确指出该子树是左子树还是右子树。第95页二叉树五种形态（1）（2）（3）（4）（5）第96页满二叉树假如一棵二叉树任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称为满二叉树。在满二叉树里，树叶个数等于分支结点个数加一。第97页完全二叉树假如一棵二叉树最多只有最下面两层结点度数能够小于2，而且最下面一层结点都集中在该层左边若干位置，则此二叉树称作完全二叉树。第98页二叉树遍历先序：根-左子树-右子树(abcd)中序：左子树-根-右子树(badc)后序：左子树-右子树-根(bdca)abcd第99页图习惯上，惯用G=(V,E)代表一个图，图中结点又称为顶点，V是结点有限集合，结点偶对称为边，E是边集合。任意一个含有n个结点无向图，其边数小于等于n*(n-1)/2;我们把边数恰好等于n*(n-1)/2n个结点无向图称为完全图。在一个n个结点有向图中，最大边数为n*(n-1)。一个结点度就是与该结点相关联边数目。第100页1(第七届)一棵二叉树高度为h，全部结点度为0，或为2，则此树最少有()个结点A)2h-1B)2h1C)2h十1D)h十12(第七届)无向图G(V，E)，其中Va，b，c，d，e，fE(a，b)，(a，e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)，对该图进行深度优先遍历，得到顶点序列正确是()A)a，b，e，c，d，fB)a，c，f，e，b，dC)a，e，b，c，f，dD)a，b，e，d，f，c3（第八届）按照二叉树定义，含有3个结点二叉树有()种。A)3B)4C)5D)64（第八届）在一个有向图中，全部顶点入度之和等于全部顶点出度之和()倍。A)12B)1C)2D)45.（第九届）假设我们用d=(a1,a2,.,a5),表示无向图G5个顶点度数，下面给出哪（些）组d值合理（）。A）5，4，4，3，1B）4，2，2，1，1C）3，3，3，2，2D）5，4，3，2，1E）2，2，2，2，26（第十届）满二叉树叶结点个数为N，它结点总数为A.NB.2*NC.2*N1D.2*N+1E.2N1第101页