算法与数据结构试题.doc

《算法与数据结构试题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一章算法分析基础1、下列时间复杂度最好的是()A、OB、OC、OD、O2、从逻辑上可以把数据结构分为哪两大类？（）A、动态结构、静态结构B、顺序结构、链式结构C、线性结构、非线性结构D、初等结构、构造型结构3、算法分析的主要任务是分析（）A．算法是否具有较好的可读性B．算法中是否存在语法错误C．算法的功能是否符合设计要求D．算法的执行时间和问题规模之间的关系4、下面程序段中带下划线的语句的执行次数是。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+

2、+)s=s+1;A．O（10）                    B．O（20）C．O（1）          D．O（102）6、数据的最小单位是（）A.数据项                            B.数据类型C.数据元素                     　D.数据变量7、下列程序的时间复杂度为（）　　i=1；k=100；　　while（i

3、)，其含义是指算法的执行时间和_______的数量级相同。第二章线性表1、非空的循环单链表L的尾结点（由p所指）满足（　）A.p->next=NULL                B.p=NULLC.p->next= L                 D.p= L2、从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动的元素的个数是（　　）A.n-i                          B.n-i+1C.n-i-1                        D.i3、链表不具备的特点是（　）A．可随机访问任一结点                 

4、  B．插入删除不需要移动元素C．不必事先估计存储空间                D．所需空间与其长度成正比4、顺序表的存储密度为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

5、所指结点是指针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,…,

6、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、设一个链表最常用的操作是

7、在末尾插入结点和删除尾结点，则选用哪个最节省时间（）A、单链表B、单循环链表C、带尾指针的单循环链表D、带头结点的双循环链表13、双向链表中有两个指针域，llink和rlink，分别指向前驱和后继，设p指向链表中的一个结点，q指向一待插入结点，想要求在p前插入q，则正确的插入为（）A.p->llink=q;q->rlink=p;p-llink->rlink=q;q->llink=p->llink;B.q->llink=p->llink;p-llink->rlink=q