1、第一章 单选1. 数据结构不包含的内容是( ) A. 数据的元素来源 B. 数据的逻辑结构 C. 数据的存储结构 D. 对数据施加的操作 答案: A 解析: 本题考查了数据结构的内容、作用和意义。数据结构包括逻辑结构和存储结构,并且也包含某些算法,如散列存储就需要利用某种特定的算法来实现,不过数据结构不包含元素来源。2. 在数据结构中,它的基本单位是( ) A. 数据 B. 数据项 C. 数据元素 D. 数据对象 答案: C 解析: 本题考查了数据结构中数据的基本单位。数据结构的基本单位是数据元素。3. 下列关于线性结构的说法中错误的是( ) A. 结构中只含有一个开始结点 B. 结构中只含有
2、一个终端结点 C. 结构中的结点之间存在一对一的对应关系 D. 结构中的所有结点都有一个直接前趋和直接后继 答案: D 解析: 本题考查了数据结构中的线性结构。在线性结构中,开始结点只有直接后继,终端结点只有直接前趋,其他说法均正确。4. 下列关于非线性结构的说法中正确的是( ) A. 结构中只含有一个开始结点 B. 结构中只含有一个终端结点 C. 结构中的结点之间必定存在一对一的对应关系 D. 结构中的结点可能存在多对多的对应关系 答案: D 解析: 本题考查了数据结构中的非线性结构。在非线性结构中的结点之间存在一对多或多对多的对应关系,所以可能有多个开始结点或终端结点。5. 在存储结构的四
3、种基本存储方法中,需要引用“指针”的是( ) A. 顺序存储方法 B. 链接存储方法 C. 索引存储方法 D. 散列存储方法 答案: B 解析: 本题考查了存储结构中的链接存储方法。在链接存储方法中,元素间的逻辑关系是由附加的指针域表示的,需要引用“指针”。6. 下列不属于五个算法准则的是( ) A. 输入 B. 有穷性 C. 随机性 D. 可行性 答案: C 解析: 本题考查了算法的五个准则。算法的五个准则包括:输入、输出、有穷性、确定性和可行性。7. 若要实现更快速地解决问题,就需要高效率的算法,我们把执行算法耗费的时间称为( ) A. 时间复杂度 B. 空间复杂度 C. 可读性 D. 可
4、操作性 答案: A 解析: 本题考查了算法分析中的时间复杂性概念。时间复杂性,是指执行算法所耗费的时间。8. 算法中有一指令“for(i=0;i<=9;i+)”,则该指令的执行次数和频度分别为( ) A. 9,9 B. 9,10 C. 10,10 D. 10,11 答案: D 解析: 本题考查了算法的频度和时间复杂度。在该指令中,i的值由0增至9,共循环执行10次,但由于指令自身的特点,i的最终值为10,共计算了11次,所以该指令的执行次数为10,自身执行次数(频度)为11。9. A. A B. B C. C D. D 答案: A 解析: 本题考查了算法的时间复杂度。对于任何一个总执行次
5、数为常数的算法,我们都表示成1,即。10. 下列数据结构中,属于非线性结构的是( ) A. 栈 B. 队列 C. 单链表 D. 二叉树 答案: D 解析: 本题考查了非线性结构的概念。选项中只有二叉树是非线性结构,其余均为线性结构。11. 下列关于算法的说法错误的是( ) A. 每一步算法的含义要明确 B. 算法的执行次数是有限的 C. 算法只能解决数值计算问题 D. 同一种问题可以有多种解决算法 答案: C 解析: 本题考查了算法的概念。通过设计不同的算法可以实现不同的功能,不仅仅局限于数值计算问题,其余说法均正确。12. “算法+数据结构=程序”中的数据结构指的是( ) A. 逻辑结构和存
6、储结构 B. 线性结构和非线性结构 C. 顺序存储和非线性结构 D. 线性结构和链式结构 答案: A 解析: 本题考查了数据结构的内容。数据结构包含逻辑结构和存储结构。13. 若结点的存储地址与其关键字之间存在某种映射关系,则称这种存储结构为() A. 顺序存储结构 B. 链式存储结构 C. 索引存储结构 D. 散列存储结构 答案: D 解析: 本题考查了数据结构的存储结构中的散列存储方法。散列存储方法根据元素的关键字直接计算出该元素的存储地址。14. 算法分析的两个主要方面是() A. 正确性和简明性 B. 时间复杂性和空间复杂性 C. 可读性和可维护性 D. 数据复杂性和程序复杂性 答案:
7、 B 解析: 本题考查了算法分析的两个主要概念。算法分析中要考虑时间复杂性和空间复杂性。15. 算法指的是() A. 计算机程序 B. 解决问题的计算方法 C. 解决问题的有限运算序列 D. 排序算法 答案: C 解析: 本题考查了算法的描述。算法指的是解决问题的有限运算序列。第一章 填空+简答1. 数据结构中的数据项,是具有独立含义的_ 标识单位。 答案: 最小 解析: 本题考查了数据项的概念。数据项是具有独立含义的最小标识单位。2. 在线性结构中,没有直接后继的是 _结点。 答案: 终端 解析: 本题考查了线性结构中的终端结点的概念。线性结构中的开始结点没有直接前趋,只有直接后继。终端结点
8、有直接前趋,没有直接后继。3. 算法五原则分别是输入、输出、_、确定性和可行性。 答案: 有穷性 解析: 本题考查了算法的五个准则。算法五原则分别是输入、输出、有穷性、确定性和可行性。4. 数据结构一般包括逻辑结构、存储结构和_三个方面的内容。 答案: 数据运算 解析: 本题考查了数据结构的内容。数据结构一般包括逻辑结构、存储结构和数据运算。5. 数据的逻辑结构可分为非线性结构和_两大类。 答案: 线性结构 解析: 本题考查了数据的逻辑结构的概念。逻辑结构可分为线性结构和非线性结构。6. 数据的存储结构(物理结构)一般可以用_、链接存储方法、索引存储方法和散列存储方法等四种存储方法表示。 答案
9、: 顺序存储方法 解析: 本题考查了存储结构的四种基本的存储方法。包括顺序存储方法、链接存储方法、索引存储方法和散列存储方法。7. 设有一批数据元素,为了方便地插入一个元素,宜用_结构存储。 答案: 链接 解析: 本题考查了存储结构中链接存储方法的概念。链接存储方法可以方便地插入一个元素。8. 答案: 9. 答案: 10. 答案: 11. 答案: 第二章 单选11. A. A B. B C. C D. D 答案: A 解析: 2. A. 3 B. 5 C. 8 D. 10 答案: D 解析: 3. 已知某线性表中含有6个元素,现要在第2位和第3位元素之间插入一个新的元素,那么需要移动的元素总数
10、为( ) A. 2 B. 4 C. 6 D. 0 答案: B 解析: 本题考查了线性表的插入运算。欲在第2位和第3位元素之间插入新元素,那么这个元素应插在第3位上,则从第3位开始,包括之后的所有元素都需向后移动一位,总数为:4. 已知某线性表中含有6个元素,现要删除第3位元素,那么需要移动的元素总数为( ) A. 0 B. 1 C. 2 D. 3 答案: D 解析: 本题考查了线性表的删除运算。欲删除第3位元素,则该位置之后的所有元素都需向前移动一位,总数为:5. 在线性表的单链表存储结构中, 结点 中data和next分别表示( ) A. 存储的元素,直接前趋的地址 B. 存储的元素,直接后
11、继的地址 C. 指针的数量,直接前趋的地址 D. 指针的数量,直接后继的地址 答案: B 解析: 本题考查了链表中结点的存储结构。结点包含两个域,数据域(data)中存放的是存储的元素,指针域(next)中存放的是元素的直接后继的地址,利用指针指向该直接后继的结点,实现链式存储。6. 在单链表中实现插入时,为使插入后的元素顺序与输入的元素顺序一致,可采用( ) A. 头插法建表_ B. 尾插法建表 C. 中间法建表_ D. 指针法建表 答案: B 解析: 本题考查了单链表中尾插法建表。利用头插法建表,每次都将新元素插在表头,最终的元素顺序将与输入的元素顺序相反;利用尾插法建表,每次都将新元素插
12、在表尾,最终的元素顺序和输入的元素顺序相同。7. 下列选项中,属于顺序存储结构优点的是( ) A. 插入运算方便 B. 删除运算方便 C. 存储密度大 D. 方便存储各种逻辑结构 答案: C 解析: 本题考查了顺序存储结构的特点。在顺序存储结构中,不方便做元素的插入和删除运算,因为每次都需要移动很多元素,并且只能存储线性结构的元素,不适于存储非线性结构的元素。8. 在链式存储结构中,方便做元素的插入和删除运算,原因是( ) A. 存储的元素数量很少 B. 可进行随机存取 C. 元素的存储地址都是连续的 D. 采用了“指针”表示法 答案: D 解析: 本题考查了链式存储结构的特点。在链式存储结构
13、中,利用“指针”指向下一个存储的结点,在进行元素的插入和删除时,只需改变指针的指向即可,不需要移动大量元素。9. 下列关于线性表的说法正确的是( ) A. 线性表可以含有无限个元素 B. 线性表中的元素只能是具体的数字 C. 线性表是一种线性结构 D. 长度为n的线性表最多可含有n-1个元素 答案: C 解析: 本题考查了线性表的概念。长度为n的线性表可含有n个元素,存放元素数量有限,并且也可存放字符和图片等。10. 若某线性表中第三个数据元素的存储地址为5,每个元素占3个存储单元,那么第10个元素的存储地址是( ) A. 10 B. 20 C. 30 D. 26 答案: D 解析: 第二章
14、单选+填空+算法阅读+算法设计1. 下列关于线性结构的说法错误的是( ) A. 结构中只有一个开始结点 B. 结构中只有一个终端结点 C. 终端结点的直接后继指向开始结点 D. 结构中的数据元素呈线性关系 答案: C 解析: 本题考查了线性表的逻辑特征。线性结构中,数据元素是一一对应的线性关系,结构中只含有一个开始结点和一个终端结点,并且开始结点无直接前趋,终端结点无直接后继。2. 下列数据结构中,不属于线性结构的是( ) A. 栈 B. 队列 C. 树 D. 单链表 答案: C 解析: 本题考查了线性表的逻辑结构特征。除了树是非线性结构,其他均为线性结构。3. 一个线性表含有10个数据元素,
15、每个元素占2个存储单元,若第一个元素的存储地址为100,则第10个数据元素的存储地址为( ) A. 100 B. 110 C. 118 D. 190 答案: C 解析: 4. 下列关于顺序存储结构说法正确的是( ) A. 便于元素的插入 B. 便于元素的删除 C. 含有指针 D. 可实现随机存取 答案: D 解析: 本题考查了顺序存储结构的特点。顺序存储结构不便于元素的插入和删除,链式存储结构含有指针。5. 线性表序列为1 3 11 18 20 31,若将元素22插入该表中,则需移动的元素数量为( ) A. 1 B. 2 C. 3 D. 4 答案: A 解析: 本题考查了线性表的插入运算。22
16、应插在20和31之间,所以应后移1位元素“31”。6. 对于一个需要经常进行元素在单循环链表中,令头指针head指向头结点,则下列表示该链表为空的是( ) A. head = = NULL B. head != NULL C. headnext = = head D. headnext = = NULL 答案: C 解析: 本题考查了单循环链表的概念。空单循环链表中无任何结点,头指针只能指向自己。7. 下列关于链式存储结构的说法正确的是( ) A. 可实现随机存取 B. 引用“指针”来呈现数据关系 C. 不利于元素的插入 D. 不利于元素的删除 答案: B 解析: 本题考查了链式存储结构的特点
17、。链式存储结构利于元素的插入和删除,不可实现随机存取,并引用了指针概念。8. 线性表序列为0 11 22 33 44 55,若将元素33删除,则需移动的元素数量为( ) A. 1 B. 2 C. 3 D. 4 答案: B 解析: 本题考查了线性表的插入运算。23应插在22和33之间,所以应前移2位元素。9. 若线性表中每个元素占5个存储单元,第1个元素的存储地址为5,则第5个元素的存储地址为( ) A. 10 B. 15 C. 20 D. 25 答案: D 解析: 10. 顺序表中,逻辑上相邻的元素,其存储地址( ) A. 一定相邻 B. 一定不相邻 C. 不一定相邻 D. 可能不相邻 答案:
18、 A 解析: 本题考查了顺序表中顺序存储结构的特点。顺序表的特点是将逻辑上相邻的元素存储到地址也相邻的物理地址中,所以存储地址一定相邻。11. 在单链表中,结点D所指的结点不是终端结点,那么将结点H插入到结点D后的语句是_。 答案: Hnext=Dnext;Dnext=H 解析: 本题考查了单链表的插入运算。“Hnext=Dnext”实现结点H指向结点D的下一个结点,“Dnext=H”实现结点D指向结点H。12. 在线性结构中,没有直接前趋的是_结点。 答案: 开始 解析: 本题考查了线性表的逻辑特征。线性结构中的开始结点没有直接前趋,只有直接后继。13. 顺序表中第一个元素的存储地址为100
19、,其中每个元素占5个存储单元,那么第7个元素的存储地址为_。 答案: 130 解析: 本题考查了线性表中元素的存储地址关系。100+(7-1)*5=130。14. 在一个长度为n的顺序表中删除第i个元素,需要向前移动_个元素。 答案: n-i 解析: 本题考查了顺序表的删除运算。需要删除第i个元素,所以要向前移动n-i个元素。15. 在用p指针访问单链表时,判断不是访问结束的条件是_。 答案: p!=NULL; 解析: 本题考查了单链表的概念。当访问到最后的终端结点无后继结点,所以终端结点的指针域为空,用NULL表示。16. 在访问单循环链表时,判断不是访问表结束的条件是_。 答案: p!=h
20、ead; 解析: 本题考查了单循环链表的概念。单循环链表的终端结点的指针域不为空,而是指向链表的头结点,从而构成了一个循环链表。17. 对于一个需要经常进行元素增减的线性表,宜采用 _存储结构。 答案: 链式 解析: 本题考查了链式存储结构的特点。在线性表的顺序存储结构和链式存储结构中,链式存储结构方便元素的插入和删除。18. 下列函数的功能是:在带头结点的单链表上进行选择排序。请在空白处填上适当内容将函数补充完整,并说明该算法是否是稳定的。 答案: (1)q->next(2)p->next=q->next(3)r->next=q该算法是稳定的。 解析: 本题考查单链表
21、的删除与插入(调换)。算法语句含义:从第一个和第二个结点开始比较,若第一个结点大于第二个结点,则继续比较第二个和第三个结点;若第一个结点小于第二个结点,则交换两结点的位置;直到查找完毕整条链表。该算法的目的是,将链表中的结点按关键字大小的升序进行排列,通过对算法的分析发现,此类算法并不会破坏关键字的相对次序,所以是稳定的。19. 下列函数的功能是在带头结点的单链表head中删除所有数据域值为x的结点,请在空白处填上适当的语句,使其完成指定的功能。 答案: (1)p->next=q(2)q=q->next(或q=p->next) 解析: 本题考查的是单链表的删除操作指令。20.
22、 设非空双向循环链表L的头指针为head,表结点类型为DLNode。但L中所有结点的prior域均为空(NULL),函数f30的功能就是为每个结点的prior域赋值,请将下列算法补充完整。 答案: (1)head(2)p->next->prior(3)head->prior 解析: 本题考查了双向循环链表的构成和指针域的赋值。(1)该语句用来判断链表是否是空链;(2)该语句完成prior域的赋值,使p指向的结点指向p本身,构成双向循环链表;(3)该语句令头结点head指向最后一个结点。21. 设带头结点的单链表初始为空。将从键盘读入的每个字符作为一个结点加入该链表表尾,当读入
23、回车符时结束并返回链表表头指针。请在空白处填写适当内容,完成其功能。 答案: (1)p=(ListNode *)malloc(sizeof(ListNode)(2)rear->next=p(3)head 解析: 本题考查单链表的“尾插法建表”。22. 阅读下列程序,回答问题。style=max-width:100%;(1)若链表L=12,0,15,77,26,42,则f30(L)的输出结果是?(2)函数f30的功能是什么? 答案: (1)77(2)返回(找出)链表中结点的最大值。23. 阅读下列算法,并回答问题。style=max-width:100%;(1)若SL1->data中
24、的数据为25,4,256,9,-38,47,128,256,64,SL2->data中的数据为22,4,-63,15,29,34,42,3,则算法f33(&SL1,&SL2)后SL1->data和SL2->data中的数据各是什么?(2)该算法的功能是什么? 答案: 本题考查了线性表的插入和删除运算。(1) SL1->data中的数据是25,4,256,15,29,47,128,256,64SL2->data中的数据是22,4,-63,9,-38,34,42,3(2)该算法比较两个线性表中相同下标位置的两个元素,较大者移动到较长的线性表中,较小者移
25、动到较短的线性表中。 解析: 该题程序较长,但算法简单,需耐心分析。该算法的含义是,先比较两个线性表的长度,将长度较长的线性表作为SL1代入f33函数中,将长度较小的线性表作为SL2代入f33函数中。比较两个线性表中相同下标位置的两个元素,较大者移动到较长的线性表中,较小者移动到较短的线性表中。24. 设有两个顺序表A和B,且都递增有序。试写一算法,从A中删除与B中相同的那些元素(也就是计算A-B)。 答案: 解析: 本题考查了顺序表的删除运算。算法思想是:扫描整个B表,顺序取表中每个元素,然后与表A中从某下标开始的元素进行比较(因为两表都是有序的,不必每次从头开始,用一个变量k标识上一次比较
26、结束的位置),当B中的某元素值大于或等于A的某个元素时,比较结束。记住A表的当前下标值k,之后再比较两元素值是否相等,若相等,则从表A中删除该元素,而后继续B中的下一个元素与A中从第k个元素开始向后比较;否则,继续,直到B中所有元素比较完为止。25. 设有一个带头结点的双向循环链表,head为链表的头指针。试写一算法,实现在值为x的结点之前插入一个值为y的结点。 答案: 解析: 本题考查了双向循环链表的查找运算。因为链表是双向循环链表,所以不需要用指针指向x之前的结点,但要先从开始结点用循环找到要插入的位置,也就是x结点的位置。第三章 单选1. 若入栈的一列元素序列为1,2,3,4,则可能的出
27、栈顺序是( ) A. 1,4,2,3 B. 3,4,1,2 C. 2,4,3,1 D. 4,1,3,2 答案: C 解析: 本题考查了栈的“后进先出”原则。栈中的元素遵循“后进先出”的原则,先使1进栈,然后2进栈,再立刻让2出栈,之后3和4入栈,再依次使4、3、1出栈。在其他选项中,出栈顺序不符合“后进先出”原则。2. 已知栈顶元素为1,则下列表示元素1出栈的运算是( ) A. InitStack(&S) B. GetTop(S) C. Push(&S,1) D. Pop(&S) 答案: D 解析: 本题考查了栈的基本运算中的出栈运算。在栈的运算中,Pop(&S)表示删除栈顶元素,即出
28、栈。3. 下列可用于判断顺序栈是否为空栈的运算为( ) A. S-top=-1 B. return S-top=-1 C. return S-top=StackSize-1 D. S-top=S-top+1 答案: B 解析: 本题考查了顺序栈基本运算中的置空栈。“return S-top=-1”用来判断栈空,而“S-top=-1”是用来令栈为空栈的。4. 在栈的链式存储结构中,不需要设置头结点的原因是( ) A. 该存储结构中的结点没有直接前趋 B. 该存储结构中的结点没有直接后继 C. 栈是非线性结构 D. 只在栈顶的一端进行元素的插入和删除 答案: D 解析: 本题考查了栈的链式存储结构
29、的概念。由于栈的“后进先出”原则,元素的插入和删除都只在栈顶进行,所以不需要设置头结点。5. 下列可用于判断链栈是否为空栈的运算为( ) A. return top=NULL B. top=p C. p-next=top D. top=p-next 答案: A 解析: 本题考查了链栈基本运算中的判栈空。在链栈中,用于判断空栈的运算是“return top=NULL”。6. 下列关于栈和队列的相同之处,说法正确的是( ) A. 都只在一端进行元素的插入和删除 B. 都遵循“先进先出”原则 C. 链式存储结构中都不需要设置头结点 D. 链式存储结构中都需要设置头结点 答案: A 解析: 本题考查了
30、栈和队列的概念。对于栈,只在栈顶进行元素的插入和删除,而在队列中,在队尾实现元素的插入,在队头实现元素的删除,遵循“先进先出”原则,最先插入的元素也会最先被删除;由于元素的插入和删除的实现方式不同,所以链栈不需要设置头结点,而链式队列需要。7. 在队列的基本运算中,表示将元素1插入队列中的是( ) A. InitQueue(Q) B. EnQueue(Q,1) C. DeQueue(Q) D. GetFront(Q) 答案: B 解析: 本题考查了队列的基本算法中的入队列。在队列的基本运算中,“EnQueue(Q,1)”表示将元素1插入到队列中。8. 若用一个大小为5的数组保存循环队列Q,若经
31、过一次元素的插入和两次元素的删除后,rear和front的值分别是1、4,那么在此之前rear和front的值分别是( ) A. 0,1 B. 1,2 C. 0,2 D. 1,3 答案: C 解析: 本题考查了顺序循环队列的rear值和front值的判断。在循环队列中,每经过一次元素的插入则rear的值加一,每经过一次元素的删除则front的值加一,所以应选择C。9. 循环队列的rear和front的值分别是1,5,若出队一个元素,入队两个元素,则rear和front的值分别是( ) A. 2,5 B. 3,6 C. 2,7 D. 3,7 答案: B 解析: 本题考查了顺序循环队列的rear值
32、和front值的判断。在循序队列中,入队时rear的值加1,出队时front的值加1,所以选择B。10. 在链栈中,判栈空的指令是( ) A. return top = = NULL B. return top C. top = = NULL D. return S-dataS-top 答案: A 解析: 本题考查了链栈的基本运算中的判栈空。链栈的判栈空为“return top = = NULL”。11. 清空顺序栈中所有数据元素的指令是( ) A. S-top=-1 B. return S-top = = -1 C. return S-top = = StackSize-1 D. retur
33、n top = = NULL 答案: A 解析: 本题考查了顺序栈基本运算中的置空栈。置空栈即可达到想要的结果,而置空栈的指令为S-top=-1,而return S-top = = -1是用来判断空栈的。12. 若栈S的序列为0 1 2 3,则执行一次Pop(&S)后,栈顶元素为( ) A. 0 B. 1 C. 2 D. 3 答案: C 解析: 本题考查了栈的出栈运算。Pop(&S)是出栈指令,将会删去栈顶元素,所以执行后的栈顶元素为2。13. 用于判断顺序栈是否为空栈的是( ) A. S-top=-1 B. return S-top = = -1 C. return S-to
34、p = = StackSize-1 D. return top = = NULL 答案: B 解析: 本题考查了顺序栈基本运算中的判栈空。判栈空:return S-top = = -1。14. 在链栈中,“p-data=x;p-next=top;top=p;”的含义为( ) A. 数据域为p的结点x的进栈 B. 数据域为x的结点p的进栈 C. 数据域为p的结点p的出栈 D. 数据域为p的结点x的出栈 答案: B 解析: 本题考查了链栈的进栈运算。“p-data=x”的含义为将x赋给结点P的数据域,“p-next=top;top=p”的含义为插入结点p。15. 循环队列的rear和front的值
35、分别是0,2,若出队两个元素,入队一个元素,则rear和front的值分别是( ) A. 0,1 B. 0,2 C. 1,3 D. 1,4 答案: D 解析: 本题考查了循环队列中rear值和front值的概念。在循序队列中,入队时rear的值加1,出队时front的值加1,所以选择D。16. 用于判断顺序栈是否饱和的是( ) A. S-top=-1 B. return S-top = = -1 C. return S-top = = StackSize-1 D. return top = = NULL 答案: C 解析: 本题考查了顺序栈的判栈满运算。判栈满:return S-top = =
36、 StackSize-1。17. 在链栈中,“top=p-next;free(p)”的含义为( ) A. 结点p的进栈 B. 结点p的出栈 C. 利用结点p判栈空 D. 利用结点p判栈满 答案: B 解析: 本题考查了链栈的基本运算。见“押题精华”链栈基本运算的实现。18. 若栈S的序列为0 1 2 3,x=0,则执行一次Push(&S,x)后,栈顶元素为( ) A. 0 B. 1 C. 2 D. 3 答案: A 解析: 本题考查了栈的入栈运算。Push(&S,x)是入栈指令,最终栈顶元素为x=0。19. 顺序栈中,“S-top=S-top+1;S-dataS-top=x”的含
37、义是( ) A. 判栈空 B. 判栈满 C. 元素x进栈 D. 元素x出栈 答案: C 解析: 本题考查了顺序栈的进栈运算。顺序栈栈顶指针top的值加1,然后将元素x放入栈顶,实现元素x的进栈。第三章 填空+解答1. 现有可容纳100个元素的数组A0.99,该数组供给两个栈使用,为了充分利用存储空间,若第一个栈的栈底元素保存在A99中,那么第二个栈的栈底元素应保存在_中。 答案: A0 解析: 本题考查了栈的顺序存储结构。为实现存储空间的充分利用,应使两个栈从头和尾(相向而行)分别开始进行元素的存储,这样一可避免为某个栈分配的存储空间不足,二可实现存储空间的充分利用。2. 假设以S和X分别表示
38、进栈和退栈操作,则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后,得到的输出序列为_。 答案: b,c,e,d,a 解析: 本题考查了栈的基本算法的进栈和退栈操作。3. 设顺序栈存放在S.datamaxsize中,栈底位置是maxsize-1,则栈空条件是_;栈满条件是_。 答案: s.top=maxsize; s.top=0 解析: 本题考查了顺序栈的基本运算的判栈空和判栈满。4. 从循环队列中删除一个元素时,其操作是先_,后_。 答案: 取出队头元素 移动队头指针 解析: 本题考查了循环队列的基本运算中的出队列运算。5. 若循环队列用数组datam存储元素值,用fro
39、nt和rear分别作为头尾指针,则当前元素的个数为_。 答案: (rear-front+m)%m 解析: 本题考查了对循环队列中rear值和front值的运用。6. 一个直接调用自己或间接调用自己的函数,称为_。 答案: 递归函数 解析: 本题考查了递归的概念。7. 假设输入栈的元素为a、b、c,在栈S的输出端得到一个输出序列为a、b、c,试写出在输入端所有可能的输入序列。 答案: 可能的输入序列为:a,b,c;a,c,b;b,a,c;c,a,b;c,b,a。 解析: 本题考查了栈的基本特性。8. 设将整数1,2,3,4依次进栈,进栈的同时可以出栈,请回答下述问题:(1)若入、出栈次序为Pus
40、h(1),Pop( ),Push(2),Push(3),Pop( ),Pop( ),Push(4),Pop( ),则出栈的数字序列是什么?(这里Push(i)表示i进栈,Pop()表示出栈)(2)能否得到出栈序列1423和1432?并说明为什么?(3)请分析1,2,3,4的24种排列中,哪些序列是可以通过相应的入、出栈操作得到的? 答案: (1)出栈序列为:1324。(2)不能得到1423序列。因为要得到14的出栈序列,则应做Push(1),Pop( ),Push(2),Push(3),Push(4),Pop( )。这样3在栈顶,2在栈底,所以不能得到23的出栈序列。 能得到1432的出栈序列
41、。具体操作为:Push(1),Pop( ),Push(2),Push(3),Push(4),Pop( ),Pop( ),Pop( )。(3)在1,2,3,4的24种排列中,可通过相应入、出栈操作得到的序列是:1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321,不能得到的序列是:1423,2413,3124,3142,3412,4123,4132,4213,4231,4312. 解析: 本题考查了栈的基本入、出栈操作。 第三章 算法阅读+算法设计1. 已知栈的基本操作定义如下,请在空白处填写适当内容,完成相应的功能。 答案: (1)s->top= -1(2)s->datas->top+(或s->data+s->top)(3)s->datas->top- 解析: 已知栈的基本操作定义本题考查栈的基本运算指令。2. 阅读下列程序,写出f31的输出结果。 答案: c a t c h ! 解析: 本题考查了栈的基本运算算法。根据算法中的操作指令,栈中的元素会发生改变,最终借助“while”循环并利用参数“y”将栈中的元素一一输出。3. 假设循环队列中只设rear和q