堆栈、队列和字符串
作业3
一、单项选择题
1．用单链表表示的链式队列的队头在链表的（  　）位置。（北方名校经典试题）
A）链头            B）链尾                C）链中                D）任意
【分析】队列的队头是对队列元素进行删除的一端。对于链队列在链头处进行删除，所以队头在链表的链头位置（不考虑不包含数据元素的头结点）
【答案：A】
2．栈应用的典型事例是（  　）。
A）排队        B）查    C）归并        D）用“算符优先法”进行表达式求值
【分析】排队、归并与查一般都不用栈，而用“算符优先法”进行表达式求值必须用栈，是栈
的典型应用。
【答案：B】
3．若用单链表来表示队列，则应该选用（  　）。（北方名校经典试题）
A）带尾指针的非循环链表                B）带尾指针的循环链表
C）带头指针的非循环链表                D）带头指针的循环链表 
【分析】设尾指针为Tail，对于循环链表，tail->next为队头，所以应选用带尾指什的循环链表。
【答案：B】
4．设有循环队列cq，结构定义如下：
#define MAXQSIZE 100        //最大队列长度
typedef struct QNode{
      ElemType  *base;        //初始化的动态分配空间
      int front;                //头指针，如队列不空，指向队列头元素
      int rear;                //尾指针，如队列不空，指向队列尾元素的下一个位置
}SqQueue;
SqQueue:cq;
则当一个元素入队时指针变化为（  　）。
A）cq.rear= cq.rear+1                B）cq.rear=(cq.rear+1) % MAXQSIZE
C）cq.front= cq.front+1                D）cq.front=(cq.front+1) % MAXQSIZE
【分析】队列入队时，元素应追加在队尾，也应是队尾发生变化，由于是循环队列，可知应在同余意义下取值。
【答案：B】
5．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，这样主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应该是一个（  　）结构。（北方名校经典试题）
A）堆栈            B）队列            C）数组            D）线性表 
【分析】打印任务最好采用先来先服务，也就是说缓冲区此时实际上是一个等待打印队列。
【答案：B】
6．设有循环队列cq，类型描述如上题，已知MAXQSIZE=18，cq.front=12，cq.rear=14，在连续执行了3次入队，2次出队，3次入队操作之后，（cq.ar）的值应为（  　）。
A）（13,0）        B）（14,2）        C）（13,17）        D）（14,17）
【分析】入队时，队尾发生变化，出队时，队头发生变化，可知连续执行了3次入队后，（cq.ar）的值为（12,17）；连续执行2次出队后，（cq.ar）的值为（14,17）；连续执行了3次入队后，（cq.ar）的值为（14,2）。
【答案：B】
7．设一个栈的入栈序列是ABCD，则借助于一个栈所得到的出栈序列不可能是（  　）。
A）ABCD        B）DCBA        C）ACDB        D）DABC
【分析】由于栈的入栈与出栈操作都在栈顶进行，在答案D中D最先出栈，此时从栈顶到栈底的元素分别为D、C、B、A，可知出栈序列应为DCBA，而不可能为DABC，所以本题应选择D。
【答案：D】
8．设栈最大长度为3，入栈序列为1、2、3、4、5、6，则不可能的出栈序列是（  　）。
A）1、2、3、4、5、6                B）2、1、3、4、5、6
C）3、4、2、1、5、6                D）4、3、2、1、5、6
【分析】由于栈的入栈和出栈操作都在栈顶进行，在答案D中首先出栈的元素为4，此时栈从栈底到栈顶的元素依次为1，2，3，4，这样要求栈长度至少为4，已超过材的最大长度。
【答案：D】
9．设TOP为链栈的栈顶指针，则空栈的条件是（  　）。
A）n==0        B）TOP->next==0        C）TOP==NULL    D）TOP->next==NULL
【分析】由于链栈不设立头结点，所以空链栈的条件是TOP==NULL。
【答案：C】
10．一般情况下，将递归算法转换成等价的非递归算法应该设置（  　）。（北方名校经典试题）
A）栈            B）队列            C）堆栈或队列        D）数组
【分析】栈的用途之一就是将递归转换为非递归。
【答案：A】
11．设栈的输入序列是1，2，…，n，若输出序列的第一个元素是n，则第i个输出元素是（ 
　）。
A）n-i+1            B）i                C）n-i                D）前面都不正确
【分析】由栈的特点可知出栈序列应为：n，n-1，…，2，1。
【答案：A】
12．设S为一个长度为 n的字符串，其中的字符各不相同，则 S中的互异的非平凡子串（非空且不同于S本身）的个数为（  　）。（南方名校经典试题）
            A）            B）              C）            D）
【分析】非平凡子串中长度为1的子串个数为n；
非平凡子串中长度为2的子串个数为n-1；
……
非平凡子串中长度为n-1的子串个数为2；
所以非平凡子中总数为：
【答案：D】
二、综合题
1．有 5个元素，其入栈次序为：A、B、C、D、E，在各种可能的出栈次序中，以元素C第一个出栈，D第二个出栈的次序有哪几个？（南方名校经典试题）
【解答】按照栈的特点可知以元素C第一个出栈，D第二个出栈的次序有CDEBA 、CDBAE 和CDBEA 3种。
2．已知一个栈S的输入序列为abcd，下面两个序列能否通过栈的Push和Pop操作输出；如果能，请写出操作序列；如果不能，清说明原因。（东部名校经典试题）
（1）dbca
（2）cbda
【解答】
（1）不能实现，由于最先d出栈，要求abcd先入栈，由栈的特点，出栈序列最能为dcba。
（2）可以实现，操作序列为：
入栈，入栈，入栈，出栈，出栈，入栈，出栈，出栈。
3．已知Ackerman函数定义如下：
（1）写出递归算法；
*（2）写出非递归算法。
注：（2）较难，选做。
【解答】
（1）递归算法的主体一般格式如下：
if(<递归条件>)
        <递归调用语句>;
[else
        <递归结束语句>;]
或
if(<递归结束条件>)
        <递归结束语句>;
else
        <递归调用语句>;
本题的条件比较多，但本质是一样。字符串常量池在堆中吗
测试程序见3_2_3_1，具体算法如下：
long Akm(int m,int n)
//    Ackerman函数的递归算法
{
        if(m==0)                        //条件m==0成立
            return n+1;
    else if(n==0)                    //条件m!=0且n==0成立
            return Akm(m-1,1);
        else                            //条件m!=0且n!=0成立
            return Akm(m-1,Akm(m,n-1));
}
（2）用一个数组A[0:M-1][0:N-1]来存储函数值，则可根据定义依次求其值，直到求到A[m][n]的值为止。
测试程序见3_2_3_2，具体算法如下：
long Akm(int m,int n)
//    Ackerman函数的非递归算法
{
    long A[M][N];                    //用于存储Akm的值
        int i,j;
        for(j=0;j<N;j++)
            A[0][j]=j+1;                //条件m==0成立
    for(i=1;i<=m;i++)
        {
            A[i][0]=A[i-1][1];                //条件m!=0且n==0成立
            for(j=1;j<N;j++)
                A[i][j]=A[i-1][A[i][j-1]];    //条件m!=0且n!=0成立
    }
        return A[m][n];
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。