算法与数据结构试题.doc

第一章算法分析基础1、下列时间复杂度最好的是()A、OB、OC、OD、O2、从逻辑上可以把数据结构分为哪两大类?()A、动态结构、静态结构B、顺序结构、链式结构C、线性结构、非线性结构D、初等结构、构造型结构3、算法分析的主要任务是分析()、下面程序段中带下划线的语句的执行次数是。for(i=0;i<=n;i++)for(j=0;j<=i;j++)x=x+1;5、下列程序的时间复杂度为()s=0;for(i=0;i<10;i++)for(j=0;j<10;j++)s=s+1;(10)                    (20)(1)          (102)6、数据的最小单位是()                                                  、下列程序的时间复杂度为() i=1;k=100; while(i<n) {k=k+1; i=i+2; }(1)                    (n)(n3)                    (n2)8、称算法的时间复杂度为O(logn),其含义是指算法的执行时间和_______的数量级相同。第二章线性表1、非空的循环单链表L的尾结点(由p所指)满足( )->next=NULL                =->next= L                 = L2、从一个长度为n的顺序表中删除第i个元素(1≤i≤n)时,需向前移动的元素的个数是( )-i                          -i+-i-1                        、链表不具备的特点是( )                                   、顺序表的存储密度为1,而链表的存储密度_。5、写算法,顺序查找一个元素值等于e的元素的逻辑序号。若这样的元素不存在,则返回值为0。6、完善下列程序段。在一个单链表(已知每个结点含有数据域data和指针域next)中删除p所指结点时,可执行如下操作:1)q=p->next;2)p->data=___①____;3)p->next=_____②____;4)free(q);题目如改成删除p所指的结点的后继结点,②为7、设单链表中结点结构为(data,link).已知指针q所指结点是指针p所指结点的直接前驱,若在*q 与*p之间插入结点*s,则应执行下列哪一个操作(     )A.   s->link=p->link;  p->link=s;     B.  q->link=s; s->link=pC.  p->link=s->link;s->link=p;    D.  p->link=s; s->link=q;8、若某线性表中最常用的操作是在第i个元素之前插入一个元素和删除第i个元素,则采用什么存储方式最节省时间。()A、散列表B、单链表C、二叉链表D、顺序表9、写一算法实现带头结点的单链表L的就地逆置,即在原表的存储空间中将表(a1,a2,…,an)逆置为(an,…,a2,a1)。10、指出下述程序段的功能是什么?  LinkListDemo(LinkListL){//L是无头结点单链表 ListNode*Q,*P; if(L&&L->next){ Q=L;L=L->next;P=L; while(P->next)P=P->next; P->next=Q;Q->next=NULL; } returnL; }11、线性表(a1,a2,……,an)以链接方式存储,访问第i个位置元素的时间复杂性为()。A、O(i)B、O(1)C、O(n)D、O(i-1)12、设一个链表最常用的操作是在末尾插入结点和删除尾结点,则选用哪个最节省时间()A、单链表B、单循环链表C、带尾指针的单循环链表D、带头结点的双循环链表13、双向链表中有两个指针域,llink和rlink,分别指向前驱和后继,设p指向链表中的一个结点,q指向一待插入结点,想要求在p前插入q,则正确的插入为()->llink=q;q->rlink=p;p-llink->rlink=q;q->llink=p->llink;->llink=p->llink;p-llink->rlink=q;q->rlink=p;p->llink=q->rlin