数据结构-辅导讲义ppt课件

.,1,数据结构,辅导讲义,栾晓春,.,2,数据结构考查内容,【考查目标】1掌握数据结构的基本概念、基本原理和基本方法；2掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。3能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用C或C+或JAVA语言设计与实现算法的能力。,.,3,一、线性表（一）线性表的定义和基本操作（二）线性表的实现1顺序存储2链式存储3线性表的应用二、栈、队列和数组（一）栈和队列的基本概念（二）栈和队列的顺序存储结构（三）栈和队列的链式存储结构（四）栈和队列的应用（五）特殊矩阵的压缩存储,.,4,三、树与二叉树（一）树的基本概念（二）二叉树1二叉树的定义及其主要特征2二叉树的顺序存储结构和链式存储结构3二叉树的遍历4线索二叉树的基本概念和构造（三）树、森林1树的存储结构2森林与二叉树的转换3树和森林的遍历（四）树与二叉树的应用1二叉排序树2平衡二叉树3哈夫曼（Huffman）树和哈夫曼编码,.,5,四、图（一）图的基本概念（二）图的存储及基本操作1邻接矩阵法2邻接表法（三）图的遍历1深度优先搜索2广度优先搜索（四）图的基本应用1最小（代价）生成树2最短路径3拓扑排序4关键路径五、查找（一）查找的基本概念（二）顺序查找法（三）折半查找法（四）B树及其基本操作、B+树的基本概念（五）散列（Hash）表（六）查找算法的分析及应用,.,6,六、排序（一）排序的基本概念（二）插入排序1直接插入排序2折半插入排序（三）起泡排序（bubblesort）（四）简单选择排序（五）希尔排序（shellsort）（六）快速排序（七）堆排序（八）二路归并排序（mergesort）（九）基数排序（十）外部排序（十一）各种排序算法的比较（十二）排序算法的应用,.,7,.,8,为解决计算机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）。（全国统考2009）A栈B队列C树D图设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后入队Q，若出队序列为e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是（）。（全国统考2009）A1B2C3D4若元素abcdef依次进栈，允许进栈、出栈交替进行，不允许连续三次进行出栈操作，则不可能得到的出栈序列是（）。（全国统考2010）AdcebfaBcbdaefCdbcaefDafedcb某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺序是（）。（全国统考2010）AbacdeBdbaceCdbcaeDecbad,.,9,元素abcde依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是（）。（全国统考2011）A3B4C5D6已知循环队列存放在一维数组A0.n-1，且队列非空时front和rear分别指向队列的队头元素和队尾元素。若初始时队列为空，且要求第一个入队的元素存储在A0处，则初始时front和rear的值分别是（）。（全国统考2011）A0，0B0，n-1Cn-1，0Dn-1，n-1已知操作符包括+，-，*，/，(和)，将中缀表达式a+b-a*(c+d)/e-f)+g转化为等价的后缀表达式ab+acd+e/f-*-g+时，用栈来存放暂时还不能确定的运算次序的操作符，若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是（）。（全国统考2012）A5B7C8D11,.,10,第一章绪论,考纲分析1.理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。2.掌握基本的数据处理原理和方法的基础上，能够对算法进行基本的时间复杂度与空间复杂度进行设计与分析。3.能够选择合适的数据结构和方法进行问题求解，具备采用C或C+或JAVA语言设计与实现算法的能力。,.,11,红楼梦中贾家的人物关系,.,12,.,13,典型题目解析基本概念,本章题目主要考查数据结构的基本概念，要求深刻理解数据元素、数据的逻辑结构、数据的存储结构、抽象数据类型等有关概念，理解数据类型、数据结构和抽象数据类型间的关系。1、顺序存储结构中数据元素之间的逻辑关系是由（）表示，链表存储结构中的数据元素之间的逻辑关系是由（）表示的。A线性结构B非线性结构C存储位置D指针,.,14,典型题目解析基本概念,2、在存储数据时，通常不仅要存储各数据元素的值，还要存储（）3、在链式存储结构中，要求（）A、每个结点占用一片连续的存储区域B、所有结点占用一片连续的存储区域C、结点的最后一个域是指针类型D、每个结点有多少个后继就设多少个指针4、以下术语属于逻辑结构的是A、顺序表B、哈希表C、有序表D、单链表4+、以下与数据的存储结构无关的术语是（）A、循环队列B、链表C、散列表D、栈,.,15,典型题目解析基本概念,5、可以用（）、数据关系和基本操作定义一个完整的抽象数据类型A、数据元素B、数据对象C、原子类型D、存储结构6、对于数据结构的描述，不正确的是（）A、相同的逻辑结构对应的存储结构也相同B、数据结构由逻辑结构、存储结构和基本操作三方面组成C、数据结构基本操作的实现与存储结构有关D、数据的存储结构是数据的逻辑结构的机内实现7、抽象数据类型的表示与计算机内部表示和实现无关（）,.,16,典型题目解析算法和算法分析,考查算法的基本概念、特性、算法与程序的关系，掌握算法时间性能的度量方法、基本语句执行次数的计算，时间复杂度的计算和分析。8、当输入非法错误时，一个“好”的算法会进行适当处理，而不会产生难以理解的输出结果。这被称为算法的（）。A、可读性B、健壮性C、正确性D、有穷性9、算法的时间复杂度与（）有关A、问题规模B、待处理数据的初始状态C、算法的特性D、A和B9+、算法的时间复杂度与（）有关A、问题规模B、计算机硬件性能C、编译程序的质量D、程序设计语言,.,17,典型题目解析算法和算法分析,10、算法的时间复杂度是O（n2），表明该算法（）A、问题规模是n2B、执行时间等于n2C、执行时间与n2成正比D、问题规模与n2成正比11、下列说法错误的是（）算法原地工作的含义是指不需要任何额外的辅助空间在相同的规模n下，复杂度O（n）的算法在时间上总是优于复杂度O（2n）的算法所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上限同一个算法，实现语言级别越高，执行效率越低A、B、C、D、,.,18,典型题目解析算法和算法分析,12、假设时间复杂度为O(n2)的算法在有200个元素的数组上运行需要3.1ms，则在有400个元素的数组上需要（）ms。13、设有2个算法在同一机器上运行，其执行时间分别为100n2和2n，要使前者快于后者，n至少为（）14、n是描述问题的非负整数，下面程序段的时间复杂度是（）x2;while（xn/2）x2*x;A、O(log2n)B、O(n)C、O(nlog2n)D、O(n2)15、求整数n阶乘的算法如下，其时间复杂度是（）intfact(intn)if(n=1)return1;returnn*fact(n-1)A、O(log2n)B、O(n)C、O(nlog2n)D、O(n2),.,19,典型题目解析算法和算法分析,16、将下列函数按它们在n趋向无穷时，从小到大排序。n,n-n3+7n5,nlog2n,2n/2,n3,log2n,n1/2+log2n,(3/2)n,n!,n2+log2n17、下列程序段加下划线的语句执行（）次。for（m=0,i=1;in;i+）for（j=1;j=2*i;j+）m=m+1;A、n2B、3nC、n（n+1）D、n3,.,20,典型题目解析算法和算法分析,18、分析下列时间复杂度y=0；while(y+1)*(y+1)j)j+;elsei+;n为偶数，语句y=y+i*j的执行次数是多少？for(i=1;i1,.,21,.,22,第二章线性表,考纲分析线性表（一）线性表的定义和基本操作（二）线性表的实现1.顺序存储2.链式存储3.线性表的应用,.,23,典型题目解析顺序表,1、线性表的顺序存储结构是一种（）的存储结构。A、随机存取B、顺序存取C、索引存取D、散列存取2、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A、顺序表B、双链表C、带尾指针的单循环链表D、单链表3、在n个结点的线性表的数组实现中，算法的时间复杂度是O(1)的操作是（）。A、访问第i个结点和求第i个结点的直接前驱B、在第i个结点后插入一个新结点C、删除第i个结点D、以上都不对。,.,24,典型题目解析顺序表,4、关于线性表，下列说法正确的是（）A、线性表中每个元素都有一个直接前驱和一个直接后继B、线性表中的数据元素可以具有不同的数据类型C、线性表中数据元素的类型是确定的D、线性表中任意一对相邻的数据元素之间存在序偶关系5、顺序表的插入算法中，当n个空间已满时，可再申请增加分配m个空间，若申请失败，则说明系统没有（）可分配存储空间。A、m个B、m个连续的C、n+m个D、n+m个连续的,.,25,典型题目解析顺序表,6、将下算法改成一个既正确又高效的算法。StatusDelete(Sqlist,for(count=1;i+count-11）个元素的线性表的基本操作有4种：删除第一个元素；删除最后一个元素；在第一个元素前插入新元素；在最后一个元素后面插入新元素，则最好使用（）A、只设尾指针的循环单链表B、只设尾指针的非循环双链表C、只设头指针的循环双链表D、同时设置头指针和尾指针的循环单链表,.,32,典型题目解析链表,5、单链表中增加一个头结点的目的是（）A、使表中至少有一个结点B、标识表中首结点的位置C、方便运算的实现D、说明单链表是线性表的链式存储6、对于一个线性表既要求能够快速的插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（）A、顺序存储B、链式存储C、散列存储D、以上均可,.,33,典型题目解析链表,7、若要在O（1）的时间内实现2个循环单链表的首尾相连，则两个循环单链表应各设一个指针，分别指向（）A、各自的头结点B、各自的尾结点C、各自的第一个元素节点D、一个表的头结点，一个表的尾结点8、在双链表中，指针pa所指结点后面插入pb结点，执行的语句序列是（）pb-next=pa-next;pb-prior=pa;pa-next=pb;pa-next-prior=pb;A、1234B、4321C、3412D、1432,.,34,9、设线性表非空，（）可以在O(1)的时间内在表尾插入一个新结点。A、带头结点的单链表，有一个链表指针指向头结点B、带头结点的循环单链表，有一个链表指针指向表的头结点C、不带头结点的单链表，有一个链表指针指向表的第一个结点D、不带头结点的循环单链表，有一个链表指针指向表中某个结点（除第一个结点外）9+、假设有一个没有头指针的单链表，一个指针指向此单链表中间的一个结点（不是第一个，也不是最后一个），请将改结点从单链表中删除。,典型题目解析链表,.,35,典型题目解析链表,10、已知非空线性链表由list指示，结点结构为data，link。编写算法，将链表中数据域最小的结点移到链表最前面。要求：不得额外申请新结点。11、给定一个带头结点的单链表，设head为头指针，设计算法按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间。要求：不允许使用额外的存储空间。12、设计算法，将双向链表中结点p与其后继结点交换位置。,.,36,典型题目解析链表,13、已知L为单链表的头结点地址，表中共有m（m3）个结点，从表中第i（1inext=h;C、s-next=h;h-next=sD、s-next=h-next;h-next=s;,.,46,典型题目解析栈,12、消除递归不一定使用栈。（）13、任何一个递归过程都可以转换成非递归过程。（）14、只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈。（）15、用单链表表示栈，栈顶设在链表的（）16、解决Hanoi塔问题的递归算法，其时间复杂度是（）17、从运行时间上看，通常一个递归函数要比非递归函数（）A、快一些B、慢一些C、相同D、无法比较,.,47,典型题目解析栈,18、有5个元素，其入栈次序为A、B、C、D、E，在各种可能的出栈序列中，第一个出栈元素为C且第二个出栈元素为D的出栈序列有哪几个？19、元素abcdef依次进栈，允许进栈、出栈交替进行，但不允许连续三次进行出栈操作，则不可能得到的出栈序列是（）A、dcebfaB、cbdaefC、bcaefdD、afedcb20、元素abcde依次进栈，允许进栈、出栈交替进行，则以d为首的出栈序列是（）,.,48,典型题目解析栈,21、设计一个算法，判断一个算术表达式中的括号是否匹配。算术表达式保存在带头结点的单循环链表中，每个结点有两个域：ch和link，其中ch域为字符类型。22、利用两个栈S1和S2模拟一个队列，已知栈的三个运算定义如下：PUSH（st，x）元素x入st栈；POP（st，x）出栈元素赋值给x；Sempty（st）判断是否为空。如何利用栈的运算来实现队列的三个运算：入队enqueue，出队dequeue和判断队列是否为空queue_empty。,.,49,典型题目解析队列,1、栈和队列的区别在于（）A、逻辑结构不一样B、存储结构不一样C、包含运算不一样D、插入、删除限定不一样2、若用一个长度为6的数组来实现循环队列，且当前rear和front的值分别为0和3，则队列中删除一个元素，再添加2个元素后，rear和front的值分别为（）。3、最不适合用作链队列的链表是（）A只带队首指针的非循环双链表B只带队首指针的循环双链表C只带队尾指针的循环双链表D只带队尾指针的循环单链表,.,50,典型题目解析队列,4、循环队列的存储空间为数组A21，front指向队首元素的前一位置，rear指向队尾元素。假设当前front和rear的值分别是8和3，则队列的长度是（）5、下列更适合表示队列的链表结构是（）A、单链表B、单循环链表C、双链表D、双循环链表6、如图所示为一个元素类型为字符型的环形队列，front和rear分别指向队首和队尾，则所表示的队列为（）A、ThefB、flowerisC、beautifulThefD、eautifulThef,rear,front,.,51,典型题目解析队列,7、执行（）操作时，需要队列作为辅助的存储结构A、深度优先遍历图B、广度优先遍历图C、散列查找D、遍历二叉树8、用不带头结点的单链表存储队列，其对头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）A、仅修改队头指针B、仅修改队尾指针C、队头队尾可能都要修改D、C去掉可能9、在带头结点的链队列中，队头指针应该指向（）10、已知输入序列为abcd，经过输出受限的双向队列后能得到的输出序列有（）AdacbBcadbCdbcaDbdacEallwrong,.,52,典型题目解析队列,11、若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双段队列得到的是（）A、1234B、4132C、4231D、421312、设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后入队Q，若出队序列为e2,e4,e3,e6,e5,e1，则栈S的容量至少应该是（）13、队列的队首和队尾分别指向最早进队，最后进队的元素，为使第一个进队元素在A0，front和rear分别指向?A、0,0；B、0,n-1；C、n-1,0;D、n-1,n-1;,.,53,典型题目解析队列,14、某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素abcde依次入队后再进行出队操作，则不可能得到的出队序列是A、bacdeB、dbaceC、dbcaeD、ecbad15、关于队列的叙述中，正确的是（）A、只能使用数组构成循环队列B、可以使用数组或者链表构成循环队列C、循环队列没有元素数量限制D、可以将栈看成是一个特殊的队列,.,54,典型题目解析队列,16、若以1、2、3、4作为双端队列的输入序列，试分别求以下条件的输出序列：能由输入受限的双端得到，但不能由输出受限的双端队列得到的输出序列；能由输出受限的双端得到，但不能由输入受限的双端队列得到的输出序列；既不能由输入受限的双端得到，也不能由输出受限的双端队列得到的输出序列；17、利用两个栈S1、S2模拟一个队列时，如何利用栈的操作实现入队、出队及判断队列是否为空。18、试用一个不带头结点的循环链表表示队列，说明链表指针指向何处？如何入队、出队及判断队列为空？,.,55,典型题目解析队列,19、设栈S中有2n个元素，从栈顶到栈底的元素依次为a2n,a2n-1,a1，要求通过一个循环队列重新排序站中元素，使得从栈顶到栈底的元素依次为a2n,a2n-2,a2,a2n-1,a2n-3,a1，设计算法实现，要求空间复杂度和时间复杂度为O(n)。,.,56,典型题目解析数组,1、二维数组S-3.5,0.10含有的元素个数是（）。2、二维数组A的每个元素由6个字符组成，行下标的范围是08，列下标的范围是从09，则存放A需要（）字节；A的第8列和第5行共占（）字节；若A按行优先方式存储，元素A85的起始地址与当A按列优先方式存储时的（）元素的起始地址一致。3、四维数组A8,9,10,11采用行序为主序的方式从地址A0,0,0,0开始存放，假设每个元素占用存储空间大小为L，则元素A3,4,8,10的存放地址是（）。,.,57,典型题目解析矩阵的压缩存储,特殊矩阵是指矩阵中有较多相同的元素且其分布有一定的规律；压缩存储的基本思想是：为多个相同的元素分配一个存储空降；对零元素不分配存储空间。1、设AN,N是对称矩阵，将其下三角包括对角线按行序存储到一维数组TN(N+1)/2中，则上三角元素Aij对应数组元素T的下标是（）2、对特殊矩阵采用压缩存储的目的主要是（）A、表达变的简单B、对矩阵元素的存取变得简单C、去掉矩阵中的多余元素D、减少不必要的存储空间,.,58,典型题目解析矩阵的压缩存储,3、设有一个n行n列的对称矩阵A，将其下三角部分按行存放在一维数组B中，A00存放于B0中，则第i行的对角元素Aii存放于B中（）处。4、若将n阶下三角矩阵A按列优先顺序压缩存放在一维数组B1.n(n+1)/2中，则存放到Bk中的非零元素aij的下标i,j与k的对应关系是（）。5、将一个A1.100,1.100的三对角矩阵，按行优先存入一维数组B1.298中，则A中元素A66,65在B数组中的位置K为（）。,.,59,第五章树和二叉树,考纲分析（一）树的基本概念（二）二叉树1.二叉树的定义及其主要特征2.二叉树的顺序存储结构和链式存储结构3.二叉树的遍历4.线索二叉树的基本概念和构造（三）树、森林1.树的存储结构2.森林与二叉树的转换3.树和森林的遍历（四）树与二叉树的应用1.二叉排序树2.平衡二叉树3.哈夫曼（Huffman）树和哈夫曼编码,.,60,典型题目解析树的基本概念,1、假定一颗度为3的树中结点数为50，则其最小高度应为（）。2、下列说法中，（）是正确的。A、二叉树就是度为2的树B、二叉树中不存在度大于2的结点C、二叉树是有序树D、二叉树中每个结点的度均为23、二叉树是一棵（）A、度为2的有序树B、所有结点度均为2的有序树C、度为2的无序树D、所有结点度均为2的无序树,.,61,典型题目解析树的基本概念,4、下列情况中，可称为二叉树的是（）A、每个结点至多有两棵子树的树B、哈夫曼树C、每个结点只有一棵树D、每个结点至多有两棵子树的有序树5、下列结论中正确的是（）只有一个结点的二叉树的度为0二叉树的度为2二叉树的左右子树可任意交换深度为k的完全二叉树的结点个数小于或等于深度相等的满二叉树A、B、C、D、,.,62,典型题目解析树的基本概念,6、二叉树有n个结点，则其深度为（）。A、n-1B、nC、log2n+1D、不能确定7、若完全二叉树的结点个数为100，则第60个结点的度为（）8、一棵有124个叶子结点的完全二叉树最多有（）个结点。9、一棵满二叉树中共有n个结点，其中有m个叶子结点，深度为h，则（）A、n=h+mB、h+m=2nC、m=h-1D、n=2h-110、设二叉树有2n个结点，则对于mK），则该森林中有（）棵树。A、KB、NC、N-KD、116、设树T的度为4，其中度1,2,3和4的结点个数分别为4,2,1,1，则T中的叶子数为（）17、一棵完全二叉树中共有626个结点，则叶子结点的个数为（）A、311B、312C、313D、31418、将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度为（）A、4B、5C、6D、7,.,65,典型题目解析树的基本概念,19、一棵共有n个结点的树，其中所有分支结点的度均为k，则该树中叶子结点的数目为多少？20、将有关二叉树的概念推广到三叉树，则含有244个结点的完全三叉树的高度是多少？含有244个叶子结点的完全三叉树的高度是多少？21、对于一棵含有N个结点的k叉树，请讨论其可能的最大高度和最小高度。,.,66,典型题目解析树的基本概念,22、一棵高度为h的完全k叉树有如下性质：第h层上的结点都是叶结点，其余各层上每个结点都有k棵非空子树。如果按层次自顶向下、自左向右顺序从1开始对全部结点进行编号，试问：最多有多少个结点？最少有多少个结点？结点q的第i个孩子结点的编号为多少？结点q的双亲结点的编号为多少？,.,67,典型题目解析二叉树的存储结构,23、以下说法中，（）是正确的。A、完全二叉树中，叶结点双亲的左兄弟结点一定不是叶结点B、任何一棵二叉树中，终端结点等于度为2的结点数减1C、完全二叉树不适合用顺序存储结构存储D、结点按层次编号的二叉树，第i个结点的左孩子（如果存在）编号为2i24、若用一维数组保存一个深度为5，结点个数为10的二叉树，数组的长度至少为（）A、10B、16C、31D、63,.,68,典型题目解析二叉树的存储结构,25、一棵有n个结点的二叉树采用顺序存储结构，存储在一维数组A0n-1中，结点Ai的左孩子是（）A、A2iB、A2i+1C、A2i+2D、A2i+326、在顺序存储的二叉树中，编号为i和j的两个结点在同一层上的条件是什么？如何求i和j的最近的共同祖先？27、设度为m的树采用多重链表存储，每个结点有m+1个域，其中有1个数据域，m个指向孩子的指针。则空指针的数目是多少？说明这种存储方式的利弊。,.,69,典型题目解析二叉树的存储结构,28、已知深度为h的二叉树以一维数组BT1.2h-1作为存储结构。编写算法求该二叉树的叶子结点个数。为简单起见，假设二叉树中元素结点为非零整数。29、设计算法将一棵以二叉链表存储的二叉树按顺序方式存储到一维数组中。,.,70,典型题目解析二叉树的遍历,30、一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（）A、CABDEFGB、BCDAEFGC、DACEFBGD、ADBCFEG31、现有先序遍历二叉树的结果为ABCD，则有（）种不同的二叉树可以得到这一结果。A、12B、13C、14D、1532、二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A、空或者只有一个结点B、高度等于结点数C、任一结点无左孩子D、任一结点无右孩子,.,71,典型题目解析二叉树的遍历,33、设n和m是一棵二叉树上的两个结点，在中序遍历时n在m前的条件是（）A、n在m的右方B、n是m的祖先C、n在m的左方D、n是m的子孙34、下面说法正确的是（）A、深度为k的二叉树最多有2k-1个结点，最少有k个结点B、二叉树中一定存在度为2的结点C、对二叉树的遍历指的是先序、中序或后续中的一种D、构造线索二叉树的目的是为了能方便的找到结点的双亲,.,72,典型题目解析二叉树的遍历,35、二叉树的叶子结点在先序、中序和后序的遍历序列中相对位置（）A、不发生改变B、发生改变C、不能确定D、都不对36、若二叉树采用二叉链表存储，要交换其所有分支结点左、右子树的位置，利用（）遍历方法最合适。A、先序B、中序C、后序D、层次,.,73,典型题目解析二叉树的遍历,37、判断两棵二叉树是否相似。所谓相似，是指要么它们都为空的或都是有一个根结点，要么他们的左右子树均相似。38、在二叉树中查找值为x的结点。39、求二叉树的深度。40、求二叉树中各种结点个数。,.,74,典型题目解析二叉树的遍历,41、一个二叉树以二叉链表存储，求二叉树第k层上叶子结点的个数。42、设计算法统计二叉树中每一层结点个数。43、设计算法求二叉树的宽度。44、一棵二叉树以顺序存储在数组bt1.n中，写出先序的非递归算法。45、已知二叉树采用二叉链表存储，设计算法以输出二叉树中根结点到每个叶子结点的路径。46、一棵二叉链表存储的二叉树，编写程序输入从根结点到叶结点的最长路径上的所有结点。,.,75,典型题目解析二叉树的遍历,47、证明：已知一棵二叉树的前序序列和中序序列，则可唯一确定二叉树。48、编写算法根据二叉树的先序序列和中序序列建立二叉树。49、编写算法，判断一棵二叉树是否为完全二叉树。50已知一棵二叉树的每个结点，要其么左右子树为空要么皆不为空。又知该二叉树的前序遍历序列为JFDBACEHXIK，后序遍历序列ACBEDXIHFKJ，试构造该二叉树。51、已知二叉树的层次遍历序列为ABCDEFGHIJ，中序遍历序列为DBGEHACIJF，试构造二叉树。,.,76,典型题目解析线索二叉树,48、具有n个结点的线索二叉树共有（）个线索。49、一棵左子树为空的二叉树在前序线索化后，其中空链域的个数是（）。50、一棵左右子树均不为空的二叉树在前序线索化后，其中空链域的个数是（）。51、二叉树在线索化后仍不能有效求解的问题是（）A、前序线索二叉树中求前序后继B、中序线索二叉树中求中序后继C、中序线索二叉树中求中序前驱D、后序线索二叉树中求后序后继,.,77,典型题目解析线索二叉树,52、关于线索二叉树，下列说法中不正确的是（）A、中序线索二叉树中，若结点有右孩子，则其后继是它的右子树的左分支末端的结点。B、线索二叉树利用二叉树的n+1个空指针来存放其前驱和后继信息C、在线索二叉树中，每个结点通过线索都可以直接找打它的前驱和后继D、中序线索二叉树中，若结点有左孩子，则其前驱是它的左子树的右分支末端结点。,.,78,典型题目解析线索二叉树,53、线索二叉树是一种（）结构A、逻辑B、逻辑和存储C、物理D、线性54、（）线索二叉树的遍历仍需要栈的支持55、线索二叉树中的线索指的是（）A、左孩子B、遍历C、指针D、标识56、若X是二叉树中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（）A、X的双亲B、X的右子树中最左结点C、X的左子树中最右结点D、X的左子树中最右叶子结点,.,79,典型题目解析树、森林和二叉树,57、讨论树、森林和二叉树的关系，目的是为了（）A、借助二叉树上的运算方法去实现对树的一些运算B、将树、森林按二叉树的存储方式进行存储并利用二叉树的算法解决树的有关问题C、将树、森林转换成二叉树D、体现一种技巧，实际意义不大58、深度为h的满二叉树对应的森林由（）棵树构成。A、1B、log2hC、h/2D、h,.,80,典型题目解析树、森林和二叉树,58、设F是一个森林，B是由F转换得到的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（）个。A、n-1B、nC、n+1D、n+259、设x是树T中的一个非根结点，B是T所对应的二叉树。在B中，x是其双亲的右孩子，则下列结论正确的是（）A、在树T中，x是其双亲的第一个孩子B、在树T中，x一定无右兄弟C、在树T中，x一定是叶子结点D、在树T中，x一定有左兄弟,.,81,典型题目解析树、森林和二叉树,60、已知一个森林的前序序列为ABCDEFGHIJKLMNO，后序序列为CDEBFHIJGAMLONK，求此森林。61、如果在表示树的孩子兄弟链表中有6个空的左指针域，7个空的右指针域，5个结点左右指针域都为空，则该二叉树叶子结点个数为多少？,.,82,典型题目解析哈弗曼树,62、一棵huffman树中共有215个结点，对其进行huffman编码，可以得到多少个不同的编码？63、下述编码中（）不是前缀编码。A、(00,01,10,11)B、(0,1,00,11)C、(0,10,110,111)D、(1,01,000,001)64、为5个使用频率不等的字符设计哈弗曼编码，不可能的方案是（）。A、000,001,010,011,1B、0000,0001,001,01,1C、000,001,01,10,11D、00,100,101,110,111,.,83,典型题目解析哈弗曼树,65、设计哈弗曼编码的长度不超过4，若已经对两个字符编码为1和01，则最多还可以为（）个字符编码。A、2B、3C、4D、566、假设字符集a,b,c,d,e中各字符出现的频率分别为4,21,7,14,31，为该字符集构造哈弗曼编码，则字符集编码的总码数为（）。A、12B、13C、14D、1567、若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点个数为（）A、n-1B、n/m-1C、(n-1)/(m-1)D、(n+1)/(m+1)-1,.,84,典型题目解析哈弗曼树,68、已知某电文中出现了10种不同的字符，每个字符出现的频率分别为A:8,B:5,C:3,D:2,E:7,F:23,G:9,H:11,I:2,J:35，现在对这段电文用三进制进行编码（编码由0、1、2组成），问电文编码的总长度至少有多少位？69、设有7个从小到大的有序序列，分别含有10、30、40、50、50、60和90个整数，现要通过6次合并将它们合并成一个有序表，问应该按怎样的次序进行这6次合并，是的总的比较次数最少？,.,85,典型题目解析历年统考真题2011,4、一棵完全二叉树有768个结点，则该二叉树中叶子结点的个数是（）A、257B、258C、384D、3855、若一棵二叉树的前序遍历序列和后序遍历序列分别是1234和4321，则该二叉树的中序遍历序列是（）A、1234B、2341C、3241D、43216、已知一棵树有2011个结点，其中叶结点个数为116，该树对应的二叉树中无右孩子的结点个数为（）A、115B、116C、1895D、1896,.,86,典型题目解析历年统考真题2010,3、下列线索二叉树中，符合后序线索二叉树的是（）,.,87,典型题目解析历年统考真题2010,4、在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的的结点，10个度为1的结点，则树T的叶子结点个个数为（）A、41B、82C、113D、1225、对于n个权值均不相同的字符构造huffman树，下列关于该树的描述中，错误的是（）A、该树一定是一棵完全二叉树B、该树一定没有度为1的结点C、树中两个权值最小的结点一定是兄弟结点D、树中任一非叶子结点的权值一定不小于下一层任一结点的权值。,.,88,典型题目解析历年统考真题2009,3、给定二叉树如图所示，设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树，若遍历后的结点序列为3175624，则其遍历方式为（）A、LRNB、NRLC、RLND、RNL4、下列二叉排序树中，满足平衡二叉树的是（）,.,89,典型题目解析历年统考真题2009,5、一直以棵完全二叉树的第6层有8个叶子结点，则该完全二叉树的结点个数最多是（）A、39B、52C、111D、1196、森林转换成为的二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是（）1父子关系2兄弟关系3u的父节点和v的父结点是兄弟关系A、只有2B、1和2C、1和3D、123,.,90,典型题目解析递归,1、递归的本质递归：调用程序自身的算法，称之为递归。特点是思路明确、代码简洁，在树、图等问题中有广泛的应用。同时，递归算法纷繁复杂，且实现过程对用户透明，使得理解变得较困难。数据的结构关系虽然有四种，但实质上数据间的关系只有前驱、后继的顺序关系。其常见的物理结构为顺序结构和链式结构，几乎所有的数据结构都可以用链式结构描述。这就使得四种结构关系在逻辑和物理上都可以有统一的表现形式。,.,91,典型题目解析递归,对于线性关系，可以理解成由第一个元素和剩余的元素组成，而剩余的元素又是一个相对较小的线性关系。对于树形结构，是由根和除根之外的若干棵子树组成。对于图形结构可以理解成某一顶点及所有后继结点为起始点形成的子图所构成。综上所述，这些数据结构都是由某一个元素和所有后继构成的相同的数据结构所组成。这说明，数据结构的定义基本上是递归的，递归是众多数据结构构造和逻辑意义上的统一体。,.,92,典型题目解析递归,2、递归算法的模型递归算法由两部分组成：最小问题，称为基本项；原问题与子问题的关系，称为递归项（递归项包含两部分内容，一是可以继续分解的子问题；二是不能继续划分的子问题，称为有解子问题）。一般形式如下：if（最小问题）基本项行为；else有解子问题的处理；可继续划分的子问题1，2n；最小子问题决定了递归的出口；不能划分的子问题即有解子问题是按问题要求的处理，如输出等。递归主要研究是有解子问题。,.,93,典型题目解析递归,至于可继续划分的子问题，则被写成同样形式的递归调用语句，且，有几个这样的子问题就有几条递归语句。体现了子问题与原问题的处理方式，只是问题规模变小。在数据结构中一般有三种情况的划分：可划分为一个子问题的：线性表、二叉排序树的查找；可划分为一个子问题的：广义表、二叉树；可划分为一个子问题的：图。根据递归项中有解子问题的处理顺序，递归可以划分为前序递归、中序递归和后序递归。,.,94,典型题目解析递归,3、题目分类例1、有一个不带头结点的单链表，输出以h为头指针的单链表中最大结点值。例2、假设二叉树采用二叉链表存储结构，编写一个算法，给出二叉树中一个非根节点（由p指针所指），求它的双亲结点。例3、利用一个二叉树遍历的思想，设计一个算法判断二叉树是否为平衡二叉树。如果是，设计算法求出每个结点的平衡因子。例4、编写算法根据先序和中序序列来确定一棵二叉树。,.,95,典型题目解析树的查找,43、用n个键值构造一棵二叉排序树，其最低高度为（）。44、在含有n个结点的二叉排序树中查找一个关键字码，最多进行（）次比较。A、n/2B、log2nC、log2n+1D、n45、在二叉排序树上查找关键字码28的结点，则依次比较的关键字码可能是（）A、30,36,28B、38,48,28C、48,18,38,28D、60,30,50,40,38,36,.,96,典型题目解析树的查找,46、具有5层的平衡二叉树至少有（）个结点。47、在含有12个结点的平衡二叉树上查找结点35（假设存在），则依次比较的关键字可能是A46,36,18,20,28,35B47,37,18,27,36,35C27,48,39,43,37,35D15,45,55,3548、构造平衡二叉树20.35.40.15.30.25.38,.,97,第六章图,考试大纲（一）图的基本概念（二）图的存储及基本操作1.邻接矩阵法2.邻接表法（三）图的遍历1.深度优先搜索2.广度优先搜索（四）图的基本应用1.最小（代价）生成树2.最短路径3.拓扑排序4.关键路径,.,98,典型题目解析图的概念,1、n个顶点的强连通图至少有（）条边，其形状是（）。A、nB、n+1C、n-1D、n(n-1)E、无回路F、有回路G、环状H、树状2、图的生成树（），n个顶点的生成树有（）条边。A、唯一B、不唯一C、唯一性不确定D、nE、n+1F、n-13、G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。A、6B、7C、8D、9,.,99,典型题目解析图的概念,4、以下关于有向图的说法中，正确的是A、强连通图中任何顶点到其他所有顶点都有弧B、有向完全图一定是强连通图C、有向图中某顶点的入度等于出度D、有向图边集的子集和顶点集的子集可构成原有有向图的子图5、黑板上图的强连通分量的个数是（）6、无向图G有16条边，度为4的顶点有3个，度3的顶点有4个，其余顶点的度小于3，则图G至少有（）个顶点。A、10B、11C、12D、13,.,100,典型题目解析图的概念,7、设无向图G=（V,E）和G=（V,E），如果G是G的生成树，则下面的说法中错误的是（）A、G是G的子图B、G为G的连通分量C、G为G的极小连通子图且V=VD、G是G的一个无环子图8、无向图的邻接矩阵是一个（），有向图的邻接矩阵是一个（）。A、上三角矩阵B、下三角矩阵C、对称矩阵D、无规律9、一个图的邻接矩阵表示是（）的，邻接表表示是（）的。A、唯一B、不唯一,.,101,典型题目解析图的存储,10、具有n个顶点e条边的无向图采用邻接矩阵存储，则零元素的个数是（）A、eB、2eC、n2-eD、n2-2e11、在有向图的邻接表存储结构中，顶点v在边表中出现的次数是（）A、顶点v的度B、顶点v的出度C、顶点v的入度D、依附于顶点v的边数12、假设一个有向图具有n个顶点e条边，该有向图采用邻接表存储，则删除与顶点i相关联的所有边的时间复杂度是（）A、O(n)B、O(e)C、O(n+e)D、O(n*e),.,102,典型题目解析图的存储,13、用邻接表存储图所用的空间大小（）A、与图的顶点数和边数都有关B、只与图的边数有关C、只与图的顶点数有关D、与边数的平方有关14、图G是n个顶点的无向完全图，则下列说法正确的有（）A、G的邻接多重表需要n(n-1)个边结点和n个顶点结点B、G的连通分量个数最少C、G为连通图D、G所有顶点的度的总和为n(n-1),.,103,典型题目解析图的存储,15、若一个有向图有拓扑排序序列，则其邻接矩阵必然为（）矩阵A、对称B、稀疏C、三角D、一般16、在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为（）A、nB、n+eC、n2D、n317、n个顶点的无向图的邻接表中，最多有（）个表结点。A、n2B、n（n-1）C、n（n+1）D、n（n-1）/2,.,104,典型题目解析图的存储,10、无向图G含有n个结点e条边，每个顶点信息（假设只存储编号）占用2个字节，每条边的权值信息占用4个字节，每个指针占用4个字节，计算采用邻接矩阵和邻接表分别占用多少存储空间？11、设有向图G采用邻接表存储，设计算法求图G中每个顶点的入度。12、设计算法，将一个无向图的邻接表转换成邻接矩阵。,.,105,典型题目解析图的遍历,13、深度优先遍历方法遍历一个有向无环图，并在深度优先遍历算法中按退栈次序打印出相应的顶点，则输出的顶点序列是A、逆拓扑有序B、拓扑有序C、无序D、顶点编号次序14、无向图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、abecdfB、acfebdC、aebcfdD、aedfcb15、若要求连通图的生成树最小，则采用（）方法。A、深度优先遍历B、广度优先遍历C、Prim算法D、Kruskal算法,.,106,典型题目解析图的遍历,16、下面不正确的是（）A、图的遍历是从给定源点出发每个顶点仅被访问一次B、图的遍历有深度遍历和广度遍历C、图的深度遍历不适合有向图D、图的深度遍历为一个递归过程17、若一个无向图含有n个顶点和e条边，采用临接表存储，则深度优先遍历的时间复杂度为（）18、采用邻接表存储的无向图，深度优先搜索遍历的时间复杂度为（）A、O(n2)B、O(e2)C、O(n+e)D、O(e),.,107,典型题目解析图的遍历,16、对一个图进行遍历可以得到不同遍历序列，那么导致遍历序列不唯一的因素有哪些？17、设计图的深度优先搜索编写算法，判断以邻接表存储的有向图中是否存在由顶点vi到顶点vj的路径(i，j不等)。18、基于图的广度优先搜索编写算法，判断以邻接表存储的有向图中是否存在由定点vi到顶点vj的路径(i，j不等)。,.,108,典型题目解析图的应用,19、在图采用邻接表存储时，