栈与队列部分习题(持续更新中)
栈与队列的知识点参考文章:链接 【数据结构】栈和队列的概念与基本操作代码实现
1. 单选题
- 一个栈的输入序列为 1 2 3 4 5,则下列序列中不可能是栈的输出序列的是( )。
A. 2 3 4 1 5
B. 5 4 1 3 2
C. 2 3 1 4 5
D. 1 5 4 3 2
选B
方法一:带选项去试
方法二:
引用 牛客网中用户cpppppp的解答:
可能出现 :
…小…中…大…
…小…大…中…
…中…小…大…
…中…大…小…
…大…中…小…
不可能出现:
…大…小…中…
证明过程链接
- 表达式
a*(b+c)-d
的后缀表达式是( )。
A.
abcd*+-
B.abc+*d-
C.abc*+d-
D.+*abcd
选B
首先,我们遍历表达式:
遇到a
,直接加入后缀表达式。
遇到*
,由于栈为空,直接入栈。
遇到(
,直接入栈。
遇到b
,加入后缀表达式。
遇到+
,由于栈顶元素为(
,直接入栈。
遇到c
,加入后缀表达式。
遇到)
,依次将栈中的运算符加入后缀表达式,直到出现(
,并删除栈顶的(
。
现在后缀表达式为abc+*
。
遇到-
,由于栈为空,直接入栈。
遇到d
,加入后缀表达式。
遍历完毕,栈非空,将栈中元素依次弹出。
最终的后缀表达式为abc+*d-
。
因此,表达式a*(b+c)-d
的后缀表达式是abc+*d-
.
a*(b+c)-d
具体过程如下:
遇到 | 栈中元素 | 栈顶元素 | 后缀表达式 |
---|---|---|---|
a |
无 | 无 | 无 |
* |
无 | 无 | a |
( |
* |
* |
a |
b |
*( |
( |
a |
+ |
*( |
( |
ab |
c |
*(+ |
+ |
ab |
) |
*(+ |
+ |
abc |
- |
* |
* |
abc+ |
d |
- |
- |
abc+* |
无 | 无 | 无 | abc+*d |
无 | 无 | 无 | abc+*d- |
- 循环队列 A[0…m-1]存放其元素值,用 front 和 rear 分别表示队头和队尾,则当前队列中的元素数是( )
A (rear-front+m)%m
B rear-front+1
C rear-front-1
D rear-front
选A
牺牲一个元素空间:
- 队列中元素的个数为:
(rear-front+MAXSIZE)%MAXSIZE;
- 队满:
(rear + 1)%MAXSIZE;
- 队空:
rear==front;
- 为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的( )分别设在这片内存空间的两端
A 长度
B 深度
C 栈顶
D 栈底
选D
两栈共享连续存储空间,两个栈的栈底分别设在这个存储空间的两端的存储结构中,为了使两栈的空间能够做到互补余缺,减少溢出的可能性,两个栈的栈满溢出都不能按位置判别,仅当两栈的栈顶相遇时,才可能栈满溢出。
- 设有一个 10 阶的对称矩阵 A,采用压缩存储方式,以行序为主存储,a11为第一元素,其存储地址为 1,每个元素占一个地址空间,则 a85的地址为( )。
A. 13
B. 33
C. 18
D. 40
前7行占用空间为:
前7行占用空间为 = n ⋅ ( n + 1 ) 2 = 7 ⋅ ( 7 + 1 ) 2 = 28 \text{前7行占用空间为} = \frac{n \cdot (n+1)}{2}=\frac{7\cdot (7+1)}{2} = 28 前7行占用空间为=2n⋅(n+1)=27⋅(7+1)=28
a88 = 28 + 5 = 33 \text{a88} = 28+5 =33 a88=28+5=33
- 用数组 r 存储静态链表,结点的 next 域指向后继,工作指针 j 指向链中结点,使 j 沿链移动的操作为( )。
A.
j=r[j].next
B.j=j+1
C.j=j->next
D.j=r[j]->next
选A
静态链表的知识可以参考文章:链接: 【数据结构】静态链表、循环单链表、双向链表、双向循环链表的概念与基本操作代码实现
2. 简答题
- 表达式
23+((12*3-2)/4+34*5/7)+108/9
的后缀表达式是_____.
23 12 3 * 2 - 4 / 34 5 * 7 / + + 108 9 / +
- 已知链栈结点的定义如下:
typedef struct Snode
{ SElemType data; //数据域
struct Snode *next; //指针域
}LinkStack;
设栈顶指针为top,无头结点,请分别实现链栈的入栈和出栈操作。
//入栈
void WareHouse(LinkStack* &top){
LinkStack* p;//新建结点
p=(LinkStack*)malloc(sizeof(LinkStack));//开辟新空间
if(!p){
cout<<"overflow"<<endl;
exit(0);
}
else{
cin>>p->data;
p->next = top;
top = p ;
}
}
//出栈
void DeliverFromGodown(LinkStack* &top){
LinkStack *s;//
if(top){//判断是否为空
s=top;
top= top->next;
free(top);
}
}
- 完成下面函数:
形参dec为十进制数,函数将dec转换为八进制,并返回。
栈用顺序栈实现,算法中要实现栈的初始化(InitStack)和入栈(Push)出栈(Pop)操作。int DecimalToOctal(int dec)
//十进制 转换为 八进制
int DecimalToOctal(int dec){
SNode s;
s.top = -1;//栈的初始化
s.data =(int* )malloc(MAXSIZE*sizeof(int));
while(dec){//入栈
s.data[++s.top] = dec%8;
dec = dec/8;
}
while(s.top>=0){//出栈
cout<<s.data[s.top--];
}
cout<<endl;
}
栈与队列的知识点参考文章:链接 【数据结构】栈和队列的概念与基本操作代码实现