数据结构作业VIP专享VIP免费

第三章作业 3.8 根据大O和Ω 的定义，写出下列表达式的上限和下限。注意确定适当的c和n0: (a)c1n c=c1,n0=1时，c1n在O(n)中。 c=c1,n0=1时，c1n在Ω (n)中。 (b)c2n3+c3 对于n>1,c2n3+c3≤c2n3+c3n3≤(c2+c3)n3,T(n)在O(n3)中，c=c2+c3，n0=1。 对于n>1,c2n3+c3≥c2n3,T(n)在Ω (n3)中，c=c2，n0=1。 (c)c4nlogn+c5n 对于n>2,c4nlogn+c5n≤c4nlogn+c5nlogn≤(c4+c5)nlogn,T(n)在O(nlogn)中，c=c4+c5,n0=2。 对于n>2,c4nlogn+c5n≥c4n+c5n≥(c4+c5)n,T(n)在Ω (n)中，c=c4+c5,n0=2。 (d)c62n+c7n6 对于n>1,c62n+c7n6≤c6n6+c7n6≤(c6+c7)n6,T(n)在O(n6)中，c=c6+c7,n0=1。 对于n>1,c62n+c7n6≥c62n+c72n≥(c6+c7)2n,T(n)在Ω (2n)中，c=c6+c7,n0=1。 3.9 对于下列各组函数式f(n)与 g(n)的关系为：或者 f(n)在O(g(n))中，或者f(n)在Ω (g(n))中，或者 f(n)=Θ (g(n))。对于每一组函数，确定两个函数究竟是哪种关系，并简述理由。 (a)f(n)=logn2;g(n)=logn+5 f(n)=2logn,n>32时，2logn≥logn+5,c=1,n0=32,f(n)在Ω (g(n))中。 (b)f(n)=n ;g(n)=logn2 n>2时，n ≤logn2,c=1,n0=2,f(n)在O(g(n))中。 (c)f(n)=log2n;g(n)=logn n>2时，log2n≥logn，c=1,n0=2，f(n)在Ω (g(n))中。 (d)f(n)=n;g(n)=log2n n>16时，n≥log2n，c=1,n0=16，f(n)在Ω (g(n))中。 (e)f(n)=nlogn+n;g(n)=logn nlogn+n≥logn，f(n)在Ω (g(n))中。 (f)f(n)=10;g(n)=log10 10和log10都是常量，f(n)在Θ (g(n))中。 (g)f(n)=2n;g(n)=10n2 n>9时，2n≥10n2,c=1,n0=9,f(n)在Ω (g(n))中。 (h)f(n)=2n;g(n)=3n 2n≤3n,f(n)在O(g(n))中。 第四章作业 4.18 已知Q是一个非空队列，S是一个空栈。仅用栈和队列的ADT函数和一个成员变量X编写一个算法，使得Q中的元素倒置。 void reverse(Queue& Q, Stack& S) { ELEM X; while(!Q.isEmpty()) { X=Q.dequeue(); S.push(X); } while(!S.isEmpty()) { X=S.pop(); Q.enqueue(X); }} 4.20 编译器和文本编辑器的一个存在的普遍问题时判断一个字符串中的圆括号（或者其他括号）是否平衡且匹配。例如，字符串“（（（））（））（）”中的圆括号恰好平衡且匹配，但是字符串“）（）（”中的圆括号不平衡，字符串“（））”中的圆括号不匹配。 (a)给出一个算法，当字符串中的圆括号恰好平衡且匹配时返回true，否则返回false。用一个栈来记录当前扫描到的未匹配的左圆括号。提...