时间复杂度_线性表_答案

1、1. 分析下面算法（程序段），该算法的时间复杂度是 O( n3) 。s=0;for (i=0;in;i+) for (j=0;jn;j+) for (k=0;kn;k+) s=s+Bijk;sum=s;2. 分析下面算法（程序段）该算法的时间复杂度是O(n) 。i=s=0;while (sn) i+; s+=i; /s=s+i 注：f(n)=(1+n)n/2 ; f(n)N最大语句频度为n 3. 分析下面算法（程序段），该算法的时间复杂度是O(logn)。i=1;while (i=n) i=i*2;注：2nnext=s;s-next=p-next; B s-next=p-next;p-next

2、=s;Cp-next=s;p-next=s-next; D p-next=s-next;p-next=s;6. 在双向链表指针p的结点前插入一个指针q的结点操作是（ C ）。A. p-Llink=q;q-Rlink=p;p-Llink-Rlink=q;q-Llink=q；B. p-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink;C. q-Rlink=p;q-Llink=p-Llink;p-Llink-Rlink=q;p-Llink=q;D. q-Llink=p-Llink;q-Rlink=q;p-Llink=q;p-Llink=q;基本知识时

3、间复杂度单链表1、 是否带头2、 头插法、尾插法3、 长度、查找、插入、删除、合并、排序4、 应用：表达式相加#include #include typedef struct Polynodeint coef;int exp;struct Polynode *next;Polynode,*Polylist;Polylist polycreate()Polynode *head,*rear,*s;int c,e;head=(Polynode*)malloc(sizeof(Polynode);rear=head;scanf(%d%d,&c,&e);while(c!=0)s=(Polynode*)m

4、alloc(sizeof(Polynode);s-coef=c;s-exp=e;rear-next=s;rear=s;scanf(%d%d,&c,&e);rear-next=NULL;return(head);void printL(Polylist L)Polynode *p;p=L-next;while(p!=NULL)printf(%d %dn,p-coef,p-exp);p=p-next;printf(n);void polyadd(Polylist polya,Polylist polyb)Polynode *p,*q,*tail,*temp;int sum;p=polya-next

5、;q=polyb-next;tail=polya;while(p!=NULL&q!=NULL)if(p-expexp)tail-next=p;tail=p;p=p-next;else if(p-exp=q-exp)sum=p-coef+q-coef;if(sum!=0)p-coef=sum;tail-next=p;tail=p;p=p-next;temp=q;q=q-next;free(temp);elsetemp=p;p=p-next;free(temp);temp=q;q=q-next;free(temp);elsetail-next=q;tail=q;q=q-next;if(p!=NUL

6、L)tail-next=p;elsetail-next=q;void main()Polylist polya;Polylist polyb;printf(请输入多项式A：n);polya=polycreate();printf(请输入多项式B：n);polyb=polycreate();printf(多项式A：n);printL(polya);printf(多项式B：n);printL(polyb);polyadd(polya,polyb);printL(polya);循环链表双向链表编程题1、 单链表原地逆序。LinkList * Routine(LinkList *head)LinkLi

7、st *pre=NULL,*cur=head;While(cur)LinkList *next=cur-next;cur-next=pre;pre=cur;cur=next;return pre;LinkList *reverse(LinkList *p, LinkList *&head) if(p = NULL | p-next = NULL) head = p; return p; else LinkList *temp = reverse(p-next, head); temp-next = p; return p; #include #include typedef char Elem

8、Type;typedef struct NodeElemType data;struct Node *next;Node,*LinkList;void InitLinkList(LinkList *L)*L=(Node*)malloc(sizeof(Node);(*L)-next=NULL;void CreatFromHead(LinkList L)Node *s;char c;int flag=1;while(flag)scanf(%c,&c);if(c=#)flag=0;elses=(Node*)malloc(sizeof(Node);s-data=c;s-next=L-next;L-ne

9、xt=s;void printLinkList(LinkList L)Node *p;p=L-next;while(p!=NULL)printf(%c ,p-data);p=p-next;printf(n);void Reverse(LinkList L)Node *tail;Node *next;Node *cur;Node *pre;tail=L-next;while(tail-next!=NULL)tail=tail-next;pre=L-next;cur=pre-next;next=cur-next;pre-next=NULL;cur-next=pre;while(next-next!

10、=NULL)pre=cur;cur=next;next=next-next;cur-next=pre;pre=cur;cur=next;cur-next=pre;L-next=tail;void main()LinkList L;InitLinkList(&L);CreatFromHead(L);printLinkList(L);Reverse(L);printLinkList(L);2、 设一个没有头结点指针的单链表。一个指针指向此单链表中间的一个结点（不是第一个，也不是最后一个结点），将该结点从单链表中删除，要求时间复杂度O（1）。解：狸猫换太子,将要删除的下个节点的值给#include

11、#include typedef char ElemType;typedef struct NodeElemType data;struct Node *next;Node,*LinkList;LinkList CreatLinkList()Node *s,*p;int flag=1;ElemType ch;LinkList L;L=(Node*)malloc(sizeof(Node);L-next=NULL;scanf(%c,&ch);if(ch=#)L-data=0;flag=0;elseL-data=ch;p=L;while(flag)scanf(%c,&ch);if(ch=#)flag

12、=0;elses=(Node*)malloc(sizeof(Node);s-data=ch;s-next=p-next;p-next=s;p=p-next;return L;void printList(LinkList L)Node *p;p=L;while(p!=NULL)printf(%c,p-data);p=p-next;printf(n);void Delete(LinkList L,Node *p)Node *q;q=L;q=p-next;p-data=p-next-data;p-next=q-next;free(q);void main()LinkList L;Node *p;L

13、=CreatLinkList();printList(L);p=L-next-next;Delete(L,p);printList(L);3、 判断一个单链表是否存在环。解：快慢指针。一个一次走一步，一个一次走2步。根据相遇的结点和开始结点同时开始走，相遇时就是环的入口。4、 判断两个单链表是否相交。解：如果只求是否相交，2个指针，都走到2个链表的尾部，判断是否相同。否者，求2个链表的长度ln1,ln2，长度单链表先走|ln1-ln2|步，接着一起走，判断是否相同。5、 输出一个单链表的倒数第K个节点。解：2个指针，一个先走K步，让后同时走，先走的到链表尾时，后走的正好在倒数第K个上。6、 约

14、瑟夫环问题。已知n个人（以编号1，2，3.n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。/方法1、使用链表#include#include#includeusing namespace std;int main(int argc, char* argv) int total=0; couttotal; int keyNum=0; coutkeyNum; if(keyNumkeyNum | keyNum1 | total1) coutinput error!endl; sy

15、stem(paused); list* table=new list(); for(int i=1; ipush_back(i); int shout=1; for(list:iterator it=table-begin(); table-size()!=1;) if(shout+=keyNum) /cout*iterase(it); shout=1; else +it; if(it=table-end() it=table-begin(); coutThe last one is:; coutbegin()endl; system(pause); return 0; /方法2、数学推导#i

16、nclude #include using namespace std;int main() int total = 0; cout total; int number = 0; cout number; /* If number = 3 * f(1) = 0 * f(2) = 1 = (f(1) + 3) % 2 * f(3) = 1 = (f(2) + 3) % 3 * f(4) = 0 = (f(3) + 3) % 4 * f(5) = 3 = (f(4) + 3) % 5 * . * f(n) = x = (f(n-1) + 3) % n * */ int last = 0; / f(

17、1) = 0 for (int i = 2; i = total; +i) last = (last + number) % i; cout The last one is : last + 1 endl; return 0;#include #include #define N 30typedef struct Nodeint number;int code;struct Node *next;Node,*List;List InitList()int n;int i;int code;Node *p;Node *s;List L;p=(Node*)malloc(sizeof(Node);p

18、-number=1;p-next=NULL;L=p;printf(请输入人数n（30以内）n);scanf(%d,&n);for(i=1;inumber=i+1;s-next=NULL;p-next=s;p=p-next;p=L;printf(请输入每个人的密码n);for(i=0;icode=code;p=p-next;return L;void printL(List L)Node *p;p=L;printf(n);while(p!=NULL)printf(%d %d n,p-number,p-code);p=p-next;void yuesefu(List L,List CL,int m)Node *p;Node *q;int i;p=L;while(p-next!=NULL)p=p-next;p-next=L;p=L;printf(n);while(p-next!=p)for(i=0;inext;if(m=1)p=p-next;q=p-next;p-next=p-next-next;p=p-next;q-next=CL-next;CL-ne