x=2*x;
假设n>=0，则其时间复杂度应为（）
A.O（log2n）
B.O（nlog2n）
C.O（n）
D.O（n^2）
参考答案：
A
18、下列程序输出的结果为（）
inti=11,j=5;
switch（i/j）
{
case3;
j+=i;
case2;
j+=4;
case4;
j+=5;
case1;
j+=1;
break;
}
System.out.println（j）;
A.9
B.14
C.5
D.15
参考答案：
D
j=5+4+5+1=15
19、有关构造方法，下列叙述正确的是（）
A.默认的构造方法可以具有参数
B.假如一个类缺少没有参数的构造方法，但是有其它的构造方法，，则编译器生成一个缺省的构造方法
C.编译器总会给每一个类生成一个无参的缺省构造方法
D.默认的构造方法初始化了在类中声明的实例变量
参考答案：
D
解析：
A、默认构造方法可以没有参数，也可以有参数，但是每个参数都必须有默认值。
B、有了就不会再生成缺省的了。
C、如果没有默认的构造方法，编译器才会为类生成一个无参的缺省构造方法，不是总是生成的，是有条件的。
D、默认的构造方法不初始化变量。
20、在UML中，（）体现了一种contains-a的关系
A.聚合关系
B.实现关系
C.组合关系
D.关联关系
参考答案：
C
UML定义的关系主要有六种：
依赖、类属、关联、实现、聚合和组合。
组合也是关联关系的一种特例，他体现的是一种contains-a的关系，这种关系比聚合更强，也称为强聚合；他同样体现整体与部分间的关系，但此时整体与部分是不可分的，整体的生命周期结束也就意味着部分的生命周期结束；比如你和你的大脑；表现在代码层面，和关联关系是一致的，只能从语义级别来区分。
21、一个上下文无关文法一般是由一组非终结符号、一组终结符号，一个开始符号和一组产生式构成，那么产生式是用于定义（）的一种规则
A.逻辑推理
B.语义成分
C.词法成分
D.语法成分
参考答案：
D
多选题
1、可唯一确定一棵二叉树的是（）
A.给定一棵二叉树的后序和中序遍历序列
B.给定一棵二叉树的先序和后序遍历序列
C.给定一棵二叉树的先序和中序遍历序列
D.给定先序、中序和后序遍历序列中的任意一个即可
参考答案：
A、C
2、下面哪些是使用分治法的前提条件（）
A.该问题具有最优子结构性质
B.原问题和子问题求解方法相同
C.子问题必须是一样的
D.子问题之间不包含公共的子问题
参考答案：
ABD
3、下面关于Java的说法正确的是（）
A.一个类只能定义一个构造函数
B.类中的构造函数不可省略
C.构造函数必须与类同名
D.普通类方法可以与类同名
参考答案：
C、D
4、有关单例模式的说法中正确的是（）
A.用户无法通过new方式实例化单例类
B.单例模式属于创建型模式
C.单例模式用于多线程应用程序
D.违背了单一职责原则
参考答案：
A、B、C
5、下面的存储过程实现用户验证功能，如果不成功，返回0，成功则返回1.
CREATEPROCEDUREVALIDATE@USERNAMECHAR,@PASSWORDCHAR,@LEGALBITOUTPUTASIFEXISTS（SELECT*FROMRENWHERESNAME=@USERNAMEANDPWD=@PASSWORD）
SELECT@LEGAL=1
ELSE
SELECT@LEGAL=0
该用户的用户名和密码分别是’Tom’和’123’，执行该存储过程语句和结果正确的是：
（）
A.declare@LEGALbit
execdbo.validate’Tom’,’123’,@LEGALOUTPUT
SELECT@LEGAL
结果：
1
B.declare@LEGALbit
execdbo.validate’TomCat’,’123’,@LEGALOUTPUT
SELECT@LEGAL
结果：
1
C.declare@LEGALbit
execdbo.validate’Tom’,’123’,@LEGALOUTPUT
SELECT@LEGAL
结果：
0
D.declare@LEGALbit
execdbo.validate’TomCat’,’123’,@LEGALOUTPUT
SELECT@LEGAL
结果：
0
参考答案：
A、D
6、Spring有哪三个核心组件（）
A.Beans
B.Context
C.IOC
D.Core
参考答案：
A、B、D
7、下列关于视图的说法中正确的是（）
A.对视图的使用与表一样，也可以进行插、查、删、改操作
B.视图与表一样，也存储着数据
C.对视图的操作，是最终都要转化成对基本表的操作
D.可以根据数据库表和自由表建立视图
参考答案：
C、D
8、关于wait（）和sleep（）说法正确的是（）
A.wait（）和sleep（）都会释放锁
B.sleep（）可以在任何地方使用
C.wait（）只能在方法或者语句块中使用
D.wait（）和sleep（）都是Thread类的方法
参考答案：
B、C
sleep（）方法（休眠）是线程类（Thread）的静态方法，调用此方法会让当前线程暂停执行指定的时间，
将执行机会（CPU）让给其他线程，但是对象的锁依然保持，因此休眠时间结束后会自动恢复（线程回到就绪状态，请参考第66题中的线程状态转换图）。
wait（）是Object类的方法，调用对象的wait（）方法导致当前线程放弃对象的锁（线程暂停执行），进入对象的等待池（waitpool），只有调用对象的notify（）方法（或notifyAll（）方法）时才能唤醒等待池中的线程进入等锁池（lockpool），如果线程重新获得对象的锁就可以进入就绪状态。
9、下列等价类的叙述中正确的是（）
A.若输入条件为一个布尔变量，则可以确定一个有效等价类和一个无效等价类
B.若输入条件为一个逻辑量，则可为每一个输入值确定一个有效等价类，并针对这组值确定一个无效等价类
C.若输入条件规定了“必须如何”的条件，则可以确定一个有效等价类和两个无效等价类
D.若输入条件规定了取值的上下限，则可以确定一个有效等价类和两个无效等价类
参考答案：
A、B、D
划分等价类的6条原则：
（1）在输入条件规定了取值范围或值的个数的情况下，可以确立一个有效等价类和两个无效等价类
（2）在输入条件规定了输入值的集合或者规定了“必须如何”的条件的情况下，可以确立一个有效等价类和一个无效等价类
（3）在输入条件是一个布尔量的情况下，可确定一个有效等价类和一个无效等价类
（4）在规定了输入数据的一组值（假定n个），并且程序要对每一个输入值分别处理的情况下，可确立n个有效等价类和一个无效等价类
（5）在规定了输入数据必须遵守的规则的情况下，可确立一个有效等价类（符合规则）和若干个无效等价类（从不同角度违反规则）
（6）在确知已划分的等价类中，各元素在程序处理中的方式不同的情况下，则再将该等价类进一步地划分为更小的等价类
简答题
等价类划分法应如何取值？
与边界值法取值有何不同？
答：
（1）若输入条件规定了取值范围，且取值范围上、下限之间的数据是有意义的数据，则可以确立一个有效等价类和两个无效等价类。
（2）若输入条件规定了“必须如何”的条件，则可确立一个有效等价类和一个无效等价类。
（3）若输入条件是一个布尔型量，则可以确定一个有效等价类和一个无效等价类。
（4）若输入条件是一个逻辑型量，则可为每一个输入值确立一个有效等价类且软件要对每个输入值分别进行处理，则可为每一个值确立一个有效等价类，此外还要针对这组值确立一个无效等价类。
编程题
1、争吵
时间限制：
C/C++语言2000MS；其他语言4000MS
内存限制：
C/C++语言65536KB；其他语言589824KB
题目描述：
有n 个人排成了一行队列，每个人都有一个站立的方向：
面向左或面向右。
由于这n 个人中每个人都很讨厌其他的人，所以当两个人面对面站立时，他们会发生争吵，然后其中一个人就会被踢出队列，谁被踢出队列都是有可能的。
我们用字符L 来表示一个面向左站立的人，用字符R 来表示一个面向右站立的人，那么这个队列可以用一个字符串描述。
比如RLLR 就表示一个四个人的队列，其中第一个人和第二个人是面对面站立的。
他们发生争吵后队列可能会变成LLR，也可能变成RLR；若变成RLR，则第一个人与第二个人还会发生争吵，队列会进一步变成LR 或者RR。
若在某个时刻同时可能有很多的争吵会发生时，接下来只会发生其中的一个，且任意一个都是有可能发生的。
你想知道经过一系列的争吵后，这个队列最少会剩下多少人？
输入
第一行包含一个有字符L 和R 构成的字符串。
1≤字符串长度≤ 105
输出
输出队列中最少会剩下多少人。
样例输入
LRRLRL
样例输出
2
Hint
一种可能的变化情况是这样的:
LRRLRL->LRLRL->LRRL->LRL->LR
2、球赛
时间限制：
C/C++语言1000MS；其他语言3000MS
内存限制：
C/C++语言65536KB；其他语言589824KB
题目描述：
大学生足协决定举办全国性的大学生足球赛，由每个学校派遣一支队伍代表该校参赛。
比赛分区分为几个赛区进行，最终的总决赛中，将有不超过n支队伍参加。
经过激烈的角逐，有机会参与总决赛的队伍已经决出。
协会对比赛的规则进行了调整，以便使得比赛更具有观赏性。
1. 总决赛的参赛队伍为n支，n为偶数；
2. 进入前1/2的队伍才有资格进入淘汰赛；
3. 队伍按积分排名，具体规则为：
胜一场积3分；平一场积1分；负一场积0分。
队伍首先按积分降序排列，积分相同按净胜球数降序排列，仍然相同的按进球数降序排列。
4. 基于上述规则，尚未出现有排名歧义的情况发生。
随着赛程的进行，目前各个队伍对战的结果已经确定了，小B负责确定进入淘汰赛的名单，她向你求助，你能帮她吗？
输入
测试数据有多组，每组测试数据的第一行为一个整数n（1=随后的n*（n-1）/2行为赛事的开展情况，每行的格式为name1-name2num1:
num2，表示两支队伍的比分情况（1=确保不会有两支队伍同名，也不会出现队伍自己通自己比赛的情况，且每场比赛仅出现一次。
输出
对每组测试数据，输出n/2行，为按字母序排列的进入淘汰赛的n/2支队伍的名单，每个名字在单独的行中输出。
样例输入
4
A
B
C
D
A-B1:
1
A-C2:
2
A-D1:
0
B-C1:
0
B-D0:
3
C-D0:
3
2
a
A
a-A2:
1
样例输出
A
D
a
3、课程冲突
时间限制：
C/C++语言2000MS；其他语言4000MS
内存限制：
C/C++语言65536KB；其他语言589824KB
题目描述：
小明是一名学生，又到了学校的选课时间，他想选一些课程学习，已知课程开课时间都在每周一到周五之内，早上4讲课，下午4讲课，晚上2讲课。
小明担心选课时间上有所冲突。
所以他希望可以对课程时间进行检查。
输入
首先输入一个整数n（0之后输入n行选课信息，每行选课信息有2个数字。
第一个数字表示开课时间，开课时间用2位数表示，前一位用0到4表示周一至周五，后一位用0到9表示从早到晚顺序第几讲课，如12表示礼拜二第三讲课。
01表示礼拜一第二讲课。
每行第二个数字表示课程代码，如：
204521。
课程代码为6位数字。
输入课程代码均不重复。
输出
如果没有冲突课程，输出YES。
如果有冲突课程，也就是同一个时间多于一节课，输出所有冲突的课程。
输出有多行，如果多个不同的上课时间都有课程冲突，按照周一到周五，早上到晚上时间先后，按行输出冲突信息。
在同一行内，先输出冲突时间，之后输出这一时间的所有课程，输出课程的顺序为输入中这些课程出现的顺序，课程之间以空格分隔，不要在行末输出多余的空格。
样例输入
5
01 204521
23 204523
22 204526
01 204528
22 204527
样例输出
01 204521 204528
22 204526 204527
Hint
InputSample2
3
11204521
23204522
43204531
OutputSample2
YES
升级会员 