3 栈和队列答案
更新时间:2024-03-18 14:07:01 阅读量: 综合文库 文档下载
- 3d开奖结果推荐度:
- 相关推荐
第3章 栈和队列
一、基础知识题
3.1 设将整数1,2,3,4依次进栈,但只要出栈时栈非空,则可将出栈操作按任何次序夹入其中,请回答下述问题:
(1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈,Pop( )表示出栈)? (2)能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。
(3)请分析 1,2 ,3 ,4 的24种排列中,哪些序列是可以通过相应的入出栈操作得到的。
3.2 链栈中为何不设置头结点?
3.3 循环队列的优点是什么? 如何判别它的空和满? 3.4 设长度为n的链队用单循环链表表示,若设头指针,则入队出队操作的时间为何? 若只设尾指针呢?
3.5 指出下述程序段的功能是什么?
(1) void Demo1(SeqStack *S){ int i; arr[64] ; n=0 ;
while ( StackEmpty(S)) arr[n++]=Pop(S); for (i=0, i< n; i++) Push(S, arr[i]); } //Demo1
(2) SeqStack S1, S2, tmp; DataType x;
...//假设栈tmp和S2已做过初始化 while ( ! StackEmpty (&S1)) {
x=Pop(&S1) ; Push(&tmp,x); }
while ( ! StackEmpty (&tmp) ) {
x=Pop( &tmp); Push( &S1,x); Push( &S2, x); }
(3) void Demo2( SeqStack *S, int m) { // 设DataType 为int 型 SeqStack T; int i; InitStack (&T);
while (! StackEmpty( S))
if(( i=Pop(S)) !=m) Push( &T,i); while (! StackEmpty( &T)) {
i=Pop(&T); Push(S,i);
} }
(4)void Demo3( CirQueue *Q) { // 设DataType 为int 型 int x; SeqStack S; InitStack( &S);
while (! QueueEmpty( Q ))
{x=DeQueue( Q); Push( &S,x);} while (! StackEmpty( &s))
{ x=Pop(&S); EnQueue( Q,x );} }// Demo3
(5) CirQueue Q1, Q2; // 设DataType 为int 型 int x, i , n= 0;
... // 设Q1已有内容, Q2已初始化过 while ( ! QueueEmpty( &Q1) )
{ x=DeQueue( &Q1 ) ; EnQueue(&Q2, x); n++;} for (i=0; i< n; i++) { x=DeQueue(&Q2) ;
EnQueue( &Q1, x) ; EnQueue( &Q2, x);} 3.6 简述栈和线性表的差别。
3.7 写出下列程序段的输出结果(栈的元素类型SElemType为char)。 void main() {
Stack S; char x,y; InitStack(S);
x= ‘c’; y= ‘k’;
Push(S,x); Push(S, ‘a’); Push(S,y); Pop(S,x); Push(S, ‘t’); Push(S,x); Pop(S,x); Push(S, ‘s’);
while(!StackEmpty(S)) { Pop(S,y); printf(y); } printf(x); }
3.8 写出下列中缀表达式的后缀形式: (1) A * B * C
(2) - A + B - C + D (3) A* - B + C
(4) (A + B) * D + E / (F + A * D) + C
(5) A && B|| ! (E > F) /*注:按C++的优先级*/ (6) !(A && !( (B < C)||(C > D) ) )||(C < E) 二、算法设计题:
3.9 回文是指正读反读均相同的字符序列,如\和\均是回文,但\不是回文。试写一个算法判定给定的字符向量是否为回文。(提示:将一半字符入栈)
3.10 利用栈的基本操作,写一个将栈S中所有结点均删去的算法void
ClearStack( SeqStack *S),并说明S为何要作为指针参数?
3.11 利用栈的基本操作, 写一个返回S中结点个数的算法 int StackSize( SeqStack S),并说明S为何不作为指针参数?
3.12 设计算法判断一个算术表达式的圆括号是否正确配对。 (提示: 对表达式进行扫描,凡遇到'('就进栈,遇')'就退掉栈顶的'(',表达式被扫描完毕,栈应为空。 3.13 对于循环向量中的循环队列,写出求队列长度的公式。
3.14 假设循环队列中只设rear和quelen 来分别指示队尾元素的位置和队中元素的个数,试给出判别此循环队列的队满条件,并写出相应的入队和出队算法,要求出队时需返回队头元素。
一、基础知识题
3.1 设将整数1,2,3,4依次进栈,但只要出栈时栈非空,则可将出栈操作按任何次序夹入其中,请回答下述问题:
(1)若入、出栈次序为Push(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的出栈序列。具体操作为: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 3.2 链栈中为何不设置头结点? 答:
链栈不需要在头部附加头结点,因为栈都是在头部进行操作的,如果加了头结点,等于要对头结点之后的结点进行操作,反而使算法更复杂,所以只要有链表的头指针就可以了。 3.3 循环队列的优点是什么? 如何判别它的空和满? 答:
循环队列的优点是:它可以克服顺序队列的\假上溢\现象,能够使存储队列的向量空间得到充分的利用。判别循环队列的\空\或\满\不能以头尾指针是否相等来确定,一般是通过以下几种方法:一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合,如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数,不仅可判别空或满,还可以得到队列中元素的个数。
3.4 设长度为n的链队用单循环链表表示,若设头指针,则入队出队操作的时间为何? 若只设尾指针呢?
答:
当只设头指针时,出队的时间为1,而入队的时间需要n,因为每次入队均需从头指针开始查找,找到最后一个元素时方可进行入队操作。若只设尾指针,则出入队时间均为1。因为是循环链表,尾指针所指的下一个元素就是头指针所指元素,所以出队时不需要遍
历整个队列。
3.5 指出下述程序段的功能是什么? (1) void Demo1(SeqStack *S){ int i; arr[64] ; n=0 ;
while ( StackEmpty(S)) arr[n++]=Pop(S); for (i=0, i< n; i++) Push(S, arr[i]); } //Demo1
(2) SeqStack S1, S2, tmp; DataType x;
...//假设栈tmp和S2已做过初始化 while ( ! StackEmpty (&S1)) {
x=Pop(&S1) ; Push(&tmp,x); }
while ( ! StackEmpty (&tmp) ) {
x=Pop( &tmp); Push( &S1,x); Push( &S2, x); }
(3) void Demo2( SeqStack *S, int m) { // 设DataType 为int 型 SeqStack T; int i; InitStack (&T);
while (! StackEmpty( S))
if(( i=Pop(S)) !=m) Push( &T,i); while (! StackEmpty( &T)) {
i=Pop(&T); Push(S,i); } }
(4)void Demo3( CirQueue *Q) { // 设DataType 为int 型 int x; SeqStack S; InitStack( &S);
while (! QueueEmpty( Q ))
{x=DeQueue( Q); Push( &S,x);} while (! StackEmpty( &s))
{ x=Pop(&S); EnQueue( Q,x );} }// Demo3
(5) CirQueue Q1, Q2; // 设DataType 为int 型 int x, i , n= 0;
... // 设Q1已有内容, Q2已初始化过
while ( ! QueueEmpty( &Q1) )
{ x=DeQueue( &Q1 ) ; EnQueue(&Q2, x); n++;} for (i=0; i< n; i++) { x=DeQueue(&Q2) ;
EnQueue( &Q1, x) ; EnQueue( &Q2, x);} 答:
(1)程序段的功能是将一栈中的元素按反序重新排列,也就是原来在栈顶的元素放到栈底,栈底的元素放到栈顶。此栈中元素个数限制在64个以内。
(2)程序段的功能是利用tmp栈将一个非空栈s1的所有元素按原样复制到一个栈s2当中去。
(3)程序段的功能是利用栈T,将一个非空栈S中值等于m的元素全部删去。 (4)程序段的功能是将一个循环队列Q经过S栈的处理,反向排列,原来的队头变成队尾,原来的队尾变成队头。
(5)这段程序的功能是将队列1的所有元素复制到队列2中去,但其执行过程是先把队列1的元素全部出队,进入队列2,然后再把队列2的元素复制到队列1中。 3.6 简述栈和线性表的差别。
解:线性表是具有相同特性的数据元素的一个有限序列。栈是限定仅在表尾进行插入或删除操作的线性表。
3.7 写出下列程序段的输出结果(栈的元素类型SElemType为char)。 void main() {
Stack S; char x,y; InitStack(S);
x= ‘c’; y= ‘k’;
Push(S,x); Push(S, ‘a’); Push(S,y); Pop(S,x); Push(S, ‘t’); Push(S,x); Pop(S,x); Push(S, ‘s’);
while(!StackEmpty(S)) { Pop(S,y); printf(y); } printf(x); }
解:stack
3.8 写出下列中缀表达式的后缀形式: (1) A * B * C
(2) - A + B - C + D (3) A* - B + C
(4) (A + B) * D + E / (F + A * D) + C
(5) A && B|| ! (E > F) /*注:按C++的优先级*/ (6) !(A && !( (B < C)||(C > D) ) )||(C < E) 【解答】
(1) A B * C *
(2) A - B + C - D + (3) A B - * C +
(4) A B + D * E F A D * + / + C +
(5) A B && E F > ! ||
(6) A B C < C D > || ! && ! C E < ||
二、算法设计题: 二、算法设计题:
3.9 回文是指正读反读均相同的字符序列,如\和\均是回文,但\不是回文。试写一个算法判定给定的字符向量是否为回文。(提示:将一半字符入栈) 解:
根据提示,算法可设计为: //以下为顺序栈的存储结构定义
#define StackSize 100 //假定预分配的栈空间最多为100个元素 typedef char DataType;//假定栈元素的数据类型为字符 typedef struct{
DataType data[StackSize]; int top; }SeqStack;
int IsHuiwen( char *t)
{//判断t字符向量是否为回文,若是,返回1,否则返回0 SeqStack s; int i , len; char temp;
InitStack( &s);
len=strlen(t); //求向量长度
for ( i=0; i while( !EmptyStack( &s)) {// 每弹出一个字符与相应字符比较 temp=Pop (&s); if( temp!=S[i]) return 0 ;// 不等则返回0 else i++; } return 1 ; // 比较完毕均相等则返回 1 } 3.10 利用栈的基本操作,写一个将栈S中所有结点均删去的算法void ClearStack( SeqStack *S),并说明S为何要作为指针参数? 解: 算法如下 void ClearStack (SeqStack *S) { // 删除栈中所有结点 S->Top = -1; //其实只是将栈置空 } 因为要置空的是栈S,如果不用指针来做参数传递,那么函数进行的操作不能对原来的栈产生影响,系统将会在内存中开辟另外的单元来对形参进行函数操作。结果等于什么也没 有做。所以想要把函数操作的结果返回给实参的话,就只能用指针来做参数传递了。 3.11 利用栈的基本操作, 写一个返回S中结点个数的算法 int StackSize( SeqStack S),并说明S为何不作为指针参数? 解: 算法如下: int StackSize (SeqStack S) {//计算栈中结点个数 int n=0; if(!EmptyStack(&S)) { Pop(&S); n++; } return n; } 上述算法的目的只要得到S栈的结点个数就可以了。并不能改变栈的结构。所以S不用指针做参数,以避免对原来的栈中元素进行任何改变。系统会把原来的栈按值传递给形参,函数只对形参进行操作,最后返回元素个数。 3.12 设计算法判断一个算术表达式的圆括号是否正确配对。 (提示: 对表达式进行扫描,凡遇到'('就进栈,遇')'就退掉栈顶的'(',表达式被扫描完毕,栈应为空。 解: 根据提示,可以设计算法如下: int PairBracket( char *SR) {//检查表达式ST中括号是否配对 int i; SeqStack S; //定义一个栈 InitStack (&s); for (i=0; i if ( S[i]=='(' ) Push(&S, SR[i]); //遇'('时进栈 if ( S[i]==')' ) //遇')' if (!StackEmpty(S))//栈不为空时,将栈顶元素出栈 Pop(&s); else return 0;//不匹配,返回0 } if EmptyStack(&s) return 1;// 匹配,返回1 else return 0;//不匹配,返回0 } 3.13 对于循环向量中的循环队列,写出求队列长度的公式。 解: 公式如下(设采用第二种方法,front指向真正的队首元素,rear指向真正队尾后一位置,向量空间大小:QueueSize Queuelen=(QueueSize+rear-front)%QueueSize 3.14 假设循环队列中只设rear和quelen 来分别指示队尾元素的位置和队中元素的个数, 试给出判别此循环队列的队满条件,并写出相应的入队和出队算法,要求出队时需返回队头元素。 解: 根据题意,可定义该循环队列的存储结构: #define QueueSize 100 typedef char Datatype ; //设元素的类型为char型 typedef struct { int quelen; int rear; Datatype Data[QueueSize]; }CirQueue; CirQueue *Q; 循环队列的队满条件是:Q->quelen==QueueSize 知道了尾指针和元素个数,当然就能计算出队头元素的位置。算法如下: (1)判断队满 int FullQueue( CirQueue *Q) {//判队满,队中元素个数等于空间大小 return Q->quelen==QueueSize; } (2)入队 void EnQueue( CirQueue *Q, Datatype x) {// 入队 if(FullQueue( Q)) Error(\队已满,无法入队\ Q->Data[Q->rear]=x; Q->rear=(Q->rear+1)%QueueSize;//在循环意义上的加1 Q->quelen++; } (3)出队 Datatype DeQueue( CirQueue *Q) {//出队 if(Q->quelen==0) Error(\队已空,无元素可出队\ int tmpfront; //设一个临时队头指针 tmpfront=(QueueSize+Q->rear - Q->quelen+1)%QueueSize;//计算头指针位置 Q->quelen--; return Q->Data[tmpfront]; }
正在阅读:
3 栈和队列答案03-18
硕士研究生复试政审表填写模板102-20
部编语文二下教材分析及听课笔记04-20
存储技术基础 实验一 LUNs的配置03-28
GILAIR-3及GILAIR-5 空气采样器 说明书 - 图文12-28
海洋科学导论考试复习题04-07
2014年高考理科分段人数07-22
参观科技馆活动安全应急预案09-21
第8课 春秋战国的纷争07-19
4.16 医学影像管理与持续改进09-30
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 队列
- 答案
- 2012年高考历史 高考试题+模拟新题分类汇编专题17 古今中国的科
- 3-25列方程组解应用题
- “新工科”背景下民办高校应用型本科物联网工程专业人才培养模式
- 电大《中国传统文化导论》最全的复习资料
- 新东方社会实践报告
- 2014年11月份三级笔译实务(汉译英)真题
- 小学综合组教研活动讲稿
- 专四语法分类汇总
- 公务员面试真题
- 我国民事执行法律制度的缺陷及完善(下)探讨与研究
- 练习题
- 10年理科综合考试大纲
- 2017-2022年中国汽车转向系统市场投资前景分析研究报告(目录)
- 苏教版三年级上册英语期末专项复习题
- 南开17春秋学期《经济统计与EXCEL的统计分析》在线作业
- 实验一-M序列的产生及其特性试验
- 山东省郓城县郓城镇南城初级中学八年级语文上册第一单元拓展阅读
- 易经与姓名学规律 - 图文
- DSP的FFT实现设计报告
- 证券事务代表的任职资格整理汇总