第3次習(xí)題課矩陣chapter4

1、習(xí)題講解3張?jiān)?張仁濤 Chapter3.1 2010年全國(guó)考研統(tǒng)考題設(shè)將n(n,1)個(gè)整數(shù)存放到一維數(shù)組R中，試設(shè)計(jì)一個(gè)在時(shí)間和空間兩方面盡可能有效的算法， 將R中保有的序列循環(huán)左移P（0Pn）個(gè)位 置，即將R中的數(shù)據(jù)由（X0 X1 Xn-1）變換為（Xp Xp+1 Xn-1X0X1 Xp-1)（1） 給出算法的基本設(shè)計(jì)思想。（2） 根據(jù)設(shè)計(jì)思想，采用C或C+或JAVA語(yǔ)言表述算法，關(guān)鍵之處給出注釋。（3） 說明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度設(shè)計(jì)思想可以將這個(gè)問題看做是把數(shù)組

2、ab轉(zhuǎn)換成數(shù)組ba（a代表數(shù)組的前p個(gè)元素，b代表數(shù)組中余下的n-p個(gè)元素）。先將a逆置得到a-1b， 再將b逆置得到a-1b-1，最后將整個(gè)a-1b-1逆置得到（a-1b-1）-1=ba?；蛳饶嬷胊b，得到b-1a-1，再分別逆置b-1和a-1，得到ba。void Converse(int R,int n,int p)Reverse(R,0,p-1);Reverse(R,p,n-1);Reverse(R,0,n-1);void Reverse(int R,int from,int to) int i,temp;for(i = 0; i (c-d)|af&(xz)|&的優(yōu)先級(jí)比|高&+-abc

3、dafxyyz2. 如果一棵樹有n1個(gè)度為1的結(jié)點(diǎn)，有n2個(gè)度為2的結(jié)點(diǎn)，nm個(gè)度為m的結(jié)點(diǎn)，試問有多少個(gè)度為0的結(jié)點(diǎn)？寫出推導(dǎo)過程。節(jié)點(diǎn)數(shù)= 邊數(shù)+ 10 + 1 + 2 + 3 + + = 1 + 22 + 33 + + + 10 = 2 + 23 + 34 + + 1 + 13.分別找出滿足以下條件的所有二叉樹1）二叉樹的前序序列與中序序列相同NLR=LNRSo：所有節(jié)點(diǎn)都沒有左節(jié)點(diǎn)、只有根節(jié)點(diǎn)、空樹2）二叉樹的中序序列與后序序列相同LNR=LRNSo：所有節(jié)點(diǎn)都沒有右節(jié)點(diǎn)、只有根節(jié)點(diǎn)、空樹3）二叉樹的前序序列與后序序列相同NLR=LRNSo：只有根節(jié)點(diǎn)、空樹4.若用二叉鏈表作為二叉樹的

4、存儲(chǔ)表示，試對(duì)以下問題編寫遞歸算法。1）統(tǒng)計(jì)二叉樹中葉結(jié)點(diǎn)的個(gè)數(shù)。public static int leafNum(BinaryNode root) if (root = null) return 0;if (root.left = null & root.right = null) return 1;return leafNum(root.left) + leafNum(root.right);2）以二叉樹為參數(shù)，交換每個(gè)結(jié)點(diǎn)的左子女和右子女public static void switchLR(BinaryNode root) if (root = null) return;Binary

5、Node tmp = root.left; root.left = root.right; root.right = tmp; switchLR(root.left); switchLR(root.right);5.已知先序ABECDFGHIJ，中序EBCDAFHIGJ，試畫出二叉樹。ABECDFGHIJEBCDAFHIGJABECDEBCDFGHIJFHIGJBFEECDCDGHIJHIGJECGDDHIHIJJDHJIII6.編寫一個(gè)Java函數(shù)，輸入后綴表達(dá)式，構(gòu)造其二叉樹表示。設(shè)每個(gè)操作符有一個(gè)或兩個(gè)操作數(shù)。 遍歷表達(dá)式 若為操作數(shù)，將其構(gòu)造成節(jié)點(diǎn)棧； 若為一元操作符，彈出一個(gè)節(jié)點(diǎn)作為

6、操作符的右child構(gòu)造新節(jié)點(diǎn)，將新節(jié)點(diǎn)入棧； 若為二元操作數(shù)，彈出兩個(gè)節(jié)點(diǎn)分別作為操作符的右左child構(gòu)造新的節(jié)點(diǎn)，將新節(jié)點(diǎn)入棧。public static BinaryNode makeTreeFromPostfixExpression(String expression) Stack stack = new Stack ();expression = expression.replaceAll( , ); for (int i = 0; i 55 6 9 14 15 16 1733495 + 6 - 119 11 14 15 16 171617292014 15 16 17 20911

7、141516 17 20 295620 29 3333 4923帶權(quán)外路徑長(zhǎng)度：2 * 5 + 3 * 5 + 6 * 4 + 9 * 3 + 14 * 3 + 15 * 3 + 16 * 2 + 17 * 2 = 22920 + 29 - 4916 + 17 - 3314 + 15 - 299 + 11 - 208.c1,c2,c3,c4,c5,c6,c7,c8這八個(gè)字母的出現(xiàn)頻率分別5,25,3,6,10,11,36,4為這八個(gè)字母設(shè)計(jì)不等長(zhǎng)的Huffman編碼,并給出該電文的總碼數(shù)。3 4 5 6 10 11 25 36100015 6 7 10 11 25 36396101025c2136c77 10 11 11 25 36172211 11 17 25 3601011105c111 + 11 - 2217 22 25 36710c511c617 + 22 - 3925 36 3914c816c403c325+ 36- 6139 61c1:0110c2:10c3:0010c4:0111c5: