《MOOC 数据结构-厦门大学 中国大学慕课答案.docx》由会员分享,可在线阅读,更多相关《MOOC 数据结构-厦门大学 中国大学慕课答案.docx(129页珍藏版)》请在文库网上搜索。
1、 MOOC 数据结构-厦门大学 中国大学慕课答案1.1 什么是数据结构1、问题:数据结构的研究对象主要包括:选项:A、数据集合中元素之间的关系B、数据集合的存储实现方式C、对数据集合进行的操作D、操作算法优劣的评价正确答案:【数据集合中元素之间的关系#数据集合的存储实现方式#对数据集合进行的操作#操作算法优劣的评价】2、问题:数据结构主要研究非数值计算的问题。选项:A、正确B、错误正确答案:【正确】3、问题:数据结构的研究与计算机硬件无关。选项:A、正确B、错误正确答案:【错误】1.2 数据结构的基本概念(一)逻辑结构1、问题:数据的逻辑结构是指 ( )关系的整体。选项:A、数据存储结构之间B
2、、数据类型之间C、数据元素之间逻辑D、数据项之间逻辑正确答案:【数据元素之间逻辑】2、问题:以下说法不正确的是( )。选项:A、数据可由若干个数据元素构成。B、数据项是不可分割的最小可标识单位。C、数据项可由若干个数据元素构成。 D、数据元素是数据的最小单位。正确答案:【数据项可由若干个数据元素构成。#数据元素是数据的最小单位。】3、问题:数据的逻辑结构可以分为( )。选项:A、动态结构和静态结构B、线性结构和非线性结构C、内部结构和外部结构D、集合、线性结构、树形结构、图状结构正确答案:【线性结构和非线性结构#集合、线性结构、树形结构、图状结构】1.2 数据结构的基本概念(二)物理结构1、问
3、题:下面关于数据的逻辑结构与存储结构说法正确的是( )。选项:A、逻辑结构要体现出存储结构。B、存储结构要体现出逻辑结构。C、两者是一一对应的。D、二者毫无关系。正确答案:【存储结构要体现出逻辑结构。】2、问题:在数据的存储中,一个结点通常存储一个( )。选项:A、数据结构B、数据类型C、数据元素D、数据项正确答案:【数据元素】3、问题:在决定选取任何类型的存储结构时,一般不多考虑( )。选项:A、对数据有哪些运算B、结点个数的多少C、各结点的具体取何值D、所用编程语言实现这种结构是否方便正确答案:【各结点的具体取何值】1.3 抽象数据类型1、问题:以下关于 ADT 抽象数据类型说法错误的是(
4、 )。选项:A、ADT 建立的封装技术将可能的处理实现细节隐蔽起来。 B、可采用程序设计语言的控制结构和基本数据类型来实现 ADT 的所提供的逻辑接口。C、同一 ADT 只有唯一的数据结构可以实现。D、ADT 是对数据进行处理的一种逻辑描述。正确答案:【同一 ADT 只有唯一的数据结构可以实现。】2、问题:下列关于抽象数据类型(ADT)定义的说法,正确的有( )。选项:A、ADT 的定义只取决于它的一组逻辑特性。B、ADT 的定义与计算机内部如何表示和实现无关。C、不论 ADT 的内部结构如何变化,只要它的数学特性不变,都不影响它的外部使用。D、ADT 定义了一个完整的(狭义)数据结构。正确答
5、案:【ADT 的定义只取决于它的一组逻辑特性。#ADT 的定义与计算机内部如何表示和实现无关。#不论 ADT 的内部结构如何变化,只要它的数学特性不变,都不影响它的外部使用。#ADT 定义了一个完整的(狭义)数据结构。】1.4 什么是算法1、问题:计算机中算法是解决某一问题的有限运算序列,必须具备输入、输出、( )等 5 个特性。选项:A、确定性、有穷性和健壮性B、可读性、正确性和健壮性C、可行性、正确性和可读性D、可行性、确定性和有穷性正确答案:【可行性、确定性和有穷性】2、问题:数据的运算(即操作) ( )。选项:A、在不同计算机上的实现方法都是相同的。B、必须用程序设计语言来描述C、与采
6、用何种存储结构有关D、有算术运算和关系运算两大类正确答案:【与采用何种存储结构有关】3、问题:算法的设计目标有( )等等。选项:A、可行性B、健壮性C、有穷性 D、正确性正确答案:【健壮性#正确性】1.5 算法的分析与度量1、问题:算法分析的主要任务之一是分析( )。选项:A、算法中是否存在语法错误B、算法的执行时间与问题规模之间的关系C、算法中输入和输出之间的关系D、算法是否具有较好的可读性正确答案:【算法的执行时间与问题规模之间的关系】2、问题:给出算法的时间复杂度是属于一种( )。选项:A、事前统计的方法B、事前分析估算的方法C、事后统计的方法D、事后分析估算的方法正确答案:【事前分析估
7、算的方法】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、问题:下列程序段的时间复杂度是(
8、)。count=0;for (k=1;k=n;k*=2) for(j=1;j=n;j+) count+;选项:A、B、C、D、正确答案:【】4、问题:下列程序段的时间复杂度是( )。int k=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、问题:计算机所处理数据一般具有某种内在联系,这是指( )
9、。选项:A、数据与数据之间存在某种关系B、数据元素与数据元素之间存在某种关系C、元素内部存在某种结构D、数据项与数据项之间存在某种关系正确答案:【数据元素与数据元素之间存在某种关系】7、问题:数据的运算( )。选项:A、效率与采用何种存储结构有关B、是根据存储结构来定义的C、有算术运算和关系运算两大类D、必须用程序设计语言来描述正确答案:【效率与采用何种存储结构有关】8、问题:某算法的时间复杂度为 O(nlogn),表明该算法的( )。选项:A、问题规模是 O(nlogn)B、执行时间等于 O(nlogn)C、执行时间与 O(nlogn)成正比D、问题规模与 O(nlogn)成正比正确答案:【
10、执行时间与 O(nlogn)成正比】9、问题:下列程序段的时间复杂度是( )。int fact(int n) if (n=1) return 1; 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) Qij = 0;for (i=1; i=m1;
11、+i) for (j=1; j=n2; +j) for (k=1; k=n1; +k) Qij +=Mik * Nkj;选项: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、算法的优劣与算法描述语言无关,与
12、所用计算机也无关。F、算法原地工作的含义是指该算法不需要任何额外的辅助空间。G、对于相同规模的 n,时间复杂度 O(n)的算法运行时间总是小于时间复杂度的算法的运行时间。H、算法最终必须由计算机程序实现。I、算法的可行性是指代码不能有二义性。 J、算法可以用不同的语言描述,如果用 C 语言或 PASCAL 语言等高级语言来描述,则算法实际上就是程序了。K、健壮的算法不会因非法输入数据而出现莫名其妙的状态。正确答案:【算法的有穷性是指算法必须能在有限时间和有限步骤内执行完。#算法的优劣与算法描述语言无关,与所用计算机也无关。#健壮的算法不会因非法输入数据而出现莫名其妙的状态。】13、问题:下列叙
13、述正确的是( )。选项:A、数据元素是数据项中不可分割的最小可标识单位。B、从逻辑上可以把数据结构分为顺序结构、链式结构等类别。C、研究数据结构就是研究数据的逻辑结构和存储结构。D、数据类型可看成是程序设计语言中已实现的数据结构。E、数据元素之间的关联关系在数据的逻辑结构中体现。F、数据对象是由有限个类型相同的数据元素构成的。G、逻辑结构不相同的数据,必须采用不同类型的存储方法。H、如果数据元素值发生改变,则数据的逻辑结构也随之改变。I、数据结构是相互之间存在一种或多种特定关系的数据元素的集合。J、逻辑结构相同的数据,可以采用多种不同的存储方法。K、逻辑结构相同的数据,在设计存储结构时,它们的
14、节点类型也一定相同。L、选择数据结构时应考虑程序运行时所需输入和处理的数据总量。正确答案:【数据类型可看成是程序设计语言中已实现的数据结构。#数据元素之间的关联关系在数据的逻辑结构中体现。#数据对象是由有限个类型相同的数据元素构成的。#数据结构是相互之间存在一种或多种特定关系的数据元素的集合。#逻辑结构相同的数据,可以采用多种不同的存储方法。#选择数据结构时应考虑程序运行时所需输入和处理的数据总量。】2.1 线性表的定义(一)概念和 ADT1、问题:下列有关线性表的叙述中,正确的是( )。选项:A、线性表中元素之间的关系是线性关系。B、线性表中至少有一个元素。C、线性表中的任一元素有且仅有一个
15、直接前趋。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、无法确定正确
16、答案:【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、与删除元素的位置及顺序表的长度都无关正确答案:【与删除元素的位置及顺序表的长
17、度都有关】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
18、 的升序链表,若将它们合并为一个长度为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、所需存
19、储空间与线性表长度成正比。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
20、 = 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、问题:非空的循环单链表
21、 head 的尾结点 p 满足 ( )。选项:A、p - next = headB、p - next = NULLC、p = NULLD、p = head正确答案:【p - next = head】3、问题:对于长度为 n(n1)的双向链表 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 -
22、 next = head正确答案:【head - prior = head#head - next = head】2.5 顺序表与线性链表的比较(一)顺序表与链表1、问题:静态链表与顺序表相比,优点在于( )。选项:A、所有操作的算法实现更简单B、便于随机存取 C、便于插入和删除D、便于利用零散的存储空间正确答案:【便于插入和删除】2、问题:若某线性表最常用的操作是存取任意指定序号的元素和在表尾元素之后进行插入和删除操作,则采用( )存储方式最节省时间。选项:A、带头结点的单链表B、不带头结点的单链表C、带头结点的双向循环链表D、顺序表正确答案:【顺序表】3、问题:设线性表中有 2n 个元素,
23、以下操作中,( )在单链表上实现要比在顺序表上实现效率更高。选项:A、删除指定位置元素的下一个元素B、在最后一个元素的后面插入一个新元素C、顺序输出前 k 个元素D、交换第 i 个元素和第 n-i+1 个元素的值 (i=1, 2, , n)正确答案:【删除指定位置元素的下一个元素】2.5 顺序表与线性链表的比较(二)各种链表的对比1、问题:与非循环单链表相比,循环单链表的主要优点是( )。选项:A、不再需要头指针B、已知某个节点的位置后,能够容易找到它的前驱节点C、在进行插入、删除操作时,能更好地保证链表不断开D、从表中任意节点出发都能扫描到整个链表正确答案:【从表中任意节点出发都能扫描到整个
24、链表】2、问题:若某线性表最常用的操作是在表尾结点插入新结点和删除表尾结点,则采用( )存储方式最节省时间。选项:A、带头结点的双向循环链表B、不带头结点的单链表C、仅有尾指针的循环单链表D、仅有头指针的循环单链表正确答案:【带头结点的双向循环链表】 3、问题:若某线性表最常用的操作是在表尾结点之后插入新结点和删除表头结点,则采用( )存储方式最节省时间。选项:A、仅有头指针的循环单链表B、仅有尾指针的循环单链表C、带头结点的单链表D、带头结点的双向循环链表正确答案:【仅有尾指针的循环单链表】4、问题:下列关于链表的描述,正确的是( )。选项:A、在循环单链表中,从表中任一结点出发都可以通过前
25、后移动操作来遍历整个循环链表。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、删除表中的
26、最后一个元素。C、在第一个元素之前插入一个元素。D、在最后一个元素之前插入一个元素。E、在最后一个元素之后插入一个元素。F、在最后一个元素之后插入一个元素。正确答案:【在第一个元素之前插入一个元素。】3、问题:带头结点的双向链表 L 为空表时应满足( )。选项:A、L = NULLB、L - prior = L - next C、L - prior = NULLD、L - next = NULL正确答案:【L - next = NULL】4、问题:在只设有表尾指针 rear 但没有头结点的非空循环单链表中,删除表尾结点的时间复杂度为( )。选项:A、O(1)B、O(n)C、O(nlogn)D、
27、正确答案:【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 结点及其所有后继结点正
28、确答案:【删除 p 结点的直接前驱结点】7、问题:下列关于存储相同数据元素的说法中,正确的是( )。选项:A、顺序存储比链式存储少占空间B、顺序存储比链式存储多占空间C、链式存储比顺序存储难于扩充空间D、顺序存储和链式存储都要求占用整块存储空间正确答案:【顺序存储比链式存储少占空间】 8、问题:在单链表中,增加头结点的主要目的是( )。选项:A、方便运算的实现B、标识表结点中首元结点的位置C、使单链表至少有一个结点D、说明单链表是线性表的链式存储实现正确答案:【方便运算的实现】9、问题:非空的单循环链表的头指针为 head,尾指针为 rear, 则下列条件中总是成立的为( )。选项:A、rea
29、r-next = headB、rear-next next = 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-p
30、rior=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、问题:下面关
31、于静态链表的表述中,错误的有( )。选项:A、静态链表既有顺序存储的优点,又有动态链表的优点。所以,它存取表中第 i个元素的时间与 i 无关。B、静态链表在创建时确定了能容纳的元素个数的最大值。C、静态链表与动态链表在元素的插入、删除操作上类似,不需做元素的移动。D、静态链表需要分配较大的连续空间。E、静态链表中元素的指针域存储的是下一个数据元素的内存地址。F、静态链表无法实现随机存取。G、所谓静态链表就是不允许插入和删除元素的链表。正确答案:【静态链表既有顺序存储的优点,又有动态链表的优点。所以,它存取表中第 i 个元素的时间与 i 无关。#静态链表中元素的指针域存储的是下一个数据元素的内存
32、地址。#所谓静态链表就是不允许插入和删除元素的链表。】 12、问题:下列关于线性表的描述中,正确的是( )。选项:A、线性表的顺序存储结构优于其链式存储结构。B、线性表如果需要频繁进行插入和删除结点操作,顺序存储结构更优于链式存储结构。C、线性表的顺序存储结构和链式存储结构都可以进行顺序存取。D、顺序存储结构只能用于存储线性结构。E、读取线性表的第 i 个元素所需的时间与 i 的大小有关。F、静态链表需要分配较大的连续空间,插入和删除不需要移动元素。G、在一个长度为 n 的有序单链表中插入一个新结点并仍保持有序的时间复杂度为O(n)。H、在单链表中,可以从头结点开始查找任何一个结点。正确答案:
33、【线性表的顺序存储结构和链式存储结构都可以进行顺序存取。#静态链表需要分配较大的连续空间,插入和删除不需要移动元素。#在一个长度为 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 -
34、next】14、问题:在一个长度为 n (n1) 的带头结点的单链表上,设有头尾两个指针,下列操作中执行时间与 n 无关的有( )。选项:A、删除表中的第一个元素B、删除表中最后一个元素C、在第一个元素前插入一个新元素D、在最后一个元素后插入一个新元素E、在第一个元素后插入一个新元素F、在最后一个元素前插入一个新元素正确答案:【删除表中的第一个元素#在第一个元素前插入一个新元素#在最后一个元素后插入一个新元素#在第一个元素后插入一个新元素#在最后一个元素前插入一个新元素】 15、问题:在双向链表中,删除指针 p 所指的结点时,则修改指针的正确语句序列为( )。选项:A、p-prior-next
35、=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、
36、问题:一个栈的入栈序列为 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、t
37、op=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#orw
38、hile#te”后,栈中从栈底到栈顶的内容为( )。选项:A、forwhiteB、whiteC、froE、orwhileG、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
39、+e*-D、ab+cd+*e-正确答案:【ab+cd+*e-】3.3 栈与递归的实现(二)递归的实现1、问题:递归函数如下:void f ( int n ) printf( %d, n%10 ); if ( n/10 != 0) f( n/10 );执行语句 f( 857 ) 的输出结果是( )。选项:A、857B、758C、75D、7正确答案:【758】2、问题:递归函数如下:void print( int w ) int i; if ( w != 0 ) print( w-1 ); for (i=1; i=w; i+ ) printf( %3d, i ); printf( n ); 执行语
40、句 print( 3 ) 的输出结果是( )。选项:A、 1 1 2 1 2 3B、 1 2 3 1 2 1C、 1 2 2 3 3 3D、 3 3 3 2 2 1正确答案:【 1 1 2 1 2 3】3.4 队列的定义与实现(一)定义和链队列1、问题:若用单链表来表示队列,则应该选用( )。选项:A、带尾指针的非循环队列B、带尾指针的循环链表C、带头指针的非循环链表D、带头指针的循环链表正确答案:【带尾指针的循环链表】2、问题:栈和队列的共同点是( )。选项:A、都是先进后出B、都是后进先出 C、只允许在端点处插入和删除元素D、没有共同点正确答案:【只允许在端点处插入和删除元素】3、问题:在
41、解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据打印,该缓冲区应是一个( )结构。选项:A、数组B、线性表C、堆栈D、队列正确答案:【队列】3.4 队列的定义与实现(二)循环队列和双端队列1、问题:循环队列存储在数组 A0.7中,假设当前队尾指针 Rear 和队头 Front 的值分别为 0 和 5,当队列中加入 2 个元素、删除 3 个元素后,Rear 和 Front 的值分别为多少( )。选项:A、7 和 3B、0 和 2C、2 和 0D、3 和 7正确答案:【2 和 0】2、问题:某队列允许在两端
42、进行入队操作,但仅允许在一端进行出队操作,则入队序列 abcde 不可能得到的出队序列是( )。选项:A、bacdeB、dbaceC、dbcaeD、ecbad正确答案:【dbcae】第三周 栈和队列 单元测验1、问题:一个栈的入栈序列为 1,2,3,n,其出栈序列是。若,则 可能取值的个数是( )。选项:A、n-3 B、n-2C、n-1D、nE、F、n(n-1)G、正确答案:【n-1】2、问题:循环队列 Q 采用数组空间 Q.base0,n-1 存放其元素值,已知其头尾指针分别是 front 和 rear,则当前队列中的元素个数是( )。选项:A、rear-frontB、rear-front+
43、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.b