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

《给出以下算法的时间复杂度》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章绪论1、填空题1.常见的数据结构有_________结构，_________结构，_________结构等三种。2.常见的存储结构有_________结构，_________结构等两种。3.数据的基本单位是_________，它在计算机中是作为一个整体来处理的。4.数据结构中的结构是指数据间的逻辑关系，常见的结构可分为两大类，_________和_________。2、应用题1、给出以下算法的时间复杂度.voidfun(intn){inti=1,k=100;while(i

2、_______________。2、给出以下算法的时间复杂度.voidfun2(intn){inti=1,k=100;while(i

3、______________；②_____________________________；4.在单向链表中，若要删除某个结点p，必须要找到_______________结点，才能实现该操作。2、选择题1.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。(A)n   (B)2n－1   (C)2n   (D)n-12.在单链表中，如果在结点p之后插入一个新结点s，其操作为。（A）s->next=p->next;p->next=s;（B）p->next=s;s->next=p->next;（C）s->next=

4、p;p->next=s->next;（D）p->next=s;s->next=p;3.若长度为n的线性表采用顺序存储结构，在其第i个位置删除一个元素的算法的平均时间复杂度为(   )。(1≤i≤n)A．O(0)   B．O(1)   C.O(n)   D．O(n2)4.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素需要移动的元素个数为(   )。(1≤i≤n+1)A．n-i  B．n-i+1   C.i   D．n-i-13、判断题1.线性表中每一个元素都有一个前驱和一个后继。（）4、程序设计题1、单链表的

5、结点结构定义如下：structLinkNode{LinkNode*next;intdata;};请根据述函数的功能写程序。（10分）voidInsert(LinkNode*h,LinkNode*s){//h指向链表的头结点（即使链表中没有元素，头结点也存在。）//链表中元素已经递增有序//函数功能为将结点s插入到链表h中。插入后链表仍然保持递增的顺序}2、设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。顺序表的结构定义如下：#defineListSize100//假定表空间大小为100struct

6、SqList{   intelem[ListSize];//数组elem用于存放表中的数据   intlength;//当前的表长度};//以上为顺序表的结构//函数头定义如下voidInsertIncreaseList(SqList&L,intx){}///////3、单链表中结点的结构如下所示：typedefstructnode{intdata;structnode*next;}node;请设计满足下述功能的函数。要求：建立带头结点的单链表H，要求函数从屏幕上读入m个整数，每读入一个，便生成相应的结点，并且把它插入到链表

7、H的尾部。函数形式为voidCreateLinkList(node*H)。（10分）第3章栈和队列1、填空题1.栈和队列在本质上都是_____________。2.栈的操作特点是_____________。队列的操作特点是_____________。3.栈和队列是一种特殊的_____________，栈的特点是_____________；队列的特点是_____________。2、选择题1.消除递归不一定需要使用栈，此说法_______。A.正确   B.错误2.对于栈，输入序列为（1，2，3，4），不可能得到的输出序列有_

8、______。(A)（1，2，3，4） (B)（4，3，2，1） (C)（1，3，4，2） (D)（3，1，2，4）3.用单循环链表表示队列，正确的说法是。(A)可设一个头指针使入队、出队都方便；(B)可设一个尾指针使入队、出队都方便；(C)必须设头尾指针才能使入队、出队都方便；(D)无论