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

数据结构练习第三章 栈和队列一、选择题1栈和队列的共同特点是( )。A.只允许在端点处插入和删除元素B.都是先进后出 C.都是先进先出D.没有共同点2向顺序栈中压入新元素时，应当（ ）。A先移动栈顶指针，再存入元素 B先存入元素，再移动栈顶指针C先后次序无关紧要 D同时进行3允许对队列进行的操作有( )。A. 对队列中的元素排序 B. 取出最近进队的元素C. 在队头元素之前插入元素 D. 删除队头元素4用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改5设用链表作为栈的存储结构则退栈操作（ ）。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. top-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，2B. 3，2，5，6，4，1C. 3，1，2，5，4，6 D. 1，5，4，6，2，311队列的删除操作是在（ ）进行。A队首 B队尾 C队前 D队后12当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（ ）语句修改top指针。Atop+; Btop=0; Ctop-; Dtop=N;13队列的插入操作是在（ ）进行。A队首 B队尾 C队前 D队后14若已有一个栈，输入序列为A，B，C，D，E，那么下面哪种序列不可能得到？（ ）AABCDE BEDCBA CBAEDC DECDBA(d) 注意: 入栈和出栈操作可以交替进行，因此就可能有多种输出序列了。15栈和队列共同具有的特点是（）A.都是先进后出B.都是先进先出C.只允许在端点进行操作运算 D.既能先进先出，也能先进后出16若用一个有6个单元的数组来实现循环队列，rear和front的初值分别为0和3。则从队列中删除一个元素，再添加两个元素后，rear和front的值分别为（）A.1和5 B.2和4C.4和2 D.5和117一个栈的入栈序列是a，b，c，d，e，则栈的输出序列不可能是( )A. dceab B. decbaC. edcba D. abcde18元素大小为1个单元，容量为n个单元的非空顺序栈中，以地址高端为栈底，以top作为栈顶指针，则出栈处理后，top的值应修改为( )A. top=topB. top=n-1 C. top=top-1D. top=top+119设有一个栈，按A、B、C、D的顺序进栈，则可能为出栈序列的是( )A.DCBA B.CDAB C.DBAC D.DCAB20在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top为栈顶指针，则当做出栈处理时，top变化为( )A.top+ B.top- C.top不变 D.top=021. 关于栈和队列的说法中正确的是（ ）A栈和队列都是线性结构B.栈是线性结构，队列不是线性结构C.栈不是线性结构，队列是线性结构D.栈和队列都不是线性结构22. 设一个栈的输入序列是a，b，c，d，则所得到的输出序列（输入过程中允许出栈）不可能出现的是（ ）Aa，b，c，dB.a，b，d，cC.d，c，b，a D.c，d，a，b 23. 在具有m个单元的循环队列中，队头指针为front，队尾指针为rear，则队满的条件是（ ）Afront=rearB.(front+1)%m=rearC.rear+1=front D.(rear+1)%m=front24. 循环队列存储在数组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.top=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；26. 循环队列sq中，用数组elem025存放数据元素，sq.front指示队头元素的前一个位置，sq.rear指示队尾元素的当前位置，设当前sq.front为20，sq.rear为12，则当前队列中的元素个数为（）A.8 B.16 C.17 D.1827. 有关栈的描述，正确的是（）A.栈是一种先进先出的特殊的线性表B.只能从栈顶执行插入、删除操作C.只能从栈顶执行插入、栈底执行删除D.栈顶和栈底均可执行插入、删除操作28. 设顺序循环队列Q0：M-1的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ ）。A. R-F B. F-R C. (R-F+M)M D. (F-R+M)M29. 设一数列的输入顺序为1,2,3,4,5,6，通过栈操作不可能排成的输出序列为（ ）。A3,2,5,6,4,1 B1,5,4,6,2,3C2,4,3,5,1,6 D4,5,3,6,2,130. 设有一个栈，元素的进栈次序为A,B,C,D,E，则下列（ ）是不可能的出栈序列。 AA,B,C,D,E BB,C,D,E,A CE,A,B,C,D DE,D,C,B,A31在具有N个单元的顺序存储循环队列中，假定front和rear分别为对头指针和对尾指针，则判断对满的条件为（ ）。Afront= rear B(rear+1)%MAXSIZE=frontCfront-rear=1 Drear%MAXSIZE=front32一个元素进入队列的时间复杂度是（ ）。 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，234假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件是（ ）。A.front=NULL B.front!=NULL C.rear!=NULL D.front=rear35若让元素a，b，c依次进栈，则出栈次序不可能出现（ ）种情况。Acba Bbac Ccab Dacb36在一个链队列中，假定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的一维数组顺序存储一个栈时，假定用top=1表示栈空，则向这个栈插入一个元素时，首先应执行（ ）语句修改top指针。 Atop+； Btop-； Ctop=NULL ； Dtop；39当采用顺序存储方式存储队列时，可能出现存储空间剩余，而不允许继续入队的情况，称为（ ）。A溢出 B 假溢出 C队列不能用顺序存储方式 D数组存储空间过小40当利用大小为N的一维数组顺序存储一个循环队列时，该队列的最大长度为（ ）。 A.N-2 B.N-1 C.N D.N+141从一个循环顺序队列删除元素时，首先需要（ ）。A.前移一位队首指针 B.后移一位队首指针C.取出队首指针所指位置上的元素 D.取出队尾指针所指位置上的元素42循环队列存储在数组A0.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.1644对于栈操作数据的原则是（ ）。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 646设栈的输入序列是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;beginif y=1 then calc :=xelse calc := calc (x,y-1)+x end;a,b均为正整数，则 calc(a,b)=( )A.a*(b-1) B. a*b C. a+b D. a+a50执行完下列语句段后，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. -+*abcd52允许对队列进行的操作有( )。 A. 对队列中的元素排序 B. 取出最近进队的元素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-front-1 D. rear-front56若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )A. 1和 5 B. 2和4 C. 4和2 D. 5和157栈和队的共同点是( )。 A. 都是先进后出 B. 都是后进先出C. 只允许在端点处插入和删除元素 D. 没有共同点58设栈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. 2594个园盘的Hahoi塔，总的移动次数为( ).A.7 B.-8 C.15 D.1660和顺序栈相比，链栈有一个比较明显的优势是（ ）。A. 通常不会出现栈满的情况 B. 通常不会出现栈空的情况C. 插入操作更容易实现 D. 删除操作更容易实现61执行（ ）操作时，需要使用队列作辅助存储空间。A.查找哈希(Hash)表 B. 广度优先搜索网 C. 先序(根)遍历二叉树 D. 深度优先搜索网62设有一顺序栈已经含有3个元素，如图3.1所示元素a4正等待进栈。下列不可能出现的出栈序列是（ A ）A.a3,a1,a4,a2 B. a3,a2,a4,a1 C. a3,a4,a2,a1 D. a4,a3,a2,a1 a1a2Topa363在一个链队中，若f,r分别为队首、队尾指针，则插入s所指结点的操作为（ B）A.f-next=s;f=s; B.r-next=s;r=s;C.s-next=r;r=s; D.s-next=f;f=s;64若用一个大小为6的数组来实现循环队列，且当rear和front的值分别是0和3。当从队列中删除一个元素，再加入两个元素后，rear 和front 的值分别是（A ）A. 2和4 B. 1和5 C. 4和2 D. 5和165有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ C ）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二、填空题1后缀算式9 2 3 +- 10 2 / -的值为_。中缀算式（3+4X）-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+，stack.sstack.top=x3设输入序列为1、2、3，则经过栈的作用后可以得到_种不同的输出序列。54不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为_。O(1)5设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储_个队列元素；当前实际存储_个队列元素（设头指针F指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置）。m-1，(R-F+M)%M6设有一个顺序共享栈S0：n-1，其中第一个栈项指针top1的初值为-1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是_。top1+1=top27栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为_表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为_表。FILO，FIFO8设某顺序循环队列中有m个元素，且规定队头指针F指向队头元素的前一个位置，队尾指针R指向队尾元素的当前位置，则该循环队列中最多存储_队列元素。m-19设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为_。F=R10从一个栈删除元素时，首先取出 ，然后再前移一位 。栈顶元素、栈顶指针11后缀表达式“2 10 + 5 * 6 9 /”的值为 。612中缀表达示3+X*（2.4/5-6）所对应的后缀表达示为_。3 x 2.4 5 6 *13用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342的出栈顺序，相应的S和X操作串为_SXSSXSXX_。14在循环队列中，存储空间为0n-1,设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么队满标志为front=(rear+1)%n，队空标志为_front=rear_。15对于栈只能在_栈顶位置_插入和删除元素。16设输入元素的顺序是A，B，C，D，通过栈的变换，在输出端可得到各种排列。若输出序列的第一个元素为D，则输出序列为_DCBA_。17队列中允许进行删除的一端为_队头_。18我们通常把队列中允许插入的一端称为_队尾_。19队列的原则是 。先进先出；20顺序存储的队列如果不采用循环方式，则会出现 问题。假溢出21栈的原则是 。先进后出。22对于一个顺序栈作进栈运算时，应先判断栈是否为 ，判断的条件是 ，作出栈运算时，应先判断栈是否为 ，判断的条件是 。满 ;top=MAXSIZE-1 ;空 ;top=-1。23在长度为Maxsize的循环队列中，删除一个新元素，修改front队头指针为 。front=(front+1)/Maxsize 24在链队列中，与入队相关的指针是 、与出队有关的指针是 （头指针或尾指针）。尾指针 、 头指针 25当用长度为N的一维数组顺序存储一个栈时，假定用top=N表示栈空，则表示栈满的条件为 。top = = 026向一个栈顶指针为HS的链栈中插入一个新结点*P果，应执行 和 操作。p-next = HS 、HS = p27从一个栈顶指针为HS的非空链栈中删除结点并不需要返回栈顶结点的值和回收结点时，应执行 操作。HS = HS-next28假定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)*3/(4*(10-7) 、831在一个具有n个单元的顺序栈中，假定以地址高端（即下标为n的单元）作为栈底，以top作为栈顶指针，则当向栈中压入一个元素时，top的变化是top=_。 top-132在作进栈运算时应先判别栈是否_(1)_;在作退栈运算时应先判别栈是否_(2)_；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_(3)_。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_(4)_分别设在内存空间的两端，这样只有当_(5)_时才产生溢出。(1)满 (2)空 (3)n (4)栈底 (5)两栈顶指针相邻（即值之差的绝对值为1）33多个栈共存时，最好用_作为存储结构。链式存储结构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*+的值为_。937在循环队列中，队列长度为n ,存储位置从0到n-1编号，以rear指示实际的队尾元素，现要在此队列中插入一个新元素，新元素的位置是（ ）。 rear=(rear+1)%n38已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是_。s=(LNode *)malloc(sizeof(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)=front41设有元素序列的入栈次序为：（a1,a2,an）,其出栈的次序为(ap1,ap2,apn) 现已知pl=n,则pi=_。n-i+142用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是 _和_；若只设尾指针，则出队和入队的时间复杂度分别是_和_。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+1 n%1044写出下面程序的运行结果 program priout(input，output);procedure print(f1,f2: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);endwriteln(fl,f2);endbegin print (4,16); end.(13 11),(12 12),(9 13),(6 14),(5 15),(4 16) 输出每组两个数占一行，也没括号三、判断题1（ ）不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。T2（ ）在循环顺序队列中插入新元素不需要判断队列是否满了。 3( )入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。T 4（ ）栈是一种先进后出的线性表。 5（ ）消除递归不一定需要使用栈。6（ ）栈是实现过程和函数等子程序所必需的结构。7（ ）设栈采用顺序存贮结构。若已有i-1个元素进栈，则将第i个元素进栈时，进栈算法的时间复杂性为O(i)。8（ ）在链队列中，即使不设置尾指针也能进行入队操作。9（ ）设尾指针的循环链表表示队列,则入队和出队算法的时间复杂度均为O(1)。10（ ）栈和队列都是线性表，只是在插入和删除时受到了一些限制。11（ ）队列在程序调用时必不可少，因此递归离不开队列。12( ) 栈可以作为实现程序设计语言过程调用时的一种数据结构。13（ ）栈又称后进先出表，队列又称为先进先出表。14（ ）栈和队列都是限制存取点的线性结构。四、简答题1简述栈和队列的共同点和不同点。它们与线性表有什么关系？2在一般的顺序队列中，什么是假溢出？怎样解决假溢出问题？当队尾到达数组最后一个单元时，就认为队满，但此时数组前面可能还有空单元，因此叫假溢出。解决的办法采用循环队列。3简述栈和队列这两种数据结构的相同点和不同点。栈和队列都是操作受限的线性表。栈是先进后出，操作在一端进行；队列是先进先出，插入在一端，删除在另一端进行。4如题31图所示，输入元素为A，B，C，在栈的输出端得到一个输出序列ABC，试写出在栈的输入端三个可能的输入序列。 ABC；CBA；ACB5如题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什么是循环队列？用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质（队尾插入和队头删除），容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再入队，然而队列中元素个数小于队列的长度（容量）。循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储单元”或“作标记”的方法解决“队满”和“队空”的判定问题。应该指出，除特别说明，循环队列通常是指顺序存储结构，而不是链式存储结构。7有5个元素，其入栈次序为A,B,C,D,E,在各种可能的出栈序列中，第一个出栈元素为C且第二个出栈元素为D的出栈序列有哪几个？三个：CDEBA，CDBEA，CDBAE8简述递归思想。现有两个正整数M和N，如果采用递归方法解决MN运算，试结合递归思想，说明其终止条件和递归语句是什么？递归是程序设计中的重要技术。利用递归技术编写的程序结构清晰、易读、且其正确性容易证明。当问题的定义是递归的、数据结构是递归的和问题的解法是递归的时，最好利用递归。求解递归问题时，要先写出问题求解的递归定义。递归定义由基本项和归纳项组成。基本项描述了一个或几个递归过程的终结状态，即不需要继续递归就可直接求解的状态。归纳项描述了从当前状态向终结状态的转换。递归过程的实质是将复杂问题分解成若干子问题，子问题与原问题具有相同特征，但是简单了。子问题解决了，原问题迎刃而解。本题求解两个整数M和N相乘，可以利用递归技术变为M个N相加。基本项是M=1,归纳项是(M-1)个N相乘。其递归过程如下：long MultiToAdd(int m,int n) 用递归算法求m*n if(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个元素，可有14种出栈序列，abcd和dcba就是其中两种；有10(4!-14=10)种排列得不到，其中，dabc和adbc是不可能得到的两种。10队列可以用循环单链表来实现，故可以只设置一个头指针或者只设置一个尾指针。请你分析对于循环单链表实现的队列，用哪种方案更合适。循环单链表若只设头指针，则出队操作时间复杂度是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（2Hn-2+1）+1 =22 Hn-2+2+1 =22（2Hn-3+1）+2+1 =23 Hn-3+22+2+1 = 2k Hn-k+2k-1 +2k-2 +21 +20 =2n-1 H1+2n-2+2n-3+21+20 因为H1=1，所以原式Hn=2n-1+2n-2+21+20=2n-1故总盘数为n的Hanoi塔的移动次数是2n-1。12 用一个数组S（设大小为MAX）作为两个堆栈的共享空间。请说明共享方法，栈满/栈空的判断条件，并用C或PASCAL设计公用的入栈操作push（i，x），其中i为0或1，用于表示栈号，x为入栈值。两栈共享一向量空间（一维数组），栈底设在数组的两端，两栈顶相邻时为栈满。设共享数组为SMAX，则一个栈顶指针为-1，另一个栈顶指针为MAX时，栈为空。 用C写的入栈操作push（i，x）如下： const MAX=共享栈可能达到的最大容量 typedef struct node elemtype sMAX； int top2； anode； anode ds; int push(int I,elemtype x)ds为容量有MAX个类型为elemtype的元素的一维数组，由两个栈共享其空间。I的值为0或1x为类型为elemtype的元素。本算法将x压入栈中。如压栈成功，返回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的规则如下：设操作符栈s，初始化为空栈，压入优先级最低的操作符#。对中缀表达式从左向右扫描，遇操作数，直接写入exp2；若是操作符（记为w），分如下情况处理，直至表达式exp1扫描完毕。（1）w为一般操作符（+，-，*，/等），要与栈顶操作符比较优先级，若w优先级高于栈顶操作符，则入栈；否则，栈顶运算符退栈到exp2，w再与新栈顶操作符作上述比较处理，直至w入栈。（2）w为左括号（），w入栈。（3）w为右括号（），操作符栈退栈并进入exp2，直到碰到左括号为止，左括号退栈（不能进入exp2），右括号也丢掉，达到exp2中消除括号的目的。（4）w为#，表示中缀表达式exp1结束，操作符栈退栈到exp2，直至碰到#，退栈，整个操作结束。14有字符串次序为3*-y-a/y2,利用栈，给出将次序改为3y-*ay2/-的操作步骤。（可用X代表扫描该字符串过程中顺序取一个字符进栈的操作，用S代表从栈中取出一个字符加入到新字符串尾的出栈操作。例如，ABC变为BCA的操作步骤为XXSXSS）XSXXXSSSXXSXXSXXSSSS15计算算术表达式的值时，可用两个栈作辅助工具。对于给出的一个表达式，从左向右扫描它的字符，并将操作数放入栈S1中，运算符放入栈S2中，但每次扫描到运算符时，要把它同S2的栈顶运算符进行优先级比较，当扫描到的运算符的优先级不高于栈顶运算符的优先级时，取出栈S1的栈顶和次栈顶的两个元素，以及栈S2的栈顶运算符进行运算将结果放入栈S1中（得到的结果依次用T1、T2等表示）。为方便比较，假设栈S2的初始栈顶为（运算符的优先级低于加、减、乘、除中任何一种运算）。现假设要计算表达式： A-B*C/D+E/F。写出栈S1和S2的变化过程。步骤栈S1栈S2输入的算术表达式（按字符读入）初始A-B*C/D+E/F1AA-B*C/D+E/F2A-B*C/D+E/F3AB-B*C/D+E/F4AB-*C/D+E/F5ABC-*C/D+E/F6AT1（注：T1=B*C）-/D+E/F7AT1D-/D+E/F8AT2（注：T2=T1/D）T3 （注：T3=A-T2）-+E/F9T3E+E/F10T3E+/F11T3EF+/F12T3T4（注：T4=E/F）T5（注：T5= T3+ T4）+16简述顺序存储队列的假溢出的避免方法及队列满和空的条件。设顺序存储队列用一维数组qm表示，其中m为队列中元素个数，队列中元素在向量中的下标从0到m-1。设队头指针为front，队尾指针是rear，约定front指向队头元素的前一位置，rear指向队尾元素。当front等于-1时队空，rear等于m-1时为队满。由于队列的性质（“删除”在队头而“插入”在队尾），所以当队尾指针rear等于m-1时，若front不等于-1，则队列中仍有空闲单元，所以队列并不是真满。这时若再有入队操作，会造成假“溢出”。其解决办法有二，一是将队列元素向前“平移”（占用0至rear-front-1）；二是将队列看成首尾相连，即循环队列（0.m-1）。在循环队列下，仍定义front=rear时为队空，而判断队满则常用两种办法，一是用“牺牲一个单元”，即rear+1=front（准确记是（rear+1）%m=front，m是队列容量）时为队满。另一种解法是“设标记”方法，如设标记tag，tag等于0情况下，若删除时导致front=rear为队空；tag=1情况下，若因插入导致front=rear则为队满。17如果用一个循环数组q0.m-1表示队列时，该队列只有一个队列头指针front，不设队列尾指针rear，而改置计数器count用以记录队列中结点的个数。编写实现队列的三个基本运算：判空、入队、出队（3分）队列中能容纳元素的最多个数是多少？（1分）typedef structElemType qm; int front,count; front是队首指针，count是队列中元素个数cqnode; 定义类型标识符。(1)判空：int Empty(cqnode cq) cq是cqnode类型的变量 if(cq.count=0) return(1)；else return(0); 空队列入队: int EnQueue(cqnode cq，ElemType x)if(count=m)printf(“队满n”)；exit(0); cq.q(cq.front+count)%m=x; x入队 count+; return(1); 队列中元素个数增加1,入队成功出队: int DelQueue(cqnode cq)if(count=0)printf(“队空n”)；return(0); printf(“出队元素”，cq.qcq.front); 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作为双端队列的输入序列，试分别求出以下