数据结构练习第三章栈和队列

1、、选择题数据结构练习第三章栈和队列1. 栈和队列的共同特点是 （）A. 只允许在端点处插入和删除元素B. 都是先进后出C. 都是先进先出D. 没有共同点2.A.C.3.A.C.4.A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D. 头、尾指针可能都要修改设用链表作为栈的存储结构则退栈操作（ ）。 必须判别栈是否为满B. 必须判别栈是否为空判别栈元素的类型D. 对栈不作任何判别设指针变量 front 表示链式队列的队头指针， 指针变量 rear 表示链式队列的 队尾指针，指针变量s指向将要入队列的结点X,则入队列的操作序列为A.front-next=s ；front=s ； B.

2、s-next=rear ；rear=s ；C. rear-next=s ；rear=s ；D. s-next=front ；front=s ；7. 设指针变量 top 指向当前链式栈的栈顶， 则删除栈顶元素的操作序列为A.top=top+1;B. top=top-1;C. top-next=top;D. top=top-next;8. 队列是一种（）的线性表。A. 先进先出 B. 先进后出 C. 只能插入 D. 只能删除9. 设输入序列 1、2、3、,、 n 经过栈作用后，输出序列中的第一个元素是 则输出序列中的第 i 个输出元素是（C. n+l -i D. 不能确定 3、4、5、6，则通过栈

3、的作用后可以得到的输出序列向顺序栈中压入新元素时，应当 先移动栈顶指针， 再存入元素 先后次序无关紧要 允许对队列进行的操作有 对队列中的元素排序 在队头元素之前插入元素oB.）。B先存入元素， 再移动栈顶指针同时进行用链接方式存储的队列，在进行插入运算时B.取出最近进队的元素D. 删除队头元素（ ）.5 A. C.6）。）。n，）。A. n-i B. n-1-i 10设输入序列为 1、2、 为（ ）。A. 5 ，3，4，6，1，2C. 3 ，1，2，5，4，6 11队列的删除操作是在（A.队首B12当利用大小为 则退栈时，用（A. top+;13.队列的插入操作是在（B. 3 ，2，5，6，

4、4，1D. 1，5， 4， 6，2，3）进行。.队尾 C .队前N 的数组顺序存储一个栈时，假定用 ）语句修改 top 指针。B . top=0; C . top-;）进行。D 队后 top = = N 表示栈空，top=N;32A.队首B .队尾C队前D.队后14. 若已有一个栈，输入序列为A, B, C, D, E,那么下面哪种序列不可能得到？ （）A. ABCDE B . EDCBAC . BAEDCD. ECDBA（d） 注意 : 入栈和出栈操作可以交替进行，因此就可能有多种输出序列了。15. 栈和队列共同具有的特点是（）A.都是先进后出B.都是先进先出C.只允许在端点进行操作运算D.

5、既能先进先出，也能先进后出16. 若用一个有 6个单元的数组来实现循环队列，rear 和 front 的初值分别为 0 和3。则从队列中删除一个元素， 再添加两个元素后， rear 和 front 的值分别 为（ ）C.4 和 2 D.5 和 1A.1 和5B.2 和417. 一个栈的入栈序列是a，b，c，d，e，贝U栈的输出序列不可能 是（）A. dceabB. decba18. 元素大小为 1 个单元，容量为 n 个单元的非空顺序栈中， 以地址高端为栈底，以 top 作为栈顶指针，贝出栈处理后， top 的值应修改为 （）A. top=topB. top=n-1 C. top=top-1D

6、. top=top+119. 设有一个栈，按A B、C D的顺序进栈，贝冋能为出栈序列的是（）A.DCBA B.CDAB C.DBACD.DCAB20. 在一个具有 n 个单元的顺序栈中，假定以地址低端（即 0单元）作为栈底， 以 top 为栈顶指针，贝当做出栈处理时，A.top+B.top-C.top21. 关于栈和队列的说法中正确的是（A. 栈和队列都是线性结构B. 栈是线性结构，队列不是线性结构C. 栈不是线性结构，队列是线性结构D. 栈和队列都不是线性结构22. 设一个栈的输入序列是 a， b， c， d， 许出栈）不可能出现的是（ ）A. a， b， c， dC.d， c， b， a

7、C. edcbaD. abcdetop 变化为 ( ) 不变 D.top=0)则所得到的输出序列（输入过程中允B.a，D.c，b，d，c d，a，b)B.s.elem top+1 =e； s.top=s.top+1 ；D.s.top=s.top+1 ；s.elem top =e；23. 在具有m个单元的循环队列中，队头指针为front ，队尾指针为rear，则队 满的条件是（ ）A. front=rearB.（front+1）%m=rearC.rear+1=frontD.（rear+1）%m=frontD)。24. 循环队列存储在数组 A0.m 中，贝入队时的操作为 （A. rear=rear

8、+1B. rear=（rear+1） % （m-1）C. rear=（rear+1） % m D. rear=（rear+1） % （m+1）25. 顺序栈 S 中 top 为栈顶指针，指向栈顶元素所在的位置， elem 为存放栈的 数组，贝元素 e 进栈操作的主要语句为（A.s.elem top =e； s.top=s.top+1 ；C.s.top=s.top+1 ； s.elem top+1 =e；26. 循环队列sq中，用数组elem 0 25存放数据元素，sq.front指示队头元素的前一个位置， sq.rear 指示队尾元素的当前位置， 设当前 sq.front 为 20， sq.r

9、ear 为 12，则当前队列中的元素个数为（）A.8 B.16 C.1727. 有关栈的描述，正确的是（）A. 栈是一种先进先出的特殊的线性表B. 只能从栈顶执行插入、删除操作C. 只能从栈顶执行插入、栈底执行删除D. 栈顶和栈底均可执行插入、删除操作28. 设顺序循环队列 Q0： 指向队头元素的前一位置， 列中的元素个数为（ ）。A. R-F B. F-R29. 设一数列的输入顺序为（ ）。A. 3,2,5,6,4,1C. 2,4,3,5,1,6D.18M-1的头指针和尾指针分别为F和R,头指针F总是 尾指针R总是指向队尾元素的当前位置，则该循环队C. （R-F+M） MD. （F-R+M）

10、 M1,2,3,4,5,6 ,通过栈操作不可能排成的输出序列为B . 1,5,4,6,2,3. 4,5,3,6,2,1A,B,C,D,E ，则下列（ ）是不可能的出栈30. 设有一个栈，元素的进栈次序为 序列。A . A,B,C,D,EBC. E,A,B,C,DD31. 在具有N个单元的顺序存储循环队列中，假定 front和rear分别为对头指 针和对尾指针，则判断对满的条件为（A. front= rear C. front-rear=1DB,C,D,E,AE,D,C,B,A32. 一个元素进入队列的时间复杂度是（A. O（1）B . O（n）33. 若让元素 1 ， 2， 3 依次进栈，A.

11、3， 2， 1B.2C.3， 1， 2D.1）。B. （rear+1）%MAXSIZE=front . rear%MAXSIZE=front ）。C . O（n2）D则出栈次序不可能出现（， 1， 3， 3， 2O（log 2n）种情况。34. 假定一个链队的队首和队尾指针分别为 是（ ）。A.front=NULL C.rear!=NULL35. 若让元素 a， b， c 依次进栈，A. cbaB. bac36. 在一个链队列中，假定 点的操作应执行（ ）。A. front-next=s; front=s; C. rear-next=s; rear=s;37. 栈的插入与删除操作在A. 栈顶B

12、. 栈底front 和 rear ，则判断队空的条件B.front!=NULL D . front=rear则出栈次序不可能出现（CcabD和 rear 分别为队头和队尾指针,则插入 *s 结）种情况。acbfronts-next=rear; rear=s;D s-next=front; front=s; ）进行。任意位置 D. 指定位置38.当利用大小为N的一维数组顺序存储一个栈时，假定用 top= 1表示栈空,C.则向这个栈插入一个元素时,首先应执行（）语句修改 top 指针。Atop+ ；B top- ； Ctop=NULL ； Dtop ；39当采用顺序存储方式存储队列时， 可能出现存

13、储空间剩余， 而不允许继续入 队的情况，称为(A.溢出B .假溢出 C .队列不能用顺序存储方式 D .数组存储空间过小 40.当利用大小为N的一维数组顺序存储一个循环队列时， 该队列的最大长度为 ( )。A.N-2B.N-1 C.N D.N+141从一个循环顺序队列删除元素时，首先需要()。A.前移一位队首指针B .后移一位队首指针C.取出队首指针所指位置上的元素D.取出队尾指针所指位置上的元素42循环队列存储在数组 A0.m 中，则入队时的操作为 ( ) 。A. rear=rear+1C. rear=(rear+1) % m)。B. rear=(rear+1) % (m-1)D. rear

14、=(rear+1) % (m+1)434 个园盘的 Hahoi 塔，总的移动次数为 ( )A.7 B. 8 44对于栈操作数据的原则是( A. 先进先出 B. 后进先出 45有六个元素 6， 5， 4， 3， 序列？( )A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 46设栈的输入序列是 1，A. 1 ， 2， 4， 3，D. 4 ， 3， 1， 2， 47如进栈序列A1,2,5,3,4 B 可能1，2，B. 2E. 3 2，3， 3,1,2,5,44，2，C.15)。C. 后进后出 D. 不分顺序 的顺序进栈，问下列哪一个不是合法的出栈D.16C. 3 4 6 5 2 1D.

15、2 3 4 1 5 6)不可能是其出栈序列。4，C. 1，4，3，2，4，4,则，1，3，2，1， 5。可能得到的出栈序列为 ( )C 3,2,5,4,1D 1,4,2,3,5 E 都不3，48一个栈的入栈序列为 A,B,C,D,E ，则栈的不可能的出栈序列是 ( )A. ABCDE B. EDCBA C. DECBA 49 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)=( ) A.a*(b-1)B.

16、a*b50执行完下列语句段后，iint f(int x) return (x0) ? x* f(x-1):2); int i ;i =f(f(1);A2B. 4C. a+b 值为：(D. a+a )。C. 8D.)。D.DCEAB无限递归51表达式 a*(b+c)-d 的后缀表达式是 ( Aabcd*+-B. abc+*d- C. abc*+d- D. -+*abcd52允许对队列进行的操作有 ( )。A.对队列中的元素排序C.在队头元素之前插入元素53. 用不带头结点的单链表存储队列，队尾结点，则在进行出队操作时 A.仅修改队头指针B.C队头，队尾指针都可能要修改54. 对于循环队列（）。

17、A.无法判断队列是否为空C.队列不可能满B.D.B.取出最近进队的元素D.删除队头元素其队头指针指向队头结点，队尾指针指向仅修改队尾指针 队头，队尾指针都要修改无法判断队列是否为满 D.以上说法都不是55. 循环队列A0.m-1存放其元素值，用front和rear分别表示队头和队尾， 则当前队列中的元素数是（）。A. （rear-fro nt+m）%mC. rear-fr on t-1D. rear-fr ontB. rear-fr on t+156. 若用一个大小为6的数组来实现循环队列，且当前 rear和front的值分别 为0和3,当从队列中删除一个元素， 别为多少？（）A. 1 和 5

18、B. 257. 栈和队的共同点是（A.都是先进后出和4)。B.再加入两个元素后，rear和front的值分C. 4和 2 D. 5都是后进先出D.没有共同点C.只允许在端点处插入和删除元素58. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过 栈S，个元素出栈后即进队列 Q,若6个元素出队的序列是e2,e4,e3,e6,e5,e1 则栈S的容量至少应该是（）。A.59.A.760.6B. 4C. 34个园盘的Hahoi塔，总的移动次数为（）.B.-8C.15和顺序栈相比，链栈有一个比较明显的优势是（B.D.D. 2A.通常不会出现栈满的情况C.插入操作更容易实现6

19、1. 执行（）操作时，A.查找哈希（Hash）表C.先序（根）遍历二叉树62. 设有一顺序栈已经含有 不可能出现的出栈序列是（A.a3,a1,a4,a2C. a3,a4,a2,a1D.16）。通常不会出现栈空的情况 删除操作更容易实现 需要使用队列作辅助存储空间。B.广度优先搜索网 深度优先搜索网3.1所示元素a4正等待进栈。下列D.3个元素，如图A )B. a3,a2,a4,a1D. a4,a3,a2,a1a1a2Top a363在一个链队中，若f,r分别为队首、队尾指针，则插入s所指结点的操作为 （B）A.f-n ext=s;f=s;C.s-n ext=r;r=s;B.r- n ext=s

20、;r=s; D.s-n ext=f;f=s;64. 若用一个大小为6的数组来实现循环队列，且当rear和front的值分别是 0和3o当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是(A )A. 2 和 4 B. 1 和 565. 有六个元素6，5，4，3,序列？ ( CA. 5 4 3 6 1 2C. 4 和 2 D. 5 和 12, 1的顺序进栈，问下列哪一个不是合法的出栈）B. 4 5 3 1 2 6C. 3 4 6 5 2 1 D. 2 3 4 1 5 6二、填空题1 .后缀算式 对应的后缀算式为2下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。t

21、yp edef struct int s100; int top; sqstack;void p ush(sqstack &stack,i nt x) “ ”if (stack.top=m-1) printf(“overflow ” );else ; stack.top+ ，stack.sstack.top=x3.设输入序列为1、2、3，则经过栈的作用后可以得到 出序列。59 2 3 +- 10 2 / -的值为。中缀算式（3+4X） -2Y/3 O -1 , 3 4 X * + 2 Y * 3 / -种不同的输4不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间 复杂度均为。

22、O(1)5设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储队列元素；当前实际存储队列元素(设头指针F 指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置)。m-1，(R-F+M)%M6 设有一个顺序共享栈S0 : n-1，其中第一个栈项指针top1的初值为-1，第 二个栈顶指针top2的初值为n，则判断共享栈满的条件是 o top 1+1=top27栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把 栈称为 ;队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为 。FILO, FIFO&设某顺序循环队列中有 m个元素，且

23、规定队头指针 F指向队头元素的前一个 位置，队尾指针R指向队尾元素的当前位置，则该循环队列中最多存储 队列元素。m-19设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空 的条件为o F=R,然后再前移一10 .从一个栈删除元素时，首先取出位。栈顶元素、栈顶指针11后缀表达式“ 2 10 + 5 * 6- 9 / ”的值为12.中缀表达示3+X* (2.4/5-6 )所对应的后缀表达示为 2.4 5/6 - * +13 .用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234,为了得到1342的出栈顺序，相应的 S和X操作串为SXSSXSXX 。14. 在循环队列中，存储空

24、间为0n-1,设队头指针front指向队头元素前一个 空闲元素，队尾指针指向队尾元素，那么队满标志为fron t=(rear+1)% n ，队空 标志为 _front=rear_ 。15. 对于栈只能在 二栈顶位置插入和删除元素。16. 设输入元素的顺序是 A, B, C, D,通过栈的变换，在输出端可得到各种排 列。若输出序列的第一个元素为 D,则输出序列为DCBA_。17. 队列中允许进行删除的一端为 队头。18. 我们通常把队列中允许插入的一端称为 队尾_19. 队列的原则是。先进先出；问题。假溢出20顺序存储的队列如果不采用循环方式，则会出现21.栈的原则是。先进后出。22 .对于一个

25、顺序栈作进栈运算时，应先判断栈是否为，判断的条件是，作出栈运算时，应先判断栈是否 为，判断的条件是。满;top=MAXSIZE-1 ;空；top=-1 。23.在长度为Maxsize的循环队列中，删除一个新元素，为。front=(front+1)/Maxsize24 .在链队列中，与入队相关的指针是 (头指针或尾指针)。尾指针修改 front队头指针、与出队有关的指针是头指针top=N表示栈空，则25. 当用长度为N的一维数组顺序存储一个栈时，假定用表示栈满的条件为 。top = = 026. 向一个栈顶指针为HS的链栈中插入一个新结点*卩果，应执行操作。p-next = HS 、HS = p

26、27. 从一个栈顶指针为HS的非空链栈中删除结点并不需要返回栈顶结点的值和回收结点时，应执行 操作。HS = HS-next28假定front和rear分别为一个链队的队首和队尾指针，则该链队中只有一个结点的条件为 。( front = = rear ) & ( front vNULL )29 .中缀算术表达式3+4/(25-(6+15)*8 所对应的后缀算术表达式 为。3 4 25 6 15 + - / 8 * +30后缀算术表达式24 8 + 3 * 4 10 7 - * /所对应的中缀算术表达式为,值为。(24+8)*3/(4*(10-7)31. 在一个具有n个单元的顺序栈中，假定以地址

27、高端(即下标为n的单元)作 为栈底，以top作为栈顶指针，则当向栈中压入一个元素时，top的变化是top=。 top-132. 在作进栈运算时应先判别栈是否_(1)_;在作退栈运算时应先判别栈是否 ;当栈中元素为n个，作进栈运算寸发生上溢，则说明该栈的最大容量为。为了增加内存空间的利用率和减少溢出的可能性， 由两个栈共享一片连续的空间 时，应将两栈的(4)_分别设在内存空间的两端,这样只有当 时才产生溢出。 (1)满(2)空(3)n (4) 栈底(5)两栈顶指针相邻(即值之差的绝对值为 1)33. 多个栈共存时，最好用 乍为存储结构。链式存储结构34. 顺序栈用data1.n存储数据，栈顶指针

28、是top,则值为x的元素入栈的操 作是。if(top!=n) data+top=x;35. 循环队列的引入，目的是为了克服 。假溢出时大量移动数据元素。36. 设 a=6, b=4, c=2, d=3, e=2,则后缀表达式 abc-/de*+ 的值为。937. 在循环队列中，队列长度为 n ,存储位置从0到n-1编号，以rear指示实 际的队尾元素, 现要在此队列中插入一个新元素, 新元素的位置是 ()。 rear=(rear+1)%n38. 已知链队列的头尾指针分别是f和r，贝U将值x入队的操作序列是 。 s=(LNode *)malloc( sizeof (Lnode) ；s-data=

29、x;s-next=r-next；r-next=s ；r=s ；39. 区分循环队列的满与空，只有两种方法，它们是牺牲一个存储单元 设标记40. 已知一循环队列的存储空间为m.n,其中nm队头和队尾指针分别为front 和 rear ，贝此循环队列判满的条件是 ( )(rear+1)%(n-m+1)=front41. 设有元素序列的入栈次序为： (a1,a2, , ,an), 其出栈的次序为 (ap1,ap2, ,apn) 现已知 pl=n, 贝 pi= 。 n-i+142. 用循环链表表示的队列长度为n,若只设头指针，则出队和入队的时间复杂 度分别是 和；若只设尾指针，贝出队和入队的时间复杂度

30、分别是 和。 O(1),O(n),O(1),O(1)43. 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如 123 存放成 321。请填空：#includevoid convert(char *a, int n) int i;if(i=n/10) convert(,i);*a=;main()int number; char str10=scanf( “%d”,&number); convert(str,number); puts(str);a+1n%1044. 写出下面程序的运行结果 program priout(input ， output);procedure prin

31、t(f1,f2:integer);var f3:integer;begin if fl=f2 thenbegin if f2 mod fl=0 then f3:=f1+1 else f3:=f1+3print(f3,f2-1);endwriteln(fl, , f2);endbegin print (4,16); end./输出每组两个数占一行,(13 11),(12 12),(9 13),(6 14),(5 15),(4 16)也没括号三、判断题1.( )不论是入队列操作还是入栈操作， 在顺序存储结构上都需要考虑 “溢出” 情况。 T2.(3. ()况。T4.5.6.7.)在循环顺序队列中插

32、入新元素不需要判断队列是否满了。X入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情(栈时,8 (9. (O(1)。10.11.12.13.14.)栈是一种先进后出的线性表。V)消除递归不一定需要使用栈。 V)栈是实现过程和函数等子程序所必需的结构。V)设栈采用顺序存贮结构。若已有i-1个元素进栈，则将第i个元素进 进栈算法的时间复杂性为 0(i)。X)在链队列中，即使不设置尾指针也能进行入队操作。V)设尾指针的循环链表表示队列，则入队和出队算法的时间复杂度均为V)栈和队列都是线性表，只是在插入和删除时受到了一些限制。V)队列在程序调用时必不可少，因此递归离不开队列。X)栈可以作为

33、实现程序设计语言过程调用时的一种数据结构)栈又称后进先出表，队列又称为先进先出表。V)栈和队列都是限制存取点的线性结构。V( (四、简答题1. 简述栈和队列的共同点和不同点。它们与线性表有什么关系？2. 在一般的顺序队列中，什么是假溢出？怎样解决假溢出问题？当队尾到达数组最后一个单元时，就认为队满，但此时数组前面可能还有空单元， 因此叫假溢出。解决的办法采用循环队列。3 .简述栈和队列这两种数据结构的相同点和不同点。栈和队列都是操作受限的线性表。 栈是先进后出，操作在一端进行；队列是先进 先出，插入在一端，删除在另一端进行。4 .如题31图所示，输入元素为A, B, C, 试写出在栈的输入端三

34、个可能的输入序列。ABC CBA ACBVo在栈的输出端得到一个输出序列ADC输出弟输入端桂5.如题32图所示，在栈的输入端有6个元素，顺序为A, B, C, D, E, 否在栈的输出端得到序列DCFEB及EDBFCA若能，给出栈操作的过程, 能,简述其理由。输出端AliCDEF栈ABCFo能若不DCFEBA 可 以：push(A), push(B), push(C), push(D), pop (D), pop (C), pu st(E).,Push(F), pop( F), pop (E), pop (B), pop(A)EDBFCA根据入栈顺序B不能在C前面出栈。6.什么是循环队列？用常

35、规意义下顺序存储结构的一维数组表示队列，由于队列的性质(队尾插入和队头删除)，容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能 再入队，然而队列中元素个数小于队列的长度(容量)。循环队列是解决“假溢 出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺 牲一个存储单元”或“作标记”的方法解决“队满”和“队空”的判定问题。应 该指出，除特别说明，循环队列通常是指顺序存储结构，而不是链式存储结构。 7有 5 个元素，其入栈次序为 A,B,C,D,E, 在各种可能的出栈序列中，第一个出 栈元素为 C 且第二个出栈元素为 D 的出栈序列有哪几个？三个：CDEBA CDBEA

36、 CDBAE8简述递归思想。现有两个正整数 M和N,如果采用递归方法解决 MX N运算， 试结合递归思想，说明其终止条件和递归语句是什么？ 递归是程序设计中的重要技术。 利用递归技术编写的程序结构清晰、 易读、且其 正确性容易证明。 当问题的定义是递归的、 数据结构是递归的和问题的解法是递 归的时， 最好利用递归。 求解递归问题时， 要先写出问题求解的递归定义。 递归 定义由基本项和归纳项组成。 基本项描述了一个或几个递归过程的终结状态， 即 不需要继续递归就可直接求解的状态。 归纳项描述了从当前状态向终结状态的转 换。递归过程的实质是将复杂问题分解成若干子问题， 子问题与原问题具有相同 特征

37、，但是简单了。子问题解决了，原问题迎刃而解。本题求解两个整数 M和N相乘，可以利用递归技术变为 M个N相加。基本项是 M=1,归纳项是(M-1)个N相乘。其递归过程如下：long MultiToAdd(int m,int n)/用递归算法求m*nif(m=1) return (n);else return (MultiToAdd(m-1,n)+n); 9设输入序列为 a,b,c,d, 试写出借助一个栈可得到的两个输出序列和两个不能 得到的输出序列。n个元素的排列有n!种，但借助栈结构，n个入栈元素只可得到1/(n+1)(2n) ! / (n!*n!)种出栈序列，这个数小于n!。本题4个元素，可

38、有14种出栈序列， abed和deba就是其中两种；有10(4!-14=10)种排列得不到，其中，dabc和adbc 是不可能得到的两种。10队列可以用循环单链表来实现， 故可以只设置一个头指针或者只设置一个尾 指针。请你分析对于循环单链表实现的队列，用哪种方案更合适。O(1)。循环单链表若只设头指针，则出队操作时间复杂度是 O(1) ，而入队操作时间复 杂度是0(n);若只设尾指针，则出队和入队操作时间复杂度都是 11试推导出当总盘数为 n 的 Hanoi 塔的移动次数。设Hi为n个盘子的Hanoi塔的移动次数。(假定n个盘子从钢针X移到钢针Z， 可借助钢针 丫) 则 H n =2Hn-1+

39、1个盘子从X移到丫，第n个盘子移到Z再将那n-1个移到Z/先将 n-1=2( 2Hn-2+1 )+1=22 Hn-2+2+1=22 (2Hn-3+1)+2+1=2393 Hn-3+22+2+1=2k Hn-k+2k-1 +2k-2 +, +21 +2=2n-1 Hi+2n-2+2n-3+, +21+20因为 H=1，所以原式 Hn=2n-1+2n-2+, +21+20=2n-1故总盘数为n的Hanoi塔的移动次数是2n-1。12.用一个数组S (设大小为MAX作为两个堆栈的共享空间。请说明共享方法，栈满/栈空的判断条件，并用C或PASCA设计公用的入栈操作push (i ,x)， 其中i为0或

40、1,用于表示栈号，x为入栈值。两栈共享一向量空间(一维数组)，栈底设在数组的两端，两栈顶相邻时为栈满。 设共享数组为SMAX，则一个栈顶指针为-1，另一个栈顶指针为 MAX时，栈为 空。用C写的入栈操作Push (i，x)如下：con st MAX=共享栈可能达到的最大容量typ edefstruct nodeelemt ype sMAX；intto p2；anode ；anode ds;int p ush(i nt l,elemt ype x)/ ds为容量有MA)个类型为elemtype的元素的一维数组，由两个栈共享其空间。I的值为0或1/ x为类型为elemtype的元素。本算法将x压入

41、栈中。如压栈成功，返回1;否 则，返回0 if (ds.top1-ds.top0=1) printf (“栈满 n ”)； return (0)； switch (i ) case 0 : ds.s+ds.topi=x； break ；case 1 : ds.s-ds.topi=x；return (1)； /入栈成功 13用栈实现将中缀表达式8-(3+5)*(5-6/2) 转换成后缀表达式，画出栈的变化 过程图。中缀表达式8-(3+5)*(5-6/2)的后缀表达式是：8 3 5 + 5 6 2 / - * -栈的变化过程图略，表达式生成过程为：中缀表达式exp1转为后缀表达式exp2的规则如下

42、：设操作符栈S,初始化为空栈，压入优先级最低的操作符 #。对中缀表达式 从左向右扫描，遇操作数，直接写入 exp2；若是操作符(记为W)，分如下情况 处理，直至表达式exp1扫描完毕。（1）w为一般操作符（- ， * , / 等），要与栈顶操作符比 较优先级，若w优先级高于栈顶操作符，则入栈；否则，栈顶运算符退栈到exp2, w再与新栈顶操作符作上述比较处理，直至 w入栈。（2）w为左括号（），w入栈。（3） W为右括号（），操作符栈退栈并进入 exp2,直到碰到左括号为止， 左括号退栈（不能进入exp2），右括号也丢掉，达到exp2中消除括号的目的。（4） w为#，表示中缀表达式exp1结束

43、，操作符栈退栈到exp2，直至碰到 #，退栈，整个操作结束。14. 有字符串次序为3*-y-a/yA2,利用栈，给出将次序改为3y-*ay2/-的操作步 骤。（可用X代表扫描该字符串过程中顺序取一个字符进栈的操作， 用S代表从 栈中取出一个字符加入到新字符串尾的出栈操作。例如， ABC变为BCA的操作步 骤为XXSXS）XSXXXSSSXXSXXSXXSSSS15. 计算算术表达式的值时，可用两个栈作辅助工具。对于给出的一个表达式，从左向右扫描它的字符，并将操作数放入栈S1中，运算符放入栈S2中，但每次 扫描到运算符时，要把它同 S2的栈顶运算符进行优先级比较，当扫描到的运算 符的优先级不高于

44、栈顶运算符的优先级时，取出栈S1的栈顶和次栈顶的两个元素，以及栈S2的栈顶运算符进行运算将结果放入栈 S1中（得到的结果依次用 T1、T2等表示）。为方便比较，假设栈 S2的初始栈顶为？（？运算符的优先级低 于加、减、乘、除中任何一种运算）。现假设要计算表达式：A-B*C/D+E/F。写出栈S1和S2的变化过程。步骤栈S1栈S2输入的算术表达式（按字 符读入）初始?A-B*C/D+E/F?1A?A-B*C/D+E/F?2A?-B*C/D+E/F?3AB?-EC/D+E/F?4AB?*C/D+E/F?5ABC?*CD+E/F?6AT （注：T1=B*C）?-/LD+E/F?7ATD?-/D+E/

45、F?8AT2 （注：T2=T1/D） T3 （注：T3=A-T2）?- ?+E/F?9T3E?+BF?10T3E?+/LF?11T3EF?+/F?12T3T4 （注：T4=E/F）T5（注：T5= T3+ T4 ）?+?16.简述顺序存储队列的假溢出的避免方法及队列满和空的条件。设顺序存储队列用一维数组 qm表示，其中m为队列中元素个数，队列中元素 在向量中的下标从0到m-1o设队头指针为front ，队尾指针是rear，约定front指向队头元素的前一位置， rear 指向队尾元素。当 front 等于-1 时队空， rear 等于 m-1 时为队满。由于队列的性质(“删除”在队头而“插入”

46、在队尾)，所 以当队尾指针rear等于m-1时，若front不等于-1，贝U队列中仍有空闲单元， 所以队列并不是真满。这时若再有入队操作，会造成假“溢出”。其解决办法有 二，一是将队列元素向前“平移”(占用 0 至 rear-front-1 )；二是将队列看 成首尾相连，即循环队列( 0.m-1 )。在循环队列下，仍定义 front=rear 时为 队空，而判断队满贝常用两种办法， 一是用“牺牲一个单元” ，即 rear+1=front(准确记是(rear+1 ) %m=front, m是队列容量)时为队满。另一种解法是“设 标记”方法，如设标记 tag ， tag 等于 0情况下， 若删除时

47、导致 front=rear 为队 空； tag=1 情况下,若因插入导致 front=rear 贝为队满。17如果用一个循环数组q0.m-1 表示队列时,该队列只有一个队列头指针front ,不设队列尾指针 rear ,而改置计数器 count 用以记录队列中结点的个数。 编写实现队列的三个基本运算：判空、入队、出队( 队列中能容纳元素的最多个数是多少？( 1 分) typedef struct ElemType qm;int front,count; cqnode;/ front 是队首指针， count /定义类型标识符。3 分)是队列中元素个数队空 n ”) ；return (0); c

48、q.qcq.front);/计算新的队头指针/ cq 是 cqnode 类(1) 判空： int Empty(cqnode cq) 型的变量/空队列if (cq.count=0) return (1) ；else return (0); 入队 : int EnQueue(cqnode cq, ElemType x) if (count=m)printf(“队满 n ” ) ； exit(O); / x 入队/队列中元素个数增加 1, 入cq.q(cq.front+count)%m=x;count+;return (1);队成功 出队 : int DelQueue(cqnode cq) if (

49、count=O)printf( printf( “出队元素”, x=cq.qcq.front; cq.front=(cq.front+1)%m; return (x)(2) 队列中能容纳的元素的个数为 m队头指针front指向队头元素。18.给出循环队列中元素个数的计算式(设队最大长度为N,队首指针FRONT队 尾指针 REAR)循环队列中元素个数为(REAR-FRONT)+N%N其中FRONT!队首指针，指向队首 元素的前一位置；REAR是队尾指针，指向队尾元素；N是队列最大长度。 19若以 1、2、3、4 作为双端队列的输入序列，试分别求出以下条件的输出序 列： 能由输入受限的双端队列得到

50、，但不能由输出受限的双端队列得到的输出序列； 能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列； 既不能由输入受限的双端队列得到， 也不能由输出受限的双端队列得到的输出序列。(1) 4132五、应用题1. 已知一个中缀算术表达式为： 术表达式。后缀算术表达式：3 4 25 6 15(2) 4213(3) 42313+4*(25-(6/15)-8,写出对应的后缀算2. 设有一顺序队列sq，容量为5，初始状态时sq.front=sq.rear=O ，画出做完 下列操作后队列及其头尾指针的状态变化情况，若不能入队，请简述其理由后 停止。(6分)(1)(2)(3)(4)(5)d,e

51、,b入队 d,e出队 i,j入队 b出队 n,o,p入队I- h网卜re町1 哪,frnnl, irar-Ij Jb Od.c.b ASK岀貼(4b出閘六、程序填空题(或算法阅读题)1. void exam1(SeqStack S, int m) SeqStack T; int iIn iStack(T);while(!Stacke mpty (S)if (i=pop (S)!=m) push(T,i);while (!Stacke mp ty(T) i=pop(T) ; push(S,i); /exam1程序段1的功能是将一个非空栈中值等于 m的元素全部删除；(根据答题情况酌 情给分)七、算法设计题1.设有两个栈S,S2都采用顺序栈方式，并且共享一个存储区O.maxsize-1, 为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。 试设计S,S2有关入栈和出栈的操作算法。【哈尔滨工业大学2001七(12分)