admin 管理员组文章数量: 1184232
2024年4月30日发(作者：php权限管理系统)
数据结构练习（栈和队列）
一、选择题
1．有5个元素a,b,c,d,e依次进栈，允许任何时候出栈，则可能的出栈序列是 C 。
A．baecd B．dceab C．abedc D．aebcd
2．下列有关递归的叙述，不正确的是 B 。
A．在计算机系统内，执行递归函数是通过自动使用栈来实现的。
B．在时间和空间效率方面，递归算法比非递归算法好。
C．递归函数的求解过程分为递推（进栈）和回推（出栈）两个阶段。
D．在递归函数中必须有终止递归的条件。
3．栈和队列均属于哪一种逻辑结构 A 。
A．线性结构 B．顺序结构 C．非线性结构 D．链表结构
4．设输入元素为1、2、3、P和A，输入次序为123PA，元素经过栈后得到各种输出序列，
则可以作为高级语言变量名的序列有 B 种。
A．4 B．5 C．6 D．7
5．一个队列的入队序列为a，b，c，d，则该队列的输出序列是 B 。
A．dcba B．abcd C．adcb D．cbda
6． 在一个链式队列中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算是
B 。
A. =s; f=s; B. =s; r=s;
C. =s; r=s; D. =f; f=s;
7．如果5个元素出栈的顺序是1、2、3、4、5，则进栈的顺序可能是 C 。
A．3、5、4、1、2 B．1、4、5、3、2
C． 5、4、1、3、2 D．2、4、3、1、5
8．已知一个栈的进栈序列为1，2，3，…，n，其出栈输出序列是p1，p2，p3，…，pn。
若p1=3，则p2的值 D 。
A．一定是2 B．一定是1 C．可能是1 D．可能是2
9．以1，2，3，…，n的顺序进队列，则可能的出队序列有 A 种。
A．1 B．n C．n(n+1)/2 D．
10．在计算递归函数时，如不用递归过程，应借助于 B 这种数据结构。
A. 线性表 B. 栈 C. 队列 D. 双向队列
二、填空题
1．栈和队列是一种特殊的线性表，其特殊性体现在是 操作受限 线性表。
设现有元素e1,e2,e3,e4,e5和e6依次进栈，若出栈的序列是e2,e4,e3,e6,e5,e1，则
栈S的容量至少是 3 。
2．顺序循环队列中，设队头指针为front，队尾指针为rear，队中最多可有MAX个元素，
采用少用一个存储单元的方法区分队满与队空问题，则元素入队列时队尾指针的变化为
rear=(rear+1)%MAX ；元素出队列时队头指针的变化为
front=(front+1)%MAX ；队列中的元素个数为 (rear-front+ MAX) %MAX 。 队
满的判别条件为为 (rear+1)%MAX=front ，队空的判别条件为
rear==front 。
3.一个中缀表达式 a+b*(a+c)-c/d的前缀表达式为 -+a*b+ac/cd ，后缀表达
式为 abac+*+cd/- 。一个后缀表达式 2 1 + 4 2 - * 3 +的值为 9 。
4．下列函数的功能是 计算1到n的平方和 。
def sum(n):
if n==0:
return 0
else:
return sum(n-1)+n*n
5．下列算法的功能 判断输入的字符串是否为回文 。
def func():
creatstack(S) #初始化构造一个空栈S
creatqueue(Q) #初始化构造一个空队列Q
str=input(“输入一个字符串：”)
for ch in str:
push(ch)
enqueue(ch)
while not isempty(S):
a=pop()
b=dequeue()
if a!=b:
return 0
return 1
三、解答题
1．用一维数组a[7] 顺序存储一个循环队列，队首和队尾指针分别用front和rear表示，
当前队列中已有5个元素：22，30，16，36，58，其中22是队首， front值为5，请
画出对应的存储状态图，当连续做两次出队运算后，再做两次入队运算，让元素80，55
依次进队，请再画出对应的存储状态图。
22
58
36
16
30
55
80
58
36
版权声明：本文标题：数据结构_python练习(栈和队列) 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1714441001a680245.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论