多益笔试

单选
 1. 对n个元素的序列进行冒泡排序时, 最少的比较次数是()
 2. 正确选项
    A.插入排序是不稳定的排序, 时间复杂度On^2
    B.选择排序是稳定的排序, 时间复杂度On^2
    C.快速排序是不稳定的排序, 时间复杂度O(nlogn)
    D.堆排序是稳定的排序, 时间复杂度O(nlogn)
 3. 不属于有序表上需要关键字有序且是顺序存储的查找
    A.二分    B.斐波那契    C.插值    D.散列
 4. 从一个1500的未排序数组中提取3个最小的元素, 以下排序算法中, 那个算法在平均情况下的执行速度最快
    A.希尔    B.归并    C.堆排序    D.简单选择排序
 5. 现有队列Q,栈S, 初始化时Q中元素1,2,3,4,5,6(1在队头), S为空,  只允许以下操作
    1.出队并输出对应元素
    2.出臥井将其入桟
    3.出栈并输出对应元素
    则不能得到的输出序列是：
    A. 1, 2, 5, 6, 4, 3
    B. 2, 3, 4, 5, 6, 1
    C. 3, 4, 5, 6, 1, 2
    D. 6, 5, 4, 3, 2, 1
 6. 求阶乘算法如下, 时间复杂度();
    ```java
    int fact(int n){
        if (n<=1) return 1;
        return n*fact(n-1);
    }
    ```
 7. 在拓扑有序图中, 描述正确的是
    A. 可能存在环
    B.拓扑序列可能有多个
    C.可能存在回路
    D.序列一定是唯一的
 8.一文本中各个字母出现的频率分别是{d:4, u:3, 0:12，y:7，i:10)，使用哈夫曼编码，则那种是可能的编码
    A. d(001) u(000) y(01) i(10) o(11)
    В. d(0000) u(0001) у(001) о(01) і(1)
    C. d(000) u(001) y(01) i(10) o(00)
    D. d(0000) u(0001) h(001) o(000) i(1)
 9、先序序列为a,b,c,d的不同二叉树的个数是
    A. 13
    B. 14
    C. 15
    D. 16
 10.以下哪个不是红黑树的性质
    A. 根节点是黑色
    B. 节点是红色或黑色
    C.每个黑色节点的两个子节点都是红色。
    D.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
 11、下列选项中，可以执行特权指令
    A.A. 普通用户的程序
    B.B. 设备驭动程序
    C.C.动态库函数
    D.D.管理员用户的程序
12.选择排队作业中等待时问最长的作业优先调度，该调度算法是
    A. 先来先服务调度算法
    B. 高响应比优先调度算法
    C.优先权调度算法
    D.短作业优先调庭算法
13.只有满足联接条件的记录才包含在查询结果中，这种联接为,
    A. 左联接
    B. 右链接
    C.内部联接
    D,完全联接
14、以下不属于私有地址的网段是？
    A. 10.0.0.0/8
    B. 172.16.0.0/12
    C. 192.168.0.0/16
    D. 224.0.0.0/8
15、在TCP/IP建立连接过程中，客户端或服务器的状态转移说法错误的是？
    A.经历SYN_ SEND状态
    B.经历SYN_RECV状态
    C.经历TIME_WAIT状态
    D.经历ESTABLISHED状态
    E.服务器在收到syn包时将加入半连接队列

填空
 1、已知有一个关键字序列：（27,23,34,14, 1,55,20,19,85,83,10,68） 散列存儲在一个哈希表中，若散列函数H
（key） =key%7，井采用链地址法来解决冲突，则在等概率情况下查找成功的平均查找长度为___
（精确到小数点后两位即可）
第一空：
2、若一颗完全二叉树的节点个数为2n-1，则它的叶节点个数为_个。
第一空：
3、以下二叉树的后序追历输出结果为：
       A
      /  \
     B   C
    / \  / \
  D  E F  G
第一空：DEBFGCA
4、出现死锁时，除了可以采用资源剩夺的方法解决死锁问题外，还可以使用的方法是
第一空
5.191.21.10.13/24在该子网掩码下，其广播地址是___
第一空

简答:
 1.翻译中文
 2.哈希表get操作是否一定是O(1), 请简要说明出现的情况.
 3.全局变量和局部变量的区别, 怎么实现的, 操作系统和编译器怎么区分的.
 4.数据库中事务隔离的实现有哪些机制

编程题:
给定整数序列A1,A2,…An,这些整数可能是正数，可能是负数，也可能是0,求出这个整数序列中最大连续子序列的和#牛客AI配图神器#