数据结构(Java版)-小测验.doc

《数据结构(Java版)-小测验.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《数据结构（Java版）》课程测验一.填空题（10分，每空2分）1.声明抽象数据类型的目的是_使数据类型的定义和实现分离，使一种定义有多种实现_。2.右侧数据存储结构声明为table可声明为数组或顺序表，元素为结点或单链表，声明为以下4种之一Nodetable[];SinglyLinkedListtable[];SeqList>table;SeqList>table;3.中缀表达式A+B*(C-D*(E+F)/G+H)-(I-J)*K的后

2、缀表达式为__ABCDEF+*G/-H+*+IJ-K*-__。4.设一个顺序循环队列容量为60，当front=47，rear=23时，该队列有_36__个元素。5.n+100lgn的时间复杂度是_n_________________________。二.问答题（20分，每题4分）1.什么是数据结构？数据结构的概念包括哪三部分？略2.什么是算法？如何描述算法？怎样衡量算法的性能？略3.Node类能否声明以下深拷贝构造方法?为什么？PublicNode(Nodep){this(p.data,p.next

3、)}不能；Node链接地址错；4.什么是串？串和线性表的概念上有何差别？串操作的主要特点有哪些？略5.Java语言有哪几种字符串类？存储结构分别是怎样的？略三.程序阅读和改错题（10分）1.下列removeAll()方法欲删除target串中所有与pattern匹配的子串。publicstaticStringBufferremoveAll(StringBuffertarget,Stringpattern){intm=target.length(),n=pattern.length();inti=targe

4、t.indexOf(pattern),k=i;while(k!=-1){intj=k+n;k=target.indexOf(pattern,j);while(k>0&&j

5、

6、k<0&&j

7、ntln(removeAll(target,"abc"));②removeAll()方法怎样实现所求功能？（3分）③算法存在什么错误？如何改正？（3分）答：①运行结果为“ababddbcdabcabc”，正确的运行结果是“ababdd”。②removeAll()方法删除指定StringBuffer串的全部匹配子串操作，算法将待移动若干字符一次移动到位，从而提高算法效率。算法描述如下图所示，说明如下：l初始状态，设i表示首次匹配子串的首字符下标，如图（a）所示。l再设j表示i匹配子串之后的字符下标，k表示下

8、次匹配子串的首字符下标，如图（a）所示，将从j～k-1之间的若干字符向前移动到i处，完成删除一个匹配子串操作。l重复上一步操作，如果j=k，表示有两个连续的匹配子串，则没有移动字符，如图（b）所示；直到k=-1，表示其后没有匹配子串，则将从j开始至串尾的若干字符全部向前移动到i处，如图（c）所示。③算法存在错误，删除后没将字符串长度减少，导致仍然输出原长度字符串。改正：方法体return语句前增加以下一句：target.setLength(i);一.程序填空题（10分）1.程序填空：（10分）/【例1.2

9、】求两个整数的最大公约数。publicclassEx102_Gcd{publicstaticintgcd1(inta,intb)//返回a与b的最大公因数{while(b!=0){①______________;a=b;b=temp;}returna;}publicstaticintgcd2(②____________)//返回a,b的最大公因数，递归方法{if(b==0)returna;if(a<0)③______________;if(b<0)④_____________;returngcd2(⑤__

10、________);}publicstaticvoidmain(Stringargs[]){inta=12,b=18,c=24;System.out.println("gcd1("+a+","+b+","+c+")="+gcd1(gcd2(a,b),c));}}/*程序运行结果如下:gcd1(12,18,24)=6*/①inttemp=a%b;②inta,intb③returngcd2(-a,b)④returngcd2(a,-