回馈牛客，2019秋招贝壳安卓笔试题目分享

1. 有一个数组有一百万项,每项都是整数,要对这个数组进行排序,下面哪种法最快()

A.选择排序法

B.泡排序法

C.Quicksort排序法

D.Mergesort排序法

2. 已知哈希表{22,34,15,44,3,2,77},则在线性时间内,找到的最长连续元索的长度为()

A.3

B.4

C.5

D.6

3. 定{1,2,3,4,5,6,7,8}的一个排列,使其逆序列为5,3,4,0,2,1,1,0,则这个排列为()

A.53241678

B.12345678

C.48625137

D.13254786

4. 下面程序段的所需要的计算时间为()

int MaxSum(int n, int*a, int &besti, int &bestj)

{

int sum=0:

for(int i=1; i<=n;i++){

    int thissum=0;

    for(int j=i;j<=n;j++){

        thissum+=a[j];

        if(thissum>sum){

            sum=thissum;

            besti=i;

            bestj=j;

        }

    }

}

return sum;

}

A. O(n)

B. O(n^3)

C. O(1)

D. O(n^2)

5. 设问题规模为N时，某递归算法的时间复杂度记为T（N）,已知T(1)=1,T(N)=2T(N/2)+N/2,用O表的时间杂度为

A.O(logN)

B.O(N)

C.O(N2logN)

D O(NlogN)

6. 二叉树的前序遍历为ABCDEFGH中序遍历为CDBAFEHG,则次树的后续遍历为()

CDBAEFGH

ABECFGDH

HGFEABCD

DCBFHGEA

7. 已知字符串s="121121121345623",模式串P=“12112134”。采用KMP算法进行匹配时,首次匹配失败时候,i=j=6。接下来继续匹配,匹配开始时i和j分别是

A.i=1,j=0

B.i=6,j=2

C.i=2,j=1

D.i=6,j=3

8. 假设有10个关键字互为同义词,若用线性探测再散列探查法把这10个关键字存入哈希表中,至少需要探测的次数()

A.100

B.10

C.11

D.55

9. 计算式6/3+(4+5)-7/(9+8)的前序表达式和后续表达式分别为()

A.-*6/3+45/7+98 6/345+*798+/-

B.-*/63+475/+98 63/4+5*798+/-

C. -*/63+45/79+8 63/45+*79+8/

D.-*/63+45/7+98 63/45+*798+/-

二．多选

10．已知一个栈的进栈序列是123…n其出栈序列是p1p2…pn若p1=5则p2的值()

A.不可能是4

B.不可能是3

C.可能是4

D.一定是4

11. 在mysq中执行命令 drop database会()

A.删除数据库和表文件

B.仅删除表的记录,不删除表的结构

C.返回被刪除表的数量

D.返回被删除表的名称列表

12. 假设关系R(A,B,C,D),S(A,C,E,F),则R与S进行自然连接后得到的关系模式,有()列

A.6

B.4

C.8

D.7

13. 一个理想的调度算法应当考虑()

A.系统并发进程的数量

B.确保每个进程获得合理的CPU份额

C.使CPU百分百地忙碌

D.使批处理用户等待辅出的时间尽可能短

14. 对信号S执行V***作后,当S小于0时表示()

A.唤醒一个就绪进程

B.s count的绝对值为可以资源个数

C.s.count的绝对值为阻塞进程个数

D.唤醒一个阻塞进程

15. 子网掩码为255.255.0.0,下列哪些IP地址在同一网段中()

A.168.16.25.16

B.168.25.201.15

C.168.25.15.201

D.168.25.16.15

16. 在32和64位***作系统中,int类型占几个字节,指占几个字节,***作系统可以使用的最大内存空间是多大

A.32位下:4,4不限制64位下:4,8,不限制

B.32位下:4,4,2^32 64位下:4,4,2^64

C.32位下:4,4,2^32 64位下:8,8,2^64

D.32位下:4,4,2^32 64位下:4,8,2^64

17. 下面程序的输出结果是()

#include <iostream>

using namespace std;

class ClassTest

public:

ClassTest(int i=0){cout<<1;}

ClassTest(const ClassTest&x){cout <<2;}

ClassTest&operator=(const ClassTest&x){cout<<;return *this}

~ClassTestO{cout<<4; }

};

int main()

{

ClassTest obj1 (1), obj2(2), obj3(obj1);

obj1=obj2;

return 0;

}

A.1123444

B.1131444

C.121444

D.11114444

18. C++中空类默认产生哪些类成员的数()

A.缺告构造函数,缺拷贝构造函数,缺析构函数,缺省赋值运算符

B.缺省构造函数,缺省拷贝构造函数,缺省析构函数,缺省赋值运算符,缺省取址运算符const

C.缺省构造函数,缺省析构函数

D缺省构造函数,缺省拷贝构造函数,缺嘗析构酽数,缺省赋值运算符,缺省地址运算符

19. 常用的无用赋信有:()

A.对某变量A赋值后,该A值在程序中不被引用

B.对某变量A赋值后,在该A值被引用前又对A重新赋值

C.对某变量A赋值后,在该A值被引用后又对A重新赋值

D对某变量A进行递归赋值，目该A值在程序中仅在递归算法中被引用

20. 有以下函数

include <stdio. h>

void fun(int *s)

{

static int j=0;

do

{

    s[j]=s[j]+s[j+1];

}

while(++j<2);

}

void main()

{

    int k,a[10]={1,2,3,4,5};

    for(k=1;k<3;k++) fun(a);

for(k=1: k<3, k++) fun(a);

for(k-1: k<5: k++) printf( %d, a(kD:

printf("\n");

}

程序运行输出结果是()

A.5745

B.3451

C.1235

D.2345

二． 编程

计算器

时间限制:CC++语言1000MS;其他语言3000MS

内存限制:CC++语言65536KB;其他语言589824KB

题目描述

假设有这样一个计算器,该计算器只有两个按钮,按下第一个按钮能使显示数值减少1,按下第二个按钮能使显示数值乘以2,当前显示数值为N,那么至少要按多少次按钮才能使显示数值变成M?

输入

两个整数N和M,1≤N,M≤109

输出

使显示数值变成M的最少按按钮次数

样例输入

4 5

样例输出

3

家族关系

时间限制:C/C++语言1000MS;其他语言3000MS

内存限制:CC++语言65536KB;其他语言589824KB

题目描述:

小明和小红是亲兄妹,他俩起翻了翻他们家的族谐,发现他们家非常庞大，有非常多的名字在族谐里面。族谱中会写消楚每一个人的父亲是谁,当然每个人都只会有一个父亲。

对于祖先的定义,我们在这儿个例子:族里面会写小王的父亲是小丁,小丁的父亲是小东,那么实际上小东就是小王的爷爷,也是小王的祖先

小明很聪明,小明理了理他们的家庭关系,很快就青清楚了,知道了族谐中每一个人的祖先关系。

但是小红却依旧困感,于是问了很多问题,希望你能够解答。

小红的问题是,请问A是B的祖先关系是什么?究竞A是不是B的祖先,或者说B

是A的祖先,亦或者B和A不存在祖先关系呢

输入

第一行包括一个整数n表示家族成员个数

接下来n行每行对整数对a和b表示a是b的父亲,或者b是a的父亲,这需要你

来判断

如果b是-1,那么就是整个家族的根,也就是举分最大的人,保证只有一个。

第n+2行是一个整数m表示小红的询问个数

接下来m行,每行两个正整数A和B

表示小红想知道A是8的祖先关系

n,ms4000,每个节点的编号都不超过40000

输出

对于每一个询问

1表示A是B的祖先,输出2表示B是A的祖先,都不是输出0

样例输入

10

1 -1

3 1

4 1

5 1

6 1

7 1

8 1

9 1

10 1

2 10

2 3

2 4

2 5

2 10

样例输出

1

0

0

0

2

多米诺

时间限制:CC++语言1000MS;其他语言3000MS

内存限制:C/C++语言65536KB;其他语言589824KB

题目描述

多米诺骨牌大家想必都不随生,现在有n块多米诺骨放在x轴上,每一块骨牌有一个所在位置下标和尚度,每一块骨牌都只会向x轴正方向倒下,当处于位置0,高度为h0的多米诺骨牌倒下,会压倒X+1,x+h-1内的所有多米诺骨牌,对于每一块骨牌。我们希望知道,如果我把这块骨牌推倒,那么至多可以倒下多少块骨牌

输入

第一行包含一个正整数n,表示多米诺骨牌的数量(1<=n<=10^5)

接下来n行,每行包含两个正整数xh,分别表示第快多米诺骨牌的位置和高度

(-10^8<=x<-10~82<-h<=10^8),保证不会有两块骨牌在同一高度

输出

对于每个测试数据,翰出一行,包含n个正整数,第个数字表示,如果推倒第i

块多米诺骨牌,可以使得多少个骨牌倒下

样例输入

4

16 5

20 5

10 10

18 2

样例输出

3 1 4 1