数据结构（Java语言描述）习题答案.docx

1.5习题一.填空巡1 .数据的物理结构包括顺序结构的表示和存储和链式结构的表示和存储。2 .对于给定的n个元素,可以构造出的逻辑结构有（集合结构），（线性结构）,（树型结构），（图型结构）四种。3 .一个算法具有5个特性：（有穷性）、（确定性）、（可行性），有零个或多个输入、有一个或多个输出。4 .抽象数据类型被形式地定义为（D.S,P）,其中D是（数据元素）的有限集合，S是D上的（关系）有限集合，P是对D的（坛本操作）集合。5 .数据结构主要包括数据的（逻辑结构）、数据的（存储结构）和数据的（操作）这三个方面的内容.6 .一个算法的效率可分为（时间）效率和（空间）效率。二.单项选择题1 .线性结构是数据元素之间存在种（D）。A.一对多关系B.多对多关系C.多对一关系D.一对一关系2 .数据结构中,与所使用的计算机无关的是数据的（C）结构.A.存储B.物理C.逻辑D.物理和存储3 .算法分析的目的是（B）。A.找出数据结构的合理性B.分析竟法的效率以求改迸C.研究算法中的输入和输出的关系D.分析算法的易懂性和文档性4 .算法分析的两个主要方面是（A.空间更杂性和时间纪杂性B.正确性和简明性C.可读性和文档性D.数据更杂性和程序豆杂性5 .计算机算法指的是（C）.A.计算方法B.排序方法C.解决问题的有限运算序列D.调度方法6 .从逻辑上可以把数据结构分为（八）.A.线性结构和非线性结构B.紧凑结构和非紧凑结构C.动态结构和静态结构D.内部结构和外部结构pl.ncx(=ql.ncxt;1.ength-;)5 .设仃个双链表，每个结点中除有PriOr、data和next三个域外，还有一个访问频度域freq在链表被起用之前，其值均初始化为零。每当对链表进行一次1.OCaICNOdC(1.x)运算，便令元素值为X的结点的限q域的值加I，并调推表中结点的次序，使其按访问频度的递减序排列，以便使频繁访问的结点总是舞近表头。忒写个符合上述要求的算法1.oCateNOde(1.X)。static<,extendsComparable>boolean1.ocateNode(dlinklist1.Tx)DuN(lc<T>p=1.gclHead().ncxt;指针p用于查找第个data域等于X的结点DuNode<>q:while(p!=nll&&(p.data).e<uals(x)=falsc)p=p.ncxt;if(p=null)/p为空,意味着没有找到data域等x的结点returnfalse;clscp.freq÷÷:将找到的data域等于x的结点的访问频度值加Iq=p.prior;指付q用于查找P的前面结点中第一个freq域不小于当前P所指结点的freq域的结点while(q!=1.getHead()&&(q.freq).mpareo(p.freq)<()q=q.prior;if(q!=p.prior)如果q发生了前移,才有必要移动Pp.rior.next=p.next;if(p.ncxt!=null)p.next.prior=p.prior:如果P不是终端结点，才有必要修改p的后继结点的prior域p.prior=q;p.next=q.next;q.next=p;p.next.prior=p;/将P插入到q的后边)Jreturntrue;6 .一个单循环链表F,每个结点包含三个域：pre,data-flnext.其中Pre为null,将其变为双循环链表的算法如下，请对算法中的空白处城空：intdoublc_lisi(Du1.ink1.istF)Du1.Node*p,*q;if(F.ncxt=F)(F.pre=F:return;)产循环链表为空的情况q=F;=F.nexl;A.front=rcarB.front!=rcarC.front=(rear+l)%n()D.front!=(rear+1)%n()10.判定个循环队列QU(最多元素为m)为满队列的条件是_C_。A.front=rearB.front!=rearC.front=(rear+1)%mD.front!=(rear+1)%m11 .循环队列用数组A()m-l存放其元素值，己知其头尾指针分别是from和rear,则当前队列中的元素个数是_A_。A.(rcar-front+m)%mB.rcar-front+lC.rear-front-1D.rear-front12 .栈和队列的共同点是_CA.都是先进后出B,都是先进先出C.只允许在端点处插入和删除元素D.没有共同点13 .向一个栈顶指针为HS的链栈中插入一个S所指结点时，则执行一Cl(不带空的头结点)A.HS.next=s;B.s.next=HS.next:HS.next=s;C.s.nex(=HS;HS=s;D.s.ncxt=HS:HS=HS.ncxt;14.从一个栈顶指针为HS的链栈中删除一个结点时，用X保存被删结点的值，则执行_D_0(不带空的头结点)A.X=HS;HS=HS.next;B.x=HS.data;C.HS=HS.next;x=HS.data;D.x=HS.data:HS=HS.next：二.填空题1 .向栈中压入元素的操作是(先移动栈顶指针，后存入元素)。2 .时栈进行退栈时的操作是(先取出数据元素，后移动栈顶指针)。3 .在一个循环队列中，队首指针指向队首元素的(前一个位置.)。4 .从循环队列中删除一个元素时，其操作是(先移动队首指针.后取出元素)。5 .在具有n个单元的循环队列中，队满时共有(nJ)个元素。6 .一个栈的输入序列是12345,则栈的输出序列43512是(不可能的)<.7 .一个栈的输入序列是12345,则栈的输出序列12345是(可能的)。8 .在栈顶指针为HS的链栈中，判定校空的条件是(HS=null)。三.算法设计题：1 .设顺序表Va中的数据元数递增有序。试写算法，将X插入到顺序表的适当位置上，以保持该表的有序性.2 .试写一算法，实现顺序表的就地逆巴，即利用原表的存储空间耨线性表(al,a2an)逆置为(an.an-1.al).3 .瓜编写一个遍历及显示队列中元素的算法。publicvoidnextrder()inti,j=f11>nt;for(i=l;i<=size();i+)j=(j+1)%qucucArray.length;System.out.println(queuenrayj);)4 .设一循环队列QUeUe,只有头指针from,不设尾指针，另设一个内含元素个数的计数器，试写出相应的进队、出队算法。publicvoidEnQucuc(Tobj)Iif(cont=quccArray.length-1)队满Tp=(T()newObjcct(qucucArray.lcngth*2;inti=front+Ij=l.m=1:WhiIe(InVCoUni)p(j=qucucArray(i;i=(i+1)%queue11ay.length:j+;m+;queueAnay=p:front=0;count+;qcucAay(front+count)%qucucArray.length=obj;publicTDeQucucOIif(count=0)SyStem.ou.rimln("队列已空，无法Hl队！")；returnnull：front=(front+1)%qucucArray.length;count-;returnqucucArrayfront;I5 .设计一算法能判断一个算术表达式中的圆括号配对是否正确。(提示：对表达式进行扫描，凡遇到“(”就进栈，遇到“)”就退出栈顶的“(”，表达式扫描完毕时栈若为空则圆括号配对正豳。)publicstaticbleanmatching(char11exp)intstate=l.i=0:sequenceStack<Character>s=newsequenceStack<Characte>();/*定义一个顺序栈*/while(i<cxp.lcngth&&state=1)switch(expi)(cases.ush(expi);i+;break：1case')':Jif(!s.isEmply()if(s.gctHcad()='(')s.op();i+;elsestatc=O;)elsestatc=0;break:default:i+;break;if(s.isEmpty()&&state=I)returntrue;elsereturnfalse;4.7习题一.单项选择题1 .空串与空格串是相同的，这种说法B。A.正确B.不正确2 .串是一中特殊的线性表，其特殊性体现在B°A.可以顺序存储B.数据元素是一个字符C.可以链接存储D.数据元索可以是多个字符3 .设有两个串P和q,求q在P中首次出现的位置的运算称作A.连接B.模式匹配C.求子中D.求申长4 .设串s1=BCDEFG.s2=PQRST,.函数COn(x.y)返回X和y吊的连接申，subs(s,i,j)返回出s的从序号i的字符开始的j个字符组成的子串，Ien(三)返回返S的长度,则con(subs(s1,2,Ien(s2),SUbS($】Jen($2),2)的结果申是D.A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF5 .常对数组进行的两种基本悚作是A.建立与删除B.索引和修改C.查找和修改D.查找与索引6 .二维数组M的成员是6个字符(每个字符占一个存储单元，即一个字节)组成的串,行下标i的范围从。到8,列下标j的范围从I到10,则存放M至少需要2_个字节：M的第8列和第5行共占一一个字节。 A.90B.180C.240D.540 A.108B.114C.54D.60二.填空题(聘正确的答案填在相应的空中)1 .串的两种最法本的存储方式是顺序存储和徒式存储°2 .两个用相制的充分必要条件是长度相等I1.对应位世字符相等。3 .空出是。个展符的符,其长度等于C，空格串是由一个或多个空格字符组成的串,其长度等于空格字符个数.4 .设s='IAMAoTEACHER'.其长度是(口表示空格)三.算法设计题：1 .编写算法，实现remove(Stringt)操作，即从当前审中删除所仃和串I相同的子串.publicinirenove(stringt)(在当前串中删除所有与串t相等的子串，并返回甜除的次数inttimc=0.m;fbr(intj=()j<this.length-t.length+kj+)if(this.charsj=t.charsl)intx=0;fbr(inti=O;i<t.length;i+)if(this.charsj+ij=t.charsi)x+;elsebreak;)if(x=t.length)m=j;