132010年计算机专业统考试题数据结构

第三章栈和队列一、基本内容1、内容提要（1）在数据结构的角度讲，栈和队列属于线性结构，其操作是线性表操作的子集，是操作受限的线性表。但从数据类型的角度看，它们是和线性表不相同的重要数据类型。（2）栈的定义和操作。栈是只准在一端进行插入和删除操作的线性表，该端称为栈的顶端。（3）栈的顺序和链式存储结构，即在这两种结构下实现栈的操作。（4）栈的应用：表达式求值，过程调用，递归过程及消除递归。（5）队列的定义和操作，队列的删除在一端（头），而插入在另一端（尾）。因此在两种存储结构中，一般需要队头和队尾两个指针。（6）队列空的条件是首尾指针相等，而循环队列满的判定，则有牺牲一个单元和设标记两种方法。一、基本内容2、栈（1）顺序栈typedefstruct{ElemType*base;ElemType*top;intstacksize;}Sqstack;栈空：s.top=s.base栈满：s.top-s.base=s.stacksize;入栈：*s.top++=e;出栈：e=*--s.top;（2）链栈：实质是不带头结点的单链表一、基本内容3、队列（1）链队：带头结点的单链表typedefstructQNode{ElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront,rear;}LinkQueue;一、基本内容队空：Q.front==Q.rear;Q.front-next=NULL;插入：Q.rear-next=p;p-next=NULL;Q.rear=p;删除：p=Q.front-next;Q.frot-next=p-next;if(Q.rear==p)Q.rear=Q.front;一、基本内容（2）顺序（循环队列）typedefstructQNode{ElemType*base;intfront,rear;}SqQueue;队空：Q.front==Q.rear;队满：(Q.front+1)%max==Q.front;入队：Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%max;出队：e=Q.base[Q.front];Q.front=(Q.front+1)%max;一、基本内容4、要点（1）栈和队列操作在两种存储结构下的实现，注意因栈在一端操作，故通常链栈不设头结点。（2）中缀表达式转换为前缀、后缀表达式，表达式求值。（3）用递归解决问题：问题的定义是递归的，数据结构是递归的，问题的求解是递归的。（4）对只有一个元素的链队列删除元素时的处理，特别是仅设尾指针的循环队列的各种操作的实现。（5）循环队列的队空队满条件，以及入队出队操作。（6）栈和队列的应用。二、试题分析1、现假设要计算表达式：A-B*C/D+E/F。写出栈S1和S2的变化过程。分析：计算算术表达式的值时，可用两个栈作辅助工具。对于给出的一个表达式，从左向右扫描它的字符，并将操作数放入栈S1中，运算符放入栈S2中，但每次扫描到运算符时，要把它同S2的栈顶运算符进行优先级比较，当扫描到的运算符的优先级不高于栈顶运算符的优先级时，取出栈S1的栈顶和次栈顶的两个元素，以及栈S2的栈顶运算符进行运算将结果放入栈S1中（得到的结果依次用T1、T2等表示）。为方便比较，假设栈S2的初始栈顶为#（#运算符的优先级低于加、减、乘、除中任何一种运算）。二、试题分析2、用栈实现将中缀表达式8-(3+5)*(5-6/2)转换成后缀表达式，画出栈的变化过程图。分析：设操作符栈s，初始为空栈后，压入优先级最低的操作符‘#’。对中缀表达式从左向右扫描，遇操作数，直接写入exp2；若是操作符（记为w），分如下情况处理，直至表达式exp1扫描完毕。（1）w为一般操作符（’+’，’-‘，’*’，’/’等），要与栈顶操作符比较优先级，若w优先级高于栈顶操作符，则入栈；否则，栈顶运算符退栈到exp2，w再与新栈顶操作符作上述比较处理，直至w入栈。（2）w为左括号’（’，w入栈。（3）w为右括号’）’，操作符栈退栈并进入exp2，直到碰到左括号为止，左括号退栈（不能进入exp2），右括号也丢掉，达到exp2中消除括号的目的。（4）w为‘#’，表示中缀表达式exp1结束，操作符栈退栈到exp2，直至碰到‘#’，退栈，整个操作结束。二、试题分析3、利用两个栈sl,s2模拟一个队列时，如何用栈的运算实现队列的插入，删除以及判队空运算。请简述这些运算的算法思想。分析：栈的特点是后进先出，队列的特点是先进先出。初始时设栈s1和栈s2均为空。（1）用栈s1和s2模拟一个队列的输入：设s1和s2容量相等。分以下三种情况讨论：若s1未满，则元素入s1栈；若s1满，s2空，则将s1全部元素退栈，再压栈入s2，之后元素入s1栈；若s1满，s2不空（已有出队列元素），则不能入队。（2）用栈s1和s2模拟队列出队（删除）：若栈s2不空，退栈，即是队列的出队；若s2为空且s1不空，则将s1栈中全部元素退栈，并依次压入s2中，s2栈顶元素退栈，这就是相当于队列的出队。若栈s1为空并且s2也为空，队列空，不能出队。（3）判队空若栈s1为空并且s2也为空，才是队列空。讨论：s1和s2容量之和是队列的最大容量。其操作是，s1栈满后，全部退栈并压栈入s2（设s1和s2容量相等）。再入栈s1直至s1满。这相当队列元素“入队”完毕。出队时，s2退栈完毕后，s1栈中元素依次退栈到s2，s2退栈完毕，相当于队列中全部元素出队。在栈s2不空情况下，若要求入队操作，只要s1不满，就可压入s1中。若s1满和s2不空状态下要求队列的入队时，按出错处理。(1)intenqueue(stacks1,elemtpx)//将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);}(2)voiddequeue(stacks2,s1)//将s2栈顶元素退栈，实现队列元素的出队。{if(!Sempty(s2))//栈s2不空，则直接出队。{POP(s2,x);printf(“出队元素为”,x);}elseif(Sempty(s1)){printf(“队列空”);exit(0);}//若输入栈也为空，则判定队空。else{while(!Sempty(s1)){POP(s1,x);PUSH(s2,x);}POP(s2,x);printf(“出队元素”，x);}}(3)intqueue_empty()//本算法判用栈s1和s2模拟的队列是否为空。{if(Sempty(s1)&&Sempty(s2))return(1);elsereturn(0);}二、试题分析4判别表达式中三种括号是否匹配StatusAllBrackets_Test(char*str)//{InitStack(s);for(p=str;*p;p++){if(*p=='('||*p=='['||*p=='{')push(s,*p);elseif(*p==')'||*p==']'||*p=='}'){if(StackEmpty(s))returnERROR;pop(s,c);if(*p==')'&&c!='(')returnERROR;if(*p==']'&&c!='[')returnERROR;if(*p=='}'&&c!='{')returnERROR;}}if(!StackEmpty(s))returnERROR;returnOK;}二、试题分析5、在一个循环链队列中只有尾指针(rear)，写出队列的入队和出队操作。6、在循环队列中只设尾指针和队列元素个数length，求入队和出队操作。