数据结构课堂练习题--刘楚雄--exercise

习题课线性表：1.描述以下概念的区别：头指针、头结点、首结点。2.顺序表中逻辑上相邻的元素物理位置相邻，单链表中逻辑上相邻的元素物理位置相邻。3.已知P为单链表中的非首尾结点，在P结点后插入S结点的语句为：。s-next=p-next;p-next=s;类型定义：顺序表：#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;单链表typedefstructLnode{ElemTypedata;StructLnode*next;}Lnode,*LinkList;4.设顺序表va中的数据元素递增有序，试写一算法，将X插入到顺序表的适当位置上，以保持该表的有序性。StatusSqInsert(SqList&va,ElemTypex){//线性表va的元素依次和数据元素x比较，//找到第一个比它大的元素后，之后所有//数据后移，X元素放入。L=va;if(L.length=L.listsize){newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize=L.listsize+LISTINCREMENT;}i=0;while(L.elem[i]x&&iL.length)i++;if(i==L.length)L.elem[i]=x;//插在最后else{//插在中间for(j=L.length;j=i;j--)L.elem[j+1]=L.elem[j];L.elem[i]=x;}L.length++;returnOK;}//SqInsert5.已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起（即令其中一个表的首元结点连在另一个表的最后一个结点后），假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。mnStatusLinkListJoin(LinkListha,LinkLishb,LinkList&hc){//将ha,hb链表中长的一条链在短的一条后//面，并放入hc中ifmn{hc=hb;p=hb;q=ha-next;}else{hc=ha;p=ha;q=hb-next;}while(!p-next)p=p-next;p-next=q;returnok;}算法时间复杂度分析：时间：min(m,n),O(n)阶8.试写一算法，对单链表实现就地逆置StatusLinkConvert(LinkList&h){//假设有头结点，h为指向头结点的指针,//只需将头结点后结点依次加入新链，//加入总是放在新链的首元素位置上p=h-next;q=p-next;while(p){p-next=h-next;h-next=p;p=q;q=q-next;returnOK;}12312pq9.假设以两个元素递增有序排列的线性表A和B分别表示两个集合（即同一个表中元素各不相同），现要求其并集C，并保持其元素递增有序，要求使用单链表。138235qptsStatusassemjoin(LinkListha,LinkListhb,LinkList&hc){//集合以ha为基础，将hb中不同的元素//加入，并保持递增有序hc=ha;p=ha-next;q=hc;t=hb-next;s=t-next;while(p&&t){switch{case(t-data==p-data){free(t);t=s;s=s-next;q=p;p=p-next;break;}case(t-datap-data){q=p;p=p-next;break;}case(t-datap-data)//插入{t-next=p;q-next=t;q=t;t=s;s=s-next;break;}}//switch}//whileif(!p)q-next=t;returnOK;}//assemjoinhb集合和ha集合总比较次数n次，O(n)栈和队列类型定义：顺序栈#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack顺序循环队列：#defineMAXQSIZE100;typedefstruct{QElemType*base;intfront;intrear;}SqQueue;1.试写一个算法，识别依次读入的一个以@为结束符的字符序列是否形如‘序列1&序列2‘模式的字符序列。其中序列1和序列2中都不含字符’&‘,且序列2是序列1的逆序列。如‘a+b&b+a’intsymmetry(){//使用栈，对读入的字符在&之前的都//压栈，之后弹栈并和读入数比较，直//到栈空并且读入数为@是对称，否则//为不对称。InitStack(s);scanf(ch);while(ch“&”){push(s,ch);scanf(ch);}scanf(ch);while(ch“@”&&!empey(s)){pop(s,x);if(ch==x)scanf(ch);elsereturn0;}//whileif(ch==“@”&&empty(s))return1;elsereturn0;}//symmetry2.在顺序存储结构上实现输出受限的双端循环队列的入列和出列（只允许队头出列）算法。设每个元素表示一个待处理的作业，元素值表示作业的预算时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间，则插入在队头，否则插入在队尾。StatusEnQueue(SqQueue&Q,QElemTypee){//插入受限，小于平均时间插入队头，否则//插入队尾if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;//队列满t=Q.base[Q.front]+Q.base[(Q.rear-1+MAXQSIZE)%MAXQSIZE]/2if(et){if(Q.front==0)Q.front=MAXQSIZE-1;elseQ.front=Q.front–1;Q.base[Q.front]=e;}else{Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;}returnOK;}//EnQueueStatusDeQueue(SqQueue&Q,QElemType&e){if(Q.front==Q.rear)returnERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXSIZE;returnOK;}树和二叉树二叉树：每个结点最多不超过2子的有向树性质：1.在二叉树的第i层上至多有2i-1个结点。2.深度为k的二叉树至多有2k-1个结点。4.n个结点的完全二叉树的深度为log2n+1。顺序存储结构#defineMAX_TREE_SIZE100typedefTElemTypeSqBiTree[MAX_TREE_SIZE];SqBiTreebt;链式存储结构TypedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;1.一个度为2的树与一棵二叉树有何区别？答：二叉树的度小于等于2，二叉树的子树有左右之分，而度为2的树的子树不一定是有序的。判断以下是否二叉树2.一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各是多少？答：最大n,最小logkn+13.证明：一个满k叉树上的叶子结点数n0和非叶子结点数n1之间满足以下关系：n0=（k-1）n1+1证明：设树结点为n,则n=n0+n1因是满k叉树,每个非叶子结点引出k个分支，故有k*n1个分支。除根外，每个分支引出一个结点，则树共有k*n1+1个结点。所以n0+n1=k*n1+1n0=(k-1)*n1+14.找出满足下列条件的二叉树1）先序和中序遍历，得到的结点访问顺序一样。2）后序和中序遍历，得到的结点访问顺序一样。3）先序和后序遍历，得到的结点访问顺序一样。答：1）无左子树2）无右子树3）仅一个结点5.画出下列树对应的二叉树abcabca原则：森林的先序/中序遍历，即对应二叉树的先序/中序遍历先做二叉树：cbefdg6.画出和下列已知序列对应的森林F:森林的先序次序访问序列为：ABCDEFGHIJKL森林的中序次序访问序列为：CBEFDGAJIKLHjiklhajiklbefdgchbhcdiaefgjklbhcdiagjefkl二叉树先ABCDEFGHIJKL中CBEFDGAJIKLHbhcdigjefkla森林7.画出和下列已知序列对应的树T树的先根次序访问序列为：GFKDAIEBCHJ树的后根次序访问序列为：DIAEKFCJHBG思路：树的先根为二叉树的先序树的后根为二叉树的中序求出二叉树然后化为树8.试利用栈的基本操作写出先序遍历的非递归形式的算法StatusPreOrderTraverse(BiTreeT,Status(*visit)(TElemTypee)){//采用非递归方法，遍历二叉树TInitStack(S);Push(S,T);while(!StackEmpty(S)){pop(S,p);if(!visit(-data))returnERROR;if(p-rchild)push(p-rchild);if(p-lchild)push(p-lchild);}//whilereturnOK;}//PreOrderTraverse考虑一下后序？9.编写递归算法，计算二叉树中叶子结点的数目。StatusPreOrderTraverse(BiTreeT,ints){//s为叶子树目，初值为0if(T){if(!T-lchild)&&(!T-rchild)s++;PreOrderTraverse(T-lchild,s);PreOrderTraverse(T-rchild,s);}//ifreturnOK;}//PreOrderTraverse10.编写按层次顺序（同一层自左至右）遍历二叉树的算法StatusLevelTraverse(BiTreeT,status(*visit)(TElemTypee){InitQueue(Q);if(T)EnQueue(Q,T);while(!QueueEmpty(Q)){DeQueue(Q,e);if(!visit(e))returnERROR;if(e-lchild)EnQueue(Q,e-lchild);if(e-rchild)EnQueue(Q,e-rchild);}returnOK;}//LevelTraverse