判断题
- 若一个栈的输入序列为1，2，3，…，N，输出序列的第一个元素是i，则第j个输出元素是j−i−1。 (F)
- 栈的运算遵循后入先出的原则，输出的第一个是i，则第j个输出的应该是第i-j 1个元素。
- 所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。 (F)
- 循环队列：队列采用顺序存储，并且数组是头尾相接的循环结构
- 在对不带头结点的链队列作出队操作时，不会改变头指针的值。 (F)
- 会改变，头指针变为相连的指针；
- 不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑”溢出”情况。 (T)
- 队列和栈都是运算受限的线性表，只允许在表的两端进行运算。 (F)
- 队列在只允许在一端插入，在另一端删除，而队列只能在同一端进行操作。
- 栈和队列的存储方式，既可以是顺序方式，也可以是链式方式。
- 循环队列也存在着空间溢出问题。 (T)
- 循环队列解决的是假溢出问题，由于循环队列的大小是固定的，仍会出现真溢出。
- 循环队列执行出队操作时会引起大量元素的移动。
- 栈是插入和删除只能在一端进行的线性表；队列是插入在一端进行，删除在另一端进行的线性表。
- 在n个元素连续进栈以后，它们的出栈顺序和进栈顺序一定正好相反。
- 环形队列中有多少个元素可以根据队首指针和队尾指针的值来计算。
- 栈和队列的插入和删除操作特殊，所以，栈和队列是非线性结构。 (F)
- 栈和队列都是运算受限的线性表。
- 序列{1,2,3,4,5}依次入栈，则不可能得到{3,4,1,2,5}的出栈序列。 (T)
- 由题1,2,3,4,5依次入栈，所以在第一个3出栈的时候1,2均已经入栈，又由于栈的运算遵循后入先出，2会比1更先出栈，故{3,4,1,2,5}的出栈序列不可能出现。
- 队列中允许插入的一端叫队头，允许删除的一端叫队尾。 （F)
选择题
- 若用大小为6的数组来实现循环队列，且当前
front和rear的值分别为0和4。当从队列中删除两个元素，再加入两个元素后，front和rear的值分别为多少？ (A) A.2和0 B.2和2 C.2和4 D.2和6- 有已知得，
front和rear的值分别为0和4，又数组大小为6，所以值的范围为[0,5],先删除两个元素，在添加两个元素，front与rear的值分别加2，为2,0.
- 有已知得，
- 如果循环队列用大小为
m的数组表示，且用队头指针front和队列元素个数size代替一般循环队列中的front和rear指针来表示队列的范围，那么这样的循环队列可以容纳的元素个数最多为： A.m-1 B. m C.m 1 D.不能确定 - 以下数据结构中，（ ）是非线性数据结构。 (A) A.树 B.字符串 C.队列 D.栈
- 设栈S和队列Q的初始状态均为空，元素{1, 2, 3, 4, 5, 6, 7}依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是{2, 5, 6, 4, 7, 3, 1}，则栈S的容量至少是：(D)
A.1 B.2 C.3 D.4
- 由题出栈顺序是2,5,6,4,7,3,1而入栈顺序是顺序，则在5出栈前栈内至少含有1,3,4,5,四个数据，由此栈的大小至少为4
- 线性表、堆栈、队列的主要区别是什么？ (B) A.线性表用指针，堆栈和队列用数组 B.堆栈和队列都是插入、删除受到约束的线性表 C.线性表和队列都可以用循环链表实现，但堆栈不能 D.堆栈和队列都不是线性结构，而线性表是
- 栈和队列的共同点( )。 (C) A.都是先进先出 B.都是后进先出 C.只允许在端点处插入和删除元素 D.没有共同点
- 下列关于线性表,栈和队列叙述,错误的是( )。 (A) A.线性表是给定的n(n必须大于零)个元素组成的序列 B.线性表允许在表的任何位置进行插入和删除操作 C.栈只允许在一端进行插入和删除操作 D.队列只允许在一端进行插入一端进行删除
- 设用一个数组A[1……N]来存储一个栈，令A[N]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。当从栈中弹出一个元素时，变量T的变化为（ ）。
- 链式栈与顺序栈相比，一个比较明显的优点是（ ）。 (B) A.插入操作更加方便 B.通常不会出现栈满的情况 C.不会出现栈空的情况 D.删除操作更加方便
- 在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的长度是（ ）。
- 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（ ）。提示：对于栈，可以全进再依次出；也可以进一个出一个；也可以进一部分，出一个，再进一部分；但是出栈之后，不能再入栈。 (A) A.3 B.4 C.6 D.2
- 关于栈和队列的下列说法正确的是（） (B) A.栈的插入操作是在栈顶进行，插入时需将栈内所有元素后移； B.栈是后进先出的结构，出栈时除了栈顶元素，其余元素无需移动； C.循环队列的出队操作删除的是队头元素，采用循环队列存储时，其余队列元素均需要移动； D.链队列的入队操作在表尾进行，操作时间与队列长度成正比
- 一个栈的入栈序列是a,b,c,d,e，则栈的出栈序列不可能的是（ ）。 C A.edcba B.decba C.dceab D.abcde
- 在一个链表表示的队列中， f和r分别指向队列的头和尾。下列哪个操作能正确地将s结点插入到队列中： (B) A.f->next=s; f=s; B.r->next=s; r=s; C.s->next=r; r=s; D.s->next=f; f=s;
- 栈和队列具有相同的。 (B) A.抽象数据类型 B.逻辑结构 C.存储结构 D.运算
- 假定利用数组a[n]顺序存储一个栈，用top表示栈顶指针，用top==-1表示栈空，并已知栈未满，当元素x进栈时所执行的操作为（C）。 A.a[–top]=x B.a[top–]=x C.a[ top]=x D.a[top ]=x
- 队列的“先进先出”特性是指（B）。 Ⅰ.最后插入队列中的元素总是最后被删除 Ⅱ.当同时进行插入、删除操作时，总是插入操作优先 Ⅲ.每当有删除操作时，总要先做一次插入操作 Ⅳ.每次从队列中删除的总是最早插入的元素 A.Ⅰ B.Ⅰ、Ⅳ C.Ⅱ、Ⅲ D.Ⅳ
- 已知循环队列存储在一维数组A[0…n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第一个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是（ ）。
- 执行函数时，其局部变量一般采用（ ）进行存储。 (C) A.树形结构 B.静态链表 C.栈结构 D.队列结构
- 对空栈 S 进行 Push 和 Pop 操作，入栈序列为 a, b, c, d, e，经过 Push, Push, Pop, Push, Pop, Push, Push, Pop 操作后，得到的出栈序列是： (D) A.b, a, c B.b, a, e C.b, c, a D.b, c, e
- 用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为( )。 (D) A.SXSSSXXX B.SXSXSXSX C.SSSSXXXX D.SXSSXSXX
填空题
4-1 栈的运算遵循 后进先出
4-2 以下运算实现在链队上的入队列，请在空白处用适当句子予以填充。
代码语言：javascript复制void EnQueue(QueptrTp *lq,DataType x){
LqueueTp *p;
p=(LqueueTp *)malloc(sizeof(LqueueTp))
p->data=x; // 1分
p->next=NULL;
(lq->rear)->next=p// 1分;
lq->rear=p // 1分;
}4-3 以下运算实现在链栈上的初始化，请在空白处用请适当句子予以填充。
代码语言：javascript复制typedef struct Node{
DataType data;
struct Node *next;
}StackNode,*LStackTp;
void InitStack(LStackTp &ls){
ls=NULL
}//3分;函数题
舞伴问题 (20 分)
假设在周末舞会上，男士和女士们分别进入舞厅，各自排成一队。跳舞开始，依次从男队和女队队头各出一人配成舞伴，若两队初始人数不同，则较长那一队未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。 你需要用队列操作实现上述算法。请完成下面5个函数的操作。
函数接口定义：
代码语言：javascript复制int QueueLen(SqQueue Q);//队列长度
int EnQueue(SqQueue &Q, Person e);//加入队列
int QueueEmpty(SqQueue &Q);//队列是否为空
int DeQueue(SqQueue &Q, Person &e);//出队列
void DancePartner(Person dancer[], int num); //配对舞伴 Q：队列e:参加舞会的人dancer:全部舞者num:参加舞会的人数
**输入说明 先输入参加舞会人数，再分别输入参加舞会人的姓名和性别 **
**输出说明 先输出配对的男女舞伴，若队伍有剩人，则输出剩下人性别及剩下人数目。 **
裁判测试程序样例：
代码语言：javascript复制#include<iostream>
#define MAXQSIZE 100//队列可能达到的最大长度
#define OK 1
#define ERROR 0
#define OVERFLOW -2
using namespace std;
typedef struct {
char name[20]; //姓名
char sex; //性别，'F'表示女性，'M'表示男性
} Person;
//- - - - - 队列的顺序存储结构- - - - -
typedef struct {
Person data[MAXQSIZE];
int front; //头指针
int rear; //尾指针
} Queue;
typedef Queue *SqQueue;
SqQueue Mdancers, Fdancers; //分别存放男士和女士入队者队列
int InitQueue(SqQueue &Q);
void DestroyQueue(SqQueue &q);
int QueueLen(SqQueue Q);//队列长度
int EnQueue(SqQueue &Q, Person e);//加入队列
int QueueEmpty(SqQueue &Q);//队列是否为空
int DeQueue(SqQueue &Q, Person &e);//出队列
void DancePartner(Person dancer[], int num); //配对舞伴
int main(){
int i;
int n;
Person dancer[MAXQSIZE];
cin>>n;
for(i=0;i<n;i ) cin>> dancer[i].name >> dancer[i].sex;
InitQueue(Mdancers); //男士队列初始化
InitQueue(Fdancers); //女士队列初始化
cout << "The dancing partners are:" << endl;
DancePartner(dancer, n);
if (!QueueEmpty(Fdancers)) {
cout << "F:"<<QueueLen(Fdancers) ;
} else if (!QueueEmpty(Mdancers)) {
cout << "M:"<<QueueLen(Mdancers) ;
}
DestroyQueue(Fdancers);
DestroyQueue(Mdancers);
return 0;
}
int InitQueue(SqQueue &Q) {//构造一个空队列Q
Q = new Queue; //为队列分配一个最大容量为MAXSIZE的数组空间
if (!Q->data)
exit( OVERFLOW); //存储分配失败
Q->front = Q->rear = 0; //头指针和尾指针置为零，队列为空
return OK;
}
void DestroyQueue(SqQueue &q)
{
delete q;
}
/* 请在这里填写答案 */AC代码
代码语言：javascript复制int QueueLen(SqQueue Q)
{
return (Q->rear - Q->front MAXQSIZE ) % MAXQSIZE;
};//队列长度
int EnQueue(SqQueue &Q, Person e)
{
Q->rear = (Q->rear 1)% MAXQSIZE;
Q->data[Q->rear] = e;
return 0;
};//加入队列
int QueueEmpty(SqQueue &Q)
{
if(Q->rear==Q->front)
{
return 1;
}
else return 0;
};//队列是否为空
int DeQueue(SqQueue &Q, Person &e)
{
Q->front=(Q->front 1)%MAXQSIZE;
e=Q->data[Q->front];
return 0;
};//出队列
void DancePartner(Person dancer[], int num)
{
for (int i=0; i<num; i )
{
if(dancer[i].sex=='F')
{
EnQueue(Fdancers,dancer[i]);
}
if(dancer[i].sex=='M')
{
EnQueue(Mdancers,dancer[i]);
}
}
while(QueueEmpty(Mdancers)!=1&&QueueEmpty(Fdancers)!=1)
{
Person x,y;
DeQueue(Mdancers, x);
DeQueue(Fdancers, y);
cout<<y.name<<" "<<x.name<<endl;
}
}; //配对舞伴 十进制转二进制（顺序栈设计和应用） (10 分)
设计一个顺序栈，并利用该顺序栈将给定的十进制整整数转换为二进制并输出。
函数接口定义：
代码语言：javascript复制#define MaxSize 100 /* 栈最大容量 */
int top; /* 栈顶指针 */
int mystack[MaxSize]; /* 顺序栈 */
/*判栈是否为空，空返回true，非空返回false */
bool isEmpty();
/* 元素x入栈 */
void Push(int x);
/* 取栈顶元素 */
int getTop();
/* 删除栈顶元素 */
void Pop(); 其中 MaxSize 和 top 分别为栈的最大容量和栈顶指针。数组mystack 用来模拟顺序栈。请实现给出的isEmpty、Push、getTop和Pop这四个函数。
裁判测试程序样例：
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
#define MaxSize 100 /* 栈最大容量 */
int top; /* 栈顶指针 */
int mystack[MaxSize]; /* 顺序栈 */
/*判栈是否为空，空返回true，非空返回false */
bool isEmpty();/* 元素x入栈 */
void Push(int x);/* 取栈顶元素 */
int getTop();/* 删除栈顶元素 */
void Pop();/* 十进制正整数转换为二进制 */
void dec2bin(int x) {
top = -1; /* 初始化栈顶指针 */
while (x) {
Push(x % 2);
x >>= 1;
}
while (!isEmpty()) {
int t = getTop();
Pop();
printf("%d", t);
}
printf("n");
}
int main(int argc, char const *argv[])
{
int n;
while (scanf("%d", &n) != EOF) {
dec2bin(n);
}
return 0;
}
/* 请在这里填写答案 */AC代码：
代码语言：javascript复制bool isEmpty()
{
if (top == -1) return true;
else return false;
}
void Push(int x)
{
if (top == MaxSize - 1)
return;
else mystack[ top] = x;
}
int getTop()
{
if (top == -1) return 0;
else return mystack[top];
}
void Pop()
{
if (top == -1) return;
else top--;
}编程题：
7-1 银行业务队列简单模拟 (25 分)
设某银行有A、B两个业务窗口，且处理业务的速度不一样，其中A窗口处理速度是B窗口的2倍 —— 即当A窗口每处理完2个顾客时，B窗口处理完1个顾客。给定到达银行的顾客序列，请按业务完成的顺序输出顾客序列。假定不考虑顾客先后到达的时间间隔，并且当不同窗口同时处理完2个顾客时，A窗口顾客优先输出。
输入格式:
输入为一行正整数，其中第1个数字N(≤1000)为顾客总数，后面跟着N位顾客的编号。编号为奇数的顾客需要到A窗口办理业务，为偶数的顾客则去B窗口。数字间以空格分隔。
输出格式:
按业务处理完成的顺序输出顾客的编号。数字间以空格分隔，但最后一个编号后不能有多余的空格。
代码语言：javascript复制#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
int main()
{
int A[1000];
int B[1000];
int N;
int a=0, b=0, temp;
scanf("%d", &N);
for(int i=0; i<N; i ){
scanf("%d", &temp);
if(temp % 2 == 1)
A[a ] = temp;
else
B[b ] = temp;
}
int i = 0, j = 0;
if(a > 1){//A有超过两个人，输出两个
printf("%d %d", A[0], A[1]);
i = 2;
}
else if(a > 0)//A有超过一个人，输出一个
printf("%d", A[i ]);
else if(b > 0)//A没人，B有人，输出B一个
printf("%d", B[j ]);
if(j == 0)//输出了A没输出B，输出一个B来控制输出一组
printf(" %d", B[j ]);
while(i < a && j < b){
if(i 1 < a){
printf(" %d %d",A[i], A[i 1]);
i = 2;
}
else
printf(" %d", A[i ]);
printf(" %d", B[j ]);
}
while(i < a)
printf(" %d", A[i ]);
while(j < b)
printf(" %d", B[j ]);
}7-2 堆栈操作合法性 (20 分)
假设以`S`和`X`分别表示入栈和出栈操作。如果根据一个仅由`S`和`X`构成的序列，对一个空堆栈进行操作，相应操作均可行（如没有出现删除时栈空）且最后状态也是栈空，则称该序列是合法的堆栈操作序列。请编写程序，输入`S`和`X`序列，判断该序列是否合法。
输入格式:
输入第一行给出两个正整数N和M，其中N是待测序列的个数，M（≤50）是堆栈的最大容量。随后N行，每行中给出一个仅由S和X构成的序列。序列保证不为空，且长度不超过100。
输出格式:
对每个序列，在一行中输出YES如果该序列是合法的堆栈操作序列，或NO如果不是。
输入样例：
代码语言：javascript复制4 10
SSSXXSXXSX
SSSXXSXXS
SSSSSSSSSSXSSXXXXXXXXXXX
SSSXXSXXX结尾无空行输出样例：
代码语言：javascript复制YES
NO
NO
NO结尾无空行#include <iostream>
using namespace std;
int main() {
int N, M;
cin >> N >> M;
while (N--) {
string a;
int cnt = 0, flag = 1;
cin >> a;
for (int i = 0; i < a.size(); i)
if (a[i] == 'S') {
cnt ;
if (cnt > M) {
flag = 0;
cout << "NO" << endl;
break;
}
}
else {
cnt--;
if (cnt < 0) {
flag = 0;
cout << "NO" << endl;
break;
}
}
if (flag)
cout << (cnt == 0 ? "YES" : "NO") << endl;
}
return 0;
}
