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

信息学奥林匹克竞赛任课教师：郑文云、岳水平Tel13178906711信息学奥林匹克竞赛任课教师：郑文云、岳水平1一、单项选择题（共10题，每题1.5分，共计15分。每题有且仅有一个正确答案.）。二、不定项选择题（共10题，每题1.5分，共计15分。每题正确答案的个数大于或等于1。多选或少选均不得分）。三、问题求解（共2题，每题5分，共计10分）四、阅读程序写结果（共

4题，每题

8分，共计

32分）五、完善程序

(前

5空，每空

2分，后

6空，每空

3分，共28分)全国青少年信息学奥林匹克联赛初赛试题题型

（时间：2小时）

一、单项选择题（共10题，每题1.5分，共计15分。每题有且2一、奥赛相关简介和语言NOIP：全国青少年信息学奥林匹克联赛（10-11）冬令营：全国青少年信息学奥林匹克竞赛冬令营（2-3）NOI：全国青少年信息学奥林匹克竞赛（7-8）（4男1女）网上同步赛夏令营：全国青少年信息学奥林匹克竞赛夏令营选拔赛：选拔参加国际信息学奥林匹克竞赛的中国代表队的竞赛（4-5）（noi前20名）APIO2007：亚洲与太平洋地区信息学奥林匹克

IOI：国际奥林匹克竞赛（8-9）1、竞赛简介一、奥赛相关简介和语言NOIP：全国青少年信息学奥林匹克联赛3一、奥赛相关的知识和语言freepascal、gcc/g++（c++）2、竞赛语言一、奥赛相关的知识和语言freepascal、gcc/g4二、计算机的产生和发展世界上的第一台计算机（ENIAC）于1946年诞生在美国宾夕法尼亚大学第一代电子管计算机，始于1946年，结构上以CPU为中心，使用计算机语言，速度慢，存储量小，主要用于数值计算；

第二代晶体管计算机，始于1958年，结构上以存储器为中心，使用高级语言，应用范围扩大到数据处理和工业控制；

第三代中小规模集成电路计算机，始于1964年，结构上仍以存储器为中心，增加了多种外部设备，软件得到了一定的发展，文字图象处理功能加强；第四代大规模和超大规模集成电路计算机，始于1971年，应用更广泛，很多核心部件可集成在一个或多个芯片上，从而出现了微型计算机二、计算机的产生和发展世界上的第一台计算机（ENIAC）于15二、计算机的产生和发展我国从1956年开始电子计算机的科研和教学工作，1983年研制成功1亿/秒运算速度的“银河”巨型计算机，1992年11月研制成功10亿/秒运算速度的“银河II”巨型计算机，1997年研制了每秒130亿运算速度的“银河III”巨型计算机。1999年，银河四代巨型机研制成功。2000年，我国自行研制成功高性能计算机"神威I"，其主要技术指标和性能达到国际先进水平。我国成为继美国、日本之后世界上第三个具备研制高性能计算机能力的国家。

二、计算机的产生和发展我国从1956年开始电子计算机的科研和6三、计算机系统及工作原理1.计算机的系统组成

计算机系统由软件和硬件两部分组成。输入输出：触摸屏三、计算机系统及工作原理1.计算机的系统组成计算机系统由软7三、计算机系统及工作原理存储器：具有记忆功能的物理器件，用于存储信息。存储器分为内存和外存

①内存是半导体存储器(主存）：它分为只读存储器(ROM)和随机存储器(RAM)和高速缓冲存储器（Cache)；

ROM:只能读，不能用普通方法写入，通常由厂家生产时写入，写入后数据不容易丢失，也可以用特殊方法（如紫外线擦除（EPROM)或电擦除(EEPROM_)存储器)；

RAM:可读可写，断电后内容全部丢失；

Cache:因为CPU读写RAM的时间需要等待，为了减少等待时间，在RAM和CPU间需要设置高速缓存Cache,断电后其内容丢失。

②外存：磁性存储器——软盘和硬盘；光电存储器——光盘，它们可以作为永久存器；

③存储器的两个重要技术指标：存取速度和存储容量。内存的存取速度最快(与CPU速度相匹配)，软盘存取速度最慢。存储容量是指存储的信息量，它用字节(Byte)作为基本单位，三、计算机系统及工作原理存储器：具有记忆功能的物理器件，用于8三、计算机系统及工作原理1.计算机的系统组成

计算机系统由软件和硬件两部分组成。Linux、unix、DOS、NT等三、计算机系统及工作原理1.计算机的系统组成计算机系统由软9三、计算机系统及工作原理到目前为止,电子计算机的工作原理均采用冯.若依曼的存储程序方式,即把程序存储在计算机内,由计算机自动存取指令（计算机可执行的命令=操作码+操作数）并执行它。2.计算机的工作原理三、计算机系统及工作原理到目前为止,电子计算机的工作原理均采10三、计算机系统及工作原理2.计算机的工作原理（1）运算器用于进行加、减、乘、除等算术运算以及逻辑运算。运算器是决定计算机运算速度的主要环节。（2）控制器用于控制并协调计算机各部分工作流程与顺序。（3）存储器存储器由许多存储单元，用于存储程序和数据。（4）输入设备用于把程序及原始数据转换成计算机可以识别的代码并送入存储器中保存。（5）输出设备用于送出计算机运行的结构及人们所需要的信息。三、计算机系统及工作原理2.计算机的工作原理（1）运算器11四、计算机中有关数及编码在计算机中，所有的数据、指令以及一些符合等都是用特定的二进制代码表示的。b：一位二进制码叫做一比特（bit），它是计算机能处理和存储的最小单位。字节（B）：八位二进制码叫做一个字节（Byte），计算机的存储容量就是以字节为单位计算的。计算机中存贮容量的单位：字节（Byte），用B表示：字节1B=8b千字节1KB=1024B兆字节1MB=1024KB

千兆1GB=1024MB四、计算机中有关数及编码在计算机中，所有的数据12四、计算机中有关数及编码1.二进制数的运算法则0+0=00+1=11+0=11+1=0

0*0=00*1=01*0=01*1=12.十进制与二进制、八进制、十六进制数之间的相互转换进制基数特点二进制0,1逢二进一八进制0,1,2,3,4,5,6,7逢八进一十六进制0,1,2,...,9,A,B,C,D,E,F逢十六进一(1)数的进制与基数四、计算机中有关数及编码1.二进制数的运算法则0+0=0013四、计算机中有关数及编码2.十进制与二进制、八进制、十六进制数之间的相互转换（2）数的权不同进制的数，基数不同，每位上代表的值的大小（权）也不相同。四、计算机中有关数及编码2.十进制与二进制、八进制、十六进制14四、计算机中有关数及编码2.十进制与二进制、八进制、十六进制数之间的相互转换(3)十进制数转换任意进制

a)将十进制整数除以所定的进制数,取余逆序。

四、计算机中有关数及编码2.十进制与二进制、八进制、十六进制15四、计算机中有关数及编码2.十进制与二进制、八进制、十六进制数之间的相互转换

b)将十进制小数的小数部分乘以进制数取整,作为转换后的小数部分,直到为零或精确到小数点后几位。(3)十进制数转换任意进制

a)将十进制整数除以所定的进制数,取余逆序。

四、计算机中有关数及编码2.十进制与二进制、八进制、十六进制16四、计算机中有关数及编码2.十进制与二进制、八进制、十六进制数之间的相互转换(4)任意进制的数转换十进制按权值展开:四、计算机中有关数及编码2.十进制与二进制、八进制、十六进制17

一个数在计算机内被表示的二进制形式称为机器数，该数称为这个机器数的真值。机器数具有下列特点：（a）由于计算机设备上的限制和操作上的便利，机器数有固定长度；如：一个8位机器数，所能表示的无符号整数的最大值是：“11111111”，即十进制数255。（b）机器数把其真值符合数字化；

通常是用机器数中规定的符号位（一般是最高位）取0或1，来分别表示其真值的正或负。如：一个8位机器数，其最高位是符号位，那么在定点整数原码表示情况下，对于00101110和10010011其真值分别为十进制：＋46和－19（c）机器数中，采用定点或浮点方式来表示小数点的位置。四、计算机中有关数及编码一个数在计算机内被表示的二进制形式称为机器数，该183、原码、反码和补码

机器数的形式是人们规定的，原码和补码是最常见的机器数形式或称数的编码方式。（a）原码

整数X的原码是指：其符号位的0或1表示X的正或负，其数值部分就是X绝对值的二进制表示。通常用〔X〕原表示X的原码。如：假设机器数的位数是8，其中最高位是符号位，其余是数值部分，则：[+17]原＝00010001[－39]原＝10100111注：[＋0]原＝00000000[－0]原＝10000000

零的原码不唯一，有“正零”和“负零”之分。四、计算机中有关数及编码3、原码、反码和补码机器数的形式是人们规定的，原19（b）反码在反码表示法中，正数的表示方式与原码相同；负数的补码是把其原码除符号位外的各位取反（即0变1，1变0）。通常用[X]反表示X的反码。如：[＋45]反＝[＋45]原＝00101101[－32]原＝10100000则[－32]反＝11011111四、计算机中有关数及编码3、原码、反码和补码（b）反码在反码表示法中，正数的表示方式与原码相同；如：[20（c）补码

在进行减法运算时，数的原码表示显得不方便，故引进了数的补码表示。正数的补码与其原码相同；负数的补码是在其反码的最低有效位上加1。用[X]补表示X的补码。如：[+14]补＝[+14]原＝00001110[-36]原＝10100100而[-36]反＝11011011则[-36]补＝11011100数0的补码表示是唯一的，即[＋0]＝[＋0]补＝[－0]原＝00000000利用公式:[X]补+[±Y]补=[X±Y]补可以把加法和减法统一成加法。四、计算机中有关数及编码3、原码、反码和补码（c）补码在进行减法运算时，数的原码表示显得不方便214.数的定点和浮点表示数的补码表示解决了带符号数的运算问题。至于小数点的处理，计算机中通常用定点表示法或浮点表示法来解决。（a）定点表示法定点表示法是把小数点约定在机器数的某一固定的位置上。如果小数点约定在符号位和数值的最高位之间，这时所有参加运算的数的绝对值小于1，即为定点纯小数。如：[X]补＝01010000，这时X＝0.625如果小数点约定在数值的最低位之后，这时所有参加运算的数都是整数，即为定点整数。如：[X]补＝11010000，这时X＝-48四、计算机中有关数及编码4.数的定点和浮点表示数的补码表示解决了带符号数的运算问题。22由于[M]补＝01111111，即M＝27－1＝＋127

[N]补＝10000000，即N＝－27＝－128所以8位定点整数（补码表示）的范围是－128－－＋12716位定点整数（补码表示）的范围是－32768－－＋32767定点数在使用时，所有原始数据事先都要按比例化成纯小数或整数，运算结果又要按比例转换成实际值。四、计算机中有关数及编码4.数的定点和浮点表示（a）定点表示法由于[M]补＝01111111，即M＝27－1＝＋1271623（b）浮点表示法任何一个二进制数N，都可写成2e*t的形式，即N＝2e*t如：1010.11可写成2100*0.101011即1010.11＝2100*0.101011e称为N的阶码，是一个二进制整数，t称为N的尾数，是一个二进制纯小数机器数用阶码和尾数两部分表示，称为浮点表示法。一般规定：阶码是定点整数，尾数是定点纯小数。它们可采用原码、补码或其他编码表示。四、计算机中有关数及编码4.数的定点和浮点表示（b）浮点表示法任何一个二进制数N，都可写成2e*t的形式，24如：一个数X用8位机器数浮点表示如下，其中前三位表示阶符和阶码值，后五位表示尾符和尾数值，它们都用原码表示：11001100阶符阶码尾符尾值则X＝2－2*0.1100＝0.001100＝0.1875浮点表示中，尾数的大小和正负结点了所表示的数的有效数字和正负；阶码的大小和正负决定了小数点的位置；因此机器数小数点的位置随阶码的变化而浮动。为了使运算中不丢失有效数字，提供运算精度，计算机中的浮点表示，通常采用改变阶码来达到规格化数的表示。注：规格化要求尾数值的最高位必须是1。如：一个数X用8位机器数浮点表示如下，其中前三位表示阶符125如：在16位机器浮点表示中，取前六位为阶码（其中第一位为是阶符），后十位为尾数（其中第一位为尾符），它们都用原码表示，那么它能表示的最大数和最小数分别为：0111110111111111即231（1－29）约＝2.14329*1090111111111111111即－231（1－29）约＝－2.14329*109可见比相同位数机器数定点表示的范围大得多。如：在16位机器浮点表示中，取前六位为阶码（其中第一位为01265、ASCII码和BCD码a、ASCII码字符或字符的组合、控制功能符号等，在计算机内部，必须用一种二进制代码来表示。国际上广泛使用的是:美国标准信息交换代码（AmenricanStandandCodeforInformationInterechange）简称：ASCIIASCII码是7位二进制编码，它可以表示27＝128个字符。四、计算机中有关数及编码5、ASCII码和BCD码a、ASCII码字符或字符的组合、2716进制表示ASCII码A—Z:41—5Aa—z:61—7A0—9:30--39一个字符的ASCII码可用二进制表示，也可用八进制、十进制、十六进制表示。四、计算机中有关数及编码5、ASCII码和BCD码a、ASCII码16进制表示ASCII码一个字符的ASCII码可用二进制表示28计算机在进行字符处理和传送时，一般在7位的ASCII码左边附加一个奇偶校验位，组成8位代码进行存储和传送。在偶校验系统中，用附加的偶数校验位使所有字符的8位代码都有偶数个1。在奇校验系统中用附加的奇数校验位使所有字符的8位代码都有奇数个1。如：“R”和“S”的ASCII码为：1010010和1010011则偶校验：11010010和01010011奇校验：01010010和11010011

由于标准的7位ASCII码所表示的字符较少，设计扩充了的8位二进制ASCII码，可表示256个字符。计算机在进行字符处理和传送时，一般在7位的ASCII码左边附29b、BCD码十进制数在键盘输入和打印、显示输出时，往往是将各个数字以ASCII码来表示的。但在计算机内运算时，是以二进制进行的。为了便于转换，人们设计了二进制编码来表示十进制，称二----十进制码，即BCD码。BCD码是用四位二进制代码来表示一位十进制码。从16个四位二进制代码0000－1111中，只须选择其中的10个作为十进制数的10个数字的代码就可以了。这样就有多种BCD码:8421码、2421码、余3码、格雷码等。b、BCD码十进制数在键盘输入和打印、显示输出时，往往是将各308421码最常用，它是用四位二进制代码来表示十进制数字，其特点是二进制代码本身的值就是它对应的十进制数字的值。所以8421码也称BCD码。如：十进制315可用BCD码表示为001100010101注：用BCD码表示的数，形式上像二进制数，但不是真正的二进制数。（315）10＝（100111011）28421码最常用，它是用四位二进制代码来表示十进制数字，其特31五、逻辑运算1.逻辑运算

not（逻辑非）:你真我假

and（逻辑与）:同真则真

or（逻辑或）:有真就真

xor(逻辑异或)

:不同则真

如果x、y是两个布尔型变量，下面列出了4种运算的结果：f:falset:truexynotxxandyxoryxxoryfftffffttftttfffttttfttf五、逻辑运算1.逻辑运算如果x、y是两个布尔型变量，下面列32五、逻辑运算运算顺序为（1）括号

（2）函数（3）not（4）*/divmodand（5）＋－orxor

（6）关系运算符（<,>,=,<>,<=,>=）五、逻辑运算运算顺序为33五、逻辑运算2.按位运算

按位与∩:同1则1如10010101∩10110111=10010101

按位或∪:有1则1如10010101∪10110111=10110111

五、逻辑运算2.按位运算34六、网络基础知识互联网的基本使用常识（网上的浏览、搜索和查询等）

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

空集：没有任何成员的集合称为空集，记为：｛｝

幂集：一个集合的所有子集组成的集合，

如｛1，2，3｝的幂集合为：｛｝、｛1｝、｛2｝、｛3｝、｛1，2｝、｛1，3｝、｛2，3｝、｛1，2，3｝七、数据结构1.集合(1)集合的概念如：大于10小于50的奇37七、数据结构1.集合（4）集合运算并∪：集A和集B所有的成员合并起来组成新的集合；交∩：集A和集B共有的成员组成新的集合；差－：集A的成员去掉和集B中也包含的成员组成新的集合；（如：全集Ｉ＝｛1，2，3，4，5，｝，其中子集A＝｛1，2｝，B＝｛2，3｝则A∪B={1,2,3};A∩B={2};A-B={1};七、数据结构1.集合（4）集合运算（如：全集Ｉ＝｛1，2，338八、简单算法2.数组

（1）一维数组的存储由于数组中所有元素属于同一类型，所以每个元素在存储器中占用的空间大小相同。

假设数组的第一个元素存放的位置为LOC(k[1])，每个元素占用的空间大小为S，则k[i]的存放位置为：

LOC(k[i])=LOC(k[1])+S*(i-1)

例：一个向量第一个元素的存储地址是100,每个元素的长度是2,则第5个元素的地址是(

)。

A)110

B)108

C)100

D)109100＋2*（5-1）＝108八、简单算法2.数组（1）一维数组的存储例：一个向量第一个39储存元素的规律通常有“行优先”和“列优先”。

A32=a11a12a13

a21a22a23

a31a32a33

按“行优先”的顺序：a11a12a13a21a22a23a31a32a33

按“列优先”的顺序：a11a21a31a12a22a32a13a23a33

将二维数组Amn按“行优先”顺序储存在内存以后，元素aij的地址计算函数为：

LOC(aij)=LOC(a11)+(i-1)*n+(j-1)按“列优先”顺序储存在内存以后，元素aij的地址计算数为：

LOC(aij)=LOC(a11)+(j-1)*m+(i-1)

七、数据结构2.数组（2）二维数组储存元素的规律通常有“行优先”和“列优先”。

A3240例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：设数组A[10..100，20..100]以行优先的方式顺序存贮，每个元素占4个字节，且已知A[10，20]的地址为1000，则A[50，90]的地址是_______。1000+{(50-10)*81+(90-20)}*4=14240SA+[(5-1)*10+(8-1)]*3＝SA+141例1：已知数组中A中，每个元素A（I，J）在存贮时要占3个字41七、数据结构（1）栈的特点：

栈是一种线性表，对于它所有的插入和删除都限制在表的同一端进行，这一端叫做栈的“顶”，另一端则叫做栈的“底”，其操作特点是“后进先出”。3.栈（2）栈的基本运算：栈的插入栈的弹出读栈顶元素判栈是否为空七、数据结构（1）栈的特点：

栈是一种线性表，对于它所有42（3）栈的应用：计算表达式的值

(a)表达式的三种形式：中缀表达式：运算符放在两个运算对象中间，如：(2+1)*3；后缀表达式：不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，如：21+3*；

前缀表达式：同后缀表达式一样，不包含括号，运算符放在两个运算对象的前面，如：*+213。

(b)表达式的计算：

由于后缀表达式中没有括号，不需判别优先级，计算严格从左向右进行，故计算一个后缀表达式要比计算机一个中缀表达式简单得多。

（3）栈的应用：计算表达式的值

(a)表达式的三种形式：43例1：以下哪一个不是栈的基本运算()A)删除栈顶元素B)删除栈底的元素C)判断栈是否为空D)将栈置为空栈

B例2、若已知一个栈的入栈顺序是1，2，3，…，n，其输出序列为P1，P2，P3，…，Pn，若P1是n，则Pi是()A)iB)n-1C)n-i+1D)不确定

C例1：以下哪一个不是栈的基本运算()

B44七、数据结构4.队列(a)队列的特点：

队列也是一种线性表，对于它所有的插入都在队列的一端进行，所有的删除都在另一端进行，进行删除的一端叫队列的“头”，进行插入的一端叫队列的“尾”，其操作特点是“先进先出”。(b)队列的基本操作队列的插入队列的删除读队头元素判队列是否为空七、数据结构4.队列(a)队列的特点：

队列也是一种线性表，45例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.线性表的线性存贮结构优于链表存贮结构B.队列的操作方式是先进后出

C.栈的操作方式是先进先出D.二维数组是指它的每个数据元素为一个线性表的线性表

D例1、设栈S和队列Q的初始状态为空,元素e1,e2,e3,e46（一）树的基本术语（1）树的度——也即是宽度，以组成该树各结点中最大的度作为该树的度，如右图的树，其度为3;（2）树的深度——以组成该树各结点的最大层次，如上图，其深度为4；（3）森林——指若干棵互不相交的树的集合，如上图，去掉根结点A，其原来的子树T1、T2、T3的集合{T1,T2,T3}就为森林；（4）有序树——指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树。七、数据结构5.树（一）树的基本术语（1）树的度——也即是宽度，以组成该树各47（二）树的表示树的表示方法有许多，常用的方法是用括号：先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。如上图可写成如下形式：

(A(B(E(K,L),F),C(G),D(H(M),I,J)))

（二）树的表示树的表示方法有许多，48（三）二叉树

（1）二叉树的基本形态

二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：

(1)空二叉树——(a)；

(2)只有一个根结点的二叉树——(b)；

(3)右子树为空的二叉树——(c)；

(4)左子树为空的二叉树——(d)；

(5)完全二叉树——(e)（三）二叉树（1）二叉树的基本形态(1)空二叉树——(49（2）两个重要的概念：(a)完全二叉树——只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树；(b)满二叉树——除了叶结点外，每一个结点都有左右子女的二叉树。

（三）二叉树（2）两个重要的概念：(a)完全二叉树——只有最下面的两层结50(3)二叉树的性质(a)在二叉树中，第i层的结点总数不超过2^(i-1)；(c)对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；(d)具有n个结点的完全二叉树的深度为[lon2n]+1.(b)深度为k的二叉树至多有2^k-1个结点。（k>=1)（三）二叉树(3)二叉树的性质(a)在二叉树中，第i层的结点总数不超过251(4)二叉树的存储结构(1)顺序存储方式(2)链表存储方式，如：

数组下标：12345678数组D：ABCDEFGH

左指针数组L：24607000

右指针数组R：35000800（三）二叉树(4)二叉树的存储结构(1)顺序存储方式(2)链表存储方式，52(5)普通树转换成二叉树：凡是兄弟就用线连起来，然后去掉父亲到儿子的连线，只留下父母到其第一个子女的连线。（三）二叉树(5)普通树转换成二叉树：凡是兄弟就用线连起来，然后去掉父亲53(6)二叉树的遍历运算（递归定义）(a)先序遍历

访问根；按先序遍历左子树；按先序遍历右子树(b)中序遍历

按中序遍历左子树；访问根；按中序遍历右子树(c)后序遍历

按后序遍历左子树；按后序遍历右子树；访问根－*/+abcdef－中序：〔a+(b-c)〕*d-e/f先序：-*+a–bcd/ef后序：abc-+d*ef/-（三）二叉树(6)二叉树的遍历运算（递归定义）(a)先序遍历

访问54（7）哈夫曼树哈夫曼树，又称最优树，是一类带权路径长度最短的树。

从树中的一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称为路径长度，而整棵树的路径长度则是从树根到每一个结点的路径长度之和。

结点的带权路径长度就是从该结点到树根之间的路径长度与结点上权的乘积，则树的带权路径长度就是树中所有叶子结点的带权路径长度之和，记为WPL.（三）二叉树（7）哈夫曼树哈夫曼树，又称最优树，是一类带权路径长度最短的55例2、一棵二叉树的高度为h，所有结点的度为0，或为2，则此树最少有()个结点。A)2h-1B)2h-1C)2h+1D)h+1B例1、按照二叉树的定义，具有3个结点的二叉树有（）种。

A）3

B）4

C）5

D）6C例3、已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历的顺序分别为：CBGEAFHDIJ与CGEBHFJIDA则该二叉树的先序遍历的顺序为：ABCEGDFHIJ例2、一棵二叉树的高度为h，所有结点的度为0，或为2，则56例4、已知，按中序遍历二叉树的结果为：abc问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。

有5种

①a②b③a④c⑤c\/\\//baccab\/\/cbba例4、已知，按中序遍历二叉树的结果为：abc有57定义：图是由顶点集V和边集E组成，一般把图G记为G＝（V，E）。6.图

图中结点之间的关系完全是任意的，即图中任意两个数据元素之间都可能有关系，“多对多”的数据结构。七、数据结构（一）图的概念定义：图是由顶点集V和边集E组成，一般把图G记为6.图58v1v2v3v4顶点（a）有向图弧弧头弧尾v1v2v5v4v3（b）无向图边G1=(V1,E1)V1={v1,v2,v3,v4}E1={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}G2=(V2,E2)V2={v1,v2,v3,v4,v5}E2={<v1,v2>,<v1,v4>,<v2,v3>,<v2,v5>,<v3,v4>,<v3,v5>}v1v2v3v4顶点（a）有向图弧弧头弧尾v1v2v5v4v59在无向图中，与顶点依附的边的条数称为该顶点的度。在有向图中，从某顶点出发的弧的数目称为该顶点的出度；而达到某顶点的有向弧的数目称为该顶点的入度．用n表示图中顶点的数目，用e表示边或弧的数目，则：对于无向图，e的取值范围是：0到n（n－1）/2，有n（n－1）/2条边的无向图称为完全图（即任意两顶点间都有1条边）；对于有向图，e的取值范围是：0到n（n－1），有n（n－1）条边的有向图称为有向完全图（即任意两顶点间都有2条边）。在无向图中，与顶点依附的边的条数称为该顶点的度。用n表示图中60从一顶点沿图中顶点边（或弧）能够到达另一顶点，则称两顶点间存在一条路径，即路径是两顶点间经过的顶点序列。顶点序列中顶点不重复出现的路径称为简单路径；第一个顶点到最后一个顶点相同的路径称为回路或环；

在无向图中，如果顶点v和w之间存在一条路径，则称顶点v和顶点w是连通的；若图中任意两个顶点都存在路径，则称该无向图G是连通的。而连通分量指的是图中的极大连通子图。在有向图中，对于任意的两个顶点v和w，、若从v到w和从w到v之间均存在路径，则图G为强连通图。从一顶点沿图中顶点边（或弧）能够到达另一顶点，则称两顶点间顶61（二）图的存储结构（1）邻接矩阵设G=(V,E)是有n(n>=1)个顶点的图．邻接矩阵定义如下：无向图的邻接矩阵是对称的，可以用下（上）三角存储，空间需n（n+1）/2．有向图则不一定对称，空间需n2．图的存储方式有两种：顺序存储的数组表示法（连接矩阵）和链式存储的邻接表、十字链表等。（二）图的存储结构（1）邻接矩阵图的存储方式有两种：顺序存储62v1v2v3v4顶点（a）有向图弧弧头弧尾v