发布时间 : 星期六 文章数据结构习题更新完毕开始阅读
C．减少存取时间，降低上溢发生的机率 D．节省存储空间，降低下溢发生的机率 12. 对于栈操作数据的原则是（ ）。
A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序
13. 在作进栈运算时,应先判别栈是否( ① ),在作退栈运算时应先判别栈是否( ② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时，才产生上溢。
①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶 D. 栈底 ⑤: A. 两个栈的栈顶同时到达栈空间的中心点.
B. 其中一个栈的栈顶到达栈空间的中心点.
C. 两个栈的栈顶在栈空间的某一位置相遇.
D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底. 14. 输入序列为ABC，可以变为CBA时，经过的栈操作为（ ）
A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop
15. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 16. 栈和队列的共同点是（ ）。
A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点
18. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（ ）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的
19. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是（ ）。 A. a，c，b，d B. b, c，d，a C. c, d，b, a D. d, c，a，b 20. 若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是( )。 A．top=top+1; V [top]=x B. V [top]=x; top=top+1 C. top=top-1; V [top]=x D. V [top]=x; top=top-1
21. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底
13
在v[1]，栈2的底在V[m]，则栈满的条件是（ ）。
A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 22. 栈在（ ）中应用。
A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，Ｂ，Ｃ 23. 一个递归算法必须包括（ ）。
A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分 24. 执行完下列语句段后，i值为：（ ） int f(int x)
{ return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1));
A．2 B. 4 C. 8 D. 无限递归 25. 表达式a*(b+c)-d的后缀表达式是( )。
A．abcd*+- B. abc+*d- C. abc*+d- D. -+*abcd
26. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。 A．线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈
27. 用链接方式存储的队列，在进行删除运算时（ ）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改
28. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( )。
A．仅修改队头指针 B. 仅修改队尾指针
C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改
29. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（ ）的数据结构。 A．队列 B．多维数组 C．栈 D. 线性表
30. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）。
A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m
31. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )
14
A. 1和 5 B. 2和4 C. 4和2 D. 5和1
32. 已知输入序列为abcd 经过输出受限的双向队列后能得到的输出序列有（ ）。 A. dacb B. cadb C. dbca D. bdac E. 以上答案都不对 33. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ ）。
A. (rear+1) MOD n=front B. rear=front
C．rear+1=front D. (rear-l) MOD n=front
34. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。 A． 6 B. 4 C. 3 D. 2
二、填空题
1．若一个栈以数组V[1..n]存储，初始栈顶指针为top，元素X的入栈操作为______________。 2. 栈是一种限定在表的一端进行插入和删除的线性表，又被称为___________的线性表。 3. 如果一个对象部分地包含自己，或自己定义自己，则称这个对象是_________的对象。
4.设有一个顺序栈S，元素S1，S2，S3，S4，S5，S6依次进栈，如果6个元素的出栈顺序为S2，S3，S4，S6，S5，S1，则顺序栈的容量至少应为 。
5.通常程序在调用另一个程序时，都需要使用一个 来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。
6.在一个链式栈中，若栈顶指针等于NULL则为________。 7．栈顶的位置是随着_____操作而变化的。
8．在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针 ，当删除一个队列元素时，头指针 。
9.循环队列用数组A[0..m-1]存放其元素值。已知其头尾指针分别是front和rear，则当前队列中的元素个数是 ，判断队空的条件是 。
10．循环队列Q中，front和rear分别指示队列头元素及队尾元素的位置，最大队列长度为maxsize，则判断队空的条件是 ，队满的条件是 。
11.队列的插入操作在 进行，删除操作在 进行。
12.在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针 ，当删除一个队列元素时，头指针 。
13．栈是___ ____的线性表，其运算遵循_______的原则。 14．____ ___是限定仅在表尾进行插入或删除操作的线性表。
15. 设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过
15
PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_______，而栈顶指针值是_______H。设栈为顺序栈，每个元素占4个字节。
16. 当两个栈共享一存储区时，栈利用一维数组stack(1,n)表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为_______，栈2空时 ，top[2]为_______，栈满时为_______。 17．两个栈共享空间时栈满的条件_______。
18．在作进栈运算时应先判别栈是否 ;在作退栈运算时应先判别栈是否 ；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为 。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的 分别设在内存空间的两端，这样只有当 时才产生溢出。
19. 多个栈共存时，最好用_______作为存储结构。
20．表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是_______。
21. 循环队列的引入，目的是为了克服_______。 22. 已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是_______。 23．区分循环队列的满与空，只有两种方法，它们是______和______。
24. 设循环队列存放在向量sq.data[0:M]中，则队头指针sq.front在循环意义下的出队操作可表示为_______，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear）,则队满的条件为_______。 25．表达式求值是_______应用的一个典型例子。
三、判断题
1.栈和队列都是顺序存取的的线性表，但它们对存取位置的限制不同。 2.通常递归的算法简单、易懂、容易编写，但执行的效率不高。 3.在一个顺序存储的循环队列中, 队头指针指向队头元素的后一个位置。 4.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。 5.用非递归方法实现递归算法时一定要使用递归工作栈。 6．队列只允许在表的一端进行插入，而在另一端删除元素。
四、应用题
1．设有一个顺序栈S，元素s1， s2， s3， s4， s5， s6依次进栈，如果6个元素的出栈顺序为s2， s3， s4， s6， s5， s1，则顺序栈的容量至少应为多少？ 2. 试推导出当总盘数为n的Hanoi塔的移动次数。
3. 用栈实现将中缀表达式8-(3+5)*(5-6/2)转换成后缀表达式，画出栈的变化过程图。
16