數(shù)據(jù)結(jié)構(gòu)作業(yè)03第三次習(xí)題課矩陣chapter

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

2、組ba（a代表數(shù)組的前p個元素，b代表數(shù)組中余下的n-p個元素）。先將a逆置得到a-1b， 再將b逆置得到a-1b-1，最后將整個a-1b-1逆置得到（a-1b-1）-1=ba。²或先逆置ab，得到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

3、;³for(i = 0; i < (to-from+1)/2; i+)³® temp = Rfrom+i; Rfrom+i = Rto-i; Rto-i = temp; ³²時間復(fù)雜度：O(n)²空間復(fù)雜度：O(1)另法²算法思想：創(chuàng)建大小為p的輔助數(shù)組S，將R中前p個整數(shù)依次暫S中，同時將R中后n-p個整數(shù)左移，然后將S中暫存的p個數(shù)依次放回到R中的后續(xù)單元。²²時間復(fù)雜度：O(n)²空間復(fù)雜度：O(p)²數(shù)組與矩陣²設(shè)有一個n*n的對稱矩陣A，如下圖(a)所示。為了

4、節(jié)約，可以只存對角線及對角線以上的元素，或者只存對角線或?qū)蔷€以下的元素。前者稱為上三角矩陣，后者稱為下三角矩陣。我們把它們按行存放于一個一維數(shù)組B中，如圖(b)和圖(c)所示。并稱之為對稱矩陣A的壓縮方式。試問：²1）存放對稱矩陣A上三角部分或下三角部分的一維數(shù)組B有多少元素？²1+2+n=n(n+1)/2先來看第(3)問²3）若在一維數(shù)組B中從0號位置開始存放， 則如圖(a)所示的對稱矩陣中的任一元素aij 在只存下三角部分的情況下*(圖(c)應(yīng)存于一維數(shù)組的什么下標(biāo)位置？給出計算公式。²前i-1行:1+2+(i-1)=i(i-1)/2²第

5、i行:j²下標(biāo):i(i-1)/2+j-1a11a21 a22an1 an2 ann(c)²2）若在一維數(shù)組B中從0號位置開始存放， 則如圖(a)所示的對稱矩陣中的任一元素aij 在只存上三角部分的情形下(圖(b)應(yīng)存于一維數(shù)組的什么下標(biāo)位置？給出計算公式。²直接交換第(3)問的i與j²下標(biāo):j(j-1)/2+i-12009年統(tǒng)考題 3²給定二如下圖所示. 設(shè)N 代表二的根, L 代表二的左子樹, R 代表根結(jié)點的右子樹. 若遍歷后的結(jié)點序列為 3, 1, 7, 5, 6,2, 4, 則其遍歷方式是(右3中1)A. LRNB.NRLC.RLND.

6、RNL²2009年統(tǒng)考題 4²已知一棵完全二的第6 層(為第1層)有8個葉結(jié)點, 則該完全二最多是的結(jié)點個數(shù)A.39B.52C.111D.119²level 1 20level 2 2124level 6 2582625 1 + 8 2 = 11124*22009年統(tǒng)考題 5²將森林轉(zhuǎn)換為對應(yīng)的二, 若在二中, 結(jié)點u是結(jié)點v的父結(jié)點的父結(jié)點, 則在原來的森林中, u 和v 可能具有的³1)父子³2)兄弟是：³3) u 的父結(jié)點與v 的父結(jié)點是兄弟²A. 2)B. 1)和2)C. 1)和3)D. 1), 2)和3)

7、3122010年全國考研題 3²下列線索二中（用虛線表示線索），符合后序線索樹定義的是（D）PostOrder：dbca5²在一棵度為4的樹T中，若有20個度為4的結(jié)點，10個度為3的結(jié)點，1個度為2的結(jié)點， 10個度為1的結(jié)點，則樹T的葉節(jié)點個數(shù)是：²A：41B：82C：113D：122節(jié)點數(shù)=+ 120 + 10 +1 +10 + n = 20*4 + 10*3 + 1*2 + 10*1 + 1n=826²對n(n大于等于2)個不相同的字符構(gòu)成是（）樹，關(guān)于該樹的敘述中，錯誤的³ A：該樹一定是一棵完全二³ B：³ C：

8、一定沒有度為1的結(jié)點兩個最小的結(jié)點一定是兄弟結(jié)點³ D：任一非葉結(jié)點的一定不小于下一層任一結(jié)點的1.給出如下各表的二一：中綴表后綴表二²²編程時使用二：根據(jù)計算的順序?qū)懗龆?#178;²做題時使用(a+b)/(c-d*e)+e+g*h/a+/e*agh+-abc*de-x-y*z+(a+b+c/d*e)+-+-*+*xyzab/ex是-的右節(jié)點，可以按0-x來理解cd(a+b)>(c-d)|a<f&&(x<y|y>z)|>&&+-<|><abcdafxyyz&&

9、;的優(yōu)先級比|高2. 如果一棵樹有n1個度為1的結(jié)點，有n2個度為2的結(jié)點，nm個度為m的結(jié)點， 試問有多少個度為0的結(jié)點？寫出推導(dǎo)過程。節(jié)點數(shù) =+ 1𝑛0 + 𝑛1 + 𝑛2 + 𝑛3 + + 𝑛𝑚 = 𝑛1 + 2𝑛2 + 3𝑛3 + + 𝑚𝑛𝑚 + 1𝑛0 = 𝑛2 + 2𝑛3 + 3𝑛4 + +𝑚 1 ⻕

10、9;𝑚 + 13.分別找出滿足以下條件的所有二²1）二的前序序列與中序序列相同NLR=LNRSo：所有節(jié)點都沒有左節(jié)點、只有根節(jié)點、空樹²2）二的中序序列與后序序列相同LNR=LRNSo：所有節(jié)點都沒點、只有根節(jié)點、空樹²3）二的前序序列與后序序列相同NLR=LRNSo：只有根節(jié)點、空樹4.若用二叉鏈表作為二的表示，試對以下問題編寫遞歸算法。²1）統(tǒng)計二中葉結(jié)點的個數(shù)。publicifstatic int leafNum(BinaryNode root) (root = null)return 0;(root.left = null &a

11、mp;& root.right = null)return 1;ifreturn leafNum(root.left) + leafNum(root.right);²2）以二子女為參數(shù)，交換每個結(jié)點的和右publicifstaticvoidswitchLR(BinaryNoderoot)(root=null)return;BinaryNodetmp=root.left;root.left=root.right;root.right=tmp;switchLR(root.left);switchLR(root.right);5.已知先序ABECDFGHIJ，中序EBCDAFHIG

12、J，試畫出二。ABECDFGHIJEBCDAFHIGJABECDEBCDFGHIJFHIGJBFEECDCDGHIJHIGJECGDDHIHIJJDHJIII6.編寫一個Java函數(shù)，輸入后綴表，構(gòu)造其二表示。設(shè)每個操作符有一個或兩個操作數(shù)。l 遍歷表ü 若為操作數(shù)，將其構(gòu)造成節(jié)點棧；ü 若為一元操作符，彈出一個節(jié)點作為操作符的右child構(gòu)造新節(jié)點，將新節(jié)點入棧；ü 若為二元操作數(shù)，彈出兩個節(jié)點分別作為操作符的右左child構(gòu)造新的節(jié)點，將新節(jié)點入棧。public static BinaryNode makeTreeFromPostfixExpression(S

13、tring expression) Stack stack = new Stack ();expression = expression.replaceAll(" ", ""); for (int i = 0; i < expression.length(); +i) char ch = expression.charAt(i);switch (ch) case '+': case '-': case '*': case '/': case '':BinaryNode

14、right = (BinaryNode) stack.pop();²²²²²²²²BinaryNeft = (BinaryNode) stack.pop();²stack.push(new BinaryNode(ch, left, right);break;²²case '':²BinaryNode node = (BinaryNode) stack.pop();stack.push(new BinaryNode(ch, null, node);break;&

15、#178;²²default:²stack.push(new BinaryNode(ch, null, null);break;²²²return (BinaryNode) stack.pop();²²²7.給定15,03,14,02,06,09,16,17,構(gòu)造相應(yīng)的霍樹，并計算它的帶路徑長度。3 6 92 + 3 -> 514 15 16 175 + 6 -> 119 11 14 15 16 17162014 15 16 17 20911141516 17 20 295620 29 333

16、3 4923帶路徑長度：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這八個字母的出現(xiàn)頻率分別5,25,3,6,10,11,36,4為這八個字母設(shè)計不等長的Huffman編碼,并給出該電文的總碼數(shù)。3 4 5 6 10 11 25 36100015 6 7 10 11 25 363961010251367 10 11 11 25 36172211 11 17 25 3601011105