作业及答案ppt课件

数据结构作业及答案（C语言版）,2,目录,1、第2章线性表2、第3章栈和队列3、第6章树和森林4、第7章图5、第8章集合与查找6、第9章索引与散列,3,第2章线性表作业及答案1-1,1、已知有一个单链表L，设计一个算法，通过一趟遍历，在L中确定值最大的结点，返回指向该结点的指针。(注：遍历是指从头至尾访问单链表中的每一个结点且指访问一次),4,第2章线性表作业及答案1-2,2、设计一个算法，在非递减有序的单链表L中删除值相同的多余结点,5,第3章栈和队列作业及答案2-1,假设以数组Qm存放循环队列中的元素，同时设置一个标志tag=0和tag=1来区别当队头指针front和队尾指针rear相等时，队列的状态是“空”还是“满”。试编写与此结构相应的入队(EnQueue)和出队(DeQueue)算法。要求先写明结构，再写算法,6,第3章栈和队列作业及答案2-2,StatusEnQueue(SqQueue,7,第6章树和森林作业及答案4-1,1、编写递归算法，统计二叉树中度为2的结点个数,8,第6章树和森林作业及答案4-2,2、给定权值集合15,3,14,2,6,9,16,17，构造相应的Huffman树，并计算它的带权路径长度(要求画出Huffman树的构造过程),9,第6章树和森林作业及答案4-3,10,第6章树和森林作业及答案4-4,此树的带权路径长度WPL=229,11,第7章图作业及答案5-1,1、用数学归纳法证明有n个顶点的完全无向图有n(n-1)/2条边,【证明】(1)当n=1时，一个顶点时，边数为0，成立。(2)当n=2时，两个顶点，边数为1，成立。(3)设n=k时成立，即k个顶点的完全无向图有k(k-1)/2条边，则n=k+1时，第k+1个顶点到其他k个顶点的边数共k条，于是总边数为k(k-1)/2+k=(k+1)k/2。结论成立。,12,第7章图作业及答案5-2,2、对于如图所示的有向图，试画出从顶点出发进行深度优先搜索得到的深度优先生成树,结果不唯一,13,第8章集合与查找作业及答案6-1,将关键字DEC,FEB,NOV,OCT,JUL,SEP,AUG,APR,MAR,MAY,JUN,JAN依次插入到一棵初始为空的AVL树中，画出每插入一个关键字后的AVL树，需要平衡时标明平衡旋转的类型和结果(注：按字典顺序比较),DEC,14,第8章集合与查找作业及答案6-2,15,第8章集合与查找作业及答案6-3,16,第8章集合与查找作业及答案6-4,17,第9章索引与散列作业及答案7-1,给定关键字序列11,78,10,1,3,2,4,21，分别用顺序查找、折半查找、二叉排序树、平衡二叉树、散列表(用线性探查法和链地址法)实现查找，画出它们对应的存储结构(顺序查找的顺序表，折半查找的二叉判定树，二叉排序树、平衡二叉树以及两种散列表)，并求出每一种查找在等概率下查找成功时的ASL。其中，散列表为HT11，散列函数为H(key)=key%11,18,第9章索引与散列作业及答案7-2,可以得到顺序查找的平均查找长度为：ASL=(1+2+3+4+5+6+7+8)/8=(8+1)/2=4.5(2)先按关键字排序，折半查找的判定树如图所示，,从图可以得到折半查找的平均查找长度为：ASL=(1+2*2+3*4+4*1)/8=21/8=2.625,19,第9章索引与散列作业及答案7-3,(3)二叉排序树和平衡二叉树如图所示，,从图可以得到二叉排序树查找的平均查找长度为：ASL=(1+2*2+3*2+4*1+5*2)/8=25/8=3.125平衡二叉树的成功平均查找长度为：ASL=(1*1+2*2+3*3+4*2)/8=22/8=2.75,20,第9章索引与散列作业及答案7-4,(4)线性探查法解决冲突的散列表如图所示，,从图可以得到线性探查法的平均查找长度为ASL=(1+1+1+2+1+3+2+8)/8=19/8=2.375(5)链地址法