小米笔试题复盘

下面有关TCP连接建立和释放过程中的状态,描述正确的是()?

A. 连接释放过程中,关闭发起方从 TIME_WAIT状态到 CLOSED状态需要等待1个MSL

B. 连接建立过程中客户端在 SYN_SENT状态收到服务器的SYN+ACK包并发送确认ACK包后,客户端即进入 ESTABLISHED状态

C. 连接释放过程中,处于 CLOSE WAIT状态的一方仍可以继续发送数据

D. 连接建立过程中服务器在 SYN_RCVD状态收到客户端的确认ACK包后,服务器即进入 ESTABLISHED状态。

BCD。A. 2个MSL。

在—个真实的计算机系统中,系统内的资源会新添、损坏或被替换,系统内的进程会新建和退岀。如果用银行家算法控制死锁,下面哪些变化是安全的(不会导致死锁)?()

A. 增加一个进程的Max(进程需要更多的资源,超过所允许给予的资源)

B. 减少可用资源(资源被从系统中永久性地移出)

C. 减少一个进程的Max(进程不再需要那么多资源)

D. 增加可用资源(新的资源被添加到系统)

CD

UNIQUE惟一索引的作用是()

A. 保证惟一索引不能被删除

B. 保证参加惟一索引的各列,不得再参加其他的索引

C. 保证各行在该索引上的值不得为NULL

D. 保证各行在该索引上的值都不得重复

D. 顺便写点最近复习的知识点,唯一索引和普通索引的区别是唯一索引有唯一性约束,也是因为这点,在对读取到内存中的数据页,普通索引可以使用change_buffer缓存,后期再写回磁盘,而唯一索引不行。

下面关于有向无环图说法错误的是?()

A. 有向无环图至少有一个顶点入度为0

B. 有向无环图至少有一个拓扑排序

C. 有向无环图可以转换成树

D. 有向无环图至少有一个顶点出度为0

C. 有向无环图不一定可以转换成树。一个节点可能有多个父节点。

在下列序列中,若以最后一个数字为基准进行快速排序(升序),第一趟数字被移动次数最多的是()

A. 52,40,45,102,110,106,98,120

B. 110,106,102,45,40,120,98,52

C. 102,106,110,120,52,45,40,98

D. 102,106,98,52,40,45,120,110

C

从尚末排序的N名学生的考试分数中挑出排名第K的分数,平均时间复杂度最优可以达到多少?()

A. O(N*K)

B. O(N)

C. O(N^2)

D. O(N*logN)

B. 一开始直观的想法是O(N*logK),维护一个堆。实际上有O(N)的算法——BFPRT算法。

下列关于设计模式说法错误的是()

A. 用饿汉方式实现的单例模式是不能够被继承的

B. 装饰器模式在实现过程中一般不会更改被封装对象的接口定义

C. 简单工厂模式可以实现按客户端条件动态创建对象的效果

D. 适配器模式为客户端提供了与被适配对象接口定义相同的适配对象

D.
A 中饿单例模式和懒单例模式构造方法都是私有的,因而是不能被继承的,虽然有些单例模式可以被继承(如登记式模式) 。
D 中“被适配对象”是Adapter,适配器是Adaptee,Adaptee是提供给客户端调用的适配器。 Adaptee 具体适配Adapter的过程,有类适配器和对象适配器。
- 对象适配器实现目标类的接口,并依赖于源类(有源类的引用)。
- 类适配器继承自源类,并实现目标类的接口。

适配器模式类图
关于排序算法,以下的哪些叙述是正确的?

A. 快速排序的最坏时间复杂度为O(nlog(n)),它是一个不稳定排序

B. 堆排序的最坏时间复杂度为 O(nlog(n)) ,它不需要额外存储空间来完成排序

C. 归并排序的时间复杂度为 O(nlog(n)) ,它需要O(n)的额外存储空间来完成排序

D. 冒泡排序的时间复杂度为O(n^2),它是一个不稳定排序

ABC. D 中冒泡是稳定的。

1,2,3,4,5五个数字,能组成多少种不同的二叉搜索树的结构?()

A. 36

B. 42

C. 40

D. 32

卡特兰数h(5)=42。

类似题目:

  • 对于一个无限大的栈,一共n个元素,请问有几种合法的入栈出栈形式?
    • h(n)
  • 矩阵连乘:P=a1×a2×a3×……×an,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,试问有几种括号化的方案?
    • h(n-1)
  • n个结点可构造多少个不同的二叉树?
    • h(n)
  • 凸多边形三角划分。 在一个凸多边形中,通过若干条互不相交的对角线,把这个多边形划分成了若干个三角形。任务是键盘上输入凸多边形的边数n,求不同划分的方案数?
    • h(n-2)
  • 给定n对括号,求括号正确配对的字符串数?
    • h(n)
  • 在图书馆一共6个人在排队,3个在还《面试宝典》一书,3个在借《面试宝典》一书,图书馆此时没有《面试宝典》了,求他们排队的总数?
    • f(2n)= h(n)n!n!
  • 高矮排队问题。 12(2n)个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?
    • h(n)

其他题目 https://blog.csdn.net/u011489043/article/details/77884434

以下通不过编译的是:
A.abstract class Something {
private abstract String doSomething();
}
B.abstract class Name {
private String name;
public abstract boolean isSomething(String name){};
}
C.public class Something{
void doSomething() {
private String s="";
int l=s.length();
}
}
D.public class Something{
public static void main(String[] args) {
Thing t = new Thing();
new Something().addOne(t);
}

private void addOne(final Thing t) {
t.i++;
}
}
class Thing {
public int i;
}

ABC. A 中Illegal combination of modifiers: 'abstract' and 'private'。

编译程序不仅包含词法分析、语法分析、中间代码生成、目标代码生成,还包括()

A. 源代码优化

B. 代码优化

C. 表格管理

D. 出错处理

BCD. 啊啊啊,不包括源代码优化啊,一股脑都选了。我怎么记得是有源代码优化阶段的。

源码 ->(扫描)-> 单词 ( 词法分析 ) -> 标记 ->(语法分析)-> 语法树 ->(语义分析)-> 标识语义后的语法树 ->(源码优化)-> 中间代码生成 ->(代码优化)-> 目标机器代码 ->(目标代码优化)-> 最终目标代码

编译的各个阶段
在X86平台上,C语言函数调用时,通过以下哪种方式传递参数?

A. 变量地址

B. 内存

C. 寄存器

D. 堆栈

C. 人家題目问的不是传值还是传地址。 https://www.cnblogs.com/clover-toeic/p/3755401.html

搞笑我太难了 上辈子我一定是道数学题
我太难了x1

函数调用过程通常使用堆栈实现,每个用户态进程对应一个调用栈结构(call stack)。编译器使用堆栈传递函数参数、保存返回地址、临时保存寄存器原有值(即函数调用的上下文)以备恢复以及存储本地局部变量。

不同处理器和编译器的堆栈布局、函数调用方法都可能不同,但堆栈的基本概念是一样的。

注:x86平台将参数压入调用栈中。而x86_64平台具有16个通用64位寄存器,故调用函数时前6个参数通常由寄存器传递,其余参数才通过栈传递。

在 Python3中,对于字符编码叙述正确的是

A. str编码为utf-8,byte无编码

B. str编码为utf-16,byte为utf-8

C. str为 unicode字符(内部编码ut-16),byte编码为utf-8

D. str为 unicode字符(内部编码utf-16),byte无编码

A.
Python3 把系统默认编码设置为 UTF-8 ; 文本字符和二进制数据区分得更清晰,分别用 str 和 bytes 表示。文本字符全部用 str 类型表示,str 能表示 Unicode 字符集中所有字符,而二进制字节数据用一种全新的数据类型,用 bytes 来表示。
Python3 中,在字符引号前加‘b’,明确表示这是一个 bytes 类型的对象,实际上它就是一组二进制字节序列组成的数据,bytes 类型可以是 ASCII范围内的字符和其它十六进制形式的字符数据

  • Unicode 是「字符集」
  • UTF-8 是「编码规则」
下面STL容器中,哪些是有序的()

A. stack

B. map

C. set

D. vector

BC. STL中的set和map是有序容器,基于红黑树。

编译程序目标代码生成阶段主要任务是

A. 把中间代码变换成依赖具体机器的目标代码

B. 把高级语言翻译成机器语言

C. 把高级语言翻译成汇编语言

D. 把汇编语言翻译成机器语言

A. 目标代码生成阶段目标代码生成是编译器工作的最后一个阶段。这一阶段的任务是把中间代码变换成特定机器上的绝对指令代码、可重定位的指令代码或汇编指令。

关于C++,以下说法错误的是()

A. 变量或函数的定义尽量不要放在头文件中。因为头文件包含在多个源文件中,所以不应该含有变量或函数的定义

B. extern double pi=3.14此声明没有分配及初始化存储空间

C. 类不是在类定义里定义数据成员时初始化数据成员,而是通过构造函数控制初始化。

D. const对象可以定义在头文件中

B.

都好久不写C++工程了,面Java怎么C++、Python都考得到。

搞笑我太难了 上辈子我一定是道数学题
我太难了x2

A 中头文件中不可以放变量的定义!!!一般情况下头文件中只放变量的声明,因为头文件要被其他文件包含(即#include),如果把定义放到头文件的话,就不能避免多次定义变量,C++不允许多次定义变量,一个程序中对指定变量的定义只有一次,声明可以无数次。

B 中 声明仅仅是将变量的名字和类型告诉编译器,并不分配存储空间。 定义则会为其分配存储空间,也可能会为变量赋一个初始值。 extern double pi = 3.14,此时对extern变量赋予初值,就变成定义了。

C++ 初始化类的三个数据成员:const成员、static成员、const static成员
1、const成员:只能在构造函数后的初始化列表中初始化
2、static成员:在类外 初始化 ,且不加static修饰
3、const static成员:类只有唯一一份拷贝,且数值不能改变。因此,可以在类中声明处初始化,也可以像static在类外初始化

D 中对于头文件不应该含有定义这一规则,有三个例外:头文件中可以定义、值在编译时就已知道的const对象(数组的大小可以用const int型变量定义,这在C中是不行的),和inline函数
- 类定义内部的成员可以是声明,类定义和类内部成员的定义不是一回事,可以不同步进行,也”不建议“类定义时定义类内部函数。
- const 变量默认是定义该变量的文件的局部变量。当我们在头文件中定义了 const 变量后,每个包含该头文件的源文件都有了自己的 const 变量,其名称和值都一样。 如果 const 变量不是用常量表达式初始化,那么它就不应该在头文件中定义(若不初始化const变量,这个const变量有什么用呢?)。相反,和其他的变量一样,该 const 变量应该在一个源文件中定义并初始化。应在头文件中为它添加 extern 声明,以使其能被多个文件共享。

下面关于虛函数的描述中,正确的是()

A. 虚函数必须是非静态成员函数。

B. 对于虚函数,virtual关键字只能出现在类定义中的函数原型声明中,不能出现在类体外的函数定义中

C. 对于多态类,应该将构造函数和析构函数都声明为虚函数。

D. 根据类型兼容规则,基类指针(或引用)可以指向其派生类的实例,但在非虚函数的情况下,通过基类指针(或引用)却只能调用基类的函数成员,无法调用其所指实例派生类的函数成员。

ABD.
C 中 构造函数 不能设置为虚函数。
D 中函数覆盖,基类中成员函数要用virtual修饰为虚函数。

C++中,声明 int const** const * const x表示是什么类型?

A. 个 const指针,指向一个 const指针,指向一个普通指针,指向一个 const int

B. 一个 const数组,每个成员都是一个 const二维int类型 consta数组B.

C. 一个 const指针,指向一个 const双层指针,指向一个int

D. 一个 const指针,指向一个 const指针,指向一个 const int,它存着一个指针

搞笑我太难了 上辈子我一定是道数学题
我太难了x3
const int a
int const a
const int *a
int *const a
  • int const a 和 const int a均表示常量类型a
  • const int *a,常量指针,其中a是指向const int的变量指针,a的值可以变化
  • int *const a,指针常量,表示a是指向int变量的指针,但a的值不能发生变化。
int *p[10];
int (*p)[10];
int *p(int)
int (*p)(int)
  • int *p[10]表示指针数组,是一个数组变量,大小为10,数组内的元素指向int类型的指针变量;
  • int (*p)[10]表示数组指针,是指针类型,指向的是一个int类型的数组,这个数组的大小是10;
  • int *p(int)是函数声明,函数名是p,参数类型是int,返回值int*
  • int (*p)(int)是函数指针,是指针类型,指向的具有int参数,返回值是int的函数
 不属于jvm invoke 指令的是

A. invokespecial

B. invokemethod

C. invokevirtual

D. invokedynamic

B.

  • invokestatic : 调用静态方法
  • invokespecial : 调用实例构造器方法, 私有方法和父类方法
  • invokevirtual : 调用虚方法
  • invokeinterface : 调用接口方法
  • invokedynamic : 动态调用

第1道

在某个存储介质以如下形式保存一棵二叉树1(2(3,4(,5),6(7,))
上述序列表示的二叉树如下

观察后可以发现,每个节点的格式为X,X可以为空
或者
X(Y,Z),其中X不为空
请编写程序将以上述格式输入的二叉树输出为中序遍历顺序

输入描述:

上述格式表示的二叉树字符串,用字符1~9表示每个二叉树的每个节点,字符可以重复使用

输出描述:

二又树的中序遍历结果

示例1

输入:

1(2(3,4(,5),6(7,))

输出:

3245176

这道题完全模拟生成二叉树,过不了所有测试用例。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    static class Node {
        int num;
        Node left, right;

        public Node(int num) {
            this.num = num;
        }
    }

    /*请完成下面这个函数,实现题目要求的功能
    当然,你也可以不按照下面这个模板来作答,完全按照自己的想法来 ^-^
    ******************************开始写代码******************************/
    static String solution(String input) {
        char[] line = input.toCharArray();
        Node root = parse(line, 0);
        List<Integer> ans = new ArrayList<>();
        midTrace(root, ans);
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < ans.size(); i++)
            sb.append(ans.get(i));
        return sb.toString();
    }

    private static void midTrace(Node root, List<Integer> ans) {
        if (root == null) return;
        midTrace(root.left, ans);
        ans.add(root.num);
        midTrace(root.right, ans);
    }

    // 1(2(3,4(,5)),6(7,))
    // 1(,6(7,))
    private static Node parse(char[] line, int start) {
        if (start >= line.length) return null;
        if (line[start] == ')') return null;
        Node node = new Node(line[start] - '0');
        if (line[start + 1] == '(') {
            if (line[start + 2] != ',') {
                node.left = parse(line, start + 2);
                if (line[start + 3] == '(') {
                    int cnt = 0;
                    int idx = start + 3;
                    while (idx < line.length && !(cnt == 0 && line[idx] == ',')) {
                        if (line[idx] == '(')
                            cnt++;
                        else if (line[idx] == ')')
                            cnt--;

                        idx++;
                    }
                    node.right = parse(line, idx + 1);
                } else if (line[start + 3] == ',') {
                    node.right = parse(line, start + 4);
                }
            } else {
                node.right = parse(line, start + 3);
            }
        } else if (line[start + 1] == ',') {
            return node;
        }
        return node;
    }

    /******************************结束写代码******************************/


    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String res;

        String _input;
        try {
            _input = in.nextLine();
        } catch (Exception e) {
            _input = null;
        }

        res = solution(_input);
        System.out.println(res);
    }
}

考虑用栈来完成中序遍历,非递归中序遍历。

第2道

小米之家有很多米粉喜欢的产品,产品种类很多,价格也不同。比如某签字笔1元,某充电宝79元,某电池1元,某电视1999元等假设库存不限,小明去小米之家买东西,要用光N元预算的钱,请问他最少能买几件产品?

输入描述:

第1行为产品种类数
接下来的每行为每种产品的价格
最后一行为预算金额

输出描述:

能买到的最少的产品的件数,无法没有匹配的返回1

示例1

输入:

2
500
1
1000

输出:

2

这题是完全背包问题改造。

import java.util.Arrays;
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] w = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            w[i] = sc.nextInt();
        }
        int V = sc.nextInt();
        int[] dp = new int[V + 1];
        Arrays.fill(dp, V);
        dp[0] = 0;
        sc.close();
        for (int i = 1; i <= n; i++) {
            for (int v = w[i]; v <= V; v++) {
                dp[v] = Math.min(dp[v - w[i]] + 1, dp[v]);
            }
        }
        System.out.println(dp[V]);
    }
}

我只想给自己一个交代,无论成功还是失败,无论及时还是延迟。