(qu->rear+1)%MaxSize==qu->front|qu->rear-qu->front-1==MaxSize|qu->front==qu->rear|qu->front==qu->rear+1 A
25、与队头指针的队尾指针的值有关|只与队尾指针的值有关,与队头指针的值无关|只与数组大小有关,与队首指针和队尾指针的值无关|与曾经进行过多少次插入操作有关 A
26、(rear-front+MaxSize)%MaxSize|rear-front+1|(rear-front-1)%MaxSize|(rear-front)%MaxSize A 27、1和5|2和4|4和2|5和1 B
28、只带队头指针的非循环双链表|只带队头指针的循环双链表|只带队尾指针的循环双链表|只带队尾指针的循环单链表 A
29、f->next=s;f=s;|r->next=s;r=s;|s->next=r;r=s;|s->next=f;f=s; B 30、r=f->next;|r=r->next;|f=f->next;|f=r->next; C 31、链头|链尾|链中|任意 A 32、A*B+C/D-E+F|AB*C+D/E-F+|ABC+*DE-+/|ABCDEF*+/-+ C 33、
push,pop,push,pop,push,pop|push,push,push,pop,pop,pop|push,push,pop,pop,push,pop|push,pop,push,push,pop,pop B
34、st.top==-1|st.top!=-1|st.top!=MaxSize|st.top==MaxSize A 35、st.top!=-1|st.top==-1|st.top!=MaxSize-1|st.top==MaxSize-1 D 36、abcd*+-|abc+*d-|abc*+d-|-+*abcd B
37、2 2 3 * + 2 * 6 3 * 2 / +|2 2 * 3 + 2 * 6 3 * 2 / +|2 2 3 * 2 * 6 3 * + 2 / +|2 2 3 * + 2 6 3 * 2 / + * A 38、插入操作更方便|通常不会出现栈满的情况|不会出现栈空的情况|删除操作更加方便 B
39、只有表头指针没有表尾指针的循环双链表|只有表尾指针没有表头指针的循环双链表|只有表尾指针没有表头指针的循环单链表|只有表头指针没有表尾指针的循环单链表 D
40、必须判别栈是否满|判别链栈元素的类型|必须差别链栈是否空|对链栈不作任何差别 C 41、1st->next=s;|s->next=1st->next;1st->next=s;|s->next=1st;1st=s;|s->next=1st;1st=1st->next; C 42、x=1st;1st=1st->next;|x=1st->data;|1st=1st->next;x=1st->data;|x=1st->data;1st=1st->next; D 43、edcba|decba|dceab|abcde C 44、n|n/2|(n+1)/2|(n-1)/2 C 45、O(1)|O(n)|O(n*n)|O(lbn) B 46、O(1)|O(lbn)|O(n)|O(n*n) A 47、O(m)|O(n)|O(n+t)|O(n*t) D
数据结构复习题：栈和队列 判断题
1、栈底元素是不能删除的元素。 2、顺序栈中元素值的大小是有序的。
3、在n个元素进栈后,它们的出栈顺序和进栈顺序一定正好相反。 4、栈顶元素和栈底元素有可能是同一个元素。
5、若用S[1]-S[m]表示顺序栈的存储空间,则对栈的进栈、出栈操作最多只能进行m次。 6、空栈没有栈顶指针。
数据结构复习题答案：栈和队列 判断题 1、False 2、False
- 36 -
3、True 4、True 5、False 6、False
数据结构复习题：栈和队列 算法分析题
1、设计一个算法,利用栈的基本运算将指定栈中的内容进行逆转。 2、设计一个算法,利用栈的基本运算返回指定栈中的栈底元素。
3、有两个栈s1和s2共享存储空间c[1..MaxSize],其中一个栈底设在c[1]处,另一个栈底设在c[MaxSize]处,分别编写s1和s2的进栈push(i,x)、退栈pop(i)和设置栈空setnull(i)的函数,其中i=1,2。注意:仅当整个空间c[1..MaxSize]占满时才产生上溢。
6、用不带头结点的单链表存储链栈,设计初始栈、判断栈是否为空、进栈和出栈等相应的算法。
数据结构复习题答案：栈和队列 算法分析题
1、status Nizhuan(sqstacks, int a, int b, int t) {
If(s.top==s.base) error(‘no data’);
for(i=0;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、（1）初始化操作 【共享栈的初始化】 int initDupStack(dupsqstack *s) {/*创建两个共享邻接空间的空栈由指针S指出*/ if((s=(dupsqstack*)malloc(sizeof(dupsqstack)))==NULL) - 37 - 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’）退出栈顶 6、（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; //空栈 - 38 - p=top; top=top->next; x=p->data; free(p); return x; } 数据结构复习题：栈和队列 填空题 1、在具有n个单元、顺序存储的循环队列中，队满时共有______个元素。 2、栈和队列的区别仅在于________。 3、通常元素进栈的操作是________。 4、通常元素退栈的操作是________。 5、一个栈的输入序列是12345,则栈的输出序列432512是__________。 6、一个栈的输入序列是12345,则栈的输出序列12345是________。 7、设有一个顺序栈S,元素s1,s2,s3,s4,s5,s6依次进栈,如果6个元素的出栈顺序为s2,s3,s4,s6,s5,s1,则顺序栈的容量至少应为________。 8、设栈采用顺序存储结构,若己知i-1个元素进栈,则将第i个元素进栈时,进栈算法的时间复杂度为________。 9、若用不带头结点的单链表来表示链栈S,则创建一个空栈所要执行的操作是________。 10、从环形队列中插入一个元素时,通常的操作是________。 11、在具有n个单元的环形队列(共有MaxSize个单元)中,队满时共有________个元素。 12、在链表qu中,判定只有一个结点的条件是________。 13、设栈S和队列Q的初始状态为空,元素a1,a2,a3,a4,a5,a6,a7和a8依次通过栈S,一个元素出栈后立即进入队列Q,若8个元素出队列的顺序是a3,a6,a7,a5,a8,a4,a2,a1,则栈S的容量至少应该是多少(即至少应该容纳多少个元素)? 14、设有算术表达式x+a*(y-b)-c/d,该表达式的前缀表达为________。后缀表示为______。 15、栈是一种具有______特性的线性表。 16、顺序栈和链栈的区别仅在于______的不同。 17、如果栈的最大长度难以估计,则最好使用______。 18、一个栈的输入序列是12345,则栈的输出序列12345是______。 19、设栈采用顺序存储结构,若己知i-1个元素进栈,则将第i个元素进栈时,进栈算法的时间复杂度为______。 20、表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是______。 21、若用不带头结点的单链表来表示链栈1st,则创建一个空栈所要执行的操作是______。 22、对于链栈1st,进栈操作在______端进行,出栈操作在_____端进行。 23、将递归算法转换为非递归算法时,通常使用______这种数据结构。 24、有如下递归算法: void print (int w) { int i; if (w!=0) { print(w-1); - 39 - for(i=1;i<=w;i++) printf(\ printf(\ } } 调用语句printf(4)的结果是______。 25、有如下递归过程: void reverse(int m) { printf(\ if (n/10 !=0) reverse(n/10); } 调用语句reverse(582)的结果是______。 26、求顺序存储的集合的长度的时间复杂度为____________。 27、求链接存储的集合的长度的时间复杂度为____________。 28、设集合S的长度为n，则判断x是否属于集合Ｓ的时间复杂度为____________ 31、在稀疏矩阵的顺序存储中，利用一个数组来存储非零元素，该数组的长度应____________对应三元组线性表的长度。 数据结构复习题答案：栈和队列 填空题 1、n-1 2、删除运算的不同 3、先移动栈顶指针，后存入元素 4、先取出元素，后移动栈顶指针 5、不可能的 6、可能的 7、3 8、O(1) 9、S=NULL 10、先存放元素,后移动队尾指针 11、MaxSize-1 12、qu->front==qu->rear&&qu->front!=NULL 13、5 14、-+x*a-yb/cd|xayb-*+cd/- 15、后进先出 16、存储结构 17、链栈 18、可能的 19、O(1) 20、23 12 3 * 2 - 4 / 34 5 * 7 / + + 108 9 / + 21、1st=NULL 22、链栈头|链栈头 - 40 -