数据结构习题 (2).doc

第六章 树和二叉树1、 如图所式的树，采用先序，后序和中序周游，问得出怎样的结点序列 efghacbd先序：a b e c f g h d中序：e b a f c g h d 后序：e b f g h c d a 2、已知一棵度为m的树中有n1的度为1的的结点，n2个度为2的结点， ,nm个度为m的结点，问该树中有多少个叶子结点。解：1+abcedfgh3将题1所示的树转换为对应的二叉树是什么样子的？画出来4、 请写出对二叉树按照层次遍历的算法。解：void PreOrder_Nonrecursive(Bitree *T)/先序遍历二叉树的非递归算法InitStack(S);Push(S,T); /根指针进栈while(!StackEmpty(S)while(GetTop(S,p)&p) visit(p-data);push(S,p-lchild); /向左走到尽头pop(S,p);if(!StackEmpty(S) pop(S,p); push(S,p-rchild); /向右一步/while/PreOrder_Nonrecursive5、已知某二叉树的先序遍历序列为：A，B，D，E，G，C，F，H，I，J，中序遍历序列为D，B，G，E，A，H，F，K，I, J，C，试给出该二叉树的后序遍历序列ABCDEFGHIJ后序遍历序列：D G E B H J I F C A494722961772772138544318110025196、 对于给定的一组权值W=1，4，9，25，3，49，4，81，100构造最小带权外部路径长度的扩充二叉树。并求出它的带权外部路径长度。WPL=1第三章 栈和队列1 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针) ，试编写相应的置空队、判队空 、入队和出队等算法。/先定义链队结构:typedef struct QNodeQElemType data;struct QNode *next;Qnode,*QueuePtr; /以上是结点类型的定义typedef structQueuePtr rear;LinkQueue;/只设一个指向队尾元素的指针STATUS InitQueue( LinkQueue *Q)/初始化队列Q.rear=(QueuePtr) malloc(sizeof(QNode);if(!Q.rear) exit (OVERFLOW);Q.rear-next=Q.rear;/构造循环队列return OK;STATUS ClearQueue(LinkQueue *Q)/清空队列QueuePtr temp;if(Empty(Q) return OK;while(!Empty(Q)temp=Q.rear-next-next;Q.rear-next-next=temp-next;free(temp);return OK;int EmptyQueue( LinkQueue *Q)/判队空/当头结点的next指针指向自己时为空队return Q.rear-next= =Q.rear;STATUS EnQueue( LinkQueue *Q, QElemType x)/入队/也就是在尾结点处插入元素QueuePtr p=( QueuePtr) malloc (sizeof(QNode);/申请新结点if(p) exit (OVERFLOW);p-data=x; /结点赋值p-next= Q.rear-next;Q.rear-next =p; / 将新结点链入Q.rear=p;/将尾指针移至新结点QElemType DeQueue( LinkQueue *Q)/出队/把头结点之后的元素摘下QElemType x;QueuePtr p;if(EmptyQueue( Q )exit (OVERFLOW);p=Q.rear-next-next; /将要摘下的结点x=p-data;/保存结点中数据Q.rear-next-next=p-next;/摘下结点pfree(p);/释放被删结点return x;2假设以数组sequm存放循环队列的元素，同时设变量rear和quelen分别指示循环队列中队尾元素的位置和内含元素的个数。试给出判断此循环队列的队满条件，并写出相应的入队列和出队列的算法。typedef struct QElemType *base; int rear, quelen; SeQueue;循环队列满的条件为： quelen =MAXQSIZE;STATUS EnQueue(SeQueue *Q, QElemType e) /*将新元素e插到队尾*/ if Q.quelen=MAXQSIZE /*队满上溢*/ printf(“queue is full”); return NULL; else Q.rear=( Q.rear+1)%MAXQSIZE; Q .baseQ .rear=e;Q. quelen+; return OK; QElemType DeQueue(SeQueue *Q) /*删除队头元素并返回*/ int front; if (EMPTY(Q) ) /*队空下溢*/ printf(“queue is empty”); return NULL; else Q. quelen -; front= (MAXSIZE+Q.rear-Q. quelen)%MAXQSIZE; return(Q.basefront); 3 Fibonacci序列0，1，1，2，3，5，8，13，21，其中每个元素是前两个元素之和。可递归定义为Fib(n)= n n=0,1 Fib(n-2)+Fib(n-1) n=2请设计一个计算fib（n）的递