數(shù)據(jù)結(jié)構(gòu)作業(yè)(1)

1、第3章作業(yè)作業(yè)3.83.8根據(jù)大根據(jù)大O和Ω的定義，寫出下列表達(dá)式的上限和下限。注意確定適當(dāng)?shù)牡亩x，寫出下列表達(dá)式的上限和下限。注意確定適當(dāng)?shù)腸和n0:(a)cn1c=c1n0=1時，c1n在O(n)中。c=c1n0=1時，c1n在Ω(n)中。(b)c2n3c3對于n1c2n3c3≤c2n3c3n3≤(c2c3)n3T(n)在O(n3)中，c=c2c3，n0=1。對于n1c2n3c3≥c2n3T(n)在Ω(n3)中，c=c2，n0=1

2、。(c)c4nlognc5n對于n2c4nlognc5n≤c4nlognc5nlogn≤(c4c5)nlognT(n)在O(nlogn)中，c=c4c5n0=2。對于n2c4nlognc5n≥c4nc5n≥(c4c5)nT(n)在Ω(n)中，c=c4c5n0=2。(d)c62nc7n6對于n1c62nc7n6≤c6n6c7n6≤(c6c7)n6T(n)在O(n6)中，c=c6c7n0=1。對于n1c62nc7n6≥c62nc72n≥(c

3、6c7)2nT(n)在Ω(2n)中，c=c6c7n0=1。3.93.9對于下列各組函數(shù)式對于下列各組函數(shù)式f(n)f(n)與g(n)g(n)的關(guān)系為：或者的關(guān)系為：或者f(n)f(n)在O(g(n))O(g(n))中，或者中，或者f(n)f(n)在Ω(g(n))Ω(g(n))中，或者中，或者f(n)=Θ(g(n))f(n)=Θ(g(n))。對于每一組函數(shù)，確定兩個函數(shù)究。對于每一組函數(shù)，確定兩個函數(shù)究竟是哪種關(guān)系，并簡述理由。竟是哪種關(guān)

4、系，并簡述理由。(a)f(n)=logn2g(n)=logn5f(n)=2lognn32時，2logn≥logn5c=1n0=32f(n)在Ω(g(n))中。(b)f(n)=g(n)=logn2nn2時，≤logn2c=1n0=2f(n)在O(g(n))中。n(c)f(n)=log2ng(n)=lognn2時，log2n≥logn，c=1n0=2，f(n)在Ω(g(n))中。(d)f(n)=ng(n)=log2n”中的圓括號不匹配。中的

5、圓括號不匹配。(a)(a)給出一個算法，當(dāng)字符串中的圓括號恰好平衡且匹配時返回給出一個算法，當(dāng)字符串中的圓括號恰好平衡且匹配時返回truetrue，否則，否則返回返回falsefalse。用一個棧來記錄當(dāng)前掃描到的未匹配的左圓括號。提示：從左到。用一個棧來記錄當(dāng)前掃描到的未匹配的左圓括號。提示：從左到右掃描一個合法的字符串，保證任何時候所遇到的右圓括號不會比左圓括號多。右掃描一個合法的字符串，保證任何時候所遇到的右圓括號不會比左圓括號多

6、。boolbalance(Stringstr)StackSintpos=0while(str.At(pos)!=NULL)if(str.At(pos)==’(’)S.push(’(’)elseif(str.At(pos)==’)’)if(S.isEmpty())returnFALSEelseS.pop()if(S.isEmpty())returnTRUEelsereturnFALSE(3)(3)試寫一算法，實現(xiàn)單鏈表的就地逆置，即利用原