数据结构作业(1).doc

第3章 作业3.8 根据大O和的定义，写出下列表达式的上限和下限。注意确定适当的c和n0:(a)cn c=c1,n0=1时，c1n在O(n)中。 c=c1,n0=1时，c1n在(n)中。(b)c2n3+c3 对于n1,c2n3+c3c2n3+c3n3(c2+c3)n3,T(n)在O(n3)中，c=c2+c3，n0=1。 对于n1,c2n3+c3c2n3,T(n)在(n3)中，c=c2，n0=1。(c)c4nlogn+c5n 对于n2,c4nlogn+c5nc4nlogn+c5nlogn(c4+c5)nlogn,T(n)在O(nlogn)中，c=c4+c5,n0=2。 对于n2,c4nlogn+c5nc4n+c5n(c4+c5)n,T(n)在(n)中，c=c4+c5,n0=2。(d)c62n+c7n6 对于n1,c62n+c7n6c6n6+c7n6(c6+c7)n6,T(n)在O(n6)中，c=c6+c7,n0=1。 对于n1,c62n+c7n6c62n+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,n32时，2lognlogn+5,c=1,n0=32,f(n)在(g(n)中。(b)f(n)=;g(n)=logn2 n2时，logn2,c=1,n0=2,f(n)在O(g(n)中。(c)f(n)=log2n;g(n)=logn n2时，log2nlogn，c=1,n0=2，f(n)在(g(n)中。(d)f(n)=n;g(n)=log2n n16时，nlog2n，c=1,n0=16，f(n)在(g(n)中。(e)f(n)=nlogn+n;g(n)=logn nlogn+nlogn，f(n)在(g(n)中。(f)f(n)=10;g(n)=log10 10和log10都是常量，f(n)在(g(n)中。(g)f(n)=2n;g(n)=10n2 n9时，2n10n2,c=1,n0=9,f(n)在(g(n)中。(h)f(n)=2n;g(n)=3n 2n3n,f(n)在O(g(n)中。第4章 作业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) rear-next = rear-pre =q; q-next = q-pre = rear; rear = q; else q-pre = rear-next; q-next = rear-next-next; rear-next-next-pre = q; rear-next-next = q; return true;Status DeCLQueue(CLQueue &rear, ElemType &x) if(rear-next = rear) return false; rear = rear-pre; CLQueue q = rear-next; q-next-pre = rear; rear-next = q-next; free(q); return true;(6)假设将循环队列定义为: 以域变量front和length分别指示循环队列中队首元素的位置和内含元素的个数, 试写出队列初始化、入队列和出队列的算法。SeQueue QueueInit(SeQueue cq) 队列初始化 cq.rear=0; cq.length=0; return cq; SeQueue QueueIn(SeQueue cq，ElemType x) 元素x入队 if(cq.length=m) return(0); 队满 else cq.rear=(cq.rear+1) % m; 计算插入元素位置 cq.Qcq.rear=x; 将元素x入队列 cq.length+; 修改队列长度 return (cq);ElemType Q