MOOC 数据结构-厦门大学 中国大学慕课答案

MOOC数据结构-厦门大学中国大学慕课答案1.1什么是数据结构1、问题：数据结构的研究对象主要包括：选项：A、数据集合中元素之间的关系B、数据集合的存储实现方式C、对数据集合进行的操作D、操作算法优劣的评价正确答案:【数据集合中元素之间的关系#数据集合的存储实现方式#对数据集合进行的操作#操作算法优劣的评价】2、问题：数据结构主要研究非数值计算的问题。选项：A、正确B、错误正确答案:【正确】3、问题：数据结构的研究与计算机硬件无关。选项：A、正确B、错误正确答案:【错误】1.2数据结构的基本概念（一）——逻辑结构1、问题：数据的逻辑结构是指（）关系的整体。选项：A、数据存储结构之间B、数据类型之间C、数据元素之间逻辑D、数据项之间逻辑正确答案:【数据元素之间逻辑】2、问题：以下说法不正确的是（）。选项：A、数据可由若干个数据元素构成。B、数据项是不可分割的最小可标识单位。C、数据项可由若干个数据元素构成。D、数据元素是数据的最小单位。正确答案:【数据项可由若干个数据元素构成。#数据元素是数据的最小单位。】3、问题：数据的逻辑结构可以分为（）。选项：A、动态结构和静态结构B、线性结构和非线性结构C、内部结构和外部结构D、集合、线性结构、树形结构、图状结构正确答案:【线性结构和非线性结构#集合、线性结构、树形结构、图状结构】1.2数据结构的基本概念（二）——物理结构1、问题：下面关于数据的逻辑结构与存储结构说法正确的是（）。选项：A、逻辑结构要体现出存储结构。B、存储结构要体现出逻辑结构。C、两者是一一对应的。D、二者毫无关系。正确答案:【存储结构要体现出逻辑结构。】2、问题：在数据的存储中，一个结点通常存储一个（）。选项：A、数据结构B、数据类型C、数据元素D、数据项正确答案:【数据元素】3、问题：在决定选取任何类型的存储结构时，一般不多考虑（）。选项：A、对数据有哪些运算B、结点个数的多少C、各结点的具体取何值D、所用编程语言实现这种结构是否方便正确答案:【各结点的具体取何值】1.3抽象数据类型1、问题：以下关于ADT抽象数据类型说法错误的是（）。选项：A、ADT建立的封装技术将可能的处理实现细节隐蔽起来。B、可采用程序设计语言的控制结构和基本数据类型来实现ADT的所提供的逻辑接口。C、同一ADT只有唯一的数据结构可以实现。D、ADT是对数据进行处理的一种逻辑描述。正确答案:【同一ADT只有唯一的数据结构可以实现。】2、问题：下列关于抽象数据类型（ADT）定义的说法，正确的有（）。选项：A、ADT的定义只取决于它的一组逻辑特性。B、ADT的定义与计算机内部如何表示和实现无关。C、不论ADT的内部结构如何变化，只要它的数学特性不变，都不影响它的外部使用。D、ADT定义了一个完整的（狭义）数据结构。正确答案:【ADT的定义只取决于它的一组逻辑特性。#ADT的定义与计算机内部如何表示和实现无关。#不论ADT的内部结构如何变化，只要它的数学特性不变，都不影响它的外部使用。#ADT定义了一个完整的（狭义）数据结构。】1.4什么是算法1、问题：计算机中算法是解决某一问题的有限运算序列，必须具备输入、输出、（）等5个特性。选项：A、确定性、有穷性和健壮性B、可读性、正确性和健壮性C、可行性、正确性和可读性D、可行性、确定性和有穷性正确答案:【可行性、确定性和有穷性】2、问题：数据的运算（即操作）（）。选项：A、在不同计算机上的实现方法都是相同的。B、必须用程序设计语言来描述C、与采用何种存储结构有关D、有算术运算和关系运算两大类正确答案:【与采用何种存储结构有关】3、问题：算法的设计目标有（）等等。选项：A、可行性B、健壮性C、有穷性D、正确性正确答案:【健壮性#正确性】1.5算法的分析与度量1、问题：算法分析的主要任务之一是分析（）。选项：A、算法中是否存在语法错误B、算法的执行时间与问题规模之间的关系C、算法中输入和输出之间的关系D、算法是否具有较好的可读性正确答案:【算法的执行时间与问题规模之间的关系】2、问题：给出算法的时间复杂度是属于一种（）。选项：A、事前统计的方法B、事前分析估算的方法C、事后统计的方法D、事后分析估算的方法正确答案:【事前分析估算的方法】3、问题：下述函数中时间复杂度最小的是（）。选项：A、B、C、D、正确答案:【】4、问题：下面程序段的时间复杂度是（）。i=1;while(i=n)i=i*5;选项：A、B、nC、D、正确答案:【】第一周绪论单元测验1、问题：某算法的时间复杂度为。若该算法在规模为n的数据集上，运行时间为10秒；如果数据规模扩大为2n，该算法大约需要运行（）。选项：A、10秒B、100秒C、6-7分钟D、以上都不对正确答案:【以上都不对】2、问题：以下函数中时间复杂度最小的是（）。选项：A、B、C、D、E、F、G、正确答案:【#】3、问题：下列程序段的时间复杂度是（）。count=0;for(k=1;k=n;k*=2)for(j=1;j=n;j++)count++;选项：A、B、C、D、正确答案:【】4、问题：下列程序段的时间复杂度是（）。intk=0,j=0;while(j=n){k++;j+=k;}选项：A、B、C、D、E、正确答案:【】5、问题：下面的数据结构是（）。DS=(D,R)，其中D={a,b,c,d,e}，R={r}，r={a,b,a,e,b,c,d,e}。注：“表示有序对。选项：A、集合B、线性结构C、树形结构D、图状结构E、顺序存储结构F、链式存储结构正确答案:【图状结构】6、问题：计算机所处理数据一般具有某种内在联系，这是指（）。选项：A、数据与数据之间存在某种关系B、数据元素与数据元素之间存在某种关系C、元素内部存在某种结构D、数据项与数据项之间存在某种关系正确答案:【数据元素与数据元素之间存在某种关系】7、问题：数据的运算（）。选项：A、效率与采用何种存储结构有关B、是根据存储结构来定义的C、有算术运算和关系运算两大类D、必须用程序设计语言来描述正确答案:【效率与采用何种存储结构有关】8、问题：某算法的时间复杂度为O(nlogn)，表明该算法的（）。选项：A、问题规模是O(nlogn)B、执行时间等于O(nlogn)C、执行时间与O(nlogn)成正比D、问题规模与O(nlogn)成正比正确答案:【执行时间与O(nlogn)成正比】9、问题：下列程序段的时间复杂度是（）。intfact(intn){if（n=1)return1;elsereturn(n*fact(n-1));}选项：A、O(1)B、O(n)C、D、O(logn)正确答案:【O(n)】10、问题：下列程序段的时间复杂度是（）。i=1;while(i=n)i*=10;选项：A、O(n)B、C、O(logn)D、正确答案:【O(logn)】11、问题：下列程序段的时间复杂度是（）。for(i=1;i=m1;++i)for(j=1;j=n2;++j)Q[i][j]=0;for(i=1;i=m1;++i)for(j=1;j=n2;++j)for(k=1;k=n1;++k)Q[i][j]+=M[i][k]*N[k][j];选项：A、O(m1*n2)B、O(m1*n2*n1)C、O(m1+n2*n1)D、O(m1*n2+n1*n2)E、O(m1*n2+n1*n2+m1*n1)正确答案:【O(m1*n2*n1)】12、问题：下列关于算法的叙述正确的是（）。选项：A、算法的有穷性是指算法必须能在有限时间和有限步骤内执行完。B、算法的时间复杂度与空间复杂度紧密相关。C、算法的效率只与问题规模有关，而与数据的存储结构无关。D、用不同算法求解同一问题的时间复杂度不同。E、算法的优劣与算法描述语言无关，与所用计算机也无关。F、算法原地工作的含义是指该算法不需要任何额外的辅助空间。G、对于相同规模的n，时间复杂度O(n)的算法运行时间总是小于时间复杂度的算法的运行时间。H、算法最终必须由计算机程序实现。I、算法的可行性是指代码不能有二义性。J、算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。K、健壮的算法不会因非法输入数据而出现莫名其妙的状态。正确答案:【算法的有穷性是指算法必须能在有限时间和有限步骤内执行完。#算法的优劣与算法描述语言无关，与所用计算机也无关。#健壮的算法不会因非法输入数据而出现莫名其妙的状态。】13、问题：下列叙述正确的是（）。选项：A、数据元素是数据项中不可分割的最小可标识单位。B、从逻辑上可以把数据结构分为顺序结构、链式结构等类别。C、研究数据结构就是研究数据的逻辑结构和存储结构。D、数据类型可看成是程序设计语言中已实现的数据结构。E、数据元素之间的关联关系在数据的逻辑结构中体现。F、数据对象是由有限个类型相同的数据元素构成的。G、逻辑结构不相同的数据，必须采用不同类型的存储方法。H、如果数据元素值发生改变，则数据的逻辑结构也随之改变。I、数据结构是相互之间存在一种或多种特定关系的数据元素的集合。J、逻辑结构相同的数据，可以采用多种不同的存储方法。K、逻辑结构相同的数据，在设计存储结构时，它们的节点类型也一定相同。L、选择数据结构时应考虑程序运行时所需输入和处理的数据总量。正确答案:【数据类型可看成是程序设计语言中已实现的数据结构。#数据元素之间的关联关系在数据的逻辑结构中体现。#数据对象是由有限个类型相同的数据元素构成的。#数据结构是相互之间存在一种或多种特定关系的数据元素的集合。#逻辑结构相同的数据，可以采用多种不同的存储方法。#选择数据结构时应考虑程序运行时所需输入和处理的数据总量。】2.1线性表的定义（一）——概念和ADT1、问题：下列有关线性表的叙述中，正确的是（）。选项：A、线性表中元素之间的关系是线性关系。B、线性表中至少有一个元素。C、线性表中的任一元素有且仅有一个直接前趋。D、线性表中的任一元素有且仅有一个直接后继。正确答案:【线性表中元素之间的关系是线性关系。】2、问题：插入和删除操作是线性表的基本操作，这两种操作在数组中也经常使用。选项：A、正确B、错误正确答案:【错误】2.1线性表的定义（二）——合并与归并1、问题：将两个长度均为n的有序线性表归并成一个有序线性表，最少需要（）次比较。选项：A、n-1B、nC、2n-1D、2n正确答案:【n】2、问题：假设两个集合分别存储在两个线性表中，长度分别为m和n，将它们合并到一个新的线性表中，则该线性表的最小长度是（）。选项：A、m+nB、min(m,n)C、max(m,n)D、无法确定正确答案:【max(m,n)】2.2顺序表1、问题：顺序表具有随机存取特性，指的是（）。选项：A、查找值为x的元素与顺序表中元素个数n无关B、查找值为x的元素与顺序表中元素个数n有关C、查找序号为i的元素与顺序表中元素个数n无关D、查找序号为i的元素与顺序表中元素个数n有关正确答案:【查找序号为i的元素与顺序表中元素个数n无关】2、问题：顺序表中，删除一个元素所需要的时间（）。选项：A、与删除元素的位置及顺序表的长度都有关B、只与删除元素的位置有关C、只与顺序表的长度有关D、与删除元素的位置及顺序表的长度都无关正确答案:【与删除元素的位置及顺序表的长度都有关】3、问题：假设某顺序表中第一个元素的存储地址是1010H，每个元素占8个存储单元，则第5个元素的存储地址是（）。【注意：本题的地址采用十六进制表示（数字末尾加H）】选项：A、1042HB、1050HC、1030HD、1038H正确答案:【1030H】4、问题：在N个结点的顺序表中插入一个结点，等概率情况下，平均需要移动（）个结点。选项：A、(n-1)/2B、n/2C、(n+1)/2D、n正确答案:【n/2】5、问题：顺序表中元素的逻辑顺序与存储顺序总是一致的。选项：A、正确B、错误正确答案:【正确】2.3线性链表（一）——单链表1、问题：已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是（）。选项：A、O(n)B、O(m*n)C、O(min(m,n))D、O(max(m,n))正确答案:【O(max(m,n))】2、问题：下列关于单链表的说法，错误的是（）。选项：A、数据域用于存储线性表的一个数据元素。B、指针域用于存储一个指向本结点对应元素的直接后继所在结点的指针。C、单链表中各结点的地址不可以连续。D、单链表无法随机存取。正确答案:【单链表中各结点的地址不可以连续。】3、问题：单链表具备的特点有（）。选项：A、插入和删除不需要移动元素。B、不必事先估计整个线性表所需的存储空间。C、所需存储空间与线性表长度成正比。D、只能顺序访问。正确答案:【插入和删除不需要移动元素。#不必事先估计整个线性表所需的存储空间。#所需存储空间与线性表长度成正比。#只能顺序访问。】4、问题：在一个单链表中，已知q是p的前趋结点，若在q和p之间插入结点s，则应当执行语句序列（）。选项：A、s-next=p-next;p-next=s;B、s-next=q-next;p-next=s;C、s-next=q-next;q-next=s;D、q-next=s;s-next=p;正确答案:【s-next=q-next;q-next=s;#q-next=s;s-next=p;】2.3线性链表（二）——静态链表1、问题：静态链表中的指针域存放的是（）。选项：A、下一个元素的地址B、内存地址C、下一个元素在数组中的位置D、以上都不对正确答案:【下一个元素在数组中的位置】2、问题：静态链表不需要一开始就分配所有的存储空间，可以等到要插入数据元素时再申请选项：A、正确B、错误正确答案:【错误】2.4循环链表和双向链表1、问题：对于双向链表，在两个结点之间插入一个新结点需修改的指针共（）个。选项：A、1B、2C、3D、4正确答案:【4】2、问题：非空的循环单链表head的尾结点p满足（）。选项：A、p-next==headB、p-next==NULLC、p==NULLD、p==head正确答案:【p-next==head】3、问题：对于长度为n（n≥1）的双向链表L，在p所指结点之前插入一个新结点，其时间复杂度为（）。选项：A、O(1)B、O(n)C、O(nlogn)D、正确答案:【O(1)】4、问题：对于一个头指针为head的带头结点的双向循环链表，可以作为判定该表为空表的条件是（）。选项：A、head==NULLB、head==NULLC、head-prior==headD、head-next==head正确答案:【head-prior==head#head-next==head】2.5顺序表与线性链表的比较（一）——顺序表与链表1、问题：静态链表与顺序表相比，优点在于（）。选项：A、所有操作的算法实现更简单B、便于随机存取C、便于插入和删除D、便于利用零散的存储空间正确答案:【便于插入和删除】2、问题：若某线性表最常用的操作是存取任意指定序号的元素和在表尾元素之后进行插入和删除操作，则采用（）存储方式最节省时间。选项：A、带头结点的单链表B、不带头结点的单链表C、带头结点的双向循环链表D、顺序表正确答案:【顺序表】3、问题：设线性表中有2n个元素，以下操作中，（）在单链表上实现要比在顺序表上实现效率更高。选项：A、删除指定位置元素的下一个元素B、在最后一个元素的后面插入一个新元素C、顺序输出前k个元素D、交换第i个元素和第n-i+1个元素的值（i=1,2,…,n）正确答案:【删除指定位置元素的下一个元素】2.5顺序表与线性链表的比较（二）——各种链表的对比1、问题：与非循环单链表相比，循环单链表的主要优点是（）。选项：A、不再需要头指针B、已知某个节点的位置后，能够容易找到它的前驱节点C、在进行插入、删除操作时，能更好地保证链表不断开D、从表中任意节点出发都能扫描到整个链表正确答案:【从表中任意节点出发都能扫描到整个链表】2、问题：若某线性表最常用的操作是在表尾结点插入新结点和删除表尾结点，则采用（）存储方式最节省时间。选项：A、带头结点的双向循环链表B、不带头结点的单链表C、仅有尾指针的循环单链表D、仅有头指针的循环单链表正确答案:【带头结点的双向循环链表】3、问题：若某线性表最常用的操作是在表尾结点之后插入新结点和删除表头结点，则采用（）存储方式最节省时间。选项：A、仅有头指针的循环单链表B、仅有尾指针的循环单链表C、带头结点的单链表D、带头结点的双向循环链表正确答案:【仅有尾指针的循环单链表】4、问题：下列关于链表的描述，正确的是（）。选项：A、在循环单链表中，从表中任一结点出发都可以通过前后移动操作来遍历整个循环链表。B、在双向链表中，可以从任一结点开始沿同一方向查找到任何其他结点。C、单链表不具有随机存取特性，而双向链表具有随机存取特性。D、为了方便插入和删除，可以使用双向链表存放数据。正确答案:【为了方便插入和删除，可以使用双向链表存放数据。】第二周线性表单元测验1、问题：顺序表中，结点的插入和删除操作的时间复杂度分别为（）。选项：A、O(1)、O(1)B、O(n)、O(1)C、O(1)、O(n)D、O(n)、O(n)正确答案:【O(n)、O(n)】2、问题：在表长为n的顺序表中，下列操作中需要移动元素最多的是（）。选项：A、删除表中的第一个元素。B、删除表中的最后一个元素。C、在第一个元素之前插入一个元素。D、在最后一个元素之前插入一个元素。E、在最后一个元素之后插入一个元素。F、在最后一个元素之后插入一个元素。正确答案:【在第一个元素之前插入一个元素。】3、问题：带头结点的双向链表L为空表时应满足（）。选项：A、L==NULLB、L-prior==L-nextC、L-prior==NULLD、L-next==NULL正确答案:【L-next==NULL】4、问题：在只设有表尾指针rear但没有头结点的非空循环单链表中，删除表尾结点的时间复杂度为（）。选项：A、O(1)B、O(n)C、O(nlogn)D、正确答案:【O(n)】5、问题：当元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用（）存储结构。选项：A、顺序表B、静态单链表C、双向循环链表D、单链表E、循环单链表F、双向链表G、静态循环单链表正确答案:【顺序表】6、问题：已知指针p指向某双向链表的一个中间结点，下列语句序列实现的操作是（）。q=p-prior;p-prior=q-prior;q-prior-next=p;free(q);选项：A、删除p结点B、删除p结点的直接前驱结点C、删除p结点的直接后继结点D、删除p结点及其所有后继结点正确答案:【删除p结点的直接前驱结点】7、问题：下列关于存储相同数据元素的说法中，正确的是（）。选项：A、顺序存储比链式存储少占空间B、顺序存储比链式存储多占空间C、链式存储比顺序存储难于扩充空间D、顺序存储和链式存储都要求占用整块存储空间正确答案:【顺序存储比链式存储少占空间】8、问题：在单链表中，增加头结点的主要目的是（）。选项：A、方便运算的实现B、标识表结点中首元结点的位置C、使单链表至少有一个结点D、说明单链表是线性表的链式存储实现正确答案:【方便运算的实现】9、问题：非空的单循环链表的头指针为head，尾指针为rear，则下列条件中总是成立的为（）。选项：A、rear-next==headB、rear-nextnext==headC、head-next==rearD、head-next-next==rear正确答案:【rear-next==head】10、问题：双向链表中有两个指针域:prior和next，分别指回前驱及后继。设p指向链表中的一个结点，q指向待插入结点，现要求在p前插入q,则正确的插入语句序列为（）。选项：A、p-prior=q;q-next=p;p-prior-next=q;q-prior=p-prior;B、q-prior=p-prior;p-prior-next=q;q-next=p;p-prior=q-next;C、q-next=p;p-next=q;p-prior-next=q;q-next=p;D、p-prior-next=q;q-next=p;q-prior=p-prior;p-prior=q;E、q-prior=p-prior;q-next=p;q-prior-next=q;q-next-prior=q;正确答案:【p-prior-next=q;q-next=p;q-prior=p-prior;p-prior=q;#q-prior=p-prior;q-next=p;q-prior-next=q;q-next-prior=q;】11、问题：下面关于静态链表的表述中，错误的有（）。选项：A、静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。B、静态链表在创建时确定了能容纳的元素个数的最大值。C、静态链表与动态链表在元素的插入、删除操作上类似，不需做元素的移动。D、静态链表需要分配较大的连续空间。E、静态链表中元素的指针域存储的是下一个数据元素的内存地址。F、静态链表无法实现随机存取。G、所谓静态链表就是不允许插入和删除元素的链表。正确答案:【静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。#静态链表中元素的指针域存储的是下一个数据元素的内存地址。#所谓静态链表就是不允许插入和删除元素的链表。】12、问题：下列关于线性表的描述中，正确的是（）。选项：A、线性表的顺序存储结构优于其链式存储结构。B、线性表如果需要频繁进行插入和删除结点操作，顺序存储结构更优于链式存储结构。C、线性表的顺序存储结构和链式存储结构都可以进行顺序存取。D、顺序存储结构只能用于存储线性结构。E、读取线性表的第i个元素所需的时间与i的大小有关。F、静态链表需要分配较大的连续空间，插入和删除不需要移动元素。G、在一个长度为n的有序单链表中插入一个新结点并仍保持有序的时间复杂度为O(n)。H、在单链表中，可以从头结点开始查找任何一个结点。正确答案:【线性表的顺序存储结构和链式存储结构都可以进行顺序存取。#静态链表需要分配较大的连续空间，插入和删除不需要移动元素。#在一个长度为n的有序单链表中插入一个新结点并仍保持有序的时间复杂度为O(n)。#在单链表中，可以从头结点开始查找任何一个结点。】13、问题：如果要在单链表中删除p所指结点，可执行如下语句序列：q=p-next;p-date=q-date;p-next=();free(q);选项：A、p-next-nextB、qC、q-nextD、q-next-nextE、p正确答案:【p-next-next#q-next】14、问题：在一个长度为n(n1)的带头结点的单链表上，设有头尾两个指针，下列操作中执行时间与n无关的有（）。选项：A、删除表中的第一个元素B、删除表中最后一个元素C、在第一个元素前插入一个新元素D、在最后一个元素后插入一个新元素E、在第一个元素后插入一个新元素F、在最后一个元素前插入一个新元素正确答案:【删除表中的第一个元素#在第一个元素前插入一个新元素#在最后一个元素后插入一个新元素#在第一个元素后插入一个新元素#在最后一个元素前插入一个新元素】15、问题：在双向链表中，删除指针p所指的结点时，则修改指针的正确语句序列为（）。选项：A、p-prior-next=p-next;p-next-prior=p-prior;B、p-prior=p-prior-prior;p-prior-next=p;C、p-next-prior=p;p-next=p-next-next;D、p-next=p-prior-prior;p-prior=p-next-next;E、p-next-prior=p-prior;p-prior-next=p-next;正确答案:【p-prior-next=p-next;p-next-prior=p-prior;#p-next-prior=p-prior;p-prior-next=p-next;】3.1栈的定义与实现1、问题：一个栈的入栈序列为1,2,3,…,n，其出栈序列是。若，则为（）。选项：A、iB、n-iC、n-i+1D、不确定正确答案:【n-i+1】2、问题：设栈最大长度为3，入栈序列为1、2、3、4、5、6，则不可能的出栈序列是（）。选项：A、1、2、3、4、5、6B、2、1、3、4、5、6C、3、4、2、1、5、6D、4、3、2、1、5、6正确答案:【4、3、2、1、5、6】3、问题：在n个单元的顺序栈中，假设以地址高端（下标为n-1的单元）作为栈底，以top作为栈顶指针，则向栈中压入一个元素时，top的变化是（）。选项：A、top不变B、top=top-nextC、top=top-1D、top=top+1正确答案:【top=top-1】3.2栈的应用举例（一）——数制转换、括号匹配、行编辑器1、问题：利用栈将十进制数N（N100）转换为二进制数时，为了确保栈在处理过程中不会发生上溢，则该栈至少要有（）个存储单元。选项：A、6B、7C、8D、9正确答案:【7】2、问题：利用栈对表达式{(a-b)/[c*(d+e)]*(f-g)}进行括号匹配的检验时，该栈至少要有（）个存储单元才能确保不发生上溢。选项：A、3B、5C、7D、9正确答案:【3】3、问题：如果“#”表示退格符，“@”表示退行符，则从终端接收字符串“fro##or@while##te”后，栈中从栈底到栈顶的内容为（）。选项：A、forwhiteB、whiteC、froE、or@whileG、teH、whileJ、te正确答案:【white】3.2栈的应用举例（三）—表达式求值1、问题：利用栈求表达式的值时，假设操作符栈OPND只有2个存储单元。在处理下列表达式的过程中，不会发生上溢的是（）。选项：A、A-B*(C-D)B、(A-B)*C-DC、(A-B*C)-DD、(A-B)*(C-D)正确答案:【(A-B)*C-D】2、问题：表达式(a+b)*(c+d)-e的后缀表达式是（）。选项：A、abcde++*-B、ab+cde+*-C、ab+cd+e*-D、ab+cd+*e-正确答案:【ab+cd+*e-】3.3栈与递归的实现（二）——递归的实现1、问题：递归函数如下：voidf(intn){printf(%d,n%10);if(n/10!=0)f(n/10);}执行语句f(857)的输出结果是（）。选项：A、857B、758C、75D、7正确答案:【758】2、问题：递归函数如下：voidprint(intw){inti;if(w!=0){print(w-1);for(i=1;i=w;i++)printf(%3d,i);printf(\n);}}执行语句print(3)的输出结果是（）。选项：A、112123B、123121C、122333D、333221正确答案:【112123】3.4队列的定义与实现（一）——定义和链队列1、问题：若用单链表来表示队列，则应该选用（）。选项：A、带尾指针的非循环队列B、带尾指针的循环链表C、带头指针的非循环链表D、带头指针的循环链表正确答案:【带尾指针的循环链表】2、问题：栈和队列的共同点是（）。选项：A、都是先进后出B、都是后进先出C、只允许在端点处插入和删除元素D、没有共同点正确答案:【只允许在端点处插入和删除元素】3、问题：在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据打印，该缓冲区应是一个（）结构。选项：A、数组B、线性表C、堆栈D、队列正确答案:【队列】3.4队列的定义与实现（二）——循环队列和双端队列1、问题：循环队列存储在数组A[0..7]中，假设当前队尾指针Rear和队头Front的值分别为0和5，当队列中加入2个元素、删除3个元素后，Rear和Front的值分别为多少（）。选项：A、7和3B、0和2C、2和0D、3和7正确答案:【2和0】2、问题：某队列允许在两端进行入队操作，但仅允许在一端进行出队操作，则入队序列abcde不可能得到的出队序列是（）。选项：A、bacdeB、dbaceC、dbcaeD、ecbad正确答案:【dbcae】第三周栈和队列单元测验1、问题：一个栈的入栈序列为1,2,3,…,n，其出栈序列是。若，则可能取值的个数是（）。选项：A、n-3B、n-2C、n-1D、nE、F、n(n-1)G、正确答案:【n-1】2、问题：循环队列Q采用数组空间Q.base[0,n-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（）。选项：A、rear-frontB、rear-front+1C、rear-front+nD、(rear-front+n)%nE、rear-front-1F、(rear-front)%n正确答案:【(rear-front+n)%n】3、问题：已知操作符包括“+”，“-”，“/”，“(”和“)”。将中缀表达式a+b-a*((c+d)/e-f)+g转换为等价的后缀表达式ab+acd+e/f-*-g+时，用栈来存放暂时还不能确定运算次序的操作符。若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是()。选项：A、5B、7C、8D、11正确答案:【5】4、问题：在宾馆的客房管理中，为了保证每间客房硬件设施的磨损率尽可能均等，可以利用（）这种数据结构来管理空闲的客房，以使得每间客房的使用率尽可能均等。选项：A、线性表B、栈C、队列D、双端队列E、双栈F、超栈G、超队列正确答案:【队列】5、问题：以下方法中，（）不能区分循环队列的满与空。选项：A、牺牲一个存储单元B、设置一个标志变量C、判断头尾指针相等D、使用一个计数器正确答案:【判断头尾指针相等】6、问题：设栈S用顺序存储结构表示，则栈S为空的条件是（）。选项：A、S.top!=S.baseB、S.top==S.baseC、S.top!=S.base+nD、S.top==S.base+n正确答案:【S.top==S.base】7、问题：设有一空栈，现有输入序列为1，2，3，4，5，经过PUSH，PUSH，POP，GetTop，PUSH，GetTop，PUSH，POP，PUSH后，得到的输出序列为（ꢀ）。选项：A、5，4，3，2，1B、2，1，3，4C、2，3D、2，4正确答案:【2，4】8、问题：链栈与顺序栈相比，有一个比较明显的优点是（ꢀ）。选项：A、插入操作更加方便B、通常不会出现栈满的情况C、不会出现栈满的情况D、删除操作更加方便正确答案:【通常不会出现栈满的情况】9、问题：利用栈将十进制正数N（N）转换为十六进制数时，为了确保栈在处理过程中不会发生上溢，则该栈至少要有（）个存储单元。选项：A、3B、4C、5D、6正确答案:【4】10、问题：下列关于栈的叙述中，错误的是（）。选项：A、采用非递归方式重写递归程序是必须使用栈。B、函数调用时，系统要用栈保存必要的信息。C、只要确定了入栈次序，即可确定出栈次序。D、栈是一种受限的线性表，允许在其两端进行操作。E、消除递归不一定需要使用栈。F、进栈和出栈操作的算法时间复杂度均为O(n)。G、两个栈共享一片连续的内存空间时，为了提高内存利用率、减少溢出，应当把两个栈的栈底分别设置在整篇内存空间的两端。正确答案:【采用非递归方式重写递归程序是必须使用栈。#只要确定了入栈次序，即可确定出栈次序。#栈是一种受限的线性表，允许在其两端进行操作。#进栈和出栈操作的算法时间复杂度均为O(n)。】11、问题：下列关于循环队列的叙述中，正确的是（）。选项：A、循环队列不会产生假溢出。B、循环队列也存在空间溢出问题。C、循环队列比非循环队列节省空间。D、循环队列一定优于非循环队列。E、循环队列入队操作的复杂度比非循环队列高。F、循环队列是一种顺序存储的线性结构。正确答案:【循环队列不会产生假溢出。#循环队列也存在空间溢出问题。#循环队列是一种顺序存储的线性结构。】12、问题：银行柜台有2个服务窗口，客户可以在其中任意一个窗口排队办理业务，一旦开始排队，就不能够再进入到另一个队列中。客户x的业务办理完成后，银行系统会在今日流水记录的尾部新增一条流水记录x。已知在某日银行开门营业后，依次有a,b,c,d,e,f,g共7位客户前来办理业务，且每人只办理一次。以下四个流水记录中，一定错误的是（）。选项：A、abcdefgB、abdcfegC、abfcgdeD、gfedcbaE、adcbgefF、afbgcdeG、dacbegfH、eabdfcg正确答案:【gfedcba#adcbgef#dacbegf#eabdfcg】4.1串的定义1、问题：若串s=progress，其子串的个数是（）。选项：A、8B、35C、37D、256正确答案:【35】2、问题：串是一种特殊的线性表，其特殊性体现在（）。选项：A、可以顺序存储B、数据元素是一个字符C、可以链接存储D、数据元素可以是多个字符正确答案:【数据元素是一个字符】3、问题：若串S1=‘ABCDEFG’,S2=‘9898’,S3=‘TTT’,S4=‘012345’,执行concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2)))其结果为（）。选项：A、ABCTTTG0123B、ABCDTTT2345C、ABCTTTG1234D、ABCDTTT1234正确答案:【ABCTTTG1234】4.2串的表示和实现1、问题：对于一个链串s，查找第i个元素的算法时间复杂度为（）。选项：A、O(1)B、O(n)C、D、以上都不对正确答案:【O(n)】2、问题：若链串结点的定义如下所示，每个字符占1个字节，指针占4个字节，则该链串的存储密度为（）。typedefstructnode{chardata[4];structnode*next;}LinkStrNode;选项：A、1/4B、1/2C、2/3D、3/4正确答案:【1/2】3、问题：下列关于串的说法，错误的是（）。选项：A、串是由有限个字符构成的序列，子串是主串中任意字符构成的有限序列。B、串长度为串中不同字符的个数。C、串通常有顺序存储和链式存储两种存储结构。D、空串就是由空格构成的串。正确答案:【串是由有限个字符构成的序列，子串是主串中任意字符构成的有限序列。#串长度为串中不同字符的个数。#空串就是由空格构成的串。】4.3串的模式匹配算法（一）——朴素算法1、问题：在执行朴素的模式匹配算法时，最坏的情况为每次失配的字符均出现在（）。选项：A、模式串的最末字符B、主串的第一个字符C、模式串的第一个字符D、主串的最末字符正确答案:【模式串的最末字符】2、问题：设主串s=ababaaaba，模式串t=ababadd，采用朴素的模式匹配算法，第一次出现“失配”（s[i]≠t[j]）时，i=j=6，则下次开始匹配时，i和j的值分别是（）。【提示：这里i和j的取值范围从1开始】选项：A、i=2,j=1B、i=6,j=4C、i=6,j=1D、i=3,j=1正确答案:【i=2,j=1】4.3串的模式匹配算法（二）——KMP算法1、问题：设acbcaca是模式串，则它的next数组元素依次为（）。选项：A、0112122B、0111123C、0111221D、0111132正确答案:【0111123】2、问题：设abcaabbabcab是模式串，则它的next数组元素依次为（）。选项：A、011122112112B、011122312345C、011021301101D、011021101101正确答案:【011122312345】4.3串的模式匹配算法（三）——KMP算法1、问题：设abcaabbabcab是模式串，则它的nextval数组元素依次为（）。选项：A、011122112112B、011122312342C、011021301105D、011011101101正确答案:【011021301105】2、问题：设abcaacabaca是模式串，则它的nextval数组元素依次为（）。选项：A、01112212321B、01102201320C、01101101110D、01101201210正确答案:【01102201320】第四周串单元测验1、问题：文本编辑器中为了便于管理文本的页和行，在进入文本编辑前会先为文本建立相应的页表和行表，页表的每一项给出了页号和该页的起始行号，而行表的每一项则指示了每一行的行号、起始地址和该行子串的长度。就文本编辑过程中行表和页表的维护而言，下列说法中正确的是（）。选项：A、在某行内插入若干字符，只需要修改行表中该行的长度。B、插入一行，不仅涉及行表的插入，可能还要涉及页表的修改或插入。C、若被删除的行是所在页的起始行，只需修改页表中相应页的起始行号。D、在某行内修改若干字符，一定会改变行表中该行的长度。E、删除一行，不仅涉及行表的删除，可能还要涉及页表的修改或删除。正确答案:【插入一行，不仅涉及行表的插入，可能还要涉及页表的修改或插入。#删除一行，不仅涉及行表的删除，可能还要涉及页表的修改或删除。】2、问题：已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”。采用KMP算法进行匹配，第一次出现“失配”（s[i]≠t[j]）时，i=j=5，则下次开始匹配时，i和j的值分别是（）。【出自：2015年全国统考408，提示：这里i、j的取值范围是从0开始的】选项：A、i=1,j=0B、i=5,j=0C、i=5,j=2D、i=6,j=2E、i=6,j=0正确答案:【i=5,j=2】3、问题：设acbcaca是模式串，则在进行KMP算法进行匹配时，它的next数组元素依次为（）。选项：A、0112122B、0111123C、0111221D、0111132E、0111113正确答案:【0111123】4、问题：设串S1='1234567'，S2='abab'，S3='AAA'，S4='+-*/@#'，则执行replace(S1,substr(S1,4,length(S3)),concat(S3,substr(S4,length(S2),index(S2,'a'))))的结果串是（）。选项：A、'1234AAA@'B、'123AAA/7'C、'123AAA7'D、'123AAA/@E、7'正确答案:【'123AAA/7'】5、问题：设ababaabab是模式串，则它的nextval数组元素依次为（）。选项：A、010104101B、010102101C、010100011D、010101011E、001231234正确答案:【010104101】6、问题：设主串s=ababaaababaa，模式串t=ababaddecgg，采用改进的KMP算法（nextval数组）进行匹配，第一次出现“失配”（s[i]≠t[j]）时，i=j=6，则下次开始匹配时，i和j的值分别是（）。【提示：这里i、j的取值是从1开始的】选项：A、i=6,j=4B、i=6,j=2C、i=6,j=1D、i=7,j=1E、i=7,j=2F、i=7,j=3G、i=7,j=5H、i=6,j=3I、i=7,j=4正确答案:【i=6,j=4】7、问题：设主串T=abaabaabcabaabc，模式串S=“abaabc，采用KMP算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是（）。选项：A、9B、10C、12D、15正确答案:【10】8、问题：下列关于串的叙述，正确的是（）。选项：A、串是一种数据对象和操作都特殊的线性表。B、空串与空格串是相同的。C、若串S的长度为n且字符各不相同，则S的子串个数为n(n+1)/2+1。D、KMP算法的特点是在模式匹配时指示主串的指针不会回溯。E、设模式串的长度为m，主串的长度为n，当，朴素的模式匹配算法所花的时间代价可能会更少。且处理只匹配一次的模式时F、串中的元素只能是字母。G、两个字符串相等的条件是两个串的长度相等，并且两个串包含的字符相同。正确答案:【串是一种数据对象和操作都特殊的线性表。#若串S的长度为n且字符各不相同，则S的子串个数为n(n+1)/2+1。#KMP算法的特点是在模式匹配时指示主串的指针不会回溯。#设模式串的长度为m，主串的长度为n，当只匹配一次的模式时，朴素的模式匹配算法所花的时间代价可能会更少。】且处理9、问题：对于串的各种基本操作StrAssign、StrCompare、StrLength、SubString、Concat、DestroyString、ClearString、StrCopy、StrEmpty、Replace、StrInsert、StrDelete、Index，其中（）可以由其他基本操作构造而得。选项：A、StrAssignB、StrCompareC、StrLengthD、SubStringE、ConcatF、DestroyStringG、ClearStringH、StrCopyI、StrEmptyJ、ReplaceK、StrInsertL、StrDeleteM、Index正确答案:【StrCopy#StrEmpty#Replace#StrInsert#StrDelete#Index】5.1数组的定义及顺序存储1、问题：如果一个二维数组A[1..m,1..n]按行优先顺序存储，设的相对地址为0，则任一元素A[i,j]的相对地址为（）。选项：A、i+jB、i*n+jC、(i-1)*n+jD、(i-1)*n+j-1正确答案:【(i-1)*n+j-1】2、问题：如果一个二维数组A[4][6]（即A是一个4行6列的二维数组）按列优先顺序存储（数组下标从0开始），每个元素占一个存储单元，数组首地址为100，则元素a[1,4]的地址为（）。选项：A、125B、120C、117D、113正确答案:【117】3、问题：数组A三维的长度分别为，每个数组元素占一个存储单元，LOC(0,0,0)为基址。若以行序为主序，则元素A[i][j][k]的地址为（）（其中，）。选项：A、B、C、D、正确答案:【】4、问题：二维数组是一种非线性结构。选项：A、正确B、错误正确答案:【正确】5.2矩阵的压缩存储（一）——特殊矩阵1、问题：在n*n对称矩阵的压缩存储中，需要保存的元素个数是（）。选项：A、n(n+1)/2B、n(n-1)/2C、D、不确定正确答案:【n(n+1)/2】2、问题：将一个三对角矩阵度至少为（）。按列优先顺序存储到一维数组B中，则B的长选项：A、3n-2B、3n-1C、3nD、3n+1正确答案:【3n-2】3、问题：对一些特殊矩阵采用压缩存储的目的主要是为（）。选项：A、表达变得简单B、减少不必要的存储空间的开销C、去掉矩阵中的多余元素D、对矩阵元素的存取变得简单正确答案:【减少不必要的存储空间的开销】5.2矩阵的压缩存储（二）——三元组顺序表1、问题：设已知一个稀疏矩阵的三元组顺序表为：((1,2,3)，(1,6,1)，(3,1,5)，(3,2,-1)，(4,5,4)，(5,1,-3))，则其转置矩阵的三元组表中的第3个三元组为（）。选项：A、(2,1,3)B、(3,1,5)C、(3,2,-1)D、(2,3,-1)正确答案:【(2,1,3)】2、问题：若采用三元组顺序表来压缩存储稀疏矩阵，只要把每个三元组的行下标和列下标互换，就完成了对该矩阵的转置运算。选项：A、正确B、错误正确答案:【错误】3、问题：稀疏矩阵压缩存储之后，就失去了随机存取的特性。选项：A、正确B、错误正确答案:【正确】5.2矩阵的压缩存储（三）——行逻辑链接的顺序表1、问题：如果稀疏矩阵N的rpos值如下表所示，则该矩阵的第5行具有的非零元个数为（）。row123456rpos[row]134558选项：A、0B、3C、5D、8正确答案:【3】2、问题：设已知一个稀疏矩阵的三元组顺序表为：((1,2,3)，(1,6,1)，(3,1,5)，(3,2,-1)，(4,5,4)，(5,1,-3))，则其转置矩阵的rpos[5]为（）（假设数组下标从1开始）。选项：A、1B、4C、5D、6正确答案:【5】5.2矩阵的压缩存储（四）——十字链表1、问题：当高阶矩阵中非零元素个数较少且位置或个数经常变动时，采用（）存储结构更为恰当。选项：A、二维数组B、三元组顺序表C、十字链表D、行逻辑链接的顺序表正确答案:【十字链表】2、问题：下列关于十字链表的叙述，正确的是（）。选项：A、十字链表可以用于稀疏矩阵的存储表示。B、十字链表的结点中只需要记录非零元的值，无需记录其在矩阵中的位置。C、采用十字链表存储时，实现两个矩阵相加的算法复杂度为O(ta+tb)，其中ta和tb分别为两个矩阵中的非零元个数。D、采用十字链表存储时无法实现矩阵乘法。正确答案:【十字链表可以用于稀疏矩阵的存储表示。#采用十字链表存储时，实现两个矩阵相加的算法复杂度为O(ta+tb)，其中ta和tb分别为两个矩阵中的非零元个数。】5.3广义表1、问题：广义表E=(e,a,E)的长度为（）。选项：A、2B、3C、5D、无穷大正确答案:【3】2、问题：广义表(a,(a,b),d,e,((i,j),k))的长度和深度分别为（）。选项：A、6和4B、8和4C、5和3D、5和2正确答案:【5和3】3、问题：广义表操作GetTail(GetHead(GetTail(((e,f),(g,h)))))得到的结果是（）。选项：A、()B、hC、(h)D、(g,h)正确答案:【(h)】4、问题：广义表的存储结构应采用（）。选项：A、顺序存储B、链式存储C、十字链表存储D、循环链表存储正确答案:【链式存储】第五周数组和广义表单元测验1、问题：4行5列的二维数组M（数组下标从0开始），M按行优先顺序存储时元素M[2][4]的起始地址与M按列优先顺序存储时元素（）的起始地址相同。选项：A、M[1][3]B、M[2][3]C、M[2][4]D、M[3][3]E、M[3][2]F、M[3][1]G、M[4][2]正确答案:【M[2][3]】2、问题：对广义表E=((a,((b),c)),e,E)实施由取表头GetHead和取表尾GetTail组成的操作序列（）得到的结果是c。选项：A、GetHead(GetTail(GetHead(GetTail(GetHead(E)))))B、GetHead(GetTail(GetTail(E)))C、GetHead(GetHead(GetTail(GetHead(GetHead(GetTail(GetHead(GetHead(E))))))))D、GetHead(GetTail(GetHead(E)))E、GetHead(GetTail(GetHead(GetTail(E))))正确答案:【GetHead(GetTail(GetHead(GetTail(GetHead(E)))))】3、问题：若广义表满足GetHead(A)=GetTail(A)，则A为（）。选项：A、()B、(())C、((),())D、((),(),())E、((()))正确答案:【(())】4、问题：设采用一维数组来存放一个m行n列的对称矩阵，且只存放矩阵的下三角阵。当需要访问上三角阵第i行，第j列的元素（ji），其数组下标是（）。（说明：i、j及一维数组下标均从0开始）选项：A、B、C、D、E、F、G、正确答案:【】5、问题：数组A[4][5][6][7]的每个元素占4个字节，将其按列优先次序存储在起始地址为300（即LOC(A[0][0][0][0])=300）的内存单元中，则元素A[1][3][5][2]的地址为（）。选项：A、1712B、653C、508D、1132E、1792F、673正确答案:【1712】6、问题：设广义表A=(a,(((b,c),(d,e)),f),g)，Head(p)为求广义表p的表头的函数，Tail(p)为求广义表p的表尾的函数，那么从表A中取出子表(b,c)的操作为（）。选项：A、Head(Head(Head(Tail(A))))B、Tail(Head(Head(Head(A))))C、Head(Head(Head(Head(Tail(A)))))D、Tail(Head(Head(Head(Head(A)))))E、Head(Head(Head(Head(Head(Head(Tail(A)))))))F、Tail(Head(Head(Head(Head(Head(Head(A)))))))正确答案:【Head(Head(Head(Tail(A))))】7、问题：对于五对角矩阵至少是（）。选项：，已按行压缩存储到一维数组B中，则B的长度A、5nB、5n-2C、5n-4D、5n-6E、5n-8正确答案:【5n-6】8、问题：将一个三对角矩阵A[100][100]中的元素按行存储在一维数组B[298]中，矩阵A中的元素A[55][56]在数组B中的下标为（）。（说明：矩阵及数组的下标均从0开始）选项：A、164B、165C、166D、167正确答案:【166】9、问题：一个矩阵从a[0][0]开始存放，每个元素占用4个存储单元，若a[8][9]的存储地址为2676，a[12][17]的存储地址为3028，则此矩阵的存储方式是（）。选项：A、只能以行为主序存储B、只能以列为主序存储C、以行或以列为主序存储均可D、以上都不对正确答案:【只能以行为主序存储】10、问题：与三元组顺序表相比，稀疏矩阵用十字链表表示，其优点在于（）。选项：A、便于实现增加或减少矩阵中非零元素的操作B、便于实现增加或减少矩阵元素的操作C、可以节省存储空间D、可以更快地查找某个非零元素正确答案:【便于实现增加或减少矩阵中非零元素的操作】11、问题：对稀疏拒阵采用压缩存储，其缺点之一是（）。选项：A、无法判定矩阵有多少行多少列B、无法根据行列号查找某个矩阵元素C、无法根据行列号计算矩阵元素的存储地址D、使矩阵元素之间的逻辑关系更加复杂正确答案:【无法根据行列号计算矩阵元素的存储地址】12、问题：设有一个12′12的对称矩阵M，将其上三角部分的元素（1≤i≤j≤12）按行优先存人C语言的一维数组N中，元素选项：在N中的下标是（）。A、50B、51C、55D、66正确答案:【50】13、问题：将一个10′10对称矩阵M的上三角部分的元素（1≤i≤j≤10）按列优先存入C语言的一-维数组N中，元素选项：在N中的下标是（）。A、15B、16C、22D、23E、21正确答案:【22】14、问题：适用于压缩存储稀疏矩阵的两种存储结构是（）和（）。选项：A、二叉链表B、三元组表C、十字链表D、邻接矩阵E、双向链表F、邻接多重表正确答案:【三元组表#十字链表】15、问题：下列关于广义表的叙述中，正确的是（）。选项：A、广义表可以是一个多层次的结构、B、广义表至少有一个元素。C、广义表可以被其他广义表所共享。D、广义表不能是递归表。E、广义表的长度总是有限的。F、广义表必须至少有一个元素是子表。G、广义表不可以是自身的子表。H、广义表的深度总是有限的。正确答案:【广义表可以是一个多层次的结构、#广义表可以被其他广义表所共享。#广义表的长度总是有限的。】16、问题：下列关于特殊矩阵和稀疏矩阵的说法，正确的有（）。选项：A、特殊矩阵压缩存储后，无法实现对其元素进行随机访问。B、以行为主序或以列为主序对于多维数组的存储没有影响。C、稀疏矩阵中值为零的元素较多，可以采用三元组表存储。D、在一般情况下，采用压缩存储后，对称矩阵是所有特殊矩阵中存储空间节约最多的。E、数组就是矩阵，矩阵就是数组。F、采用三元组表表示稀疏矩阵，主要目的是为了节省存储空间。G、采用十字链表存储稀疏矩阵，主要目的是为了节省运算时间。正确答案:【以行为主序或以列为主序对于多维数组的存储没有影响。#稀疏矩阵中值为零的元素较多，可以采用三元组表存储。#采用三元组表表示稀疏矩阵，主要目的是为了节省存储空间。】6.1树的定义1、问题：在一棵度为3的树上，度为3的结点数为3个，度为2的结点数为2个，度为1的结点数为2个，则度为0的结点数为（）个。选项：A、不确定B、8C、9D、10正确答案:【9】2、问题：树最适合用来表示（）。选项：A、有序数据元素B、无序数据元素C、元素之间具有分支层次关系的数据D、元素之间无联系的数据正确答案:【元素之间具有分支层次关系的数据】3、问题：假设一棵树的嵌套括号表示为(a(b(e),c(f(h,i,j),g),d))，则该树上终端结点的个数为（）。选项：A、4B、5C、6D、7正确答案:【6】4、问题：一棵含有n个结点的m(m=3)叉树，其分支数为（）。选项：A、mnB、n+mC、n-1D、无法确定正确答案:【n-1】6.2二叉树（一）——定义和性质1、问题：一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。选项：A、250B、500C、254D、501正确答案:【501】2、问题：深度为6（根的层次为1）的二叉树至多有()个结点。选项：A、62B、63C、64D、65正确答案:【63】3、问题：设高度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含的结点上下限分别为（）。选项：A、B、C、D、正确答案:【】4、问题：在一棵含有n个结点的二叉树中，若度为2的结点数为，度为1的结点数为，度为0的结点数为，则该树的最大高度为（）。选项：A、nB、C、D、正确答案:【n#】5、填空题：4个结点的二叉树可以有种不同的形态。正确答案:【14】6.2二叉树（二）——存储结构1、问题：假设二叉树的顺序存储结构如下图所示：1234567891011121314abc?d?e??fg??h则该二叉树的中序遍历序列为（）。选项：A、fdgbacheB、bfdgacheC、bfdgahecD、fdgbahec正确答案:【bfdgache】2、问题：含有n个结点的二叉树采用顺序存储结构，至少需要分配（）个存储单元。选项：A、nB、2nC、D、正确答案:【】3、问题：含有n个结点的二叉树，若采用二叉链表存储，则整个存储结构中只有（）个非空指针域。选项：A、n-1B、nC、n+1D、不确定正确答案:【n-1】4、问题：含有n个结点的二叉树，若采用三叉链表存储，则整个存储结构中有（）个空的指针域。选项：A、n-1B、nC、n+1D、n+2正确答案:【n+2】6.3二叉树的遍历（一）——递归算法1、问题：任何一棵二叉树的叶结点在先序、中序和后序遍历的序列中的相对次序（）。选项：A、不发生变化B、发生变化C、不能确定D、以上都不对正确答案:【不发生变化】2、问题：某非空二叉树的前序序列和后序序列正好相反，则二叉树一定是（）的二叉树。选项：A、只有一个结点B、高度等于其结点数C、任一结点无左孩子D、任一结点无右孩子正确答案:【高度等于其结点数】3、问题：在一非空二叉树的中序遍历序列中，根结点的右边（）。选项：A、只有右子树上的所有结点B、只有右子树上的部分结点C、只有左子树上的部分结点D、只有左子树上的所有结点正确答案:【只有右子树上的所有结点】6.3二叉树的遍历（二）——非递归算法1、问题：欲实现二叉树的非递归后序遍历算法而不必使用栈结构，则二叉树应采用（）存储结构。选项：A、二叉链表B、三叉链表C、顺序D、广义表正确答案:【三叉链表】2、问题：非递归中序遍历（空指针进栈）含有n个结点高度为h的二叉树时，为了确保栈在处理过程中不会发生上溢，则该栈至少要有（）个存储单元。选项：A、nB、n+1C、hD、h+1正确答案:【h+1】3、问题：非递归中序遍历二叉树时，当遍历到某个结点的时候，栈中的所有元素均为该元素的祖先。选项：A、正确B、错误正确答案:【正确】6.3二叉树的遍历（三）——应用1、问题：设一棵二叉树的中序遍历序列为BDCAE，后序遍历序列为DBEAC，则这棵二叉树的前序遍历序列为（）。选项：A、CAEBDB、CDBEAC、CBDAED、CBDEA正确答案:【CBDAE】2、问题：设一棵二叉树的先序遍历序列为ABCDEFG，中序遍历序列为BDCEAGF，则这棵二叉树的后序遍历序列为（）。选项：A、CABDEFGB、DACEFBGC、DECBGFAD、ADCFEG正确答案:【DECBGFA】3、问题：设一棵二叉树的扩展后序遍历序列为二叉树的前序和中序遍历序列分别为（）。选项：，则这棵A、ABCDEFG和DECBGFAB、ABCDEFG和BDCEAGC、AFGBDEC和CBEDAFGD、ABCDEFG和CBEDAFG正确答案:【ABCDEFG和CBEDAFG】第六周树和二叉树（上）单元测验1、问题：已知一棵二叉树有10个结点，则其中至多有（）个结点有两个子结点。选项：A、3B、4C、5D、6E、1F、7正确答案:【4】2、问题：若二叉树的先序遍历序列为EFHIGJK，中序遍历序列为HFIEJKG，则该二叉树的右子树的根是（）。选项：A、EB、FC、GD、HE、IF、JG、K正确答案:【G】3、问题：若一个深度为3的二叉树的先序遍历为ABCDE，则该二叉树有（）种可能的形态。选项：A、3B、4C、5D、6E、7F、8正确答案:【6】4、问题：设x,y是二叉树上的两个结点，在先序遍历序列中x在y之前，而在后序遍历序列中x在y之后，则x和y的关系是（）。选项：A、x是y的左兄弟B、x是y的右左兄弟C、x是y的祖先D、x是y的子孙正确答案:【x是y的祖先】5、问题：一棵满二叉树有m个叶子结点和n个结点，其高度为h，则有（）。选项：A、n=h+mB、h+m=2nC、m=h-1D、E、F、2m-1=nG、H、正确答案:【##2m-1=n】6、问题：在一棵度数为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是（）。选项：A、41B、82C、113D、122正确答案:【82】7、问题：若一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1，则该二叉树的中序遍历序列不会是（）。选项：A、1,2,3,4B、2,1,3,4C、3,2,4,1D、4,3,2,1E、3,4,2,1F、3,4,1,2G、1,3,4,2正确答案:【2,1,3,4#3,2,4,1#3,4,1,2】8、问题：若有一棵完全二叉树有384个叶子结点，且最后一层有奇数个结点，则该二叉树的结点个数是（）。选项：A、765B、766C、767D、768正确答案:【768】9、问题：已知一棵含45个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（）。选项：A、0B、1C、2D、22E、23F、43G、44H、45正确答案:【44】10、问题：设一棵非空完全二叉树T的所有叶结点均位于同一层，且每个非叶结点都有2个子结点。若T有k个叶结点，则T的结点总数是（）。选项：A、2k-1B、2kC、D、正确答案:【2k-1】11、问题：对于任意一棵高度为5且有10个结点的二叉树，若采用顺序存储结构保存，每个结点占1个存储单元（仅存放结点的数据信息），则存放该二叉树需要的存储单元数量至少是（）。选项：A、31B、16C、15D、10E、63F、22正确答案:【31】12、问题：给定二叉树如右图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列是3,1,7,5,6,2，4，则其遍历方式是（）。选项：A、LRNB、NRLC、RLND、RNL正确答案:【RNL】13、问题：已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是（）。选项：A、39B、52C、111D、119正确答案:【111】14、问题：下列关于树的叙述中，正确的有（）。选项：A、树和二叉树是两种不同的树形结构。B、树中元素之间是多对多的关系。C、一棵有n个结点的树中，无论其度是多少，分支数必定为n-1。D、对一棵树进行先根遍历和后根遍历时，其叶子结点出现的相对次序都是相同的。E、一棵树上的任一结点要么是叶子，要么是内部结点。F、在一棵树的先根遍历序列中，若结点u出现在结点v之前，则u必定是v的祖先。正确答案:【树和二叉树是两种不同的树形结构。#一棵有n个结点的树中，无论其度是多少，分支数必定为n-1。#对一棵树进行先根遍历和后根遍历时，其叶子结点出现的相对次序都是相同的。】15、问题：下列关于二叉树的叙述中，正确的有（）。选项：A、n(n2)个结点的二叉树中至少有一个度为2的结点。B、任何一棵完全二叉树中，叶子结点或者和分支结点一样多，或者只比分支结点多一个。C、二叉树就是度为2的树。D、完全二叉树最适合采用顺序存储结构。E、满二叉树中的所有棵子树都是完全二叉树。F、完全二叉树中，若某个结点无左孩子，则其必为叶子。G、在叶子数目和权值均相同的所有二叉树中，最优二叉树一定是完全二叉树。正确答案:【任何一棵完全二叉树中，叶子结点或者和分支结点一样多，或者只比分支结点多一个。#完全二叉树最适合采用顺序存储结构。#满二叉树中的所有棵子树都是完全二叉树。#完全二叉树中，若某个结点无左孩子，则其必为叶子。】16、问题：一棵二叉树的先序遍历序列为ABCDEFG，它的中序遍历序列可能是（）。选项：A、CDBAFEGB、ABCDEFGC、BDCEAGFD、BGCDAEFE、CABDEFGF、DACEFBGG、ADCFEGBH、CGBAEDG正确答案:【CDBAFEG#ABCDEFG#BDCEAGF#ADCFEGB】6.4线索二叉树（一）——基本概念及查找方法1、问题：若对如下的二叉树进行中序线索化，则结