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

信息学奥林匹克竞赛,任课教师：郑文云、岳水平Tel:13518080777、13178906711,一、单项选择题（共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-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为中心，使用计算机语言，速度慢，存储量小，主要用于数值计算； 第二代晶体管计算机，始于1958年，结构上以存储器为中心，使用高级语言，应用范围扩大到数据处理和工业控制； 第三代中小规模集成电路计算机，始于1964年，结构上仍以存储器为中心，增加了多种外部设备，软件得到了一定的发展，文字图象处理功能加强； 第四代大规模和超大规模集成电路计算机，始于1971年，应用更广泛，很多核心部件可集成在一个或多个芯片上，从而出现了微型计算机,二、计算机的产生和发展,我国从1956年开始电子计算机的科研和教学工作，1983年研制成功1亿/秒运算速度的“银河”巨型计算机，1992年11月研制成功10亿/秒运算速度的“银河II”巨型计算机，1997年研制了每秒130亿运算速度的“银河III”巨型计算机。1999年，银河四代巨型机研制成功。 2000年，我国自行研制成功高性能计算机神威I，其主要技术指标和性能达到国际先进水平。我国成为继美国、日本之后世界上第三个具备研制高性能计算机能力的国家。,三、计算机系统及工作原理,1.计算机的系统组成,计算机系统由软件和硬件两部分组成。,输入输出：触摸屏,三、计算机系统及工作原理,存储器：具有记忆功能的物理器件，用于存储信息。存储器分为内存和外存内存是半导体存储器(主存）：它分为只读存储器(ROM)和随机存储器(RAM)和高速缓冲存储器（Cache)；ROM:只能读，不能用普通方法写入，通常由厂家生产时写入，写入后数据不容易丢失，也可以用特殊方法（如紫外线擦除（EPROM)或电擦除(EEPROM_)存储器)；RAM:可读可写，断电后内容全部丢失；Cache:因为CPU读写RAM的时间需要等待，为了减少等待时间，在RAM和CPU间需要设置高速缓存Cache,断电后其内容丢失。 外存：磁性存储器软盘和硬盘；光电存储器光盘，它们可以作为永久存器； 存储器的两个重要技术指标：存取速度和存储容量。内存的存取速度最快(与CPU速 度相匹配)，软盘存取速度最慢。存储容量是指存储的信息量，它用字节(Byte)作为基本单位，,三、计算机系统及工作原理,1.计算机的系统组成,计算机系统由软件和硬件两部分组成。,Linux、unix、DOS、NT等,三、计算机系统及工作原理,到目前为止,电子计算机的工作原理均采用冯.若依曼的存储程序方式,即把程序存储在计算机内,由计算机自动存取指令（计算机可执行的命令=操作码+操作数）并执行它。,2.计算机的工作原理,三、计算机系统及工作原理,2.计算机的工作原理,（1）运算器用于进行加、减、乘、除等算术运算以及逻辑运算。运算器是决定计算机运算速度的主要环节。（2）控制器用于控制并协调计算机各部分工作流程与顺序。（3）存储器存储器由许多存储单元，用于存储程序和数据。（4）输入设备用于把程序及原始数据转换成计算机可以识别的代码并送入存储器中保存。（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+1=0 0*0=0 0*1=0 1*0=0 1*1=1,2.十进制与二进制、八进制、十六进制数之间的相互转换,(1)数的进制与基数,四、计算机中有关数及编码,2.十进制与二进制、八进制、十六进制数之间的相互转换,（2）数的权 不同进制的数，基数不同，每位上代表的值的大小（权）也不相同。,四、计算机中有关数及编码,2.十进制与二进制、八进制、十六进制数之间的相互转换,(3)十进制数转换任意进制 a) 将十进制整数除以所定的进制数,取余逆序。,四、计算机中有关数及编码,2.十进制与二进制、八进制、十六进制数之间的相互转换,b)将十进制小数的小数部分乘以进制数取整,作为转换后的小数部分,直到为零或精确到小数点后几位。,(3)十进制数转换任意进制 a) 将十进制整数除以所定的进制数,取余逆序。,四、计算机中有关数及编码,2.十进制与二进制、八进制、十六进制数之间的相互转换,(4)任意进制的数转换十进制 按权值展开:,一个数在计算机内被表示的二进制形式称为机器数，该数称为这个机器数的真值。,机器数具有下列特点：,（a）由于计算机设备上的限制和操作上的便利，机器数有固定长度； 如：一个8位机器数，所能表示的无符号整数的最大值是： “11111111”，即十进制数255。,（b）机器数把其真值符合数字化； 通常是用机器数中规定的符号位（一般是最高位）取0或1， 来分别表示其真值的正或负。 如：一个8位机器数，其最高位是符号位，那么在定点整数 原码表示情况下，对于00101110 和 10010011 其真值分别为十进制：46 和 19,（c）机器数中，采用定点或浮点方式来表示小数点的位置。,四、计算机中有关数及编码,3、原码、反码和补码,机器数的形式是人们规定的，原码和补码是最常见的机器数形式或称数的编码方式。,（a）原码,整数X的原码是指：其符号位的0或1表示X的正或负，其数值部分就是X绝对值的二进制表示。通常用X原表示X的原码。,如：假设机器数的位数是8，其中最高位是符号位，其余是数值部分，则： +17原00010001 39原10100111,注：0原00000000 0原10000000 零的原码不唯一，有“正零”和“负零”之分。,四、计算机中有关数及编码,（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补11011100,数0的补码表示是唯一的，即0 0补 0原00000000,利用公式:X补+ Y补=X Y补可以把加法和减法统一成加法。,四、计算机中有关数及编码,3、原码、反码和补码,4.数的定点和浮点表示,数的补码表示解决了带符号数的运算问题。至于小数点的处理，计算机中通常用定点表示法或浮点表示法来解决。,（a）定点表示法,定点表示法是把小数点约定在机器数的某一固定的位置上。,如果小数点约定在符号位和数值的最高位之间，这时所有参加运算的数的绝对值小于1，即为定点纯小数。,如： X补01010000，这时X0.625,如果小数点约定在数值的最低位之后，这时所有参加运算的数都是整数，即为定点整数。,如： 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.101011e称为N的阶码，是一个二进制整数，t称为N的尾数，是一个二进制纯小数,机器数用阶码和尾数两部分表示，称为浮点表示法。一般规定： 阶码是定点整数，尾数是定点纯小数。它们可采用原码、补码或其他编码表示。,四、计算机中有关数及编码,4.数的定点和浮点表示,如：一个数X用8位机器数浮点表示如下，其中前三位表示阶符 和阶码值，后五位表示尾符和尾数值，它们都用原码表示：,1 10 0 1100阶符 阶码 尾符 尾值,则X22*0.11000.0011000.1875,浮点表示中，尾数的大小和正负结点了所表示的数的有效数字和正负；阶码的大小和正负决定了小数点的位置；因此机器数小数点的位置随阶码的变化而浮动。,为了使运算中不丢失有效数字，提供运算精度，计算机中的浮点表示，通常采用改变阶码来达到规格化数的表示。注：规格化要求尾数值的最高位必须是1。,如：在16位机器浮点表示中，取前六位为阶码（其中第一位为 是阶符）， 后十位为尾数（其中第一位为尾符），它们都用 原码表示，那么它能表示的最大数和最小数分别为：,0111110111111111即231（129）约2.14329*1090111111111111111即231（129）约2.14329*109,可见比相同位数机器数定点表示的范围大得多。,5、ASCII码和BCD码,a、ASCII码,字符或字符的组合、控制功能符号等，在计算机内部，必须用一种二进制代码来表示。国际上广泛使用的是:美国标准信息交换代码（Amenrican Standand Codefor Information Interechange）简称：ASCII,ASCII码是7位二进制编码，它可以表示27128个字符。,四、计算机中有关数及编码,16进制表示ASCII码AZ:415Aaz:617A09:30-39,一个字符的ASCII码可用二进制表示，也可用八进制、十进制、十六进制表示。,四、计算机中有关数及编码,5、ASCII码和BCD码,a、ASCII码,计算机在进行字符处理和传送时，一般在7位的ASCII码左边附加一个奇偶校验位，组成8位代码进行存储和传送。,在偶校验系统中，用附加的偶数校验位使所有字符的8位代码都有偶数个1。,在奇校验系统中用附加的奇数校验位使所有字符的8位代码都有奇数个1。,如：“R”和“S”的ASCII码为：1010010 和1010011 则偶校验： 11010010 和 01010011 奇校验： 01010010 和 11010011,由于标准的7位ASCII码所表示的字符较少，设计扩充了的8位二进制ASCII码，可表示256个字符。,b、BCD码,十进制数在键盘输入和打印、显示输出时，往往是将各个数字以ASCII码来表示的。但在计算机内运算时，是以二进制进行的。,为了便于转换，人们设计了二进制编码来表示十进制，称二-十进制码，即BCD码。,BCD码是用四位二进制代码来表示一位十进制码。,从16个四位二进制代码00001111中，只须选择其中的10个作为十进制数的10个数字的代码就可以了。这样就有多种BCD码:8421码、2421码、余3码、格雷码等。,8421码最常用，它是用四位二进制代码来表示十进制数字，其特点是二进制代码本身的值就是它对应的十进制数字的值。所以8421码也称BCD码。,如：十进制315可用BCD码表示为001100010101,注：用BCD码表示的数，形式上像二进制数，但不是真正的 二进制数。 （315）10（100111011）2,五、逻辑运算,1.逻辑运算 not（逻辑非） :你真我假 and（逻辑与） :同真则真 or（逻辑或） :有真就真 xor(逻辑异或) :不同则真,如果x、y是两个布尔型变量，下面列出了4种运算的结果：f:false t:truex y not x x and y x or yx xor yf f tf f ff t tf t tt f ff t tt t f t t f,五、逻辑运算,运算顺序为（1）括号 （2）函数 （3）not （4）* / div mod and（5） or xor （6）关系运算符（,=,= ）,五、逻辑运算,2.按位运算 按位与:同1则1 如1001010110110111=10010101 按位或:有1则1 如1001010110110111=10110111,六、网络基础知识,互联网的基本使用常识（网上的浏览、搜索和查询等）,七、数据结构,数据结构是相互之间存在一种或多种特定关系的数据元素的集合，数据之间的关系称之为结构。,四种基本的数据结构：,集合：数据元素间除了“同属于一个集合”外，无其他关系。,线性结构：一个对一个，如线性表、数组、栈、队列。,树形结构：一个对多个，如树。,图形结构：多个对多个，如图。,七、数据结构,1.集合,(1)集合的概念某些具有共性又有个性的对象汇集在一起构成的整体。,如：大于10小于50的奇数；26个小写英文字母。,（2）元素与集合的关系 51，2，3，4，5,（3）几种重要的集合空集：没有任何成员的集合称为空集，记为：幂集：一个集合的所有子集组成的集合，如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）一维数组的存储 由于数组中所有元素属于同一类型，所以每个元素在存储 器中占用的空间大小相同。假设数组的第一个元素存放的位置为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,将二维数组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以行优先的方式顺序存贮，每个元素占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；,后缀表达式：不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，如：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 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.线性表的线性存贮结构优于链表存贮结构B.队列的操作方式是先进后出C.栈的操作方式是先进先出D. 二维数组是指它的每个数据元素为一个线性表的线性表,D,（一）树的基本术语,（1）树的度也即是宽度，以组成该树各结点中最大的度作为该树的度，如右图的树，其度为3;,（2）树的深度以组成该树各结点的最大层次，如上图，其深度为4；,（3）森林指若干棵互不相交的树的集合，如上图，去掉根结点A，其原来的子树T1、T2、T3的集合T1,T2,T3就为森林；,（4）有序树指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树。,七、数据结构,5.树,（二）树的表示,树的表示方法有许多，常用的方法是用括号：先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。如上图可写成如下形式：(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，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树；,(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)普通树转换成二叉树：,凡是兄弟就用线连起来，然后去掉父亲到儿子的连线，只留下父母到其第一个子女的连线。,（三）二叉树,(6)二叉树的遍历运算（递归定义）,(a)先序遍历访问根；按先序遍历左子树；按先序遍历右子树,(b)中序遍历按中序遍历左子树；访问根；按中序遍历右子树,(c)后序遍历按后序遍历左子树；按后序遍历右子树；访问根,中序：a+(b-c)*d-e/f,先序：- * + a bcd/ef,后序：abc - + d * ef / -,（三）二叉树,（7）哈夫曼树,哈夫曼树，又称最优树，是一类带权路径长度最短的树。,从树中的一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称为路径长度，而整棵树的路径长度则是从树根到每一个结点的路径长度之和。,结点的带权路径长度就是从该结点到树根之间的路径长度与结点上权的乘积，则树的带权路径长度就是树中所有叶子结点的带权路径长度之和，记为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则该二叉树的先序遍历的顺序为：,ABCEGDFHIJ,例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,v4E1=,G2=(V2,E2)V2=v1,v2,v3,v4,v5E2=, , ,在无向图中，与顶点依附的边的条数称为该顶点的度。在有向图中，从某顶点出发的弧的数目称为该顶点的出度；而达到某顶点的有向弧的数目称为该顶点的入度,用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之间均存在路径，则图G为强连通图。,（二）图的存储结构,（1）邻接矩阵设G=(V,E)是有n(n=1)个顶点的图邻接矩阵定义如下：无向图的邻接矩阵是对称的，可以用下（上）三角存储，空间需n（n+1）/2有向图则不一定对称，空间需n2,图的存储方式有两种：顺序存储的数组表示法（连接矩阵）和 链式存储的邻接表、十字链表等。,1 2 3 41 0 1 1 02 0 0 0 0 3 0 0 0 14 1 0 0 0,1 2 3 4 5 1 0 1 0 1 02 1 0 1 0 1 3 0 1 0 1 14 1 0 1 0 0 5 0 1 1 0 0,（2）邻接表,邻接表是图的一种链式结构。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（或弧）。,（三）图的遍历,图的遍历与树的遍历类似，即寻找某一策略使得从某一顶点出发，沿着某一线路能够访问图中的所有顶点一次且仅访问一次。,图的遍历方式有两种：深度优先和广度优先。,1、深度优先： 尽可能“深”的搜索图形，即对于新发现的顶点，如果它还有以此为起点而未访问的边，就沿此边继续访问下去。当顶点V的所有边都已被访问过，则从最后被访问的顶点开始，依次返回新近被访问过，则从最后被访问的顶点开始，依次返回新近被访问的且尚有邻接顶点未被访问过的顶点，再从该顶点重复上述搜索过程。,由于深度优先搜索可以由多个初始顶点开始重复进行，因此可能产生一个有数棵深度优先树组成的森林。,2、广度优先,从顶点v0出发，先访问v0，然后访问所有与v0邻接的顶点v1，v2,vt，再依次访问与v1v2,vt相邻接的所有未曾访问的顶点，如此循环进行下去，直至图中的所有顶点均被访问完成为止。,广度搜索：A-B-E-C-D-F-G,深度搜索：A-B-C-D-G-F-E,2、无向图G=(V，E)，其中V=a,b,c,d,e,f E=(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,c,1、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。 A)1/2B)1C)2D)4,B,D,3、用邻接矩阵表示下面的无向图,1 2 3 4 5 6 71 0 1 0 0 0 0 02 1 0 1 1 0 0 03 0 1 0 1 1 0 04 0 1 1 0 1 1 15 0 0 1 1 0 0 16 0 0 0 0 1 0 17 0 0 0 1 1 1 0,