腾讯CSIG笔试题
一、选择题
如果一棵二叉树结点的先根遍历序列是A B C，后根遍历序列是C B A，则该二叉树结点的中根遍历序列（D ）
A. 必为A B C B. 必为A C B
C. 必为B C A D. 不能确定
若在线性表中采用折半查找法查找元素，该线性表应该（C）
A.元素排列顺序无关，但必须采用连续存储结构
B.元素排列顺序无关，但必须采用链式存储结构
C.元素按值排序，且采用连续存储结构
D.元素按值排序，且采用链式存储结构
下列关于this指针的说法正确的是（B ）
A）this指针存在于每个函数之中
B）在类的非静态函数中this指针指向调用该函数的对象
C）this指针是指向虚函数表的指针
D）this指针是指向类的函数成员的指针
下列的各类函数中，不是类的成员函数。（ C ）
A 构造函数 B 析构函数 C 友元函数 D 拷贝构造函数
下列for循环的循环体执行次数为（ A）
for(int i=5, j=-5; i=j=0; i--, j++){
}
A 0 B1 C 无限 D 5
UNIX中， 函数fork 在父进程中得到的结果是 (1) , 在子进程中得到的结果是(2) ,fork后子进程继承了父进程的(3) , 父进程可以使用_(4)_函数得到子进程终止的状态 ( )
A (1) 0 (2) 0 (3) 连接的共享内存 (4) wait
B (1) 0 (2) >0 的pid (3) 环境(4) wait
C (1) >0的pid (2) 0 (3) 锁资源 (4) waitpid
D (1) >0的pid (2) 0 (3) 文件句柄 (4) waitpid
TCP的三次握手过程，accept发生在哪个时段？（ C ）
A. Server收到SYN之后
B. Server发出SYN+ACK之后
C. Server收到ACK之后
D. 以上皆可能
对IP数据报进行分片的主要目的是（C ）。
A. 适应各个物理网络不同的地址长度 B. 拥塞控制
C. 适应各个物理网络不同的MTU长度 D.流量控制
关于SQL优化，以下说明哪个是错误的（ B ）
A.类似分页功能的SQL，建议先用主键关联，然后返回结果集，效率会高很多
B.通常情况下，join的性能比较差，建议改造成子查询写法
C.多表联接查询时，关联字段类型尽量一致，并且都要有索引
D.尽可能不使用TEXT/BLOB类型，确实需要的话，建议拆分到子表中，不要和主表放在一起，避免SELECT*的时候读性能太差
二、编程题
请实现一个函数, 返回给定单向链表的长度.
package com.leetecode.top100.linkedlist.createnode;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class CreateNode {
static class Node{
private Integer value;
private Node node;
public Node(Integer value) {
this.value = value;
}
public void setValue(Integer value) {
this.value = value;
}
public void setNode(Node node) {
this.node = node;
}
public Integer getValue() {
return value;
}
public Node getNode() {
return node;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine()); //单链表结点个数
int count=0;
Node head = new Node(count);
Node curNode=head;
if(curNode==null){
return;
}
while(curNode!=null&&count<n){
Node node = new Node(++count);
curNode.setNode(node);
curNode=node;
}
while(head!=null){
System.out.print(head.getValue()+"->");
head=head.getNode();
}
}
}
给定一个字符串，找出其中一个最长的子串，子串中的字符都是唯一的
package com.leetecode.top100.string.longsubstring;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
public class LongSubstring {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine(); //输入字符串
System.out.println(longSubstring(str));
}
public static int longSubstring(String str){
if(str==null||str.length()==0){
return 0;
}
int i=0,count=0,j=0;
HashSet<Character> set = new HashSet<>();
while(i<str.length()){
if(!set.contains(str.charAt(i))){ //集合不包含该元素
set.add(str.charAt(i));
count=Math.max(set.size(),count);
i++;
}else { //集合中包含该元素
set.remove(str.charAt(j));
j++;
}
}
return count;
}
}
3.有若干个大数组，每个数组里面都存放了超过千万级别的无符号整数(unsigned int)，怎么快速求出这些大数组的交集？
package com.leetecode.top100.array.twoarraycontain;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
//求两个数组的交集
public class TwoArrayContain {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] str1 = br.readLine().trim().split(" ");
String[] str2 = br.readLine().trim().split(" ");
System.out.println(twoArrayContain(str1,str2));
}
public static HashSet<String> twoArrayContain(String[] str1,String[] str2){
if(str1==null|| str2==null){
return null;
}
HashSet<String> set = new HashSet<>(Arrays.asList(str1));
set.retainAll(Arrays.asList(str2));//取交集方法retainAll()；如果存在交集元素，set保存交集；否则set是空
return set;
}
}
4.给定一个100MB的文件words.txt，文件中每行对应一个句子，请开发一个接口实现输入词联想的功能，程序运行环境为linux,运行内存为100MB，要求接口时延尽可能小。
假设给定的文件内容如下：
abcdefg
abdefg
aabefg
babefg
假设输入词是ab，则应该输出abcdefg和abdefg
全志科技HR面33人在聊