離散數(shù)學(xué)屈婉玲版課后習(xí)題.doc
《離散數(shù)學(xué)屈婉玲版課后習(xí)題.doc》由會(huì)員分享,可在線閱讀,更多相關(guān)《離散數(shù)學(xué)屈婉玲版課后習(xí)題.doc(34頁珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、. 第一章部分課后習(xí)題參考答案 16 設(shè)p、q的真值為0;r、s的真值為1,求下列各命題公式的真值。 (1)p∨(q∧r) 0∨(0∧1) 0 (2)(p?r)∧(﹁q∨s) (0?1)∧(1∨1) 0∧10. (3)(p∧q∧r)?(p∧q∧﹁r) (1∧1∧1) ? (0∧0∧0)0 (4)(r∧s)→(p∧q) (0∧1)→(1∧0) 0→01 17.判斷下面一段論述是否為真:“是無理數(shù)。并且,如果3是無理數(shù),則也是無理數(shù)。另外6能被2整除,6才能被4整除?!? 答:p: 是無理數(shù) 1
2、q: 3是無理數(shù) 0 r: 是無理數(shù) 1 s: 6能被2整除 1 t: 6能被4整除 0 命題符號(hào)化為: p∧(q→r)∧(t→s)的真值為1,所以這一段的論述為真。 19.用真值表判斷下列公式的類型: (4)(p→q) →(q→p) (5)(p∧r) (p∧q) (6)((p→q) ∧(q→r)) →(p→r) 答: (4) p q p→q q p q→p (p→q)→(q→p) 0 0 1 1 1
3、 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式類型為永真式 (5)公式類型為可滿足式(方法如上例) (6)公式類型為永真式(方法如上例) 第二章部分課后習(xí)題參考答案 3.用等值
4、演算法判斷下列公式的類型,對(duì)不是重言式的可滿足式,再用真值表法求出成真賦值. (1) (p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答:(2)(p→(p∨q))∨(p→r)(p∨(p∨q))∨(p∨r)p∨p∨q∨r1 所以公式類型為永真式 (3) P q r p∨q p∧r (p∨q)→(p∧r) 0 0 0 0 0 1 0 0 1 0
5、 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1
6、 1 1 1 1 所以公式類型為可滿足式 4.用等值演算法證明下面等值式: (2)(p→q)∧(p→r)(p→(q∧r)) (4)(p∧q)∨(p∧q)(p∨q) ∧(p∧q) 證明(2)(p→q)∧(p→r) (p∨q)∧(p∨r) p∨(q∧r)) p→(q∧r) (4)(p∧q)∨(p∧q)(p∨(p∧q)) ∧(q∨(p∧q) (p∨p)∧(p∨q)∧(q∨p) ∧(q∨q) 1∧(p∨q)∧(p∧q)∧1 (p∨q)∧(p∧q) 5.求下列公式的主析取范式與主合取范式,
7、并求成真賦值 (1)(p→q)→(q∨p) (2)(p→q)∧q∧r (3)(p∨(q∧r))→(p∨q∨r) 解: (1)主析取范式 (p→q)→(qp) (pq)(qp) (pq)(qp) (pq)(qp)(qp)(pq)(pq) (pq)(pq)(pq) ∑(0,2,3) 主合取范式: (p→q)→(qp) (pq)(qp) (pq)(qp) (p(qp))(q(qp)) 1(pq) (pq) M1
8、 ∏(1) (2) 主合取范式為: (p→q)qr(pq)qr (pq)qr0 所以該式為矛盾式. 主合取范式為∏(0,1,2,3,4,5,6,7) 矛盾式的主析取范式為 0 (3)主合取范式為: (p(qr))→(pqr) (p(qr))→(pqr) (p(qr))(pqr) (p(pqr))((qr))(pqr)) 11 1 所以該式為永真式. 永真式的主合取
9、范式為 1 主析取范式為∑(0,1,2,3,4,5,6,7) 第三章部分課后習(xí)題參考答案 14. 在自然推理系統(tǒng)P中構(gòu)造下面推理的證明: (2)前提:pq,(qr),r 結(jié)論:p (4)前提:qp,qs,st,tr 結(jié)論:pq 證明:(2) ①(qr) 前提引入 ②qr ①置換 ③qr ②蘊(yùn)含等值式 ④r 前提引入 ⑤q ③④拒取式 ⑥pq 前提引入 ⑦¬p(3)
10、 ⑤⑥拒取式 證明(4): ①tr 前提引入 ②t ①化簡(jiǎn)律 ③qs 前提引入 ④st 前提引入 ⑤qt ③④等價(jià)三段論 ⑥(qt)(tq) ⑤ 置換 ⑦(qt) ⑥化簡(jiǎn) ⑧q ②⑥ 假言推理 ⑨qp 前提引入 ⑩p ⑧⑨假言推理 (11)pq ⑧⑩合取 15在自然推理系統(tǒng)P中用附加前提法證明下面各推理: (1) 前提:p(qr),sp,q 結(jié)論:sr 證明 ①s
11、 附加前提引入 ②sp 前提引入 ③p ①②假言推理 ④p(qr) 前提引入 ⑤qr ③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理 16在自然推理系統(tǒng)P中用歸謬法證明下面各推理: (1)前提:pq,rq,rs 結(jié)論:p 證明: ①p 結(jié)論的否定引入 ②p﹁q 前提引入 ③﹁q ①②假言推理 ④¬rq 前提引入 ⑤¬r ④化簡(jiǎn)律 ⑥r(nóng)¬s 前提引入 ⑦r
12、 ⑥化簡(jiǎn)律 ⑧r﹁r ⑤⑦ 合取 由于最后一步r﹁r 是矛盾式,所以推理正確. 第四章部分課后習(xí)題參考答案 3. 在一階邏輯中將下面將下面命題符號(hào)化,并分別討論個(gè)體域限制為(a),(b)條件時(shí)命題的真值: (1) 對(duì)于任意x,均有2=(x+)(x). (2) 存在x,使得x+5=9. 其中(a)個(gè)體域?yàn)樽匀粩?shù)集合. (b)個(gè)體域?yàn)閷?shí)數(shù)集合. 解: F(x): 2=(x+)(x). G(x): x+5=9. (1)在兩個(gè)個(gè)體域中都解釋為,在(a)中為假命題,在(b)中為真命題。 (2)在兩個(gè)個(gè)體域中都解釋為,在(a)(b)中均為真命題。
13、4. 在一階邏輯中將下列命題符號(hào)化: (1) 沒有不能表示成分?jǐn)?shù)的有理數(shù). (2) 在北京賣菜的人不全是外地人. 解: (1)F(x): x能表示成分?jǐn)?shù) H(x): x是有理數(shù) 命題符號(hào)化為: (2)F(x): x是北京賣菜的人 H(x): x是外地人 命題符號(hào)化為: 5. 在一階邏輯將下列命題符號(hào)化: (1) 火車都比輪船快. (3) 不存在比所有火車都快的汽車. 解: (1)F(x): x是火車; G(x): x是輪船; H(x,y): x比y快 命題符號(hào)化為: (2) (1)F(x): x是火車; G(
14、x): x是汽車; H(x,y): x比y快
命題符號(hào)化為:
9.給定解釋I如下:
(a) 個(gè)體域D為實(shí)數(shù)集合R.
(b) D中特定元素=0.
(c) 特定函數(shù)(x,y)=xy,x,y.
(d) 特定謂詞(x,y):x=y,(x,y):x 15、
(b) D中特定元素=2.
(c) D上函數(shù)=x+y,(x,y)=xy.
(d) D上謂詞(x,y):x=y.
說明下列各式在I下的含義,并討論其真值.
(1) xF(g(x,a),x)
(2) xy(F(f(x,a),y)→F(f(y,a),x)
答:(1) 對(duì)于任意自然數(shù)x, 都有2x=x, 真值0.
(2) 對(duì)于任意兩個(gè)自然數(shù)x,y,使得如果x+2=y, 那么y+2=x. 真值0.
11. 判斷下列各式的類型:
(1)
(3) yF(x,y).
解:(1)因?yàn)? 為永真式;
所以 為永真式;
(3)取解釋I個(gè)體域?yàn)槿w實(shí)數(shù)
16、F(x,y):x+y=5
所以,前件為任意實(shí)數(shù)x存在實(shí)數(shù)y使x+y=5,前件真;
后件為存在實(shí)數(shù)x對(duì)任意實(shí)數(shù)y都有x+y=5,后件假,]
此時(shí)為假命題
再取解釋I個(gè)體域?yàn)樽匀粩?shù)N,
F(x,y)::x+y=5
所以,前件為任意自然數(shù)x存在自然數(shù)y使x+y=5,前件假。此時(shí)為假命題。//錯(cuò)誤的吧
此公式為非永真式的可滿足式。
13. 給定下列各公式一個(gè)成真的解釋,一個(gè)成假的解釋。
(1) (F(x)
(2) x(F(x)G(x)H(x))
解:(1)個(gè)體域:本班同學(xué)
F(x):x會(huì)吃飯, G(x):x會(huì)睡覺.成真解釋
F(x):x是泰安人,G(x):x是濟(jì)南人.(2) 17、成假解釋
(2)個(gè)體域:泰山學(xué)院的學(xué)生
F(x):x出生在山東,G(x):x出生在北京,H(x):x出生在江蘇,成假解釋.
F(x):x會(huì)吃飯,G(x):x會(huì)睡覺,H(x):x會(huì)呼吸. 成真解釋.
第六章部分課后習(xí)題參考答案
5.確定下列命題是否為真:
(1) 真
(2) 假
(3) 真
(4) 真
(5){a,b}{a,b,c,{a,b,c}} 真
(6){a,b}{a,b,c,{a,b}} 真
(7){a,b}{ 18、a,b,{{a,b}}} 真
(8){a,b}{a,b,{{a,b}}} 假
6.設(shè)a,b,c各不相同,判斷下述等式中哪個(gè)等式為真:
(1){{a,b},c,} ={{a,b},c} 假
(2){a ,b,a}={a,b} 真
(3){{a},}={{a,b}} 假
(4){,{},a,b}={{,{}},a,b} 假
8.求下列集合的冪集:
(1){a,b,c} P(A)={ ,{a},,{c},{a,b},{a,c},{b,c},{a,b,c}}
( 19、2){1,{2,3}} P(A)={ , {1}, {{2,3}}, {1,{2,3}} }
(3){} P(A)={ , {} }
(4){,{}} P(A)={ , {1}, {{2,3}}, {1,{2,3}} }
14.化簡(jiǎn)下列集合表達(dá)式:
(1)(AB)B )-(AB)
(2)((ABC)-(BC))A
解:
(1)(AB)B )-(AB)=(AB)B )~(AB)
=(AB)~(AB))B=B=
(2)((ABC)-(BC))A=((ABC)~(BC))A
=(A~(BC))((BC )~(BC))A
=(A~(BC))A=(A~(BC 20、))A=A
18.某班有25個(gè)學(xué)生,其中14人會(huì)打籃球,12人會(huì)打排球,6人會(huì)打籃球和排球,5人會(huì)打籃球和網(wǎng)球,還有2人會(huì)打這三種球。已知6個(gè)會(huì)打網(wǎng)球的人都會(huì)打籃球或排球。求不會(huì)打球的人數(shù)。
解: 阿A={會(huì)打籃球的人},B={會(huì)打排球的人},C={會(huì)打網(wǎng)球的人}
|A|=14, |B|=12, |AB|=6,|AC|=5,| ABC|=2, |C|=6,CAB
如圖所示。
25-(5+4+2+3)-5-1=25-14-5-1=5
不會(huì)打球的人共5人
21.設(shè)集合A={{1,2},{2,3},{1,3},{}},計(jì)算下列表達(dá)式:
(1)A
(2)A
(3)A
(4) 21、A
解: (1)A={1,2}{2,3}{1,3}{}={1,2,3,}
(2)A={1,2}{2,3}{1,3}{}=
(3)A=123=
(4)A=
27、設(shè)A,B,C是任意集合,證明
(1)(A-B)-C=A- BC
(2)(A-B)-C=(A-C)-(B-C)
證明
(1) (A-B)-C=(A~B) ~C= A( ~B~C)= A~(BC) =A- BC
(2) (A-C)-(B-C)=(A~C) ~(B ~C)= (A~C) (~BC)
=(A~C~B) (A~CC)= (A~C~B)
= A~(BC) =A- BC 由(1)得證。
第七 22、章部分課后習(xí)題參考答案
7.列出集合A={2,3,4}上的恒等關(guān)系I A,全域關(guān)系EA,小于或等于關(guān)系LA,整除關(guān)系DA.
解:IA ={<2,2>,<3,3>,<4,4>}
EA={<2,2>,<2,3>,<2,4>,<3,4>,<4,4>,<3,2>,<3,3>,<4,2>,<4,3>}
LA={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>}
DA={<2,4>}
13.設(shè)A={<1,2>,<2,4>,<3,3>}
B={<1,3>,<2,4>,<4,2>}
求AB,AB, domA, domB, dom(AB), ranA, r 23、anB, ran(AB ), fld(A-B).
解:AB={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>}
AB={<2,4>}
domA={1,2,3}
domB={1,2,4}
dom(A∨B)={1,2,3,4}
ranA={2,3,4}
ranB={2,3,4}
ran(AB)={4}
A-B={<1,2>,<3,3>},fld(A-B)={1,2,3}
14.設(shè)R={<0,1><0,2>,<0,3>,<1,2>,<1,3>,<2,3>}
求RR, R-1, R{0,1,}, R[{1,2}]
解:RR={<0, 24、2>,<0,3>,<1,3>}
R-1,={<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>}
R{0,1}={<0,1>,<0,2>,<0,3>,<1,2>,<1,3>}
R[{1,2}]=ran(R|{1,2})={2,3}
16.設(shè)A={a,b,c,d},,為A上的關(guān)系,其中
=
求。
解: R1R2={,,}
R2R1={ 25、b>,}
36.設(shè)A={1,2,3,4},在AA上定義二元關(guān)系R,
, 26、
任意的, 27、
〈a,b〉R〈c,d〉a + b = c + d
(1) 證明R為等價(jià)關(guān)系.
(2) 求R導(dǎo)出的劃分.
(1)證明:R
∴R是自反的
任意的, 28、
(2)∏={{<1,1>}, {<1,2>,<2,1>}, {<1,3>,<2,2>,<3,1>}, {<1,4>,<4,1>,<2,3>,<3,2>}, {<2,4>,<4,2>,<3,3>}, {<3,4>,<4,3>}, {<4,4>}}
43. 對(duì)于下列集合與整除關(guān)系畫出哈斯圖:
(1) {1,2,3,4,6,8,12,24}
(2) {1,2,3,4,5,6,7,8,9,10,11,12}
解:
(1) (2)
45.下圖是兩個(gè)偏 29、序集的哈斯圖.分別寫出集合A和偏序關(guān)系R的集合表達(dá)式.
(a) (b)
解: (a)A={a,b,c,d,e,f,g}
R={,,,,,,,, 30、`極小元`最大元和最小元.
(1)A={a,b,c,d,e}
R={,,,,, 31、b,c,e
最大元: e 無
最小元: a 無
第八章部分課后習(xí)題參考答案
1. 設(shè)f :NN,且
f (x)=
求f (0), f ({0}), f (1), f ({1}), f ({0,2,4,6,…}),f ({4,6,8}), f -1({3,5,7}).
解:f (0)=0, f ({0})={0}, f (1)=1, f ({1})={1},
f ({0,2,4,6,…})=N,f ({4,6,8})={2,3,4}, f -1 ({ 32、3,5,7})={6,10,14}.
4. 判斷下列函數(shù)中哪些是滿射的?哪些是單射的?哪些是雙射的?
(1) f:NN, f(x)=x2+2 不是滿射,不是單射
(2) f:NN,f(x)=(x)mod 3,x除以3的余數(shù) 不是滿射,不是單射
(3) f:NN,f(x)= 不是滿射,不是單射
(4) f:N{0,1},f(x)= 是滿射,不是單射
(5) f:N-{0}R,f(x)=lgx 不是滿射,是單射
(6) f:RR,f(x)=x2-2x-15 不是滿射,不是單射
5. 設(shè)X={a 34、
解:由握手定理圖G的度數(shù)之和為:
3度與4度頂點(diǎn)各2個(gè),這4個(gè)頂點(diǎn)的度數(shù)之和為14度。
其余頂點(diǎn)的度數(shù)共有6度。
其余頂點(diǎn)的度數(shù)均小于3,欲使G的頂點(diǎn)最少,其余頂點(diǎn)的度數(shù)應(yīng)都取2,
所以,G至少有7個(gè)頂點(diǎn), 出度數(shù)列為3,3,4,4,2,2,2,.
7、設(shè)有向圖D的度數(shù)列為2,3,2,3,出度列為1,2,1,1,求D的入度列,并求,
,.
解:D的度數(shù)列為2,3,2,3,出度列為1,2,1,1,D的入度列為1,1,1,2.
,,
8、設(shè)無向圖中有6條邊,3度與5度頂點(diǎn)各1個(gè),其余頂點(diǎn)都是2度點(diǎn),問該圖有多少個(gè)頂點(diǎn)?
解:由握手定理圖G的度數(shù) 35、之和為:
設(shè)2度點(diǎn)個(gè),則,,該圖有4個(gè)頂點(diǎn).
14、下面給出的兩個(gè)正整數(shù)數(shù)列中哪個(gè)是可圖化的?對(duì)可圖化的數(shù)列,試給出3種非同構(gòu)的無向圖,其中至少有兩個(gè)時(shí)簡(jiǎn)單圖。
(1) 2,2,3,3,4,4,5 (2) 2,2,2,2,3,3,4,4
解:(1) 2+2+3+3+4+4+5=23 是奇數(shù),不可圖化;
(2) 2+2+2+2+3+3+4+4=16, 是偶數(shù),可圖化;
18、設(shè)有3個(gè)4階4條邊的無向簡(jiǎn)單圖G1、G2、G3,證明它們至少有兩個(gè)是同構(gòu)的。
證明:4階4條邊的無向簡(jiǎn)單圖的頂點(diǎn)的最大度數(shù)為3,度數(shù)之和為8,因而度數(shù)列為2,2,2,2;3,2,2 36、,1;3,3,1,1。但3,3,1,1對(duì)應(yīng)的圖不是簡(jiǎn)單圖。所以從同構(gòu)的觀點(diǎn)看,4階4條邊的無向簡(jiǎn)單圖只有兩個(gè):
所以,G1、G2、G3至少有兩個(gè)是同構(gòu)的。
20、已知n階無向簡(jiǎn)單圖G有m條邊,試求G的補(bǔ)圖的邊數(shù)。
解:
21、無向圖G如下圖
(1)求G的全部點(diǎn)割集與邊割集,指出其中的割點(diǎn)和橋;
(2) 求G的點(diǎn)連通度與邊連通度。
解:點(diǎn)割集: {a,b},(d)
邊割集{e2,e3},{e3,e4},{e1,e2},{e1,e4}{e1,e3},{e2,e4},{e5}
==1
23、求G的點(diǎn)連通度、邊連通度與最小度數(shù)。
解:、 、
28、設(shè)n階無向簡(jiǎn)單圖為 37、3-正則圖,且邊數(shù)m與n滿足2n-3=m問這樣的無向圖有幾種非同構(gòu)的情況?
解: 得n=6,m=9.
31、設(shè)圖G和它的部圖的邊數(shù)分別為和,試確定G的階數(shù)。
解: 得
45、有向圖D如圖
(1)求到長(zhǎng)度為1,2,3,4的通路數(shù);
(2)求到長(zhǎng)度為1,2,3,4的回路數(shù);
(3)求D中長(zhǎng)度為4的通路數(shù);
(4)求D中長(zhǎng)度小于或等于4的回路數(shù);
(5)寫出D的可達(dá)矩陣。
解:有向圖D的鄰接矩陣為:
,
(1)到長(zhǎng)度為1,2,3,4的通路數(shù)為0,2,0,0;
(2)到長(zhǎng)度為1,2,3,4的回路數(shù)為0,0,4,0;
(3)D中長(zhǎng)度為4的通路數(shù)為 38、32;
(4)D中長(zhǎng)度小于或等于4的回路數(shù)10;
(4)出D的可達(dá)矩陣
第十六章部分課后習(xí)題參考答案
1、畫出所有5階和7階非同構(gòu)的無向樹.
2、一棵無向樹T有5片樹葉,3個(gè)2度分支點(diǎn),其余的分支點(diǎn)都是3度頂點(diǎn),問T有幾個(gè)頂點(diǎn)?
解:設(shè)3度分支點(diǎn)個(gè),則
,解得
T有11個(gè)頂點(diǎn)
3、無向樹T有8個(gè)樹葉,2個(gè)3度分支點(diǎn),其余的分支點(diǎn)都是4度頂點(diǎn),問T有幾個(gè)4度分支點(diǎn)?根據(jù)T的度數(shù)列,請(qǐng)至少畫出4棵非同構(gòu)的無向樹。
解:設(shè)4度分支點(diǎn)個(gè),則
,解得
度數(shù)列111111113344
4、棵無向樹T有 (i=2,3,…,k)個(gè)i度分支點(diǎn),其余頂點(diǎn)都 39、是樹葉,問T應(yīng)該有幾片樹葉?
解:設(shè)樹葉片,則
,解得
評(píng)論:2,3,4題都是用了兩個(gè)結(jié)論,一是握手定理,二是
5、n(n≥3)階無向樹T的最大度至少為幾?最多為幾?
解:2,n-1
6、若n(n≥3)階無向樹T的最大度 =2,問T中最長(zhǎng)的路徑長(zhǎng)度為幾?
解:n-1
7、證明:n(n≥2) 階無向樹不是歐拉圖.
證明:無向樹沒有回路,因而不是歐拉圖。
8、證明:n(n≥2) 階無向樹不是哈密頓圖.
證明:無向樹沒有回路,因而不是哈密頓圖。
9、證明:任何無向樹T都是二部圖.
證明:無向樹沒有回路,因而不存在技術(shù)長(zhǎng)度的圈,是二部圖。
10、什么樣的無向樹T既 40、是歐拉圖,又是哈密頓圖?
解:一階無向樹
14、設(shè)e為無向連通圖G中的一條邊, e在G的任何生成樹中,問e應(yīng)有什么性質(zhì)?
解:e是橋
15、設(shè)e為無向連通圖G中的一條邊, e不在G的任何生成樹中, 問e應(yīng)有什么性質(zhì)?
解:e是環(huán)
23、已知n階m條的無向圖 G是k(k≥2)棵樹組成的森林,證明:m = n-k.;
證明:數(shù)學(xué)歸納法。k=1時(shí), m = n-1,結(jié)論成立;
設(shè)k=t-1(t-1)時(shí),結(jié)論成立,當(dāng)k=t時(shí), 無向圖 G是t棵樹組成的森林,任取兩棵樹,每棵樹任取一個(gè)頂點(diǎn),這兩個(gè)頂點(diǎn)連線。則所得新圖有t-1棵樹,所以m = n- 41、(k-1).
所以原圖中m = n-k
得證。
24、在圖16.6所示2圖中,實(shí)邊所示的生成子圖T是該圖的生成樹.
(1)指出T的弦,及每條弦對(duì)應(yīng)的基本回路和對(duì)應(yīng)T的基本回路系統(tǒng).
(2) 指出T的所有樹枝, 及每條樹枝對(duì)應(yīng)的基本割集和對(duì)應(yīng)T的基本割集系統(tǒng).
(a) (b)
圖16.16
解:(a)T的弦:c,d,g,h
T的基本回路系統(tǒng): S={{a,c,b},{a,b,f,d},{e,a,b,h},{e,a 42、,b,f,g}}
T的所有樹枝: e,a,b,f
T的基本割集系統(tǒng): S={{e,g,h},{a,c,d,g,h},{b,c,d,g,h},{f,d,g}}
(b)有關(guān)問題仿照給出
25、求圖16.17所示帶權(quán)圖中的最小生成樹.
(a) (b)
圖16.17
解:
注:答案不唯一。
37、畫一棵權(quán)為3,4,5,6,7,8,9的最優(yōu)2叉樹,并計(jì)算出它的權(quán).
38.下面給出的各符號(hào)串集合哪些是前綴碼?
A1={0,10,110,1111} 是前綴碼
A2={1,01,001 43、,000} 是前綴碼
A3={1,11,101,001,0011} 不是前綴碼
A4={b,c,aa,ac,aba,abb,abc} 是前綴碼
A5={ b,c,a,aa,ac,abc,abb,aba} 不是前綴碼
41.設(shè)7個(gè)字母在通信中出現(xiàn)的頻率如下:
a: 35% b: 20%
c: 15% d: 10%
e: 10% f: 5%
g: 5%
用Huffman算法求傳輸它們的前綴碼.要求畫出最優(yōu)樹,指出每個(gè)字母對(duì)應(yīng)的編碼.并指出傳輸10n(n≥2)個(gè)按上述頻率出現(xiàn)的字母,需要多少個(gè)二進(jìn)制數(shù)字.
解:
a:01 b:10 c:000 d:110 e:001 f:1111 g:1110
W(T)=5*4+5*4+10*3+10*3+15*3+20*2+35*2=255
傳輸10n(n≥2)個(gè)按上述頻率出現(xiàn)的字母,需要255*10n-2個(gè)二進(jìn)制數(shù)字.
.
- 溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 建筑施工重大危險(xiǎn)源安全管理制度
- 安全培訓(xùn)資料:典型建筑火災(zāi)的防治基本原則與救援技術(shù)
- 企業(yè)雙重預(yù)防體系應(yīng)知應(yīng)會(huì)知識(shí)問答
- 8 各種煤礦安全考試試題
- 9 危險(xiǎn)化學(xué)品經(jīng)營(yíng)單位安全生產(chǎn)管理人員模擬考試題庫試卷附答案
- 加壓過濾機(jī)司機(jī)技術(shù)操作規(guī)程
- 樹脂砂混砂工藝知識(shí)總結(jié)
- XXXXX現(xiàn)場(chǎng)安全應(yīng)急處置預(yù)案
- 某公司消防安全檢查制度總結(jié)
- 1 煤礦安全檢查工(中級(jí))職業(yè)技能理論知識(shí)考核試題含答案
- 4.燃?xì)獍踩a(chǎn)企業(yè)主要負(fù)責(zé)人模擬考試題庫試卷含答案
- 工段(班組)級(jí)安全檢查表
- D 氯化工藝作業(yè)模擬考試題庫試卷含答案-4
- 建筑起重司索信號(hào)工安全操作要點(diǎn)
- 實(shí)驗(yàn)室計(jì)量常見的30個(gè)問問答題含解析