给出以下算法的时间复杂度.doc

文档介绍：给出以下算法的时间复杂度第1章绪论1、,_________结构,_________结构等三种。,_________结构等两种。,它在计算机中是作为一个整体来处理的。,常见的结构可分为两大类,_________和_________。2、应用题1、(intn){inti=1,k=100;while(i<n){k=k+1;i=i+2;}}时间复杂度为_______________。2、(intn){inti=1,k=100;while(i<n){i=i*10;k=k+1;}}时间复杂度为_______________。第2章线性表1、,一种是_______________表,另一种是_______________表。。,则其操作序列为:?_____________________________;?_____________________________;,若要删除某个结点p,必须要找到_______________结点,才能实现该操作。2、,其最少的比较次数是。(A)n(B)2n,1(C)2n(D)n-1在单链表中,如果在结点p之后插入一个新结点s,其操作为。2.(A)s->next=p->next;p->next=s;(B)p->next=s;s->next=p->next;(C)s->next=p;p->next=s->next;(D)p->next=s;s->next=p;,在其第i个位置删除一个元素的算法的平均时间复杂度为()。(1?i?n)2A(O(0)B(O(1)(n)D(O(n),在其第i个位置插入一个新元素需要移动的元素个数为()。(1?i?n+1)A(n-iB(n-i+(n-i-13、。()4、程序设计题1、单链表的结点结构定义如下:structLinkNode{LinkNode*next;intdata;};请根据述函数的功能写程序。(10分)voidInsert(LinkNode*h,LinkNode*s){//h指向链表的头结点(即使链表中没有元素,头结点也存在。)//链表中元素已经递增有序//函数功能为将结点s插入到链表h中。插入后链表仍然保持递增的顺序}2、设顺序表L是一个递增有序表,试写一算法,将x插入L中,并使L仍是一个有序表。顺序表的结构定义如下:#defineListSize100//假定表空间大小为100structSqList{intelem[ListSize];//数组elem用于存放表中的数据intlength;//当前的表长度};//以上为顺序表的结构//函数头定义如下voidInsertIncreaseList(SqList&L,intx){}///////3、单链表中结点的结构如下所示:typedefstructnode{intdata;structnode*next;}node;请设计满足下述功能的函数。要求:建立带头结点的单链表H,要求函数从屏幕上读入m个整数,每读入一个,便生成相应的结点,并且把它插入到链表H的尾部。函数形式为voidCreateLinkList(node*H)。(10分)第3章栈和队列1、。。队列的操作特点是_____________。,栈的特点是_____________;队列的特点是_____________。2、,此说法_______。,输入序列为(1,2,3,4),不可能得到的输出序列有_______。(A)(1,2,3,4)(B)(4,3,2,1)(C)(1,3,4,2)(D)(3,1,2,4),正确的说法是。(A)可设一个头指针使入队、出队都方便;(B)可设一个尾指针使入队、出队都方便;(C)必须设头尾指针才能使入队、出队都方便;(D)无论如何,只可能使入队方便。3、。()2