【数据结构】数据结构练习题2——栈+队列

一、选择题

1.假定一个循环顺序队列的队首和队尾指针分别为f和r，则判断队空的条件是（D） A f+1==r B r+1==f C f==0 D f==r

2.假定一个链队（有头结点）的队首和队尾指针分别为front和rear，则判断队空的条件是（A） A front==rear B front!=NULL C rear!=NULL D front==NULL

3.循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是 （A） A (rear-front+m)%m B rear-front+1 C rear-front-1 D rear-front

4.判定一个循环队列QU（最多元素为m, m= =Maxsize-1）为满队列的条件是 （A） A ((rear- front)+ Maxsize)% Maxsize = =m B rear-front-1= =m C front= =rear D front= = rear+1

5.一个队列的数据入列序列是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

6.从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行什么。(不带空的头结点) （D） A x=HS; HS= HS—＞next; B x=HS—＞data; C HS= HS—＞next; x=HS—＞data; D x=HS—＞data; HS= HS—＞next;

7.从一个循环顺序队列删除元素时，首先需要（B） A 前移一位队首指针 B 后移一位队首指针 C 取出队首指针所指位置上的元素 D 取出队尾指针所指位置上的元素

8.在一个循环顺序队列中，队首指针指向队首元素的什么位置。（C） A 前一个 B 后一个 C 当前 D 后面

9.当利用大小为N的一维数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行什么语句修改top指针。 （B） A top++ B top– C top=0 D top

10.栈和队列的共同点是 （C） A 都是先进后出 B 都是先进先出 C 只允许在端点处插入和删除元素 D 没有共同点

11.一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是 （C） A edcba B decba C dceab D abcde

12.队列操作的原则是（A） A 先进先出 B 后进先出 C 只能进行插入 D 只能进行删除

13.判定一个顺序栈ST（最多元素为m0）为空的条件是 （B） A top!=0 B top= =0 C top!=m0 D top= =m0-1

14.栈结构通常采用的两种存储结构是（A） A 顺序存储结构和链式存储结构 B 散列方式和索引方式 C 链表存储结构和数组 D 线性存储结构和非线性存储结构

15.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为 （C） A i B n-i C n-i+1 D 不确定

二、编程题

判断字符串镜像——栈

【注意】本题务必使用顺序栈或者链式栈的一种来实现，否则不给分。

【问题描述】试写一个算法，识别依次读入的一个以“@”为结束符的字符序列是否为形如 “序列1&序列2” 模式的字符序列。其中序列1和序列2都不含字符 “&”，且序列2是序列1的逆序列。例如，“ a+b&b+a ”是属该模式的字符序列，而 “1+3&3-1”则不是。

【输入形式】 以@为结尾的一串字符

【输出形式】 若符合模式则输出字符串长度，否则输出no

【样例输入】 a+b&b+a@

【样例输出】 3

#include
#include
using namespace std;

class array_stack
{
public:
	array_stack(int size);
	bool push(char str);
	void pop();
	char top();
	bool is_empty();
	bool is_full();

private:
	struct STACK
	{
		char data;
		struct STACK * next;
	}*p, *q, *head;
	int _size;
	int max_size;
};

array_stack::array_stack(int size)
{
	p = NULL; q = NULL;
	head = NULL;
	max_size = size;
	_size = 0;
}


inline bool array_stack::push(char str)
{
	if (is_full())
		return false;
	p = new STACK;
	p->data = str;
	p->next = NULL;
	if (head == NULL)
		head = p;
	if (q == NULL)
		q = p;
	else
	{
		q->next = p;
		q = p;
	}
	_size++;
	return true;
}

void array_stack::pop()
{
	if (is_empty())
		return;
	if (head->next == NULL)	// 只有一个元素时候
	{
		delete head;
		head = NULL;
		p = NULL;
		q = NULL;
		return;
	}
	for (p = head; p->next != q; p = p->next);
	delete q;
	p->next = NULL;
	q = p;
	_size--;
}

char array_stack::top()
{
	if (is_empty())
		return '0';
	for (p = head; p->next != NULL; p = p->next);
	return p->data;
}

bool array_stack::is_empty()
{
	if (head == NULL)
		return true;
	return false;
}

bool array_stack::is_full()
{
	if (_size > str;
	for (i = 0; str[i] != '&'; i++)
	{
		sta1.push(str[i]);
		str_length++;
	}

	for (i = str.find('&') + 1; str[i] != '@'; i++)
	{
		if (str[i] == sta1.top())
			sta1.pop();
	}
	if (sta1.is_empty())
		cout