数据结构作业.ppt
教材:数据结构（C语言版）严蔚敏 吴伟民 编著 清华大学出版社计算机科学与技术学院计算机科学与技术学院第二章作业补充作业：写出按正位序建立一个单链表的算法。2.3 在什么情况下用顺序表比链表好？2.11 设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。第三章作业2.写出检验括号匹配的算法。写出检验括号匹配的算法。补充作业：补充作业：1.设将整数设将整数1、2、3、4依次进栈，但只要出栈时栈非空，则可将出栈依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下有问题：操作按任何次序夹入其中，请回答下有问题：（1）若入栈次序为）若入栈次序为push(1)，pop()，push(2），），push(3)，pop()，pop()，push(4)，pop()，则出栈的数字序列为什么？，则出栈的数字序列为什么？（2）请分析）请分析1、2、3、4的的24种排列中，哪些序列可以通过相应的种排列中，哪些序列可以通过相应的入出栈得到入出栈得到3.12 写出以下程序段的输出结果（队列中的元素类型写出以下程序段的输出结果（队列中的元素类型QElemType 为为char）。）。Void main()Queue Q;InitQueue(Q);Char x=e,y=c;EnQueue(Q,h);EnQueue(Q,r);EnQueue(Q,y);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q,a);While(!QueueEmpty(Q)DeQueue(Q,y);Printf(y);Printf(x);第四章作业4.3 设 s=I AM A STUDENT，t=GOOD，q=WORKER，求：（1）StrLength(s)，StrLength(t)（2）SubString(s,8,7)，SubString(t,2,1)（3）Index(s,A)，Index(s,t)（4）Replace(s,STUDENT,q)（5）Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)4.7 令s=aaab,t=abcabaa,u=abcaabbabcabaacbacba。试分别求出它们的next函数值和nextval函数值。第五章 作 业5.1 假设有二维数组A 68，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，计算：（1）数组A的体积（即存储量）；（2）数组A的最后一个元素a57的第一个字节的地址；（3）按行存储时，元素a14的第一个字节的地址；（4）按列存储时，元素a47的第一个字节的地址。5.10 求下列广义表操作的结果：（1）GetHead(p,h,w);（4）GetTail(a,b),(c,d);（5）GetHead(GetTail(a,b),(c,d)。5.12 按教科书5.5节中图5.8所示结点结构，画出下列广义表的存储结构图，并求它的深度。（1）(),a,(b,c),(),d),(e)（2 (a),b),(),d),(e,f)第六章 作业6.1 已知一棵树边的集合为已知一棵树边的集合为,，请画出这棵树，并回答下列问题：请画出这棵树，并回答下列问题：(1)哪个是根结点？哪个是根结点？(2)哪些是叶子结点？哪些是叶子结点？(3)哪个是结点哪个是结点G的双亲？的双亲？(4)哪些是结点哪些是结点G的祖先？的祖先？(5)哪些是结点哪些是结点G的子孙？的子孙？(6)哪些是结点哪些是结点E的子孙？的子孙？(7)哪些是结点哪些是结点E的兄弟？哪些是结点的兄弟？哪些是结点F的兄弟？的兄弟？(8)结点结点B和和N的层次号分别是什么？的层次号分别是什么？(9)树的深度是多少？树的深度是多少？(10)以结点以结点C为根的子树的深度是多少为根的子树的深度是多少？6.3 试分别画出具有试分别画出具有3个结点的树和个结点的树和3个结点个结点的二叉树的所有不同形态。的二叉树的所有不同形态。6.12 对题对题6.3所得各种形状的二叉树，分别所得各种形状的二叉树，分别写出前序、中序和后序遍历的序列。写出前序、中序和后序遍历的序列。6.15 请对如图所示二叉树进行后序线索化，请对如图所示二叉树进行后序线索化，为每个空指针建立相应的前驱或后继线索。为每个空指针建立相应的前驱或后继线索。BACFEDHG6.17 阅读下列算法，若有错，则改征之。阅读下列算法，若有错，则改征之。BiTree InSucc(BiTree q)/已知q是指向中序线索二叉树上某个结点的指针，/本函数返回指向*q的后继的指针。r=qrchild;if(!r rtag)while(!rrtag)r=rrchild;return r;/InSucc6.19 分别画出和下列树对应的各个二叉树：分别画出和下列树对应的各个二叉树：ABACAFEDCBJIHGKCBA(a)(b)(c)(d)6.21 画出和下列二叉树相应的森林：画出和下列二叉树相应的森林：ACABCBAMIFKJHGEDCBACBA(a)(b)(c)(d)(e)6.22 对于对于6.19题中给出的各树分别求出以下题中给出的各树分别求出以下遍历序列遍历序列：（1）先根序列；先根序列；（2）后根序列。）后根序列。补充作业：补充作业：设权设权W=10,5,12,7,4,2,建立一棵哈夫曼树（按左子树根结点的建立一棵哈夫曼树（按左子树根结点的权小于等于右子根的权的次序构造，画权小于等于右子根的权的次序构造，画出建树过程），并求出其带权路径长度出建树过程），并求出其带权路径长度WPL。6.27 假设一棵二叉树的先序序列为假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列和中序序列ABCDEFGHIJK。请画出该二叉树。请画出该二叉树。第七章作业7.77.7、7.97.9、7.107.10、7.117.11、7.137.13补充作业：补充作业：请根据给出的邻接表，画出对应图。请根据给出的邻接表，画出对应图。并写出从并写出从C C点开始深度和广度优先遍历序列，画出点开始深度和广度优先遍历序列，画出相应的生成树。相应的生成树。EDCBAF103443357.7 对给出如下的无向带权图，对给出如下的无向带权图，（1）写出它的邻接矩阵，并按普里姆斯算法）写出它的邻接矩阵，并按普里姆斯算法求其最小生成树；求其最小生成树；（2）写出它的邻接表，并按克鲁斯卡尔算法）写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。求其最小生成树。7.9试列出下图中全部可能的拓扑有序序列，试列出下图中全部可能的拓扑有序序列，并指出应用并指出应用7.5.1节中算法求得的是哪一个序节中算法求得的是哪一个序列（注意：应先确定其存储结构）。列（注意：应先确定其存储结构）。7.10对于下图所示的对于下图所示的 AOE 网络，计算各活动网络，计算各活动弧的弧的 e(ai)和和 l(aj)函数值，各时间函数值，各时间(顶点顶点)的的 ve(vi)和和 vl(vj)函数值；列出各条关键路径。函数值；列出各条关键路径。7.11试利用试利用 Dijkstra 算法求右图中从顶点算法求右图中从顶点 a 到其它各顶点间的最短路径，写出执行算法到其它各顶点间的最短路径，写出执行算法过程中各步的状态。过程中各步的状态。第九章 作业9.9 9.19补充作业：补充作业：在顺序表(2,5,7,10,14,15,18,23,35,41,52)中，(1)用顺序查找关键字为23的记录需做 次关键码比较，用折半查找需做 次关键码比较？(2)用顺序查找关键字为12的记录需做 次关键码比较，用折半查找需做 次关键码比较？9.9 已知如下所示长度为12的表（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)(1)试按表中元素的的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的ASL。(2)若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的ASL。(3)按表中元素顺序构造一棵平衡二叉树，并求其在等概率的情况先查找成功的ASL。9.19 选取哈希函数H(k)=(3k)MOD 11。用开放定址法处理冲突，di=i(7k)MOD 10+1)(i=1,2,3,)。试在010的散列地址空间中对关键字序列（22,41,53,46,30,13,01,67）构造哈希表，并求等概率情况下查找成功时的平均查找长度。第十章作业10.1 10.3 10.1210.1 10.3 10.1210.1 以关键码序列（503,087,512,061,908,170,897,275,653,426）为例，手工执行以下排序算法，写出每一趟排序结束时的关键码状态：（1）直接插入排序；（2）希尔排序(增量d1=5)；（3）快速排序；（4）堆排序；（5）归并排序；（6）基数排序；1.设关键字序列为96,83,40,11,67,25，写出用下列算法排序时，第一趟结束时的状态。（1）希尔排序（d1=3）（2）快速排序 （3）归并排序 （4）堆排序10.3 试问在10.1题所列各种排序方法中，哪些是稳定的？哪些是不稳定的？并为每一种不稳定的排序方法举出一个不稳定的实例。10.12 判别以下序列是否为堆（小顶堆或大顶堆）。如果不是，则把它调整为堆（要求记录交换次数最少）。（1）(100,86,48,73,35,39,42,57,66,21)；（2）(12,70,33,65,24,56,48,92,86,33)；
