数据结构辅导讲义前章课件

数据结构辅导讲义栾晓春栾晓春 为解决解决计算机与打印机之算机与打印机之间速度不匹配速度不匹配问题，通常，通常设置一个打印数置一个打印数据据缓冲区，主机将要冲区，主机将要输出的数据依次写入出的数据依次写入该缓冲区，而打印机冲区，而打印机则依次依次从从该缓冲区中取出数据。冲区中取出数据。该缓冲区的冲区的逻辑结构构应该是（是（）。（全国）。（全国统考考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）Adcebfa Bcbdaef Cdbcaef Dafedcb某某队列允列允许在其两端在其两端进行入行入队操作，但操作，但仅允允许在一端在一端进行出行出队操作，操作，则不可能得到的不可能得到的顺序是（序是（）。（全国）。（全国统考考2010）Abacde Bdbace Cdbcae Decbad元素元素abcde依次依次进入初始入初始为空的空的栈中，若元素中，若元素进栈后可停留、可出后可停留、可出栈，直到所有元素都出直到所有元素都出栈，则在所有可能的出在所有可能的出栈序列中，以元素序列中，以元素d开开头的的序列个数是序列个数是（）。（全国）。（全国统考考2011）A3 B4 C5 D6 已知循已知循环队列存放在一列存放在一维数数组A0.n-1，且，且队列非空列非空时front和和rear分分别指向指向队列的列的队头元素和元素和队尾元素。若初始尾元素。若初始时队列列为空，且要求第一空，且要求第一个入个入队的元素存的元素存储在在A0处，则初始初始时front和和rear的的值分分别是（是（）。）。（全国（全国统考考2011）A0，0 B0，n-1 Cn-1，0 Dn-1，n-1 已知操作符包括已知操作符包括+，-，*，/，(和和)，将中，将中缀表达式表达式a+b-a*(c+d)/e-f)+g转化化为等价的后等价的后缀表达式表达式ab+acd+e/f-*-g+时，用，用栈来存来存放放暂时还不能确定的运算次序的操作符，若不能确定的运算次序的操作符，若栈初始初始时为空，空，则转换过程中同程中同时保存在保存在栈中的操作符的最大个数是（中的操作符的最大个数是（）。（全国）。（全国统考考2011）A5 B7 C8 D11第一章绪论考考纲分析分析1.理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。2.掌握基本的数据处理原理和方法的基础上，能够对算法进行基本的时间复杂度与空间复杂度进行设计与分析。3.能够选择合适的数据结构和方法进行问题求解，具备采用C 或C+或 JAVA 语言设计与实现算法的能力。红楼梦中贾家的人物关系典型题目解析基本概念本章本章题目主要考目主要考查数据数据结构的基本概念，构的基本概念，要求深刻理解数据元素、数据的要求深刻理解数据元素、数据的逻辑结构、构、数据的存数据的存储结构、抽象数据构、抽象数据类型等有关概型等有关概念，理解数据念，理解数据类型、数据型、数据结构和抽象数据构和抽象数据类型型间的关系。的关系。1、顺序存序存储结构中数据元素之构中数据元素之间的的逻辑关关系是由（系是由（）表示，）表示，链表存表存储结构中的数构中的数据元素之据元素之间的的逻辑关系是由（关系是由（）表示的。）表示的。A线性性结构构B非非线性性结构构C存存储位置位置D指指针典型题目解析基本概念2、在存、在存储数据数据时，通常不，通常不仅要存要存储各数据元各数据元素的素的值，还要存要存储（）3、在、在链式存式存储结构中，要求（）构中，要求（）A、每个、每个结点占用一片点占用一片连续的存的存储区域区域B、所有、所有结点占用一片点占用一片连续的存的存储区域区域C、结点的最后一个域是指点的最后一个域是指针类型型D、每个、每个结点有多少个后点有多少个后继就就设多少个指多少个指针4、以下、以下术语属于属于逻辑结构的是构的是A、顺序表序表B、哈希表、哈希表C、有序表、有序表D、单链表表4+、以下与数据的存、以下与数据的存储结构无关的构无关的术语是（）是（）A、循、循环队列列B、链表表C、散列表、散列表D、栈 典型题目解析基本概念5、可以用（）、数据关系和基本操作定、可以用（）、数据关系和基本操作定义一个完一个完整的抽象数据整的抽象数据类型型 A、数据元素、数据元素B、数据、数据对象象 C、原子、原子类型型D、存、存储结构构6、对于数据于数据结构的描述，不正确的是（）构的描述，不正确的是（）A、相同的、相同的逻辑结构构对应的存的存储结构也相同构也相同B、数据、数据结构由构由逻辑结构、存构、存储结构和基本操作三构和基本操作三方面方面组成成C、数据、数据结构基本操作的构基本操作的实现与存与存储结构有关构有关D、数据的存、数据的存储结构是数据的构是数据的逻辑结构的机内构的机内实现7、抽象数据、抽象数据类型的表示与型的表示与计算机内部表示和算机内部表示和实现无关（）无关（）典型题目解析算法和算法分析考考查算法的基本概念、特性、算法与程序的关系，算法的基本概念、特性、算法与程序的关系，掌握算法掌握算法时间性能的度量方法、基本性能的度量方法、基本语句句执行次数行次数的的计算，算，时间复复杂度的度的计算和分析。算和分析。8、当、当输入非法入非法错误时，一个，一个“好好”的算法会的算法会进行行适当适当处理，而不会理，而不会产生生难以理解的以理解的输出出结果。果。这被被称称为算法的（）。算法的（）。A、可、可读性性B、健壮性、健壮性C、正确性、正确性D、有、有穷性性9、算法的、算法的时间复复杂度与（）有关度与（）有关A、问题规模模B、待、待处理数据的初始状理数据的初始状态C、算法的特性、算法的特性D、A和和B9+、算法的、算法的时间复复杂度与（）有关度与（）有关A、问题规模模B、计算机硬件性能算机硬件性能C、编译程序的程序的质量量D、程序、程序设计语言言算法的健壮性也称为鲁棒性，指的是算法对非法输入的抵抗能力。鲁棒性原是统计学中的一个专门术语，20世纪70年代初开始在控制理论的研究中流行起来，用以表征控制系统对特性或参数摄动的不敏感性。典型题目解析算法和算法分析10、算法的、算法的时间复复杂度是度是O（n2），表明），表明该算法（算法（）A、问题规模是模是n2 B、执行行时间等于等于n2C、执行行时间与与n2成正比成正比D、问题规模与模与n2成正比成正比11、下列、下列说法法错误的是（）的是（）算法原地工作的含算法原地工作的含义是指不需要任何是指不需要任何额外的外的辅助空助空间在相同的在相同的规模模n下，复下，复杂度度O（n）的算法在）的算法在时间上上总是是优于复于复杂度度O（2n）的算法）的算法 所所谓时间复复杂度是指最坏情况下，估算算法度是指最坏情况下，估算算法执行行时间的一个上限的一个上限 同一个算法，同一个算法，实现语言言级别越高，越高，执行效率越低行效率越低A、B、C、D、典型题目解析算法和算法分析12、假、假设时间复复杂度度为O(n2)的算法在有的算法在有200个元素的个元素的数数组上运行需要上运行需要3.1ms，则在有在有400个元素的数个元素的数组上需上需要（）要（）ms。13、设有有2个算法在同一机器上运行，其个算法在同一机器上运行，其执行行时间分分别为100n2和和2n，要使前者快于后者，要使前者快于后者，n至少至少为（）（）14、n是描述是描述问题的非的非负整数，下面程序段的整数，下面程序段的时间复复杂度是（）度是（）x 2;while（xn/2）x 2*x;A、O(log2n)B、O(n)C、O(nlog2n)D、O(n2)15、求整数、求整数n阶乘的算法如下，其乘的算法如下，其时间复复杂度是（）度是（）int fact(int n)if(n=1)return 1;return n*fact(n-1)A、O(log2n)B、O(n)C、O(nlog2n)D、O(n2)典型题目解析算法和算法分析16、将下列函数按它、将下列函数按它们在在n趋向无向无穷时，从小到大排序。，从小到大排序。n,n-n3+7n5,nlog2n,2n/2,n3,log2n,n1/2+log2n,(3/2)n,n!,n2+log2n17、分析下列、分析下列时间复复杂度度y=0；while(y+1)*(y+1)=n)y=y+1;i=1;j=0;while(i+jj)j+;else i+;n为偶数，偶数，语句句y=y+i*j的的执行次数是多少？行次数是多少？for(i=1;i=n;i+)if(2*i=n)for(j=2*i;j1第二章线性表考考纲分析分析线性表性表（一）（一）线性表的定性表的定义和基本操作和基本操作（二）（二）线性表的性表的实现 1.顺序存序存储 2.链式存式存储 3.线性表的性表的应用用典型题目解析顺序表1、线性表的性表的顺序存序存储结构是一种（构是一种（）的存）的存储结构。构。A、随机存取、随机存取B、顺序存取序存取C、索引存取、索引存取D、散列存取、散列存取2、若某、若某线性表最常用的操作是存取任一指定序号的元性表最常用的操作是存取任一指定序号的元素和在最后素和在最后进行插入和行插入和删除运算，除运算，则利用（利用（）存）存储方方式最式最节省省时间。A、顺序表序表B、双、双链表表C、带尾指尾指针的的单循循环链表表 D、单链表表3、在、在n个个结点的点的线性表的数性表的数组实现中，算法的中，算法的时间复复杂度是度是O(1)的操作是（）。的操作是（）。A、访问第第i个个结点和求第点和求第i个个结点的直接前点的直接前驱B、在第、在第i个个结点后插入一个新点后插入一个新结点点C、删除第除第i个个结点点D、以上都不、以上都不对。典型题目解析顺序表4、关于、关于线性表，下列性表，下列说法正确的是（）法正确的是（）A、线性表中每个元素都有一个直接前性表中每个元素都有一个直接前驱和一个直和一个直接后接后继B、线性表中的数据元素可以具有不同的数据性表中的数据元素可以具有不同的数据类型型C、线性表中数据元素的性表中数据元素的类型是确定的型是确定的D、线性表中任意一性表中任意一对相相邻的数据元素之的数据元素之间存在序存在序偶关系偶关系5、顺序表的插入算法中，当序表的插入算法中，当n个空个空间已已满时，可再，可再申申请增加分配增加分配m个空个空间，若申，若申请失失败，则说明系明系统没有（）可分配存没有（）可分配存储空空间。A、m个个B、m个个连续的的C、n+m个个D、n+m个个连续的的典型题目解析顺序表6、将下算法改成一个既正确又高效的算法。、将下算法改成一个既正确又高效的算法。Status Delete(Sqlist&a,int i,int k)/删除除顺序表序表a中从第中从第i个元素起的个元素起的k个元素个元素if(i1|ka.length)return ERROR;else for(count=1;count=i+1;j-)a.elemj-1=a.elemj;a.length-;return OK;for(count=1;i+count-1=a.length-k;count+)a.elemi+count-1=a.elemi+count+k-1;a.length-=k;典型题目解析顺序表7、设计一个一个时间复复杂度度为O（n）的算法，）的算法，实现将将数数组An种所有元素循种所有元素循环左移左移k个位置。个位置。8、一个、一个长度度为L（L1）的升序序列）的升序序列S，处在第在第 L/2 个位置的数称个位置的数称为S 的中位数。例如，若序列的中位数。例如，若序列S1=(11,13,15,17,19)，则S1 的中位数的中位数为15。两个。两个序列的中位数是含它序列的中位数是含它们所有元素的升序序列的中位所有元素的升序序列的中位数。例如，若数。例如，若S2=(2,4,6,8,10)，则S1 和和S2 的中的中位数位数为10。现有两个等有两个等长的升序序列的升序序列A 和和B，试设计一个在一个在时间和空和空间两方面都尽可能高效的算法，两方面都尽可能高效的算法，找出两个序列找出两个序列A 和和B 的中位数。的中位数。9、已知数、已知数组An中的元素中的元素为整型，整型，设计算法将其算法将其调整整为左右两部分，左左右两部分，左边所有元素所有元素为奇数，右奇数，右边所所有元素有元素为偶数，并要求算法的偶数，并要求算法的时间复复杂度度为 O（n）算法的基本算法的基本设计思想：分思想：分别求两个升序序求两个升序序列列A 和和B 的中位数，的中位数，设为a 和和b。1）若）若a=b，则a 或或b 即即为所求的中位数。所求的中位数。2）否）否则（假（假设a1）的）的带头结点的点的单链表表h上，另上，另设有尾指有尾指针r指向尾指向尾结点，点，执行（）操作与行（）操作与链表的表的长度有关。度有关。A删除除单链表第一个元素表第一个元素B删除除单链表的最后一个元素表的最后一个元素C在在单链表第一个元素前插入一个新的元素表第一个元素前插入一个新的元素D在在单链表的最后一个元素后插入一个新元素表的最后一个元素后插入一个新元素典型题目解析链表4、设一个一个单链表最常用的操作是在最后一个元素表最常用的操作是在最后一个元素之后插入一个元素和之后插入一个元素和删除第一个元素，除第一个元素，则采用（）采用（）存存储方式最方式最节省省时间A、单链表表B、仅有有头指指针的的单循循环链表表C、双、双链表表D、仅有尾指有尾指针的的单循循环链表表4+、如果、如果对于具有于具有n（n1）个元素的）个元素的线性表的基性表的基本操作有本操作有4种：种：删除第一个元素；除第一个元素；删除最后一个元除最后一个元素；在第一个元素前插入新元素；在最后一个元素素；在第一个元素前插入新元素；在最后一个元素后面插入新元素，后面插入新元素，则最好使用（）最好使用（）A、只、只设尾指尾指针的循的循环单链表表B、只、只设尾指尾指针的非循的非循环双双链表表C、只、只设头指指针的循的循环双双链表表D、同、同时设置置头指指针和尾指和尾指针的循的循环单链表表典型题目解析链表5、单链表中增加一个表中增加一个头结点的目的是（）点的目的是（）A、使表中至少有一个、使表中至少有一个结点点B、标识表中首表中首结点的位置点的位置C、方便运算的、方便运算的实现D、说明明单链表是表是线性表的性表的链式存式存储6、对于一个于一个线性表既要求能性表既要求能够快速的插入和快速的插入和删除，又要求存除，又要求存储结构能反映数据之构能反映数据之间的的逻辑关系，关系，则应该用（）用（）A、顺序存序存储B、链式存式存储C、散列存、散列存储D、以、以上均可上均可典型题目解析链表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、1234 B、4321 C、3412 D、14329、设线性表非空，（性表非空，（）可以在）可以在O(1)的的时间内在表内在表尾插入一个新尾插入一个新结点。点。A、带头结点的点的单链表，有一个表，有一个链表指表指针指向指向头结点点B、带头结点的循点的循环单链表，有一个表，有一个链表指表指针指向指向表的表的头结点点C、不、不带头结点的点的单链表，有一个表，有一个链表指表指针指向表指向表的第一个的第一个结点点D、不、不带头结点的循点的循环单链表，有一个表，有一个链表指表指针指指向表中某个向表中某个结点（除第一个点（除第一个结点外）点外）9+、假、假设有一个没有有一个没有头指指针的的单链表，一个指表，一个指针指指向此向此单链表中表中间的一个的一个结点（不是第一个，也不是点（不是第一个，也不是最后一个），最后一个），请将改将改结点从点从单链表中表中删除。除。典型题目解析链表典型题目解析链表10、已知非空、已知非空线性性链表由表由list指示，指示，结点点结构构为data，link。编写算法，将写算法，将链表中数据域最表中数据域最小的小的结点移到点移到链表最前面。要求：不得表最前面。要求：不得额外申外申请新新结点。点。11、给定一个定一个带头结点的点的单链表，表，设head为头指指针，设计算法按算法按递增次序增次序输出出单链表中各表中各结点的数据元素，并点的数据元素，并释放放结点所占的存点所占的存储空空间。要求：不允要求：不允许使用使用额外的存外的存储空空间。12、设计算法，将双向算法，将双向链表中表中结点点p与其后与其后继结点交点交换位置。位置。典型题目解析链表13、已知、已知L为单链表的表的头结点地址，表中共点地址，表中共有有m（m3）个）个结点，从表中第点，从表中第i（1im）个）个结点起到第点起到第m个个结点构成一点构成一个部分循个部分循环链表，如表，如图。设计算法将算法将这部部分循分循环链表中所有表中所有结点点顺序完全序完全颠倒。倒。14、在、在长度大于度大于1的循的循环单链表中，既无表中，既无头结点也无点也无头指指针，s为链表中某个表中某个结点的指点的指针，编写算法写算法删除除s的前的前驱结点。点。a1 a2 a3 anL典型题目解析链表15、单链表的表的头指指针为head，设计算法将算法将链表中表中记录按照数据域按照数据域递增的次序增的次序进行就地排序。行就地排序。16、设有两个有两个单链表，一个升序，一个降序。表，一个升序，一个降序。设编写算法，将写算法，将这两个两个链表合并表合并为一个有序一个有序链表。表。17、从、从键盘输入入n个英文个英文单词，输入格式入格式为n,单词1，单词n，其中，其中n表示随后表示随后输入英入英语单词个数，个数，试编写算法建立一个写算法建立一个单链表，要求：表，要求：如果如果单词重复出重复出现，则只在只在链表上只保留一个；表上只保留一个；统计单词出出现的次数，然后的次数，然后输出次数最多的前出次数最多的前k(knext=s;B、s-next=h;C、s-next=h;h-next=s D、s-next=h-next;h-next=s;典型题目解析栈12、消除、消除递归不一定使用不一定使用栈。（）。（）13、任何一个、任何一个递归过程都可以程都可以转换成非成非递归过程。（）程。（）14、只有那种使用了局部、只有那种使用了局部变量的量的递归过程在程在转换成非成非递归过程程时才必才必须使用使用栈。（）。（）15、用、用单链表表示表表示栈，栈顶设在在链表的（）表的（）16、解决、解决Hanoi塔塔问题的的递归算法，其算法，其时间复复杂度是（度是（）17、从运行、从运行时间上看，通常一个上看，通常一个递归函数要比函数要比非非递归函数（函数（）A、快一些、快一些B、慢一些、慢一些C、相同、相同D、无法、无法比比较典型题目解析栈18、有、有5个元素，其入个元素，其入栈次序次序为A、B、C、D、E，在各种可能的出，在各种可能的出栈序列中，第一个出序列中，第一个出栈元元素素为C且第二个出且第二个出栈元素元素为D的出的出栈序列有哪序列有哪几个？几个？19、元素、元素abcdef依次依次进栈，允，允许进栈、出、出栈交交替替进行，但不允行，但不允许连续三次三次进行出行出栈操作，操作，则不可能得到的出不可能得到的出栈序列是（）序列是（）A、dcebfa B、cbdaef C、bcaefd D、afedcb20、元素、元素abcde依次依次进栈，允，允许进栈、出、出栈交交替替进行，行，则以以d为首的出首的出栈序列是（）序列是（）典型题目解析栈21、设计一个算法，判断一个算一个算法，判断一个算术表达式表达式中的括号是否匹配。算中的括号是否匹配。算术表达式保存在表达式保存在带头结点的点的单循循环链表中，每个表中，每个结点有两个点有两个域：域：ch和和link，其中，其中ch域域为字符字符类型。型。22、利用两个、利用两个栈S1和和S2模模拟一个一个队列，已列，已知知栈的三个运算定的三个运算定义如下：如下：PUSH（st，x）元素元素x入入st栈；POP（st，x）出）出栈元素元素赋值给x；Sempty（st）判断是否）判断是否为空。如何利空。如何利用用栈的运算来的运算来实现队列的三个运算：入列的三个运算：入队enqueue，出，出队dequeue和判断和判断队列是否列是否为空空queue_empty。典型题目解析队列1、栈和和队列的区列的区别在于（）在于（）A、逻辑结构不一构不一样B、存、存储结构不一构不一样C、包含运算不一、包含运算不一样D、插入、插入、删除限定不一除限定不一样2、若用一个、若用一个长度度为6的数的数组来来实现循循环队列，列，且当前且当前rear和和front的的值分分别为0和和3，则队列中列中删除一个元素，再添加除一个元素，再添加2个元素后，个元素后，rear和和front的的值分分别为（）。（）。3、最不适合用作、最不适合用作链队列的列的链表是（）表是（）A 只只带队首指首指针的非循的非循环双双链表表B 只只带队首指首指针的循的循环双双链表表C 只只带队尾指尾指针的循的循环双双链表表D 只只带队尾指尾指针的循的循环单链表表典型题目解析队列4、循、循环队列的存列的存储空空间为数数组A21，front指向指向队首元素的前一位置，首元素的前一位置，rear指向指向队尾元素。假尾元素。假设当前当前front和和rear的的值分分别是是8和和3，则队列的列的长度是（）度是（）5、下列更适合表示、下列更适合表示队列的列的链表表结构是（）构是（）A、单链表表B、单循循环链表表C、双、双链表表D、双循、双循环链表表6、如、如图所示所示为一个元素一个元素类型型为字符型的字符型的环形形队列，列，front和和rear分分别指向指向队首和首和队尾，尾，则所表示的所表示的队列列为（）（）A、The f B、flower isC、beautiful The f D、eautiful The f012345678910111213141516171819202122Theflow erisbeatuifulrearfront典型题目解析队列7、执行（行（）操作）操作时，需要，需要队列作列作为辅助的存助的存储结构构A、深度、深度优先遍先遍历图B、广度、广度优先遍先遍历图C、散列、散列查找找D、遍、遍历二叉二叉树8、用不、用不带头结点的点的单链表存表存储队列，其列，其对头指指针指向指向队头结点，点，队尾指尾指针指向指向队尾尾结点，点，则在在进行行出出队操作操作时（）（）A、仅修改修改队头指指针B、仅修改修改队尾指尾指针C、队头队尾可能都要修改尾可能都要修改D、C去掉可能去掉可能9、在、在带头结点的点的链队列中，列中，队头指指针应该指向（）指向（）10、已知、已知输入序列入序列为abcd，经过输出受限的双向出受限的双向队列后能得到的列后能得到的输出序列有（）出序列有（）A dacb B cadb C dbca D bdac E all wrong典型题目解析队列11、若以、若以1234作作为双端双端队列的列的输入序列，入序列，则既既不能由不能由输入受限的双端入受限的双端队列得到，也不能由列得到，也不能由输出受限的双段出受限的双段队列得到的是（）列得到的是（）A、1234 B、4132 C、4231 D、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;典型题目解析队列14、某、某队列允列允许在其两端在其两端进行入行入队操作，操作，但但仅允允许在一端在一端进行出行出队操作。若元素操作。若元素abcde依次入依次入队后再后再进行出行出队操作，操作，则不可不可能得到的出能得到的出队序列是序列是A、bacde B、dbace C、dbcae D、ecbad15、关于、关于队列的叙述中，正确的是（）列的叙述中，正确的是（）A、只能使用数、只能使用数组构成循构成循环队列列B、可以使用数、可以使用数组或者或者链表构成循表构成循环队列列C、循、循环队列没有元素数量限制列没有元素数量限制D、可以将、可以将栈看成是一个特殊的看成是一个特殊的队列列典型题目解析队列16、若以、若以1、2、3、4作作为双端双端队列的列的输入序列，入序列，试分分别求以下条件的求以下条件的输出序列：出序列：能由能由输入受限的双端得到，但不能由入受限的双端得到，但不能由输出受限的双出受限的双端端队列得到的列得到的输出序列；出序列；能由能由输出受限的双端得到，但不能由出受限的双端得到，但不能由输入受限的双入受限的双端端队列得到的列得到的输出序列；出序列；既不能由既不能由输入受限的双端得到，也不能由入受限的双端得到，也不能由输出受限出受限的双端的双端队列得到的列得到的输出序列；出序列；17、利用两个、利用两个栈S1、S2模模拟一个一个队列列时，如何利用，如何利用栈的操作的操作实现入入队、出、出队及判断及判断队列是否列是否为空。空。18、试用一个不用一个不带头结点的循点的循环链表表示表表示队列，列，说明明链表指表指针指向何指向何处？如何入？如何入队、出、出队及判断及判断队列列为空？空？典型题目解析队列19、设栈S中有中有2n个元素，从个元素，从栈顶到到栈底的底的元素依次元素依次为a2n,a2n-1,a1，要求通，要求通过一个循一个循环队列重新排序站中元素，使得从列重新排序站中元素，使得从栈顶到到栈底底的元素依次的元素依次为a2n,a2n-2,a2,a2n-1,a2n-3,a1，设计算法算法实现，要求空，要求空间复复杂度和度和时间复复杂度度为O(n)。典型题目解析数组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的的存放地址是（）。存放地址是（）。典型题目解析矩阵的压缩存储特殊矩特殊矩阵是指矩是指矩阵中有中有较多相同的元素且其分布有多相同的元素且其分布有一定的一定的规律；律；压缩存存储的基本思想是：的基本思想是：为多个相同多个相同的元素分配一个存的元素分配一个存储空降；空降；对零元素不分配存零元素不分配存储空空间。1、设AN,N是是对称矩称矩阵，将其下三角包括，将其下三角包括对角角线按行序存按行序存储到一到一维数数组TN(N+1)/2中，中，则上三角元素上三角元素Aij对应数数组元素元素T的下的下标是（）是（）2、对特殊矩特殊矩阵采用采用压缩存存储的目的主要是（）的目的主要是（）A、表达、表达变的的简单B、对矩矩阵元素的存取元素的存取变得得简单C、去掉矩、去掉矩阵中的多余元素中的多余元素D、减少不必要的存、减少不必要的存储空空间典型题目解析矩阵的压缩存储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为（）。（）。第五章树和二叉树考纲分析（一）树的基本概念（二）二叉树1.二叉树的定义及其主要特征2.二叉树的顺序存储结构和链式存储结构3.二叉树的遍历4.线索二叉树的基本概念和构造（三）树、森林1.树的存储结构2.森林与二叉树的转换3.树和森林的遍历（四）树与二叉树的应用1.二叉排序树2.平衡二叉树3.哈夫曼（Huffman）树和哈夫曼编码典型题目解析树的基本概念1、假定一、假定一颗度度为3的的树中中结点数点数为50，则其最小高其最小高度度应为（）。（）。2、下列、下列说法中，（）是正确的。法中，（）是正确的。A、二叉、二叉树就是度就是度为2的的树B、二叉、二叉树中不存在度大于中不存在度大于2的的结点点C、二叉、二叉树是有序是有序树D、二叉、二叉树中每个中每个结点的度均点的度均为23、二叉、二叉树是一棵（）是一棵（）A、度、度为2的有序的有序树B、所有、所有结点度均点度均为2的有序的有序树C、度、度为2的无序的无序树D、所有、所有结点度均点度均为2的无序的无序树典型题目解析树的基本概念4、下列情况中，可称、下列情况中，可称为二叉二叉树的是（）的是（）A、每个、每个结点至多有两棵子点至多有两棵子树的的树B、哈夫曼、哈夫曼树 C、每个、每个结点只有一棵点只有一棵树D、每个、每个结点至多有两棵子点至多有两棵子树的有序的有序树5、下列、下列结论中正确的是（）中正确的是（）只有一个只有一个结点的二叉点的二叉树的度的度为0二叉二叉树的度的度为2 二叉二叉树的左右子的左右子树可任意交可任意交换深度深度为k的完全二叉的完全二叉树的的结点个数小于或等于深点个数小于或等于深度相等的度相等的满二叉二叉树A、B、C、D、典型题目解析树的基本概念6、二叉、二叉树有有n个个结点，点，则其深度其深度为（）。（）。A、n-1 B、n C、log2n+1 D、不能确定、不能确定7、若完全二叉、若完全二叉树的的结点个数点个数为100，则第第60个个结点的度点的度为（）（）8、一棵有、一棵有124个叶子个叶子结点的完全二叉点的完全二叉树最多有（）最多有（）个个结点。点。9、一棵、一棵满二叉二叉树中共有中共有n个个结点，其中有点，其中有m个叶子个叶子结点，深度点，深度为h，则（）（）A、n=h+m B、h+m=2n C、m=h-1 D、n=2h-110、设二叉二叉树有有2n个个结点，点，则对于于mK），），则该森林中有（）棵森林中有（）棵树。A、KB、N C、N-K D、116、设树T的度的度为4，其中度，其中度1,2,3和和4的的结点个点个数分数分别为4,2,1,1，则T中的叶子数中的叶子数为（）（）17、一棵完全二叉、一棵完全二叉树中共有中共有626个个结点，点，则叶叶子子结点的个数点的个数为（）（）A、311 B、312 C、313 D、31418、将有关二叉、将有关二叉树的概念推广到三叉的概念推广到三叉树，则一一棵有棵有244个个结点的完全三叉点的完全三叉树的高度的高度为（）（）A、4B、5C、6D、7典型题目解析树的基本概念19、一棵共有、一棵共有n个个结点的点的树，其中所有分支，其中所有分支结点的度均点的度均为k，则该树中叶子中叶子结点的数目点的数目为多少？多少？20、将有关二叉、将有关二叉树的概念推广到三叉的概念推广到三叉树，则含有含有244个个结点的完全三叉点的完全三叉树的高度是多的高度是多少？含有少？含有244个叶子个叶子结点的完全三叉点的完全三叉树的高的高度是多少？度是多少？21、对于一棵含有于一棵含有N个个结点的点的k叉叉树，请讨论其可能的最大高度和最小高度。其可能的最大高度和最小高度。典型题目解析树的基本概念22、一棵高度、一棵高度为h的的完全k叉叉树有如下性有如下性质：第第h层上的上的结点都是叶点都是叶结点，其余各点，其余各层上每上每个个结点都有点都有k棵非空子棵非空子树。如果按。如果按层次自次自顶向下、自左向右向下、自左向右顺序从序从1开始开始对全部全部结点点进行行编号，号，试问：最多有多少个最多有多少个结点？点？最少有多少个最少有多少个结点？点？结点点q的第的第i个孩子个孩子结点的点的编号号为多少？多少？结点点q的双的双亲结点的点的编号号为多少？多少？典型题目解析二叉树的存储结构23、以下、以下说法中，（）是正确的。法中，（）是正确的。A、完全二叉、完全二叉树中，叶中，叶结点双点双亲的左兄弟的左兄弟结点点一定不是叶一定不是叶结点点B、任何一棵二叉、任何一棵二叉树中，中，终端端结点等于度点等于度为2的的结点数减点数减1C、完全二叉、完全二叉树不适合用不适合用顺序存序存储结构存构存储D、结点按点按层次次编号的二叉号的二叉树，第，第i个个结点的左点的左孩子（如果存在）孩子（如果存在）编号号为2i24、若用一、若用一维数数组保存一个深度保存一个深度为5，结点个点个数数为10的二叉的二叉树，数，数组的的长度至少度至少为（）（）A、10 B、16 C、31 D、63典型题目解析二叉树的存储结构25、一棵有、一棵有n个个结点的二叉点的二叉树采用采用顺序存序存储结构，构，存存储在一在一维数数组A0n-1中，中，结点点Ai的左孩子的左孩子是（）是（）A、A2i B、A2i+1 C、A2i+2 D、A2i+326、在、在顺序存序存储的二叉的二叉树中，中，编号号为i和和j的两个的两个结点在同一点在同一层上的条件是上的条件是什么？什么？如何求如何求i和和j的最近的共同祖先？的最近的共同祖先？27、设度度为m的的树采用多重采用多重链表存表存储，每个，每个结点有点有m+1个域，其中有个域，其中有1个数据域，个数据域，m个指向个指向孩子的指孩子的指针。则空指空指针的数目是多少？的数目是多少？说明明这种存种存储方式的利弊。方式的利弊。典型题目解析二叉树的存储结构28、已知深度、已知深度为h的二叉的二叉树以一以一维数数组BT1.2h-1作作为存存储结构。构。编写算法求写算法求该二叉二叉树的叶子的叶子结点个数。点个数。为简单起起见，假，假设二叉二叉树中元素中元素结点点为非零整数。非零整数。29、设计算法将一棵以二叉算法将一棵以二叉链表存表存储的二的二叉叉树按按顺序方式存序方式存储到一到一维数数组中。中。典型题目解析二叉树的遍历30、一棵二叉、一棵二叉树的前序遍的前序遍历序列序列为ABCDEFG，它的中序遍，它的中序遍历序列可能是（）序列可能是（）A、CABDEFG B、BCDAEFGC、DACEFBG D、ADBCFEG31、现有先序遍有先序遍历二叉二叉树的的结果果为ABCD，则有（）种不同的二叉有（）种不同的二叉树可以得到可以得到这一一结果。果。A、12 B、13 C、14 D、1532、二叉、二叉树的先序序列和后序序列正好相反，的先序序列和后序序列正好相反，则该二叉二叉树一定是（）的二叉一定是（）的二叉树。A、空或者只有一个、空或者只有一个结点点B、高度等于、高度等于结点数点数C、任一、任一结点无左孩子点无左孩子D、任一、任一结点无右孩子点无右孩子典型题目解析二叉树的遍历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、构造、构造线索二叉索二叉树的目的是的目的是为了能方便的找了能方便的找到到结点的双点的双亲典型题目解析二叉树的遍历35、二叉、二叉树的叶子的叶子结点在先序、中序和后点在先序、中序和后序的遍序的遍历序列中相序列中相对位置（）位置（）A、不、不发生改生改变B、发生改生改变C、不能确定、不能确定D、都不、都不对36、若二叉、若二叉树采用二叉采用二叉链表存表存储，要交，要交换其所有分支其所有分支结点左、右子点左、右子树的位置，利用的位置，利用（）遍（）遍历方法最合适。方法最合适。A、先序、先序 B、中序、中序 C、后序、后序 D、层次次典型题目解析二叉树的遍历37、判断两棵二叉、判断两棵二叉树是否相似。所是否相似。所谓相似，相似，是指要么它是指要么它们都都为空的或都是有一个根空的或都是有一个根结点，要么他点，要么他们的左右子的左右子树均相似。均相似。38、在二叉、在二叉树中中查找找值为x的的结点。点。39、求二叉、求二叉树的深度。的深度。40、求二叉、求二叉树中各种中各种结点个数。点个数。典型题目解析二叉树的遍历41、一个二叉、一个二叉树以二叉以二叉链表存表存储，求二叉，求二叉树第第k层上叶子上叶子结点的个数。点的个数。42、设计算法算法统计二叉二叉树中每一中每一层结点个数。点个数。43、设计算法求二叉算法求二叉树的的宽度。度。44、一棵二叉、一棵二叉树以以顺序存序存储在数在数组bt1.n中，中，写出先序的非写出先序的非递归算法。算法。45、已知二叉、已知二叉树采用二叉采用二叉链表存表存储，设计算法算法以以输出二叉出二叉树中根中根结点到每个叶子点到每个叶子结点的路径。点的路径。46、一棵二叉、一棵二叉链表存表存储的二叉的二叉树，编写程序写程序输入从根入从根结点到叶点到叶结点的最点的最长路径上的所有路径上的所有结点。点。典型题目解析二叉树的遍历47、证明：已知一棵二叉明：已知一棵二叉树的前序序列和中序序列，的前序序列和中序序列，则可唯一确定二叉可唯一确定二叉树。48、编写算法根据二叉写算法根据二叉树的先序序列和中序序列建的先序序列和中序序列建立二叉立二叉树。49、编写算法，判断一棵二叉写算法，判断一棵二叉树是否是否为完全二叉完全二叉树。50已知一棵二叉已知一棵二叉树的每个的每个结点，要其么左右子点，要其么左右子树为空要么皆不空要么皆不为空。又知空。又知该二叉二叉树的前序遍的前序遍历序列序列为JFDBACEHXIK，后序遍，后序遍历序列序列ACBEDXIHFKJ，试构造构造该二叉二叉树。51、已知二叉、已知二叉树的的层次遍次遍历序列序列为ABCDEFGHIJ，中序遍中序遍历序列序列为DBGEHACIJF，试构造二叉构造二叉树。典型题目解析线索二叉树48、具有、具有n个个结点的点的线索二叉索二叉树共有（）个共有（）个线索。索。49、一棵左子、一棵左子树为空的二叉空的二叉树在前序在前序线索化后，索化后，其中空其中空链域的个数是（）。域的个数是（）。50、一棵左右子、一棵左右子树均不均不为空的二叉空的二叉树在前序在前序线索化后，其中空索化后，其中空链域的个数是（）。域的个数是（）。51、二叉、二叉树在在线索化后仍不能有效求解的索化后仍不能有效求解的问题是（）是（）A、前序、前序线索二叉索二叉树中求前序后中求前序后继B、中序、中序线索二叉索二叉树中求中序后中求中序后继C、中序、中序线索二叉索二叉树中求中序前中求中序前驱D、后序、后序线索二叉索二叉树中求后序后中求后序后继典型题目解析线索二叉树52、关于、关于线索二叉索二叉树，下列，下列说法中不正确的是法中不正确的是（）（）A、中序、中序线索二叉索二叉树中，若中，若结点有右孩子，点有右孩子，则其后其后继是它的右子是它的右子树的左分支末端的的左分支末端的结点。点。B、线索二叉索二叉树利用二叉利用二叉树的的n+1个空指个空指针来来存放其前存放其前驱和后和后继信息信息C、在、在线索二叉索二叉树中，每个中，每个结点通点通过线索都可索都可以直接找打它的前以直接找打它的前驱和后和后继D、中序、中序线索二叉索二叉树中，若中，若结点有左孩子，点有左孩子，则其前其前驱是它的左子是它的左子树的右分支末端的右分支末端结点。点。典型题目解析线索二叉树53、线索二叉索二叉树是一种（）是一种（）结构构A、逻辑B、逻辑和存和存储C、物理、物理D、线性性54、（）、（）线索二叉索二叉树的遍的遍历仍需要仍需要栈的支持的支持55、线索二叉索二叉树中的中的线索指的是（）索指的是（）A、左孩子、左孩子B、遍、遍历C、指、指针D、标识56、若、若X是二叉是二叉树中序中序线索索树中一个有左孩子中一个有左孩子的的结点，且点，且X不不为根，根，则X的前的前驱为（）（）A、X的双的双亲B、X的右子的右子树中最左中最左结点点C、X的左子的左子树中最右中最右结点点D、X的左子的左子树中最右叶子中最右叶子结点点典型题目解析树、森林和二叉树57、讨论树、森林和二叉、森林和二叉树的关系，目的是的关系，目的是为了（）了（）A、借助二叉、借助二叉树上的运算方法去上的运算方法去实现对树的一的一些运算些运算B、将、将树、森林按二叉、森林按二叉树的存的存储方式方式进行存行存储并利用二叉并利用二叉树的算法解决的算法解决树的有关的有关问题C、将、将树、森林、森林转换成二叉成二叉树D、体、体现一种技巧，一种技巧，实际意意义不大不大58、深度、深度为h的的满二叉二叉树对应的森林由（）棵的森林由（）棵树构成。构成。A、1 B、log2h C、h/2 D、h典型题目解析树、森林和二叉树58、设F是一个森林，是一个森林，B是由是由F转换得到的二叉得到的二叉树。若。若F中有中有n个非个非终端端结点，点，则B中右指中右指针域域为空的空的结点有（）个。点有（）个。A、n-1 B、n C、n+1 D、n+259、设x是是树T中的一个非根中的一个非根结点，点，B是是T所所对应的二叉的二叉树。在。在B中，中，x是其双是其双亲的右孩子，的右孩子，则下列下列结论正确的是（）正确的是（）A、在、在树T中，中，x是其双是其双亲的第一个孩子的第一个孩子B、在、在树T中，中，x 一定无右兄弟一定无右兄弟C、在、在树T中，中，x 一定是叶子一定是叶子结点点D、在、在树T中，中，x一定有左兄弟一定有左兄弟典型题目解析树、森林和二叉树60、已知一个森林的前序序列、已知一个森林的前序序列为ABCDEFGHIJKLMNO，后序序列，后序序列为CDEBFHIJGAMLONK，求此森林。，求此森林。61、如果在表示、如果在表示树的孩子兄弟的孩子兄弟链表中有表中有6个个空的左指空的左指针域，域，7个空的右指个空的右指针域，域，5个个结点左右指点左右指针域都域都为空，空，则该二叉二叉树叶子叶子结点个数点个数为多少？多少？典型题目解析哈弗曼树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典型题目解析哈弗曼树65、设计哈弗曼哈弗曼编码的的长度不超度不超过4，若已，若已经对两个字符两个字符编码为1和和01，则最多最多还可以可以为（）（）个字符个字符编码。A、2 B、3 C、4 D、566、假、假设字符集字符集a,b,c,d,e中各字符出中各字符出现的的频率分率分别为4,21,7,14,31，为该字符集构造哈弗曼字符集构造哈弗曼编码，则字符集字符集编码的的总码数数为（）。（）。A、12 B、13 C、14 D、1567、若度、若度为m的哈夫曼的哈夫曼树中，其叶中，其叶结点个数点个数为n，则非叶非叶结点个数点个数为（）A、n-1 B、n/m-1C、(n-1)/(m-1)D、(n+1)/(m+1)-1典型题目解析哈弗曼树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次合并，是的次合并，是的总的的比比较次数最少？次数最少？典型题目解析历年统考真题20114、一棵完全二叉、一棵完全二叉树有有768个个结点，点，则该二叉二叉树中叶子中叶子结点的个数是（）点的个数是（）A、257 B、258 C、384 D、3855、若一棵二叉、若一棵二叉树的前序遍的前序遍历序列和后序遍序列和后序遍历序列分序列分别是是1234和和4321，则该二叉二叉树的中序的中序遍遍历序列是（）序列是（）A、1234 B、2341 C、3241 D、43216、已知一棵、已知一棵树有有2011个个结点，其中叶点，其中叶结点个点个数数为116，该树对应的二叉的二叉树中无右孩子的中无右孩子的结点个数点个数为（）（）A、115 B、116 C、1895 D、1896典型题目解析历年统考真题20103、下列、下列线索二叉索二叉树中，符合后序中，符合后序线索二叉索二叉树的是（）的是（）典型题目解析历年统考真题20104、在一棵度、在一棵度为4的的树T中，若有中，若有20个度个度为4的的结点，点，10个度个度为3的的结点，点，1个度个度为2的的的的结点，点，10个度个度为1的的结点，点，则树T的叶子的叶子结点个个数点个个数为（）（）A、41 B、82 C、113 D、1225、对于于n个个权值均不相同的字符构造均不相同的字符构造huffman树，下列关于，下列关于该树的描述中，的描述中，错误的是（）的是（）A、该树一定是一棵完全二叉一定是一棵完全二叉树B、该树一定没有度一定没有度为1的的结点点C、树中两个中两个权值最小的最小的结点一定是兄弟点一定是兄弟结点点D、树中任一非叶子中任一非叶子结点的点的权值一定不小于下一定不小于下一一层任一任一结点的点的权值。典型题目解析历年统考真题20093、给定二叉定二叉树如如图所示，所示，设N代表二叉代表二叉树的根，的根，L代表根代表根结点的左子点的左子树，R代表根代表根结点的右子点的右子树，若遍，若遍历后的后的结点序列点序列为3175624，则其遍其遍历方式方式为（）（）A、LRN B、NRL C、RLN D、RNL4、下列二叉排序、下列二叉排序树中，中，满足平衡二叉足平衡二叉树的的是（）是（）典型题目解析历年统考真题2