文章目錄

單選題

題號	題目	答案
1	所謂“循環(huán)隊列”是指用單向循環(huán)鏈表或者循環(huán)數(shù)組表示的隊列。	錯
2	在用數(shù)組表示的循環(huán)隊列中，front值一定小于等于rear值。	錯
3	為解決計算機主機與打印機之間速度不匹配問題，通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是？	隊列
4	若已知一隊列用單向鏈表表示，該單向鏈表的當(dāng)前狀態(tài)（含3個對象）是：1->2->3，其中x->y表示x的下一節(jié)點是y。此時，如果將對象4入隊，然后隊列頭的對象出隊，則單向鏈表的狀態(tài)是：	2->3->4
5	某隊列允許在其兩端進行入隊操作，但僅允許在一端進行出隊操作。若元素a、b、c、d、e依次入此隊列后再進行出隊操作，則不可能得到的出隊序列是：	d b c a e
6	若用大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前front和rear的值分別為0和4。當(dāng)從隊列中刪除兩個元素，再加入兩個元素后，front和rear的值分別為多少？	2和0
7	如果循環(huán)隊列用大小為m的數(shù)組表示，且用隊頭指針front和隊列元素個數(shù)size代替一般循環(huán)隊列中的front和rear指針來表示隊列的范圍，那么這樣的循環(huán)隊列可以容納的元素個數(shù)最多為：	m
8	在一個不帶頭結(jié)點的非空鏈?zhǔn)疥犃兄?假設(shè)f和r分別為隊頭和隊尾指針,則插入s所指的結(jié)點運算是( )。	r->next=s; r=s;
9	循環(huán)順序隊列中是否可以插入下一個元素（）	與隊頭指針和隊尾指針的值有關(guān)
10	現(xiàn)有隊列 Q 與棧 S，初始時 Q 中的元素依次是{ 1, 2, 3, 4, 5, 6 }（1在隊頭），S 為空。若允許下列3種操作：（1）出隊并輸出出隊元素；（2）出隊并將出隊元素入棧；（3）出棧并輸出出棧元素，則不能得到的輸出序列是：	3, 4, 5, 6, 1, 2

題解

初始化創(chuàng)建空隊列時，令front=rear=0，每當(dāng)插入新的隊列尾元素時，rear增1，每當(dāng)刪除一個隊列首元素時，front增1。因此，在非空隊列中，頭指針始終指向隊列頭元素，而尾指針始終指向隊列尾元素的下一個位置。
front ：0+2=2，
rear 4+2=6——>0.

函數(shù)題

6-1 另類循環(huán)隊列 (20分)

如果用一個循環(huán)數(shù)組表示隊列，并且只設(shè)隊列頭指針Front，不設(shè)尾指針Rear，而是另設(shè)Count記錄隊列中元素個數(shù)。請編寫算法實現(xiàn)隊列的入隊和出隊操作。

函數(shù)接口定義：

bool AddQ( Queue Q, ElementType X );
ElementType DeleteQ( Queue Q );

其中Queue結(jié)構(gòu)定義如下：

typedef int Position;
typedef struct QNode *PtrToQNode;
struct QNode {
    ElementType *Data;  /* 存儲元素的數(shù)組   */
    Position Front;     /* 隊列的頭指針     */
    int Count;          /* 隊列中元素個數(shù)   */
    int MaxSize;        /* 隊列最大容量     */
};
typedef PtrToQNode Queue;

注意：如果隊列已滿，AddQ函數(shù)必須輸出“Queue Full”并且返回false；如果隊列是空的，則DeleteQ函數(shù)必須輸出“Queue Empty”，并且返回ERROR。

輸入樣例：

4
Del
Add 5
Add 4
Add 3
Del
Del
Add 2
Add 1
Add 0
Add 10
End

輸出樣例：

Queue Empty
5 is out
4 is out
Queue Full
3 2 1 0

代碼


#include <stdio.h>
#include <stdlib.h>

#define ERROR -1
typedef int ElementType;
typedef enum { addq, delq, end } Operation;
typedef enum { false, true } bool;
typedef int Position;
typedef struct QNode *PtrToQNode;
struct QNode {
    ElementType *Data;  /* 存儲元素的數(shù)組   */
    Position Front;     /* 隊列的頭、尾指針 */
    int Count;          /* 隊列中元素個數(shù)   */
    int MaxSize;        /* 隊列最大容量     */
};
typedef PtrToQNode Queue; 

Queue CreateQueue( int MaxSize )
{
    Queue Q = (Queue)malloc(sizeof(struct QNode));
    Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
    Q->Front = 0;
    Q->Count = 0;
    Q->MaxSize = MaxSize;
    return Q;
}

bool AddQ( Queue Q, ElementType X );
ElementType DeleteQ( Queue Q );

Operation GetOp();  /* 裁判實現(xiàn)，細(xì)節(jié)不表 */

int main()
{
    ElementType X;
    Queue Q;
    int N, done = 0;

    scanf("%d", &N);
    Q = CreateQueue(N);
    while ( !done ) {
        switch( GetOp() ) {
        case addq: 
            scanf("%d", &X);
            AddQ(Q, X);
            break;
        case delq:
            X = DeleteQ(Q);
            if ( X!=ERROR ) printf("%d is out\n", X);
            break;
        case end:
            while (Q->Count) printf("%d ", DeleteQ(Q));
            done = 1;
            break;
        }
    }
    return 0;
}

/* 你的代碼將被嵌在這里 */
bool AddQ(Queue Q, ElementType X)
{
if (Q->MaxSize==Q->Count)
{
printf("Queue Full\n");
return ERROR;
}
++Q->Count;
Q->Data[(Q->Front + Q->Count) % Q->MaxSize] = X;
return true;

}
ElementType DeleteQ(Queue Q)
{
if (Q->Count==0)
{
printf("Queue Empty\n");
return ERROR;
}
--Q->Count;
Q->Front = (Q->Front + 1) % Q->MaxSize;
return Q->Data[Q->Front];

}

6-2 雙端隊列 (25分)

雙端隊列（deque，即double-ended queue的縮寫）是一種具有隊列和棧性質(zhì)的數(shù)據(jù)結(jié)構(gòu)，即可以（也只能）在線性表的兩端進行插入和刪除。若以順序存儲方式實現(xiàn)雙端隊列，請編寫例程實現(xiàn)下列操作：

Push(X,D)：將元素X插入到雙端隊列D的頭；
Pop(D)：刪除雙端隊列D的頭元素，并返回；
Inject(X,D)：將元素X插入到雙端隊列D的尾部；
Eject(D)：刪除雙端隊列D的尾部元素，并返回。

函數(shù)接口定義：

bool Push( ElementType X, Deque D );
ElementType Pop( Deque D );
bool Inject( ElementType X, Deque D );
ElementType Eject( Deque D );

其中Deque結(jié)構(gòu)定義如下：

typedef int Position;
typedef struct QNode *PtrToQNode;
struct QNode {
    ElementType *Data;      /* 存儲元素的數(shù)組   */
    Position Front, Rear;   /* 隊列的頭、尾指針 */
    int MaxSize;            /* 隊列最大容量     */
};
typedef PtrToQNode Deque;

注意：Push和Inject應(yīng)該在正常執(zhí)行完操作后返回true，或者在出現(xiàn)非正常情況時返回false。當(dāng)Front和Rear相等時隊列為空，Pop和Eject必須返回由裁判程序定義的ERROR。

輸入樣例：

3
Pop
Inject 1
Pop
Eject
Push 2
Push 3
Eject
Inject 4
Inject 5
Inject 6
Push 7
Pop
End

輸出樣例：

Deque is Empty!
1 is out
Deque is Empty!
2 is out
Deque is Full!
Deque is Full!
3 is out
Inside Deque: 4 5

代碼

#include <stdio.h>
#include <stdlib.h>

#define ERROR -1
typedef int ElementType;
typedef enum { push, pop, inject, eject, end } Operation;
typedef enum { false, true } bool;
typedef int Position;
typedef struct QNode *PtrToQNode;
struct QNode {
    ElementType *Data;      /* 存儲元素的數(shù)組   */
    Position Front, Rear;   /* 隊列的頭、尾指針 */
    int MaxSize;            /* 隊列最大容量     */
};
typedef PtrToQNode Deque; 

Deque CreateDeque( int MaxSize )
{   /* 注意：為區(qū)分空隊列和滿隊列，需要多開辟一個空間 */
    Deque D = (Deque)malloc(sizeof(struct QNode));
    MaxSize++;
    D->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
    D->Front = D->Rear = 0;
    D->MaxSize = MaxSize;
    return D;
}

bool Push( ElementType X, Deque D );
ElementType Pop( Deque D );
bool Inject( ElementType X, Deque D );
ElementType Eject( Deque D );

Operation GetOp();          /* 裁判實現(xiàn)，細(xì)節(jié)不表 */
void PrintDeque( Deque D ); /* 裁判實現(xiàn)，細(xì)節(jié)不表 */

int main()
{
    ElementType X;
    Deque D;
    int N, done = 0;

    scanf("%d", &N);
    D = CreateDeque(N);
    while (!done) {
        switch(GetOp()) {
        case push: 
            scanf("%d", &X);
            if (!Push(X, D)) printf("Deque is Full!\n");
            break;
        case pop:
            X = Pop(D);
            if ( X==ERROR ) printf("Deque is Empty!\n");
            else printf("%d is out\n", X);
            break;
        case inject: 
            scanf("%d", &X);
            if (!Inject(X, D)) printf("Deque is Full!\n");
            break;
        case eject:
            X = Eject(D);
            if ( X==ERROR ) printf("Deque is Empty!\n");
            else printf("%d is out\n", X);
            break;
        case end:
            PrintDeque(D);
            done = 1;
            break;
        }
    }
    return 0;
}

/* 你的代碼將被嵌在這里 */

// 頭插
bool Push(ElementType X, Deque D)
{
// 算尾部位置，如果滿了返回false
if ((D->Rear + 1) % (D->MaxSize) == D->Front)
return false;
// 減完了才能用公式
D->Front--;
D->Front = (D->MaxSize + D->Front) % (D->MaxSize);
D->Data[D->Front] = X;
return true;
}

// 頭刪
ElementType Pop(Deque D)
{
if (D->Front == D->Rear)
return ERROR;
ElementType d = D->Data[D->Front];
D->Front++;
D->Front = D->Front % (D->MaxSize);
return d;
}

// 尾插
bool Inject(ElementType X, Deque D)
{
    // 算尾部位置，如果滿了返回false
if ((D->Rear + 1) % (D->MaxSize) == D->Front)
return false;
D->Data[D->Rear] = X;
D->Rear = (D->Rear + 1) % D->MaxSize;
return true;
}

// 尾刪
ElementType Eject(Deque D)
{
if (D->Front == D->Rear)
return ERROR;
if (!D->Rear)
D->Rear = D->MaxSize;
D->Rear--;
ElementType d = D->Data[D->Rear];
return d;
}

編程題

7-1 堆棧模擬隊列 (25分)

設(shè)已知有兩個堆棧S1和S2，請用這兩個堆棧模擬出一個隊列Q。

所謂用堆棧模擬隊列，實際上就是通過調(diào)用堆棧的下列操作函數(shù):

int IsFull(Stack S)：判斷堆棧S是否已滿，返回1或0；
int IsEmpty (Stack S )：判斷堆棧S是否為空，返回1或0；
void Push(Stack S, ElementType item )：將元素item壓入堆棧S；
ElementType Pop(Stack S )：刪除并返回S的棧頂元素。

實現(xiàn)隊列的操作，即入隊void AddQ(ElementType item)和出隊ElementType DeleteQ()。

輸入格式:

輸入首先給出兩個正整數(shù)N1和N2，表示堆棧S1和S2的最大容量。隨后給出一系列的隊列操作：A item表示將item入列（這里假設(shè)item為整型數(shù)字）；D表示出隊操作；T表示輸入結(jié)束。

輸出格式:

對輸入中的每個D操作，輸出相應(yīng)出隊的數(shù)字，或者錯誤信息ERROR:Empty。如果入隊操作無法執(zhí)行，也需要輸出ERROR:Full。每個輸出占1行。

輸入樣例:

3 2
A 1 A 2 A 3 A 4 A 5 D A 6 D A 7 D A 8 D D D D T

輸出樣例:

ERROR:Full
1
ERROR:Full
2
3
4
7
8
ERROR:Empty

代碼

模擬隊列

#include<stdio.h>
#include<iostream>
#include<stack>
#include<string>

using namespace std;
stack<int>s1, s2;   //定義兩個棧
int n1, n2;         //兩個棧的容量

int main()
{
char c;
int m, p, q;
cin >> n1 >> n2;
if (n1 > n2) 
swap(n1, n2);  // 保證更大的容量的S2作為輸出棧
getchar();
while (1) 
{     
// 無限循環(huán)輸入
cin >> c;
if (c == 'T') 
break;     // 輸入字符為T時結(jié)束
if (c == 'A') 
{
cin >> m;
if (s1.size() == n1 && s2.size() != 0)   // 只有當(dāng)s1為滿，s2不為空時才是滿的情況
printf("ERROR:Full\n");
else if (s1.size() == n1 && s2.size() == 0) 
{   
// 當(dāng)s1為滿，s2為空時，先將s1里面所有的元素轉(zhuǎn)移到s2，再將新加入的元素放置s1
q = n1;
while (q--) 
{
p = s1.top();
s1.pop();
s2.push(p);
}
s1.push(m);
}
else if (s1.size() != n1)  // 若s1不滿，可直接將新入的元素放置s1里面
s1.push(m);;
}
if (c == 'D') 
{   
//輸入字符為D時要出隊
if (s1.size() == 0 && s2.size() == 0)    //只有當(dāng)s1,s2均為空時才為隊空的情況
printf("ERROR:Empty\n");
else if (s1.size() != 0 && s2.size() == 0)
{  
//若s2為空，s1不空，則先把s1里面所有元素轉(zhuǎn)移至s2，再輸出s2的棧頂元素
q = s1.size();
while (q--) {
p = s1.top();
s1.pop();
s2.push(p);
}
cout << s2.top() << endl;
s2.pop();
}
else if (s2.size() != 0) 
{ 
//如果s2不為空，可直接輸出s2棧頂元素
cout << s2.top() << endl;
s2.pop();
}
}
}
return 0;
}

直接用queue

#include<bits/stdc++.h> 
using namespace std;
queue<int> q; 
  
int main()
{  
    int m,n,i,a;  
    char c;  
    cin>>m>>n;  
    n+=m;
    for(i=0;;i++)
{  
        cin>>c;  
        if(c=='T')  
            return 0;
        if(c=='A')
{  
            cin>>a;  
            if(q.size()==n)
{
                cout<<"ERROR:Full"<<endl;  
            }  
            else
{  
                q.push(a);  
            }  
        }  
        else if(c=='D')
{  
            if(q.size()==0)
{  
                cout<<"ERROR:Empty"<<endl;  
            }  
            else
{  
                cout<<q.front()<<endl;  
                q.pop();   
            }  
        }  
    }  
    return 0;  
}

本站僅提供存儲服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請點擊舉報。

九色国产,午夜在线视频,新黄色网址,九九色综合,天天做夜夜做久久做狠狠,天天躁夜夜躁狠狠躁2021a,久久不卡一区二区三区

文章目錄

單選題

題解

函數(shù)題

6-1 另類循環(huán)隊列 (20分)

輸入樣例：

輸出樣例：

代碼

6-2 雙端隊列 (25分)

輸入樣例：

輸出樣例：

代碼

編程題

7-1 堆棧模擬隊列 (25分)

輸入格式:

輸出格式:

輸入樣例:

輸出樣例:

代碼

模擬隊列

直接用queue