您现在的位置：希赛教育首页 > 自考学院 > 数据结构与算法 > 正文
数据结构第三章(栈与队列)习题参考答案
作者：自考频道 来源：希赛教育 20xx年1月5日 发表评论 进入社区
一、基础知识题
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的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢?
答：当只设头指针时，出队的时间为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 , m = 0;
... // 设Q1已有内容， Q2已初始化过 while ( ! QueueEmpty( &Q1) )
{ x=DeQueue( &Q1 ) ; EnQueue(&Q2, x); m++;} for (i=0; i< n; i++)
{ x=DeQueue(&Q2) ;
EnQueue( &Q1, x) ; EnQueue( &Q2, x);} 答：
(1)程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此栈中元素个数限制在64个以内。
(2)程序段的功能是利用tmp栈将一个非空栈的所有元素按原样复制到一个空栈当中去。
(3)程序段的功能是将一个非空栈中值等于m的元素全部删去。
(4)程序段的功能是将一个循环队列反向排列，原来的队头变成队尾，原来的队尾变成队头。
(5)首先指出程序可能有印刷错误，for语句中的n应为m才对。这段程序的功能是将队列1的所有元素复制到队列2中去，但其执行过程是先把队列1的元素全部出队，进入队列2，然后再把队列2的元素复制到队列1中。
二、算法设计题
3.6 回文是指正读反读均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈) 解：根据提示，算法可设计为：
//ishuiwen.h 存为头文件
int IsHuiwen( char *S)
{
SeqStack T;
int i , l;
char t;
InitStack( &T);
l=strlen(S); //求向量长度
for ( i=0; i
Push( &T, S[i]);
while( !EmptyStack( &T))
{
// 每弹出一个字符与相应字符比较 t=Pop (&T);
if( t!=S[l-i]) { return 0 ;}// 不等则返回0 i--;
}
return -1 ; // 比较完毕均相等则返回 -1 }
// 以下程序用于验证上面的算法 //以下是栈定义( 存为stack.h) //出错控制函数
#include
#include
void Error(char * message)
{
fprintf(stderr, "Error: %s\n",message); exit(1);
}
// 定义栈类型
#define StackSize 100
typedef char Datatype;
typedef struct{
Datatype data[StackSize]; int Top;
} SeqStack;
void InitStack( SeqStack *S) {
//初始化(置空栈)
S->Top=-1;
}
int EmptyStack(SeqStack *S) { //判栈空
return S->Top == -1;
}
int FullStack (SeqStack *S) { // 判栈满
return S->Top==StackSize-1; }
void Push (SeqStack *S , Datatype x) { //进栈
if(FullStack(S))
Error("Stack overflow");
S->data[++S->Top]=x;
}
Datatype Pop(SeqStack *S) { // 出栈(退栈)
if (EmptyStack( S) )
Error( "Stack underflow"); return S->data[S->Top--]; }
//取栈顶元素(略)
//----------------------------------------------- //以下是主程序
#include
#include
#include "stack.h>
#include "ishuiwen.h"
void main( )
{
char Str[100]="";
printf("输入一个字符串:\n"); scanf("%s",Str);
if( IsHuiwen(Str))
printf(" \n这个字符串是回文。");
else printf("\n这个字符串不是回文。"); }
附：肖平来信指出问题：
个人认为如题目所言，"abba"和"abdba"均是回文,但对于这两种回文需要区别对待，原算法在判断类似"abdba"的回文时，会认为其不是回文而与题意相违背!
我的编程思想是：设置一个float型的变量，用于存放字符串的长度，再利用取整函数对长度为奇数的回文进行判别，若将字符串长度附给一整型变量，那么无论该整形变量除任何整数，其结果仍然是一整数，因此必须设一实型变量!判断结束后，若是回文返回1，不是则返回0。
我的算法如下,已验证通过：
int HuiWen(char *p)
{
int i;
float t;
SeqStack S;
InitStack(&S);
t=strlen(p);
for(i=0;i<=t/2-1;i++)
Push(&S,p[i]);
if(floor(t/2)!=(t/2)) //针对"abdba"类的回文
i++;
while(p[i]!='\0')
if(Pop(&S)==p[i])
i++;
else
return(0);
return(1);
}
=================================================
也可以直接用字符指针而不用字符数组来处理，只需对算法稍作修改! 算法如下，已验证通过：
int HuiWen(char *p)
{
int i;
float t;
SeqStack S;
InitStack(&S);
t=strlen(p);
for(i=0;i<=t/2-1;i++，p++)
Push(&S,*p);
if(floor(t/2)!=(t/2)) //针对"abdba"类的回文
p++;
while(*p!='\0')
if(Pop(&S)==*p)
p++;
else
return(0);
return(1);
}
3.7 利用栈的基本操作，写一个将栈S中所有结点均删去的算法void
ClearStack( SeqStack *S)，并说明S为何要作为指针参数?
解： 算法如下
void ClearStack (SeqStack *S)
{ // 删除栈中所有结点
S->Top = -1; //其实只是将栈置空
}
因为我们要置空的是栈S，如果不用指针来做参数传递，那么函数进行的操作不能对原来的栈产生影响，系统将会在内存中开辟另外的单元来对形参进行函数操作。结果等于什么也没有做。所以想要把函数操作的结果返回给实参的话，就只能用指针来做参数传递了。
3.8 利用栈的基本操作， 写一个返回S中结点个数的算法 int StackSize( SeqStack S),并说明S为何不作为指针参数?
解：算法如下：
int StackSize (SeqStack S)
{
//计算栈中结点个数
int n=0;
if(!EmptyStack(&S))
{
Pop(&S);
n++;
}
return n;
}
类似于上面的原因，我们要计算栈中元素个数就要弹出元素才能"数"得出来，那如果用指针做参数的话，就会把原来的栈中元素"弹"光，要恢复还得用别的办法给它装回去，而不用指针做参数，则可以避免对原来的栈中元素进行任何操作，系统会把原来的栈按值传递给形参，函数只对形参进行操作，最后返回元素个数就可以了。
3.9 设计算法判断一个算术表达式的圆括号是否正确配对。 (提示： 对表达式进行扫描，凡遇到'('就进栈，遇')'就退掉栈顶的'('，表达式被扫描完毕，栈应为空。
解：根据提示，可以设计算法如下：
#include
#include "stack.h"
int PairBracket( char *S)
{
//检查表达式中括号是否配对
int i;
SeqStack T; //定义一个栈
InitStack (&T);
for (i=0; i
{
if ( S[i]=='(' ) Push(&T, S[i]); //遇'('时进栈
if ( S[i]==')' ) Pop(&T); //遇')'时出栈
}
return StackEmpty(&T); // 由栈空否返回正确配对与否
}
3.10 一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。 试为此双向栈设计初始化InitStack ( S ) 、入栈Push( S , i , x) 和出栈Pop( S , i )等算法， 其中i为0 或1， 用以表示栈号。
解：双向栈其实和单向栈原理相同，只是在一个向量空间内，好比是两个头对头的栈放在一起，中间的空间可以充分利用。双向栈的算法设计如下：
//双向栈的栈结构类型与以前定义略有不同
#define StackSize 100 // 假定分配了100个元素的向量空间
#define char Datatype
typedef struct{
Datatype Data[StackSize]
int top0; //需设两个指针
int top1;
}DblStack
void InitStack( DblStack *S )
{ //初始化双向栈
S->top0 = -1;
S->top1 = StackSize; //这里的top2也指出了向量空间，但由于是作为栈底，因此不会出错
}
3.11 Ackerman 函数定义如下：请写出递归算法。
[ n+1 当m=0时
AKM ( m , n ) = \{ AKM( m-1 ,1) 当m≠0 ，n=0时
[ AKM( m-1, AKM( m,n-1)) 当m≠0, n ≠ 0时
解：算法如下
int AKM( int m, int n)
{
if ( m== 0) return n+1;
if ( m<>0 && n==0 ) return AKM( m-1, 1);
if ( m<>0 && n<>0 ) return AKM( m-1, AKM( m, n-1));
}
3.12 用第二种方法 ，即少用一上元素空间的方法来区别循环队列的队空和队满，试为其设计置空队，判队空，判队满、出队、入队及取队头元素等六个基本操作的算法。 解：算法设计如下:
//存为Queue2.h文件
void InitQueue ( CirQueue *Q)
{ // 置空队
Q->front=Q->rear=0;
}
int EmptyQueue( CirQueue *Q)
{ //判队空
return Q->front==Q->rear;
}
int FullQueue( CirQueue *Q)
{ // 判队满//如果尾指针加1后等于头指针，则认为满
return (Q->rear+1)%QueueSize== Q->front;
}
3.13 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针) ，试编写相应的置空队、判队空 、入队和出队等算法。
解：算法如下：
//先定义链队结构:
typedef struct queuenode{
Datatype data;
struct queuenode *next;
}QueueNode; //以上是结点类型的定义
typedef struct{
queuenode *rear;
}LinkQueue; //只设一个指向队尾元素的指针
//linkQ.h 相应算法
void InitQueue( LinkQueue *Q)
{ //置空队：就是使头结点成为队尾元素
Q->rear = Q->rear->next;//头结点成为尾结点
Q->rear->next = Q->rear;//形成循环链表
}
int EmptyQueue( LinkQueue *Q)
{ //判队空
//当头结点的next指针指向自己时为空队
return Q->rear->next->next==Q->rear->next;
}
void EnQueue( LinkQueue *Q, Datatype x)
{ //入队
//也就是在尾结点处插入元素
QueueNode *p=(QueueNode *) malloc (sizeof(QueueNode));//申请新结点 p->data=x; p->next=NULL;//初始化结点
Q-rear->next->next=p; // 将新结点链入
p->next=Q->rear; //形成循环链表
Q->rear=p;//将尾指针移至新结点
}
Datatype DeQueue( LinkQueue *Q)
{ //出队
//把头结点之后的元素摘下
Datatype t;
QueueNode *p;
if(EmptyQueue( Q ))
Error("Queue underflow");
p=Q->rear->next->next; //将要摘下的结点
x=p->data; //保存结点中数据
Q->rear->next->next=p->next;//摘下结点p
free(p);//释放被删结点
return x;
}
肖平朋友提出看法：
仔细研究了原算法，发现存在以下几个问题：
1)虽然使用了Q->rear->next来代替头结点的表示方法，但不如直接定义头结点Q->head来的方便，而且题目也明确要求了使用头结点，在结构定义中只反映出去掉了头指针，没有反映出该链队列是否包含头结点;
2)对于入队算法，是采用头插法将新结点依次链入头结点的后面，这似乎与队列的定义相违背。队列应该在尾部入队，而不是在头部入队;
3)同上，出队操作仍然在头部进行。若顺序运行入队和出队算法，由于均在头部进行，其结果会将该队列演变成一个栈!
=================================================
我的算法如下：
typedef struct
{ QueueNode head; //去掉头指针，增加头结点!
QueueNode *rear;
}LinkQueue;
置空队：
void InitQueue(LinkQueue *Q)
{
Q->rear=Q->head;
Q->head->next=Q->rear; //形成循环空队列，尾指针指向空队列内唯一的头结点 }
判队空：
int QueueEmpty(LinkQueue *Q)
{
return Q->head->next==Q->rear;
}
入队：
void EnQueue(LinkQueue *Q)
{
QueueNode *p=(Queue *)malloc(sizeof(QueueNode));
p->data=x;
Q->rear->next=p;
p->next=Q->head;
Q->rear=p; //对于空队列，由于Q->rear=Q->head，因此第一个结点和后续结点的入队操作均一致
}
出队：
DataType DeQueue(LinkQueue *Q)
{
if(QueueEmpty(Q))
Error("Queue underflow");
DataType x;
QueueNode *p;
p=Q->head->next;
x=p->data;
Q->head->next=p->next;
if(Q->rear==p)
Q->rear=Q->head; //当最后一个结点也出队后，队列为空，尾指针重新指向头结点 free(p);
return x;
}
3.14 对于循环向量中的循环队列，写出求队列长度的公式。
解：公式如下：
Queuelen= 0 当EmptyQueue
Queuelen= rear - front 当rear>front
Queuelen= rear+QueueSize-front 当rear
Queuelen= QueueSize 当FullQueue
3.15 假设循环队列中只设rear和quelen 来分别指示队尾元素的位置和队中元素的个数，试给出判别此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素。
解：知道了尾指针和元素个数，当然就能知道队头元素了。算法如下：
int FullQueue( CirQueue *Q)
{
//判队满,队中元素个数等于空间大小
return Q->quelen==QueueSize;
}
void EnQueue( CirQueue *Q, Datatype x)
{
// 入队
if(FullQueue( Q))
Error("队已满，无法入队");
Q->Data[Q->rear]=x;
Q->rear=(Q->rear+1)%QueueSize;//在循环意义上的加1 Q->quelen++;
}
Datatype DeQueue( CirQueue *Q)
{
//出队
if(Q->quelen==0)
Error("队已空，无元素可出队");
int tmpfront; //设一个临时队头指针
if(Q->rear > Q->quelen)//计算头指针位置
tmpfront=Q->rear - Q->quelen;
else
tmpfront=Q->rear + QueueSize - Q->quelen;
quelen--;
return Q->Data[tmpfront];
}
//如果需要验证上面的算法，则需定义好结点类型的队列结构，以相应的变量来表示尾指针和队列长度。自己试试吧。最主要的是能够理解算法的意义和实现。
【大 中 小】【收藏到我的希赛教育】 【发表评论】【进入社区】
相关文章
·09年自考《数据结构》各章要点二[12] (2008-11-19)
·09年自考《数据结构》各章要点二[11] (2008-11-19)
·09年自考《数据结构》各章要点二[10] (2008-11-19)
·09年自考《数据结构》各章要点二[9] (2008-11-19)
·09年自考《数据结构》各章要点二[8] (2008-11-19)
·09年自考《数据结构》各章要点二[7] (2008-11-19)
·09年自考《数据结构》各章要点二[6] (2008-11-19)
·09年自考《数据结构》各章要点二[5] (2008-11-19)
·09年自考《数据结构》各章要点二[4] (2008-11-19)
·09年自考《数据结构》各章要点二[3] (2008-11-19)
·20xx年上半年系统分析师上午第18题
·20xx年上半年网络规划设计师下午Ⅰ第3题
·20xx年上半年网络规划设计师上午第1题
·2010上半年网络管理员下午第2题
·20xx年上半年网络规划设计师上午第13-14题
·20xx年上半年网络规划设计师上午第27-28题
·2010上半年多媒体应用设计师下午第2题
·20xx年上半年系统分析师上午第60题
·2010上半年信息处理技术员上午第1题 ·20xx年上半年信息系统监理师上午第
12题
·2010上半年软件设计师上午第23题
·2010上半年多媒体应用设计师上午第50题
博客推荐
加班费和饭碗你..
[zyihan] 深度挖掘女性职场晋升攻略
[data0204wu] 10年考研英语经典范文
[blende] 如何实施Build验证测试
[hanlix] 让CMMI融入我们的日常工作
[sunny_wwh] Oracle维护常用SQL语句汇总
[zljchh] 网络工程师常用英文单词和缩写翻译
关于我们 | 网站导航 | 投稿指南 | 友情链接 | 在线客服 | 用户注册 | 错误报告 | 工作机会 |
联系我们
希赛教育
版权所有
? 2001-2010
湘ICP备05000393号 增值电信业务经营许可证湘B2-20070093
全国统一客服热线：400-777-1218 | 互联网违法和不良信息举报中心 | 不良信息举报信箱