笔试真题刷题平台
精选近几年名企笔试真题，笔试之前刷刷真题，有备无患
一、单选题
若12*25=311成立， 则用的是几进制?
A 7
B 8
C 9
D 11
C
（1*n+2）*(2*n+5)=3*n2 +1*n+1
n2-8n-9=0
n=9 n=-1
某32位系统下, C++程序如下所示，sizeof 的值应为？
char str[] = “http://www.renren.com” （长度为21）
char *p = str ;
请计算
sizeof (str ) = ？（1）
sizeof ( p ) = ？（2）
void Foo ( char str[100]){
sizeof( str ) = ？（3）
}
void *p = malloc( 100 );
sizeof ( p ) = ？（4）
A 22, 22, 100, 100
B 4, 4, 4, 4
C 22, 4, 4, 4
D 22, 4, 100, 4
C
有字符序列（Q,H,C,Y,P,A,M,S,R,D,F,X）,新序列（F,H,C,D,P,A,M,Q,R,S,Y,X）是下列（）排序算法一趟扫描结果。
A 堆排序
B 快速排序
C 希尔排序
D 冒泡排序
B
快速排序选择QMX中间值Q作为分割点，经过一轮排序以后Q前面都是小于Q的，Q后面都是大于Q的。
关于排序算法的以下说法，正确的是？
A 快速排序的平均时间复杂度为O(nlogn)，最坏时间复杂度为O(nlogn)
B 堆排序的平均时间复杂度为O(nlogn)，最坏时间复杂度为O(n^2)
C 冒泡排序的平均时间复杂度为O(n^2)，最坏时间复杂度为O(n^2)
D 归并排序的平均时间复杂度为O(nlogn)，最坏时间复杂度为O(n^2)
C
A，快速排序最坏时间复杂度为O(n^2)
B，堆排序最坏为O(nlogn）
C,正确
D，归并排序，最坏时间复杂度O(nlogn）
假设要存储一个数据集，数据维持有序，对其的操作只有插入、删除和顺序遍历，综合存储效率和运行速度，下列哪种数据结构是最适合的是？
A 数组
B 链表
C 哈希表
D 队列
B
数组插入、删除需要移动数组元素，平均移动n/2
哈希表难以实现顺序遍历
队列插入删除效率低下
设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到Hash表中需要做几次线性探测？
A n2
B n*(n+1)
C n*(n+1)/2
D n*(n-1)/2
D
第一个关键字直接插入，第二个关键字要做1次探测，所以类推n个关键词要做0+1+2+...+(n-1) = n*(n-1) / 2 答案是D
数据库事务正确执行的四个基本要素不包括?
A 隔离性
B 持久性
C 强制性
D 一致性
C
下列的进程状态变化中，哪些是不可能发生的？
A 运行→就绪
B 运行→等待
C 等待→运行
D 等待→就绪
C
就绪状态是可以和运行状态相互转换的，超时的时候就会从运行状态转为就绪状态。但是一旦是等待状态（阻塞）就必须选转为就绪才能够运行。
以下哪些方式/命令不可以查看某IP是否可达？
A telnet
B ping
C tracert
D top
D
top是查看CPU状态参数命令
当用一台机器作为网络客户端时，该机器最多可以保持多少个到服务端的连接？
A 1
B 少于1024
C 少于65535
D 无限制
C
二、填空题
假设网络带宽是128MB/s，网络单向延时为100ms, 1000个客户端(单线程)同时向服务器传输64KB大小的文件，每个请求大小为64KB，服务器磁盘并发写入速度30MB/s，在传输过程中，服务器吞吐量为 ________MB/S ，单个请求响应时间为_______ ms
30
700
由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为 ________？
53
24
10 14
5 (5) (6) (8)
(2) (3)
路径：6* 2 +8* 2 + 5 * 2 + 2 * 3 + 3* 3 =53
三、问答题
给定一棵二叉树，求各个路径的最大和，路径可以以任意节点作为起点和终点。
比如给定以下二叉树:
2
/ \
5 3
返回10。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
int maxPathSum(TreeNode *root)
本题的具体思路，是利用前序遍历的思想，将节点左右两分支的最大都求出来，然后首先判断节点本身作为连接点，连接左右两分支的这个情况是不是比当前max更大，如果更大，更新max；然后将该节点左右两支的最大值返回给上层，供上层进行同样的判定。最终得到最大值。
代码如下：
public class Binary_Tree_Maximum_Path_Sum {
public int max = Integer.MIN_VALUE;
public int findRst(TreeNode root){
if (root == null) {
return 0;
} else {
int sumLeft = findRst(root.left);
int sumRight = findRst(root.right);
int cur = root.val;
int leftRightSum = sumLeft+cur+sumRight;
max = max<leftRightSum?leftRightSum:max;
int subMax = sumLeft > sumRight ? sumLeft : sumRight;
if (cur+subMax > 0) {
if(max<subMax+cur)
max = subMax+cur;
return cur + subMax;
} else {
return 0;
}
}
}
public int maxPathSum(TreeNode root) {
if(root==null)
return 0;
max = max<root.val?root.val:max;
findRst(root);
return max;
}
public static void main(String[] args){
Binary_Tree_Maximum_Path_Sum binary_tree_maximum_path_sum = new Binary_Tree_Maximum_Path_Sum();
TreeNode root = new TreeNode(2);
root.left = new TreeNode(-1);
root.left.left = new TreeNode(-4);
root.left.right = new TreeNode(99);
root.right = new TreeNode(-3);
root.right.left = new TreeNode(-5);
root.right.right = new TreeNode(-6);
System.out.println(binary_tree_maximum_path_sum.maxPathSum(root));
}
}
编辑距离，又称Levenshtein距离，是指两个子串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。请尝试写出一个算法来计算两个字符串的编辑距离，并计算其复杂度？在某些应用场景下，替换操作的代价比较高，假设替换操作的代价是插入和删除的两倍， 算法该如何调整？
动态规划。
字符串 A, B, 记录结果为二维数组R[n][m] （其中n，m为A， B的长度）
A 变换到 B 可以通过 如下 3个操作：
添加。即已知A[0..i]变化到B[0..j-1]的最小操作次数，最后加上 B[j]即可。 R[[i][j] = R[i][j-1] + 1 (添加操作代价为1）
删除。即已知A[0..i-1]变化到B[0..j]的最小操作次数， 最后删掉A[i]即可。 R[i][j] = R[i-1][j] + 1（删除操作代价为1）
替换。即已知A[0..i-1]变化到B[0..j-1]的最小操作次数， 最后替换A[i]为B[j]即可。 R[i][j] = R[i-1][j-1] + 1（替换操作代价为1）
公式为：
R[[i][j] = min ( R[i][j-1] + 1, R[i-1][j] + 1, R[i-1][j-1] + 1)
当i或者j为0时， 相应地值为字符串长度（因为从一个字符串变成长度为0的字符串的代价为这个字符串的长度）。
动态规划求出R[n][m]就可以了。
时间复杂度O（nm)， 空间复杂度O（nm）（其实就是计算出R[n][m]这个数组）
替换代价变为2的时候， 公式改为：
R[[i][j] = min ( R[i][j-1] + 1, R[i-1][j] + 1, R[i-1][j-1] + 2)
