发布时间 : 星期一 文章数据结构作业(1)更新完毕开始阅读21f4042c27d3240c8447efce
第三章作业
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,c62+c7n≤c6n+c7n≤(c6+c7)n,T(n)在O(n)中，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
6
6
6
6
6
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
n
2≤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。用一个栈来记录当前扫描到的未匹配的左圆括号。提示：从左到右扫描一个合法的字符串，保证任何时候所遇到的右圆括号不会比左圆括号多。
bool balance(String str) { Stack S; int pos=0;
while(str.charAt(pos)!=NULL) { if(str.charAt(pos++)==’(’) S.push(’(’);
else if(str.charAt(pos++)==’)’) if(S.isEmpty()) return FALSE; else S.pop(); }
if (S.isEmpty()) return TRUE; else return FALSE; }
(3)试写一算法，实现单链表的就地逆置，即利用原表的存储空间将线性表(a0, a1, ?, an-1)逆置为(an-1, an-2, ?, a0)。
void inverse(LinkList &L) { p=L->next; L->next=NULL; while ( p)
{ succ=p->next; p->next=L->next; L->next=p; p = succ; }
}
(4)已知有一个单向循环链表，其每个结点中含3个域：prev、data和next。其中data为数据域，next为指向后继结点的指针域，prev也为指针域，但它的值为空(NULL), 试编写算法将此单向循环链表改为双向循环链表，即使prev成为指向前驱结点的指针域。
Node* list(Node* head) { node *p,*q; p=head; q=NULL; while(p!=NULL) { p->prior=q; q=p;
p=p->next; } return q; }
(5)假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写相应的队列初始化、入队列和出队列的算法。
Status InitCLQueue(CLQueue &rear)
{ CLQueue q = (CLQueue )malloc(sizeof(struct list)); rear = q;
rear->next = rear->pre = rear; return true; }
Status EnCLQueue(CLQueue &rear, ElemType x)
{ CLQueue q = (CLQueue)malloc(sizeof(struct list)); q->data = x;
if(rear->next == rear)