《严蔚敏《数据结构(c语言版)习题集》动态存储管理》由会员分享，可在线阅读，更多相关《严蔚敏《数据结构(c语言版)习题集》动态存储管理（9页珍藏版）》请在金锄头文库上搜索。
1、第八章 动态存储管理 8.11 typedef struct char *start; int size; fmblock; /空闲块类型 char *Malloc_Fdlf(int n)/遵循最后分配者最先释放规则的内存分配算法 while(Gettop(S,b) f=p+n-1; /f 指向空闲块底部 if(p-1)-tagf-tag=0; f-uplink=p; if(!pav) p-llink=p; p-rlink=p; else q=pav-llink; p-llink=q;p-rlink=pav; q-rlink=p;pav-llink=p; pav=p; /if else if(
2、!(p-1)-tag q-size+=n; f-uplink=q; f-tag=0; else if(p-1)-tag s=q-llink;t=q-rlink; p-llink=s;p-rlink=t; s-rlink=p;t-llink=p; p-size+=q-size; (q+q-size-1)-uplink=p; p-tag=0; else /上下邻块均为空闲块 s=(p-1)-uplink; t=f+1; s-size+=n+t-size; t-llink-rlink=t-rlink; t-rlink-llink=t-llink; (t+t-size-1)-uplink=s; /Fr
3、ee_BT,该算法在课本里有详细的描述. 8.14 void Free_BS(freelist /求回收块的伙伴地址 addr-tag=0; addr-kval=n; for(i=0;availi.nodesizellink=addr; addr-rlink=addr; availi.first=addr; /作为唯一一个该大小的空闲块 else for(p=availi.first;p!=buddyp=p-rlink);/寻找伙伴 if(p=buddy) /伙伴为空闲块,此时进行合并 if(p-rlink=p) availi.first=NULL;/伙伴是此大小的唯一空闲块 else p-l
4、link-rlink=p-rlink; p-rlink-llink=p-llink; /从空闲块链中删去伙伴 new=addrp?p:addr; /合并后的新块首址 Free_BS(avail,new,2*n); /递归地回收新块 /if else /伙伴为占用块,此时插入空闲块链头部 q=p-rlink; p-rlink=addr;addr-llink=p; q-llink=addr;addr-rlink=q; /else /Free_BS 8.15 FBList *MakeList(char *highbound,char *lowbound)/把堆结构存储的的所有空闲 块链接成可利用空间
5、表,并返回表头指针 p=lowbound; while(p-tag /没有空闲块 head=p; for(q=p;ptag) q-next=p; q=p; /if p-next=NULL; return head; /返回头指针 /MakeList 8.16 void Mem_Contract(Heap j=0; for(i=0;itag) s=H.listi.length; p=H.listi.stadr; for(k=0;k * t ) 其中，指针 t 指向生成森林上具有图顶点 v 信息的根结点。 （提示：在继续按深度方向从根 v 的某一未访 问过的邻接顶点 w 向下遍历之前，建立子女结点
6、。但需要判断是作为根的第一个子女还是 作为其子女的右兄弟链入生成树。 ） 8-10 用邻接表表示图时，顶点个数设为 n，边的条数设为 e，在邻接表上执行有关图的遍历 操作时，时间代价是 O(n*e)？还是 O(n+e)？或者是 O(max(n,e)？ 【解答】 在邻接表上执行图的遍历操作时， 需要对邻接表中所有的边链表中的结点访问一次， 还需要对所有的顶点访问一次，所以时间代价是 O(n+e)。 8-15 右图是一个连通图，请画出 (1) 以顶点为根的深度优先生成树； (2) 如果有关节点，请找出所有的关节 点。 (3) 如果想把该连通图变成重连通图， 至少在图中加几条边？如何加？ 【解答】
7、(1) 从顶点出发的深度优先生成树为 此答案不唯一 (2) 8-16 试证明在一个有 n 个顶点的完全图中，生成树 的数目至少有 2n-1-1。 8-17 编写一个完整的程序， 首先定义堆和并查集的 结构类型和相关操作，再定义 Kruskal 求连通网络 的最小生成树算法的实现。并以右图为例，写出求 解过程中堆、并查集和最小生成树的变化。 8-18 利用 Dijkstra 算法的思想，设计一个求最小生成树的算法。 8-19 以右图为例，按 Dijkstra 算法计算得到的从顶点 到其它各个顶点的最短路径和最短路径长度。 8-20 在以下假设下，重写 Dijkstra 算法： (1) 用邻接表表
8、示带权有向图 G，其中每个边结点有 3 个域：邻接顶点 vertex，边上的 权值 length 和边链表的链接指针 link。 (2)用集合 T = V(G) - S 代替 S(已找到最短路径的顶点集合)，利用链表来表示集合 T。 试比较新算法与原来的算法，计算时间是快了还是慢了，给出定量的比较。 8-22 使用 Floyd 算法计算 8-19 题所用的带权有向图的各对顶点之间的最短路径。 8-23 下面是基于元素 0 到 4 的一些优先关系的集合，试问它们是否定义了一个偏序关系？ 为什么？ 0 nil do begin w := p.adj; Gw.ind := Gw.ind - 1; i
9、f ( visitedw = 0 ) and ( Gw.ind = 0 ) then dfs ( G, w ); p := p.link; end; end; 主程序 for i := 1 to n do visitedi := 0; count := 0; read ( i, j, w); while ( i 0 ) do begin new(p); p.adj := j; p.cost := w; Gj.ind := Gj.ind + 1; p.link := Gi.fout; Gi.fout := p; read ( i, j, w); end; for i := 1 to n do i
10、f ( visitedi = 0 ) and ( Gi.ind = 0 ) then dfs ( G, i ); if count e 0 0 15 19 19 15 29 38 l 17 0 15 27 19 27 37 38 l-e 17 0 0 8 0 12 8 0 此工程最早完成时间为 43。关键路径为 8-27 若 AOE 网络的每一项活动都是关键活动。 令 G 是将该网络的边去掉方向和权后得 到的无向图。 (1) 如果图中有一条边处于从开始顶点到完成顶点的每一条路径上，则仅加速该边表示 的活动就能减少整个工程的工期。这样的边称为桥(bridge)。证明若从连通图中删去桥，将 把图分割成两个连通分量。 (2) 编写一个时间复杂度为 O(n+e)的使用邻接表表示的算法，判断连通图 G 中是否有 桥，若有。输出这样的桥。
