02331数据结构课后练习题

第1章概论练习题一、单项选择题1．在数据结构中，从逻辑上可以把数据结构分为（B）A．紧凑结构和非紧凑结构B．线性结构和非线性结构C．内部结构和外部结构D．动态结构和静态结构2．若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为（D）A．顺序存储结构B．链式存储结构C．索引存储结构D．散列存储结构3．算法分析的两个主要方面是（B）A．正确性和简明性B．时间复杂性和空间复杂性C．可读性和可维护性D．数据复杂性和程序复杂性4．线性表采用链式存储结构时，要求内存中可用存储单元地址（A）A．不一定连续的B．部分地址必须是连续的C．必须是连续的D．一定是不连续的5．算法指的是（C）A．计算机程序B．解决问题的计算方法C．解决问题的有限运算序列D．排序算法二、填空题6．数据结构一般包括逻辑结构、存储结构和数据运算三个方面的内容．7．数据的逻辑结构可分为线性结构、非线性结构两大类．8．数据的存储结构（物理结构）一般可以用顺序存储结构、链式存储结构、索引存储结构及散列存储结构等四种存储方法表示．9．在选用求解一个问题的算法时，除了首先考虑算法是“正确的”之外，还主要考虑执行算法所需要的时间、执行算法所需要的存储空间及算法应易于理解、易于编程、易于调试等三点。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;”各执行22n次，故该程序段的时间复杂度为O(2n)．12．s=0;while(n=(s+1)*(s+1))s=s+1;分析：语句“s=s+1;”执行n次，故该程序段的时间复杂度为O(n)．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;”各执行1(1)6nn次，故该程序段的时间复杂度为O(2n)．15．for(i=1;i=n;i++)for(j=1;j=i;j++){x=x+1;}分析：语句“x=x+1;”执行1(1)2nn次，故该程序段的时间复杂度为O(2n)．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;”各执行2n次，故该程序段的时间复杂度为O(2n)．第2章线性表练习题一、单项选择题1．在长度为n的顺序表的第i(11)in个位置上插入一个元素，元素的移动次数为（A）A．1niB．niC．iD．1i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!=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next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个元素．8．在顺序表中插入或删除一个元素，需要平均移动表长的一半个元素，具体移动的元素个数与插入或删除的位置有关．9．顺序表中逻辑上相邻的元素在物理存储位置上一定相邻，链表结构中逻辑上相邻的元素在物理位置上不一定相邻．10．已知顺序表中一个元素的存储位置是x，每个元素占c个字节，求其后继元素位置计算公式为xc，而已知单链表中某一结点由p指向，求此后继结点存储地址的操作为pnext．11．在用p指针访问单链表时，判断不是访问结束的条件是p!NULL；在访问单循环链表时，判断不是访问表结束的条件是p!head．12．已知p指向双向链表的中间某个结点，从给定的操作语句中选择合适的填空．（1）在p结点后插入s结点的语句序列是I、G、A、D．（2）在p结点前插入s结点的语句序列是C、N、H、B．（3）删除p结点的直接后继结点的语句序列是J、Q、E、M．（4）删除p结点的直接前趋结点的语句序列是K、P、F、M．（5）删除p结点的语句序列是O、R、L．A．pnextsB．ppriorsC．snextpD．spriorpE．pnextpnextnextF．ppriorppriorpriorG．pnextpriorsH．ppriornextsI．snextpnextJ．qpnextK．qppriorL．free(p)M．free(q)N．spriorppriorO．ppriornextpnextP．ppriorpriornextpQ．pnextnextpriorpR．pnextpriorpprior13．下面是一个在带头结点的单链表head中删除所有数据域值为x的结点的算法，但不完善，请在相应的地方填上适当的语句，使之成为完整的算法．voidDeleX(LinkListhead,DataTypex){LinkNode*p,*q,*s;Phead;qpnext;while(q!=NULL)if(qdatax){sq;qqnext;free(s);pnextq;}else{pq;qqnext;}}三、算法设计题14．设有两个顺序表A和B，且都递增有序。试写一算法，从A中删除与B中相同的那些元素（即计算AB）．SeqListSubtraction(SeqListA,SeqListB){inti,j,k0;//令匹配位置为0for(i0;iA.Length;i){for(jk;jB.Length;j)//从比较匹配的位置开始查起if(A.Data[i]B.Data[j]){kj;//记录比较到的位置for(ji;jA.Length1;j)A.Data[j]A.Data[j1];//删除相同的元素A.Length;break;}}returnA;}15．已知head是指向一个带头结点的单链表的头指针，p指向该链表的任一结点。试写一算法，将p所指向的结点与其后继结点交换位置．voidExchange(LinkListhead,LinkNode*p){LinkNode*q,*s,*r;qpnext;if(q!NULL)//判断所指结点是否是最后一个结点{if(phead)//判断所指结点是否是头结点{headheadnext;//头结点指针域所指结点变成新的头结点sheadnext;//记录第2个结点headnextp;//新的头结点指针域指向原头结点pnexts;//原头结点变成第1个结点后指针域指向第2个结点}else{rhead;while(rnext!p)rrnext;//查找p指向结点直接前趋rnextq;//p指向结点直接前趋指针域指向p指向结点直接后继pnextqnext;//p指向结点指针域指向p指向结点直接后继的直接后继qnextp;//p指向结点直接后继指针域指向p}}elseprintf(“p指向的结点无后继节点!”)}16．已知两条单链表A和B分别表示两个集合，其元素值递增有序。试写一算法，求A和B的交集C，要求C同样以元素值递增的单链表形式存储．LinkListIntersection(LinkListA,LinkListB){LinkNode*p,*q,*r,*s;LinkListC(LinkNode*)malloc(SizeOf(LinkNode));rC;pA;sB;while(p!null&&q!null){if(pdataqdata)ppnext;elseif(pdataqdata)qqnext;else{s(LinkNode*)malloc(SizeOf(LinkNode));sdatapdata;snextNULL;rnexts;rs;ppnext;qqnext;}}}17．设有一个带头结点的双向循环链表，head为链表的头指针。试写一算法，实现在值为x的结点之前插入一个值为y的结点．voidInsert(DlinkListhead,DataTypex,DataTypey){DlistNode*p,*s;s(DlistNode*)malloc(SizeOf(DlistNode));sdatay;pheadnext;while(p!head&&pdata!x)ppnext;//查找结点值为x的结点if(phead)printf(“没有值为x的结点!”);else{snextp;spriorpprior;ppriornexts;ppriors;}}第3章栈和队列练习题一、单项选择题1．栈的操作原则是（C）A．顺序进出B．后进后出C．后进先出D．先进先出2．进栈序列为a，b，c，则通过入出栈操作可能得到的a，b，c的不同排列个数为（B）A．4B．5C．6D．73．按字母a，b，c，d，e顺序入栈，则出栈的输出序列不可能是（B）A．decbaB．dceabC．abcdeD．edcba4．判断一个顺序栈st（最多元素为StackSize）为栈满的条件表达式是（D）A．st.top!StackSizeB．st.top!0C．st.top!1D．st.topStackSize15．在向顺序栈中压入元素时（C）A．先存入元素，后移动栈顶指针B．谁先谁后无关紧要C．先移动栈顶指针，后压入元素D．同时进行6．一个队列的入队序列是1，3，5，7，9，则出队的输出序列只能是（B）A．9，7，5，3，1B．1，3，5，7，9C．1，5，9，3，7D．9，5，1，7，37．判断一个顺序队列sq（最多元素为QueueSize）为空队列的条件表达式为（A）A．sq.rearsq.frontB．sq.rea