【Java笔试】OYO校招Java工程师|牛客平台，算法：字符串翻转。附选择题解析

2022-05-13 00:26:04

文章目录

1、Java笔试算法题：字符串翻转
2、单选题：

2.1、同一进程下的多个线程可以共享哪一种资源：data section
2.2、一个树形的叶结点在前序遍历和后序遍历下，可以相同的相对位置出现（√ ）

说理证明：
举例证明：

2.3、下列哪一个命令为删除 sample 数据库的 tb_ame 表（D：drop table sample. tb_ ame）
2.4、在重载运算符函数时，下面（->）运算符必须重载为类成员函数形式
2.5、在对一组记录（54，38，96，23，15，72，60，45，83 ）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较（3）次

1、Java笔试算法题：字符串翻转

给出字符串"This is nowcoder"，要求完全翻转该字符串，可以用Java、Python、C++，不能用C，笔试结束后，我翻了很多CSDN网上的代码，都不对。
OYO酒店笔试题的这个代码，要求模板就有一个函数public （示范代码里没有static，调试的时候别忘了加上）String reverseString(String iniString)，没有主函数，还得自己写public static void main(String[] args)
网上答案大多误人子弟，于是我把我的代码放在这边，以供学习。
字符串翻转Java代码

import java.util.*;

public class Reverse {

    public static void main(String[] args){

        String str = "This is nowcoder";

        String[] strs = str.split("");

        if (strs.length==0){

            System.out.println("字符串为空");

        }

        else{

            StringBuffer sb = new StringBuffer();

            for(int i=0;i<strs.length;i++){

                strs[i]=reverseString(strs[i]);

            }

            sb.append(strs[0]);

            if(strs.length>1){

                for(int i=1 ; i<strs.length;i++){

                    sb.append("");

                    sb.append(strs[i]);

                }

            }

            System.out.println(sb);

        }

    }

    public static String reverseString(String iniString) {

        char[] cs = iniString.toCharArray();

        StringBuffer sb =new StringBuffer();

       for(int i =cs.length-1;i>=0;i--)

       {

           sb.append(cs[i]);

       }

        return sb.toString();

    }

}

//本人完全通过

2、单选题：

2.1、同一进程下的多个线程可以共享哪一种资源：data section

正确答案：data section
stack 栈（私有）、heap堆（共享）
data section 数据段 (线程共享)
register set 寄存器组（私有）
thread ID 线程ID。（私有）

线程共享的环境包括：进程代码段、进程的公有数据(利用这些共享的数据，线程很容易的实现相互之间的通讯)、进程打开的文件描述符、信号的处理器、进程的当前目录和进程用户ID与进程组ID。
进程拥有这许多共性的同时，还拥有自己的个性。有了这些个性，线程才能实现并发性。这些个性包括：

1.线程ID
每个线程都有自己的线程ID，这个ID在本进程中是唯一的。进程用此来标识线程。
2.寄存器组的值
由于线程间是并发运行的，每个线程有自己不同的运行线索，当从一个线程切换到另一个线程上时，必须将原有的线程的寄存器集合的状态保存，以便将来该线程在被重新切换到时能得以恢复。
3.线程的堆栈（线程之间共享堆dui，每个线程独有栈zhan）
堆栈是保证线程独立运行所必须的。
线程函数可以调用函数，而被调用函数中又是可以层层嵌套的，所以线程必须拥有自己的函数堆栈，使得函数调用可以正常执行，不受其他线程的影响。
4.错误返回码
由于同一个进程中有很多个线程在同时运行，可能某个线程进行系统调用后设置了errno值，而在该线程还没有处理这个错误，另外一个线程就在此时被调度器投入运行，这样错误值就有可能被修改。
所以，不同的线程应该拥有自己的错误返回码变量。
5.线程的信号屏蔽码
由于每个线程所感兴趣的信号不同，所以线程的信号屏蔽码应该由线程自己管理。但所有的线程都共享同样的信号处理器。
6.线程的优先级
由于线程需要像进程那样能够被调度，那么就必须要有可供调度使用的参数，这个参数就是线程的优先级。

重点：线程共享堆，独有栈

一个进程中的所有线程共享该进程的地址空间，但所有线程有各自独立的（/私有的）栈(stack)，Windows线程的缺省堆栈大小为1M。
堆(heap)的分配与栈有所不同，一般是一个进程有一个C运行时堆，这个堆为本进程中所有线程共享，windows进程还有所谓进程默认堆，用户也可以创建自己的堆。
用操作系统术语，线程切换的时候实际上切换的是一个可以称之为线程控制块的结构（TCB?），里面保存所有将来用于恢复线程环境必须的信息，包括所有必须保存的寄存器集，线程的状态等。

堆：是线程之间共有的空间，分全局堆和局部堆。全局堆就是所有没有分配的空间，局部堆就是用户分配的空间。堆在操作系统对进程初始化的时候分配，运行过程中也可以向系统要额外的堆，但是记得用完了要还给操作系统，要不然就是内存泄漏。

栈：是个线程独有的，保存其运行状态和局部自动变量的。栈在线程开始的时候初始化，每个线程的栈互相独立，因此，栈是　thread safe的。操作系统在切换线程的时候会自动的切换栈，就是切换ＳＳ／ＥＳＰ寄存器。栈空间不需要在高级语言里面显式的分配和释放。

Java [来源百度百科-堆栈概念]

栈(stack)与堆(heap)都是Java用来在Ram中存放数据的地方。与C++不同，Java自动管理栈和堆，程序员不能直接地设置栈或堆。

栈的优势是，存取速度比堆要快，仅次于直接位于CPU中的寄存器。但缺点是，存在栈中的数据大小与生存期必须是确定的，缺乏灵活性。另外，栈数据在多个线程或者多个栈之间是不可以共享的，但是在栈内部多个值相等的变量是可以指向一个地址的，详见第3点。
3、堆的优势是可以动态地分配内存大小，生存期也不必事先告诉编译器，Java的垃圾收集器会自动收走这些不再使用的数据。但缺点是，由于要在运行时动态分配内存，存取速度较慢。[自己加的]堆是线程共享的。

2.2、一个树形的叶结点在前序遍历和后序遍历下，可以相同的相对位置出现（√ ）

对，or ，错？—答案：对

说理证明：

任意两个叶子节点，一定会有一个最近公共祖先T，并且两个节点一个在T的左子树中，一个在T的右子树中，由前序遍历的访问顺序和后序遍历的访问遍历知，他们两个叶子节点在前序遍历和后序遍历中的相对位置不会有改变。链接来源：牛客网

举例证明：

先序遍历：12345
后序遍历；34251
叶子结点分别是 3,4,5
而在先序遍历中，三个叶子结点的顺序就是345，后序遍历三个叶子结点的顺序仍是345。即所谓的相同的相对位置。

2.3、下列哪一个命令为删除 sample 数据库的 tb_ame 表（D：drop table sample. tb_ ame）

删除表首先得确定是哪个数据库的，drop table 数据库名.表名
或者先选定数据库后删除使用 drop table 表名

C：是进入该数据库删除数据库内的表文件
D：是在数据库外部也就是说可以不用进去数据库就可以删除（所以D对）
B：DELETE 语句，DELETE 语句用于删除表中的行。

语法：DELETE FROM 表名称 WHERE 列名称 = 值
Person:

LastName	FirstName	Address	City
Gates	Bill	Xuanwumen	10
Wilson	Fred	Zhongshan	23

删除某行
“Fred Wilson” 会被删除：

DELETE FROM Person WHERE LastName = 'Wilson'

结果:

LastName	FirstName	Address	City
Gates	Bill	Xuanwumen	10

A：删除所有行
可以在不删除表的情况下删除所有的行。这意味着表的结构、属性和索引都是完整的：

DELETE FROM table_name

或者：

DELETE * FROM table_name

2.4、在重载运算符函数时，下面（->）运算符必须重载为类成员函数形式

A. +
B. ++
C. -
D. ->

答案：D
只能使用成员函数重载的运算符有：=、()、[]、->、new、delete。
出自《C++ Primer(Fith edition)》P.726

不能重载的5个： “. ” “ .* ” “::” “sizeof” “?:”
前2个不能被重载是保证能正常访问成员，域运算和sizeof不能被重载是因为运算对象是类而不是对象

[]、()、->、=这几个运算符如果要重载,必须重载为成员函数
只能使用成员函数重载，4个： “=” “[]” “->” “()”
只能使用成员函数重载是为了防止出现： 1 = x， 1[x], 1->x, 1(x)这样的合法语句

2.5、在对一组记录（54，38，96，23，15，72，60，45，83 ）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较（3）次

A.5
B.4
C.6
D.3

解析：
当轮到60时，局面时15，23，38，54，72，96，60，45，83
根据代码，寻找插入位置，要从第7位向前一位一位比较，当X(=60)比遇到的a[j]大时，结束比较循环。
那么一路上，60要与96、72、54比较，当发现60比54大时，结束循环，共比较了3次。

VisuAlgo.net/zh
数据结构和算法动态可视化 (Chinese)
此处推荐算法可视乎工具，但插入排序的数值被限制为上界50，有点不方便，看到此文的朋友如果有推荐可以评论。