《数据结构习题三(个人解答整理).doc》由会员分享，可在线阅读，更多相关《数据结构习题三(个人解答整理).doc（4页珍藏版）》请在三一办公上搜索。
1、1 设有一个栈，元素进栈的次序为a, b, c。问经过栈操作后可以得到哪些输出序列？解答：abc bca cba bac acb2 循环队列的优点是什么?如何判断它的空和满?解答：循环队列的优点：可以更有效的利用存储空间，并且可以很好的解决因数组越界而产生的假溢出问题。 循环队列空与满的判断： 计数器：初始化n=0，入队操作时n+，出队操作时n-。 则n=0时队空，n0&rear=front时队满。 标志位：tag，出队时置0，入队时置1。 则tag=0&rear=front时队空，tag=1&rear=front时队满。 牺牲一个元素空间。 入队前，如果(rear+1)%M=front则队满
2、，rear=front则队空。 /扩大rear和front的定义域为0MaxSize 初值rear=0；front=MaxSize 入队前，若rear=MaxSize，则为队满。入队后，使得rear=front，则令rear=MaxSize，表示队满。 若front=MaxSize，则front=rear-1。 出队前，若front=MaxSize，则为队空。出队后，使得front=rear，则令front=MaxSize，表示队空。 若rear=MaxSize，则rear=front-1.3 设有一个静态顺序队列，向量大小为MAX，判断队列为空的条件是什么？队列满的条件是什么？解答：队首指针
3、front ，一个队尾指针rear。队列为空：front=rear。队满：rear=MaxSize-1或front=rear4 设有一个静态循环队列，向量大小为MAX，判断队列为空的条件是什么？队列满的条件是什么？解答：此题和第二题基本一样，这里我只给出最常用的一种。队首指针front ，一个队尾指针rear。循环队列为空：front=rear。循环队列满：(rear+1)%MAX=front。5 利用栈的基本操作，写一个返回栈S中结点个数的算法int StackSize(SeqStack S) ，并说明S为何不作为指针参数的算法?解答：intStackSize (SeqStack S)/计算
4、栈中结点个数int n=0;if(!EmptyStack(&S)Pop(&S);n+;return n;题目只是要求找到S栈的结点个数，并不需要改变栈的结构，因此只需要传原来的栈的值作形参然后返回结点个数即可。若传指针作参数，则可改变栈的结构，这可能会由于操作问题导致栈的改变从而带来不必要的麻烦。6 一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。试为此双向栈设计初始化InitStack(S) ，入栈Push(S,i,x)，出栈Pop(S,i,x)算法，其中i为0或1 ，用以表示栈号。解答：/双向栈的栈结构类型与单向栈略有不同#define StackSize 1
5、00 / 假定分配了100个元素的向量空间typedef char Datatype/此处#define和可通用typedef structDatatype DataStackSize;int top0; /需设两个指针int top1;DoubleStackvoid InitStack(DoubleStack *S ) /初始化双向栈S-top0 = -1;S-top1 = StackSize; /这里的top1也指出了向量空间，但由于是作为栈底，因此不会出错int EmptyStack(DoubleStack *S, int i ) /判栈空(栈号 i)return i = 0 & S-t
6、op0 = -1| i = 1 & S-top1= StackSize;int FullStack(DoubleStack *S) /判栈满return (S-top0 = S-top1-1);void Push(DoubleStack *S, int i, DataType x) /进栈(栈号i)if (FullStack( S )exit(OVERFLOW);/上溢、退出运行printf(“Stack overflow”);if ( i = 0) S-Data + S-top0= x; /栈0入栈if ( i = 1) S-Data - -S-top1= x; / 栈1入栈DataType
7、 Pop(DoubleStack *S, int i) /出栈(栈号i)if (EmptyStack ( S,i) )sexit(OEVRFLOW);/下溢退出printf(“Stack underflow”);if( i=0 ) return ( S-Data S-top0- );/返回栈顶元素，指针值减1if( i=1 )return ( S-Data S-top1+ ); /因为这个栈是以另一端为底的，所以指针值加1。7 设Q0,6是一个静态顺序队列，初始状态为front=rear=0，请画出做完下列操作后队列的头尾指针的状态变化情况，若不能入对，请指出其元素，并说明理由。a, b, c, d入队a, b, c出队i , j , k , l , m入队d, i出队n, o, p, q, r入队解答：其中l、m、n、o、p、q、r均由于队列假溢出问题无法入队8 假设Q0,5是一个循环队列，初始状态为front=rear=0，请画出做完下列操作后队列的头尾指针的状态变化情况，若不能入对，请指出其元素，并说明理由。d, e, b, g, h入队d, e出队i , j , k , l , m入队b出队n, o, p, q, r入队 解答：其中k、l、m、o、p、q、r均由于队满而无法入队。
