二叉排序树的查找效率与二叉树的树形有关系吗_二叉排序树查找的缺点

2018秋招科大讯飞java笔试题（附参考答案）
　　作者：和风细雨

　　链接：2018秋招笔试科大讯飞java笔试试题_笔经面经_牛客网

　　来源：牛客网

　　前几天在讨论区看到牛友分享自己的秋招笔试试题，我也来分享一下自己做过的科大讯飞的Java笔试题，题量有点大哦~（附带参考答案）

　　单选题

　　1、下列关于继承的描述错误的是（ ）

　　A. 在Java中允许定义一个父类的引用，指向子类对象

　　B. 在Java中继承是通过extends关键字来描述的，而且只允许继承自一个直接父类

　　C. 在Java中抽象类之间也允许出现继承关系

　　D. 在Java中一个子类可以继承多个抽象类，在extends关键字后一次列出，用逗号隔开

　　参考答案：D

　　语法层面上抽象类和接口的区别

　　1）抽象类可以提供成员方法的实现细节，而接口中只能存在public abstract方法；

　　2）抽象类中的成员变量可以是各种类型的，而接口中的成员变量只能是public static final类型的；

　　3）接口中不能含有静态代码块以及静态方法，而抽象类可以有静态代码块和静态方法；

　　4）一个类只能继承一个抽象类，而一个类却可以实现多个接口。

　　2、以下关于接口的说法错误的是（ ）

　　A. 接口中的成员变量和成员方法只能是Public（或者缺省不写）

　　B. Java中的接口（interface）也继承了Object类

　　C. 实现接口的类必须全部实现接口中的方法

　　D. 接口中的方法只能有方法原型，不能有方法主体

　　参考答案：B

　　3、在一个请求分页系统中，采用NUR页面置换算法时，假如一个作业的页面走向为1,2,1,5,4,2,4,3,2,4。当分配给该作业的物理块数为3时，访问过程中命中的次数为（ ）

　　A. 3

　　B. 4

　　C. 5

　　D. 6

　　参考答案：B

　　主要的页面置换算法有:OPT、LRU、LFU、NUR以及FIFO。

　　FIFO:先进先出算法。

　　OPT:最佳置换算法。

　　LRU:最近最久未使用算法。

　　LFU:最近最少使用算法。

　　NUR:最近未使用算法。

　　4、下列程序的执行结果是（ ）

　　A. 99

　　B. 981

　　C. 198

　　D. b1

　　参考答案：D

　　5、TCP套接字函数中（ ）不会产生阻塞。

　　A. accept

　　B. bind

　　C. write

　　D. Read

　　参考答案：B

　　6、下面关于二叉排序树的说法错误的是（ ）

　　A. 在二叉排序树中，完全二叉树的查找效率最低

　　B. 对二叉排序树进行中序遍历，必定得到节点关键字的有序序列

　　C. 二叉排序树的平均查找长度是O(log2n)

　　D. 二叉排序树的查找效率与二叉树的树形有关

　　参考答案：A

　　解析：在二叉排序树中，完全二叉树的查找效率最高

　　7、多线程与多进程的主要区别之一就是共享资源，多线程是通过互斥访问来协调共享资源，在Windows系统中使用什么对象使多线程之间对资源互斥访问（ ）

　　A. SysTherad

　　B. InitTherad

　　C. Mutex

　　D. Select

　　参考答案：C

　　8、在FTP服务器上FTP主进程打开的端口为（ ）

　　A. 23

　　B. 20

　　C. 21

　　D. 22

　　参考答案：C

　　9、咖啡店销售系统具体需求为：咖啡店店员在卖咖啡时，可以根据顾客的要求加入各种配料，并根据加入配料价格的不同来计算总价。若要设计该系统可以应该采用（ ）进行设计

　　A. 装饰模式

　　B. 单例模式

　　C. 原型模式

　　D. 组合模式

　　参考答案：A

　　10、下列程序的执行结果是（ ）

　　A. 2 4

　　B. 3 4

　　C. 2

　　D. 2 3

　　参考答案：D

　　11、解决哈希冲突的链地址算法中，关于插入新的数据项的时间表述正确的是（ ）

　　A. 和数组已占用单元的百分比成正比

　　B. 和链表数目成正比

　　C. 和哈希表中项数成正比

　　D. 随装填因子线性增长

　　参考答案：D

　　散列表的装填因子定义为：α=填入表中的元素个数/散列表的长度

　　α是散列表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小。

　　12、下列关于Object类的说法，正确的是（ ）

　　A. 如果一个类显示地继承了其他类，则该类不再继承Object类

　　B. Error类不是从Object类派生出来的

　　C. 如果一个类是从Object类派生出来的，那么必须重写toString()和equals()方法

　　D. 一个类如果定义为abstract的，依然继承自Object类

　　参考答案：D

　　13、（ ）是调用者发出消息后，必须等待消息处理结束返回后，才能进行后续操作

　　A. 同步消息

　　B. 返回消息

　　C. 异步消息

　　D. 简单消息 参考答案：A

　　14、假设下列字符码中有奇偶校验位，但没有数据错误，采用偶校验的字符码是（ ）

　　A. 11010110

　　B. 11000001

　　C. 11001011

　　D. 11001001

　　参考答案：D

　　由于干扰，可能使位变为1，（为什么不变0？）这种情况，我们称为出现了“误码”。我们把如何发现传输中的错误，叫“检错”。发现错误后，如何消除错误，叫“纠错”。最简单的检错方法是“奇偶校验”，即在传送字符的各位之外，再传送1位奇/偶校验位。可采用奇校验或偶校验。

　　奇校验：所有传送的数位（含字符的各数位和校验位）中，“1”的个数为奇数，如：

　　1 0110，0101

　　0 0110，0101

　　偶校验：所有传送的数位（含字符的各数位和校验位）中，“1”的个数为偶数，如：

　　1 0100，0101

　　0 0100，0101

　　奇偶校验能够检测出信息传输过程中的部分误码（奇数位误码能检出，偶数位误码不能检出），同时，它不能纠错。在发现错误后，只能要求重发。但由于其实现简单，仍得到了广泛使用。有些检错方法，具有自动纠错能力。如循环冗余码（CRC）检错等。

　　15、下列各序列中不是堆的是（ ）

　　A. (9,8,5,3,4,2,1)

　　B. (9,4,5,8,3,1,2)

　　C. (9,5,8,4,3,2,1)

　　D. (9,8,5,4,3,1,2)

　　参考答案：B

　　解析：堆要求父节点的元素值必须全部大于或者小于子节点的元素值，A、C和D都是符合条件的大根堆，B的第三层的元素8大于第二层的父元素值4，不符合堆的条件，故而本题答案为B选项。

　　16、在Java中，以下哪个可以与函数public int A()(…)构成重载（ ）

　　A. public void A()(…)

　　B. public int A(int m)(…)

　　C. public void A(int n)(…)

　　D. public static int A()(…)

　　参考答案：B

　　17、现有如下代码段：

　　假设n>=0，则其时间复杂度应为（ ）

　　A. O(log2n)

　　B. O(nlog2n)

　　C. O(n)

　　D. O(n^2)

　　参考答案：A

　　18、下列程序输出的结果为（ ）

　　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.

　　该用户的用户名和密码分别是’Tom’和’123’，执行该存储过程语句和结果正确的是：（ ）

　　A.

　　结果：1

　　B.

　　结果：1

　　C.

　　结果：0

　　D.

　　结果：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()方法导致当前线程放弃对象的锁（线程暂停执行），进入对象的等待池（wait pool），只有调用对象的notify()方法（或notifyAll()方法）时才能唤醒等待池中的线程进入等锁池（lockpool），如果线程重新获得对象的锁就可以进入就绪状态。

　　9、下列等价类的叙述中正确的是（ ）

　　A. 若输入条件为一个布尔变量，则可以确定一个有效等价类和一个无效等价类

　　B. 若输入条件为一个逻辑量，则可为每一个输入值确定一个有效等价类，并针对这组值确定一个无效等价类

　　C. 若输入条件规定了“必须如何”的条件，则可以确定一个有效等价类和两个无效等价类

　　D. 若输入条件规定了取值的上下限，则可以确定一个有效等价类和两个无效等价类

　　参考答案：A、B、D

　　划分等价类的6条原则：

　　（1）在输入条件规定了取值范围或值的个数的情况下，可以确立一个有效等价类和两个无效等价类

　　（2）在输入条件规定了输入值的集合或者规定了“必须如何”的条件的情况下，可以确立一个有效等价类和一个无效等价类

　　（3）在输入条件是一个布尔量的情况下，可确定一个有效等价类和一个无效等价类

　　（4）在规定了输入数据的一组值（假定n个），并且程序要对每一个输入值分别处理的情况下，可确立n个有效等价类和一个无效等价类

　　（5）在规定了输入数据必须遵守的规则的情况下，可确立一个有效等价类（符合规则）和若干个无效等价类（从不同角度违反规则）

　　（6）在确知已划分的等价类中，各元素在程序处理中的方式不同的情况下，则再将该等价类进一步地划分为更小的等价类

　　简答题

　　等价类划分法应如何取值？与边界值法取值有何不同？

　　答：

　　(1)若输入条件规定了取值范围，且取值范围上、下限之间的数据是有意义的数据，则可以确立一个有效等价类和两个无效等价类。

　　(2)若输入条件规定了“必须如何”的条件，则可确立一个有效等价类和一个无效等价类。

　　(3)若输入条件是一个布尔型量，则可以确定一个有效等价类和一个无效等价类。

　　(4)若输入条件是一个逻辑型量，则可为每一个输入值确立一个有效等价类且软件要对每个输入值分别进行处理，则可为每一个值确立一个有效等价类，此外还要针对这组值确立一个无效等价类。

　　更多名企笔试真题解析、面试经验交流、招聘信息内推，尽在牛客！

　　求职之前，先上牛客！快快下载拿offer！

　　牛客APP下载_C++Java前端经典笔试面试题库_牛客网

　　编程题

　　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支队伍参加。经过激烈的角逐，有机会参与总决赛的队伍已经决出。

　　协会对比赛的规则进行了调整，以便使得比赛更具有观赏性。 总决赛的参赛队伍为n支，n为偶数； 进入前1/2的队伍才有资格进入淘汰赛； 队伍按积分排名，具体规则为：胜一场积3分；平一场积1分；负一场积0分。队伍首先按积分降序排列，积分相同按净胜球数降序排列，仍然相同的按进球数降序排列。 基于上述规则，尚未出现有排名歧义的情况发生。

　　随着赛程的进行，目前各个队伍对战的结果已经确定了，小B负责确定进入淘汰赛的名单，她向你求助，你能帮她吗？

　　输入 测试数据有多组，每组测试数据的第一行为一个整数n（1=< n <=50），为参与总决赛的球队数，随后的n行为球队的名字，由不超过30个的大小写拉丁字母构成。随后的n*(n-1)/2行为赛事的开展情况，每行的格式为name1-name2 num1:num2，表示两支队伍的比分情况（1=<num1, num2<=100）。确保不会有两支队伍同名，也不会出现队伍自己通自己比赛的情况，且每场比赛仅出现一次。

　　输出 对每组测试数据，输出n/2行，为按字母序排列的进入淘汰赛的n/2支队伍的名单，每个名字在单独的行中输出。

　　样例输入 4 A B C D A-B 1:1 A-C 2:2 A-D 1:0 B-C 1:0 B-D 0:3 C-D 0:3 2 a A a-A 2:1

　　样例输出 ADa

　　3、课程冲突

　　时间限制：C/C++语言2000MS；其他语言4000MS

　　内存限制：C/C++语言65536KB；其他语言589824KB

　　题目描述：

　　小明是一名学生，又到了学校的选课时间，他想选一些课程学习，已知课程开课时间都在每周一到周五之内，早上4讲课，下午4讲课，晚上2讲课。

　　小明担心选课时间上有所冲突。所以他希望可以对课程时间进行检查。

　　输入 首先输入一个整数n（0<n<=100），表示小明选课总数。 之后输入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

　　Input Sample 2 3 11 204521 23 204522 43 204531

　　Output Sample 2 YES