基础+数据结构+算法ppt课件

1、信息学奥林匹克竞赛,任课教师：郑文云、岳水平 Tel13178906711,一、单项选择题（共10题，每题1.5分，共计15分。每题有且仅有一个正确答案.）。 二、不定项选择题（共10题，每题1.5分，共计15分。每题正确答案的个数大于或等于 1。多选 或少选均不得分）。 三、问题求解（共2题，每题5分，共计10分） 四、阅读程序写结果（共4 题，每题8 分，共计32 分） 五、完善程序(前5空，每空2分，后6空，每空3分，共28分,全国青少年信息学奥林匹克联赛 初赛试题题型 （时间：2小时,一、奥赛相关简介和语言,NOIP：全国青少年信息学奥林匹克联赛（10-11）

2、 冬令营：全国青少年信息学奥林匹克竞赛冬令营（2-3） NOI：全国青少年信息学奥林匹克竞赛 （7-8）（4男1女） 网上同步赛 夏令营：全国青少年信息学奥林匹克竞赛夏令营 选拔赛：选拔参加国际信息学奥林匹克竞赛的中国代表队的竞赛 （4-5）（noi前20名） APIO2007：亚洲与太平洋地区信息学奥林匹克 IOI：国际奥林匹克竞赛（8-9,1、竞赛简介,一、奥赛相关的知识和语言,free pascal 、gcc/g+ （c,2、竞赛语言,二、计算机的产生和发展,世界上的第一台计算机（ENIAC）于1946年诞生在美国宾夕法尼亚大学,第一代电子管计算机，始于1946年，结构上以CPU为中心，

3、使用计算机语言，速度慢，存储量小，主要用于数值计算； 第二代晶体管计算机，始于1958年，结构上以存储器为中心，使用高级语言，应用范围扩大到数据处理和工业控制； 第三代中小规模集成电路计算机，始于1964年，结构上仍以存储器为中心，增加了多种外部设备，软件得到了一定的发展，文字图象处理功能加强； 第四代大规模和超大规模集成电路计算机，始于1971年，应用更广泛，很多核心部件可集成在一个或多个芯片上，从而出现了微型计算机,二、计算机的产生和发展,我国从1956年开始电子计算机的科研和教学工作， 1983年研制成功1亿/秒运算速度的“银河”巨型计算机， 1992年11月研制成功10亿/秒运算速度的

4、“银河II”巨型计算机， 1997年研制了每秒130亿运算速度的“银河III”巨型计算机。 1999年，银河四代巨型机研制成功。 2000年，我国自行研制成功高性能计算机神威I，其主要技术指标和性能达到国际先进水平。我国成为继美国、日本之后世界上第三个具备研制高性能计算机能力的国家,三、计算机系统及工作原理,1.计算机的系统组成,计算机系统由软件和硬件两部分组成,输入输出：触摸屏,三、计算机系统及工作原理,存储器：具有记忆功能的物理器件，用于存储信息。存储器分为内存和外存 内存是半导体存储器(主存）： 它分为只读存储器(ROM)和随机存储器(RAM)和高速缓冲存储器（Cache)； ROM:只

5、能读，不能用普通方法写入，通常由厂家生产时写入，写入后数据不容易丢失，也可以用特殊方法（如紫外线擦除（EPROM)或电擦除(EEPROM_)存储器)； RAM:可读可写，断电后内容全部丢失； Cache:因为CPU读写RAM的时间需要等待，为了减少等待时间，在RAM和CPU间需要设置高速缓存Cache,断电后其内容丢失。 外存：磁性存储器软盘和硬盘；光电存储器光盘，它们可以作为永久存器； 存储器的两个重要技术指标：存取速度和存储容量。内存的存取速度最快(与CPU速 度相匹配)，软盘存取速度最慢。存储容量是指存储的信息量，它用字节(Byte)作为基本单位,三、计算机系统及工作原理,1.计算机的系

6、统组成,计算机系统由软件和硬件两部分组成,Linux、unix、DOS、NT等,三、计算机系统及工作原理,到目前为止,电子计算机的工作原理均采用冯.若依曼的存储程序方式,即把程序存储在计算机内,由计算机自动存取指令（计算机可执行的命令=操作码+操作数）并执行它,2.计算机的工作原理,三、计算机系统及工作原理,2.计算机的工作原理,1）运算器 用于进行加、减、乘、除等算术运算以及逻辑运算。运算器是决定计算机运算速度的主要环节。 （2）控制器 用于控制并协调计算机各部分工作流程与顺序。 （3）存储器 存储器由许多存储单元，用于存储程序和数据。 （4）输入设备 用于把程序及原始数据转换成计算机可以识

7、别的代码并送入存储器中保存。 （5）输出设备 用于送出计算机运行的结构及人们所需要的信息,四、计算机中有关数及编码,在计算机中，所有的数据、指令以及一些符合等都是用特定的二进制代码表示的,b：一位二进制码叫做一比特（bit），它是计算机能处理和存储 的最小单位。 字节（B）：八位二进制码叫做一个字节（Byte），计算机的存 储容量就是以字节为单位计算的。 计算机中存贮容量的单位：字节（Byte），用 B 表示： 字节1B=8b 千字节1KB=1024B 兆字节1MB=1024KB 千兆1GB=1024MB,四、计算机中有关数及编码,1.二进制数的运算法则,0+0=0 0+1=1 1+0=1 1

8、+1=0 0*0=0 0*1=0 1*0=0 1*1=1,2.十进制与二进制、八进制、十六进制数之间的相互转换,1)数的进制与基数,四、计算机中有关数及编码,2.十进制与二进制、八进制、十六进制数之间的相互转换,2）数的权 不同进制的数，基数不同，每位上代表的值的大小（权）也不相同,四、计算机中有关数及编码,2.十进制与二进制、八进制、十六进制数之间的相互转换,3)十进制数转换任意进制 a) 将十进制整数除以所定的进制数,取余逆序,四、计算机中有关数及编码,2.十进制与二进制、八进制、十六进制数之间的相互转换,b)将十进制小数的小数部分乘以进制数取整,作为转换后的小数部分,直到为零或精确到小数

9、点后几位,3)十进制数转换任意进制 a) 将十进制整数除以所定的进制数,取余逆序,四、计算机中有关数及编码,2.十进制与二进制、八进制、十六进制数之间的相互转换,4)任意进制的数转换十进制 按权值展开,一个数在计算机内被表示的二进制形式称为机器数，该数称为 这个机器数的真值,机器数具有下列特点,a）由于计算机设备上的限制和操作上的便利，机器数有固定长度； 如：一个8位机器数，所能表示的无符号整数的最大值是： “11111111”，即十进制数255,b）机器数把其真值符合数字化； 通常是用机器数中规定的符号位（一般是最高位）取0或1， 来分别表示其真值的正或负。 如：一个8位机器数，其最高位是符

10、号位，那么在定点整数 原码表示情况下，对于00101110 和 10010011 其真值分别为十进制：46 和 19,c）机器数中，采用定点或浮点方式来表示小数点的位置,四、计算机中有关数及编码,3、原码、反码和补码,机器数的形式是人们规定的，原码和补码是最常见的机器数形式 或称数的编码方式,a）原码,整数X的原码是指：其符号位的0或1表示X的正或负，其数值部分 就是X绝对值的二进制表示。 通常用X原表示X的原码,如：假设机器数的位数是8，其中最高位是符号位，其余是数值部分， 则： +17原00010001 39原10100111,注：0原00000000 0原10000000 零的原码不唯一

11、，有“正零”和“负零”之分,四、计算机中有关数及编码,b）反码,在反码表示法中，正数的表示方式与原码相同； 负数的补码是把其原码除符号位外的各位取反（即0变1，1变0）。 通常用X反表示X的反码,如： 45反 45原00101101,32原10100000 则32反11011111,四、计算机中有关数及编码,3、原码、反码和补码,c）补码,在进行减法运算时，数的原码表示显得不方便，故引进了数的 补码表示,正数的补码与其原码相同； 负数的补码是在其反码的最低有效位上加1。用X补表示X的补码,如： +14补+14原00001110,36原10100100 而-36反11011011 则-36补11

12、011100,数0的补码表示是唯一的，即 0 0补 0原00000000,利用公式:X补+ Y补=X Y补可以把加法和减法统一成加法,四、计算机中有关数及编码,3、原码、反码和补码,4.数的定点和浮点表示,数的补码表示解决了带符号数的运算问题。 至于小数点的处理，计算机中通常用 定点表示法或浮点表示法来解决,a）定点表示法,定点表示法是把小数点约定在机器数的某一固定的位置上,如果小数点约定在符号位和数值的最高位之间，这时所有参加运算 的数的绝对值小于1，即为定点纯小数,如： X补01010000，这时X0.625,如果小数点约定在数值的最低位之后，这时所有参加运算的数都是 整数，即为定点整数,

13、如： X补11010000，这时X-48,四、计算机中有关数及编码,由于M补01111111，即M271127 N补10000000，即N 27128 所以8位定点整数（补码表示）的范围是128127,16位定点整数（补码表示）的范围是3276832767,定点数在使用时，所有原始数据事先都要按比例化成纯小数或 整数，运算结果又要按比例转换成实际值,四、计算机中有关数及编码,4.数的定点和浮点表示,a）定点表示法,b）浮点表示法,任何一个二进制数N，都可写成2e*t的形式，即N 2e*t 如：1010.11可写成2100*0.101011即1010.11 2100*0.101011 e称为N的

14、阶码，是一个二进制整数，t称为N的尾数，是一个 二进制纯小数,机器数用阶码和尾数两部分表示，称为浮点表示法。 一般规定： 阶码是定点整数，尾数是定点纯小数。它们可采用原码、 补码或其他编码表示,四、计算机中有关数及编码,4.数的定点和浮点表示,如：一个数X用8位机器数浮点表示如下，其中前三位表示阶符 和阶码值，后五位表示尾符和尾数值，它们都用原码表示,1 10 0 1100 阶符 阶码 尾符 尾值,则X22*0.11000.0011000.1875,浮点表示中，尾数的大小和正负结点了所表示的数的有效数字和正负； 阶码的大小和正负决定了小数点的位置； 因此机器数小数点的位置随阶码的变化而浮动,为

15、了使运算中不丢失有效数字，提供运算精度，计算机中的浮点表示， 通常采用改变阶码来达到规格化数的表示。 注：规格化要求尾数值的最高位必须是1,如：在16位机器浮点表示中，取前六位为阶码（其中第一位为 是阶符）， 后十位为尾数（其中第一位为尾符），它们都用 原码表示，那么它能表示的最大数和最小数分别为,0111110111111111即231（129）约2.14329*109 0111111111111111即231（129）约2.14329*109,可见比相同位数机器数定点表示的范围大得多,5、ASCII码和BCD码,a、ASCII码,字符或字符的组合、控制功能符号等，在计算机内部，必须用 一种

16、二进制代码来表示。 国际上广泛使用的是:美国标准信息交换代码 （Amenrican Standand Codefor Information Interechange） 简称：ASCII,ASCII码是7位二进制编码，它可以表示27128个字符,四、计算机中有关数及编码,16进制表示ASCII码 AZ:415A az:617A 09:30-39,一个字符的ASCII码可用二进制表示，也可用八进制、十进制、 十六进制表示,四、计算机中有关数及编码,5、ASCII码和BCD码,a、ASCII码,计算机在进行字符处理和传送时，一般在7位的ASCII码左边附加 一个奇偶校验位，组成8位代码进行存储和传

17、送,在偶校验系统中，用附加的偶数校验位使所有字符的8位代码都有 偶数个1,在奇校验系统中用附加的奇数校验位使所有字符的8位代码都有 奇数个1,如：“R”和“S”的ASCII码为：1010010 和1010011 则偶校验： 11010010 和 01010011 奇校验： 01010010 和 11010011,由于标准的7位ASCII码所表示的字符较少，设计扩充了的8位 二进制ASCII码，可表示256个字符,b、BCD码,十进制数在键盘输入和打印、显示输出时，往往是将各个数字以 ASCII码来表示的。但在计算机内运算时，是以二进制进行的,为了便于转换，人们设计了二进制编码来表示十进制，称

18、二-十进制码，即BCD码,BCD码是用四位二进制代码来表示一位十进制码,从16个四位二进制代码00001111中，只须选择其中的10个作为十进制数的10个数字的代码就可以了。 这样就有多种BCD码:8421码、2421码、余3码、格雷码等,8421码最常用，它是用四位二进制代码来表示十进制数字，其特点 是二进制代码本身的值就是它对应的十进制数字的值。 所以8421码也称BCD码,如：十进制315可用BCD码表示为001100010101,注：用BCD码表示的数，形式上像二进制数，但不是真正的 二进制数。 （315）10（100111011）2,五、逻辑运算,1.逻辑运算 not（逻辑非） :你

19、真我假 and（逻辑与） :同真则真 or（逻辑或） :有真就真 xor(逻辑异或) :不同则真,如果x、y是两个布尔型变量，下面列出了4种运算的结果： f:false t:true x y not x x and y x or yx xor y f f tf f f f t tf t t t f ff t t t t f t t f,五、逻辑运算,运算顺序为 （1）括号 （2）函数 （3）not （4）* / div mod and （5） or xor （6）关系运算符（,=,=,五、逻辑运算,2.按位运算 按位与:同1则1 如1001010110110111=10010101 按位或:有

20、1则1 如1001010110110111=10110111,六、网络基础知识,互联网的基本使用常识（网上的浏览、搜索和查询等,七、数据结构,数据结构是相互之间存在一种或多种特定关系的数据元素的 集合，数据之间的关系称之为结构,四种基本的数据结构,集合：数据元素间除了“同属于一个集合”外，无其他关系,线性结构：一个对一个，如线性表、数组、栈、队列,树形结构：一个对多个，如树,图形结构：多个对多个，如图,七、数据结构,1.集合,1)集合的概念 某些具有共性又有个性的对象汇集在一起构成的整体,如：大于10小于50的奇数；26个小写英文字母,2）元素与集合的关系 51，2，3，4，5,3）几种重要的

21、集合 空集：没有任何成员的集合称为空集，记为： 幂集：一个集合的所有子集组成的集合， 如1，2，3的幂集合为： 、1、2、3、1，2、 1，3、2，3、1，2，3,七、数据结构,1.集合,4）集合运算 并：集A和集B所有的成员合并起来组成新的集合； 交：集A和集B共有的成员组成新的集合； 差：集A的成员去掉和集B中也包含的成员组成新的集合,如：全集1，2，3，4，5， 其中子集A1，2，B2，3 则 AB=1,2,3; AB=2; A-B=1,八、简单算法,2.数组,1）一维数组的存储 由于数组中所有元素属于同一类型，所以每个元素在存储 器中占用的空间大小相同。 假设数组的第一个元素存放的位置

22、为LOC(k1)，每个元素 占用的空间大小为S，则ki的存放位置为： LOC(ki)=LOC(k1)+S*(i-1,例：一个向量第一个元素的存储地址是100,每个元素的长度是2,则第5个元素的地址是( ) 。A)110 B)108 C) 100 D) 109,1002*（5-1）108,储存元素的规律通常有“行优先”和“列优先”。A32 = a11 a12 a13a21 a22 a23a31 a32 a33,按“行优先”的顺序：a11 a12 a13 a21 a22 a23 a31 a32 a33按“列优先”的顺序：a11 a21 a31 a12 a22 a32 a13 a23 a33,将二维

23、数组Amn按“行优先”顺序储存在内存以后，元素aij的地址计算函数为：LOC(aij)=LOC(a11)+(i-1)*n+(j-1) 按“列优先”顺序储存在内存以后，元素aij的地址计算数为：LOC(aij)=LOC(a11)+(j-1)*m+(i-1,七、数据结构,2.数组 （2）二维数组,例1：已知数组中A中，每个元素A（I，J）在存贮时要占3个字节，设I从1变化到8，J从1变化到10，分配内存时是从地址SA开始连续按行存贮分配的。试问：A（5，8）的起始地址为（）A.SA+141B. SA+180C. SA+222D. SA+225,例2：设数组A10.100，20.100以行优先的方式

24、顺序存贮，每个元素占4个字节，且已知A10，20的地址为1000，则A50，90的地址是_,1000+(50-10)*81+(90-20)*4=14240,SA+(5-1)*10+(8-1)*3SA+141,七、数据结构,1）栈的特点：栈是一种线性表，对于它所有的插入和删除都限制在表的同一端进行，这一端叫做栈的“顶”，另一端则叫做栈的“底”，其操作特点是“后进先出,3.栈,2）栈的基本运算： 栈的插入 栈的弹出 读栈顶元素 判栈是否为空,3）栈的应用：计算表达式的值,a)表达式的三种形式,中缀表达式：运算符放在两个运算对象中间，如：(2+1)*3,后缀表达式：不包含括号，运算符放在两个运算对象

25、的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，如：2 1 + 3,前缀表达式：同后缀表达式一样，不包含括号，运算符放在两个运算对象的前面，如：* + 2 1 3,b)表达式的计算：由于后缀表达式中没有括号，不需判别优先级，计算严格从左向右进行，故计算一个后缀表达式要比计算机一个中缀表达式简单得多,例1：以下哪一个不是栈的基本运算( ) A)删除栈顶元素 B)删除栈底的元素 C)判断栈是否为空 D)将栈置为空栈,B,例2、若已知一个栈的入栈顺序是1，2，3，n，其输出序列为P1，P2，P3，Pn，若P1是n，则Pi是( ) A)i B)n-1 C)n-i+1

26、D)不确定,C,七、数据结构,4.队列,a)队列的特点：队列也是一种线性表，对于它所有的插入都在队列的一端进行，所有的删除都在另一端进行，进行删除的一端叫队列的“头”，进行插入的一端叫队列的“尾”，其操作特点是“先进先出,b)队列的基本操作 队列的插入 队列的删除 读队头元素 判队列是否为空,例1、设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5,e6依次通过栈S,一个元素出栈后即进入队列Q,若出队的顺序为e2,e4,e3,e6,e5,e1,则栈S的容量至少应该为( ) 。A) 2 B) 3 C) 4 D) 5,B,例2、下列叙述中，正确的是（）A.线性表的线性存贮结构优于链表存

27、贮结构 B.队列的操作方式是先进后出C.栈的操作方式是先进先出 D. 二维数组是指它的每个数据元素为一个线性表的线性表,D,一）树的基本术语,1）树的度也即是宽度，以组成该树各结点中最大的度作为该树的度，如右图的树，其度为3,2）树的深度以组成该树各结点的最大层次， 如上图，其深度为4,3）森林指若干棵互不相交的树的集合，如上图，去掉根结点A，其原来的子树T1、T2、T3的集合T1,T2,T3就为森林,4）有序树指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树,七、数据结构,5.树,二）树的表示,树的表示方法有许多， 常用的方法是用括号： 先将根结点

28、放入一对圆括号中， 然后把它的子树由左至右的 顺序放入括号中，而对子树 也采用同样的方法处理； 同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。 如上图可写成如下形式： (A(B(E(K,L),F),C(G),D(H(M),I,J,三）二叉树,1）二叉树的基本形态 二叉树也是递归定义的，其结点有左右子树之分， 逻辑上二叉树有五种基本形态,1)空二叉树(a)；(2)只有一个根结点的二叉树(b)；(3)右子树为空的二叉树(c)；(4)左子树为空的二叉树(d)；(5)完全二叉树(e,2）两个重要的概念,a)完全二叉树只有最下面的两层结点度小于2，并且最下面一层的结点都

29、集中在该层最左边的若干位置的二叉树,b)满二叉树除了叶结点外，每一个结点都有左右子女的二叉树,三）二叉树,3)二叉树的性质,a)在二叉树中，第i层的结点总数不超过2(i-1,c)对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1,d)具有n个结点的完全二叉树的深度为lon2n+1,b)深度为k的二叉树至多有2k-1个结点。（k=1,三）二叉树,4)二叉树的存储结构,1)顺序存储方式,2)链表存储方式，如：数组下标： 12345678 数组D： AB C DE F GH左指针数组L： 24607000右指针数组R： 35000800,三）二叉树,5)普通树转换

30、成二叉树,凡是兄弟就用线连起来，然后去掉父亲到儿子的连线，只留下父母到其第一个子女的连线,三）二叉树,6)二叉树的遍历运算（递归定义,a)先序遍历访问根；按先序遍历左子树；按先序遍历右子树,b)中序遍历按中序遍历左子树；访问根；按中序遍历右子树,c)后序遍历按后序遍历左子树；按后序遍历右子树；访问根,中序：a+(b-c)*d-e/f,先序：- * + a bcd/ef,后序：abc - + d * ef /,三）二叉树,7）哈夫曼树,哈夫曼树，又称最优树，是一类带权路径长度最短的树,从树中的一个结点到另一个结点之间的分支构成这两个结点之间 的路径，路径上的分支数目称为路径长度，而整棵树的路径长

31、度 则是从树根到每一个结点的路径长度之和,结点的带权路径长度就是从该结点到树根之间的路径长度与结点 上权的乘积，则树的带权路径长度就是树中所有叶子结点的带权 路径长度之和，记为WPL,三）二叉树,例2、一棵二叉树的高度为h，所有结点的度为0，或为2，则 此树最少有( )个结点。 A)2h-1 B)2h-1 C)2h+1 D)h+1,B,例1、按照二叉树的定义，具有3个结点的二叉树有（ ）种。 A） 3 B） 4 C） 5 D） 6,C,例3、已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历的顺序分别为：CBGEAFHDIJ与CGEBHFJIDA则该二叉树的先序遍历的顺序为,ABCEGDF

32、HIJ,例4、已知，按中序遍历二叉树的结果为：abc 问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树,有 5 种 a b a c c / / / b a c c a b / / c b b a,定义：图是由顶点集V和边集E组成，一般把图G记为 G（V，E,6.图,图中结点之间的关系完全是任意的，即图中任意两个 数据元素之间都可能有关系，“多对多”的数据结构,七、数据结构,一）图的概念,G1=(V1,E1) V1=v1,v2,v3,v4 E1,G2=(V2,E2) V2=v1,v2,v3,v4,v5 E2=, ,在无向图中，与顶点依附的边的条数称为该顶点的度。 在有向图中，从

33、某顶点出发的弧的数目称为该顶点的出度； 而达到某顶点的有向弧的数目称为该顶点的入度,用n表示图中顶点的数目，用e表示边或弧的数目，则： 对于无向图，e的取值范围是：0到n（n1）/2， 有n（n1）/2条边的无向图称为完全图 （即任意两顶点间都有1条边）； 对于有向图， e的取值范围是：0到n（n1）， 有n（n1）条边的有向图称为有向完全图 （即任意两顶点间都有2条边,从一顶点沿图中顶点边（或弧）能够到达另一顶点，则称两顶点间 存在一条路径，即路径是两顶点间经过的顶点序列,顶点序列中顶点不重复出现的路径称为简单路径； 第一个顶点到最后一个顶点相同的路径称为回路或环,在无向图中，如果顶点v和w之间存在一条路径， 则称顶点v 和顶点w是连通的；若图中任意两个顶点都存在路径， 则称该无向图G是连通的。而连通分量指的是图中的极大连通子图。 在有向图中，对于任意的两个顶点v和w，、若从v到w和从w到v 之间均