作业7-栈及其应用(防止题目重复)

Bertha 。 2022-12-26 15:28 126阅读 0赞

1-1  
通过对堆栈S操作：Push(S,1), Push(S,2), Pop(S),  
Push(S,3), Pop(S), Pop(S)。输出的序列为：123。(F)  
\[解析\]输出序列为231

1-2  
若一个栈的输入序列为1，2，3，…，N，输出序列的第一个元素是i，  
则第j个输出元素是j−i−1。()  
\[解析\]查到的一个看法是不确定,但是这是判断题…  
https://blog.csdn.net/qq\_46088286/article/details/106633024

1-3  
若一个栈的输入序列为\{1, 2, 3, 4, 5\}，  
则不可能得到\{3, 4, 1, 2, 5\}这样的出栈序列。(F)  
\[解析\]Push(1)Push(2)Push(3)Pop()Push(4)Pop()  
下一个你想得到1 就必须先弹出2 , 那序列就不对了

2-4  
给定一个堆栈的入栈序列为\{ 1, 2, ⋯, n \}，  
出栈序列为\{ p1, p2, ⋯, pn \}。如果p2=n，  
则存在多少种不同的出栈序列？  
A.1  
B.2  
C.n−1  
D.n  
\[解析\]既然第2个出栈的是n,那么第一个出栈的可能是前n-1个元素的  
其中一个,此时后面的出栈序列就确定了  
所以有n-1种出栈序列

2-5  
设一个堆栈的入栈顺序是1、2、3、4、5。  
若第一个出栈的元素是4，则最后一个出栈的元素必定是：()  
A.1  
B.3  
C.5  
D.1或者5  
\[解析\]也就是说在压入123的时候 都不出栈,然后压入4,再弹出4  
之后对最后出栈的元素有两种情况:  
(1)先压入5,然后 弹出5321  
(2)先弹出321,然后压入5,弹出5

2-6  
从栈顶指针为ST的链栈中删除一个结点且用X保存被删结点的值，  
则执行：©  
A.X= ST->data;  
B.X= ST; ST = ST->next;  
C.X= ST->data; ST = ST->next;  
D.ST = ST->next; X= ST->data;  
\[解析\]X = ST->next, ST = ST->next;  
其实我感觉答案不太好, 因为这样没法是放栈顶结点的空间  
但是答案又提示了 X只保存结点的值,所以 无所谓了

2-7  
设栈S和队列Q的初始状态均为空，元素a、b、c、d、e、f、g依次  
进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序  
是b、d、c、f、e、a、g，则栈S的容量至少是：(3)  
A.1  
B.2  
C.3  
D.4  
\[解析\]求栈S存储的元素的峰值  
压入a, b (状态a, b)  
然后 弹出b (状态a)  
压入c, d (状态a, c, d)  
弹出d, c (状态a)  
压入e, f (a, e, f)  
弹出f, e, a ()  
压入g (g)  
弹出g ()  
所以至少容量应该是3

2-8  
假设有5个整数以1、2、3、4、5的顺序被压入堆栈，  
且出栈顺序为3、5、4、2、1，那么为了获得这样的输出，  
堆栈大小至少为：©  
A.2  
B.3  
C.4  
D.5  
\[解析\]  
压入1, 2, 3 ( 1, 2, 3)  
弹出3 (1, 2)  
压入4, 5 (1, 2, 4, 5)  
弹出 5, 4, 2, 1()

2-9  
若元素a、b、c、d、e、f依次进栈，允许进栈、退栈操作交替进行，  
但不允许连续三次进行退栈工作，则不可能得到的出栈序列是？(D)  
A.b c a e f d  
B.c b d a e f  
C.d c e b f a  
D.a f e d c b  
\[解析\]  
检查每个选项  
A:  
压入 a, b (a, b)  
弹出b (a)  
压入c (a, c)  
弹出c, a()  
压入d, e (d, e)  
弹出e (d)  
压入f (d, f)  
弹出f, d ()  
\{正确\}  
B:  
压入a, b, c (a, b, c)  
弹出c, b (a)  
压入d (a, d)  
弹出d, a ()  
压入e (e)  
弹出e ()  
压入f (f)  
弹出f ()  
\{正确\}  
C:同理 不在展示  
D:  
压入a (a)  
弹出a ()  
压入b, c, d, e, f(b, c, d, e, f)  
此时会连续5次弹出操作,所以\{错误\}

2-10  
设一个栈的输入序列是1、2、3、4、5，则下列序列中，  
是栈的合法输出序列的是？(A)  
A.3 2 1 5 4  
B.5 1 2 3 4  
C.4 5 1 3 2  
D.4 3 1 2 5  
\[解析\]  
A:  
压入1, 2, 3 (1, 2, 3)  
弹出3, 2, 1 ()  
压入4, 5 (4, 5)  
弹出5, 4  
B:  
压入1, 2, 3, 4, 5 (1, 2, 3, 4 ,5)  
弹出5 (1, 2, 3, 4)  
选项中弹出1, 但实际应该弹出4  
\{错误\}  
C:  
压入1, 2, 3, 4 (1, 2, 3, 4)  
弹出4 (1, 2, 3)  
压入5 (1, 2, 3, 5)  
弹出5 (1, 2, 3)  
选项要求弹出1, 但实际应该弹出3  
\{错误\}  
D:  
压入1, 2, 3, 4 (1, 2, 3, 4)  
弹出4, 3 (1, 2)  
选项要求弹出1, 但实际应该弹出2  
\{错误\}

2-11  
有六个元素以6、5、4、3、2、1的顺序进栈，  
问哪个不是合法的出栈序列？(B)  
A.2 3 4 1 5 6  
B.3 4 6 5 2 1  
C.5 4 3 6 1 2  
D.4 5 3 1 2 6  
\[解析\]  
选项B:  
压入6, 5, 4, 3 (6, 5, 4, 3)  
弹出3, 4 (6, 5)  
选项要求弹出6, 但实际应该弹出5  
\{错误\}

2-12  
若一个栈的入栈序列为1、2、3、…、N，  
输出序列的第一个元素是i，则第j个输出元素是：(D)  
A.i−j−1  
B.i−j  
C.j−i−1  
D.不确定  
\[解析\]输出第一个元素是 i, 所以 前i个(1…i)个元素依次压入  
但是输出第一个元素i之后, 究竟是该压入元素,还是弹出元素就不确定了  
所以 之后的 输出序列也不确定

2-13  
若一个栈的入栈序列为1、2、3、…、N,其输出序列为p1、p2、p3、…、pN.  
若p1=N，则pi为：©  
A.i  
B.n−i  
C.n−i+1  
D.不确定  
\[解析\]第一个输出的是N,那么元素应该从1到N依次压入栈  
然后在弹出栈,所以输出序列是原来的逆序  
p2 = N-1, 将每个选项代入可知 C正确

2-14  
将5个字母ooops按此顺序入栈，  
则有多少种不同的出栈顺序可以仍然得到ooops？()  
A.1  
B.3  
C.5  
D.6  
\[解析\]关键是三个o的出栈顺序, 但是不会

2-15  
栈的插入和删除操作在()进行。(A)  
A.栈顶  
B.栈底  
C.任意位置  
D.指定位置

2-16  
表达式a\*(b+c)-d的后缀表达式是：(A)  
A.a b c + \* d -  
B.a b c d \* + -  
C.a b c \* + d -  
D.- + \* a b c d  
\[解析\]  
数栈:  
符号栈:  
后缀栈:a b c + \* d -

7-16 堆栈操作合法性 (20分)

假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列，对一个空堆栈进行操作，相应操作均可行（如没有出现删除时栈空）且最后状态也是栈空，则称该序列是合法的堆栈操作序列。请编写程序，输入S和X序列，判断该序列是否合法。  
输入格式:

输入第一行给出两个正整数N和M，其中N是待测序列的个数，M（≤50）是堆栈的最大容量。随后N行，每行中给出一个仅由S和X构成的序列。序列保证不为空，且长度不超过100。  
输出格式:

对每个序列，在一行中输出YES如果该序列是合法的堆栈操作序列，或NO如果不是。

输入样例：  
4 10  
SSSXXSXXSX  
SSSXXSXXS  
SSSSSSSSSSXSSXXXXXXXXXXX  
SSSXXSXXX

输出样例：  
YES  
NO  
NO  
NO

#include <iostream>
    #include <malloc.h>
    #include <cstring>
    using namespace std;
    
    #define OVERFLOW -2
    #define OK 1
    #define FALSE 0
    const int STACK_INIT_SIZE = 100;
    const int STACKINCREMENT = 10;
    const int MAXNUM = 1e2 + 5;
    typedef int Status;
    typedef char SElemType;
    typedef struct 
    {
        
    	SElemType *base;
    	SElemType *top;
    	int stacksize;
    }Stack;
    
    void InitStack(Stack &S)
    {
        
    	S.base = (SElemType*)malloc(sizeof(SElemType) * STACK_INIT_SIZE);
    	if (S.base == NULL) exit(OVERFLOW);
    	S.top = S.base;
    	S.stacksize = STACK_INIT_SIZE;
    }
    
    void DestroyStack(Stack &S)
    {
        
    	free(S.base);
    	S.base = NULL;
    	S.top = NULL;
    	S.stacksize = 0;
    }
    
    Status Push(Stack &S, SElemType e)
    {
        
    	if (S.top - S.base == S.stacksize)
    	{
        
    		S.base = (SElemType*)realloc(S.base, sizeof(SElemType) * (S.stacksize + STACKINCREMENT));
    		if (S.base == NULL) exit(OVERFLOW);
    		S.stacksize += STACKINCREMENT;
    	}
    	*S.top = e;
    	S.top++;
    	return OK;
    }
    
    Status Pop(Stack &S, SElemType &e)
    {
        
    	if (S.base == S.top) return FALSE;
    	else 
    	{
        
    		e = *(S.top - 1);
    		S.top--;
    		return OK;
    	}
    }
    
    bool EmptyStack(Stack S)
    {
        
    	if (S.base == S.top) return true;
    	else return false;
    }
    int LengthStack(Stack S)
    {
        
    	return S.top - S.base;
    }
    int main()
    {
        
    	int n, m;
    	int errors = 0;
    	SElemType str[MAXNUM];
    	SElemType temp;
    	Stack S;
    	cin >> n >> m;
    	for (int i = 0; i < n; i++)
    	{
        
    		memset(str, 0, sizeof(str));
    		InitStack(S);
    		errors = 0;
    		scanf("%s", str);
    		for (int i = 0; i < strlen(str); i++)
    		{
        
    			if (str[i] == 'S')
    			{
        
    				if (LengthStack(S) == m) 
    				{
        
    					errors++;
    					break;
    				}
    				Push(S, str[i]);
    			}
    			else 
    			{
        
    				if (EmptyStack(S) == true)
    				{
        
    					errors++;
    					break;
    				}
    				else 
    				{
        
    					Pop(S, temp);
    				}
    			}
    			//cout << "[" << LengthStack(S) << "]" << endl;
    		}
    		if (errors > 0 || LengthStack(S) != 0) 
    		{
        
    			cout << "NO" << endl;
    		}
    		else if (errors == 0)
    		{
        
    			cout << "YES" << endl;
    		}
    		DestroyStack(S);
    	}
    	system("pause");
    	return 0;
    }

习题3.8 符号配对 (20分)

请编写程序检查C语言源程序中下列符号是否配对：/*与*/、(与)、\[与\]、\{与\}。  
输入格式:

输入为一个C语言源程序。当读到某一行中只有一个句点.和一个回车的时候，标志着输入结束。程序中需要检查配对的符号不超过100个。  
输出格式:

首先，如果所有符号配对正确，则在第一行中输出YES，否则输出NO。然后在第二行中指出第一个不配对的符号：如果缺少左符号，则输出?-右符号；如果缺少右符号，则输出左符号-?。  
输入样例1：

void test()
    {
        
        int i, A[10];
        for (i=0; i<10; i++) /*/
            A[i] = i;
    }
    .

输出样例1：

NO  
/\*-?

输入样例2：

void test()
    {
        
        int i, A[10];
        for (i=0; i<10; i++) /**/
            A[i] = i;
    }]
    .

输出样例2：

NO  
?-\]

//这份代码写的很烂,偷个懒
    #include <iostream>
    #include <malloc.h>
    #include <cstring>
    using namespace std;
    
    #define OVERFLOW -2
    #define OK 1
    #define FALSE 0
    const int STACK_INIT_SIZE = 100;
    const int STACKINCREMENT = 10;
    const int MAXNUM = 1e2 + 5;
    typedef int Status;
    typedef char SElemType;
    typedef struct 
    {
        
    	SElemType *base;
    	SElemType *top;
    	int stacksize;
    }Stack;
    
    void InitStack(Stack &S)
    {
        
    	S.base = (SElemType*)malloc(sizeof(SElemType) * STACK_INIT_SIZE);
    	if (S.base == NULL) exit(OVERFLOW);
    	S.top = S.base;
    	S.stacksize = STACK_INIT_SIZE;
    }
    
    void DestroyStack(Stack &S)
    {
        
    	free(S.base);
    	S.base = NULL;
    	S.top = NULL;
    	S.stacksize = 0;
    }
    
    Status Push(Stack &S, SElemType e)
    {
        
    	if (S.top - S.base == S.stacksize)
    	{
        
    		S.base = (SElemType*)realloc(S.base, sizeof(SElemType) * (S.stacksize + STACKINCREMENT));
    		if (S.base == NULL) exit(OVERFLOW);
    		S.stacksize += STACKINCREMENT;
    	}
    	*S.top = e;
    	S.top++;
    	return OK;
    }
    
    Status Pop(Stack &S, SElemType &e)
    {
        
    	if (S.base == S.top) return FALSE;
    	else 
    	{
        
    		e = *(S.top - 1);
    		S.top--;
    		return OK;
    	}
    }
    
    void getTop(Stack S, SElemType &e)
    {
        
    	e = *(S.top - 1);
    }
    bool EmptyStack(Stack S)
    {
        
    	if (S.base == S.top) return true;
    	else return false;
    }
    int LengthStack(Stack S)
    {
        
    	return S.top - S.base;
    }
    int main()
    {
        
    	int n, m;
    	int errors = 0;
    	SElemType str[MAXNUM];
    	SElemType temp;
    	Stack S;
    	InitStack(S);
    	while (true)
    	{
        
    		memset(str, 0, sizeof(str));
    		scanf("%s", str);
    		if (strlen(str) == 1 && str[0] == '.')
    			break;
    		if (errors > 0)
    			continue;
    		for (int i = 0; i < strlen(str); i++)
    		{
        
    			if (str[i] == '(' || str[i] == '[' || str[i] == '{')
    				Push(S, str[i]);
    			else if (str[i] == '/' && i != strlen(str) - 1 && str[i + 1] == '*')
    			{
        
    				Push(S, str[i]);
    				i++;
    				//这里注意一下如果没有i++, 下一次读取到的是*, 这个*本应该和前面的/构成一个符号
    				//如果不i++, 可能会被第二次用作和下一个符号/构成*/
    				//但是 只有i++不行 ,因为 下面 的else if里面 还是无法解决 */这个问题
    				//所以我加了continue;
    				continue;
    			}
    			else if (str[i] == ')' || str[i] == ']' || str[i] == '}' || (str[i] == '*' && i != strlen(str) - 1 && str[i + 1] == '/'))
    			{
        
    				if (EmptyStack(S))
    				{
        
    					errors++;
    					cout << "NO" << endl;
    					if (str[i] == '*')
    					cout << "?-" << "*/" << endl;
    					else 
    						cout << "?-" << str[i] << endl;
    					break;
    				}
    				getTop(S, temp);
    				if (str[i] == ')')
    				{
        
    					if (temp == '(')
    						Pop(S, temp);
    					else 
    					{
        
    						errors++;
    						cout << "NO" << endl;
    						if (temp == '/')
    							cout << temp << "*" << "-?" << endl;
    						else 
    							cout << temp << "-?" << endl;
    						break;
    					}
    				}
    				else if (str[i] == ']')
    				{
        
    					if (temp == '[')
    						Pop(S, temp);
    					else 
    					{
        
    						errors++;
    						cout << "NO" << endl;
    						if (temp == '/')
    							cout << temp << "*" << "-?" << endl;
    						else 
    							cout << temp << "-?" << endl;
    						break;
    					}
    				}
    				else if (str[i] == '}')
    				{
        
    					if (temp == '{')
    						Pop(S, temp);
    					else 
    					{
        
    						errors++;
    						cout << "NO" << endl;
    						if (temp == '/')
    							cout << temp << "*" << "-?" << endl;
    						else 
    							cout << temp << "-?" << endl;
    						break;
    					}
    				}
    				else if (str[i] == '*' && i != strlen(str) - 1 && str[i + 1] == '/')
    				{
        
    					if (temp == '/')
    						Pop(S, temp);
    					else 
    					{
        
    						errors++;
    						cout << "NO" << endl;
    						if (temp == '/')
    							cout << temp << "*" << "-?" << endl;
    						else 
    							cout << temp << "-?" << endl;
    						break;
    					}
    					i++;
    				}
    			}
    		}
    	}
    	if (errors == 0 && EmptyStack(S)) 
    		cout << "YES" << endl;
    	else if (errors == 0 && !EmptyStack(S))
    	{
        
    		getTop(S, temp);
    		cout << "NO" << endl;
    		cout << temp << "-?" << endl;
    	}
    	system("pause");
    	return 0;
    }