邱桂香老师——计算机基础.ppt

信息学竞赛基础知识 东北育才学校 邱桂香 你给自己的定位如何？ 普及信息学的教师？ 教学设备的维修员？ 领导的打字员？ 其他教师的软件制作？ 你的定位和别人眼中的你一致吗？ 奥赛辅导工作最重要的是什么？ 一个计算机专家 一定是一个优秀 的竞赛辅导老师 吗？ 一个优秀的竞赛 辅导老师一定是 计算机专家吗？ 我们很执着 点燃希望，走过激情燃烧的岁月！ 初赛试题结构 第一部分 基础知识 第二部分 问题求解 第三部分 阅读程序 第四部分 完善程序 第一部分 一、计算机的发展与应 用 二、计算机概述 三、多媒体技术应用 四、计算机网络使用基 础 一、计算机的发展与应用 一、计算机的发展与应用 1、下面列出的四项中，不属于计算机病毒特征的 是( ) A潜伏性 B激发性 C传播性 D免疫 性 2、国产银河型数字式电子计算机是属于下列哪种 类型计算机( ) A微型 B小型 C中型 D巨型 3、计算机病毒是指( ) A能传染给用户的磁盘病毒 B已感染病毒的磁 盘 C具有破坏性的特制程序 D已感染病毒的程 序 4、最早的计算机的用途是用于( ) A科学计算 B自动控制 C辅助设计 D系统仿真 5、操作系统在第几代计算机开始应用( ) A第一代 B第二代 C第三代 D第四 代 1 什么是CISC机？什么是RISC机？ 2 计算机的发展分为几个阶段？正在 研制的新型计算机具有哪些特点？ 3 简述“三金”工程的含义。 4 什么是计算机病毒，它具有哪些特 征，如何采取具体的防范措施？ 资 料 二、计算机概述 1. 世界上首先实现存储程序的电子数字计算机是 （ ）。 AENIAC B、UNIVAC C、EDVAC D、EDSAC 2、计算机能直接执行的指令包括两部分，它们是 ( ) A源操作数与目标操作数 B操作码与操作 数 CASCII码与汉字代码 D数字与字符 3、下列诸因素中，对微机工作影响最小的是( ) A尘土 B噪声 C温度 D湿度 4、在计算机中，ASCII码是几位二进制代码( ) A7 B8 C12 D16 5、下面四个不同进制的数，最小的一个数是( ) A(11011001)2 B(37)8 C(75)10 D(A7)16 资 料 1 简述冯诺依曼型计算机的组成与工作原理 。 2 计算机硬件系统由哪五个基本部分组成？它 们各自的功能是什么？ 3 机器指令由哪几部分组成？按其功能分为哪 几种指令类型？ 4.在计算机中，带符号数有几种表示方法？它 们之间的转换关系是什么？各自有什么用途 ？ 5 ASCII码由几位二进制数组成？它能表示什 么信息？ 6 二进制的计算规则。 三、多媒体技术应用 1彩色显示器所显示的五彩斑斓的色彩，是由哪三色混 合而成的（ ）。 A. 红 B. 白 C. 蓝 D. 绿 E. 橙 2下面哪个部件对于个人桌面电脑的正常运行不是必需 的（ ）。 A.CPU B. 图形卡（显卡） C. 光驱 D. 主板 E. 内存 3.下列哪个（些）不是个人计算机的硬件组成部分（ ）。 A.主板 B.虚拟内存 C.电源 D.硬盘 E.总线 4.一个文本屏幕有25列及80行，屏幕的左上角以（1，1 ）表示，而右下角则以（80，25）表示，屏幕上每一 个字符占用两字节（byte），整个屏幕则以线性方式存 储在电脑的存储器内，屏幕左上角开始，位移为0，然 后逐列逐列存储。求位于屏幕（X，Y）的第一个字节 的位移是（ ） A.（Y*80+X）*2-1 B.（Y-1）*80+X-1）*2 C.（Y*80+X-1）*2 D.（Y-1）*80+X）*2-1 1. 多媒体计算机系统的基本配置包 含了哪些设备？ 2 CD-ROM的功能大小取决于哪几 个参数？ 3 显示存储空间由哪几个主要的因 素决定？ 4 目前国际上有哪几种压缩数据的 标准？ 资 料 四、计算机网络使用基础 1、Internet的规范译名应为( ) A英特尔网 B因特网 C万维网 D以太网 2、下列哪些计算机网络不是按覆盖地域划分的( ) A局域网 B都市网 C广域网 D星型网 3、以下列举Internet的各种功能中，错误的是( ) A编译程序 B传送电子邮件 C查询信息 D数据库检索 4、计算机网络最突出的优点是( ) A传送信息速度高 B共享资源 C内存容量大 D交互性好 5、TCPIP协议共有( )层协议 A.3 B.4 C.5 D.6 1 什么是WAN网？什么是LAN网，他们各自 的功能是什么？ 2 什么是计算机网络的拓扑结构？常见的拓 扑结构有几种？ 3. 什么是计算机网络协议？说出OSI 的七层 协议的名称。 4. 在Internet中，IP地址和域名的作用是什么 ？它们之间有什么异同？ 资 料 第二部分 数学知识 组合、排列、集合 等 数据结构 图、树等 第三部分 阅读程序 直接推理 有流程图推断算法 动态模拟 由底向上阅读分析 例一 Var m,n,i:integer; t:extended; Begin read(n,m); t:=1; for i:=1 to m do t:=t*(n-i+1)/i; writeln(t:0:0); End. 输入： 10 5 输出： 例二 Label 10,20,30; Var s,p:string;I,k,n,j,m:integer; Begin readln(s);n:=length(s); readln(p);m:=length(p); i:=0; 10: i:=i+1;j:=I;k:=1; 例二（续） 20: If s j =0时，X反=X 当X=0时，符号位为1，其 余各位取反。 特点: 1.反码的和等于和的反码 2.有二个零 +0=000 -0=111 3.当最高位有进位而丢掉进位(即 2)时,要在最低位加1(循环进位) 原码,反码和补码之间的转换 X反 符号位不变数值位 不变(符号位为0) 变反(符号位为 1) +,0,1 X真值 X原 数值位不变 数值位不变(符号位为0) 变反加1(符号位为1) 符号位不变 X补 当X为正数，X反=X原=X补=X， 当X为负数时，X补=X反+1，X补=X原 2 . 5 ASCII码 ASCII码是美国信息交换标准代码的缩略 语。是目前国际上最为流行的字符信息编 码方案。它包括数字09、大小写字母和 专用符号等95种可打印字符，还有33种 控制字符。 一个字符ASCII码通常占一个字节，用七 位二进制编码组成，ASCII码最多可表示 128个不同的符号。字节的最高位被很多 系统用做校验码，以便提高字符信息传输 的可靠性。 2 . 12 汉字信息编码 汉字信息也采用二进制的数字化信息编码 。目前的汉字编码方案有二字节、三字节 甚至四字节的。 国标码（国家标准信息交换用汉字编码） ，是二字节码，用七位二进制数编码表示 一个汉字。目前国标码收入6763个汉字， 其中一级汉字（最常用）3755个，二级汉 字3008个，另外还包括682个西文字符、 图符。 2 . 6 二进制 采用二进制，优点： （1）易于物理实现 （2）二进制运算简单 （3）机器可靠性高 （4）通用性强 乘法 除法 整数转换 小数转换 0+0=0 0+1=1 1+0=1 1+1=10 0*0=0 0*1=0 1*0=0 1*1=1 3 . 2 CD-ROM 光驱的技术指标 (1) 数据传输率(Data Transfer Rate),即大家常说的倍 速，它是衡量光驱性能的最基本指标。单倍速光驱就是指每 秒可从光驱存取150KB数据的光驱。现在年青一代的40或48 倍速光驱每秒钟能读取6000KB和7200KB的数据。 (2) 平均寻道时间(Average Access Time),平均寻 道时间是指激光头（光驱中用于读取数据的一个装置）从原 来位置移到新位置并开始读取数据所花费的平均时间，显然 ，平均寻道时间越短，光驱的性能就越好。 (3) CPU占用时间(CPU Loading)，CPU占用时间是 指光驱在维持一定的转速和数据传输率时所占用CPU的时间 ，它也是衡量光驱性能好坏的一个重要指标。CPU占用时间 越少，其整体性能就越好。 (4) 数据缓冲区(Buffer)，数据缓冲区是光驱内部的存 储区。它能减少读盘次数，提高数据传输率。现在大多数光 驱的缓冲区为128K或256K。 3 . 3 显示存储空间 显示存储空间 =水平分辨率垂直分辨率色彩数目 例如，若采用640 480，16色显示模 式，只需要150KB的存储空间。但是 ，如果想在1280 1024，16M色的 显示模式下运行，4MB的显示存储 空间是不可能运行的。 3 .4 压缩标准 目前，国际上的压缩技术标准有 JPEG，MPEG 和P 4。 JPEG适合于连续色调、多级灰度、彩色或单色 静止图象数据压缩的国际标准。可获得10：1到 80：1的压缩比。 MPEG包括MPEG视频、 MPEG音频和MPEG系 统三部分，处理活动影象中的视频压缩 、音频 压缩，以及多种压缩后数据流的复合和同步问题 。可获得50：1到00：1的压缩比。 P 4目标是针对可视电话 和电视会议的。适应 各种通道容量的传输。 4 . 1 广域网和局域网 1、广域网WAN（Wide Area Network） 是跨地域性的网络系统，大多数WAN都是 网络互连而成的，如著名的Internet网络。 2、局域网LAN（Local Area Network） 一般由一个部门或公司组建，地理范围仅在 建筑楼内或单位内部。 3、城域网：可以看成是广域网的一种。 4 . 2 计算机网络拓扑结构 网络中各个站点相互连接的方法和形 式称之为网络拓扑。把向工作站、服务器 等网络单元抽象成为“点”，把网络中的电 缆等通信媒体抽象为“线”，从而抽象出了 络系统的具体结构，即为逻辑结构。网络 拓扑结构有： 计算机网络拓扑结构 4.3 网络协议 计算机通信协议指双方在通信中所 应共同遵守的约定。计算机通信协议精 确地定了计算机在彼此通信时的所有细 节。它规定每台计算机发送每条信息的 格式和含义，规定哪些情况下应发送那 些特殊的信息，以及接受方的计算机所 应作出什么反映等等。 OSI七层协议 主机A 主机B 1 应用层 应用层 2 表示层 表示层 3 会话层 会话层 4 运输层 运输层 5 网络层 网络层 6 数据链路层 数据链路 层 7 物理层 物理层 应用层协议 表示层协议 会话层协议 运输层协议 网络层协议 链路层协议 物理层协议 4.4 IP地址 Internet中的每台主机都被分配一个唯一 的32位地址，即IP地址。该地址由网络号 和主机号两部分组成，其中网络号表示一 个网络，而主机号表示这个网络中的一台 计算机。 IP地址由4个十进制数字字段组成, 字段 之间用点分开, 4个字段中的每个数字在 0255之间，如1。 IP地址类型 IP地址按网络规模的大小主要可分成三类: A类 地址、B类地址、C类地址。A类的第一个字段 的值在1126之间，一般用于大型网络；B类的 第一个字段的值在128 191之间，一般用于 中型网络或网络管理器，如路由器等；C类的第 一个字段在值在191 233之间，一般用于小 型网络。 网络地址数 网络主机数 主机总数 A类 126 16,38 7,064 2,064,770,064 B类 16,256 6 4,516 1,048,872,096 C类 2,064,512 254 524,386,048 域名 用IP地址标识主机既没有规律，又很难记忆，用 户很难用数字表示的IP地址与计算机的情况联系 起来，给访问Internet带来了很大的不便如果采 用域名系统，就可以很好地解决这些问题。 域名系统是由TCP/IP提供的一种服务，可以将域 名翻译成相应的IP地址。域名系统采用层次结构 ，按地理域或组织域进行分层，各层间用圆点 “.” 隔开。在主机的域名表示中，从左向右， 域名依次从小到大，例如在 中，最高域名为cn，次高 域名为com，最后一个域名为easthuman。 数学相关题目 1（第八届）在书架上放有编号为1，2，.n的 n本书。现将n本书全部取下然后再放回去，当 放回去时要求每本书都不能放在原来的位置上。 例如：n=3时,原来位置为1 2 3,放回去时只能为 ： 3 1 2 或 2 3 1 这两种。 问题：求当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门课程。 题目 3(第七届)平面上有三条平行直线，每条 直线上分别有7，5，6个点，且不同直线上 三个点都不在同一条直线上。问用这些点为 顶点，能组成多少个不同四边形? 4（第十届）已知a, b, c, d, e, f, g七个人 中，a会讲英语；b会讲英语和汉语；c会讲 英语、意大利语和俄语；d会讲汉语和日语 ；e会讲意大利语和德语；f会讲俄语、日语 和法语；g会讲德语和法语。能否将他们的 座位安排在圆桌旁，使得每个人都能与他身 边的人交谈？如果可以，请以“a b”开头写出 你的安排方案： 。 从n个不同元素中,任取m个元素,按照一定的 顺序排成一列,叫做从n个不同元素中取出m 个元素的一个排列. 2.组合的定义:从n个不同元素中,任取m个元素,并成一组 ,叫做从n个不同元素中取出m个元素的一 个组合. 3.排列数公式: 4.组合数公式: 1.排列的定义: 排列与组合的区别与联系:与顺序有关的为排列问题,与顺序 无关的为组合问题. 例1 学校师生合影，共8个学生，4个老师，要求老师在 学生中间，且老师互不相邻，共有多少种不同的合影方 式？ 解 先排学生共有 种排法,然后把老师插入学生 之间的空档，共有7个空档可插,选其中的4个空档,共 有 种选法.根据乘法原理,共有的不同坐法为 种. 结论1 插入法:对于某两个元素或者几个元素要求不 相邻的问题,可以用插入法.即先排好没有限制条件的 元素,然后将有限制条件的元素按要求插入排好元素 的空档之中即可. 分析 此题涉及到的是不相邻问题,并且是对老师有特殊 的要求,因此老师是特殊元素,在解决时就要特殊对待. 所涉及问题是排列问题. 解 因为女生要排在一起,所以可以将3个女生看成是 一个人,与5个男生作全排列,有 种排法,其中女生内 部也有 种排法,根据乘法原理,共有 种不同的排 法. 例2 5个男生3个女生排成一排,3个女生要排在一起, 有多少种不同的排法? 结论2 捆绑法:要求某几个元素必须排在一起的问题, 可以用捆绑法来解决问题.即将需要相邻的元素合并 为一个元素,再与其它元素一起作排列,同时要注意合 并元素内部也可以作排列. 分析 此题涉及到的是排队问题,对于女生有特殊的限 制,因此,女生是特殊元素,并且要求她们要相邻,因此 可以将她们看成是一个元素来解决问题. 解 把所有的硬币全部取出来,将得到 0.0523+0.1010=2.15元,所以比2元多0.15元,所 以剩下0.15元即剩下3个5分或1个5分与1个1角,所以 共有 种取法. 例3 袋中有5分硬币23个,1角硬币10个,如果从袋中 取出2元钱,有多少种取法? 结论3 剩余法:在组合问题中,有多少取法,就有多少 种剩法,他们是一一对应的,因此,当求取法困难时,可 转化为求剩法. 分析 此题是一个组合问题,若是直接考虑取钱的问题 的话,情况比较多,也显得比较凌乱,难以理出头绪来. 但是如果根据组合数性质考虑剩余问题的话,就会很 容易解决问题. 例4 学校安排考试科目9门,语文要在数学之前考,有 多少种不同的安排顺序? 解 不加任何限制条件,整个排法有 种,“语文安排 在数学之前考”,与“数学安排在语文之前考”的排法 是相等的,所以语文安排在数学之前考的排法共有 种. 结论4 对等法:在有些题目中,它的限制条件的肯定与 否定是对等的,各占全体的二分之一.在求解中只要求 出全体,就可以得到所求. 分析 对于任何一个排列问题,就其中的两个元素来讲 的话,他们的排列顺序只有两种情况,并且在整个排列 中,他们出现的机会是均等的,因此要求其中的某一种 情况,能够得到全体,那么问题就可以解决了.并且也避 免了问题的复杂性. 例5 某个班级共有43位同学,从中任抽5人,正、副 班长、团支部书记至少有一人在内的抽法有多少种? 解 43人中任抽5人的方法有 种,正副班长,团支部 书记都不在内的抽法有 种,所以正副班长,团支部书 记至少有1人在内的抽法有 种. 结论5 排异法:有些问题,正面直接考虑比较复杂,而它 的反面往往比较简捷,可以先求出它的反面,再从整体中 排除. 分析 此题若是直接去考虑的话,就要将问题分成好几 种情况,这样解题的话,容易造成各种情况遗漏或者重 复的情况.而如果从此问题相反的方面去考虑的话,不 但容易理解,而且在计算中也是非常的简便.这样就可 以简化计算过程. 数据结构相关题目 1.(第六届)已知，按中序遍历二叉树的结果为 ：abc 问：有多少种不同形态的二叉树可以得到这 一遍历结果，并画出这些二叉树。 2(第七届)已知一棵二叉树的结点名为大写 英文字母，其中序与后序遍历的顺序分别为 ：CBGEAFHDIJ与CGEBHFJIDA，则该二 叉树的先序遍历的顺序为：_。 3（第九届）无向图G有16条边，有3个4度 顶点、4个3度顶点，其余顶点的度均小于3 ，则G至少_个顶点。 扩展 二叉树 二叉树由结点的有限集合构成，这个有 限集合或者为空集，或者由一个根结点及两 棵不相交的分别成为这个根的左子树和右子 树的二叉树（它们也是结点的集合）组成。 二叉树的结点的子树要区分左子树和右 子树，即使在结点只有一棵子树的情况下也 要明确指出该子树是左子树还是右子树。 二叉树的五种形态 （1） （2） （3） （4） （5） 满二叉树 如果一棵二叉树的任何结点，或者是树叶 ，或者恰有两棵非空子树，则此二叉树称 为满二叉树。 在满二叉树里，树叶的个数等于分支结点 个数加一。 完全二叉树 如果一棵二叉树最多只有最