数据结构练习题(含答案)

数据结构练习题习题1绪论1.1单项选择题1.数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。①A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象②A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法2.数据结构DS(DataStruct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。①A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象②A．操作Ｂ．映象Ｃ．存储Ｄ．关系3.在数据结构中，从逻辑上可以把数据结构分成。A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构4.算法分析的目的是①，算法分析的两个主要方面是②。①A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性②A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性5.计算机算法指的是①，它必具备输入、输出和②等五个特性。①A.计算方法B.排序方法C.解决问题的有限运算序列D.调度方法②A.可行性、可移植性和可扩充性B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性1.2填空题（将正确的答案填在相应的空中）1.数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。2.在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。3.在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。4.在图形结构中，每个结点的前驱结点数和后续结点数可以。5.线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。6.算法的五个重要特性是____,____,____,____,____。7.分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是____。for(i=0;in;i++)for(j=0;jn;j++)A[i][j]=0;8.分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是____。for(i=0;in;i++)for(j=0;ji;j++)A[i][j]=0;9.分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是____。s=0;for(i=0;in;i++)for(j=0;jn;j++)for(k=0;kn;k++)s=s+B[i][j][k];sum=s;10.分析下面算法（程序段）给出最大语句频度，该算法的时间复杂度是____。i=s=0;while(sn){i++;s+=i;//s=s+i}11.分析下面算法（程序段）给出最大语句频度，该算法的时间复杂度是____。i=1;while(i=n)i=i*2;1.3算法设计题1.试写一算法,自大到小依次输出顺序读入的三个数X,Y和Z的值.2.试写一算法,求出n个数据中的最大值。写出最大语句频度，该算法的时间复杂度。习题答案1.11.C,A2.B,D3.C4.C,A5.C,B1.21.线性结构、树形结构、图形结构，非线性结构2.没有、1、没有、13.前驱、1、后续、任意多个4.任意多个5.一对一、一对多、多对多6.有穷性、确定性、可行性、输入、输出7.最大语句频度：n2，时间复杂度：.O(n2)8.最大语句频度：n(n+1)/2，时间复杂度：.O(n2)9.最大语句频度：n3，时间复杂度：.O(n3)10.最大语句频度：n12，时间复杂度：.O(n12)11.最大语句频度：log2n，时间复杂度：.O(log2n)习题2线性表2.1单项选择题1.一个向量（即一批地址连续的存储单元）第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是____。A.110B.108C.100D.1202.线性表的顺序存储结构是一种___的存储结构，而链式存储结构是一种___的存储结构。A．随机存取B．索引存取C．顺序存取D．散列存取3.线性表的逻辑顺序与存储顺序总是一致的，这种说法___。A.正确B.不正确4.线性表若采用链式存储结构时，要求内存中可用存储单元的地址___。A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续或不连续都可以5.在以下的叙述中，正确的是___。A.线性表的顺序存储结构优于链表存储结构B.线性表的顺序存储结构适用于频繁插入/删除数据元素的情况C.线性表的链表存储结构适用于频繁插入/删除数据元素的情况D.线性表的链表存储结构优于顺序存储结构6.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法___。A.正确B.不正确7.不带头结点的单链表head为空的判定条件是____。A.head==NULLB.head-next==NULLC.head-next==headD.head!=NULL8.带头结点的单链表head为空的判定条件是____。A.head==NULLB.head-next==NULLC.head-next==headD.head!=NULL9.非空的循环单链表head的尾结点（由p所指向）满足____。A.p-next==NULLB.p==NULLC.p-next==headD.p==head10.在双向循环链表的p所指结点之后插入s所指结点的操作是____。A.p-right=s;s-left=p;p-right-left=s;s-right=p-right;B.p-right=s;p-right-left=s;s-left=p;s-right=p-right;C.s-left=p;s-right=p-right;p-right=s;p-right-left=s;D.s-left=p;s-right=p-right;p-right-left=s;p-right=s;11.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行____。A.s-next=p-next;p-next=s;B.p-next=s-next;s-next=p;B.q-next=s;s-next=p;C.p-next=s;s-next=q;12.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行____。A.s-next=p;p-next=s;B.s-next=p-next;p-next=s;C.s-next=p-next;p=s;C.p-next=s;s-next=p;13.在一个单链表中，若删除p所指结点的后续结点，则执行____。A.p-next=p-next-next；B.p=p-next;p-next=p-next-next；C.p-next=p-next;D.p=p-next-next；14.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较____个结点。A.nB.n/2C.(n-1)/2D.(n+1)/215.在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是____。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)16.给定有n个元素的向量，建立一个有序单链表的时间复杂度是____。A.O(1)）B.O(n)C.O(n2)D.O(n*log2n)2.2填空题（将正确的答案填在相应的空中）1.单链表可以做____的链接存储表示。2.在双链表中，每个结点有两个指针域，一个指向______，另一个指向_____。3.在一个单链表中p所指结点之前插入一个s(值为e)所指结点时，可执行如下操作：q=head;while(q-next!=p)q=q-next;s=newNode;s-data=e;q-next=;//填空s-next=;//填空4.在一个单链表中删除p所指结点的后继结点时，应执行以下操作：q=p-next;p-next=____;//填空delete;//填空5.在一个单链表中p所指结点之后插入一个s所指结点时，应执行s-next=____和p-next=____的操作。6.对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是____；在给定值为x的结点后插入一个新结点的时间复杂度是____。2.3算法设计题:1.设顺序表va中的数据元数递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。StatusInsert_SqList(SqList&va,intx){if(va.length+1maxsize)returnERROR;va.length++;for(i=va.length-1;va.elem[i]x&&i=0;i--)va.elem[i+1]=va.elem[i];va.elem[i+1]=x;returnOK;}2.试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1,a2,….an）逆置为(an,an-1,….,a1)。voidreverse(inta[],intsize){inti,j,tmp;for(i=0,j=size-1;ij;i++,j--){tmp=a[i];a[i]=a[j];a[j]=tmp;}}3.已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一算法，删除表中所有大于x且小于y的元素（若表中存在这样的元素）同时释放被删除结点空间。voiddel(LinkListL,elemtypea,elemtypeb){p=L;q=p-next;while(q!=L&&q-dataa){p=q;q=q-next;}while(q!=L&&q-datab){r=q;q=q-next;free(r);}if(p!=q)p-next=q;}4.试写一算法，实现单链表的就地逆置(要求在原链表上进行)。voidconverse(NODEPTRL){NODEPTRp,q;p=L-next;q=p-next;L-next=NULL;while(p)/*对于当前结点p，用头插法将结点p插入到头结点之后*/{p-next=L-next;L-next=p;p=q;q=q-next;}}习题答案2.11.B2.A,C3.B4.D5.C6.A7.A8.B9.C10.D11.B12.B13.A14.D15.B16.C2.21.线性结表2.前驱结点、后继结点3.s,p4.q-next,q5.p-next,s6.O(1),O(n)习题3栈和队列3.1单项选择题1.一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是____。A.edcbaB.decbaC.dceabD.abcde2.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为____。A.iB.n=iC.n-i+1D.不确定3.栈结构通常采用的两种存储结构是____。A.顺序存储结构和链式存储结构B.散列方式和索引方式C.链表存储结构和数组D.线性存储结构和非线性存储结构4.判定一个顺序栈ST（最多元素为m0）为空的条件是____。A.top!=0B.top==0C.top!=m0D.top==m0-15.判定一个顺序栈ST（最多元素为m0）为栈满的条件是____。A.top！=0B.top==0C.top！=m0D.top==m0-16.栈的特点是____，队列的特点是____。A.先进先出B.先进后出7.向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行____。(不带空的头结点)A.HS—＞next=s;B.s—＞next=HS—＞next;HS—＞next=s;C.s—＞next=HS;HS=s;D.s—＞next=HS;HS=HS—＞nex