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

《数据结构练习 第三章 栈和队列.docx》由会员分享，可在线阅读，更多相关《数据结构练习 第三章 栈和队列.docx（38页珍藏版）》请在三一办公上搜索。

1、数据结构练习 第三章 栈和队列数据结构练习第三章 栈和队列 一、选择题 1栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2向顺序栈中压入新元素时，应当。 A先移动栈顶指针，再存入元素 B先存入元素，再移动栈顶指针 C先后次序无关紧要 D同时进行 3允许对队列进行的操作有( )。 A. 对队列中的元素排序 B. 取出最近进队的元素 C. 在队头元素之前插入元素 D. 删除队头元素 4用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 5设

2、用链表作为栈的存储结构则退栈操作。 A. 必须判别栈是否为满 B. 必须判别栈是否为空 C. 判别栈元素的类型 D.对栈不作任何判别 6设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为。 A.front-next=s；front=s； B. 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. t

3、op-next=top; D. top=top-next; 8队列是一种的线性表。 A. 先进先出 B. 先进后出 C. 只能插入 D. 只能删除 9设输入序列1、2、3、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是。 A. n-i B. n-1-i C. n+l -i D.不能确定 10设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为。 A. 5，3，4，6，1，2 B. 3，2，5，6，4，1 C. 3，1，2，5，4，6 D. 1，5，4，6，2，3 11队列的删除操作是在进行。 A队首 B队尾 C队前 D队后 12当利用大小为N 的

4、数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用语句修改top指针。 Atop+; Btop=0; Ctop-; Dtop=N; 13队列的插入操作是在进行。 1 A队首 B队尾 C队前 D队后 14若已有一个栈，输入序列为A，B，C，D，E，那么下面哪种序列不可能得到？ AABCDE BEDCBA CBAEDC DECDBA (d) 注意: 入栈和出栈操作可以交替进行，因此就可能有多种输出序列了。 15栈和队列共同具有的特点是 A.都是先进后出 B.都是先进先出 C.只允许在端点进行操作运算 D.既能先进先出，也能先进后出 16若用一个有6个单元的数组来实现循环队列，re

5、ar和front的初值分别为0和3。则从队列中删除一个元素，再添加两个元素后，rear和front的值分别为 A.1和5 B.2和4 C.4和2 D.5和1 17一个栈的入栈序列是a，b，c，d，e，则栈的输出序列不可能是( ) A. dceab B. decba C. edcba D. abcde 18元素大小为1个单元，容量为n个单元的非空顺序栈中，以地址高端为栈底，以top作为栈顶指针，则出栈处理后，top的值应修改为( ) A. top=top B. top=n-1 C. top=top-1 D. top=top+1 19设有一个栈，按A、B、C、D的顺序进栈，则可能为出栈序列的是(

6、) A.DCBA B.CDAB C.DBAC D.DCAB 20在一个具有n个单元的顺序栈中，假定以地址低端作为栈底，以top为栈顶指针，则当做出栈处理时，top变化为( ) A.top+ B.top- C.top不变 D.top=0 21. 关于栈和队列的说法中正确的是 A栈和队列都是线性结构 B.栈是线性结构，队列不是线性结构 C.栈不是线性结构，队列是线性结构 D.栈和队列都不是线性结构 22. 设一个栈的输入序列是a，b，c，d，则所得到的输出序列不可能出现的是 Aa，b，c，d B.a，b，d，c C.d，c，b，a D.c，d，a，b 23. 在具有m个单元的循环队列中，队头指针为

7、front，队尾指针为rear，则队满的条件是 Afront=rear B.(front+1)%m=rear C.rear+1=front D.(rear+1)%m=front 24. 循环队列存储在数组A0.m中，则入队时的操作为( D)。 A. rear=rear+1 B. rear=(rear+1) % (m-1) C. rear=(rear+1) % m D. rear=(rear+1) % (m+1) 25. 顺序栈S中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的主要语句为 A.s.elemtop=e； B.s.elemtop+1=e； s.t

8、op=s.top+1； s.top=s.top+1； C.s.top=s.top+1； D.s.top=s.top+1； s.elemtop+1=e； s.elemtop=e； 2 26. 循环队列sq中，用数组elem025存放数据元素，sq.front指示队头元素的前一个位置，sq.rear指示队尾元素的当前位置，设当前sq.front为20，sq.rear为12，则当前队列中的元素个数为 A.8 B.16 C.17 D.18 27. 有关栈的描述，正确的是 A.栈是一种先进先出的特殊的线性表 B.只能从栈顶执行插入、删除操作 C.只能从栈顶执行插入、栈底执行删除 D.栈顶和栈底均可执行插

9、入、删除操作 28. 设顺序循环队列Q0：M-1的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为。 A. R-F B. F-R C. (R-F+M)M D. (F-R+M)M 29. 设一数列的输入顺序为1,2,3,4,5,6，通过栈操作不可能排成的输出序列为。 A3,2,5,6,4,1 B1,5,4,6,2,3 C2,4,3,5,1,6 D4,5,3,6,2,1 30. 设有一个栈，元素的进栈次序为A,B,C,D,E，则下列是不可能的出栈序列。 AA,B,C,D,E BB,C,D,E,A CE,A,B,C,D D

10、E,D,C,B,A 31在具有N个单元的顺序存储循环队列中，假定front和rear分别为对头指针和对尾指针，则判断对满的条件为。 Afront= rear B(rear+1)%MAXSIZE=front Cfront-rear=1 Drear%MAXSIZE=front 32一个元素进入队列的时间复杂度是。 AO(1) BO(n) CO(n2) DO(log2n) 33若让元素1，2，3依次进栈，则出栈次序不可能出现种情况。 A.3，2，1 B.2，1，3 C.3，1，2 D.1，3，2 34假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件是。 A.front=NUL

11、L B.front!=NULL C.rear!=NULL D.front=rear 35若让元素a，b，c依次进栈，则出栈次序不可能出现种情况。 Acba Bbac Ccab Dacb 36在一个链队列中，假定front和rear分别为队头和队尾指针，则插入*s结点的操作应执行。 Afront-next=s; front=s; Bs-next=rear; rear=s; C rear-next=s; rear=s; Ds-next=front; front=s; 37栈的插入与删除操作在进行。 A.栈顶 B.栈底 C.任意位置 D.指定位置 38当利用大小为N的一维数组顺序存储一个栈时，假定用

12、top=1表示栈空，则向这个栈插入一个元素时，首先应执行语句修改top指针。 3 Atop+； Btop-； Ctop=NULL ； Dtop； 39当采用顺序存储方式存储队列时，可能出现存储空间剩余，而不允许继续入队的情况，称为。 A溢出 B 假溢出 C队列不能用顺序存储方式 D数组存储空间过小 40当利用大小为N的一维数组顺序存储一个循环队列时，该队列的最大长度为。 A.N-2 B.N-1 C.N D.N+1 41从一个循环顺序队列删除元素时，首先需要。 A.前移一位队首指针 B.后移一位队首指针 C.取出队首指针所指位置上的元素 D.取出队尾指针所指位置上的元素 42循环队列存储在数组A

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

14、设栈的输入序列是1，2，3，4,则不可能是其出栈序列。 A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2， D. 4，3，1，2， E. 3，2，1，4， 47如进栈序列1，2，3，4，5。可能得到的出栈序列为( ) A1,2,5,3,4 B3,1,2,5,4 C3,2,5,4,1 D1,4,2,3,5 E都不可能 48一个栈的入栈序列为A,B,C,D,E，则栈的不可能的出栈序列是( )。 A. ABCDE B. EDCBA C. DECBA D.DCEAB 49function calc(x,y :integer) : integer; begin if y=1 then

15、 calc :=x else calc := calc (x,y-1)+x end; a,b均为正整数，则 calc(a,b)=( ) A.a*(b-1) B. a*b C. a+b D. a+a 50执行完下列语句段后，i值为：。 int f(int x) return (x0) ? x* f(x-1):2); int i ; i =f(f(1); A2 B. 4 C. 8 D. 无限递归 51表达式a*(b+c)-d的后缀表达式是( )。 Aabcd*+- B. abc+*d- C. abc*+d- D. -+*abcd 52允许对队列进行的操作有( )。 4 A. 对队列中的元素排序 B

16、. 取出最近进队的元素 C. 在队头元素之前插入元素 D. 删除队头元素 53用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时( ) A仅修改队头指针 B.仅修改队尾指针 C队头，队尾指针都可能要修改 D.队头，队尾指针都要修改 54对于循环队列( )。 A. 无法判断队列是否为空 B. 无法判断队列是否为满 C. 队列不可能满 D. 以上说法都不是 55循环队列A0.m-1存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( )。 A. (rear-front+m)%m B. rear-front+1 C. rear-

17、front-1 D. rear-front 56若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 57栈和队的共同点是( )。 A. 都是先进后出 B. 都是后进先出 C. 只允许在端点处插入和删除元素 D. 没有共同点 58设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。 A

18、 6 B. 4 C. 3 D. 2 594个园盘的Hahoi塔，总的移动次数为( ). A.7 B.-8 C.15 D.16 60和顺序栈相比，链栈有一个比较明显的优势是。 A. 通常不会出现栈满的情况 B. 通常不会出现栈空的情况 C. 插入操作更容易实现 D. 删除操作更容易实现 61执行操作时，需要使用队列作辅助存储空间。 A. 查找哈希(Hash)表 B. 广度优先搜索网 C. 先序(根)遍历二叉树 D. 深度优先搜索网 62设有一顺序栈已经含有3个元素，如图3.1所示元素a4正等待进栈。下列不可能出现的出栈序列是 A.a3,a1,a4,a2 B. a3,a2,a4,a1 C. a3,

19、a4,a2,a1 D. a4,a3,a2,a1 a1 a2 Top a3 63在一个链队中，若f,r分别为队首、队尾指针，则插入s所指结点的操作为 A.f-next=s;f=s; B.r-next=s;r=s; C.s-next=r;r=s; D.s-next=f;f=s; 5 64若用一个大小为6的数组来实现循环队列，且当rear和front的值分别是0和3。 当从队列中删除一个元素，再加入两个元素后，rear 和front 的值分别是 A. 2和4 B. 1和5 C. 4和2 D. 5和1 65有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？ A. 5 4 3

20、 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 二、填空题 1后缀算式9 2 3 +- 10 2 / -的值为_。中缀算式-2Y/3对应的后缀算式为_。-1，3 4 X * + 2 Y * 3 / - 2下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。 typedef struct int s100; int top; sqstack; void push(sqstack &stack,int x) if (stack.top=m-1) printf(“overflow”); else _;_; stack.top+，sta

21、ck.sstack.top=x 3设输入序列为1、2、3，则经过栈的作用后可以得到_种不同的输出序列。5 4不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为_。O(1) 5设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储_个队列元素；当前实际存储_个队列元素。m-1，(R-F+M)%M 6设有一个顺序共享栈S0：n-1，其中第一个栈项指针top1的初值为-1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是_。top1+1=top2 7栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为_表；队列的插入和删除运算分别在队列

22、的两端进行，先进队列的元素必定先出队列，所以又把队列称为_表。FILO，FIFO 8设某顺序循环队列中有m个元素，且规定队头指针F指向队头元素的前一个位置，队尾指针R指向队尾元素的当前位置，则该循环队列中最多存储_队列元素。m-1 9设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为_。F=R 10从一个栈删除元素时，首先取出 ，然后再前移一位 。栈顶元素、栈顶指针 11后缀表达式“2 10 + 5 * 6 9 /”的值为 。6 12中缀表达示3+X*所对应的后缀表达示为_。3 x 2.4 5 6 * 13用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了

23、得到1342的出栈顺序，相应的S和X操作串为_SXSSXSXX_。 6 14在循环队列中，存储空间为0n-1,设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么队满标志为front=(rear+1)%n，队空标志为_front=rear_。 15对于栈只能在_栈顶位置_插入和删除元素。 16设输入元素的顺序是A，B，C，D，通过栈的变换，在输出端可得到各种排列。若输出序列的第一个元素为D，则输出序列为_DCBA_。 17队列中允许进行删除的一端为_队头_。 18我们通常把队列中允许插入的一端称为_队尾_。 19队列的原则是 。先进先出； 20顺序存储的队列如果不采用循环

24、方式，则会出现 问题。假溢出 21栈的原则是 。先进后出。 22对于一个顺序栈作进栈运算时，应先判断栈是否为 ，判断的条件是 ，作出栈运算时，应先判断栈是否为 ，判断的条件是 。满 ;top=MAXSIZE-1 ;空 ;top=-1。 23在长度为Maxsize的循环队列中，删除一个新元素，修改front队头指针为 。front=(front+1)/Maxsize 24在链队列中，与入队相关的指针是 、与出队有关的指针是 。尾指针 、 头指针 25当用长度为N的一维数组顺序存储一个栈时，假定用top=N表示栈空，则表示栈满的条件为 。top = = 0 26向一个栈顶指针为HS的链栈中插入一个

25、新结点*P果，应执行 和 操作。p-next = HS 、HS = p 27从一个栈顶指针为HS的非空链栈中删除结点并不需要返回栈顶结点的值和回收结点时，应执行 操作。HS = HS-next 28假定front和rear分别为一个链队的队首和队尾指针，则该链队中只有一个结点的条件为 。( front = = rear ) & ( front NULL ) 29中缀算术表达式3+4/(25-(6+15)*8 所对应的后缀算术表达式为 。3 4 25 6 15 + - / 8 * + 30后缀算术表达式24 8 + 3 * 4 10 7 - * / 所对应的中缀算术表达式为 ，值为 。(24+8

26、)*3/(4*(10-7) 、8 31在一个具有n个单元的顺序栈中，假定以地址高端作为栈底，以top作为栈顶指针，则当向栈中压入一个元素时，top的变化是top=_。 top-1 32在作进栈运算时应先判别栈是否_(1)_;在作退栈运算时应先判别栈是否_(2)_；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_(3)_。 为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_(4)_分别设在内存空间的两端，这样只有当_(5)_时才产生溢出。 (1)满 (2)空 (3)n (4)栈底 (5)两栈顶指针相邻 33多个栈共存时，最好用_作为存储结构。链

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

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

29、),O(n),O(1),O(1) 43下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空： #include void 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+1 n%10 44写出下面程序的运行结果 program priout(input，output); procedure print(f1,f

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

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

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

33、B 5如题32图所示，在栈的输入端有6个元素，顺序为A，B，C，D，E，F。能否在栈的输出端得到序列DCFEBA及EDBFCA？若能，给出栈操作的过程，若不能，简述其理由。 DCFEBA可以：push(A),push(B),push(C),push(D),pop(D),pop(C),pust(E)., Push(F),pop(F),pop(E),pop(B),pop(A) EDBFCA：根据入栈顺序B不能在C前面出栈。 6什么是循环队列？ 用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质，容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再入队，然而队列中元素个数小于队列的长

34、度。循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储单元”或“作标记”的方法解决“队满”和“队空”的判定问题。应该指出，除特别说明，循环队列通常是指顺序存储结构，而不是链式存储结构。 7有5个元素，其入栈次序为A,B,C,D,E,在各种可能的出栈序列中，第一个出栈元素为C且第二个出栈元素为D的出栈序列有哪几个？ 三个：CDEBA，CDBEA，CDBAE 8简述递归思想。现有两个正整数M和N，如果采用递归方法解决MN运算，试结合递归思想，说明其终止条件和递归语句是什么？ 递归是程序设计中的重要技术。利用递归技术编写的程序结构清晰、易读、且其正确

35、性容易证明。当问题的定义是递归的、数据结构是递归的和问题的解法是递归的时，最好利用递归。求解递归问题时，要先写出问题求解的递归定义。递归定义由基本项和归纳项组成。基本项描述了一个或几个递归过程的终结状态，即不需要继续递归就可直接求解的状态。归纳项描述了从当前状态向终结状态的转换。递归过程的实质是将复杂问题分解成若干子问题，子问题与原问题具有相同特征，但是简单了。子问题解决了，原问题迎刃而解。 本题求解两个整数M和N相乘，可以利用递归技术变为M个N相加。基本项是M=1,归纳项是(M-1)个N相乘。其递归过程如下： long MultiToAdd(int m,int n) 用递归算法求m*n if

36、(m=1) return (n); else return (MultiToAdd(m-1,n)+n); 9设输入序列为a,b,c,d,试写出借助一个栈可得到的两个输出序列和两个不能得到的输出序列。 n个元素的排列有n!种，但借助栈结构，n个入栈元素只可得到1/(n+1)(2n)！/)种出栈序列，这个数小于n!。本题4个元素，可有14种出栈序列，abcd和dcba就是其中两种；有10(4!-14=10)种排列得不到，其中，dabc和adbc是不可能得到的两种。 10队列可以用循环单链表来实现，故可以只设置一个头指针或者只设置一个尾指针。请你分析对于循环单链表实现的队列，用哪种方案更合适。 循环

37、单链表若只设头指针，则出队操作时间复杂度是O(1)，而入队操作时间复杂度是O(n)；若只设尾指针，则出队和入队操作时间复杂度都是O(1)。 11试推导出当总盘数为n的Hanoi塔的移动次数。 设Hn为n个盘子的Hanoi塔的移动次数。(假定n个盘子从钢针X移到钢针Z，可借助钢针Y) 则 Hn =2Hn-1+1 先将n-1个盘子从X移到Y，第n个盘子移到Z，再将那n-1个移到Z =2+1 2 =2 Hn-2+2+1 =22+2+1 =23 Hn-3+22+2+1 10 kk-1k-210 = 2 Hn-k+2 +2 +2 +2 =2n-1 H1+2n-2+2n-3+21+20 n-1n-210n

38、 因为H1=1，所以原式Hn=2+2+2+2=2-1 故总盘数为n的Hanoi塔的移动次数是2n-1。 12 用一个数组S作为两个堆栈的共享空间。请说明共享方法，栈满/栈空的判断条件，并用C或PASCAL设计公用的入栈操作push，其中i为0或1，用于表示栈号，x为入栈值。 两栈共享一向量空间，栈底设在数组的两端，两栈顶相邻时为栈满。设共享数组为SMAX，则一个栈顶指针为-1，另一个栈顶指针为MAX时，栈为空。 用C写的入栈操作push如下： const MAX=共享栈可能达到的最大容量 typedef struct node elemtype sMAX； int top2； anode； a

39、node ds; int push(int I,elemtype x) ds为容量有MAX个类型为elemtype的元素的一维数组，由两个栈共享其空间。I的值为0或1 x为类型为elemtype的元素。本算法将x压入栈中。如压栈成功，返回1；否则，返回0 ifprintf；return； switch case 0：ds.s+ds.topi=x；break； case 1：ds.s-ds.topi=x； return；入栈成功 13用栈实现将中缀表达式8-(3+5)*(5-6/2)转换成后缀表达式，画出栈的变化过程图。 中缀表达式8-(3+5)*(5-6/2)的后缀表达式是： 8 3 5 + 5 6 2 / - * - 栈的变化过程图略，表达式生成过程为： 中缀表达式exp1转为后缀表达式exp2的规则如下： 设