搜索
数据结构复习题第一章概论一、选择题1、研究数据结构就是研究（D）。A.数据的逻辑结构B.数据的存储结构C.数据的逻辑结构和存储结构D.数据的逻辑结构、存储结构及其基本操作2、算法分析的两个主要方面是（A）。A.空间复杂度和时间复杂度B.正确性和简单性C.可读性和文档性D.数据复杂性和程序复杂性3、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（B）等5个特性。A.可行性、可移植性和可扩充性B.可行性、有穷性和确定性C.确定性、有穷性和稳定性D.易读性、稳定性和确定性4、下面程序段的时间复杂度是（C）。for(i=0;im;i++)for(j=0;jn;j++)a[i][j]=i*j;A.O(m2)B.O(n2)C.O(m*n)D.O(m+n)5、算法是（D）。A.计算机程序B.解决问题的计算方法C.排序算法D.解决问题的方法和步骤，是规则的有穷集合6、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（C）。A.O(n)B.O(nlog2n)C.O(n2)D.O(log2n)7、下面程序段的时间复杂度为（C）。i=1;while(i=n)i=i*3;A.O(n)B.O(3n)C.O(log3n)D.O(n3)8、数据结构是一类数据的表示及其相关操作，它一般包括三个方面的内容：数据的逻辑结构、（D）和数据的运算。A.数据的操作B.数据的算法C.数据的连接D.数据的存储结构9、抽象数据类型的三个组成部分分别为（A）。A.数据对象、数据关系和基本操作B.数据元素、逻辑结构和存储结构C.数据项、数据元素和数据类型D.数据元素、数据结构和数据类型10、下列程序段的时间复杂度为（B）。x=n;y=0;while(x=(y+1)*(y+1))y=y+1;A.O(n)B.)(nOC.O(1)D.O(n2)二、填空题1、程序段“i=1;while(i=n)i=i*2;”的时间复杂度为log2n。2、数据结构的四种基本类型中，树形结构的元素是一对多关系。3、数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。4、数据结构按逻辑结构可分为四类，它们分别是集合、线性结构、树状结构和图状结构。5、线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。6、在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后继结点，其余每个结点有且只有1个后继结点。7、在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。8、在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。9、数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引、散列。10、一个算法的效率可分为时间效率和空间效率。三、简答题1、简述线性结构与非线性结构的不同点。答：线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是多对多的。第二章线性表一、选择题1、下述哪一条是顺序存储结构的优点？（A）A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示2、下面关于线性表的叙述中，错误的是哪一个？（B）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。3、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度（C）。A.O(log2n)B.O(1)C.O(n)D.O(n2)4、若一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间。（A）。A.顺序表B.单链表C.双链表D.单循环链表5、具有线性结构的数据结构是（D）。A.图B.树C.广义表D.栈6、在一个长度为n的顺序表中，在第i个元素之前（元素从1开始计数）插入一个新元素时，需向后移动（）个元素。（B）A.n-iB.n-i+1C.n-i-1D.i7、非空的循环单链表head的尾结点p满足（A）。A.p-next==headB.p-next==NULLC.p==NULLD.p==head8、链表不具有的特点是（A）。A.可随机访问任一元素B.插入删除不需要移动元素C.不必事先估计存储空间D.所需空间与线性表长度成正比9、线性表采用链式存储时，结点的存储地址（）。A.必须是连续的B.必须是不连续的C.连续与否均可D.和头结点的存储地址相连续10、在一个长度为n的顺序表中删除第i个元素，需要向前移动（A）个元素。A.n-iB.n-i+1C.n-i-1D.i+111、从表中任一结点出发，都能扫描整个表的是（C）。A.单链表B.顺序表C.循环链表D.静态链表12、在具有n个结点的单链表上查找值为x的元素时，其时间复杂度为（A）。A.O(n)B.O(1)C.O(n2)D.O(n-1)13、线性表L=(a1,a2,……,an)，下列说法正确的是（D）。A.每个元素都有一个直接前驱和一个直接后继B.线性表中至少要有一个元素C.表中诸元素的排列顺序必须是由小到大或由大到小D.除第一个和最后一个元素外，其余每个元素都由一个且仅有一个直接前驱和直接后继14、在线性表的下列存储结构中，读取元素花费的时间最少的是（D）。A.单链表B.双链表C.循环链表D.顺序表15、在一个单链表中，若删除p所指向结点的后续结点，则执行（A）。A.p-next=p-next-next;B.p=p-next;p-next=p-next-next;C.p=p-next;D.p=p-next-next;16、循环链表的主要优点是（D）。A.不再需要头指针B.已知某结点位置后能容易找到其直接前驱C.在进行插入、删除运算时能保证链表不断开D.在表中任一结点出发都能扫描整个链表17、在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（A）。A.访问第i个元素的前驱（1ni）B.在第i个元素之后插入一个新元素(ni1)C.删除第i个元素(ni1)D.对顺序表中元素进行排序18、已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为（A）。A.q-next=s-next；s-next=p；B.s-next=p；q-next=s-next；C.p-next=s-next；s-next=q；D.s-next=q；p-next=s-next；19、在以下的叙述中，正确的是（C）。A.线性表的顺序存储结构优于链表存储结构B.线性表的顺序存储结构适用于频繁插入/删除数据元素的情况C.线性表的链表存储结构适用于频繁插入/删除数据元素的情况D.线性表的链表存储结构优于顺序存储结构20、在表长为n的顺序表中，当在任何位置删除一个元素的概率相同时，删除一个元素所需移动的平均个数为（A）。A.(n-1)/2B.n/2C.(n+1)/2D.n21、在单链表中，指针p指向元素为x的结点，实现删除x的后继的语句是（B）。A.p=p-next;B.p-next=p-next-next;C.p-next=p;D.p=p-next-next;二、填空题1、设单链表的结点结构为（data,next）。已知指针p指向单链表中的结点，q指向新结点，欲将q插入到p结点之后，则需要执行的语句：；。答案：q-next=p-nextp-next=q2、线性表的逻辑结构是，其所含元素的个数称为线性表的。答案：线性结构长度3、带头结点的单链表head为空的条件是。答案：head-next==NULL4、在一个单链表中删除p所指结点的后继结点时，应执行以下操作：q=p-next;p-next=____;答案：q-next三、判断题1、单链表不是一种随机存储结构。2、在具有头结点的单链表中，头指针指向链表的第一个数据结点。3、在线性表的顺序存储结构中，逻辑上相邻的两个元素但是在物理位置上不一定是相邻的。4、顺序存储结构的主要缺点是不利于插入或删除操作。()5、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。()6、顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。()7、线性表的特点是每个元素都有一个前驱和一个后继。()8、取线性表的第i个元素的时间同i的大小有关.()9、线性表只能用顺序存储结构实现。()10、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。()11、链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。()四、程序分析填空题1、函数实现单链表的插入算法，请在空格处将算法补充完整。intListInsert(LinkListL,inti,ElemTypee){LNode*p,*s;intj;p=L;j=0;while((p!=NULL)&&(ji-1)){p=p-next;j++;}if(p==NULL||ji-1)returnERROR;s=(LNode*)malloc(sizeof(LNode));s-data=e;(1);(2);returnOK;}/*ListInsert*/答案：(1)s-next=p-next(2)p-next=s2、函数ListDelete_sq实现顺序表删除算法，请在空格处将算法补充完整。intListDelete_sq(Sqlist*L,inti){intk;if(i1||iL-length)returnERROR;for(k=i-1;kL-length-1;k++)L-slist[k]=（1）;（2）;returnOK;}答案：（1）L-slist[k+1]（2）--L-Length3、函数实现单链表的删除算法，请在空格处将算法补充完整。intListDelete(LinkListL,inti,ElemType*s){LNode*p,*q;intj;p=L;j=0;while((（1）)&&(ji-1)){p=p-next;j++;}if(p-next==NULL||ji-1)returnERROR;q=p-next;（2）;*s=q-data;free(q);returnOK;}/*listDelete*/答案：(1)p-next!=NULL(2)p-next=q-next五、编程题1、有两个循环链表，链头指针分别为L1和L2，要求写出算法将L2链表链到L1链表之后，且连接后仍保持循环链表形式。答案：voidmerge(Lnode*L1,Lnode*L2){Lnode*p,*q;while(p-next!=L1)p=p-next;while(q-next!=L2)q=q-next;q-next=L1;p-next=L2;}2、设一个带头结点的单向链表的头指针为head，设计算法，将链表的记录，按照data域的值递增排序。答案：voidassending(Lnode*head){Lnode*p,*q,*r,*s;p=head-next;q=p-next;p-next=NULL;while(q){r=q;q=q-next;if(r-data=p-data){r-next=p;head-next=r;p=r;}else{while(!p&&r-datap-data){s=p;p=p-next;}r-next=p;s-next=r;}p=head-next;}}六、应用题1、线性表有两种存储结构：一是顺序表，二是链表。试问：（1）如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用