数据结构习题三(个人解答整理).doc

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则队满，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，判断队列为空的条件是什么？队列满的条件是什么？解答：队首指针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)/计算栈中结点个数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 100 / 假定分配了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-top0 = -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 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，请画出做完下列操作后队列的头尾