数据结构复习题目

《数据结构复习题目》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章概论练习题一、单项选择题1．在数据结构中，从逻辑上可以把数据结构分为（B）A．紧凑结构和非紧凑结构B．线性结构和非线性结构C．内部结构和外部结构D．动态结构和静态结构2．若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为（D）A．顺序存储结构B．链式存储结构C．索引存储结构D．散列存储结构3．算法分析的两个主要方面是（B）A．正确性和简明性B．时间复杂性和空间复杂性C．可读性和可维护性D．数据复杂性和程序复杂性4．线性表采用链式存储结构时，要求内存中可用存储单元地址（A）A．不一定连续的B．部分地

2、址必须是连续的C．必须是连续的D．一定是不连续的5．算法指的是（C）A．计算机程序B．解决问题的计算方法C．解决问题的有限运算序列D．排序算法二、填空题6．数据结构一般包括逻辑结构、存储结构和数据运算三个方面的内容．7．数据的逻辑结构可分为线性结构、非线性结构两大类．8．数据的存储结构（物理结构）一般可以用顺序存储结构、链式存储结构、索引存储结构及散列存储结构等四种存储方法表示．9．在选用求解一个问题的算法时，除了首先考虑算法是“正确的”之外，还主要考虑执行算法所需要的时间、执行算法所需要的存储空间及算法应易于理解、易

3、于编程、易于调试等三点。10．设有一批数据元素，为了最快地存取某元素，宜用顺序结构存储，为了方便的插入一个元素，宜用链式结构存储．三、应用题设n为正整数，利用大“O”记号，写出下列各程序段的时间复杂度．11．for(i=1;i<=n;i++){y=y+1;for(j=1;j<=2*n;j++)x=x+1;}分析：语句“y=y+1;”执行n次，语句“x=x+1;”各执行次，故该程序段的时间复杂度为O()．12．s=0;while(n>=(s+1)*(s+1))s=s+1;分析：语句“s=s+1;”执行次，故该程序段的时间

4、复杂度为O()．13．x=1;sum=0;for(i=0;i<=n;i++){x=x*i;sum=sum+x;}分析：语句“x=x*i”和“sum=sum+x;”各执行n次，故该程序段的时间复杂度为O(n)．14．for(i=1;i<=n;i++)if(3*i<=n)for(j=3*i;j<=n;j++){x++;y=3*x+2;}分析：语句“x++”和“y=3*x+2;”各执行次，故该程序段的时间复杂度为O()．15．for(i=1;i<=n;i++)for(j=1;j<=i;j++){x=x+1;}分析：语句“x=

5、x+1;”执行次，故该程序段的时间复杂度为O()．16．sum=0;i=0;while(i<=100){sum=sum+i;i++;}分析：语句“sum=sum+i;”和“i++;”各执行100次，故该程序段的时间复杂度为O(1)．17．x=1;s=0;for(i=1;i<=n;i++){++x;s+=x;}for(j=1;j<=n;j++)for(k=1;k<=n;k++){x++;s=s+x;}分析：语句“++x;”执行n次，语句“x++;”和“s=s+x;”各执行次，故该程序段的时间复杂度为O()．第2章线性表练

6、习题一、单项选择题1．在长度为n的顺序表的第i个位置上插入一个元素，元素的移动次数为（A）A．B．C．D．2．若一个顺序表中第一个元素的存储地址为1000，每个元素占4个地址单元，那么，第6个元素的存储地址应是（A）A．1020B．1010C．1016D．10243．带头结点的单链表（以head为头指针）为空的判断条件是（C）A．head!=NULLB．head->next==headC．head->next==NULLD．head==NULL4．在单循环链表中，p指向表任一结点，判断表不是访问结束的条件是（B）A．p

7、!=NULLB．p!=headC．p->next!=headD．p->next!=NULL5．在一个单链表中，已知q指向p所指向结点的前趋结点，若在p、q所指结点之间插入一个s所指向的新结点，则执行的操作是（A）A．q->next=s;s->next=pB．p->next=s;s->next=qC．s->next=p->next;p->next=sD．p->next=s->next;s->next=p6．在一个单链表中，若删除p指向结点的后继结点，则执行的操作是（A）A．q=p->next;p->next=p->nex

8、t->next;free(q);B．p=p->next;q=p->next;p=q->next;free(q);C．q=p->next->next;p=p->next;free(q);D．p=p->next->next;q=p->next;free(q);二、填空题7．在一个长度为n的顺序表中删除第i个元素，需要向前移动n-i个元