40 第二部分试题部分 9. 假设栈初始为空, 将中缀表达式 a/b+(cd-ef)/g 转换为等价的后缀表达式的过程中, 当扫描到 f 时, 栈中的元素依次是 ( ) 2014 年全国试题 2(2) 分 A. +(- B. +(- C. /+(- D. /+-* 10. 循环队列存放

Size: px

Start display at page:

Download "40 第二部分试题部分 9. 假设栈初始为空, 将中缀表达式 a/b+(c*d-e*f)/g 转换为等价的后缀表达式的过程中, 当扫描到 f 时, 栈中的元素依次是 ( ) 2014 年全国试题 2(2) 分 A. +(*- B. +(-* C. /+(*-* D. /+-* 10. 循环队列存放"

衣柚金
5 years ago
Views:

1 第 3 章栈和队列 39 第 3 章栈和队列一选择题 1. 为解决计算机主机与打印机之间速度不匹配问题, 通常设置一个打印数据缓冲区, 主机将要输出的数据依次写入该缓冲区, 而打印机则依次从该缓冲区中取出数据该缓冲区的逻辑结构应该是 ( ) 2009 年全国试题 1(2) 分 A. 栈 B. 队列 C. 树 D. 图 2. 设栈 S 和队列 Q 的初始状态均为空, 元素 a, b, c, d, e, f, g 依次进入栈 S 若每个元素出栈后立即进入队列 Q, 且 7 个元素出队的顺序是 b, d, c, f, e, a, g, 则栈 S 的容量至少是 ( ) 2009 年全国试题 2(2) 分 A. 1 B. 2 C. 3 D 若元素 a, b, c, d, e, f 依次进栈, 允许进栈退栈操作交替进行, 但不允许连续三次进行退栈操作, 则不可能得到的出栈序列是 ( ) 2010 年全国试题 1(2) 分 A. d, c, e, b, f, a B. c, b, d, a, e, f C. b, c, a, e, f, d D. a, f, e, d, c, b 4. 某队列允许在其两端进行入队操作, 但仅允许在一端进行出队操作若元素 a,b,c,d,e 依次入此队列后再进行出队操作, 则不可能得到的出队序列是 ( ) 2010 年全国试题 2(2) 分 A. b, a, c, d, e B. d, b, a, c, e C. d, b, c, a, e D. e, c, b, a, d 5. 元素 a, b, c, d, e 依次进入初始为空的栈中, 若元素进栈后可停留可出栈, 直到所有元素都出栈, 则在所有可能的出栈序列中, 以元素 d 开头的序列个数是 ( ) 2011 年全国试题 2(2) 分 A. 3 B. 4 C. 5 D 已知循环队列存储在一维数组 A[0..n-1] 中, 且队列非空时 front 和 rear 分别指向队头元素和队尾元素若初始时队列为空, 且要求第 1 个进入队列的元素存储在 A[0] 处, 则初始时 front 和 rear 的值分别是 ( ) 2011 年全国试题 3(2) 分 A. 0, 0 B. 0, n-1 C. n-1, 0 D. n-1, n-1 7. 已知操作符包括 '+','-','*','/','(' 和 ')' 将中缀表达式 a+b-a*((c+d)/e-f)+g 转换为等价的后缀表达式 ab+acd+e/f-*-g+ 时, 用栈来存放暂时还不能确定运算次序的操作符若栈初始时为空, 则转换过程中同时保存在栈中的操作符的最大个数是 ( ) 2012 年全国试题 2 (2) 分 A. 5 B. 7 C. 8 D 一个栈的入栈序列为 1, 2, 3,, n, 其出栈序列是 p 1, p 2, p 3,, p n 若 p 2 =3, 则 p 3 可能取值的个数是 ( ) 2013 年全国试题 2(2) 分 A. n-3 B. n-2 C. n-1 D. 无法确定

2 40 第二部分试题部分 9. 假设栈初始为空, 将中缀表达式 a/b+(c*d-e*f)/g 转换为等价的后缀表达式的过程中, 当扫描到 f 时, 栈中的元素依次是 ( ) 2014 年全国试题 2(2) 分 A. +(*- B. +(-* C. /+(*-* D. /+-* 10. 循环队列存放在一维数组 A[0..M-1] 中,end1 指向队头元素,end2 指向队尾元素的后一个位置假设队列两端均可进行入队和出队操作, 队列中最多能容纳 M-1 个元素, 初始时为空下列判断队空和队满的条件中, 正确的是 ( ) 2014 年全国试题 3(2) 分 A. 队空 :end1==end2; 队满 :end1==(end2+1) mod M B. 队空 :end1==end2; 队满 :end2==(end1+1) mod (M-1) C. 队空 :end2==(end1+1) mod M; 队满 :end1==(end2+1) mod M D. 队空 :end1==(end2+1) mod M; 队满 :end2==(end1+1) mod (M-1) 11. 已知程序如下 : int s(int n) { return (n<=0)? 0 : s(n-1) +n; } void main() { cout<< s(1); } 程序运行时使用栈来保存调用过程的信息, 自栈底到栈顶保存的信息依次对应的是 ( ) 2015 年全国试题 1(2 分 ) A. main()->s(1)->s(0) B. S(0)->S(1)->main() C. main()->s(0)->s(1) D. S(1)->S(0)->main() 12. 栈的特点是 ( 1 ), 队列的特点是 ( 2 ), 栈和队列都是 ( 3 ) 若进栈序列为 1, 2, 3, 4, 则 ( 4 ) 不可能是一个出栈序列 ( 不一定全部进栈后再出栈 ); 若进队列的序列为 1, 2, 3, 4, 则 ( 5 ) 是一个出队列序列北方交通大学 1999 一 1(5 分 ) 1, 2: A. 先进先出 B. 后进先出 C. 进优于出 D. 出优于进 3: A. 顺序存储的线性结构 B. 链式存储的线性结构 C. 限制存取点的线性结构 D. 限制存取点的非线性结构 4, 5: A. 3, 2, 1, 4 B. 3, 2, 4, 1 C. 4, 2, 3, 1 D. 4, 3, 2, 1 E. 1, 2, 3, 4 F. 1, 3, 2, 一个栈的输入序列为 1, 2, 3,, n, 若输出序列的第一个元素是 n, 输出第 i(1 i n) 个元素是 ( ) 电子科技大学 2012 一 4(2 分 ) 中山大学 1999 一 9(1 分 ) A. 不确定 B. n-i C. i D. n-i 设栈的输入序列为 1, 2, 3,, n; 输出序列为 p 1, p 2,, p n ; 若 p 1 =n, 则当 n i 1 时, p i 为 ( ); 若存在 k>1 使 p k =n, 则当 i>k 时,p i 为 ( ) 中国科学技术大学 1992 八 8(1 分 ) A. p i =n-i+1 B. p i 不确定 C. p i =n-(i-k) 15. 中缀表达式 (A+B)*(C-D)/(E-F*G) 的后缀表达式是 ( ) 北京邮电大学 2005 一 2(2 分 ) A. A+B*C-D/E-F*G B. AB+CD-*EFG*-/ C. AB+C*D-E/F-G* D. ABCDEFG+*-/-* 16. 某表达式的前缀形式为 :+ - * ^ ABCD/E/F+GH, 它的中缀形式为 ( ) 中国科学技术大学 1992 八 7(1 分 )

3 第 3 章栈和队列 41 A. A B *C-D+E/F/G+H B. A B *(C-D)+ E/ F G +H C. A B *C-D+E/(F/(G+H)) D. A B*(C-D) +E/(F/(G+H)) 17. 表达式 a*(b+c)-d 的后缀表达式是 ( ) 南京理工大学 2001 一 2(1.5 分 ) A. abcd*+- B. abc+*d- C. abc*+d- D. -+*abcd 18. 与中缀表达式 a*b+c/d-e 等价的前缀表达式是 ( ) 华中科技大学 2006 一 5(2 分 ) A. -+*ab/cde B. *+/-abcde C. abcde*+/- D. +*ab-/cde 19. 利用栈求表达式的值时, 设立操作数栈 OPND, 设 OPND 只有两个存储单元, 在下列表达式中, 不发生上溢的是 ( ) 四川大学 2005 A. A-B*(C-D) B. (A-B)*C-D C. (A-B*C)-D D. (A-B)*(C-D) 20. 有六个元素 6, 5, 4, 3, 2, 1 的顺序进栈, 问下列哪一个不是合法的出栈序列?( ) 北方交通大学 2001 一 3(2 分 ) A B C D 设栈的输入序列是 1, 2, 3, 4, 则 ( ) 不可能是其出栈序列中科院计算所 2000 一 10(2 分 ) 烟台大学 2007 一 4(2 分 ) A. 1, 2, 4, 3 B. 2, 1, 3, 4 C. 1, 4, 3, 2 D. 4, 3, 1, 2 E. 3, 2, 1, 四个元素 1,2,3,4 依次进栈, 出栈次序不可能出现 ( ) 种情况北京邮电大学 2005 一 1(2 分 ) A. 1, 2, 3, 4 B. 4, 1, 3, 2 C. 1, 4, 3, 2 D. 4, 3, 2, 如进栈序列 1, 2, 3, 4, 5 可能得到的出栈序列为( ) 上海交通大学 2005 四 1(2 分 ) A. 1, 2, 5, 3, 4 B. 3, 1, 2, 5, 4 C. 3, 2, 5, 4, 1 D. 1, 4, 2, 3, 5 E. 都不可能 24. 一个栈的入栈序列为 A, B, C, D, E, 则栈的不可能出栈序列是 ( ) 中南大学 2005 一 2(2 分 ) A. ABCDE B. EDCBA C. DECBA D. DCEAB 25. 设 n 个元素进栈序列是 1, 2, 3,, n, 其输出序列是 p1, p2, p3,, pn, 若 p1=3, 则 p2 的值为 ( ) 武汉大学 2006 A. 一定是 2 B. 一定是 1 C. 不可能是 1 D. 以上都不对 26. 某堆栈的输入序列为 a, b, c, d, 下面的四个序列中, 不可能是它的输出序列的是 ( ) 北京航空航天大学 2000 一 3(2 分 ) 北京邮电大学 1999 一 3(2 分 ) A. a, c, b, d B. b, c, d, a C. c, d, b, a D. d, c, a, b 27.( 多选 ) 若已知一个栈的入栈序列是 1, 2, 3, 4, 其出栈序列为 p 1, p 2, p 3, p 4, 则 p 2, p 4 可能为 ( ) 华中科技大学 2007 二 16(2 分 ) A. 2 4 B. 2 1 C. 4 3 D 输入序列为 ABC, 可以变为 CBA 时, 经过的栈操作为 ( ) 中山大学 1999 一 8(1 分 ) 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

4 42 第二部分试题部分 29. 依次读入数据元素序列 {a, b, c, d, e, f, g} 进栈, 每进一个元素, 机器可要求下一个元素进栈或弹栈, 如此进行, 则栈空时弹出的元素构成的序列是以下哪些序列?( ) 哈尔滨工业大学 2000 七 (8 分 ) A. {d, e, c, f, b, g, a} B. {f, e, g, d, a, c, b} C. {e, f, d, g, b, c, a} D. {c, d, b, e, f, a, g} 个圆盘的 Hanoi 塔, 总的移动次数为 ( ) 北京邮电大学 2005 一 3(2 分 ) A. 7 B. -8 C. 15 D 当字符序列 t3_ 作为下图输入时, 输出长度为 3 的, 且可用作 C 语言标识符的序列的有 ( ) 浙江大学 2004 二 (5 分 ) A. 4 个 B. 5 个 C. 3 个 D. 6 个 32. 和顺序栈相比, 链栈有一个比较明显的优势是 ( ) 北京理工大学 2006 五 6(1 分 ) A. 通常不会出现栈满的情况 B. 通常不会出现栈空的情况 C. 插入操作更容易实现 D. 删除操作更容易实现 33. 若一个栈以向量 V[1..n] 存储, 初始栈顶指针 top 为 n+1, 则下面 x 进栈的正确操作是 ( ) 南京理工大学 1998 一 13(2 分 ) 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 若栈采用顺序存储方式存储, 现两栈共享空间 V[1..m],top[i] 代表第 i 个栈 (i =1, 2) 栈顶, 栈 1 的底在 V[1], 栈 2 的底在 V[m], 则栈满的条件是 ( ) 南京理工大学 1999 一 14(1 分 ) 江苏大学 2005 一 2(2 分 ) A. top[2]-top[1] =0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 35. 栈在 ( ) 中应用中山大学 1998 二 3(2 分 ) A. 递归调用 B. 子程序调用 C. 表达式求值 D. A,B,C 36. 向一个栈顶指针为 h 的带头结点的链栈中插入指针 s 所指的结点时, 应执行 ( ) 北京理工大学 2005 十一 6(1 分 ) A. h->next=s; B. s->next=h; C. s->next=h; h->next=s; D. s->next=h->next; h->next=s; 37. 一个递归算法必须包括 ( ) 武汉大学 2000 二 2 A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D. 终止条件和迭代部分 38. function calc(x, y :integer) : integer; begin if y=1 then calc :=x else calc := calc (x, y-1)+x end; a b 均为正整数, 则 calc(a, b)=( ) 中国科学技术大学 1995 十四 14(6 分 ) A. a*(b-1) B. a*b C. a+b D. a+a

5 第 3 章栈和队列执行完下列语句段后,i 值为 ( ) 浙江大学 2000 一 6(3 分 ) 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. 无限递归 40. 设计一个判别表达式中左右括号是否配对出现的算法, 采用 ( ) 数据结构最佳西安电子科技大学 1996 一 6(2 分 ) A. 线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈 41. 递归过程或函数调用时, 处理参数及返回地址, 要用一种称为 ( ) 的数据结构福州大学 1998 一 1(2 分 ) A. 队列 B. 多维数组 C. 栈 D. 线性表 42. 允许对队列进行的操作有 ( ) 华中科技大学 2004 一 2(1 分 ) A. 对队列中的元素排序 B. 取出最近进队的元素 C. 在队头元素之前插入元素 D. 删除队头元素 43. 若用单链表来表示队列, 下面几种数据结构中, 最合适的是 ( ) 四川大学 2004 A. 带尾指针的非循环链表 B. 带尾指针的循环链表 C. 带头指针的非循环链表 D. 带头指针的循环链表 44. 对于循环队列 ( ) 北京理工大学 2005 十一 7(1 分 ) A. 无法判断队列是否为空 B. 无法判断队列是否为满 C. 队列不可能满 D. 以上说法都不是 45. 循环队列 A[0..m-1] 存放其元素值, 用 front 和 rear 分别表示队头和队尾, 则当前队列中的元素数是 ( ) 南京理工大学 2001 一 5(1.5 分 ) A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front 46. 若循环队列使用 C 数组 A[m] 存放其数据元素, 已知头指针 front 指向队首元素, 尾指针 rear 指向队尾元素后的空单元, 则当前队列中的元素个数为 ( ) 华中科技大学 2007 一 3(2 分 ) A. (rear-front+m)%m B. rear-front+1 C. rear-front D. rear-front 设顺序队列的容量为 MaxSize, 其头指针为 front, 尾指针为 rear, 空队列的条件为 ( ) 电子科技大学 2008 一 4(2 分 ) A. front=rear B. front=maxsize C. front+1=rear D. rear=0 48. 循环队列存储在数组 A[0..m] 中, 则入队时的操作为 ( ) 中山大学 1999 一 6(1 分 ) A. rear=rear+1 B. rear=(rear+1) mod(m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 49. 若用一个大小为 6 的数组来实现循环队列, 且当前 rear 和 front 的值分别为 0 和 3, 当从队列中删除一个元素, 再加入两个元素后,rear 和 front 的值分别为多少?( ) 浙江大学 1999 四 1(4 分 )

6 44 第二部分试题部分 A. 1 和 5 B. 2 和 4 C. 4 和 2 D. 5 和已知输入序列为 abcd, 经过输出受限的双向队列后能得到的输出序列有 ( ) 西安交通大学 1996 三 3(3 分 ) A. dacb B. cadb C. dbca D. bdac E. 以上答案都不对 51. 若以 1234 作为双端队列的输入序列, 则既不能由输入受限的双端队列得到, 也不能由输出受限的双端队列得到的输出序列是 ( 台大学 2007 一 5(2 分 ) ) 西安电子科技大学 1996 一 5(2 分 ) 烟 A B C D 最大容量为 n 的循环队列, 队尾指针是 rear, 队头是 front, 则队空的条件是 ( ) 南京理工大学 1999 一 16(2 分 ) A. (rear+1) MOD n=front B. rear=front C. rear+1=front D. (rear-l) MOD n=front 53. 栈和队的共同点是 ( ) 大连理工大学 2004 一 1(2 分 ) A. 都是先进后出 B. 都是后进先出 C. 只允许在端点处插入和删除元素 D. 没有共同点 54. 将递归算法转变成对应非递归算法时, 需要使用 ( ) 保存中间结果华中科技大学 2007 一 15(2 分 ) A. 栈 B. 队列 C. 二叉树 D. 单链表 55. 队列的先进先出特性是指 ( ) 武汉理工大学 2004 一 4(3 分 ) A. 最后插入队列中的元素总是最后被删除 B. 当同时进行插入删除操作时, 总是插入操作优先 C. 每当有删除操作时, 总要先做一次插入操作 D. 每次从队中删除的总是最早插入的元素 56. 设栈 S 和队列 Q 的初始状态为空, 元素 e1, e2, e3, e4, e5 和 e6 依次通过栈 S, 一个元素出栈后即进队列 Q, 若 6 个元素出队的序列是 e2, e4, e3, e6, e5, e1, 则栈 S 的容量至少应该是 ( ) 南京理工大学 2000 一 6(1.5 分 ) 哈尔滨工业大学 2004 二 3(1 分 ) A. 6 B. 4 C. 3 D 用单链表表示的链式队列的队头在链表的 ( ) 位置清华大学 1998 一 1(2 分 ) 烟台大学 2007 一 6(2 分 ) A. 链头 B. 链尾 C. 链中 58. 实现时需使用队列的运算是 ( ) 电子科技大学 2005 一 9(1 分 ) A. 递归过程 B. 二叉树的中序遍历 C. 图的深度优先搜索 D. 二叉树的层次遍历 59. 下列更合适表示队列的链表结构是 ( ) 北京理工大学 2006 九 6(1 分 ) A. 单向链表 B. 单向循环链表 C. 双向链表 D. 双向循环链表 60. 队列操作的原则是 ( ) 暨南大学 2010 一 2(2 分 ) A. 先进先出 B. 后进先出 C. 只能进行插入 D. 只能进行删除

7 第 3 章栈和队列执行 ( ) 操作时, 需要使用队列作辅助存储空间华中科技大学 2006 一 1(2 分 ) A. 查找哈希 (Hash) 表 B. 广度优先搜索网 C. 先序 ( 根 ) 遍历二叉树 D. 深度优先搜索网 62. 在下列栈的基本操作中,( ) 的初始条件不要求栈 S 已存在北京理工大学 2007 一 3(1 分 ) A. InitStack(&S) B. DestroyStack(&S) C. ClearStack(&S) D. StackEmpty(S) 63. 在算符优先级中, 算符 + 和 ( 的优先关系是 ( ) 北京理工大学 2007 一 5(1 分 ) A. + > ( B. + < ( C. + = ( D. 取决于它们出现的位置 64. 在带头结点的链队列中, 队头指针指向链表的 ( ) 北京理工大学 2007 一 4(1 分 ) A. 最后一个元素结点 B. 第一个元素结点 C. 头结点 D. 都不是二判断题 1. 同一组不重复输入序列执行不同的入出栈组合操作, 所得结果也可能相同 ( ) 北京邮电大学 2005 二 3(1 分 ) 2. 消除递归不一定需要使用栈 ( ) 中科院计算所 1998 二 2(2 分 ) 中国科技大学 1998 二 2(2 分 ) 3. 栈是实现过程和函数等子程序所必需的结构 ( ) 合肥工业大学 2000 二 2(1 分 ) 4. 栈和队列都是顺序存取的线性表, 但它们对存取位置的限制不同 ( ) 暨南大学 2011 三 6(1 分 ) 5. 两个栈共享一个向量空间的优点是其中一个栈可用该空间的一半或以上 ( ) 哈尔滨工程大学即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作, 所得的输出序列也一定相同 ( ) 北京邮电大学 1999 二 4(2 分 ) 中国海洋大学 2005 二 11(1 分 ) 7. 有 n 个数顺序 ( 依次 ) 进栈, 出栈序列有 Cn 种,Cn=[1/(n+1)]*(2n)!/[(n!)*(n!)] ( ) 北京邮电大学 1998 一 3(2 分 ) 8. 设栈采用顺序存储结构若已有 i-1 个元素入栈, 则将第 i 个元素入栈时, 入栈算法的时间复杂性为 O(i) ( ) 上海交通大学 1994 一 1(2 分 ) 9. 栈的输入序列是 1, 2,, n, 输出序列是 a 1, a 2,, a n, 若 a i =n(1 i n), 则有 :a i >a i+1 > >a n ( ) 中国科学技术大学 1991 一 5(2 分 ) 10. 设栈采用顺序存储结构, 若已有 n 个元素进栈, 则出栈算法的时间复杂性为 O(n) ( ) 上海海事大学 2005 一 2(2 分 ) 11. 堆栈和队列都是操作受限的线性表栈是插入和删除只能在一端进行的线性表 ; 队列是插入在一端进行, 删除在另一端进行的线性表 ( ) 吉林大学 2007 一 10(1 分 ) 12. 栈和队列均为操作受限的线性表 ( ) 中国海洋大学 2005 二 9(1 分 )

8 46 第二部分试题部分 13. 栈和队列都是限制存取点的线性结构 ( ) 中科院软件所 1999 六 (5)(2 分 ) 14. 任何一个递归过程都可以转换成非递归过程 ( ) 上海交通大学 1998 一 3(1 分 ) 15. 只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈 ( ) 上海交通大学 1998 一 4(1 分 ) 16. 中缀表达式 :(a+b)*d+e/(f+a*d)+c 的后缀表达式为 :ab+d*efad+/*+c+ ( ) 南京理工大学 2004 二 1(1 分 ) 17. 在链队列中, 即使不设置尾指针也能进行入队操作 ( ) 中南大学 2005 三 5(2 分 ) 18. 在链队列中执行出队操作是在队头进行的, 故不可能改变尾指针的值 ( ) 中国科学技术大学队列在程序调用时必不可少, 因此递归离不开队列 ( ) 北京邮电大学 2006 二 3(1 分 ) 20. 通常使用队列来处理函数或过程的调用 ( ) 南京航空航天大学 1997 一 5(1 分 ) 21. 队列逻辑上是一个下端和上端既能增加又能减少的线性表 ( ) 上海交通大学 1998 一 2(1 分 ) 22. 设尾指针的循环链表表示队列, 则入队和出队算法的时间复杂度均为 O(1) ( ) 中南大学 2003 一 5(1 分 ) 23. 栈和队列都是线性表, 只是在插入和删除时受到了一些限制 ( ) 北京邮电大学 2002 一 3(1 分 ) 烟台大学 2007 二 3(1 分 ) 三填空题 1. 若某堆栈初始为空,PUSH 与 POP 分别表示对栈进行一次进栈与出栈操作, 那么, 对于输入序列 a, b, c, d, e, 经过 PUSH, PUSH, POP, PUSH, POP, PUSH, PUSH 以后, 输出序列是北京航空航天大学 2006 一 3(1 分 ) 2. 在栈的 ADT 定义中, 除初始化操作外, 其他基本操作的初始条件都要求北京理工大学 2005 二 1(2 分 ) 3. 若已知一个栈的入栈序列是 1, 2, 3,, n, 其输出序列为 p1, p2, p3,..., pn, 若 p1=n, 则 pi 为北京交通大学 2005 二 2(2 分 ) 4. 栈是的线性表, 其运算遵循的原则北京科技大学 1997 一 3 5. 堆栈是一种操作受限的线性表, 它只能在线性表的进行插入和删除操作, 对栈的访问是按照的原则进行的暨南大学 2010 二 3(2 分 ) 6. 向栈中压入元素的操作是先, 后暨南大学 2011 二 5(2 分 ) 7. 设有一个空栈, 栈顶指针为 1000H( 十六进制 ), 现有输入序列为 1, 2, 3, 4, 5, 经过 PUSH, PUSH, POP, PUSH, POP, PUSH, PUSH 之后, 输出序列是, 而栈顶指针值是 H 设栈为顺序栈, 每个元素占 4 字节西安电子科技大学 1998 二 1(4 分 ) 8. 当两个栈共享一存储区时, 栈利用一维数组 stack(1, n) 表示, 两栈顶指针为 top[1] 与 top[2], 则当栈 1 空时,top[1] 为, 栈 2 空时,top[2] 为, 栈满时为南京理工大学 1997 三 1(3 分 ) 9. 两个栈共享空间时栈满的条件中山大学 1998 一 3(1 分 ) 北京邮电大学 2006

9 第 3 章栈和队列 47 一 3(2 分 ) 10. 在进行入栈运算时应先判别栈是否 (1) ; 在进行出栈运算时应先判别栈是否 (2) ; 当栈中元素为 n 个, 作进栈运算时发生上溢, 则说明该栈的最大容量为 (3) 为了增加内存空间的利用率和减少溢出的可能性, 由两个栈共享一片连续的空间时, 应将两栈的 (4) 分别设在内存空间的两端, 这样只有当 (5) 时才产生溢出山东工业大学 1994 一 1(5 分 ) 11. 多个栈共存时, 最好用作为存储结构南京理工大学 2001 二 7(2 分 ) 12. 有五个数据依次进栈 :1, 2, 3, 4, 5 在各种出栈的序列中, 以 3, 4 先出栈的序列有个 (3 在 4 之前出栈 ) 上海交通大学 1997 一 (6 分 ) 13. 顺序栈用 data[1..n] 存储数据, 栈顶指针是 top, 则值为 x 的元素入栈的操作是合肥工业大学 2001 三 2(2 分 ) 14. 表达式 23+((12*3-2)/4+34*5/7)+108/9 的后缀表达式是中山大学 1998 一 4(1 分 ) 北京邮电大学 2006 一 4(2 分 ) 15. 设 a=6, b=4, c=2, d=3, e=2, 则后缀表达式 abc-/de*+ 的值为南京邮电学院 2004 二 1(5 分 ) 16. 在按算符优先法求解表达式 3-1+5*2 时, 最先执行的运算是, 最后执行的运算是北京理工大学 2005 二 3(2 分 ) 17. 用 S 表示入栈操作,X 表示出栈操作, 若元素入栈顺序为 1, 2, 3, 4, 为了得到 1, 3, 4, 2 的出栈顺序, 相应的 S 和 X 操作串为同济大学又称作先进先出表重庆大学 2000 一队列的特点是北京理工大学 2000 二 2(2 分 ) 中南大学 2005 二 6(2 分 ) 20. 在具有 n 个元素的非空队列中插入一个元素或者删除一个元素的操作时间复杂度采用大 O 形式表示为北京航空航天大学 2006 一 4(1 分 ) 21. 循环队列是队列的一种存储结构南京理工大学 2005 二 10(1 分 ) 22. 循环队列的引入, 目的是为了克服厦门大学 2001 一 1(14/8 分 ) 23. 在循环队列中, 队列长度为 n, 存储位置从 0 到 n-1 编号, 以 rear 指示实际的队尾元素, 现要在此队列中插入一个新元素, 新元素的位置是南京邮电学院 2003 一 1(4 分 ) 24. 已知链队列的头尾指针分别是 f 和 r, 则将值 x 入队的操作序列是合肥工业大学 2000 三 3(2 分 ) 25. 区分循环队列的满与空, 只有两种方法, 它们是和北京邮电大学 2001 二 2(4 分 ) 26. 已知一循环队列的存储空间为 [m..n], 其中 n>m, 队头和队尾指针分别为 front 和 rear, 则此循环队列判满的条件是中南大学 2003 三 4(1 分 ) 27. 循环队列用数组 A[0..m-1] 存放其元素值, 已知其头尾指针分别是 front 和 rear, 则当前队列的元素个数是厦门大学 2000 六 1(16%/3 分 ) 北京交通大学 2005 二 9(2 分 ) 28. 用循环链表表示的队列长度为 n, 若只设头指针, 则出队和入队的时间复杂度分别是和 ; 若只设尾指针, 则出队和入队的时间复杂度分别是和西安电子

10 48 第二部分试题部分科技大学 2003 一 2(20/10 分 ) 29. 设循环队列容量为 Q, 当 rear<front 时, 队列长度为东南大学 2005 数据结构部分二 1(1 分 ) 30. 用一个大小为 1000 的数组来实现循环队列, 当前 rear 和 front 的值分别为 0 和 994, 若要达到队满的条件, 还需要继续入队的元素个数是北京工业大学 2005 二 3(3 分 ) 31. 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中如 123 存放成 321 请填空 : #include<stdio.h> void convert(char *a, int n) {int i; if(i=n/10) convert( _, i); *a= ; } main() {int number; char str[10]=" " scanf("%d", &number); convert(str, number); puts(str); } 浙江大学 2004 一 6(40/6 分 ) 32. 下面的程序将一个整数 e 压入堆栈 S, 实现堆栈的入栈操作, 请在空格处填上适当的语句实现该操作其中堆栈 S 的定义如下 : typedef struct{ int *base; int *top; int stacksize;}sqstack; int Push(SqStack S, int e) {if( (1) ) {S.base=(int*)realloc(S.base, (S.stacksize+1)*sizeof(int)); if( (2) ) {printf("not Enough Memory!\n"); return 0;} S.top= (3) ; S.stacksize= (4) ; } (5) ; return 1; } 西南交通大学 2005 四应用题 1. 假设以 I 和 O 分别表示入栈和出栈操作, 栈的初态和终态均为空入栈和出栈的操作序列表示为仅由 I 和 O 组成的序列 (1) 下面所示的序列中哪些是合法的?(2 分 ) A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO (2) 通过对 (1) 的分析, 给出判断一个给定序列是否合法的算法思想 (4 分 ) 哈尔滨工业大学 2005 四 2(6 分 ) 武汉大学 2000 五 2(12 分 ) 2. 假设以 S 和 X 分别表示入栈和出栈操作, 则对初态和终态均为空的栈操作可由 S 和 X 组成的序列表示 ( 如 SXSX)

11 第 3 章栈和队列 49 (1) 试指出判别给定序列是否合法的一般规则 (2) 两个不同合法序列 ( 对同一输入序列 ) 能否得到相同的输出元素序列? 如能得到, 请举列说明东南大学 1992 二 (10 分 ) 3. 设 a, b, c 三个元素的进栈次序是 a, b, c, 符号 PUSH 与 POP 分别表示对堆栈进行一次进栈操作与一次出栈操作 (1) 请分别写出所有可能的出栈序列以及获得该出栈序列的操作序列 ; (2) 指出不可能出现的出栈序列北京航空航天大学 2007 一 1(3 分 ) 4. 有 n 个数顺序依次进栈, 所有可能的出栈序列共有多少种? 厦门大学 2006 一 2(20/3 分 ) 5. 名词解释 : 栈吉林工业大学 1999 一 3(2 分 ) 燕山大学 1999 一 1(2 分 ) 6. 名词解释 : 队列大连海事大学 1996 一 6(1 分 ) 7. 什么是循环队列? 哈尔滨工业大学 2001 三 2(3 分 ) 河南大学 1998 一 4(3 分 ) 8. 有 5 个元素, 其入栈次序为 A, B, C, D, E, 在各种可能的出栈序列中, 第一个出栈元素为 C 且第二个出栈元素为 D 的出栈序列有哪几个? 武汉理工大学 2003 三 23(6 分 ) 北京航空航天大学 2008 一 2(4 分 ) 9. 设栈 S 和队列 Q 的初始状态为空, 元素依次通过栈 S, 一个元素出栈后即进入队列 Q 若这 6 个元素出队列的顺序是 , 则栈的容量至少应该是多少? 厦门大学 2006 一 1(20/3 分 ) 10. 递归算法和非递归算法比较有哪些主要的优点和缺点? 北京理工大学 2005 三 2(4 分 ) 11. 简述递归过程的关键点电子科技大学 2005 三 4(6 分 ) 12. 将两个栈 S1 和 S2 存入数组 V[1..m] 应如何安排最好? 请写出栈顶指针 top 的初始值和判断栈空栈满的条件是什么? 东南大学 1998 一 5(6 分 ) 烟台大学 2007 四 1(5 分 ) 13. 若有一个一维数组 A, 它的元素下标从 1 开始到 MAX 要在数组 A 中建立两个栈共享同一空间, 栈 S1 的栈顶指针为 topl, 栈 S2 的栈顶指针为 top2, 为了最大限度地利用数组 A 的空间, 则应该如何共享? 栈满和栈空的条件是什么? 北京理工大学 2006 十一 3(5 分 ) 14. 设输入序列为 a, b, c, d, 试写出借助一个栈可得到的两个输出序列和两个不能得到的输出序列北京科技大学 2001 一 4(2 分 ) 15. 试证明 : 若借助栈由输入序列 1, 2,, n 得到输出序列为 P 1, P 2,, P n ( 它是输入序列的一个排列 ), 则在输出序列中不可能出现这样的情形 : 存在着 i<j<k, 使 P j <P k <P i 上海交通大学 1998 二 (15 分 ) 16.(1) 什么是递归程序? (2) 递归程序的优缺点是什么? (3) 递归程序在执行时, 应借助于什么来完成? (4) 递归程序的入口语句出口语句一般用什么语句实现? 大连海事大学 1996 二 4(4 分 ) 17. 试推导出总盘数为 n 的 Hanoi 塔的移动次数北京邮电大学 2001 四 3(5 分 ) 18. 用一个数组 S( 设大小为 MAX) 作为两个堆栈的共享空间请说明共享方法, 栈满 / 栈空的判断条件, 并用 C 或 Pascal 设计公用的入栈操作 push(i,x), 其中 i 为 0 或 1, 用于表示

12 50 第二部分试题部分栈号,x 为入栈值浙江大学 1998 五 2(7 分 ) 19. 在一个算法中需要建立多个堆栈时可以选用下列三种方案之一, 试问 : 这三种方案之间相比较各有什么优缺点? (1) 分别用多个顺序存储空间建立多个独立的堆栈 ; (2) 多个堆栈共享一个顺序存储空间 ; (3) 分别建立多个独立的链接堆栈北京航空航天大学 1998 一 6(4 分 ) 20. 在某程序中, 有两个栈共享一个一维数组空间 SPACE[N] SPACE[0] SPACE[N-1] 分别是两个栈的栈底 (1) 对栈 1 栈 2, 试分别写出 ( 元素 x) 入栈的主要语句和出栈的主要语句 (2) 对栈 1 栈 2, 试分别写出栈满栈空的条件北京理工大学 1999 二 2(8 分 ) 21. 用栈实现将中缀表达式 8-(3+5)*(5-6/2) 转换成后缀表达式, 画出栈的变化过程图南京航空航天大学 2001 五 (10 分 ) 22. 将表达式 (a+b)*c+d-(e+g)*h 改写成后缀表达式吉林大学 2007 二 4(3 分 ) 23. 在表达式中, 有的运算符要求从右到左计算, 如 A**B**C 的计算次序应为 (A**(B**C)), 这在由中缀生成后缀的算法中是怎样实现的?( 以 ** 为例说明 ) 东南大学 1993 一 2(6 分 ) 1997 一 1(8 分 ) 24. 有字符串次序为 3*-y-a/y^2, 利用栈, 给出将次序改为 3y-*ay2^/- 的操作步骤 ( 可用 X 代表扫描该字符串过程中顺序取一个字符进栈的操作, 用 S 代表从栈中取出一个字符加入到新字符串尾的出栈操作例如,ABC 变为 BCA 的操作步骤为 XXSXSS ) 东北大学 2001 一 4(4 分 ) 25. 用栈作工具, 将十进制数 9027 转换为八进制数, 试列出运算过程和栈中元素的变化过程华中科技大学 2006 四 1(10 分 ) 26. 画出对算术表达式 A-B*C/D-E F 求值时, 操作数栈和运算符栈的变化过程东南大学 2000 一 3(6 分 ) 27. 设输入元素为 P 和 A, 输入次序为 123PA, 如图 ( 编者略 ) 元素经过栈后到达输出序列, 当所有元素均到达输出序列后, 有哪些序列可以作为高级语言的变量名? 中山大学简述顺序存储队列的假溢出的避免方法及队列满和空的条件山东大学 2000 一 2(4 分 ) 29. 简要叙述循环队列的数据结构, 并写出其初始状态队列空队列满时的队首指针与队尾指针的值南京航空航天大学 1995 七 (5 分 ) 30. 队列可以用循环单链表来实现, 故可以只设置一个头指针或者只设置一个尾指针请你分析对于循环单链表实现的队列, 用哪种方案更合适北京大学 2003 五 1(5 分 ) 31. 利用两个栈 sl s2 模拟一个队列时, 如何用栈的运算实现队列的插入删除以及判队空运算请简述这些运算的算法思想北京邮电大学 1992 一 1 东南大学 1999 一 1(7 分 ) 32. 利用两个栈 s1 和 s2 模拟一个队列时, 如何用栈的运算实现入队出队和判断队列空的运算?

13 第 3 章栈和队列 51 北京理工大学 2006 六 1(50/7 分 ) 33. 如果用一个循环数组 q[0..m-1] 表示队列时, 该队列只有一个队列头指针 front, 不设队列尾指针 rear, 而改置计数器 count 用以记录队列中结点的个数 (1) 编写实现队列的三个基本运算 : 判空入队出队 (3 分 ) (2) 队列中能容纳元素的最多个数是多少?(1 分 ) 东北大学 2002 一给出循环队列中元素个数的计算式 ( 设队最大长度为 N, 队首指针 FRONT, 队尾指针 REAR) 西北大学 2000 二 7(5 分 ) 35. 顺序队列一般应该组织成为环状队列的形式, 而且一般队列头或尾其中之一应该特殊处理例如, 队列为 listarray[0..n-1], 队列头指针为 front, 队列尾指针为 rear, 则 listarray[rear] 表示下一个可以插入队列的位置请解释其原因北京大学 1999 一 3(20/3 分 ) 36. 设一个双端队列, 元素进入该队列的次序为 a,b,c,d 求既不能由输入受限的双端队列得到, 又不能由输出受限的双端队列得到的输出序列中山大学 1999 一 4(3 分 ) 五算法设计题 1. 设有两个栈 S 1 S 2 都采用顺序栈方式, 并且共享一个存储区 [O..maxsize-1], 为了尽量利用空间, 减少溢出的可能, 可采用栈顶相向, 迎面增长的存储方式试设计 S 1 S 2 有关入栈和出栈的操作算法哈尔滨工业大学 2001 七 (12 分 ) 2. 设从键盘输入一整数的序列 :a 1, a 2, a 3,, a n, 试编写算法实现 : 用栈结构存储输入的整数, 当 a i -1 时, 将 a i 进栈 ; 当 a i =-1 时, 输出栈顶整数并出栈算法应对异常情况 ( 入栈满等 ) 给出相应的信息南京航空航天大学 1998 六 (10 分 ) 3. 设表达式以字符形式已存入数组 E[n] 中,'#' 为表达式的结束符, 试写出判断表达式中括号 ('(' 和 ')') 是否配对的 C 语言描述算法 :EXYX(E) ( 注 : 算法中可调用栈操作的基本算法 ) 北京科技大学 2001 九 1(10 分 ) 4. 假设称正读和反读都相同的字符序列为回文, 例如,'abcba' 是回文,'abcde' 和 'ababab' 则不是回文试写一个算法判别读入的一个以 '@' 为结束符的字符序列是否是回文中国海洋大学 2007 八 (15 分 ) 5. 设计一个算法, 判断一个算术表达式中的括号是否配对算术表达式保存在带头结点的单循环链表中, 每个结点有两个域 :ch 和 link, 其中 ch 域为字符类型 6. 设整数序列 a 1, a 2,, a n, 给出求解最大值的递归程序南京航空航天大学 2000 六 7. 线性表中元素存放在向量 A(1,, n) 中, 元素是整型数试写出递归算法求出 A 中的最大和最小元素北京邮电大学 1994 八 (10 分 ) 8. 已知求两个正整数 m 与 n 的最大公因子的过程用自然语言可以表述为反复执行如下动作 : 第一步 : 若 n 等于零, 则返回 m; 第二步 : 若 m 小于 n, 则 m 与 n 相互交换 ; 否则, 保存 m, 然后将 n 送 m, 将保存的 m 除以 n 的余数送 n (1) 将上述过程用递归函数表达出来 ( 设求 x 除以 y 的余数可以用 x MOD y 形式表示 ) (2) 写出求解该递归函数的非递归算法北京航空航天大学 2001 五 (15 分 ) 9. 已知 Ackermann 函数定义如下 :

14 52 第二部分试题部分 n 1 当 m 0时 Ack( mn, ) Ack( m 1,1) 当 m 0, n 0时 Ack( m 1, Ack( m, n 1)) 当 m 0, n 0时 (1) 写出 Ack(2, 1) 的计算过程 (2) 写出计算 Ack(m, n) 的非递归算法北京师范大学 2005 六 2(15 分 ) 北京航空航天大学 1999 六 (15 分 ) 10. 设计算法以求解从集合 {1..n} 中选取 k(k n) 个元素的所有组合例如, 从集合 {1..4} 中选取 2 个元素的所有组合的输出结果为 :1 2, 1 3, 1 4, 2 3, 2 4, 3 4 合肥工业大学 2000 五 5(8 分 ) 11. 对于任意的无符号的十进制整数 m, 写出将其转换为十六进制整数的算法 ( 转换仅要求能够输出正确的十六进制的整数即可 ) 兰州大学 2000 九 (10 分 ) 12. 已知递归函数 F(m)( 其中 DIV 为整除 ): 1 当 m 0时 Fm ( ) mf( m DIV 2) 当 m 0时 (1) 写出求 F(m) 的递归算法 ; (2) 写出求 F(m) 的非递归算法北京师范大学 2003 五 3(15 分 ) 13. 试设计算法,n 为大于等于 0 的整数, 利用堆栈设计下列函数的非递归算法 1 n 0 Pn ( ) n* P( n/2) n 0 天津大学 2006 二 2(7 分 ) 14. 已知有 n 个元素存放在向量 S[1..n] 中, 其值各不相同, 请写一递归算法, 生成并输出 n 个元素的全排列中国科学技术大学 1992 十三 (20 分 ) 苏州大学 2005 五 (15 分 ) 15. 请利用两个栈 S1 和 S2 来模拟一个队列已知栈的三个运算定义如下 :PUSH(ST, x): 元素 x 入 ST 栈 ;POP(ST, x):st 栈顶元素出栈, 赋给变量 x;sempty(st): 判 ST 栈是否为空那么如何利用栈的运算来实现该队列的三个运算 :enqueue: 插入一个元素入队列 ;dequeue: 删除一个元素出队列 ;queue_empty: 判队列为空 ( 请写明算法的思想及必要的注释 ) 上海交通大学 1999 二 (12 分 ) 厦门大学 2005 六 (15 分 ) 16. 设结点结构为 (data, link), 试用一个全局指针 p 和某种链接结构实现一个队列, 画出示意图, 并给出入队 addq 和出队 deleteq 过程, 要求它们的时间复杂性都是 O(1)( 不计 new 和 dispose 时间 ) 东南大学 1996 二 (10 分 ) 17. 设以带头结点的循环链表表示队列, 只设有队尾指针请写出入队出队队列长度的算法及处理逻辑流程图南京航空航天大学 2004 一 2(10 分 ) 山东科技大学 2002 一 2(6 分 ) 18. 编程 : 假设以数组 Q[m] 存放循环队列中的元素, 同时以 rear 和 length 分别指示环形队列中的队尾位置和队列中所含元素的个数试给出该循环队列的队空条件和队满条件, 并写出相应的初始化 (initqueue) 插入(enqueue) 和删除 (dlqueue) 元素的操作天津大学 2002 一 5(10 分 )

15 第 3 章栈和队列如果允许在循环队列的两端都可以进行插入和删除操作要求 : (1) 写出循环队列的类型定义 ; (2) 写出从队尾删除和从队头插入的算法北方交通大学 1994 三 (12 分 ) 20. 已知 Q 是一个非空队列,S 是一个空栈仅用队列和栈的 ADT 函数和少量工作变量, 使用 Pascal 或 C 语言编写一个算法, 将队列 Q 中的所有元素逆置栈的 ADT 函数有 : makeempty(s:stack); // 置空栈 push(s:stack;value:datatype); // 新元素 value 进栈 pop(s:stack):datatype; // 出栈, 返回栈顶值 isempty(s:stack):boolean; // 判栈空否队列的 ADT 函数有 : enqueue(q:queue:value:datatype); // 元素 value 进队 dequeue(q:queue):datatype; // 出队列, 返回队头值 isempty(q:queue):boolean; // 判队列空否清华大学 2000 六 (12 分 ) 华南理工大学 2005 二 7(4 分 ) 21. 将 n 个队列顺序映射到数组 v[l..m] 中, 每一队列在 v 中表示为一循环队列试画出其示意图并写出对应这种表示的 addq 和 deleteq 过程东南大学 1993 二 (20 分 )

第三章栈和队列

第三章栈和队列第 3 章栈 3.1 ADT 栈 3.2 ADT 栈的实现 3.3 ADT 栈的应用 2008-3-31 福州大学数学与计算机科学学院吴英杰 1 1 栈的定义和特点 3.1 ADT 栈 (stack) 定义 : 限定仅在表首进行插入或删除操作的线性表, 表首栈顶, 表尾栈底, 不含元素的空表称空栈特点 : 先进后出 (FILO) 或后进先出 (LIFO) 进栈栈顶... an... 出栈栈

40 第二部分试题部分 9. 假设栈初始为空, 将中缀表达式 a/b+(c*d-e*f)/g 转换为等价的后缀表达式的过程中, 当扫描 到 f 时, 栈中的元素依次是 ( ) 2014 年全国试题 2(2) 分 A. +(*- B. +(-* C. /+(*-* D. /+-* 10. 循环队列存放

40 第二部分试题部分 9. 假设栈初始为空, 将中缀表达式 a/b+(cd-ef)/g 转换为等价的后缀表达式的过程中, 当扫描到 f 时, 栈中的元素依次是 ( ) 2014 年全国试题 2(2) 分 A. +(- B. +(- C. /+(- D. /+-* 10. 循环队列存放