复习——栈和队列习题_用链接方式存储的队列,在进行删除运算时( )。

摘选了部分客观题

1.若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个（1≤j≤i）输出元素是（ D ）。
A. i-j-1 B. i-j C. j-i+1 D. 不确定的

因为这题并没有说明要一次进完再弹出，所以是不确定的。

---

2.向一个顺序栈插入一个元素时，首先把待插入元素写入到这个位置上，然后使栈顶后移一个位置。 （ X ）

根据我们老师的解释是需要先判断是否栈满，然后再进行赋值、移动
但在百度上看了一下，解释是这样的：向一个顺序栈插入一个元素时，首先使 栈顶指针 后移一个位置，然后把待插入元素 写入 （或插入） 到这个位置上
我觉得二者的差别是栈顶指针是指向当前栈顶还是栈顶元素的下一个位置…

---

3.用链接方式存储的队列，在进行删除运算时( D )。
A. 仅修改头指针 B.仅修改尾指针
C.头、尾指针都要修改 D.头、尾指针可能都要修改

在有头结点的链队列的出队操作中，一般只需修改队头指针
但当原队列中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改队尾指针，使其指向头结点，且删去此结点后队列变空。

---

4.两栈共享数组存储空间的好处是（ B ）
A.减少存取时间，降低上溢出发生的机率
B.节省存储空间，降低上溢出发生的机率
C.减少存取时间，降低下溢出发生的机率
D.节省存储空间，降低下溢出发生的机率

两个栈可以互相调节存储空间。只有两栈都满时才会发生上溢（栈满）。

---

5.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是（ C ）
A.6
B.4
C.3
D.2
这类题目为模拟题，即模拟进栈/队列、出栈/队列的操作
首先可以知道出栈的序列为：e2，e4，e3，e6，e5，e1
所以整个操作为：
e1，e2入栈（2个数据元素），e2出栈
e3，e4入栈（3个数据元素），e4,e3出栈
e5，e6入栈（3个数据元素），e6，e5，e1出栈。
可见至少需要存三个数据元素

---

6.设循环队列的下标范围是0~n-1，其头、尾指针分别为f和r，则其元素个数为(D)
A.r-f
B.r-f+1
C.(r-f)%n +1
D.(r-f+n)%n

举例子即可，固定结论

---

7.若栈采用顺序存储方式存储，现两栈共享空间V[1…m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（ B ）
A.|top[2]-top[1]|=0
B.top[1]+1=top[2]
C.top[1]+top[2]=m
D.top[1]=top[2]

这里的栈顶应该是有元素的地方吧，感觉题目给的不是很清晰，这个答案记住好了…

---

8.若某栈的输入序列为a，b，c，d，则所得出栈的输出序列不可能是（ D ）
A. a,c,b,d
B. b,c,d,a
C. c,d,b,a
D. d,c,a,b

这类题还是需要按照选项模拟啦…
只对D分析
如果第一个输出的是d，那么abc都已经压入栈中，但a不可能先于b出来。

---

9.每次从队列中取出的应是具有最高优先权的元素，这种队列就是优先级队列。（ √ ）

这个是定义，记住即可…

---

10.栈是实现过程和函数等子程序所必需的结构。（ √ ）

不要认为只要说的绝对就是错的…
在学计算机系统的时候的栈帧就说明了这个必需结构

---

11.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。（ √ ）

尾指针的下一个就是头结点了，这样就可以间接地起到头指针作用
这也是为什么在单循环链表中尾指针比头指针好的原因啦
(头指针找尾指针要遍历哦！)

---

12.消除递归不一定需要使用栈，此说法（ √ ）

这里的消除递归就是把递归函数变成不使用递归方法的函数
这点我们在后面的归并排序里可以看到，有递归算法和一种不递归的算法，且没有使用栈

---

13.任何一个递归过程都可以转换成非递归过程。（ √ ）

首先明确一点电脑是不会递归的
dalao的讨论，大家应该可以学到些知识。
小白菜在这里就不说话了…

---

14.循环队列不存在空间溢出问题。( X )

循环队列只是排除了假溢出的问题
而且他是顺序表，肯定会有溢出的=。=

---

15.即使对不含相同元素的同一输出序列进行两组不同的合法入栈和出栈组合操作，所得的输出序列也一定相同。( X )

先解释一下题目意思：给你一个无相同元素的序列，让你进行两个不同的入/出栈顺序操作，最后的出栈序列一定相同
这肯定错啊…

---

16.一个栈的入栈序列为1,2,3,…,n ，其出栈序列是 p 1 ,p 2 ,p 3 ,…p n 。若p 2 = 3，则 p 3 可能取值的个数是（C）
A. n-3
B. n-2
C. n-1
D.无法确定

通过p2==3可以知道，p1的可能值为 1、2、4
p1 ==1时，p3可以为2，4，5，6，7，…， n 共n-2个
p1 ==2时，p3可以为1，4，5，6，7，… ，n 共n-2个
p1 ==4时，p3可以为2，5，6，7，8，… ，n 共n-3个

将上述的可能值的集合取并集
p3可以为1,2,4,5,6，…n 共n-1种可能
所以答案选C

---

17.向一个循环队列中插入元素时，需要首先移动_____ 队尾指针_______，然后再向所指位置写入新插入的元素。

汗，这道题好像队尾指针指向的是有元素的地方…

---

加油加油，下一单元！