习题集.docx

1求整数的二分序列算法如下，该算法的渐近时间复杂度函数是（ ）。void binary ( int n ) while ( n ) printf ( %dn, n); n = n / 2; A、O( log(n) )B、O( n*log2(n) )C、O ( n2 )D、O ( n )正确答案： A2算法分析是为了分析算法的效率以求改进，那么算法分析的两个主要方面是（ ）。A、正确性和简明性B、空间复杂度和时间复杂度C、可读性和文档性D、数据复杂性和程序复杂性正确答案： B3下面说法错误的是（ ） (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2*n)的算法 （3）最坏时间复杂度是指在最坏情况下，估算出来的算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低A、(1)B、(1),(2)C、(1),(4)D、(3)正确答案： C4在下面程序段中，x 赋值语句的频度是（ ） for (i=1;i=n;i+) for (j=1;j=n;j+) x=x+1;A、O(2*n)B、O(n)C、O(n2)D、O(log2(n)正确答案： C5下面有若干算法（关于问题规模 n）的执行时间频度函数和若干渐近时间复杂度函数，请问以下哪个对应关系是正确的。(1) 100*n3 (2) 6*n2 - 12*n + 1 (3) 1024 (4) n + 2*log2(n) (5) n*(n + 1)*(n + 2) / 6 (6) 2(n+1) + 100 * n(a) O(1) (b) O( 2n) (c) O(n) (d) O(n2) (e) O( log2(n) ) (f) O ( n3)A、(1)-(a) (2)-(b) (3)-(c) (4)-(d) (5)-(e) (6)-(f)B、(1)-(f) (2)-(d) (3)-(a) (4)-(c) (5)-(f) (6)-(b)C、(1)-(f) (2)-(e) (3)-(d) (4)-(c) (5)-(b) (6)-(a)D、(1)-(f) (2)-(b) (3)-(c) (4)-(e) (5)-(f) (6)-(b)正确答案： B6在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（ ）。A、数据的处理方法B、数据元素的类型C、数据元素之间的关系D、数据的存储方法正确答案： C7数据结构在计算机内存中的表示是指（ ）A、数据的存储结构B、数据结构C、数据的逻辑结构D、数据元素之间的关系正确答案： A8算法的计算量的大小称为算法的（ ）。A、效率B、复杂度C、现实性D、难度正确答案： B9在数据结构中，从逻辑关系上可以把数据结构分成（ ）A、动态结构和静态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构正确答案： C10算法的时间复杂度取决于（ ）。A、问题的规模B、待处理数据的初态C、A和BD、执行算法的计算机速度正确答案： C11在数据结构中，与所使用的计算机无关的是数据的（ ）结构。A、逻辑B、存储C、逻缉和存储D、物理正确答案： A12计算机执行下面的语句时，语句 s 的执行次数为（ ） 。for ( i=1; i=i; j-) s;A、n*(n+1)/2B、n*(n-1)/2C、n2D、(n-2)*(n+3)/2正确答案： D13下面算法的渐近时间复杂度函数分别是（ ）。void combi ( int n ) int i, j, k; for ( i=1; i=n; i+) for ( j=i+1; j=n; j+) for ( k=j+1; kdata=x;_；r-next=s；r=s；A、r-next=s-nextB、r-next=s;C、s-next=r-nextD、s-next=r正确答案： C24表达式3* 2(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（ ），其中为乘幂A、3,2,4,1,1；(*(+*-B、3,2,8；(*-C、3,2,4,2,2；(*(-D、3,2,8；(*(-正确答案： D25函数调用时，为处理参数及返回地址，要用一种称为（ ）的数据结构A、队列B、多维数组C、栈D、线性表正确答案： C26设有顺序栈 S，元素 s1, s2, s3, s4, s5, s6 依次进栈，若这 6 个元素出栈顺序是 s2, s3, s4, s6 , s5, s1，则栈的容量至少应该是A、2B、3C、5D、6正确答案： B27一个栈的输入序列是 1、2、3，则不可能的栈输出序列是( )。A、3 1 2B、1 2 3C、3 2 1D、以上都可能正确答案： A28下面的程序段执行完后，变量 i 值应该是：int func ( int x ) if ( x0 ) return x * func ( x-1 ); else return 2;int i;i = func ( func(1) );A、2B、4C、8D、无限递归正确答案： B29队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是_。A、先进先出B、先进后出C、先进不出D、后进不出正确答案： A30已知循环队列用数组 A 0.m-1 存放元素，其头尾指示器分别是 front 和 rear，则队列的元素个数是（ ）。A、rear-front+1B、rear-front+mC、(rear-front+m)%mD、(rear-front+1)%m正确答案： C31已知一个栈的进栈序列是 1，2，3，n，输出序列是 p1，p2，p3，.，pn，若 p13，则 p2 应该A、可能是2B、一定是2C、可能是1D、一定是1正确答案： A32链栈定义如下：typedef struct Node int data; struct Node * next; StackNode, *LStack;以下函数实现了(带头结点的)链栈初始化，请问_处用哪条语句予以填充。void InitStack ( LStack *S ) _;A、S=NULLB、S-next=NULLC、S.next=NULLD、以上都不对正确答案： B33有链栈定义如下：typedef struct Node int data; struct Node * next; StackNode, *LStack;以下函数实现了(带头结点)链栈上的进栈，请问空白处应用哪些语句予以填充。void Push（LStack *S, int x） LStack p; p=(LStack)malloc(sizeof(StackNode); _; p-next=S-next; _;A、p-data=x S-next=p-nextB、S-next=p p-data=xC、p-data=x S=pD、p-data=x S-next=p正确答案： D34若栈中已有 n 个元素，在作进栈操作时发生了溢出，则说明该栈的最大容量是A、n-1B、nC、n+1D、n/2正确答案： B35若栈采用数组方式存储，现将两个栈共享一个数组 v 0.m-1 的空间，数组元素 topi 代表第 i 个栈( i =1, 2)栈顶，栈 1 的栈底在 v0，栈 2 的栈底在 vm-1，则栈满的判定条件应该是A、top2-top1的绝对值=0B、top1+1=top2C、top1+top2=mD、top1=top2正确答案： B36以下运算实现在(元素为整数的)链队列上的入队操作，请问空白处应用哪些语句予以填充。void EnQueue ( LinkQueue *q, int x) LNode *p; p=(LNode *)malloc(sizeof(LNode); _=x; p-next=NULL; (q-rear)-next=_; _;A、p-data p q-rear=pB、p-data p q-rear=p-nextC、p-data p q=pD、p p-data q-rear=p正确答案： A37一个栈的输入序列是：1，2，3则不可能的栈输出序列是_。A、3 2 1B、1 2 3C、2 1 3D、 3 1 2正确答案： D38循环队列的队满条件应该是（提示：队尾指示器始终指向末元素的下一个可用空位）A、(sq.rear+1) % maxsize =(sq.front+1) % maxsizeB、(sq.front+1) % maxsize =sq.rearC、(sq.rear+1) % maxsize =sq.frontD、sq.rear =sq.front正确答案： C39栈和队列的共同点是A、都是先进先出B、都是先进后出C、只允许在端点处插入和删除元素D、没有共同点正确答案： C40循环队列用数组A0.m-1存放其元素值，已知其头尾指针分别是front和rear ，则当前队列的元素个数是( )A、(rear-front)%mB、(rear-front+1)%mC、(front-rear+1)%mD、rear-front正确答案： B41队列是限制插入只能在表的一端、删除在表的另一端进行的线性表，其特点是( )。A、LILOB、LIFOC、FILOD、以上都不对正确答案： A42顺序栈定义如下：typedef struct int data; int top; /等于实际栈顶元素的下标 int stacksize; int incrementsize; SqStack;以下函数实现了退栈操作，请问空白处应用哪些语句予以填充。int Pop (SqStack *S, int *x) if ( _ ) return 0; *x=_; S-top = _; return 1;A、S-top =0 S-elemS-top S-top - 1B、S-top =-1 S-elemS-top S-top - 1C、S-top =-1 S-top - 1 S-elemS-topD、S-top =0 S-top - 1 S-elemS-top正确答案： B43线性表L=（a1,a2,an）用数组实现，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是（ ）。A、(n-1)/2B、n/2C、(n+1)/2D、以上都不对正确答案： A44以下说法错误的是 ( )A、对于线性表来说，定位运算LocateElem在顺序表和单链表上的时间复杂度均为O（n）B、指定位置读取元素操作在顺序表上只需常数时间O（1）便可实现，因此顺序表是一种随机存取结构C、在链表上实现读表元运算的平均时间复杂度为O（1）D、插入、删除操作在链表上的实现可在O（1）时间内完成E、插入、删除操作在顺序表上的实现，平均时间复杂度为O（n）正确答案： C45对于顺序表，以下说法错误的是（ ）A、顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的内存物理地址B、顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列C、顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻D、顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中正确答案： A46长度为 n 的线性表是具有 n 个（ ）的有限序列（n0）A、表元素B、字符C、数据元素D、数据项E、信息项正确答案： C47在循环链表中，将头指针改设为尾指针（rear）后，其头结点和尾结点的存储位置分别是（ ）A、rear和rear-next-nextB、rear-next 和rearC、rear-next-next和rearD、rear和rear-next正确答案： B48对于顺序存储的线性表，指定位序访问元素和增加、删除元素的时间复杂度为（ ）A、O(n) O(n)B、O(n) O(1)C、O(1) O(n)D、O(1) O(1)正确答案： C49对于顺序表的插入算法而言，若以结点移动为标准操作，则插入算法的在最坏情况下的移动次数为（ ），时间复杂度是（ ）；在平均情况下的移动次数为（ ），时间复杂度是（ ）。A、n, O(n), n/2, O(n/2)B、n/2, O(n), n/2, O(n)C、n, O(n), n, O(n)D、n, O(n), n/2, O(n)正确答案： D50以下为顺序表的查找算法，分析算法，请在空白处填上正确的语句int LocateElem_Sq ( SqList L, ElemType X) /在 L 中查找第一值等于 X 的元素。若找到则返回该元素位序号；否则返回 0 _; while ( ( i =L.length ) & ( L.elemi-1 != X) ) i+; if( _ ) return i; else return 0;A、i=0, iB、i=1, i=L.lengthC、i=1, iD、i=0, inext=s;s-next=p-nextB、s-next=p-next;p-next=sC、p-next=s;p-next=s-nextD、p-next=s-next;p-next=s正确答案： B53静态链表中指针表示的是（ ）A、内存地址B、数组下标C、下一元素地址D、左、右孩子地址正确答案： B54若某线性表中最常用的操作是读取第 i 个元素和找第 i 个元素的前趋，则采用（ ）存储方式最节省时间A、顺序表B、单链表C、双链表D、单循环链表正确答案： A55对于一个头指针为 head 的带头结点的单链表，判定该链表为空的条件是（ ）A、head=NULLB、headnext=NULLC、headnext=headD、head!=NULL正确答案： B56下面关于线性表的叙述中，错误的是哪一个？A、线性表采用顺序存储，必须占用一片连续的存储单元B、线性表采用顺序存储，便于进行插入和删除操作C、线性表采用链接存储，不必占用一片连续的存储单元D、线性表采用链接存储，便于插入和删除操作正确答案： B57设单链表的结点结构为 (data, next)，其中 next 为指针域。已知有指针 px 指向单链表中 data=x 的结点，指针 py 指向 data=y 的新结点，若需要将 y 插入到 x 之后，则需要执行以下语句（ ）A、px-next=py; py-next=px-next;B、py-next=px-next; px-next=py;C、px-next=py-next; py-next=px;D、py-next=px; px-next=py-next;正确答案： B58链表不具有的特点是（ ）A、插入、删除不需要移动元素B、可随机访问任一元素C、不必事先估计存储空间D、所需空间与表长度成正比正确答案： B59设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最方便A、单链表B、单循环链表C、带尾指针的单循环链表D、带头结点的双循环链表正确答案： D60下述哪一条是顺序存储结构的优点？A、存储空间紧凑B、插入运算方便C、删除运算方便D、可方便地用于各种逻辑结构的存储表示正确答案： A61顺序表是线性表的（ ）A、链式存储结构B、顺序存储结构C、索引存储结构D、散列存储结构正确答案： B62线性表（ a1,a2,an）以单链表存储时，访问第 i 个元素的时间复杂性为（ ）A、O（i）B、O（1）C、O（n）D、O（i-1）正确答案： C63在单链表中若在每个结点中增加一个指针域,所含指针指向前驱结点，这样构成的链表中有两个方向不同的链，称为( )。A、双向链表B、单链表C、循环链表D、双向循环链表正确答案： A64对于双向链表，在两个结点之间插入一个新结点需修改的指针共（ ）个，而单链表需要修改（ ）个。A、2, 1B、1, 2C、2, 4D、4, 2正确答案： D65用单链表实现线性表的基本思想是：用（ ）表示结点间的逻辑关系。A、元素下标B、结点相邻C、链接指针D、以上都错正确答案： C66计算机执行下面的语句时，语句s的执行次数为 （_）。 for (i=l；i=i;j-) s;正确答案：第一空： (n+3)(n-2)/267对于给定的n个元素,可以构造出的逻辑结构有（_），（_），（_），（_）四种。正确答案：第一空： 集合第二空： 线性结构第三空： 树形结构第四空： 图68程序段 i=1; while (inext=ls; _; 正确答案：第一空： p-data=x,第二空： ls=p75队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是_。正确答案：第一空： 先进先出76一个栈的输入序列是：1，2，3则不可能的栈输出序列是_。正确答案：第一空： 3 1 277循环队列的引入，目的是为了克服_。正确答案：第一空： 假溢出时大量移动数据元素78以下运算实现在链队上的入队列，请在_处用适当句子予以填充。 Void EnQueue(QueptrTp *lq,DataType x) LqueueTp *p; p=(LqueueTp *)malloc(sizeof(LqueueTp); _=x; p-next=NULL; (lq-rear)-next=_; _; 正确答案：第一空： p-data,第二空： p第三空： lq-rear=p79已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是_ _、_ _、_ _、_ _、_ _。正确答案：第一空： s=(LinkedList)malloc(sizeof(LNode)；第二空： s-data=x;第三空： s-next=r-next；第四空： r-next=s；第五空： r=s；80链栈定义如下： Typedef Struct Node DataType data; Struct Node * next; StackNode,*LstackTp; 以下运算实现在链栈上的退栈，请在_处用请适当句子予以填充。 Int Pop(LstackTp &ls,DataType &x) LstackTp p; if(ls!=NULL) p=ls; x=_; ls=ls-next; _; return(1)； else return(0); 正确答案：第一空： p-data,第二空： free(p)81表达式求值是_应用的一个典型例子。正确答案：第一空： 栈82单链表表示法的基本思想是用_表示结点间的逻辑关系。正确答案：第一空： 指针83线性表L=（a1,a2,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_。正确答案：第一空： （n-1）/284对于双向链表,在两个结点之间插入一个新结点需修改的指针共 _个，单链表为_个。正确答案：第一空： 4第二空： 285以下为顺序表的定位运算，分析算法，请在横线处填上正确的语句。 int locate_sqlist(sqlist L,datatype X) /*在顺序表L中查找第一值等于X的结点。若找到回传该结点序号；否则回传0*/ _; while(iL.last)&(L.datai-1!=X) i+; if(_) return(i); else return(0); 正确答案：第一空： i=1第二空： iL.last86对单链表中元素按插入方法排序的C语言描述算法如下，其中L为链表头结点指针。请填充算法中标出的空白处，完成其功能。 typedef struct node int data; struct node *next; linknode,*link; void Insertsort(link L) link p,q,r,u; p=L-next; (1) ; while(2) ) r=L; q=L-next; while(3) & q-datadata) r=q; q=q-next; u=p-next; (4) ; (5) ; p=u; 正确答案：第一空： L-next=null置空链表,然后将原链表结点逐个插入到有序表中第二空： p!=null当链表尚未到尾，p为工作指针第三空： q!=null查p结点在链表中的插入位置，这时q是工作指针。第四空： p-next=r-next将p结点链入链表中第五空： r-next=p r是q的前驱，u是下个待插入结点的指针87在单链表中若在每个结点中增加一个指针域,所含指针指向前驱结点，这样构成的链表中有两个方向不同的链，称为_。正确答案：第一空： 双向链表88设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:_； _;正确答案：第一空： py-next=px-next第二空： px-next=py89对于顺序表的插入算法insert_sqlist来说，若以结点移动为标准操作，则插入算法的在最坏情况下的移动次数为_，时间复杂度是_。在平均情况下的移动次数为_，时间复杂度是_。正确答案：第一空： n第二空： O(n)第三空： n/2第四空： O(n)90hc 在带头结点的非空单链表中，头结点的存储位置由( )指示，首元素结点的存储位置由( )指示，除首元素结点外，其它任一元素结点的存储位置由( )指示。正确答案：第一空： 头指针第二空： 头结点指针域第三空： 前驱结点指针域91顺序存储方式的优点是存储密度大，且插入、删除运算效率高。正确答案： 92线性表若采用链式存储结构时，要求内存中可用存储单元的地址一定是不连续的。正确答案： 93数据元素是数据的最小单位。正确答案： 94记录是数据处理的最小单位。正确答案： 95数据的物理结构是指数据在计算机内的实际存储形式。正确答案： 96数据的逻辑结构是指数据的各数据项之间的逻辑关系.正确答案： 97线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。正确答案： 98算法就是程序。正确答案： 99数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构。正确答案： 100对任何数据结构，链式存储结构一定优于顺序存储结构。( )正确答案： 101线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( )正确答案： 102顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( )正确答案： 103链表是采用链式存储结构的线性表，在进行指定位置插入、删除操作时，在链表中比在顺序存储结构中时间效率高。 ( )正确答案： 104顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( )正确答案： 105线性表就是顺序存储的表。( )正确答案： 106链表中的头结点仅起到标识的作用。( )正确答案： 107所谓静态链表就是一直不发生变化的链表。( )正确答案： 108线性表只能用顺序存储结构实现。( )正确答案： 109循环链表不是线性表. ( )正确答案： 110要求循环队列不损失一个空间全部都能得到利用，设置一个标志tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此相应的入队与出队算法。正确答案：入队算法：int EnterQueue(SeqQueue *Q, QueueElementType x) /*将元素x入队*/ if(Q-front=Q-front & tag=1) /*队满*/ return(FALSE); if(Q-front=Q-front & tag=0) /*x入队前队空，x入队后重新设置标志*/ tag=1;Q-elememtQ-rear=x;Q-rear=(Q-rear+1)%MAXSIZE; /*设置队尾指针*/Return(TRUE); 出队算法： int DeleteQueue( SeqQueue *Q , QueueElementType *x) /*删除队头元素，用x返回其值*/if(Q-front=Q-rear & tag=0) /*队空*/ return(FALSE);*x=Q-elementQ-front;Q-front=(Q-front+1)%MAXSIZE; /*重新设置队头指针*/if(Q-front=Q-rear) tag=0; /*队头元素出队后队列为空，重新设置标志域*/Return(TUUE); 111设表达式以字符形式已存入数组En中，#为表达式的结束符，试写出判断表达式中括号（和）是否配对的C语言描述算法：EXYX(E); (注：算法中可调用栈操作的基本算法。)正确答案：题目分析判断表达式中括号是否匹配，可通过栈，简单说是左括号时进栈，右括号时退栈。退栈时，若栈顶元素是左括号，则新读入的右括号与栈顶左括号就可消去。如此下去，输入表达式结束时，栈为空则正确，否则括号不匹配。 int EXYX(char E,int n) /E是有n字符的字符数组，存放字符串表达式，以#结束。本算法判断表达式中圆括号是否匹配。char s30; /s是一维数组，容量足够大，用作存放括号的栈。 int top=0; /top用作栈顶指针。 stop= #; /#先入栈，用于和表达式结束符号#匹配。 int i=0; /字符数组E的工作指针。 while(Ei!= #) /逐字符处理字符表达式的数组。 switch(Ei) case(: s+top=(; i+ ; break ;case): if(stop=(top-; i+; break;elseprintf(“括号不配对”);exit(0);case#: if(stop=#)printf(“括号配对n”);return (1);else printf(“ 括号不配对n”);return (0); /括号不配对 default : i+; /读入其它字符，不作处理。 /算法结束。算法讨论本题是用栈判断括号匹配的特例：只检查圆括号的配对。一般情况是检查花括号（，）、方括号（，）和圆括号（，）的配对问题。编写算法中如遇左括号（，或（）就压入栈中，如遇右括号（，或），则与栈顶元素比较，如是与其配对的括号（左花括号，左方括号或左圆括号），则弹出栈顶元素；否则，就结论括号不配对。在读入表达式结束符#时，栈中若应只剩#，表示括号全部配对成功；否则表示括号不匹配。 另外，由于本题只是检查括号是否匹配，故对从表达式中读入的不是括号的那些字符，一律未作处理。再有，假设栈容量足够大，因此入栈时未判断溢出。112画出对算术表达式A-B*C/D-EF求值时操作数栈和运算符栈的变化过程。正确答案： 113设有两个栈S1,S2都采用顺序栈方式，并且共享一个存储区O.maxsize-1,为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。正确答案：题目分析两栈共享向量空间，将两栈栈底设在向量两端，初始时，s1栈顶指针为-1，s2栈顶为maxsize。两栈顶指针相邻时为栈满。两栈顶相向，迎面增长，栈顶指针指向栈顶元素。#define maxsize 两栈共享顺序存储空间所能达到的最多元素数#define elemtp int /假设元素类型为整型typedef structelemtp stackmaxsize; /栈空间 int top2; /top为两个栈顶指针stk;stk s; /s是如上定义的结构类型变量，为全局变量。(1)入栈操作：int push(int i,int x)/入栈操作。i为栈号，i=0表示左边的栈s1，i=1表示右边的栈s2，x是入栈元素。入栈成功返回1，否则返回0。if(i1)printf(“栈号输入不对”);exit(0);if(s.top1-s.top0=1) printf(“栈已满n”);return(0);switch(i) case 0: s.stack+s.top0=x; return(1); break; case 1: s.stack-s.top1=x; return(1);/push（2） 退栈操作 elemtp pop(int i) /退栈算法。i代表栈号，i=0时为s1栈，i=1时为s2栈。退栈成功返回退栈元素，否则返回-1。 if(i1)printf(“栈号输入错误n”)；exit(0); switch(i) case 0: if(s.top0=-1) printf(“栈空n”)；return（-1）； else return(s.stacks.top0-); case 1: if(s.top1=maxsize printf(“栈空n”); return(-1); else return(s.stacks.top1+); /算法结束 算法讨论 请注意算法中两栈入栈和退栈时的栈顶指针的计算。两栈共享空间示意图略，s1栈是通常意义下的栈，而s2栈入栈操作时，其栈顶指针左移（减1），退栈时，栈顶指针右移（加1）。114请利用两个栈S1和S2来模拟一个队列。已知栈的三个运算定义如下：PUSH(ST,x):元素x入ST栈；POP(ST,x)：ST栈顶元素出栈，赋给变量x；Sempty(ST)：判ST栈是否为空。那么如何利用栈的运算来实现该队列的三个运算：enqueue:插入一个元素入队列； dequeue:删除一个元素出队列；queue_empty：判队列为空。（请写明算法的思想及必要的注释）正确答案：题目分析栈的特点是后进先出，队列的特点是先进先出。所以，用两个栈s1和s2模拟一个队列时，s1作输入栈，逐个元素压栈，以此模拟队列元素的入队。当需要出队时，将栈s1退栈并逐个压入栈s2中，s1中最先入栈的元素，在s2中处于栈顶。s2退栈，相当于队列的出队，实现了先进先出。显然，只有栈s2为空且s1也为空，才算是队列空。(1) int enqueue(stack s1,elemtp x)/s1是容量为n的栈，栈中元素类型是elemtp。本算法将x入栈，若入栈成功返回1，否则返回0。if(top1=n & !Sempty(s2) /top1是栈s1的栈顶指针，是全局变量。printf(“栈满”);return(0); /s1满s2非空,这时s1不能再入栈。if(top1=n & Sempty(s2) /若s2为空，先将s1退栈,元素再压栈到s2。 while(!Sempty(s1) POP(s1,x);PUSH(s2,x); PUSH(s1,x); return(1); /x入栈，实现了队列元素的入队。(2) void dequeue(stack s2,s1)/s2是输出栈，本算法将s2栈顶元素退栈，实现队列元素的出队。if(!Sempty(s2) /栈s2不空，则直接出队。 POP(s2,x); printf(“出队元素为”,x); else /处理s2空栈。 if(Sempty(s1) printf(“队列空”);exit(0);/若输入栈也为空，则判定队空。 else /先将栈s1倒入s2中，再作出队操作。 while(!Sempty(s1) POP(s1,x);PUSH(s2,x); POP(s2,x); /s2退栈相当队列出队。 printf(“出队元素”，x); /结束算法dequue。(3) int queue_empty()/本算法判用栈s1和s2模拟的队列是否为空。if(Sempty(s1)&Sempty(s2) return(1);/队列空。 else return(0