当前位置:首页 » 数据结构练习题 » 正文

数据结构-栈和队列练习题

4714 人参与  2018年09月10日 21:42  分类 : 数据结构练习题  评论

1. 判断题

l)栈是运算受限制的线性表。 

2)在栈空的情况下,不能作出栈操作,否则产生溢出。 

3)栈一定是顺序存储的线性结构。

参考答案: (1) √     (2)√    (3)×   

2. 选择题

(l)设入栈序列是 1 2 、 … 、 n ,入栈过程中不允许中途出栈,则第 i 个输出的元素是 (   )。

A.不确定             B.i                  C. n - i              D. n - i + 1

(2)铁路调度用“栈”,假设进栈车厢编队序列为“ ABC " (进栈过程中可以出栈),出栈则有许多编队序列,以下不可能出现的序列是(  )。

A. " ABC "             B. " CBA "            C. " BAC "          D. " CAB "

(3)当栈中当前元素为 n 个,此时进行进栈运算时发生上溢,则该栈的最大、容量为(  )。

A. n/2                 B. n - 1               C. n                D. n + 1

(4)在栈中存取数据的原则是(  )。

A.先进先出           B.后进先出         C.后进后出        D.随意进出

 (5)插入和删除只能在一端进行的线性表,称为(  )。

A.队列               B.循环队列         C.栈              D. 循环栈

 (6栈结构通常采用的两种存储结构是(   

A线性存储结构和链式存储结构       B散列方式和索引方式    

C链式存储结构和数组               D.线性存储结构和非线性存储结构

 参考答案:D     D     C      B     C     C    

3. 简述利用两个栈模拟一个队列的入队、出对、判断队空等运算。

答:利用两个栈模拟一个队列的运算的基本思想是:

用一个栈S1作为输入栈,而另一个栈S2作为输出栈。

当入队时,总是将数据加入到作为输入的栈(即S1)中;

在输出时,如果输出栈S2已空,则从输入栈S1将以输入到输入栈中的数据输入到输出栈S2中,然后由输出栈S2输出数据,如果输出栈S2不为空,则就应由输出栈S2直接输出数据元素。

显然,当S1S2均为空时,表示队列为空

4. 若已知一个栈的入栈序列是1234n ,其输出序列是P1P2P3Pn,若P1=n,则Pi为多少?

P1=n,即n是最先出栈的,根据栈的原理,n必定是最后入栈的,那么输入顺序必定是1234n,则出栈的序列是n 4321,所以Pi = n-i+1

5. 对于一个栈,给出输入项ABC。如果输入项序列由ABC组成,试给出全部可能的输出序列。

本题利用栈的后进先出的特点,有如下几种情况:

AABBCC出产生输出序列ABC

AABCCB出产生输出序列ACB

ABBACC出产生输出序列BAC

ABBCCA出产生输出序列BCA

ABCCBA出产生输出序列CBA

不可能产生输出序列CBA

6. 利用栈的基本操作,写一个将栈S中所有结点均删除的算法void ClearStack (SeqStack*S),并说明S为何要作为指针参数?

要将栈S中所有结点均删除,可以利用栈的基本操作Pop(出栈)运算来实现,从栈顶元素开始,不断执行出栈运算,直到栈为空为止。实现本题功能的算法如下:

    voidClearStack (SeqStack*S)    
    {
        while (!StackEmpty (*S) )Pop (*S );
    }

说明:根据C语言的特征,函数形参为指针变量,可以将该形参在函数体内所修改的值返回给实参。根据题意,栈S在执行完该函数后,其结点已全部删除,内容已发生修改,故,S要作为指针参数。 

7. 利用栈的基本操作,写一个返回栈中结点个数的算法int  StackSize (SeqStackS),并说明S为何不用作为指针参数?

根据题意,设一变量count来统计栈中结点的个数,从栈顶元素出发,循环执行出栈运算,直到栈空。实现本题功能的函数如下:

    intStackSize (SeqStackS)    
    {
    intcount=0;
    while (!StackEmpty (S)) 
    {
    conut++;
    Pop (s);
    }
    }

说明:依据题意,该算法只需统计栈中结点个数,执行完函数后不能修改实参栈的内容。所以,在该函数中,S不能用作指针参数。

8. 如果用一个循环数组qu[0m0-1]表示队列时,该队列只有一个头指针front,不设队尾指针rear,而改置计数器count用以记录队列中结点的个数。

1)编写实现队列的五个基本运算;

2)队列中能容纳元素的最多个数还是m0-1吗?

解:

1)依题意,有如下条件:

队列为空:count==0front==1

队列为满:count==m0

队列尾的第一个元素位置==front+count% m0

队列首的第一个元素位置==front+1% m0

队列类型定义如下:

typedef int qu[m0]

由此得到如下对应上述基本运算的5个函数如下:

    /* m0定义为全局变量 */    
    void makenull(front,count) /*使队列q为空*/
    int front,count;
    {   front=1;
    count=0;
    }
    int empty(count) /*判定队列q是否为空*/
    int count;
    {   if(count==0)return(1);
    else return(0);
    }
    void pop(q,front,count,x) /*取队列头元素给x*/
    qu q;
    int front,count;
    ElemType *x;
    {   if(count==0)printf(”队列下溢出\n”);
    else
    {   front=(front+1)% m0;
    *x=q[front];
    }
    }
    void enqueue(q,x,front,count)/*将元素x入队列*/
    qu q;
    int front,count;
    ElemType x;
    {   int place;
    if(count==0)printf(”队列上溢出\n”);
    else
    {   count++;
    place=(front+count)% m0;
    }
    }
    void dequeue(q,front,count)/*删除队列头元素*/
    qu q;
    int front,count;
    {  if(count==0)printf(”队列下溢出\n”);
    else
    {  front=(front+1)% m0;
    count--;
    }
    }

2)队列中可容纳的最多元素个数为m0个。

来源:我是码农,转载请保留出处和链接!

本文链接:http://www.54manong.com/?id=352

数据结构  

微信号:qq444848023    QQ号:444848023

加入【我是码农】QQ群:864689844(加群验证:我是码农)

<< 上一篇 下一篇 >>

网站分类

标签列表

最近发表

全站首页 | 数据结构 | 区块链| 大数据 | 机器学习 | 物联网和云计算 | 面试笔试

本站资源大部分来自互联网,版权归原作者所有!