# 数据结构与算法 数据结构与算法课后习题答案

• L9_299931
了解作者
• 219.9KB
文件大小
• rar
文件格式
• 0
收藏次数
• VIP专享
资源类型
• 0
下载次数
• 2022-05-14 17:38
上传日期

weis 习题答案.rar
• weis 习题答案
• ch11.pdf
13KB
• ch10.pdf
44.4KB
• ch08.pdf
14.4KB
• ch00.pdf
4KB
• ch09.pdf
41.9KB
• ch03.pdf
15KB
• ch06.pdf
31.3KB
• ch02.pdf
14.4KB
• ch05.pdf
13.1KB
• ch07.pdf
21.7KB
• ch01.pdf
11.4KB
• ch04.pdf
28.4KB
• ch12.pdf
4.3KB

<html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta charset="utf-8"> <meta name="generator" content="pdf2htmlEX"> <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1"> <link rel="stylesheet" href="https://static.pudn.com/base/css/base.min.css"> <link rel="stylesheet" href="https://static.pudn.com/base/css/fancy.min.css"> <link rel="stylesheet" href="https://static.pudn.com/prod/directory_preview_static/627fea2cebb030486d250f97/raw.css"> <script src="https://static.pudn.com/base/js/compatibility.min.js"></script> <script src="https://static.pudn.com/base/js/pdf2htmlEX.min.js"></script> <script> try{ pdf2htmlEX.defaultViewer = new pdf2htmlEX.Viewer({}); }catch(e){} </script> <title></title> </head> <body> <div id="sidebar" style="display: none"> <div id="outline"> </div> </div> <div id="pf1" class="pf w0 h0" data-page-no="1"><div class="pc pc1 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/627fea2cebb030486d250f97/bg1.jpg"><div class="t m0 x1 h2 y1 ff1 fs0 fc0 sc0 ls0 ws0">Chapter<span class="_"> </span>10:<span class="_"> </span>Algorithm<span class="_"> </span>Design<span class="_"> </span>Techniques</div><div class="t m0 x1 h3 y2 ff2 fs1 fc0 sc0 ls0 ws0">10.1<span class="_ _0"> </span>First,<span class="_ _1"> </span>we<span class="_ _2"> </span>show<span class="_ _2"> </span>that<span class="_ _2"> </span>if<span class="_ _1"> </span><span class="ff3">N</span></div><div class="t m0 x2 h4 y2 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x3 h3 y2 ff2 fs1 fc0 sc0 ls0 ws0">evenly<span class="_ _2"> </span>divides<span class="_ _2"> </span><span class="ff3">P</span></div><div class="t m0 x4 h4 y2 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x5 h3 y2 ff2 fs1 fc0 sc0 ls0 ws0">,<span class="_ _2"> </span>then<span class="_ _2"> </span>each<span class="_ _2"> </span>of</div><div class="t m0 x6 h4 y2 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x7 h5 y2 ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 x8 h6 y3 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x9 h7 y3 ff2 fs2 fc0 sc0 ls0 ws0">(<span class="ff3">i</span></div><div class="t m0 xa h6 y3 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xb h8 y3 ff5 fs2 fc0 sc0 ls0 ws0">&#8722;<span class="ff2">1)<span class="ff3">P</span></span></div><div class="t m0 xc h6 y3 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xd h8 y3 ff5 fs2 fc0 sc0 ls0 ws0">+<span class="ff2">1</span></div><div class="t m0 xe h3 y2 ff2 fs1 fc0 sc0 ls0 ws0">through</div><div class="t m0 xf h4 y2 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x10 h5 y2 ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 x11 h9 y3 ff3 fs2 fc0 sc0 ls0 ws0">iP</div><div class="t m0 x12 h4 y3 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x13 h3 y4 ff2 fs1 fc0 sc0 ls0 ws0">must<span class="_ _2"> </span>be</div><div class="t m0 x14 h3 y5 ff2 fs1 fc0 sc0 ls0 ws0">placed<span class="_ _3"> </span>as<span class="_ _3"> </span>the<span class="_ _4"> </span><span class="ff3">i</span></div><div class="t m0 x15 h6 y6 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x16 h9 y6 ff3 fs2 fc0 sc0 ls0 ws0">th</div><div class="t m0 x17 h4 y6 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x18 h3 y7 ff2 fs1 fc0 sc0 ls0 ws0">job<span class="_ _4"> </span>on<span class="_ _3"> </span>some<span class="_ _4"> </span>processor.<span class="_ _5"> </span>Suppose<span class="_ _3"> </span>otherwise.<span class="_ _5"> </span>Then<span class="_ _3"> </span>in<span class="_ _4"> </span>the<span class="_ _3"> </span>supposed</div><div class="t m0 x14 h3 y8 ff2 fs1 fc0 sc0 ls0 ws0">optimal<span class="_ _6"> </span>ordering,<span class="_ _6"> </span>we<span class="_ _7"> </span>must<span class="_ _6"> </span>be<span class="_ _6"> </span>able<span class="_ _7"> </span>to<span class="_ _6"> </span>&#64257;nd<span class="_ _6"> </span>some<span class="_ _6"> </span>jobs</div><div class="t m0 x19 h4 y8 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x1a h5 y8 ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 x1b h9 y9 ff3 fs2 fc0 sc0 ls0 ws0">x</div><div class="t m0 x1c h4 y9 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x1d h3 ya ff2 fs1 fc0 sc0 ls0 ws0">and</div><div class="t m0 x1e h4 ya ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x1f h5 ya ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 xa h9 y9 ff3 fs2 fc0 sc0 ls0 ws0">y</div><div class="t m0 x20 h4 y9 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x21 h3 ya ff2 fs1 fc0 sc0 ls0 ws0">such<span class="_ _6"> </span>that</div><div class="t m0 x22 h4 ya ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x23 h5 ya ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 x24 h9 y9 ff3 fs2 fc0 sc0 ls0 ws0">x</div><div class="t m0 x25 h4 y9 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x26 h3 ya ff2 fs1 fc0 sc0 ls0 ws0">is<span class="_ _6"> </span>the<span class="_ _7"> </span><span class="ff3">t</span></div><div class="t m0 x27 h6 yb ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x28 h9 yb ff3 fs2 fc0 sc0 ls0 ws0">th</div><div class="t m0 x29 h4 yb ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x2a h3 yc ff2 fs1 fc0 sc0 ls0 ws0">job</div><div class="t m0 x14 h3 yd ff2 fs1 fc0 sc0 ls0 ws0">on<span class="_ _8"> </span>some<span class="_ _8"> </span>processor<span class="_ _6"> </span>and</div><div class="t m0 x2b h4 yd ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x2c h5 yd ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 x2 h9 ye ff3 fs2 fc0 sc0 ls0 ws0">y</div><div class="t m0 x2d h4 ye ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x2e h3 yf ff2 fs1 fc0 sc0 ls0 ws0">is<span class="_ _8"> </span>the<span class="_ _6"> </span><span class="ff3">t</span></div><div class="t m0 x2f h4 yf ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x30 ha yf ff5 fs1 fc0 sc0 ls0 ws0">+<span class="ff2">1</span></div><div class="t m0 x31 h9 y10 ff3 fs2 fc0 sc0 ls0 ws0">th</div><div class="t m0 x32 h4 y10 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x33 h3 y11 ff2 fs1 fc0 sc0 ls0 ws0">job<span class="_ _8"> </span>on<span class="_ _6"> </span>some<span class="_ _8"> </span>processor<span class="_ _6"> </span>but<span class="_ _8"> </span><span class="ff3">t</span></div><div class="t m0 x34 h9 ye ff3 fs2 fc0 sc0 ls0 ws0">x</div><div class="t m0 x35 h4 ye ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x36 h3 yf ff3 fs1 fc0 sc0 ls0 ws0"> <span class="ff2">&gt;</span> t</div><div class="t m0 x37 h9 ye ff3 fs2 fc0 sc0 ls0 ws0">y</div><div class="t m0 x22 h4 ye ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x38 h3 yf ff2 fs1 fc0 sc0 ls0 ws0">.<span class="_ _9"> </span>Let</div><div class="t m0 x39 h4 yf ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x3a h5 yf ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 x13 h9 ye ff3 fs2 fc0 sc0 ls0 ws0">z</div><div class="t m0 x3b h4 ye ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x27 h3 yf ff2 fs1 fc0 sc0 ls0 ws0">be<span class="_ _6"> </span>the</div><div class="t m0 x14 h3 y12 ff2 fs1 fc0 sc0 ls0 ws0">job<span class="_"> </span>immediately<span class="_ _7"> </span>following</div><div class="t m0 x2e h4 y12 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x3c h5 y12 ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 x3d h9 y13 ff3 fs2 fc0 sc0 ls0 ws0">x</div><div class="t m0 x3e h4 y13 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x3f h3 y14 ff2 fs1 fc0 sc0 ls0 ws0">.<span class="_ _a"> </span>If<span class="_"> </span>we<span class="_"> </span>swap</div><div class="t m0 x40 h4 y14 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x41 h5 y14 ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 x4 h9 y13 ff3 fs2 fc0 sc0 ls0 ws0">y</div><div class="t m0 x42 h4 y13 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x43 h3 y14 ff2 fs1 fc0 sc0 ls0 ws0">and</div><div class="t m0 x44 h4 y14 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x45 h5 y14 ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 x46 h9 y13 ff3 fs2 fc0 sc0 ls0 ws0">z</div><div class="t m0 x47 h4 y13 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x48 h3 y14 ff2 fs1 fc0 sc0 ls0 ws0">,<span class="_"> </span>it<span class="_ _7"> </span>is<span class="_"> </span>easy<span class="_"> </span>to<span class="_"> </span>check<span class="_"> </span>that<span class="_"> </span>the<span class="_"> </span>mean<span class="_"> </span>pro-</div><div class="t m0 x14 h3 y15 ff2 fs1 fc0 sc0 ls0 ws0">cessing<span class="_"> </span>time<span class="_ _7"> </span>is<span class="_ _7"> </span>unchanged<span class="_"> </span>and<span class="_ _7"> </span>thus<span class="_ _7"> </span>still<span class="_ _7"> </span>optimal.<span class="_ _a"> </span>But<span class="_ _7"> </span>now</div><div class="t m0 x49 h4 y15 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x6 h5 y15 ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 x4a h9 y16 ff3 fs2 fc0 sc0 ls0 ws0">y</div><div class="t m0 x1e h4 y16 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 xb h3 y17 ff2 fs1 fc0 sc0 ls0 ws0">follows</div><div class="t m0 x4b h4 y17 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x4c h5 y17 ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 x4d h9 y16 ff3 fs2 fc0 sc0 ls0 ws0">x</div><div class="t m0 x4e h4 y16 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x4f h3 y17 ff2 fs1 fc0 sc0 ls0 ws0">,<span class="_ _7"> </span>which<span class="_"> </span>is<span class="_ _7"> </span>impos-</div><div class="t m0 x14 h3 y18 ff2 fs1 fc0 sc0 ls0 ws0">sible<span class="_ _8"> </span>because<span class="_ _6"> </span>we<span class="_ _8"> </span>know<span class="_ _2"> </span>that<span class="_ _8"> </span>the<span class="_ _8"> </span>jobs<span class="_ _8"> </span>on<span class="_ _2"> </span>any<span class="_ _8"> </span>processor<span class="_ _6"> </span>must<span class="_ _8"> </span>be<span class="_ _8"> </span>in<span class="_ _8"> </span>sorted<span class="_ _8"> </span>order<span class="_ _6"> </span>from<span class="_ _8"> </span>the</div><div class="t m0 x14 h3 y19 ff2 fs1 fc0 sc0 ls0 ws0">results<span class="_"> </span>of<span class="_"> </span>the<span class="_"> </span>one<span class="_"> </span>processor<span class="_"> </span>case.</div><div class="t m0 x14 h3 y1a ff2 fs1 fc0 sc0 ls0 ws0">Let</div><div class="t m0 x50 h4 y1a ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x51 h5 y1a ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 x52 h9 y1b ff3 fs2 fc0 sc0 ls0 ws0">e</div><div class="t m0 x53 h6 y1b ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x54 h7 y1b ff2 fs2 fc0 sc0 ls0 ws0">1</div><div class="t m0 x55 h3 y1c ff2 fs1 fc0 sc0 ls0 ws0">,</div><div class="t m0 x56 h4 y1c ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x57 h5 y1c ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 x58 h9 y1b ff3 fs2 fc0 sc0 ls0 ws0">e</div><div class="t m0 x59 h6 y1b ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x5a h7 y1b ff2 fs2 fc0 sc0 ls0 ws0">2</div><div class="t m0 x5b h3 y1c ff2 fs1 fc0 sc0 ls0 ws0">,<span class="_ _7"> </span>...,</div><div class="t m0 x15 h4 y1c ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x16 h5 y1c ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 x5c h9 y1b ff3 fs2 fc0 sc0 ls0 ws0">eM</div><div class="t m0 x18 h4 y1b ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x5d h3 y1a ff2 fs1 fc0 sc0 ls0 ws0">be<span class="_ _7"> </span>the<span class="_"> </span>extra<span class="_ _7"> </span>jobs<span class="_ _7"> </span>if<span class="_ _7"> </span><span class="ff3">N</span></div><div class="t m0 x5e h4 y1a ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x5f h3 y1a ff2 fs1 fc0 sc0 ls0 ws0">does<span class="_ _7"> </span>not<span class="_ _7"> </span>evenly<span class="_ _7"> </span>divide<span class="_ _7"> </span><span class="ff3">P</span></div><div class="t m0 x60 h4 y1a ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x61 h3 y1a ff2 fs1 fc0 sc0 ls0 ws0">.<span class="_ _a"> </span>It<span class="_ _7"> </span>is<span class="_ _6"> </span>easy<span class="_"> </span>to<span class="_ _7"> </span>see<span class="_ _7"> </span>that</div><div class="t m0 x14 h3 y1d ff2 fs1 fc0 sc0 ls0 ws0">the<span class="_ _8"> </span>processing<span class="_ _6"> </span>time<span class="_ _8"> </span>for<span class="_ _8"> </span>these<span class="_ _8"> </span>jobs<span class="_ _8"> </span>depends<span class="_ _6"> </span>only<span class="_ _8"> </span>on<span class="_ _8"> </span>how<span class="_ _8"> </span>quickly<span class="_ _8"> </span>they<span class="_ _8"> </span>can<span class="_ _8"> </span>be<span class="_ _6"> </span>scheduled,</div><div class="t m0 x14 h3 y1e ff2 fs1 fc0 sc0 ls0 ws0">and<span class="_ _7"> </span>that<span class="_ _6"> </span>they<span class="_ _7"> </span>must<span class="_ _6"> </span>be<span class="_ _7"> </span>the<span class="_ _6"> </span>last<span class="_ _7"> </span>scheduled<span class="_ _7"> </span>job<span class="_ _6"> </span>on<span class="_ _6"> </span>some<span class="_ _7"> </span>processor.<span class="_ _a"> </span>It<span class="_ _6"> </span>is<span class="_ _7"> </span>easy<span class="_ _7"> </span>to<span class="_ _7"> </span>see<span class="_ _7"> </span>that<span class="_ _6"> </span>the</div><div class="t m0 x14 h3 y1f ff2 fs1 fc0 sc0 ls0 ws0">&#64257;rst<span class="_ _1"> </span><span class="ff3">M</span></div><div class="t m0 x55 h4 y1f ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x56 h3 y1f ff2 fs1 fc0 sc0 ls0 ws0">processors<span class="_ _2"> </span>must<span class="_ _1"> </span>have<span class="_ _2"> </span>jobs</div><div class="t m0 x62 h4 y1f ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x63 h5 y1f ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 x31 h6 y20 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x64 h7 y20 ff2 fs2 fc0 sc0 ls0 ws0">(<span class="ff3">i</span></div><div class="t m0 x32 h6 y20 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x65 h8 y20 ff5 fs2 fc0 sc0 ls0 ws0">&#8722;<span class="ff2">1)<span class="ff3">P</span></span></div><div class="t m0 x40 h6 y20 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x41 h8 y20 ff5 fs2 fc0 sc0 ls0 ws0">+<span class="ff2">1</span></div><div class="t m0 x66 h3 y21 ff2 fs1 fc0 sc0 ls0 ws0">through</div><div class="t m0 x1b h4 y21 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">P</span></div><div class="t m0 x67 h5 y21 ff3 fs1 fc0 sc0 ls0 ws0">j</div><div class="t m0 x1c h9 y20 ff3 fs2 fc0 sc0 ls0 ws0">iP</div><div class="t m0 x68 h6 y20 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x69 h8 y20 ff5 fs2 fc0 sc0 ls0 ws0">+<span class="ff3">M</span></div><div class="t m0 x6a h4 y20 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x8 h3 y22 ff2 fs1 fc0 sc0 ls0 ws0">;<span class="_ _1"> </span>we<span class="_ _2"> </span>leave<span class="_ _2"> </span>the<span class="_ _2"> </span>details<span class="_ _1"> </span>to<span class="_ _2"> </span>the</div><div class="t m0 x14 h3 y23 ff2 fs1 fc0 sc0 ls0 ws0">reader.</div><div class="t m0 x1 h3 y24 ff2 fs1 fc0 sc0 ls0 ws0">10.3</div><div class="t m0 x6b h3 y25 ff2 fs1 fc0 sc0 ls0 ws0">,</div><div class="t m0 x14 h3 y26 ff2 fs1 fc0 sc0 ls0 ws0">4<span class="_ _b"> </span>7<span class="_ _b"> </span>8<span class="_ _b"> </span>9</div><div class="t m0 x6c h3 y27 ff2 fs1 fc0 sc0 ls0 ws0">0</div><div class="t m0 x62 h3 y26 ff2 fs1 fc0 sc0 ls0 ws0">1<span class="_ _b"> </span>5</div><div class="t m0 x6d h3 y27 ff2 fs1 fc0 sc0 ls0 ws0">sp</div><div class="t m0 x6e h3 y28 ff2 fs1 fc0 sc0 ls0 ws0">nl</div><div class="t m0 xc h3 y29 ff2 fs1 fc0 sc0 ls0 ws0">3<span class="_ _c"> </span>:</div><div class="t m0 x6f h3 y28 ff2 fs1 fc0 sc0 ls0 ws0">6<span class="_ _b"> </span>2</div><div class="t m0 x1 h3 y2a ff2 fs1 fc0 sc0 ls0 ws0">10.4<span class="_ _0"> </span>One<span class="_"> </span>method<span class="_"> </span>is<span class="_ _7"> </span>to<span class="_"> </span>generate<span class="_"> </span>code<span class="_"> </span>that<span class="_"> </span>can<span class="_ _d"> </span>be<span class="_"> </span>evaluated<span class="_"> </span>by<span class="_"> </span>a<span class="_"> </span>stack<span class="_ _d"> </span>machine.<span class="_ _e"> </span>The<span class="_"> </span>two<span class="_"> </span>opera-</div><div class="t m0 x14 h3 y2b ff2 fs1 fc0 sc0 ls0 ws0">tions<span class="_ _7"> </span>are<span class="_ _7"> </span><span class="ff3">Push</span></div><div class="t m0 x70 h4 y2b ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x71 h3 y2b ff2 fs1 fc0 sc0 ls0 ws0">(the<span class="_ _7"> </span>one<span class="_ _7"> </span>node<span class="_ _7"> </span>tree<span class="_ _7"> </span>corresponding<span class="_"> </span>to)<span class="_ _6"> </span>a<span class="_ _7"> </span>symbol<span class="_ _7"> </span>onto<span class="_ _6"> </span>a<span class="_"> </span>stack<span class="_ _7"> </span>and<span class="_ _7"> </span><span class="ff3">Combine,</span></div><div class="t m0 x72 h4 y2b ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x14 h3 y2c ff2 fs1 fc0 sc0 ls0 ws0">which<span class="_ _6"> </span>pops<span class="_ _6"> </span>two<span class="_ _6"> </span>trees<span class="_ _7"> </span>of<span class="_ _f"></span>f<span class="_ _7"> </span>the<span class="_ _6"> </span>stack,<span class="_ _6"> </span>merges<span class="_ _7"> </span>them,<span class="_ _6"> </span>and<span class="_ _6"> </span>pushes<span class="_ _7"> </span>the<span class="_ _6"> </span>result<span class="_ _6"> </span>back<span class="_ _7"> </span>on.<span class="_ _10"> </span>For<span class="_ _6"> </span>the</div><div class="t m0 x14 h3 y2d ff2 fs1 fc0 sc0 ls0 ws0">example<span class="_ _7"> </span>in<span class="_ _7"> </span>the<span class="_ _7"> </span>text,<span class="_ _6"> </span>the<span class="_ _7"> </span>stack<span class="_ _7"> </span>instructions<span class="_ _7"> </span>are<span class="_ _7"> </span><span class="ff3">Push(s),<span class="_ _7"> </span>Push(nl),<span class="_ _6"> </span>Combine,<span class="_ _7"> </span>Push(t),<span class="_"> </span>Com-</span></div><div class="t m0 x14 h5 y2e ff3 fs1 fc0 sc0 ls0 ws0">bine,<span class="_"> </span>Push(a),<span class="_"> </span>Combine,<span class="_"> </span>Push(e),<span class="_"> </span>Combine,<span class="_"> </span>Push(i),<span class="_"> </span>Push<span class="_"> </span>(sp),<span class="_"> </span>Combine,<span class="_"> </span>Combine.</div><div class="t m0 x14 h3 y2f ff2 fs1 fc0 sc0 ls0 ws0">By<span class="_ _6"> </span>encoding<span class="_ _7"> </span>a<span class="_ _6"> </span><span class="ff3">Combine</span></div><div class="t m0 x2c h4 y2f ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x73 h3 y2f ff2 fs1 fc0 sc0 ls0 ws0">with<span class="_ _6"> </span>a<span class="_ _7"> </span>0<span class="_ _6"> </span>and<span class="_ _6"> </span>a<span class="_ _7"> </span><span class="ff3">Push</span></div><div class="t m0 x66 h4 y2f ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x74 h3 y2f ff2 fs1 fc0 sc0 ls0 ws0">with<span class="_ _6"> </span>a<span class="_ _7"> </span>1<span class="_ _6"> </span>followed<span class="_ _7"> </span>by<span class="_ _7"> </span>the<span class="_ _6"> </span>symbol,<span class="_ _6"> </span>the<span class="_ _7"> </span>total</div><div class="t m0 x14 h3 y30 ff2 fs1 fc0 sc0 ls0 ws0">extra<span class="_ _2"> </span>space<span class="_ _8"> </span>is<span class="_ _2"> </span>2<span class="ff3">N</span></div><div class="t m0 x75 h4 y30 ff4 fs1 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x76 ha y30 ff3 fs1 fc0 sc0 ls0 ws0"> <span class="ff5">&#8722;</span> <span class="ff2">1<span class="_ _1"> </span>bits<span class="_ _2"> </span>if<span class="_ _2"> </span>all<span class="_ _2"> </span>the<span class="_ _2"> </span>symbols<span class="_ _1"> </span>are<span class="_ _8"> </span>of<span class="_ _2"> </span>equal<span class="_ _2"> </span>length.<span class="_ _11"> </span>Generating<span class="_ _8"> </span>the<span class="_ _2"> </span>stack</span></div><div class="t m0 x14 h3 y31 ff2 fs1 fc0 sc0 ls0 ws0">machine<span class="_"> </span>code<span class="_"> </span>can<span class="_ _d"> </span>be<span class="_"> </span>done<span class="_"> </span>with<span class="_"> </span>a<span class="_"> </span>simple<span class="_"> </span>recursive<span class="_ _d"> </span>procedure<span class="_ _d"> </span>and<span class="_"> </span>is<span class="_"> </span>left<span class="_"> </span>to<span class="_"> </span>the<span class="_"> </span>reader.</div><div class="t m0 x1 h3 y32 ff2 fs1 fc0 sc0 ls0 ws0">10.6<span class="_ _0"> </span>Maintain<span class="_"> </span>two<span class="_ _7"> </span>queues,<span class="_ _7"> </span><span class="ff3">Q</span></div><div class="t m0 x77 h6 y33 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x2c h7 y33 ff2 fs2 fc0 sc0 ls0 ws0">1</div><div class="t m0 x2d h3 y34 ff2 fs1 fc0 sc0 ls0 ws0">and<span class="_"> </span><span class="ff3">Q</span></div><div class="t m0 x78 h6 y33 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x79 h7 y33 ff2 fs2 fc0 sc0 ls0 ws0">2</div><div class="t m0 x7a h3 y34 ff2 fs1 fc0 sc0 ls0 ws0">.<span class="_ _a"> </span><span class="ff3">Q</span></div><div class="t m0 x7b h6 y33 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x31 h7 y33 ff2 fs2 fc0 sc0 ls0 ws0">1</div><div class="t m0 x7c h3 y34 ff2 fs1 fc0 sc0 ls0 ws0">will<span class="_ _7"> </span>store<span class="_"> </span>single-node<span class="_ _7"> </span>trees<span class="_"> </span>in<span class="_ _7"> </span>sorted<span class="_"> </span>order,<span class="_"> </span>and<span class="_"> </span><span class="ff3">Q</span></div><div class="t m0 x7d h6 y33 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x7e h7 y33 ff2 fs2 fc0 sc0 ls0 ws0">2</div><div class="t m0 x14 h3 y35 ff2 fs1 fc0 sc0 ls0 ws0">will<span class="_ _4"> </span>store<span class="_ _3"> </span>multinode<span class="_ _4"> </span>trees<span class="_ _3"> </span>in<span class="_ _4"> </span>sorted<span class="_ _4"> </span>order.<span class="_ _5"> </span>Place<span class="_ _3"> </span>the<span class="_ _4"> </span>initial<span class="_ _4"> </span>single-node<span class="_ _3"> </span>trees<span class="_ _3"> </span>on<span class="_ _4"> </span><span class="ff3">Q</span></div><div class="t m0 x7f h6 y36 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x80 h7 y36 ff2 fs2 fc0 sc0 ls0 ws0">1</div><div class="t m0 x81 h3 y35 ff2 fs1 fc0 sc0 ls0 ws0">,</div><div class="t m0 x14 h3 y37 ff2 fs1 fc0 sc0 ls0 ws0">enqueueing<span class="_ _6"> </span>the<span class="_ _8"> </span>smallest<span class="_ _8"> </span>weight<span class="_ _8"> </span>tree<span class="_ _6"> </span>&#64257;rst.<span class="_ _11"> </span>Initially,<span class="_ _8"> </span><span class="ff3">Q</span></div><div class="t m0 x1b h6 y38 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x67 h7 y38 ff2 fs2 fc0 sc0 ls0 ws0">2</div><div class="t m0 x1d h3 y39 ff2 fs1 fc0 sc0 ls0 ws0">is<span class="_ _8"> </span>empty.<span class="_ _9"> </span>Examine<span class="_ _6"> </span>the<span class="_ _8"> </span>&#64257;rst<span class="_ _2"> </span>two</div><div class="t m0 x14 h3 y3a ff2 fs1 fc0 sc0 ls0 ws0">entries<span class="_ _2"> </span>of<span class="_ _1"> </span>each<span class="_ _2"> </span>of<span class="_ _2"> </span><span class="ff3">Q</span></div><div class="t m0 x82 h6 y3b ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x83 h7 y3b ff2 fs2 fc0 sc0 ls0 ws0">1</div><div class="t m0 x84 h3 y3c ff2 fs1 fc0 sc0 ls0 ws0">and<span class="_ _2"> </span><span class="ff3">Q</span></div><div class="t m0 x85 h6 y3b ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x86 h7 y3b ff2 fs2 fc0 sc0 ls0 ws0">2</div><div class="t m0 x87 h3 y3c ff2 fs1 fc0 sc0 ls0 ws0">,<span class="_ _1"> </span>and<span class="_ _2"> </span>dequeue<span class="_ _2"> </span>the<span class="_ _2"> </span>two<span class="_ _1"> </span>smallest.<span class="_ _11"> </span>(This<span class="_ _2"> </span>requires<span class="_ _2"> </span>an<span class="_ _2"> </span>easily</div><div class="t m0 x14 h3 y3d ff2 fs1 fc0 sc0 ls0 ws0">implemented<span class="_ _7"> </span>extension<span class="_ _7"> </span>to<span class="_ _7"> </span>the<span class="_ _7"> </span>ADT.)<span class="_"> </span>Merge<span class="_ _7"> </span>the<span class="_"> </span>tree<span class="_"> </span>and<span class="_ _7"> </span>place<span class="_"> </span>the<span class="_ _7"> </span>result<span class="_"> </span>at<span class="_ _7"> </span>the<span class="_ _7"> </span>end<span class="_"> </span>of<span class="_ _7"> </span><span class="ff3">Q</span></div><div class="t m0 x7f h6 y3e ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x80 h7 y3e ff2 fs2 fc0 sc0 ls0 ws0">2</div><div class="t m0 x81 h3 y3f ff2 fs1 fc0 sc0 ls0 ws0">.</div><div class="t m0 x14 h3 y40 ff2 fs1 fc0 sc0 ls0 ws0">Continue<span class="_"> </span>this<span class="_ _7"> </span>step<span class="_"> </span>until<span class="_"> </span><span class="ff3">Q</span></div><div class="t m0 x73 h6 y41 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x2d h7 y41 ff2 fs2 fc0 sc0 ls0 ws0">1</div><div class="t m0 x3c h3 y42 ff2 fs1 fc0 sc0 ls0 ws0">is<span class="_"> </span>empty<span class="_"> </span>and<span class="_"> </span>only<span class="_"> </span>one<span class="_"> </span>tree<span class="_"> </span>is<span class="_"> </span>left<span class="_"> </span>in<span class="_"> </span><span class="ff3">Q</span></div><div class="t m0 x88 h6 y41 ff4 fs2 fc0 sc0 ls0 ws0"><span class="fc1 sc0">O</span></div><div class="t m0 x89 h7 y41 ff2 fs2 fc0 sc0 ls0 ws0">2</div><div class="t m0 x8a h3 y42 ff2 fs1 fc0 sc0 ls0 ws0">.</div><div class="t m0 x32 h3 y43 ff2 fs1 fc0 sc0 ls0 ws0">-54-</div></div><div class="pi" data-data='{"ctm":[1.568627,0.000000,0.000000,1.568627,0.000000,0.000000]}'></div></div> </body> </html>

相关推荐
• 数据结构与算法
数据结构与算法
• 数据结构与算法
数据结构与算法 很不错哦.经典的课件内容 需要的小伙伴们不要错过哦
• 数据结构与算法
数据结构与算法
• 数据结构与算法数据结构与算法
数据结构与算法.rar数据结构与算法.rar数据结构与算法.rar数据结构与算法.rar数据结构与算法.rar数据结构与算法.rar数据结构与算法.rar
• 数据结构与算法
数据结构与算法的课件,还有其实验课的完整的实验报告且含代码
• 数据结构与算法
关于汉诺塔的，源代码。可以移动。数据结构与算法。期末项目的一部分
• 数据结构与算法.rar
数据结构讲义和算法讲义.rar，
• 数据结构与算法.rar
数据结构与算法.DOC 1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效...
• 数据结构 算法分析 课件
数据结构 算法分析 课件 四川大学上课用课件，很简洁啊，欢迎下载！！！
• 数据结构与算法
慕k网,牛k网数据结构与算法讲解,自己看了一点点,觉得非常不错,非常适合学习数据结构与算法的小伙伴们.分享给大家了.