数据结构习题课

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数据结构习题课,作者：王丽萍,1,第2章 线性表,在线性表中最常用的操作是存取第i个元素及其前驱的值，采用,顺序表,存储方式最省时间。,某线性表中最常用的操作是存取序号为i的元素和在最后进行插入和删除运算，则采用,顺序表,存储方式时间性能最好。,在链表中最常用的操作是删除表中最后一个结点和在最后一个结点之后插入元素，则采用,_D_,最节省时间。,A.,带头指针的单向循环链表 B.双向链表,C.带尾指针的单向循环链表,D.带头指针的双向循环链表,2,在线性表中最常用的操作是存取第i个元素及其前驱的值，可采用,_ABCD_,存储方式。,A.顺序表 B.单向链表,C.双向循环链表 D.单向循环链表,假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表的（即A表和B表的）结点空间存储表C。,3,void merge(Linklist A,Linklist B,Linklist C),Linklist pa,pb,p;,pa=A-next;,pb=B-next;,C=A;,C-next=NULL;,free(B);,4,while(pa&pb),if(pa-data data),p=pa;,pa=pa-next;,p-next=C-next;,C-next=p;,5,else,p=pb;,pb=pb-next;,p-next=C-next;,C-next=p;,6,if(!pa),while(pb),p=pb;,pb=pb-next;,p-next=C-next;,C-next=p;,7,else if(!pb),while(pa),p=pa;,pa=pa-next;,p-next=C-next;,C-next=p;,8,建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的data域存放一个二进制位，并在此链表上实现对二进制数加1的运算。(假设链表L为从低位到高位）,void AddOne(Linklist L),Linklist p=L-next;,while(p-next&p-data=1),p-data=0;,p=p-next;,9,if(p-next),p-data=1;,else,if(p-data=0),p-data=1;,else,p-data=0;,Linklist q=(Linklist)malloc(sizeof(Node);,10,q-data=1;,q-next=NULL;,p-next=q;,return;,11,第三章 栈和队列,设队列中有A、B、C、D、E这5个元素，其中队首元素为A。如果对这个队列重复执行下列4操作：,（1）输出队首元素；,（2）把队首元素值插入到队尾；,（3）删除队首元素；,（4）再次删除队首元素。,直到队列成为空队列为止，是否可能得到输出队列：,A、C、E、C、C,12,试利用栈编写计算下列递归函数的非递归形式的算法。,0,m=0,n,0,g(m,n)=,g(m-1,2n)+n,m 0,n,0,(程序）,13,第6章 树和二叉树,画出与下列已知序列对应的树T：,树的先根次序访问序列为CFKDAIEBCHJ,树的后根次序访问序列为DIAEKFCJHBG,（P177)树与二叉树的转换关系：树中的任意一个结点都对应于二叉树中的一个结点。树中某结点的第一个孩子在二叉树中是相应结点的左孩子，树中某结点的右兄弟结点在二叉树中是相应结点的右孩子。,树的后根遍历序列,=,二叉树的中序遍历序列,14,根据先序序列和中序序列确定二叉树,将二叉树转化为树：,二叉树中每个结点都对应于树中每个结点；,二叉树中某结点的左孩子为树中该结点的第一个孩子；,二叉树中某节点的右孩子为树中该结点的右兄弟。,15,假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为：,0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10,构造哈夫曼树的算法步骤：（P184）,找最小树：在森林F中选择两棵结点权值最小的二叉树，作为一棵新二叉树的左右子树，标记新二叉树的根结点权值为其左、右子树的根结点权值之和；,删除与加入：从F中删除被选中的那两棵二叉树，同时把新构成的二叉树加入到森林F中。,16,(1)0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10,0.02,0.03,0.05,17,（2）0.07,0.19,0.06,0.32,0.21,0.10，,0.05,0.02,0.03,0.05,0.06,0.11,18,（3）,0.07,0.19,0.32,0.21,0.10,，0.11,0.02,0.03,0.05,0.06,0.11,0.07,0.17,0.10,19,（4）0.19,0.32,0.21,0.11,，,0.17,0.02,0.03,0.05,0.06,0.11,0.07,0.17,0.10,0.28,20,（5）,0.19,0.32,0.21,0.28,0.02,0.03,0.05,0.06,0.11,0.07,0.17,0.10,0.28,0.19,0.40,0.21,21,（6）,0.32,，,0.28,，0.40,0.02,0.03,0.05,0.06,0.11,0.07,0.17,0.10,0.28,0.19,0.40,0.21,0.32,0.60,22,（7）,0.40，0.60,0.02,0.03,0.05,0.06,0.11,0.07,0.17,0.10,0.28,0.19,0.40,0.21,0.32,0.60,0.10,0,1,0,1,0,1,0,1,0,1,0,1,0,1,23,已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。,int leaf(Bitree T),if(!T),return 0;,if(!T-Lchild&!T-Rchild),return 1;,return(leaf(T-Lchild)+leaf(T-Rchild);,24,第7章 图,已知如图（P245,图7.30)所示的AOE-网，试求：,25,（1）,每个事件的最早发生时间和最晚发生时间；,事件vi的最早发生时间ve(i)：从源点到顶点vi的最长路径的长度。,ve(0)=0;,ve(i)=Maxve(k)+dut(),事件vi的最晚发生事件vl(i):在保证汇点按其最早发生时间发生这一前提下，求事件vi的最晚发生时间。,vl(n-1)=ve(n-1),vl(i)=Minvl(k)-dut(),26,（1）,每个事件的最早发生时间；,ve(0)=0,ve(1)=maxve(0)+dut()=5,ve(2)=maxve(0)+dut()=6 ve(3)=maxve(1)+dut(),ve(2)+dut()=12 ve(4)=maxve(3)+dut(),ve(2)+dut()=15,27,（1）,每个事件的最晚发生时间；,vl(9)=ve(9)=23,vl(8)=min(vl(9)-dut()=21,vl(7)=min(vl(8)-dut()=19,vl(6)=min(vl(9)-dut()=19,vl(5)=min(vl(8)-dut()=16,vl(4)=min(vl(5)-dut(),vl(7)-dut()=15,28,（2）每个活动的最早开始时间和最晚开始时间；,活动ai的最早开始时间e(i):如果活动ai对应的弧为,则e(i)等于从源点到顶点j的最长路径的长度，即：e(i)=ve(j);,活动ai的最晚开始时间l(i):如果活动ai对应的弧为,其持续时间为dut(),则有：l(i)=vl(k)-dut()。,29,每个活动的最早开始时间,e()=ve(0)=0,e()=ve(0)=0,e()=ve(1)=5,e()=ve(2)=6,e()=ve(2)=6,e()=ve(3)=12,30,每个活动的最晚开始时间,l()=vl(1)-dut()=4,l()=vl(2)-dut()=0,l()=vl(3)-dut()=9,l()=vl(3)-dut()=6,31,给出关键路径。,关键路径：从源点到汇点的最长路径的长度为完成整个工程任务所需的时间，该路径叫做关键路径。关键路径上的活动叫做关键活动。,关键活动：e(i)=l(i)的活动ai即为关键活动。,32,已知如图（P245,图7.31）所示的有向网，试利用Dijkstra算法求顶点1到其余顶点的最短路径，并给出算法执行过程中各步的状态。,33,Dijkstra算法,对于图G=（V，E），将图中的顶点分成两组：,第一组S：已求出的最短路径的终点集合,第二组V-S：尚未求出最短路径的顶点集合,算法将按最短路径长度的递增顺序逐个将第二组的顶点加入到第一组中，直到所有顶点都被加入到第一组顶点集S为止。,34,35,（1）用Prime算法从顶点9开始，手工构造最小生成树。,36,Prime算法：,假设N=(V,E)是连通网，TE为最小生成树中边的集合。,初始U=,(V),TE=,;,在所有u,U,vV-U的边中选一条代价最小的边（，）并入集合TE，同时将 并入U；,重复（2），直到U=V为止。,此时，TE中必含有n-1条边，则T=(V,TE)为N的最小生成树。,37,(1)(2),(3)(4),38,(5),(6),39,(7),(8),40,(9),41,（2）用Kruscal算法手工构造最小生成树。,假设N=(V,E)是连通网，将N中的边按权值从小到大的顺序排列。,将n个顶点看成n个集合；,按权值由小到大的顺序选择边，所选边应满足两个顶点不在同一个顶点集合内，将该边放到生成树边的集合中。同时将该边的两个顶点所在的顶点集合合并；,重复直到所有的顶点都在同一个顶点集合内。,42,(1),(2),43,(3),(4),44,(5),(6),45,(7),(8),46,(9),47,配色方案修改：,48,49,