文档库 最新最全的文档下载
当前位置:文档库 › 《数据结构》习题集:第3章 栈和队列

《数据结构》习题集:第3章 栈和队列

《数据结构》习题集:第3章 栈和队列
《数据结构》习题集:第3章 栈和队列

第3章栈和队列

一、选择题

1.栈结构通常采用的两种存储结构是(A )。

A、顺序存储结构和链表存储结构

B、散列和索引方式

C、链表存储结构和数组

D、线性链表结构和非线性存储结构

2.设栈ST 用顺序存储结构表示,则栈ST 为空的条件是( B )

A、ST.top-ST.base<>0

B、ST.top-ST.base==0

C、ST.top-ST.base<>n

D、ST.top-ST.base==n

3.向一个栈顶指针为HS 的链栈中插入一个s 结点时,则执行( C )

A、HS->next=s;

B、s->next=HS->next;HS->next=s;

C、s->next=HS;HS=s;

D、s->next=HS;HS=HS->next;

4.从一个栈顶指针为HS 的链栈中删除一个结点,用x 保存被删除结点的值,则执行( C)

A 、x=HS;HS=HS->next;

B 、HS=HS->next;x=HS->data;

C 、x=HS->data;HS=HS->next;

D 、s->next=Hs;Hs=HS->next;

5.表达式a*(b+c)-d 的后缀表达式为( B )

A、abcdd+-

B、abc+*d-

C、abc*+d-

D、-+*abcd

6.中缀表达式A-(B+C/D)*E 的后缀形式是( D )

A、AB-C+D/E*

B、ABC+D/E*

C、ABCD/E*+-

D、ABCD/+E*-

7.一个队列的入列序列是1,2,3,4,则队列的输出序列是( B )

A、4,3,2,1

B、1,2,3,4

C、1,4,3,2

D、3,2,4,1

8.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值,已知其头尾指针分别是front 和rear,则判定此循环队

列为空的条件是()

A、Q.rear-Q.front==n

B、Q.rear-Q.front-1==n

C、Q.front==Q.rear

D、Q.front==Q.rear+1

9.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值,已知其头尾指针分别是front 和rear,则判定此循环队

列为满的条件是()

A、Q.front==Q.rear

B、Q.front!=Q.rear

C、Q.front==(Q.rear+1)%n

D、Q.front!=(Q.rear+1)%n

10.若在一个大小为6 的数组上实现循环队列,且当前rear 和front 的值分别为0 和3,当从队列中删除一个元素,

再加入两个元素后,rear 和front 的值分别为()

A、1,5

B、2, 4

C、4,2

D、5,1

11.用单链表表示的链式队列的队头在链表的()位置

A、链头

B、链尾

C、链中

12.判定一个链队列Q(最多元素为n 个)为空的条件是()

A、Q.front==Q.rear

B、Q.front!=Q.rear

C、Q.front==(Q.rear+1)%n

D、Q.front!=(Q.rear+1)%n

13.在链队列Q 中,插入s 所指结点需顺序执行的指令是()

A 、Q.front->next=s;f=s;

B 、Q.rear->next=s;Q.rear=s;

C 、s->next=Q.rear;Q.rear=s;

D 、s->next=Q.front;Q.front=s;

14.在一个链队列Q 中,删除一个结点需要执行的指令是()

A、Q.rear=Q.front->next;

B、Q.rear->next=Q.rear->next->next;

C、Q.front->next=Q.front->next->next;

D、Q.front=Q.rear->next;

15.用不带头结点的单链表存储队列,其队头指针指向队头结点,队尾指针指向队尾结点,则在进行出队操作时()

A、仅修改队头指针

B、仅修改队尾指针

C、队头尾指针都要修改

D、队头尾指针都可能要修改。

16.栈和队列的共同点是()

A、都是先进后出

B、都是先进先出

C、只允许在端点处插入和删除元素

D、没有共同点

17.消除递归()需要使用栈。

A、一定

B、不一定

18.设有一顺序栈S,元素s1,s2,s3,s4,s5,s6 依次进栈,如果6 个元素出栈的顺序是s2,s3,s4,s6,s5,s1,

则栈的容量至少应该是()

A、2

B、3

C、5

D、6

19.若一个栈的输入序列是a,b,c,则通过入、出栈操作可能得到a,b,c 的不同排列个数为()

A、4

B、5

C、6

D、7

20.设有一顺序栈已经含有3 个元素,如图3.1 所示元素a4 正等待进栈。下列不可能出现的出栈序列是()

A、a3,a1,a4,a2

B、a3,a2,a4,a1

C、a3,a4,a2,a1

D、a4,a3,a2,a1

图3.1

21.链栈和顺序栈相比,有一个比较明显的优势是()

A、通常不会出现栈满的情况

B、通常不会出现栈空的情况

C、插入操作更容易实现

D、删除操作更加容易实现

22.若一个栈的输入序列是1,2,3,4,…,n,输出序列的第一个元素是n,则第i 个输出元素是( C )

A、不确定

B、n-i

C、n-i+1

D、n-i-1

23.以下说法正确的是( )

A、因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况

B、因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况

C、对于链栈而言,在栈满状态下,如果此时再作进栈运算,则会发生“上溢”

D、对于顺序栈而言在栈满状态下如果此时再作进栈运算,则会发生“下溢”。

二、判断题

1.在顺序栈栈满情况下,不能做进栈运算,否则会产生“上溢”。

2.链栈与顺序栈相比的一个优点是链栈插入和删除操作更加方便。

3.若一个栈的输入序列为1,2,3,…,n,其输出序列的第一个元素为n,则其输出序列的每个元素一定满足

a i=i+1(i=1,2, …,n)。

4.在链队列中,即使不设置尾指针也能进行入队操作。

5.在对链队列(带头指针)做出队操作时,不会改变front 指针的值。

6.循环队列中元素个数为rear-front。

7.一个栈的输入序列是1,2,3,4,则在栈的输出序列中可以得到4,3,1,2。

8.一个栈的输入序列是1,2,3,4,则在栈的输出序列中可以得到1,2,3,4。

9.若以链表作为栈的存储结构,则进栈需要判断栈是否满。

10.若以链表作为栈的存储结构,则出栈需要判断栈是否空。

三、填空题

1.栈的特点是(先进后出),队列的特点是(先进先出)。

2.线性表、栈、队列都是()结构,可以在线性表的()位置插入和删除元素;对于栈只能在()插

入和删除元素;对于队列只能在()插入元素和在()位置删除元素。

3.有程序如下,则此程序的输出结果(栈的元素类型是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);

}

4.在栈顶指针为HS 的链栈中,判定栈空的条件是()。

5.向栈中压入元素的操作是先()后()。

6.对栈进行退栈操作是先()后()。

7.用循环链表表示的队列长度为n,若只设头指针,则出队和入队的时间复杂度分别是()和();若只

设尾指针,则出队和入队的时间复杂度分别是()和()。

8.从循环队列中删除一个元素时,其操作是()。

9.在一个循环队列中,队首指针指向队首元素的()。

10.在具有n 个单元的循环队列中,队满时共有()个元素。

11.在HQ 的链队列中,判断只有一个结点的条件是()。

12.设栈S 和队列Q 的初始状态为空,元素a、b、c、d、e、f 依次通过栈S,一个元素出栈后即进入队列Q。若

这6个元素出队列的顺序是b、d、c、f、e、a 则栈S 的容量至少应该是()。

13.有程序如下,则此程序的输出结果(队列的元素类型是QSelemType 为char)是()。

void main(){

char x=’e’,y=’c’;

enqueue(q,’h’);enqueue(q,’r’);enqueue(q,y);dequeue(q,x);enqueue(q,x);degueue(q,x);

enqu eue(q,’a’);

while(!queueempty(q)){

dequeue(q,y);printf(y);

}

printf(x);

}

14.有如下递归函数:

int dunno(int m){

int value;

if(m==0)

value=3;

else

value=dunno(m-1)+5;

return(value);

}

执行语句printf(“%d\n”,dunno(3));的结果是()。

四、简答题

1.对于堆栈,给出三个输入项A,B,C,如果输入项序列为ABC,试给出全部可能的输出序列,并写

出每种序列对应的操作。例如:A 进B 进C 进C 出B 出A 出,产生的序列为CBA。

2.简述以下算法的功能(栈的元素类型是SelemType 为int)。

(1)

status algo1(stack s){

int I,n,a[255];

n=0;

while(!stackempty(s)){

n++;

pop(s,a[n]);

}

for(I=1;I<=n;I++)

push(s,a[I]);

}

(2)

status algo2(stack s,int e){

stack t;int d;

initstack(t);

while(!stackempty(s)){

pop(s,d);

if(d!=e)

push(t,d);

}

while(!stackempty(t)){

pop(t,d);

push(s,d);

}

}

3.内存中一片连续空间(不妨假设地址从0 到m-1)提供给两个栈s1 和s2 使用,怎样分配这部分存储空间,

使得对任一栈仅当这部分空间全满时才发生溢出。

4.有递归过程如下:

void print(int w){

int I;

if(w!=0){

print(w-1);

for(I=1;I<=w;I++)

printf(“%3d”,w);

printf(“\n”);

}

}

问:调用语句print(4)的结果是什么?

5.简述以下算法的功能(栈和队列的元素类型均为int)

void algo(queue &q){

stack s;

int d;

initstack(s);

while(!queueempty(q)){

dequeue(q,d);

push(s,d);

}

while(!stackempty(s)){

pop(s,d);

enqueue(q,d);

}

}

6.假设Q[0,9]是一个非循环线性队列,初始状态为front=rear=0,画出做完下列操作后队列的头尾指针的状态变

化情况,如果不能入队,请指出其元素,并说明理由。

d,e,b,g,h 入队d,e 出队I,j,k,l,m入队 b 出队n,o,p,q,r 入队。

7.按照运算符优先数法,画出对下面算术表达式求值时,操作数栈和运算符栈的变化过程:

9-2*4+(8+1)/3。

8.设栈S=(1,2,3,4,5,6,7),其中7 为栈顶元素。写出调用algo 后栈S 的状态。

void algo(Stack *S){

int i=0;

Queue Q;

Stack T;

InitQueue(Q);

InitStack(T);

while(!StackEmpty(S)){

if(i%2==0)

Push(T,Pop(S));

else

EnQueue(Q,Pop(S));

i++;

}

while(!QueueEmpty(Q))

Push(S,DeQueue(Q));

while(!StackEmpty(T))

Push(S,Pop(T));

}

五、设计题

1.回文是指正读反读均相同的字符序列,如“abba”和“abdba”均是回文,但“good”不是回文。试写一个算

法判定给定的字符向量是否为回文。(提示:将一半字符入栈)

2.设从键盘输入一整数的序列:a1, a2, a3,…,an,试编写算法实现:用栈结构存储输入的整数,当ai≠-1时,

将ai进栈;当ai=-1时,输出栈顶整数并出栈。算法应对异常情况(入栈满等)给出相应的信息。

3.从键盘上输入一个后缀表达式,试编写算法计算表达式的值。规定:逆波兰表达式的长度不超过一行,以$符

作为输入结束,操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如:234 34+2*$。

4.假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空,入栈和出栈的操作序列可表示为仅由I和O

组成的序列,称可以操作的序列为合法序列,否则称为非法序列。

①下面所示的序列中哪些是合法的?

A. IOIIOIOO

B. IOOIOIIO

C. IIIOIOIO

D. IIIOOIOO

②通过对①的分析,写出一个算法,判定所给的操作序列是否合法。若合法,返回true,否则返回false(假定

被判定的操作序列已存入一维数组中)。

5.假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素站点(注意不设头指针) ,试编写相应的

置空队、判队空、入队和出队等算法。

6.假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag,以tag == 0和tag == 1来区别在队头指针(front)

和队尾指针(rear)相等时,队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。

7.如果允许在循环队列的两端都可以进行插入和删除操作。要求:

①写出循环队列的类型定义;

②写出“从队尾删除”和“从队头插入”的算法。

8.已知Ackermann函数定义如下:

a)

①写出计算Ack(m,n)的递归算法,并根据此算法给出出Ack(2,1)的计算过程。

②写出计算Ack(m,n)的非递归算法。

9.已知f为单链表的表头指针, 链表中存储的都是整型数据,试写出实现下列运算的递归算法:

①求链表中的最大整数;

②求链表的结点个数;

③求所有整数的平均值。

(2)回文是指正读反读均相同的字符序列,如“abba”和“abdba”均是回文,但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示:将一半字符入栈)

根据提示,算法可设计为:

//以下为顺序栈的存储结构定义

#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

Push( &s, t[i]);

while( !EmptyStack( &s))

{// 每弹出一个字符与相应字符比较

temp=Pop (&s);

if( temp!=S[i]) return 0 ;// 不等则返回0

else i++;

}

return 1 ; // 比较完毕均相等则返回 1

}

(3)设从键盘输入一整数的序列:a1, a2, a3,…,a n,试编写算法实现:用栈结构存储输入的整数,当a i≠-1时,将a i进栈;当a i=-1时,输出栈顶整数并出栈。算法应对异常情况(入栈满等)给出相应的信息。

#define maxsize 栈空间容量

void InOutS(int s[maxsize])

//s是元素为整数的栈,本算法进行入栈和退栈操作。

{int top=0; //top为栈顶指针,定义top=0时为栈空。

for(i=1; i<=n; i++) //n个整数序列作处理。

{scanf(“%d”,&x); //从键盘读入整数序列。

if(x!=-1) // 读入的整数不等于-1时入栈。

if(top==maxsize-1){printf(“栈满\n”);exit(0);}else s[++top]=x; //x入栈。

else //读入的整数等于-1时退栈。

{if(top==0){printf(“栈空\n”);exit(0);} else printf(“出栈元素是%d\n”,s[top--]);}} }//算法结束。

(4)从键盘上输入一个后缀表达式,试编写算法计算表达式的值。规定:逆波兰表达式的长度不超过一行,以$符作为输入结束,操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如:234 34+2*$。

[题目分析]逆波兰表达式(即后缀表达式)求值规则如下:设立运算数栈OPND,对表达式从左到右扫描(读入),当表达式中扫描到数时,压入OPND栈。当扫描到运算符时,从OPND退出两个数,进行相应运算,结果再压入OPND 栈。这个过程一直进行到读出表达式结束符$,这时OPND栈中只有一个数,就是结果。

float expr( )

//从键盘输入逆波兰表达式,以‘$’表示输入结束,本算法求逆波兰式表达式的值。

{float OPND[30]; // OPND是操作数栈。

init(OPND); //两栈初始化。

float num=0.0; //数字初始化。

scanf (“%c”,&x);//x是字符型变量。

while(x!=’$’)

{switch

{case‘0’<=x<=’9’:while((x>=’0’&&x<=’9’)||x==’.’) //拼数

if(x!=’.’) //处理整数

{num=num*10+(ord(x)-ord(‘0’)); scanf(“%c”,&x);}

else //处理小数部分。

{scale=10.0; scanf(“%c”,&x);

while(x>=’0’&&x<=’9’)

{num=num+(ord(x)-ord(‘0’)/scale;

scale=scale*10; scanf(“%c”,&x); }

}//else

push(OPND,num); num=0.0;//数压入栈,下个数初始化

case x=‘’:break; //遇空格,继续读下一个字符。

case x=‘+’:push(OPND,pop(OPND)+pop(OPND));break;

case x=‘-’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2-x1);break;

case x=‘*’:push(OPND,pop(OPND)*pop(OPND));break;

case x=‘/’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2/x1);break;

default: //其它符号不作处理。

}//结束switch

scanf(“%c”,&x);//读入表达式中下一个字符。

}//结束while(x!=‘$’)

printf(“后缀表达式的值为%f”,pop(OPND));

}//算法结束。

[算法讨论]假设输入的后缀表达式是正确的,未作错误检查。算法中拼数部分是核心。若遇到大于等于‘0’

且小于等于‘9’的字符,认为是数。这种字符的序号减去字符‘0’的序号得出数。对于整数,每读入一个数字字符,前面得到的部分数要乘上10再加新读入的数得到新的部分数。当读到小数点,认为数的整数部分已完,要接着处理小数部分。小数部分的数要除以10(或10的幂数)变成十分位,百分位,千分位数等等,与前面部分数相加。在拼数过程中,若遇非数字字符,表示数已拼完,将数压入栈中,并且将变量num恢复为0,准备下一个数。这时对新读入的字符进入‘+’、‘-’、‘*’、‘/’及空格的判断,因此在结束处理数字字符的case后,不能加入break 语句。

(5)假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空,入栈和出栈的操作序列可表示为仅由I 和O组成的序列,称可以操作的序列为合法序列,否则称为非法序列。

①下面所示的序列中哪些是合法的?

A. IOIIOIOO

B. IOOIOIIO

C. IIIOIOIO

D. IIIOOIOO

②通过对①的分析,写出一个算法,判定所给的操作序列是否合法。若合法,返回true,否则返回false(假定被判定的操作序列已存入一维数组中)。

①A和D是合法序列,B和C 是非法序列。

②设被判定的操作序列已存入一维数组A中。

int Judge(char A[])

//判断字符数组A中的输入输出序列是否是合法序列。如是,返回true,否则返回false。

{i=0; //i为下标。

j=k=0; //j和k分别为I和字母O的的个数。

while(A[i]!=‘\0’) //当未到字符数组尾就作。

{switch(A[i])

{case‘I’: j++; break; //入栈次数增1。

case‘O’: k++; if(k>j){printf(“序列非法\n”);exit(0);}

}

i++; //不论A[i]是‘I’或‘O’,指针i均后移。}

if(j!=k) {printf(“序列非法\n”);return(false);}

else{printf(“序列合法\n”);return(true);}

}//算法结束。

[算法讨论]在入栈出栈序列(即由‘I’和‘O’组成的字符串)的任一位置,入栈次数(‘I’的个数)都必须大于等于出栈次数(即‘O’的个数),否则视作非法序列,立即给出信息,退出算法。整个序列(即读到字符数组中字符串的结束标记‘\0’),入栈次数必须等于出栈次数(题目中要求栈的初态和终态都为空),否则视为非法序列。

(6)假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素站点(注意不设头指针) ,试编写相应的置空队、判队空、入队和出队等算法。

算法如下:

//先定义链队结构:

typedef struct queuenode{

Datatype data;

struct queuenode *next;

}QueueNode; //以上是结点类型的定义

typedef struct{

queuenode *rear;

}LinkQueue; //只设一个指向队尾元素的指针

(1)置空队

void InitQueue( LinkQueue *Q)

{ //置空队:就是使头结点成为队尾元素

QueueNode *s;

Q->rear = Q->rear->next;//将队尾指针指向头结点

while (Q->rear!=Q->rear->next)//当队列非空,将队中元素逐个出队{s=Q->rear->next;

Q->rear->next=s->next;

free(s);

}//回收结点空间

}

(2)判队空

int EmptyQueue( LinkQueue *Q)

{ //判队空

//当头结点的next指针指向自己时为空队

return Q->rear->next->next==Q->rear->next;

}

(3)入队

void EnQueue( LinkQueue *Q, Datatype x)

{ //入队

//也就是在尾结点处插入元素

QueueNode *p=(QueueNode *) malloc (sizeof(QueueNode));//申请新结点p->data=x; p->next=Q->rear->next;//初始化新结点并链入

Q-rear->next=p;

Q->rear=p;//将尾指针移至新结点

}

(4)出队

Datatype DeQueue( LinkQueue *Q)

{//出队,把头结点之后的元素摘下

Datatype t;

QueueNode *p;

if(EmptyQueue( Q ))

Error("Queue underflow");

p=Q->rear->next->next; //p指向将要摘下的结点

x=p->data; //保存结点中数据

if (p==Q->rear)

{//当队列中只有一个结点时,p结点出队后,要将队尾指针指向头结点

Q->rear = Q->rear->next; Q->rear->next=p->next;}

else

Q->rear->next->next=p->next;//摘下结点p

free(p);//释放被删结点

return x;

}

(7)假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag,以tag== 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时,队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。

【解答】

循环队列类定义

#include

template class Queue { //循环队列的类定义

public:

Queue (int=10 );

~Queue ( ) { delete [ ] Q;}

void EnQueue (Type& item );

Type DeQueue ();

Type GetFront ( );

void MakeEmpty ( ){ front = rear = tag = 0;}//置空队列

int IsEmpty ( )const{ return front == rear && tag == 0;}//判队列空否

int IsFull ( )const{ return front == rear && tag == 1;} //判队列满否

private:

int rear, front, tag; //队尾指针、队头指针和队满标志

Type *Q; //存放队列元素的数组

int m; //队列最大可容纳元素个数

}

构造函数

template

Queue:: Queue ( int sz ) : rear (0),front (0), tag(0), m (sz) {

//建立一个最大具有m个元素的空队列。

Q =new Type[m]; //创建队列空间

assert ( Q != 0 ); //断言:动态存储分配成功与否

}

插入函数

template

void Queue ::EnQueue ( Type &item) {

assert ( ! IsFull ( ) );//判队列是否不满,满则出错处理

rear = ( rear + 1 ) % m;//队尾位置进1, 队尾指针指示实际队尾位置

Q[rear] = item;//进队列

tag = 1;//标志改1,表示队列不空

}

删除函数

template

Type Queue ::DeQueue ( ) {

assert ( ! IsEmpty ( ) );//判断队列是否不空,空则出错处理

front =( front + 1 ) % m;//队头位置进1, 队头指针指示实际队头的前一位置

tag = 0;//标志改0, 表示栈不满

return Q[front]; //返回原队头元素的值

}

读取队头元素函数

template

Type Queue ::GetFront ( ) {

assert ( ! IsEmpty ( ) );//判断队列是否不空,空则出错处理

return Q[(front + 1) % m]; //返回队头元素的值

}

(8)如果允许在循环队列的两端都可以进行插入和删除操作。要求:

①写出循环队列的类型定义;

②写出“从队尾删除”和“从队头插入”的算法。

[题目分析] 用一维数组 v[0..M-1]实现循环队列,其中M是队列长度。设队头指针 front和队尾指针rear,约定front指向队头元素的前一位置,rear指向队尾元素。定义front=rear时为队空,(rear+1)%m=front 为队满。约定队头端入队向下标小的方向发展,队尾端入队向下标大的方向发展。

(1)#define M 队列可能达到的最大长度

typedef struct

{ elemtp data[M];

int front,rear;

} cycqueue;

(2)elemtp delqueue ( cycqueue Q)

//Q是如上定义的循环队列,本算法实现从队尾删除,若删除成功,返回被删除元素,否则给出出错信息。

{ if (Q.front==Q.rear) {p rintf(“队列空”); exit(0);}

Q.rear=(Q.rear-1+M)%M; //修改队尾指针。

return(Q.data[(Q.rear+1+M)%M]); //返回出队元素。

}//从队尾删除算法结束

void enqueue (cycqueue Q, elemtp x)

// Q是顺序存储的循环队列,本算法实现“从队头插入”元素x。

{if (Q.rear==(Q.front-1+M)%M) {printf(“队满”; exit(0);)

Q.data[Q.front]=x; //x 入队列

Q.front=(Q.front-1+M)%M; //修改队头指针。

}// 结束从队头插入算法。

(9)已知Ackermann函数定义如下:

①写出计算Ack(m,n)的递归算法,并根据此算法给出出Ack(2,1)的计算过程。

②写出计算Ack(m,n)的非递归算法。

int Ack(int m,n)

{if (m==0) return(n+1);

else if(m!=0&&n==0) return(Ack(m-1,1));

else return(Ack(m-1,Ack(m,m-1));

}//算法结束

(1)Ack(2,1)的计算过程

Ack(2,1)=Ack(1,Ack(2,0)) //因m<>0,n<>0而得

=Ack(1,Ack(1,1)) //因m<>0,n=0而得

=Ack(1,Ack(0,Ack(1,0))) // 因m<>0,n<>0而得

= Ack(1,Ack(0,Ack(0,1))) // 因m<>0,n=0而得

=Ack(1,Ack(0,2)) // 因m=0而得

=Ack(1,3) // 因m=0而得

=Ack(0,Ack(1,2)) //因m<>0,n<>0而得

= Ack(0,Ack(0,Ack(1,1))) //因m<>0,n<>0而得

= Ack(0,Ack(0,Ack(0,Ack(1,0)))) //因m<>0,n<>0而得

= Ack(0,Ack(0,Ack(0,Ack(0,1)))) //因m<>0,n=0而得

= Ack(0,Ack(0,Ack(0,2))) //因m=0而得

= Ack(0,Ack(0,3)) //因m=0而得

= Ack(0,4) //因n=0而得

=5 //因n=0而得

(2)int Ackerman( int m, int n)

{int akm[M][N];int i,j;

for(j=0;j

for(i=1;i

{akm[i][0]=akm[i-1][1];

for(j=1;j

akm[i][j]=akm[i-1][akm[i][j-1]];

}

return(akm[m][n]);

}//算法结束

(10)已知f为单链表的表头指针, 链表中存储的都是整型数据,试写出实现下列运算的递归算法:

①求链表中的最大整数;

②求链表的结点个数;

③求所有整数的平均值。

#include //定义在头文件"RecurveList.h"中

class List;

class ListNode {//链表结点类

friend class List;

private:

int data;//结点数据

ListNode *link;//结点指针

ListNode ( const int item ) : data(item), link(NULL) { }//构造函数

};

class List { //链表类

private:

ListNode *first, current;

int Max ( ListNode *f );

int Num ( ListNode *f );

float Avg ( ListNode *f, int&n );

public:

List ( ) : first(NULL), current (NULL) { }//构造函数

~List ( ){ }//析构函数

ListNode* NewNode ( const int item );//创建链表结点, 其值为item

void NewList ( const int retvalue );//建立链表, 以输入retvalue结束

void PrintList ( );//输出链表所有结点数据

int GetMax ( ) { return Max ( first ); }//求链表所有数据的最大值

int GetNum ( ) { return Num ( first ); }//求链表中数据个数

float GetAvg ( ) { return Avg ( first ); }//求链表所有数据的平均值

};

ListNode* List:: NewNode ( const int item ) {//创建新链表结点

ListNode *newnode = new ListNode (item);

return newnode;

}

void List::NewList ( const int retvalue ) {//建立链表, 以输入retvalue结束

first = NULL; int value;ListNode *q;

cout << "Input your data:\n"; //提示

cin >> value; //输入

while ( value != retvalue ) { //输入有效

q = NewNode ( value ); //建立包含value的新结点

if ( first == NULL ) first = current = q;//空表时, 新结点成为链表第一个结点

else {current->link = q;current = q; } //非空表时, 新结点链入链尾

cin >> value;//再输入

}

current->link = NULL; //链尾封闭

}

void List::PrintList ( ) {//输出链表

cout << "\nThe List is : \n";

ListNode *p = first;

while ( p != NULL ) { c out << p->data << ' '; p = p->link; }

cout << ‘\n’;

}

int List ::Max ( ListNode *f ) {//递归算法: 求链表中的最大值if ( f ->link == NULL ) return f ->data; //递归结束条件

int temp = Max ( f ->link );//在当前结点的后继链表中求最大值

if ( f ->data > temp ) return f ->data;//如果当前结点的值还要大, 返回当前检点值else return temp;//否则返回后继链表中的最大值

}

int List ::Num ( ListNode *f ) {//递归算法: 求链表中结点个数if ( f == NULL ) return 0;//空表, 返回0

return 1+ Num ( f ->link );//否则, 返回后继链表结点个数加1

}

float List :: Avg ( ListNode *f , int&n ) {//递归算法: 求链表中所有元素的平均值if ( f ->link == NULL ) //链表中只有一个结点, 递归结束条件{n = 1; return ( float ) (f ->data ); }

else { float Sum = Avg ( f ->link, n ) * n;n++;return ( f ->data + Sum ) / n; }

}

#include "RecurveList.h" //定义在主文件中

int main ( int argc, char* argv[ ] ) {

List test; int finished;

cout << “输入建表结束标志数据:”;

cin >> finished;//输入建表结束标志数据

test.NewList ( finished );//建立链表

test.PrintList ( );//打印链表

cout << "\nThe Max is : " << test.GetMax ( );

cout << "\nThe Num is : " << test.GetNum ( );

cout << "\nThe Ave is : " << test.GetAve () << '\n';

printf ( "Hello World!\n" );

return 0;

}

数据结构第三章栈和队列3习题

第三章栈和队列试题 一、单项选择题 1.栈的插入和删除操作在()进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 2.当利用大小为n的数组顺序存储一个栈时,假定用top==n表示栈空,则向这个栈插入一个元素时, 首先应执行()语句修改top指针。 A. top++; B. top--; C. top = 0; D. top; 3.若让元素1,2,3依次进栈,则出栈次序不可能出现()种情况。 A. 3, 2, 1 B. 2, 1, 3 C. 3, 1, 2 D. 1, 3, 2 4.在一个顺序存储的循环队列中,队头指针指向队头元素的()位置。 A. 前一个 B. 后一个 C. 当前 D. 后面 5.当利用大小为n的数组顺序存储一个队列时,该队列的最大长度为()。 A. n-2 B. n-1 C. n D. n+1 6.从一个顺序存储的循环队列中删除一个元素时,需要()。 A. 队头指针加一 B. 队头指针减一 C. 取出队头指针所指的元素 D. 取出队尾指针所指的元素 7.假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear,则判断队空的条件为()。 A. front+1 == rear B. rear+1 == front C. front == 0 D. front == rear 8.假定一个链式队列的队头和队尾指针分别为front和rear,则判断队空的条件为()。 A. front == rear B. front != NULL C. rear != NULL D. front == NULL 9.设链式栈中结点的结构为(data, link),且top是指向栈顶的指针。若想在链式栈的栈顶插入一 个由指针s所指的结点,则应执行操作()。 A. top->link = s; B.s->link = top->link; top->link = s; C. s->link = top; top = s; D. s->link = top; top = top->link; 10.设链式栈中结点的结构为(data, link),且top是指向栈顶的指针。若想摘除链式栈的栈顶结点, 并将被摘除结点的值保存到x中,则应执行操作()。 A. x = top->data; top = top->link; B. top = top->link; x = top->data; C. x = top; top = top->link; D. x = top->data; 11.设循环队列的结构是 #define MaxSize 100 typedef int ElemType;

数据结构考研真题 栈和队列

第3章栈和队列 一选择题 1. 对于栈操作数据的原则是()。【青岛大学 2001 五、2(2分)】 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 2. 在作进栈运算时,应先判别栈是否( ① ),在作退栈运算时应先判别栈是否( ② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。 为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时,才产生上溢。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶 D. 栈底 ⑤: A. 两个栈的栈顶同时到达栈空间的中心点. B. 其中一个栈的栈顶到达栈空间的中心点. C. 两个栈的栈顶在栈空间的某一位置相遇. D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底. 【上海海运学院 1997 二、1(5分)】【上海海运学院 1999 二、1(5分)】 3. 一个栈的输入序列为123…n,若输出序列的第一个元素是n,输出第i(1<=i<=n)个元素是()。 A. 不确定 B. n-i+1 C. i D. n-i 【中山大学 1999 一、9(1分)】 4. 若一个栈的输入序列为1,2,3,…,n,输出序列的第一个元素是i,则第j个输出元素是()。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 【武汉大学 2000 二、3】 5. 若已知一个栈的入栈序列是1,2,3,…,n,其输出序列为p 1,p 2 ,p 3 ,…,p N ,若p N 是n,则 p i 是( )。 A. i B. n-i C. n-i+1 D. 不确定 【南京理工大学 2001 一、1(1.5分)】 6. 有六个元素6,5,4,3,2,1 的顺序进栈,问下列哪一个不是合法的出栈序列?() A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 【北方交通大学 2001 一、3(2分)】 7. 设栈的输入序列是1,2,3,4,则()不可能是其出栈序列。【中科院计算所2000一、10(2分)】 A. 1,2,4,3, B. 2,1,3,4, C. 1,4,3,2, D. 4,3,1,2, E. 3,2,1,4, 8. 一个栈的输入序列为1 2 3 4 5,则下列序列中不可能是栈的输出序列的是()。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 【南开大学 2000 一、1】【山东大学 2001 二、4 (1分)】【北京理工大学 2000 一、2(2分)】 9. 设一个栈的输入序列是 1,2,3,4,5,则下列序列中,是栈的合法输出序列的是()。 A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4 【合肥工业大学 2001 一、1(2分)】 10. 某堆栈的输入序列为a, b,c ,d,下面的四个序列中,不可能是它的输出序列的是

第三章栈和队列习题_数据结构电子教案

习题三栈和队列 一单项选择题 1. 在作进栈运算时,应先判别栈是否(① ),在作退栈运算时应先判别栈是否(② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③ )。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 2.若已知一个栈的进栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,...,pn,若p1=3,则p2为( )。 A 可能是2 B 一定是2 C 可能是1 D 一定是1 3. 有六个元素6,5,4,3,2,1 的顺序进栈,问下列哪一个不是合法的出栈序列?() A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 4.设有一顺序栈S,元素s1,s2,s3,s4,s5,s6依次进栈,如果6个元素出栈的顺序是s2,s3,s4, s6, s5,s1,则栈的容量至少应该是() A.2 B. 3 C. 5 D.6 5. 若栈采用顺序存储方式存储,现两栈共享空间V[1..m],top[i]代表第i个栈( i =1,2)栈顶,栈1的底在v[1],栈2的底在V[m],则栈满的条件是()。 A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 6. 执行完下列语句段后,i值为:() int f(int x) { return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1)); A.2 B. 4 C. 8 D. 无限递归 7. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时,对象栈和算符栈为(),其中^为乘幂。 A. 3,2,4,1,1;(*^(+*- B. 3,2,8;(*^- C. 3,2,4,2,2;(*^(- D. 3,2,8;(*^(- 8. 用链接方式存储的队列,在进行删除运算时()。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 9. 递归过程或函数调用时,处理参数及返回地址,要用一种称为()的数据结构。 A.队列 B.多维数组 C.栈 D. 线性表 10.设C语言数组Data[m+1]作为循环队列SQ的存储空间, front为队头指针,rear为队尾指针,则执行出队操作的语句为() A.front=front+1 B. front=(front+1)% m C.rear=(rear+1)%(m+1) D. front=(front+1)%(m+1) 11.循环队列的队满条件为 ( ) A. (sq.rear+1) % maxsize ==(sq.front+1) % maxsize; B. (sq.front+1) % maxsize ==sq.rear C. (sq.rear+1) % maxsize ==sq.front D.sq.rear ==sq.front

栈和队列习题答案

第三章栈和队列习题答案 一、基础知识题 设将整数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 链栈中为何不设置头结点 答:链栈不需要在头部附加头结点,因为栈都是在头部进行操作的,如果加了头结点,等于要对头结点之后的结点进行操作,反而使算法更复杂,所以只要有链表的头指针就可以了。 循环队列的优点是什么如何判别它的空和满 答:循环队列的优点是:它可以克服顺序队列的"假上溢"现象,能够使存储队列的向量空间得到充分的利用。判别循环队列的"空"或"满"不能以头尾指针是否相等来确定,一般是通过以下几种方法:一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合,如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数,不仅可判别空或满,还可以得到队列中元素的个数。 设长度为n的链队用单循环链表表示,若设头指针,则入队出队操作的时间为何若只设尾指针呢答:当只设头指针时,出队的时间为1,而入队的时间需要n,因为每次入队均需从头指针开始查找,找到最后一个元素时方可进行入队操作。若只设尾指针,则出入队时间均为1。因为是循环链表,尾指针所指的下一个元素就是头指针所指元素,所以出队时不需要遍历整个队列。 指出下述程序段的功能是什么 (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]); } .. // 设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)程序段的功能是将一栈中的元素按反序重新排列,也就是原来在栈顶的元素放到栈底,栈底的

第三章栈和队列练习题

第三章栈和队列练习题 一、单项选择题 1.一个顺序栈一旦被声明,其占用空间的大小()。 A.已固定B.可以改变C.不能固定D.动态变化 2.链栈和顺序栈相比,有一个比较明显的缺点,即()。 A.插入操作更加方便B.通常不会出现栈满的情况 C.不会出现栈空的情况D.删除操作更加方便 3.用单链表表示的链式队列的队头在链表的()位置。 A.链头B.链尾C.链中D.任意位置 4.在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区,主机将要输出的数据依次写入缓冲区中,而打印机则从缓冲区中取出数据打印,该缓冲区应该是一个()结构。 A.堆栈B.队列C.数组D.先性表 5.若已知一个栈的入栈序列是1,2,3,…,30,其输出序列是p1,p2,p3,…p n,若p1=30,则p10为()。 A.11 B.20 C.19 D.21 6.循环队列A[m] 存放其元素,用front和rear分别表示队头及队尾,则循环队列满的条件是()。 A.(rear+1)%m=front B.rear =front+1 C.rear=front D.(rear+1)%m-1=front 7.在一个栈顶指针为top的链栈中,将一个p指针所指的结点入栈,应执行()。 A.top->next=p; B.p->next=top->next; top->next=p; C.p->next=top; top=p; D.p->next=top->next; top=top->next; 8.在一个栈顶指针为top的链栈中删除一个结点时,用x保存被删结点的值,则执行()。 A.x=top;top=top->next; B.x=top->data;

PTA第三章栈与队列练习题

1-1 通过对堆栈S操作:Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出得序列为:123。(2分) T F 作者: DS课程组 单位: 浙江大学 1-2 在用数组表示得循环队列中,front值一定小于等于rear值。(1分) T F 作者: DS课程组 单位: 浙江大学 1-3 若一个栈得输入序列为{1, 2, 3, 4, 5},则不可能得到{3, 4, 1, 2, 5}这样得出栈序列。(2分) T F 作者: 徐镜春 单位: 浙江大学 1-4 If keys are pushed onto a stack in the order {1, 2, 3, 4, 5}, then it is impossible to obtain the output sequence {3, 4, 1, 2, 5}、(2分) T F 作者: 徐镜春 单位: 浙江大学 1-5 所谓“循环队列”就是指用单向循环链表或者循环数组表示得队列。(1分) T F 作者: DS课程组 单位: 浙江大学 1-6 An algorithm to check for balancing symbols in an expression uses a stack to store the symbols、(1分) T F 2-1 设栈S与队列Q得初始状态均为空,元素a、b、c、d、e、f、g依次进入栈S。若每个元素出栈后立即进入队列Q,且7个元素出队得顺序就是b、d、c、f、e、 a、g,则栈S得容量至少就是: (2分) 1. 1 2. 2 3. 3 4. 4 作者: DS课程组

数据结构第3章栈和队列自测卷答案(供参考)

head 1. 向量、栈和队列都是 线性 结构,可以在向量的 任何 位置插入和删除元素;对于栈只能在 栈顶 插入和删除元素;对于队列只能在 队尾 插入和 队首 删除元素。 2. 栈是一种特殊的线性表,允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。 3. 队列 是被限定为只能在表的一端进行插入运算,在表的另一端进行删除运算的线性表。 4. 在一个循环队列中,队首指针指向队首元素的 前一个 位置。 5. 在具有n 个单元的循环队列中,队满时共有 n-1 个元素。 6. 向栈中压入元素的操作是先 移动栈顶指针 ,后 存入元素 。 7. 从循环队列中删除一个元素时,其操作是 先 移动队首指针 ,后 取出元素 。 8.带表头结点的空循环双向链表的长度等于 0 。 解: 二、判断正误(判断下列概念的正确性,并作出简要的说明。) (每小题1分,共10分) ( × )1. 线性表的每个结点只能是一个简单类型,而链表的每个结点可以是一个复杂类型。 错,线性表是逻辑结构概念,可以顺序存储或链式存储,与元素数据类型无关。 ( × )2. 在表结构中最常用的是线性表,栈和队列不太常用。 错,不一定吧?调用子程序或函数常用,CPU 中也用队列。 ( √ )3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表,是一种后进先出型结构。 ( √ )4. 对于不同的使用者,一个表结构既可以是栈,也可以是队列,也可以是线性表。 正确,都是线性逻辑结构,栈和队列其实是特殊的线性表,对运算的定义略有不同而已。 ( × )5. 栈和链表是两种不同的数据结构。 错,栈是逻辑结构的概念,是特殊殊线性表,而链表是存储结构概念,二者不是同类项。 ( × )6. 栈和队列是一种非线性数据结构。 错,他们都是线性逻辑结构,栈和队列其实是特殊的线性表,对运算的定义略有不同而已。 ( √ )7. 栈和队列的存储方式既可是顺序方式,也可是链接方式。 ( √ )8. 两个栈共享一片连续内存空间时,为提高内存利用率,减少溢出机会,应把两个栈的栈底 分别设在这片内存空间的两端。 ( × )9. 队是一种插入与删除操作分别在表的两端进行的线性表,是一种先进后出型结构。 错,后半句不对。 ( × )10. 一个栈的输入序列是12345,则栈的输出序列不可能是12345。 错,有可能。 三、单项选择题(每小题1分,共20分) ( B )1.栈中元素的进出原则是 A.先进先出 B.后进先出 C.栈空则进 D.栈满则出 ( C )2.若已知一个栈的入栈序列是1,2,3,…,n ,其输出序列为p1,p2,p3,…,pn ,若p1=n ,则pi 为 A.i B.n=i C.n-i+1 D.不确定 解释:当p1=n ,即n 是最先出栈的,根据栈的原理,n 必定是最后入栈的(事实上题目已经表明了),那么输入顺序必定是1,2,3,…,n ,则出栈的序列是n ,…,3,2,1。 (若不要求顺序出栈,则输出序列不确定) ( B )3.判定一个栈ST (最多元素为m0)为空的条件是

数据结构第3章栈和队列自测卷答案

head 第3章 栈和队列 自测卷答案 班级 一、填空题(每空1分,共15分) 1. 向量、栈和队列都是 线性 结构,可以在向量的 任何 位置插入和删除元素;对于栈只能在 栈顶 插入和删除元素;对于队列只能在 队尾 插入和 队首 删除元素。 2. 栈是一种特殊的线性表,允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。 3. 队列 是被限定为只能在表的一端进行插入运算,在表的另一端进行删除运算的线性表。 4. 在一个循环队列中,队首指针指向队首元素的 前一个 位置。 5. 在具有n 个单元的循环队列中,队满时共有 n-1 个元素。 6. 向栈中压入元素的操作是先 移动栈顶指针 ,后 存入元素 。 7. 从循环队列中删除一个元素时,其操作是 先 移动队首指针 ,后 取出元素 。 8.带表头结点的空循环双向链表的长度等于 0 。 解: 二、判断正误(判断下列概念的正确性,并作出简要的说明。)(每小题1分,共10分) ( × )1. 线性表的每个结点只能是一个简单类型,而链表的每个结点可以是一个复杂类型。 错,线性表是逻辑结构概念,可以顺序存储或链式存储,与元素数据类型无关。 ( × )2. 在表结构中最常用的是线性表,栈和队列不太常用。 错,不一定吧?调用子程序或函数常用,CPU 中也用队列。 ( √ )3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表,是一种后进先出型结构。 ( √ )4. 对于不同的使用者,一个表结构既可以是栈,也可以是队列,也可以是线性表。 正确,都是线性逻辑结构,栈和队列其实是特殊的线性表,对运算的定义略有不同而已。 ( × )5. 栈和链表是两种不同的数据结构。 错,栈是逻辑结构的概念,是特殊殊线性表,而链表是存储结构概念,二者不是同类项。 ( × )6. 栈和队列是一种非线性数据结构。 错,他们都是线性逻辑结构,栈和队列其实是特殊的线性表,对运算的定义略有不同而已。 ( √ )7. 栈和队列的存储方式既可是顺序方式,也可是方式。 ( √ )8. 两个栈共享一片连续存空间时,为提高存利用率,减少溢出机会,应把两个栈的栈底分别 设在这片存空间的两端。 ( × )9. 队是一种插入与删除操作分别在表的两端进行的线性表,是一种先进后出型结构。 错,后半句不对。 ( × )10. 一个栈的输入序列是12345,则栈的输出序列不可能是12345。 错,有可能。 三、单项选择题(每小题1分,共20分) ( B )1.栈中元素的进出原则是 A.先进先出 B.后进先出 C.栈空则进 D.栈满则出 ( C )2.若已知一个栈的入栈序列是1,2,3,…,n ,其输出序列为p1,p2,p3,…,pn ,若p1=n ,

第3章-栈与队列习题参考答案

习题三参考答案 备注: 红色字体标明的是与书本内容有改动的内容。 一、选择题 1.在栈中存取数据的原则是( B )。 A.先进先出 B. 先进后出 C. 后进后出 D. 没有限制 2.若将整数1、2、3、4依次进栈,则不可能得到的出栈序列是( D )。 A.1234 B. 1324 C. 4321 D. 1423 3.在链栈中,进行出栈操作时(B )。 A.需要判断栈是否满 B. 需要判断栈是否为空 C. 需要判断栈元素的类型 D. 无需对栈作任何差别 4.在顺序栈中,若栈顶指针top指向栈顶元素的下一个存储单元,且顺序栈的最大容量是maxSize,则顺序栈的判空条件是( A )。 A.top==0 B.top==-1 C. top==maxSize D.top==maxSize-1 5.在顺序栈中,若栈顶指针top指向栈顶元素的下一个存储单元,且顺序栈的最大容量是maxSize。则顺序栈的判满的条件是( C )。 A.top==0 B.top==-1 C. top==maxSize D.top==maxSize-1 6.在队列中存取数据元素的原则是( A )。 A.先进先出 B. 先进后出 C. 后进后出 D. 没有限制 7.在循环顺序队列中,假设以少用一个存储单元的方法来区分队列判满和判空的条件,front和rear分别为队首和队尾指针,它们分别指向队首元素和队尾元素的下一个存储单元,队列的最大存储容量为maxSize,则队列的判空条件是(A )。 A.front==rear B. front!=rear C. front==rear+1 D. front==(rear+1)% maxSize 8.在循环顺序队列中,假设以少用一个存储单元的方法来区分队列判满和判空的条件,front和rear分别为队首和队尾指针,它们分别指向队首元素和队尾元素的下一个存储单元,队列的最大存储容量为maxSize,则队列的判满条件是(D )。 A.front==rear B. front!=rear C. front==rear+1 D. front==(rear+1)% maxSize 9.在循环顺序队列中,假设以少用一个存储单元的方法来区分队列判满和判空的条件,front和rear分别为队首 和队尾指针,它们分别指向队首元素和队尾元素的下一个存储单元,队列的最大存储容量为maxSize,则队列的长度是(C )。 A.rear-front B. rear-front+1 C. (rear-front+maxSize)%maxSize D. (rear-front+1)%maxSize 10.设长度为n的链队列采用单循环链表加以表示,若只设一个头指针指向队首元素,则入队操作的时间复杂度 为( B )。 A.O(1) B.O(n) C.O(log2n) D.O(n2) 二、填空题 1.栈是一种操作受限的特殊线性表,其特殊性体现在其插入和删除操作都限制在表尾进行。允许插入和删除 操作的一端称为栈顶,而另一端称为栈底。栈具有后进先出的特点。 2.栈也有两种存储结构,一种是顺序存储,另一种是链式存储;以这两种存储结构存储的栈分别称为顺序 栈和链栈。 3.在顺序栈中,假设栈顶指针top是指向栈顶元素的下一个存储单元,则顺序栈判空的条件是 top==0 ; 栈顶

第三章+栈和队列(参考答案)

第三章栈和队列 一、判断题 1、链栈的初始化是指开辟足够多的结点,然后置栈顶指针为 NULL。(×) 2、递归定义的数据结构通常不需要用递归的算法来实现对它的操作。(×) 二、填空题 1、向一个链式栈插入一个新结点时,首先把栈顶指针的值赋给新结点的指针域,然后把新结点的存储位置赋给___栈顶指针_____。 2、迷宫问题是一个回溯控制的问题,最好使用____栈______的方法来解决。 3、有如下递归过程: Void Print(int w) { int i; if (w!=0) { Print(w?1); for (i=1;i<=w;i++) printf(“%3d”,w); printf(“\n”); } } 调用语句print(4)的结果是__________。 1 2 2 3 3 3 4 4 4 4 4、假设用循环单链表实现队列,若队列非空,且队尾指针为R, 则将新结点S加入队列时,需执行下面语句:_ S->next=R->next _________;___ R->next=S _______;R=S; 三、选择题 1、设有4个数据元素a1、a 2、a3和a4,对他们分别进行栈操作或队操作。在进栈或进队操作时,按a1、a2、a 3、a4次序每次进入一个元素。假设栈或队的初始状态都是空。 现要进行的栈操作是进栈两次,出栈一次,再进栈两次,出栈一次;这时,第一次出栈得到的元素是 A 2,第二次出栈得到的元素是 B 4;类似地,考虑对这四个数据元素进行的队操作是进队两次,出队一次,再进队两次,出队一次;这时,第一次出队得到的元素是 C 1,第二次出队得到的元素是 D 2。经操作后,最后在栈中或队中的元素还有 E 2个。 供选择的答案: A~D:①a1 ②a2 ③ a3 ④a4 E:①1 ②2 ③ 3 ④ 0 2、栈是一种线性表,它的特点是 A 2。设用一维数组A[1,…,n]来表示一个栈,A[n]为栈底,用整型变量T指示当前栈顶位置,A[T]为栈顶元素。往栈中推入(PUSH)一个新元素时,变量T的值 B 2;从栈中弹出(POP)一个元素时,变量T的值 C 1。设栈空时,有输入序列a,b,c,经过PUSH,POP,PUSH,PUSH,POP操作后,从栈中弹出的元素的序列是 D 6,变量T的值是 E 4。 供选择的答案: A:①先进先出②后进先出③进优于出④出优于进⑤随机进出 B,C:①加1 ②减1 ③不变④清⑤加2 ⑥减2 D:① a,b ②b,c ③c,a ④b,a ⑤ c,b ⑥a,c E:① n+1 ②n+2 ③ n ④ n-1 ⑤ n-2 3、在做进栈运算时,应先判别栈是否 A 2;在做退栈运算时,应先判别栈是否 B 1。当栈中元素为n个,做进栈运算时发生上溢,则说明该栈的最大容量为 C 2。

PTA第三章栈和队列练习题教学提纲

1-1 通过对堆栈S 操作:Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为:123。 (2分) T F 作者: DS 课程组 单位: 浙江大学 1-2 在用数组表示的循环队列中,front 值一定小于等于rear 值。 (1分) T F 作者: DS 课程组 单位: 浙江大学 1-3 若一个栈的输入序列为{1, 2, 3, 4, 5},则不可能得到{3, 4, 1, 2, 5}这样的出栈序列。 (2分) T F 作者: 徐镜春 单位: 浙江大学 1-4 If keys are pushed onto a stack in the order {1, 2, 3, 4, 5}, then it is impossible to obtain the output sequence {3, 4, 1, 2, 5}. (2分) T F 作者: 徐镜春 单位: 浙江大学 1-5 所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。 (1分) T F 作者: DS 课程组 单位: 浙江大学 1-6 An algorithm to check for balancing symbols in an expression uses a stack to store the symbols. (1分) T F 2-1 设栈S 和队列Q 的初始状态均为空,元素a 、b 、c 、d 、e 、f 、g 依次进入栈S 。若每个元素出栈后立即进入队列Q ,且7个元素出队的顺序是b 、d 、c 、f 、e 、a 、g ,则栈S 的容量至少是: (2分)

栈和队列练习题答案

第3章栈和队列练习题答案 一、填空题 1. 线性表、栈和队列都是线性结构,可以在线性表的任何位置插入和删除元素;对于栈只能在栈顶插入和删除元素;对于队列只能在队尾插入和队首删除元素。 2. 栈是一种特殊的线性表,允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。 3. 队列是被限定为只能在表的一端进行插入运算,在表的另一端进行删除运算的线性表。 二、判断正误 (√)1. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表,是一种后进先出型结构。(√)2. 对于不同的使用者,一个表结构既可以是栈,也可以是队列,也可以是线性表。 正确,都是线性逻辑结构,栈和队列其实是特殊的线性表,对运算的定义略有不同而已。 (×)3. 栈和队列是一种非线性数据结构。 错,他们都是线性逻辑结构,栈和队列其实是特殊的线性表,对运算的定义略有不同而已。 (√)4. 栈和队列的存储方式既可是顺序方式,也可是链接方式。 (√)5. 两个栈共享一片连续内存空间时,为提高内存利用率,减少溢出机会,应把两个栈的栈底分别设在这片内存空间的两端。 (×)6. 队是一种插入与删除操作分别在表的两端进行的线性表,是一种先进后出型结构。 错,后半句不对。 (×)7. 一个栈的输入序列是12345,则栈的输出序列不可能是12345。 错,有可能。 三、单项选择题 (B)1.栈中元素的进出原则是 A.先进先出B.后进先出C.栈空则进D.栈满则出 (C)2.若已知一个栈的入栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,…,pn,若p1=n,则pi为 A.i B.n-i C.n-i+1 D.不确定 解释:当p1=n,即n是最先出栈的,根据栈的原理,n必定是最后入栈的(事实上题目已经表明了),那么输入顺序必定是1,2,3,…,n,则出栈的序列是n,…,3,2,1。 (若不要求顺序出栈,则输出序列不确定) (D)3.数组Q[n]用来表示一个循环队列,f为当前队列头元素的前一位置,r为队尾元素的位置,假定队列中元素的个数小于n,计算队列中元素的公式为 (A)r-f; (B)(n+f-r)% n; (C)n+r-f; (D)(n+r-f)% n E:①1 ②2 ③3 ④0 四、阅读理解 1.【严题集3.3②】写出下列程序段的输出结果(栈的元素类型SElem Type为char)。 void main( ){ Stack S; Char x,y; InitStack(S); x=’c’;y=’k’;

第三章栈与队列 练习题

第三章栈与队列练习题 一、选择题 1、栈结构通常采用的两种存储结构是( A )。 A、顺序存储结构和链表存储结构 B、散列和索引 C、链表存储结构和数组 D、线性链表和非线性存储 2、设栈ST用顺序存储结构表示,则栈ST为空的条件是(B) A、ST.top-ST.base<>0 B、ST.top-ST.base==0 C、ST.top-ST.base<>n D、ST.top-ST.base==n 3、向一个栈顶指针为HS的链栈中插入一个s结点时,则执行() A、HS->next=s; B、s->next=HS->next;HS->next=s; C、s->next=HS;HS=s; D、s->next=HS;HS=HS->next; 4、从一个栈顶指针为HS的链栈中删除一个结点,用x保存被删除结点的值,则执行(C) A、x=HS;HS=HS->next; B、HS=HS->next;x=HS->data; C、 x=HS->data;HS=HS->next; D、s->next=Hs;Hs=HS->next; 7、一个队列的入列序列是1,2,3,4,则队列的输出序列是(B )//尾插入元素,头删除元素。 A、4,3,2,1 B、1,2,3,4 C、1,4,3,2 D、3,2,4,1 9、循环队列SQ采用数组空间SQ.base[0,n-1]存放其元素值,已知其头尾指针分别是front和rear,则判定此循环队列为满的条件是(C)//不懂啊!!! A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 11、用单链表表示的链式队列的队头在链表的(A)位置 A、链头 B、链尾 C、链中 12、判定一个链队列Q(最多元素为n个)为空的条件是( A) A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 14、在一个链队列Q中,删除一个结点需要执行的指令是(C) A、Q.rear=Q.front->next; B、Q.rear->next=Q.rear->next->next; C、 Q.front->next=Q.front->next->next; D、Q.front=Q.rear->next; 15、用不带头结点的单链表存储队列,其队头指针指向队头结点,队尾指针指向队尾结点,则在进行出队操作时(D) A、仅修改队头指针 B、仅修改队尾指针 C、队头尾指针都要修改 D、队头尾指针都可能要修改。 16、栈和队列的共同点是(C) A、都是先进后出 B、都是先进先出 C、只允许在端点处插入和删除元素 D、没有共同点 18、设有一顺序栈S,元素s1,s2,s3,s4,s5,s6依次进栈,如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是(B) A、2 B、 3 C、 5 D、 6 20、设有一顺序栈已经含有3个元素,如图3.1所示元素a4正等待进栈。下列不可能出现的出栈序列是(A) 0 maxsize-1

数据结构第3章栈与队列习题

第3章栈与队列 一、单项选择题 1.元素A、B、C、D依次进顺序栈后,栈顶元素是,栈底元素是。 A.A B.B C.C D.D 2.经过以下栈运算后,x的值是。 InitStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s,x); A.a B.b C.1 D.0 3.已知一个栈的进栈序列是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 4.设一个栈的输入序列为A、B、C、D,则借助一个栈所得到的序列是。 A.A,B,C,D B.D,C,B,A C.A,C,D,B D.D,A,B,C 5.一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是。 A.edcba B.decba C.dceab D.abcde 6.已知一个栈的进栈序列是1,2,3,……,n,其输出序列的第一个元素是i,则第j个出栈元素是。 A.i B.n-i C.j-i+1 D.不确定 7.已知一个栈的进栈序列是1,2,3,……,n,其输出序列是p1,p2,…,Pn,若p1=n,则pi的值。 A.i B.n-i C.n-i+1 D.不确定 8.设n个元素进栈序列是1,2,3,……,n,其输出序列是p1,p2,…,p n,若p1=3,则p2的值。 A.一定是2 B.一定是1

C.不可能是1 D.以上都不对 9.设n个元素进栈序列是p1,p2,…,p n,其输出序列是1,2,3,……,n,若p3=1,则p1的值。 A.可能是2 B.一定是1 C.不可能是2 D.不可能是3 10.设n个元素进栈序列是p1,p2,…,p n,其输出序列是1,2,3,……,n,若p3=3,则p1的值。 A.可能是2 B.一定是2 C.不可能是1 D.一定是1 11.设n个元素进栈序列是p1,p2,…,p n,其输出序列是1,2,3,……,n,若p n=1,则p i(1≤i≤n-1)的值。 A.n-i+1 B.n-i C.i D.有多种可能 12.判定一个顺序栈S为空的条件为。 A.S.top= =S.base B.S.top!= S.base C.S.top!= S.base+S.stacksize D.S.top= = S.base+S.stacksize 13.判定一个顺序栈S为栈满的条件是。 A.S.top-S.base= =S.stacksize B.S.top= = S.base C.S.top-S.base!=S.stacksize D.S.top!= S.base 14.链栈与顺序栈相比有一个明显的优点,即。 A.插入操作方便B.通常不会出现栈满的情况 C.不会出现栈空的情况D.删除操作更加方便 15.最不适合用作链栈的链表是。 A.只有表头指针没有表尾指针的循环双链表 B.只有表尾指针没有表头指针的循环双链表 C.只有表尾指针没有表头指针的循环单链表 D.只有表头指针没有表尾指针的循环单链表 16.如果以链表作为栈的存储结构,则退链栈操作时。 A.必须判别链栈是否满B.判别链栈元素的类型 C.必须判别链栈是否空D.对链栈不作任何判别

数据结构-第3章栈和队列自测卷答案

head 第3章 栈和队列 自测卷答案 姓名 班级 一、填空题(每空1分,共15分) 1. 向量、栈和队列都是 线性 结构,可以在向量的 任何 位置插入和删除元素;对于栈只能在 栈顶 插入和删除元素;对于队列只能在 队尾 插入和 队首 删除元素。 2. 栈是一种特殊的线性表,允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。 3. 队列 是被限定为只能在表的一端进行插入运算,在表的另一端进行删除运算的线性表。 4. 在一个循环队列中,队首指针指向队首元素的 前一个 位置。 5. 在具有n 个单元的循环队列中,队满时共有 n-1 个元素。 6. 向栈中压入元素的操作是先 移动栈顶指针 ,后 存入元素 。 7. 从循环队列中删除一个元素时,其操作是 先 移动队首指针 ,后 取出元素 。 8.带表头结点的空循环双向链表的长度等于 0 。 解: 二、判断正误(判断下列概念的正确性,并作出简要的说明。)(每小题1分,共10分) ( × )1. 线性表的每个结点只能是一个简单类型,而链表的每个结点可以是一个复杂类型。 错,线性表是逻辑结构概念,可以顺序存储或链式存储,与元素数据类型无关。 ( × )2. 在表结构中最常用的是线性表,栈和队列不太常用。 错,不一定吧?调用子程序或函数常用,CPU 中也用队列。 ( √ )3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表,是一种后进先出型结构。 ( √ )4. 对于不同的使用者,一个表结构既可以是栈,也可以是队列,也可以是线性表。 正确,都是线性逻辑结构,栈和队列其实是特殊的线性表,对运算的定义略有不同而已。 ( × )5. 栈和链表是两种不同的数据结构。 错,栈是逻辑结构的概念,是特殊殊线性表,而链表是存储结构概念,二者不是同类项。 ( × )6. 栈和队列是一种非线性数据结构。 错,他们都是线性逻辑结构,栈和队列其实是特殊的线性表,对运算的定义略有不同而已。 ( √ )7. 栈和队列的存储方式既可是顺序方式,也可是链接方式。 ( √ )8. 两个栈共享一片连续内存空间时,为提高内存利用率,减少溢出机会,应把两个栈的栈底 分别设在这片内存空间的两端。 ( × )9. 队是一种插入与删除操作分别在表的两端进行的线性表,是一种先进后出型结构。 错,后半句不对。 ( × )10. 一个栈的输入序列是12345,则栈的输出序列不可能是12345。 错,有可能。 三、单项选择题(每小题1分,共20分)

第三章 栈与队列 习题及答案(优选.)

第三章栈与队列习题及答案 一、基础知识题 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); }

相关文档
相关文档 最新文档