数据结构习题集答案(c语言版严蔚敏)

《数据结构习题集答案(c语言版严蔚敏)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、注意：作业，大家一定要独立完成！！！第1章作业P.81.8设n为正整数.试确定下列各程序段中前置以记号@的语句的频度:(1)i=1;k=0;(2)i=1;k=0;While(i<=n-1){do{@k+=10*i;@k+=10*i;i++;i++;}}While(i<=n-1);(3)i=1;k=0;(4)k=0;While(i<=n-1){for(i=1;i<=n;i++){i++;for(j=i;j<=n;j++)@k+=10*i;@k++;}}(5)for(i=1;i<=n;i++){(6)i=1;j=0;for(j=1;j<=i;j++){While(i+j<=n){for(k=1

2、;k<=j;k++)@if(i>j)j++;@x+=delta;elsei++;}}(7)x=n;y=0;//n是不小于1的常数(8)x=91;y=100;While(x>=(y+1)*(y+1)){while(y>0){@y++;@if(x>100){x-=10;y--}}elsex++;}第2章作业顺序表部分作业2.11设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。2.21试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表(a1,a2,…,an)逆置为(an,an-1,…,a1)。链表部分作业2.14试写一算法在带头结点的单

3、链表结构上实现线性表操作LENGTH(L)2.19已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删结点空间（注意：mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。第3章作业p.243.15假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈。它们的栈底分别设在数组的两个端点。试编写实现这个双向栈tws的三个操作：初始化inistack（tws）、入栈push（tws,i,x）和出栈pop（tws,i）的算法，其中i为0或1，用以

4、分别指示设在数组两端的两个栈。3.28假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。第4章作业p.284.8已知主串s=’ADBADABBAABADABBADADA’模式串pat=’ADABBADADA’写出模式串的nextval函数值，并由此画出KMP算法匹配的全过程。第6章作业6.5已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……nk个度为k的结点，问该树中有多少个叶子结点？6.7一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各为多少？6.15请对下图所示二叉树进行后序线索化

5、，为每个空指针建立相应的前驱或后继线索。ABCEDGFH6.19画出和下列树对应的二叉树。ABCDEFGHIJK（d）6.21画出和下列二叉树相应的森林：ABCDFEIGMHKJ（e）6.26假设用于通信的电文仅有8个字母组成，字母在电文中出现的频率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。试为这8个字母设计哈夫曼编码。使用0~7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。6.28假设一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA。请画出该树。第7章作业7.1已知如下图所示的有向图，请给出

6、该图的邻接矩阵和邻接表。1325467.7对下面的无向带权图：（1）写出它的邻接矩阵，并按普里姆算法从顶点a开始求其最小生成树；（2）写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。abcdefgh345555932645677.9试列出下图中全部可能的拓扑有序序列，并指出应用7.5.1节中算法TopologicalSort求得的是哪一个序列（注意：应先确定其存储结构）。1324567.11试利用Dijkstra算法求下图中从顶点a到其它各顶点间的最短路径，写出执行过程中各步的状态。155b468ea92c412gf10553d7.13试利用Floyd算法求如图所示有向图中各对顶点之间的

7、最短路径。BACD143125补充题：已知AOE网如下所示，求：（1）每个事件的最早发生时间和最迟发生时间；（2）每个活动的最早开始时间和最迟开始时间；（3）该AOE网的关键路径；（4）提高那些活动的速度，可以缩短整个工期？4F611B523GDA3232EC5第9章作业9.9已知如下所示长度为12的表（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）(1)试按表中元素