66道选择题 求答案【数据结构吧】_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：60,419贴子：
66道选择题 求答案收藏
一、1、（ ）是数据的基本单位，（ ）是数据的最小单位。A.数据项
B.数据元素
D.表元素2、在数据结构中，与所使用的计算机无关的是数据的（ ）结构。A.逻辑
C.逻辑和存储
D.物理3、数据的逻辑结构可以分为（ ）两类。A.动态结构和静态结构
B.紧凑结构和非紧凑结构C.线性结构和非线性结构
D. 内部结构和外部结构4、在计算机的存储器中表示时,物理地址和逻辑地址直接对应并且是连续的，称之为（ ）A.逻辑结构
B.顺序存储结构
C.链式存储结构
D.以上都对5、数据采用链式存储结构时，要求（ ）A.每个结点占用一片连续的存储区域
B.所有结点占用一片连续的存储区域
C.结点的最后一个数据域是指针类D.每个结点有多少个后继，就设多少个指针域6、研究数据结构就是研究（ ）。A.数据的逻辑结构
B.数据的存储结构
C.数据的逻辑结构和存储结构
D.数据的逻辑结构、存储结构及其基本操作7、算法分析的两个主要方面是（
A. 空间复杂度和时间复杂度
B. 正确性和简单性
C. 可读性和文档性
D. 数据复杂性和程序复杂性8、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（）等5个特性。A. 可执行性、可移植性和可扩充性
B. 可行性、有穷性和确定性
C. 确定性、有穷性和稳定性
D. 易读性、稳定性和确定性9、具有线性结构的数据结构是（
D.栈10、非空的循环单链表head的尾结点p满足（
）。A. p-&next==head
B. p-&next==NULL
D. p==head11、链表不具有的特点是（
）。A. 可随机访问任一元素　
B. 插入删除不需要移动元素
C. 不必事先估计存储空间
D. 所需空间与线性表长度成正比12、在双向循环链表中，在p指针所指的结点后插入一个指针q所指向的新结点，修改指针的操作是（
A. p-&next=q;q-&prior=p;p-&next-&prior=q;q-&next=q;
B. p-&next=q;p-&next-&prior=q;q-&prior=p;q-&next=p-&
C. q-&prior=p;q-&next=p-&p-&next-&prior=q;p-&next=q;
D. q-&next=p-&q-&prior=p;p-&next=q;p-&next=q;13、线性表采用链式存储时，结点的存储地址（
）。A. 必须是连续的
B. 必须是不连续的
C. 连续与否均可
D. 和头结点的存储地址相连续14、在一个长度为n的顺序表中删除第i个元素，需要向前移动（
）个元素。A. n-i
D. i+115、线性表是n个（
）的有限序列。A. 表元素
C. 数据元素
D. 数据项16、从表中任一结点出发，都能扫描整个表的是（
）。A. 单链表
C. 循环链表
D. 静态链表17、在具有n个结点的单链表上查找值为x的元素时，其时间复杂度为（
）。A. O(n)
D. O(n-1)18、线性表L=(a1,a2,……,an)，下列说法正确的是（
）。A. 每个元素都有一个直接前驱和一个直接后继
B.线性表中至少要有一个元素C.表中诸元素的排列顺序必须是由小到大或由大到小
D.除第一个和最后一个元素外，其余每个元素都由一个且仅有一个直接前驱和直接后继19、一个顺序表的第一个元素的存储地址是90，每个元素的长度为2，则第6个元素的存储地址是（
D. 10620、在线性表的下列存储结构中，读取元素花费的时间最少的是（
C. 循环链表
D. 顺序表21、在一个单链表中，若删除p所指向结点的后续结点，则执行（
）。A. p-&next=p-&next-&B. p=p-&p-&next=p-&next-&C. p =p-&D. p=p-&next-&22、将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为（
）。A. O(1)
D. O(m+n)23、线性表的顺序存储结构是一种（
）存储结构。A. 随机存取
B. 顺序存取
C. 索引存取
D. 散列存取24、顺序表中，插入一个元素所需移动的元素平均数是（
A. (n-1)/2
D. (n+1)/225、循环链表的主要优点是（
）。A. 不再需要头指针
B. 已知某结点位置后能容易找到其直接前驱C. 在进行插入、删除运算时能保证链表不断开D. 在表中任一结点出发都能扫描整个链表 26、不带头结点的单链表head为空的判定条件是（
）。A. head==NULL
B. head-&next==NULL
C. head-&next==head
D. head!=NULL27、已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为（
）。A. q-&next=s-&next；s-&next=p；
B. s-&next=p；q-&next=s-&next；
C. p-&next=s-&next；s-&next=q；
D. s-&next=q；p-&next=s-&next；28、在以下的叙述中，正确的是（
A. 线性表的顺序存储结构优于链表存储结构　
B. 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况
C. 线性表的链表存储结构适用于频繁插入/删除数据元素的情况
D. 线性表的链表存储结构优于顺序存储结构29、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入一个结点s，则执行（
）。A. s-&next=p-& p-&next=s;
B. p-&next=s-&s-&next=p;
C. s-&next=p;q-&next=s;
D. p-&next=s;s-&next=q; 30、在单链表中，指针p指向元素为x的结点，实现删除x的后继的语句是（
）。A. p=p-&
B. p-&next=p-&next-&
C. p-&next=p;
D.p=p-&next-&31、在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p-&next-&next==head，则（
）。A. p指向头结点　
B. p指向尾结点
C. p的直接后继是头结点D. p的直接后继是尾结点32、一个栈的输入序列为：a，b，c，d，e，则栈的不可能输出的序列是（
）。A. a,b,c,d,e
B. d,e,c,b,a
C. d,c,e,a,b
D. e,d,c,b,a33、判断一个循环队列Q（最多n个元素）为满的条件是（
）。A. Q-&rear==Q-&front
B. Q-&rear==Q-&front+1
C. Q-&front==(Q-&rear+1)%n
D. Q-&front==(Q-&rear-1)%n34、设计一个判别表达式中括号是否配对的算法，采用（
）数据结构最佳。A. 顺序表
D. 栈35、带头结点的单链表head为空的判定条件是（
）。A. head==NULL　
B. head-&next==NULL
C. head-&next!=NULL
D. head!=NULL36、一个栈的输入序列为：1,2,3,4，则栈的不可能输出的序列是（
）。A. 1243
E. 321437、若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0，3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（
）。A. 1和5
D. 5和138、队列的插入操作是在（
）。A. 队尾
C. 队列任意位置
D. 队头元素后39、循环队列的队头和队尾指针分别为front和rear，则判断循环队列为空的条件是（
）。A. front==rear
B. front==0
C. rear==0
D. front=rear+140、一个顺序栈S，其栈顶指针为top，则将元素e入栈的操作是（
）。A. *S-&top=e;S-&top++;
B. S-&top++;*S-&top=e;
C. *S-&top=e
D. S-&top=e;41、表达式a*(b+c)-d的后缀表达式是（
）。A. abcd+-　
B. abc+*d-
C. abc*+d-
D. -+*abcd42、将递归算法转换成对应的非递归算法时，通常需要使用（
）来保存中间结果。A.队列
D.树43、栈的插入和删除操作在（
D. 指定位置44、五节车厢以编号1，2，3，4，5顺序进入铁路调度站（栈），可以得到（
）的编组。
A. 3，4，5，1，2
B. 2，4，1，3，5
C. 3，5，4，2，1
D. 1，3，5，2，445、判定一个顺序栈S（栈空间大小为n）为空的条件是（
）。A. S-&top==0
B. S-&top!=0
C. S-&top==n
D. S-&top!=n46、在一个链队列中，front和rear分别为头指针和尾指针，则插入一个结点s的操作为（
）。A. front=front-&next
B. s-&next=rear=sC. rear-&next=s;rear=s;
D. s-&next=front=s;47、一个队列的入队序列是1，2，3，4，则队列的出队序列是（
A. 1，2，3，4　
B. 4，3，2，1
C. 1，4，3，2
D. 3，4，1，248、依次在初始为空的队列中插入元素a,b,c,d以后，紧接着做了两次删除操作，此时的队头元素是（
D. d49、正常情况下，删除非空的顺序存储结构的堆栈的栈顶元素，栈顶指针top的变化是（
）。A. top不变
C. top=top+1
D. top=top-150、判断一个循环队列Q（空间大小为M）为空的条件是（
）。A. Q-&front==Q-&rear
B. Q-&rear-Q-&front-1==M
C. Q-&front+1=Q-&rear
D. Q-&rear+1=Q-&front51、设计一个判别表达式中左右括号是否配对出现的算法，采用（
）数据结构最佳。A. 线性表的顺序存储结构
D. 线性表的链式存储结构52、当用大小为N的数组存储顺序循环队列时，该队列的最大长度为（
）。A. N　
D. N-253、队列的删除操作是在（
）。A. 队首　
D. 队后54、若让元素1，2，3依次进栈，则出栈次序不可能是（
）。A. 3，2，1　
B. 2，1，3
C. 3，1，2
D. 1，3，255、循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（
A. (rear-front+m)%m
B. rear-front+1
C. rear-front-1
D. rear-front56、在解决计算机主机和打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个（
）结构。A. 堆栈
D. 线性表57、栈和队列都是（
）。A. 链式存储的线性结构
B. 链式存储的非线性结构
C. 限制存取点的线性结构
D. 限制存取点的非线性结构58、队列和栈的主要区别是（
）。A. 逻辑结构不同
B.存储结构不同C. 所包含的运算个数不同
D. 限定插入和删除的位置不同59、对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（
）。A.正确性
D.输入性60、设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（
）。for(i=n-1；i&=0；i--)
for(j=0；j&i；j++)
B. O(nlgn)
O(n2) 61．顺序存储结构的优势是（
（A）、利于插入操作（B）、利于删除操作 （C）、利于顺序访问（D）、利于随机访问62、设有两个串S1和S2，求串S2在S1中首次出现位置的运算称作（）。A.连接
C.模式匹配
D.判断子串63、串与普通的线性表相比较，它的特殊性体现在（）。A. 顺序的存储结构
B. 链式存储结构
C. 数据元素是一个字符
D. 数据元素任意64、空串和空格串（）。
C. 可能相同
D. 无法确定65、与线性表相比，串的插入和删除操作的特点是（
A. 通常以串整体作为操作对象
B. 需要更多的辅助空间
C. 算法的时间复杂度较高
D. 涉及移动的元素更多66、设SubStr(S,i,k)是求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=’Beijing&Nanjing’，SUBSTR(S,4,5)=（）。A. ‘ijing’
B. ‘jing&’
C.‘ingNa’
D. ‘ing&N’
傲融crm数据库以客户管理为核心,涵盖商机\合同\订单\产品\客服\办公等功能模块.可集成企业ERP,呼叫中心,移动定位,丰富API集成功能!免费试用,来电立享优惠!
求大神们速度点
正在考试中
有没有在做的啊
11点50要交卷的
麻烦大神们快一点
真的很急啊
登录百度帐号推荐应用> 问题详情
设栈S和队列O的初始状态为空，元素a、b、c、d、e和f依次通过栈S，一个元素出栈后即进入队列Q，若6个元素
悬赏：0&答案豆
提问人：匿名网友
发布时间：
设栈S和队列O的初始状态为空，元素a、b、c、d、e和f依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是b、d、c、f、e、a，则栈S的容量至少应该是（）。A．6B．4C．3D．2请帮忙给出正确答案和分析，谢谢！
为您推荐的考试题库
您可能感兴趣的试题
1内部格式控制操作函数是在头文件（　　）中定义的。2下面的符号中可以用作C
标识符的是（　　）。
我有更好的答案
请先输入下方的验证码查看最佳答案
图形验证：
验证码提交中……
找答案会员
享三项特权
找答案会员
享三项特权
找答案会员
享三项特权
选择支付方式：
支付宝付款
郑重提醒：支付后，系统自动为您完成注册
请使用微信扫码支付(元)
支付后，系统自动为您完成注册
遇到问题请联系在线客服QQ：
请您不要关闭此页面,支付完成后点击支付完成按钮
遇到问题请联系在线客服QQ：
恭喜您！升级VIP会员成功
常用邮箱：
用于找回密码
确认密码：本文所属图书&>&
作者长期从事程序设计语言和数据结构课程的基础教学工作，本书是在总结这些教学经验的基础上编写而成，全书分为12章，包括绪论、线性表、栈和队列、串、数组和稀疏矩阵、递归、树形结构、广义表、查找、内排序、...&&
1. 单项选择题
【例3-1-1】元素A、B、C、D依次进栈后，栈顶元素是& ①& ，栈底元素是& ②& 。
A. A&&&&&& &&&&&&&&&&&&&&&&&&&& B. B&&&&&&&&&&&&&&&&&&&&& C. C &&&&&&&&&&&&&&&&&&&& D. D
答：元素A、B、C、D依次进栈的过程如图3.2所示，此时从栈顶到栈底依次为D、C、B、A，栈顶元素是D，栈底元素是A。本题答案为①D ②A。
图3.2 &元素进栈
【例3-1-2】经过以下栈运算后，x的值是&&&&& 。
InitStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s,x);
A. a &&&&&&&&&&&&&&&&&&&& &&&&&& B. b&&&&&&&&&&&&&&&&&&&&&&&&&&&& C. 1 &&&&&&&&&&&&&&&&&&&&&&&&&&& D. 0
答：a、b先进栈到栈s中，退栈一次，再取栈顶元素放到x中，x应为b。本题答案为B。
【例3-1-3】经过以下栈运算后，StackEmpty(s)的值是&&&&& 。
InitStack(s);Push(s,a);Push(s,b);Pop(s,x);Pop(s,y)
A. a&&&&&&& &&&&&&&&&&&&& &&&&&& B. b&&&&&&&&&&&&&&&&&&&&&&&&&&&& C. 1 &&&&&&&&&&&&&&&&&&&&&&&&&&& D. 0
答：a、b先进栈到栈s中，退栈两次，栈为空，则StackEmpty(s)为真。本题答案为C。
【例3-1-4】已知一个栈的进栈序列是ABC，出栈序列为CBA，经过的栈操作是&&&&& 。
A. push,pop,push,pop,push,pop&&&&&&&&&& &&&&&& &&&&&& B. push,push,push,pop,pop,pop
C. push,push,pop,pop,push,pop&&&&&&&&&&&&&&&&&& &&&&&& D. push,pop,push,push,pop,pop
【例3-1-5】若元素a、b、c、d、e、f依次进栈，允许进栈、退栈的操作交替进行，但不允许连续3次退栈工作，则不可能得到的出栈序列是&&&&& 。
A. dcebfa&&&&&&&&&&&&&&&&&&&& B. cbdaef&&&&&&&&&&&&&&&&&&&& C. bcaefd&&&&&&&&&&&&&&&&&&&& D. afedcb
答：选项A操作：a进，b进，c进，d进，d出，c出，e进，e出，b出，f进，f出，a出。
选项B操作：a进，b进，c进，c出，b出，d进，d出，a出，e进，e出，f进，f出。
选项C操作：a进，b进，b出，c进，c出，a出，d进，e进，e出，f进，f出，d出。
选项D操作：a进，a出，b进，c进，d进，e进，f进，f出，e出，d出，c出，b出。
从中看到，选项D中最后连续出栈5次，不符合要求。本题答案为D。
【例3-1-6】设一个栈的输入序列为A、B、C、D，则借助一个栈所得到的输出序列不可能是&&&&& 。
A. A,B,C,D&&&&&&&&&& B. D,C,B,A&&&&&&&&&&&&&&&&& C. A,C,D,B&&&&&&&&&&&&&&&&&& D. D,A,B,C
答：可以简单地推算，容易得出D，A，B，C是不可能的，因为D先出来，说明A，B，C，D均在栈中，在栈中顺序应为D，C，B，A，出栈的顺序只能是D，C，B，A，如图3.3所示。所以本题答案为D。
图3.3& 元素进栈和退栈
【例3-1-7】一个栈的进栈序列是a、b、c、d、e，则栈的不可能的输出序列是& &&&&。
A. edcba&&&&&&&&&&&&&&& B. decba&&&&&&&&&&&&&&&&&&&&&& C. dceab&&&&&&&&&&&&&&& &&&&&& D. abcde
答：栈的特点是先进后出。对于选项A，a、b、c、d、e进栈，e、d、c、b、a出栈；对于选项B，a，b，c，d进栈，d出栈，e进栈，e出栈，c、b、a依次出栈；对于选项C，a、b、c、d进栈，d出栈，c出栈，e进栈，e出栈，此时栈中从栈底到栈顶为a、b，不可能a先出栈，所以C是不可能的输出序列；对于选项D，a进栈，a出栈，b进栈，b出栈，c进栈，c出栈，d进栈，d出栈，e进栈，e出栈。本题答案为C。
【例3-1-8】已知一个栈的进栈序列是1，2，3，&，n，其输出序列的第一个元素是i（1&i&n），则第j（1&j&n）个出栈元素是&&&&& 。
A. i& &&&&&&&&&&&&&&&&&&&& B. n-i&&&&&&&&&&&&&&&&&&&&&&&&& C. j-i+1&&&&&&&&&&&&&&& &&&&&& D. 不确定
答：根据栈的特点，输出序列的第一个元素是i，无法确定第j个出栈的元素。本题答案为D。
【例3-1-9】已知一个栈的进栈序列是1，2，3，&，n，其输出序列是p1，p2，&，pn，若p1=n，则pi的值为&&&&& 。
A. i& &&&&&&&&&&&&&&&&&&&& B. n-i&&&&&&&&&&&&&&&&&&&&&&&&& C. n-i+1&&&&&&&&&&&&&&&&&&&&&& D. 不确定
答：当p1=n时，输出序列是唯一的，即为n、n-1、&、3、2、1，则：p2=n-1，p3=n-2，&，pn=1，推断出pi=n-i+1，所以本题答案为C。
【例3-1-10】设n个元素的进栈序列是p1、p2、p3、&、pn，其输出序列是1、2、3、&、n，若pn=1，则pi（1&i&n-1）的值是&&&&& 。
A. n-i+1&&&&&&&&&&&&&& B. n-i&&&&&&&&&&&&&&&&&&&&&&&&& C. i&&&&&&&&&&&&&&&&&&&&&&&&&&&&& D. 有多种可能
答：当pn=1时，进栈序列是p1、p2、p3、&、pn，由输出序列可知，p1、p2、p3、&、pn依次进栈，然后依次出栈，即pn-1=2，pn-2=3，&，p1=n，也就是说pi=n-i+1，所以本题答案为A。
当出栈序列的第一个元素为进栈序列的最后一个元素时，进栈出栈的操作是唯一的。
【例3-1-11】设n个元素的进栈序列是1、2、3、&、n，其输出序列是p1、p2、&、pn，若p1=3，则p2的值为& &&&&。
A. 一定是2&&&&&&&&& &&&&&& B. 一定是1&&&&&&&&&&&&&&&& C. 不可能是1&&&&&& &&&&&& D. 以上都不对
答：当p1=3时，说明1，2，3先进栈，立即出栈3，此时栈的状态如图3.4所示，这时可出栈2，也可能让4进栈后再出栈，也可以让4进栈、5进栈后再出栈&&从中看到，p2可能是2，也可能是4，&，n，但一定不能是1，所以本题答案为C。
【例3-1-12】设n个元素的进栈序列是p1、p2、p3、&、pn，其输出序列是1、2、3、&、n，若p3=1，则p1的值&&&&& 。
A. 可能是2&&&&&&&&&&&&&&&& B. 一定是2&&&&&&&&&&&&&&&& C. 不可能是2&&&&&&&&&&&&& D. 不可能是3
答：当p3=1时，进栈序列是p1、p2、1、&，由输出序列可知，p1、p2、p3都进栈，出栈p3，如图3.5所示，此后紧跟着出栈的一个元素就是2，而p1不可能紧跟着p3出栈，因为栈中前面有p2，因此p1不可能是2，所以本题答案为C。
&&&& &&&&&&&&&&
&&&&&&&&&& 图3.4 &元素3出栈后的情况&&&&&&& &&&&&&&&&图3.5 &元素p3出栈后的情况
【例3-1-13】设n个元素进栈序列是p1、p2、p3、&、pn，其输出序列是1、2、3、&、n，若p3=3，则p1的值&&&&& 。
A. 可能是2&&&&&&&&&&&&&&&& B. 一定是2&&&&&&&&&&&&&&&& C. 不可能是1&&&&&&&&&&&&&&&&&&&& D. 一定是1
答：当p3=3时，进栈序列是p1、p2、3、&，由输出序列可知，只有以下两种情况。
（1）p1进栈后出栈，p2进栈后出栈，即p1=1，p2=2，p3（3）进栈后出栈，这种情况下
（2）p1、p2都进栈后都出栈，即p2=1，p1=2，p3（3）进栈后出栈，这种情况下p1=2。
实际上本题就是由p1、p2的进栈序列产生1、2的出栈序列，如图3.6所示，从中看到，p1可能是1，也可能是2，所以本题答案为A。
图3.6 &p1、p2产生1、2的出栈序列
【例3-1-14】设有5个元素的进栈序列是a、b、c、d、e，其输出序列是c、e、d、b、a，则该栈的容量至少是&&&&& 。
A. 1&&&&&&& &&&&&&&&&&&&& &&&&&& B. 2&&&&&&&&&&&&&&&&&&&&&&&&&&&& C. 3&&&&&&& &&&&&&&&&&&&& &&&&&& D. 4
答：进栈序列是a、b、c、d、e，输出序列是c、e、d、b、a的操作是：a进、b进、c进、c出、d进、e进、e出、d出、b出、a出。从中看到，栈中的最多元素为4个。本题答案为D。
【例3-1-15】在数据处理过程中常需要保存一些中间数据，如果后保存的数据先处理，则使用&&&&& 来保存这些数据。
A. 线性表&&&&&&&&&&&&&&&&&& B. 栈&&&&&&&&&&&&&&&&&&&&&&&&&& C. 队列&&&&&&&&&&&&&&&&&&&&&& D. 单链表
答：由于后保存的数据先处理，栈正好满足这个特点。本题答案为B。
【例3-1-16】栈是一种具有&&&&& 特性的线性表。
答：后进先出或先进后出。
【例3-1-17】顺序栈和链栈的区别仅在于它们是栈的不同&&&&& 。
答：存储结构。
【例3-1-18】一个栈的输入序列是12345，输出序列为12345，其进栈出栈的操作为 &&&&&。
答：1进栈，1出栈，2进栈，2出栈，3进栈，3出栈，4进栈，4出栈，5进栈，5出栈。
【例3-1-19】有n个元素，它们的编号为1～n，顺序的进入一个栈，则可能的出栈序列有&&&&& 种。
以下三类问题是等价的：（1）n个不相同元素进栈的出栈序列个数；（2）由n个不相同元素构成不同形态的二叉树个数；（3）n个不相同元素的先序序列构成不同形态的二叉树个数。
【例3-1-20】判断以下叙述的正确性。
（1）栈底元素是不能删除的元素。
（2）顺序栈中元素值的大小是有序的。
（3）在n个元素进栈后，它们的出栈顺序和进栈顺序一定正好相反。
（4）栈顶元素和栈底元素有可能是同一个元素。
（5）若用s[0..m-1]表示顺序栈的存储空间，则对栈的进栈、出栈操作最多只能进行m次。
（6）栈是一种对进栈、出栈操作总次数做了限制的线性表。
（7）栈是一种对进栈、出栈操作的次序做了限制的线性表。
（8）对顺序栈进行进栈、出栈操作，不涉及元素的前、后移动问题。
（9）空栈没有栈顶指针。
答：（1）错误。当栈中只有一个元素时，这个元素也称栈底元素，它可以删除。
（2）错误。顺序栈是指用顺序存储结构实现的栈，栈中的元素不一定是有序的。
（3）错误。例如进栈序列为123，出栈的序列可以是132。
（4）正确。当栈中只有一个元素时就是这种情况。
（5）错误。可以进行任意多次的进栈、出栈操作，但栈中最多只有m个元素。
（6）错误。可以进行任意多次的进栈、出栈操作。
（7）错误。只要栈不满就可以进行进栈操作，只要栈不空就可以进行出栈操作，并不规定进栈、出栈操作的次序。
（8）正确。
（9）错误。空栈是指栈中没有元素，但一定要有栈顶指针。
【例3-1-21】输入序列A、B、C通过一个栈后产生的全部输出序列有哪些？
答：利用栈的&后进先出&的特点，有如下几种情况：
l&&&&&&& A进，A出，B进，B出，C进，C出，产生输出序列ABC。
l&&&&&&& A进，A出，B进，C进，C出，B出，产生输出序列ACB。
l&&&&&&& A进，B进，B出，A出，C进，C出，产生输出序列BAC。
l&&&&&&& A进，B进，B出，C进，C出，A出，产生输出序列BCA。
l&&&&&&& A进，B进，C进，C出，B出，A出，产生输出序列CBA。
不可能产生输出序列CAB。
【例3-1-22】有5个元素，其进栈次序为A、B、C、D、E，在各种可能的出栈次序中，以元素C、D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？
答：可能的次序有CDBAE、CDEBA、CDBEA。
【例3-1-23】设输入元素为1、2、3、P和A，入栈次序为123PA，元素经过栈后到达输出序列，当所有元素均到达输出序列后，有哪些序列可以作为高级语言的变量名？
答：高级语言变量名的定义规则是：以字母开头的字母数字串。入栈次序为123PA，以A最先出栈的序列为AP321，以P最先出栈的序列为P321A、P32A1、P3A21、PA321。可以作为高级语言的变量名的序列为AP321、P321A、P32A1、P3A21和PA321。
【例3-1-24】设有一个数列的输入顺序为123456，若采用栈结构，并以S和X分别表示进栈和出栈操作，试求通过进栈和出栈操作的合法序列。
（1）能否得到输出顺序为325641的序列？
（2）能否得到输出顺序为154623的序列？
答：（1）能得到输出顺序为325641的序列，其操作序列为：SSSXXSSXSXXX。
（2）不能得到输出顺序为154623的序列；执行SXSSSSXXSX，得到输出序列1546后，栈中元素从栈顶到栈底为32，不能让2先出栈，所以得不到输出序列154623。
【例3-1-25】证明：有可能从初始输入序列1、2、&、n，利用一个栈得到输出序列p1、p2、&、pn（p1、p2、&、pn是1、2、&、n的一种排列）的充分必要条件是：不存在这样的i、j、k满足i&j&k同时pj&pk&pi。
【充分条件】如果不存在这样的i、j、k满足i&j&k，同时pj&pk&pi，即对于输入序列：
&,pj,&,pk,&,pi,&&& （pj&pk&pi）
不存在这样的输出序列：
&,pi,&,pj,&,pk,&
（或简单地对于输入序列1、2、3而言，不存在输出序列3、1、2）
从中看到，pi后进先出，满足栈的特点，因为pi最大也就是在pj和pk之后进入，却在输出序列中排在pj和pk之前，同时也说明，在pk之前先进入的pj不可能在pk之后出来，反过来说明满足先进后出的特点，所以构成一个栈。
【必要条件】如果初始输入序列是1、2、&、n，假设是进栈，又同时存在这样的i、j、k满足i&j&k同时pj&pk&pi，即对于输入序列：
&&,pj,&,pk,&,pi,&&& （pj&pk&pi）
存在这样的输出序列：
&&,pi,&,pj,&,pk,&
从中看到，pi先进后出，满足栈的特点，因为pi最大也就是在pj和pk之后进入，同时看到在pk之前先进入的pj却在pk之前出来，反过来说明不满足先进后出的特点，与前面的假设是栈不一致，本题即证。
【例3-1-26】假设以S和X分别表示进栈和出栈操作，则初态和终态为栈空的进栈和出栈的操作序列，可以表示为仅由S和X组成的序列。称可以实现的栈操作序列为合法序列（例如SSXX为合法序列，SXXS为非法序列）。试给出区分给定序列为合法序列或非法序列的一般准则，并证明：对同一输入序列的两个不同的合法序列不可能得到相同的输出元素序列。
答：合法的栈操作序列必须满足以下两个条件：
（1）在操作序列的任何前缀（从开始到任何一个操作时刻）中，S的个数不得少于X的个数。
（2）整个操作序列中S和X的个数相等。
要求证明：对同一输入序列a1a2&an的两个不同的合法操作序列：p=p1p2&pj-1pj&p2n，q=q1q2&qj-1qj&q2n,不可能得到相同的输出元素序列。
证明：因为p&q，所以一定存在一个j（1&j&2n，设合法的栈操作序列的长度为2n），使得p1p2&pj-1=q1q2&qj-1，而pj&qj，假设操作子序列p1p2&pj-1已将a1a2&ai-1进栈且将其中某些元素出栈，而aiai＋1&an尚未进栈。
因为p和q都是合法栈操作序列，且pj&qj，所以pj和qj中必有一个为S操作，另一个为X操作（不失一般性，不妨设pj为S操作，qj为X操作），而且栈不必为空（不然就不能进行X操作）。设栈顶元素为af（1&f&i）。因此对于操作序列p来说，在其对应的输出元素序列中ai必领先于af（因为pj为S操作，它使ai进栈，而af尚在栈中），对于操作序列q来说，在其对应的输出元素序列中，af必领先于ai（因为qj为X操作，它使af出栈而ai尚未进栈），所以p和q必定对应不同的输出元素序列。
【例3-1-27】有一个字符串序列3*-y-a/y&2，试利用栈给出将其改变为3y-*ay2&/-的操作步骤（可用S代表扫描该字符串函数中顺序取一字符进栈的操作，用X代表从栈中取出一个字符加到新字符串尾的出栈的操作）。例如，ABC变为BCA，则操作步骤为SSXSXX。
答：上述转换的过程如表3.1所示，进出栈的操作步骤为：SXSSSXXXSSXSSXSSXXXX。
表3.1 &利用栈转换字符串的过程
3*-y-a/y&2
3y-*ay2&/-
您对本文章有什么意见或着疑问吗？请到您的关注和建议是我们前行的参考和动力&&
您的浏览器不支持嵌入式框架，或者当前配置为不显示嵌入式框架。
文章下载读书