数据结构：栈和队列(11页).doc

-数据结构：栈和队列1. 在一个具有n个单元的顺序栈中，假定以地址低端作为栈底，以top作为栈顶指针， 则当做退栈处理时，top变化为_。A. top不变 B. top-n C. toptop-1 D.top=top+12. 向顺序栈中压入元素时，是_。A.先移动栈顶指针，后存入元素 B.先存入元素，后移动栈顶指针 3. 在一个顺序存储的循环队列中，队首指针指向队首元素的_。A.前一个位置 B.后一个位置 C.队首元素位置4. 若进栈序列为1,2,3,4,进栈过程中可以出栈，则_不可能是一个出栈序列。A.3,4,2,1 B.2,4,3,1 C.1,4,3,2 D.3,2,1,45. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空的条件是_。A.front= =rear+1 B.front+1= =rear C.front= =rear D.front= =06. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队满的条件是_。A.rear % n= =front B.(rear-1) % n= =front C.(rear-1) % n= =rear D.(rear+1) % n= =front7. 向一个栈项指针为hs的链栈中插入一个*s结点时，则执行_。A.hs->next=s; B.s->next=hs->next; hs->next=s; C.s->next=hs；hs=s; D.s->next=hs; hs=hs->next;8. 在一个链队列中，假定front和rear分别为队首指针和队尾指针，则进行插入*s结点的操作时应执行_。A.front->next=s; front=s; B.rear->next=s; rear=s; C.front=front->next; D.front=rear->next;9. 栈的特点是_队的特点是_A.先进先出 B.先进后出 B|A10. 栈和队列的共同点是_。A.都是先进后出 B.都是先进先出 C.只允许在端点处插入和删除元素 D.没有共同点11. 一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是_。A.edcba B.decba C.dceab D.abcde12. 若己知一个栈的进栈序列是1,2,3,n,其输出序列为p1,p2,p3,pn,若p1=n,则pi(1<i<=n)为_。A.i B.n=I C.n-i+1 D.不确定13. 若己知一个栈的进栈序列是1,2,3,n,其输出序列为p1,p2,p3,pn,若pn=n,则pi(i<=i<n)为_。A.i B.n=I C.n-i+1 D.不确定14. 若己知一个栈的进栈序列是1,2,3,n,其输出序列为p1,p2,p3,pn，若p1=3,则p2_。A.可能是2 B.一定不是2 C.可能是1 D.一定是1 15. 若己知一个栈的进栈序列p1,p2,p3,pn,输出序列是1,2,3,n,若p3=1,则p1_。A.可能是2 B.一定是2 C.不可能是2 D.不可能是3 16. 若己知一个栈的进栈序列p1,p2,p3,pn,输出序列是1,2,3,n,若p3=1,则p1_。A.n-i+1 B.n-i C.i D.有多种可能17. 判定一个顺序栈st(最多元素为MaxSize)为空的条件是_。A.st->top!=-1 B.st->top=-1 C.st->top!=MaxSize-1 D.st->top=MaxSize-118. 判定一个顺序栈st(最多元素为MaxSize)为栈满的条件是_。A.st->top!=-1 B.st->top=-1 C.st->top!=MaxSize-1 D.st->top=MaxSize-119. 最不适合用作链栈的链表是_。A.只有表头指针没有表尾指针的循环双链表 B.只有表尾指针没有表头指针的循环双链表 C.只有表尾指针没有表头指针的循环单链表 D.只有表头指针没有表尾指针的循环单链表20. 向一个栈项指针为hs的链栈中插入一个s所指结点时，则执行_。A.hs->next=s; B.s->next=hs->next;hs->next=s; C.s->next=hs;hs=s; D.s->next=hs;hs=hs->next;21. 从一个栈项指针为hs的链栈中删除一个结点时，用x保存被删结点的值，则执行_。A.x=hs;hs=hs->next; B.x=hs->data; C.hs=hs->next;x=hs->data; D.x=hs->data;hs=hs->next; 22. 一个队列的入队序列是1,2,3,4,则队列的输出序列是_。A.4,3,2,1 B.1,2,3,4, C.1,4,3,2 D.3,2,4,123. 判定一个环形队列qu(最多元素为MaxSize)为空的条件是_。A.qu->rear-qu->front=MaxSize B.qu->rear-qu->front-1=MaxSize C.qu->front=qu->rear D.qu->front=qu->rear+1 24. 判定一个环形队列qi(最多元素为MaxSize)为满队列的条件是_。A.(qu->rear+1)%MaxSize=qu->front B.qu->rear-qu->front-1=MaxSize C.qu->front=qu->rear D.qu->front=qu->rear+1 25. 环形顺序队列中是否可以插入下一个元素,_。A.与队头指针的队尾指针的值有关 B.只与队尾指针的值有关,与队头指针的值无关 C.只与数组大小有关,与队首指针和队尾指针的值无关 D.与曾经进行过多少次插入操作有关26. 环形队列用数组A0.MaxSize-1存放其元素值,己知其头尾指针分别是front和rear,则当前队列的元素个数是_。A.(rear-front+MaxSize)%MaxSize B.rear-front+1 C.(rear-front-1)%MaxSize D.(rear-front)%MaxSize27. 若用一个大小为6的一维数组来实现环形队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是_。A.1和5 B.2和4 C.4和2 D.5和128. 最不适合用作链队的链表是_。A.只带队头指针的非循环双链表 B.只带队头指针的循环双链表 C.只带队尾指针的循环双链表D.只带队尾指针的循环单链表29. 在一个链队中，假设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; 30. 在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算是_。A.r=f->next; B.r=r->next; C.f=f->next; D.f=r->next;31. 用单链表表示的链队的队头在链用不着的_位置。A.链头 B.链尾 C.链中 D.任意 32. 中缀表达式A*(B+C)/(D-E+F)的后缀表达式是_。A.A*B+C/D-E+F B.AB*C+D/E-F+ C.ABC+*DE-+/ D.ABCDEF*+/-+ 33. 己知一个栈的进栈序列是ABC,出栈序列为CBA,经过的栈操作是_。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,pop34. 判定一个顺序栈st为(元素个数最多为MaxSize)空的条件为_。A.st.top=-1 B.st.top!=-1 C.st.top!=MaxSize D.st.top=MaxSize35. 判定一个顺序栈st(元素个数最多为MaxSize)为栈满的条件是_。A.st.top!=-1 B.st.top=-1 C.st.top!=MaxSize-1 D.st.top=MaxSize-136. 表达式a*(b+c)-d的后缀表达式是_。A.abcd*+- B.abc+*d- C.abc*+d- D.-+*abcd37. 表达式(2+2*3)*2+6*3/2的后缀表达式是_。A.2 2 3 * + 2 * 6 3 * 2 / + B.2 2 * 3 + 2 * 6 3 * 2 / + C.2 2 3 * 2 * 6 3 * + 2 / + D.2 2 3 * + 2 6 3 * 2 / + *38. 链栈与顺序栈相比有一个明显的优点,即_。A.插入操作更方便 B.通常不会出现栈满的情况 C.不会出现栈空的情况 D.删除操作更加方便39. 最不适合用作链栈的链表是_。A.只有表头指针没有表尾指针的循环双链表 B.只有表尾指针没有表头指针的循环双链表C.只有表尾指针没有表头指针的循环单链表 D.只有表头指针没有表尾指针的循环单链表40. 如果以链表作为栈的存储结构,则退链栈操作时_。A.必须判别栈是否满 B.判别链栈元素的类型 C.必须差别链栈是否空 D.对链栈不作任何差别41. 向一个不带头结点的栈指针为1st的链栈中插入一个s所指结点时,则执行_。A.1st->next=s; B.s->next=1st->next;1st->next=s; C.s->next=1st;1st=s; D.s->next=1st;1st=1st->next;42. 从一个不带头结点的栈顶指针为1st的链栈中删除一个结点时,用x保存被删结点的值,则执行_。A.x=1st;1st=1st->next; B.x=1st->data; C.1st=1st->next;x=1st->data; D.x=1st->data;1st=1st->next;43. 一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是_.A.edcba B.decba C.dceab D.abcde 44. 在一个长度为n的顺序存储的集合中查找值为x的元素时，在等概率情况下，查找成功时的平均查找长度为_。A.n B.n/2 C.(n+1)/2 D.(n-1)/245. 在一个长度为n的链接存储的集合中查找值为x的元素时，算法的时间复杂度为_。A.O(1) B.O(n) C.O(n*n) D.O(lbn)46. 已知一个元素x不属于一个长度为n的顺序或链接存储的集合中的元素，把它插入集合时不进行比较过程，则插入过程的时间复杂度为_。A.O(1) B.O(lbn) C.O(n) D.O(n*n)47. 设一个具有t个非零元素的m*n大小的稀疏矩阵采用顺序存储，求其转置矩阵的普通转置算法的时间复杂度为_。A.O(m) B.O(n) C.O(n+t) D.O(n*t)判断题：1. 栈底元素是不能删除的元素。 F2. 顺序栈中元素值的大小是有序的。 F3. 在n个元素进栈后,它们的出栈顺序和进栈顺序一定正好相反。 T4. 栈顶元素和栈底元素有可能是同一个元素。 T5. 若用S1-Sm表示顺序栈的存储空间,则对栈的进栈、出栈操作最多只能进行m次。 F6. 栈没有栈顶指针。 F填空题：1. 在具有n个单元、顺序存储的循环队列中，队满时共有_个元素。n-12. 栈和队列的区别仅在于_。删除运算的不同3. 通常元素进栈的操作是_。先移动栈顶指针，后存入元素4. 通常元素退栈的操作是_。先取出元素，后移动栈顶指针5. 一个栈的输入序列是12345,则栈的输出序列432512是_。 不可能的6. 一个栈的输入序列是12345,则栈的输出序列12345是_。 可能的7. 设有一个顺序栈S,元素s1,s2,s3,s4,s5,s6依次进栈,如果6个元素的出栈顺序为s2,s3,s4,s6,s5,s1,则顺序栈的容量至少应为_。 38. 设栈采用顺序存储结构,若己知i-1个元素进栈,则将第i个元素进栈时,进栈算法的时间复杂度为_。 O（1）9. 若用不带头结点的单链表来表示链栈S,则创建一个空栈所要执行的操作是_。 S=NULL10. 从环形队列中插入一个元素时,通常的操作是_。 先存放元素,后移动队尾指针11. 从环形队列中插入一个元素时,通常的操作是_。从环形队列中插入一个元素时,通常的操作是_。 MaxSize-112. 在链表qu中,判定只有一个结点的条件是_。 qu->front=qu->rear&&qu->front!=NULL13. 设栈S和队列Q的初始状态为空,元素a1,a2,a3,a4,a5,a6,a7和a8依次通过栈S,一个元素出栈后立即进入队列Q,若8个元素出队列的顺序是a3,a6,a7,a5,a8,a4,a2,a1,则栈S的容量至少应该是多少(即至少应该容纳多少个元素)? 514. 设有算术表达式x+a*(y-b)-c/d,该表达式的前缀表达为_。后缀表示为_。 -+x*a-yb/cd|xayb-*+cd/-15. 栈是一种具有_特性的线性表。 后进先出16. 顺序栈和链栈的区别仅在于_的不同。 存储结构17. 如果栈的最大长度难以估计,则最好使用_。 链栈18. 一个栈的输入序列是12345,则栈的输出序列12345是_。 可能的19. 设栈采用顺序存储结构,若己知i-1个元素进栈,则将第i个元素进栈时,进栈算法的时间复杂度为_。 O(1)20. 表达式23+(12*3-2)/4+34*5/7)+108/9的后缀表达式是_。 23 12 3 * 2 - 4 / 34 5 * 7 / + + 108 9 / +21. 若用不带头结点的单链表来表示链栈1st,则创建一个空栈所要执行的操作是_。 1st=NULL22. 对于链栈1st,进栈操作在_端进行,出栈操作在_端进行。 链栈头|链栈头23. 将递归算法转换为非递归算法时,通常使用_这种数据结构。栈24.有如下递归算法:void print (int w) int i; if (w!=0) print(w-1); for(i=1;i<=w;i+) printf("%3d",w); printf("n");调用语句printf(4)的结果是_。 122333444425. 有如下递归过程:void reverse(int m) printf("%d",n%10); if (n/10 !=0) reverse(n/10);调用语句reverse(582)的结果是_。 28526. 求顺序存储的集合的长度的时间复杂度为_。 O(1)27. 求链接存储的集合的长度的时间复杂度为_。 O(n)28. 设集合S的长度为n，则判断x是否属于集合的时间复杂度为_ O(n)29. 在稀疏矩阵的顺序存储中，利用一个数组来存储非零元素，该数组的长度应_对应三元组线性表的长度。 大于等于算法分析题：1. 设计一个算法,利用栈的基本运算将指定栈中的内容进行逆转。答：、status Nizhuan(sqstacks, int a, int b, int t)If(s.top=s.base)error(no data);for(i=0;i<s.stacksize/2;i+)a=*-top;b=*s.base;a=t;t=b;b=a;s.top-;s.base+;2. 设计一个算法,利用栈的基本运算返回指定栈中的栈底元素。答：status Getbase(Aqstacks,int &e)If(s.top=s.base) Error(no data)else e =*s.base;return e;3. 有两个栈s1和s2共享存储空间c1.MaxSize,其中一个栈底设在c1处,另一个栈底设在cMaxSize处,分别编写s1和s2的进栈push(i,x)、退栈pop(i)和设置栈空setnull(i)的函数,其中i=1,2。注意:仅当整个空间c1.MaxSize占满时才产生上溢。答：（1）初始化操作【共享栈的初始化】int initDupStack(dupsqstack *s)/*创建两个共享邻接空间的空栈由指针S指出*/ if(s=(dupsqstack*)malloc(sizeof(dupsqstack)=NULL) return FALSE; s->lefttop= -1; s->righttop=MAXNUM; return TRUE;（2）入栈操作【共享栈的入栈操作】int pushDupStack(dupsqstack *s,char status,Elemtype x)*把数据元素x压入左栈（status=L）或右栈（status=R）*/ if(s->lefttop+1= =s->righttop) return FALSE; /*栈满*/ if(status=L) s->stack+s->lefttop=x; /*左栈进栈*/ else if(status=R) s->stack-s->lefttop=x; /*右栈进栈*/ else return FALSE; /*参数错误*/return TRUE;（3）出栈操作【共享栈的出栈操作】Elemtype popDupStack(dupsqstack *s,char status)/*从左栈（status=L）或右栈（status=R）退出栈顶4. 用不带头结点的单链表存储链栈,设计初始栈、判断栈是否为空、进栈和出栈等相应的算法。答：（1）入栈操作【单个链栈的入栈操作】int pushLstack(slStacktype *top,Elemtype x)/将元素x压入链栈top中slStacktype *p;if(p=(slStacktype*)malloc(sizeof(slStacktype)=NULL) return FALSE; /申请一个结点p->data=x; p->next=top; top=p; return TRUE;（2）出栈操作【单个链栈的出栈操作】Elemtype popLstack(slStacktype *top)/从链栈top中删除栈顶元素slStacktype *p;Elemtype x;if (top= =NULL) return NULL; /空栈p=top; top=top->next; x=p->data;free(p);return x;问答题：1. 试述栈的基本性质?解答：由栈的定义可知，这种结构的基本性质综述如下： (1)集合性。栈是由若干个元素集合而成，当没有元素的空集合称为空栈； (2)线性结构。除栈底元素和栈顶元素外，栈中任一元素均有唯一的前驱元素和后继元素； (3)受限制的运算。只允许在栈顶实施压入或弹出操作，且栈顶位置由栈指针所指示；(4)数学性质。当多个编号元素依某种顺序压入，且可任意时刻弹出时，所获得的编号元素排列的数目，恰好满足卡塔南数列的计算，即： n n 2n /(n1) 其中，n为编号元素的个数，Cn 是可能的排列数目。2. 何谓队列的上溢现象?解决它有哪些方法，且分别简述其工作原理。解答：在队列的顺序存储结构中，设队头指针为front,队尾指针为rear,队的容量（存储空间的大小）为m。当有元素要加入队列时，若rearm（初始时reat0），则发生队列的上溢现象，该元素不能加入队列。 这里要特别注意的是：队列的假溢出现象，队列中还有空余的空间，但元素不能进队 列。造成这种现象的原因是由于队列的操作方式所致。 解决队列的上溢有以下几种方法： (1)建立一个足够大的存储空间，但这样做往往会造成空间使用的效率低。 (2)当出现假溢出时，可采用以下几种方法： 采用平移元素的方法。每当队列中加入一个元素时，队列中已有的元素向队头 移动一个位置（当然要有空余的空间可移）； 每当删去一个队头元素时，则依次序移队中的元素，始终使front指针指向队列 中的第一个位置； 采用循环队列方式。把队头队尾看成是一个首尾相邻的循环队列，虽然物理上假定用一个循环单链表表示队列（称此为循环链队），该队列只设一个队尾指针， 不设队首指针，试编写下列算法： (1)向循环链队插入一个元素为x的结点。 (2)从循环链队中删除一个结点（假定不需要保留被删除结点的值和不需要回收结点）。3. 假定用一个循环单链表表示队列（称此为循环链队），该队列只设一个队尾指针， 不设队首指针，试编写下列算法： (1)向循环链队插入一个元素为x的结点。 (2)从循环链队中删除一个结点（假定不需要保留被删除结点的值和不需要回收结点）解答： (1) 解答:status insert(Rear,x) / 假定Rear为循环链队的队尾指针，x为待插入的元素 (1) malloc(p); p->datax; / 建立值为x的新结点p (2) if( Rearnil) Rearp; Rear->nextp; else p->nextRear->next; Rear->nextp; Rearp; / 若条件成立则建立循环链队的第一个结点，否则在队尾插入p结点 (2) 解答:status delete(Rear) if( Rearnil ) error('underflow'); if (Rear->next= =Rear) Rearnil; else Rear->nextRear->next->next; /Rear.next 所指向的结点为循环链队的队首结点 4.为什么说栈是一种后进先出表?解答：栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。 栈也称为后进先出表（LIFO-Last IN First Out表）。5对于一个栈,给出输入项A,B,C。如果输入项序列由A,B,C所组成,试给出全部可能的输出序列。解答：A，6.有字符串次序为3*y-a/y2,试利用栈给出将次序改变为3y-*ay2/-的操作步骤。(可用X代表扫描该字符串函数中顺序取一字符进栈的操作,用S代表从栈中取出一个字符加到新字符串尾的出栈的操作)。例如:ABC变为BCA,则操作步骤为XXSXX。5. 解答：X:进栈 S:出栈XSXXXSSSXXSXXSXXSSSS7.跟踪以下代码,显示每次调用后队列中的内容。InitQueue(qu);EnQueue(qu,'A');EnQueue(qu,'B);EnQueue(qu,'C);EnQueue(qu,x;EnQueue(qu,x;EnQueue(qu,'D);EnQueue(qu,'E);EnQueue(qu,'F);EnQueue(qu,x)EnQueue(qu,'G);EnQueue(qu,X)EnQueue(qu,X)EnQueue(qu,X)解答：InitQueue(qu); 队列为空EnQueue(qu,'A'); 队列为AEnQueue(qu,'B); 队列为ABEnQueue(qu,'C); 队列为ABCEnQueue(qu,x; 队列为ABCxEnQueue(qu,x; 队列为ABCxxEnQueue(qu,'D); 队列为ABCxxDEnQueue(qu,'E); 队列为ABCxxDEEnQueue(qu,'F); 队列为ABCxxDEFEnQueue(qu,x) 队列为ABCxxDEFxEnQueue(qu,'G); 队列为ABCxxDEFxGEnQueue(qu,X) 队列为ABCxxDEFxGXEnQueue(qu,X) 队列为ABCxxDEFxGXXEnQueue(qu,X) 队列为ABCxxDEFxGXXX8. 假设Q0.10是一个线性队列,初始状态为front=rear=0,画出做完下列操作后队列的头尾指针的状态变化情况,若不能入队,请指出其元素,并说明理由。d,e,b,g,h入队d,e出队i,j,k,l,m入队n,o,p入队解答：d,e,b,g,h入队debgh F rd,e出队bgh F ri,j,k,l,m入队bghijklm F rn,o,p入队bghijklmnop F r所有元素均正好能入队，共有11个存储空间，恰好11个元素。9. 假设CQ0.10是一个环形队列,初始状态为front=rear=0,画出做完下列操作后队列的头尾指针的状态变化情况,若不能入队,请指出其元素,并说明理由。d,e,b,g,h入队d,e出队i,j,k,l,m入队b出队n,o,p入队解答： 图略 。 p不能入队，共有11个地址，p为第12个元素，故不能入队。10. 有5个元素,其进栈次序为A、B、C、D、E,在各种可能的出栈次序中,以元素C、D最先出栈(即C第一个且D第一个出栈)的次序有哪几个?答：三个：CDEBA，CDBEA，CDBAE 11. 设输入元素为1、2、3、P和A,入栈次序为123PA,元素经过栈后到达输出序列,当所有元素均到达输出序列后,有哪些序列可以作为高级语言的变量名?答：一般说，高级语言的变量名是以字母开头的字母数字序列。故本题答案是:AP321,PA321,P3A21,P32A1,P321A。12. 简要叙述栈和队列的特点.答：栈和队列都是插入和删除操作的位置受限制的线性表。栈是限定仅在表尾进行插入和删除的线性表，是后进先出的线性表，而队列是限定在表的一端进行插入，在另一端进行删除的线性表，是先进先出的线性表。-第 10 页单选题：