腾讯2018秋招正式笔试题目

不定项选择题

1、以下说法正确的是（   ）。

A.  由先序序列、中序序列可以还原出树的原貌

B.  200，190，150，170，180，140，155，160，165，120是一个最大堆

C.  排序之前必须把所有待排数据加载到内存

D.  给定一组输入，可以输出一颗唯一的哈夫曼树

参考答案：A

2、二叉树的节点的对称序列是IEGMOBA，后序序列是EMGIBAO，则该二叉树的前序序列是（   ）

A.  OIGEMAB

B.  OIAGBEM

C.  OAIGMBE

D.  OABIGME

参考答案：A

    O

   /  \

  I    A

   \    \

   G    B

   / \

  E  M

3、请选择正确的描述。（   ）

A.  静态变量和全局变量是在程序一开始时分配内存的，这部分内存无法回收，直至程序结束

B.  通常常来说，在堆上分配内存比在栈上分配内存效率更高

C.  当我预先知道待分配内存大小时，我就可以直接在栈上分配内存，只要不超过当前操作系统的可用内存大小，就永远会成功

D.  内存泄漏就是指当A程序申请一块内存时，有可能操作系统把B程序的一块内存先交给A程序使用，等A程序结束后再返回给B程序，在内存借用的这段时间内，B程序就产生了内存泄漏

参考答案：A

解析：

栈上分配内存效率更高；栈上申请内存并不总是成功；内存泄漏是使用完成之后未回收又无法使用的区域。

4、对于栈操作，输入序列ABCDEF，输出序列BCDAEF，可能的栈操作是（   ）。

A.  push, push, push, push, push, push, pop, pop, pop, pop, pop, pop

B.  push, push, pop, push, pop, push, pop, pop, push, pop, push, pop

C.  push, push, pop, push, pop, push, pop, push, pop, push, pop, pop

D.  push, push, pop, push, pop, push, pop, pop, push, push, pop, pop

参考答案：B

5、关于浮点数，下面的描述不正确的是（   ）。

A.  总能找到一个32bit整数（32 bit int），来描述一个IEEE754 32bit浮点数的整数部分

B.  总能找到一个IEEE754 64bit浮点数，来描述一个32bit整数（32 bit int）

C.  表达式（0.666f - 0.665f == 0.001f），无论在任何平台，一定返回True

D.  当两个不同的平台都使用IEEE754作为浮点数标准时，他们的浮点运算结果就会严格一致

参考答案：C

6、有如下一个类似跳表的额数据结构：

每层都是已经排好序的链表，

level  1层的链表有所有元素，

level  N层的链表只有levelN-1的1半的元素，

level  N层的结点指向levelN-1层中相同的结点。

请问查找一个元素的时间复杂度是（  ）。

A.  O(nlog2n)

B.  O(n)

C.  O(log2n)

D.  O(n2)

参考答案：C

7、请问下列代码的输出是多少？（  ）

 #include<stdio.h>
 #define  MAX 100
 int main()
 {
   int i = 0, sum = 0;
   do{
      if(i!=(i/9)*10)
        sum += i;
     }while(++i<MAX);
     printf(“%d\n”,sum);
}

A.  450

B.  360

C.  4950

D.  4590

E. 以上答案都不正确

正确答案：D

8、在公司局域网上ping www.qq.com一定不涉及的网络协议是（  ）。

A.  UDP

B.  DNS

C.  ICMP

D.  RAAP

正确答案：A

9、有Area和City两个表，两表的数据如下所示：

Area：

 ID   Name

 1    North

 2    South

 3    East

 4    West

 null  null

City:

 ID    Name     AreaID

 1     北京      1

 2     上海      2

 3     广州      3

 4     深圳      4

 5     null      null

关于下面的sql语句，描述正确的是（   ）。

select * form City left join Area on City_AreaID = Area.ID where AreaID>0 group by AreaID having count(Region)>0 order by count(Region) desc limit 1;

A.  该SQL执行会形成City和Area两表的笛卡尔积

B.  该语句执行顺序上，会先执行where再执行having再执行order by最后执行limit

C.  该语句执行顺序上，会先执行from，再执行join，再执行where

D.  select * form City left join Area on City_AreaID = Area.ID 和select * form City inner join Area on City_AreaID = Area.ID这两条SQL语句执行的结果是不同的

正确答案：B

10、假设QQ用户包含8种状态，QQ号码为42亿，最少用多少内存标识所有用户状态？（   ）

A.  约500M

B.  约1G

C.  约1.5G

D.  约2G

参考答案：C

42*10^8*4=168*10^8=16.8*10^9=

11、程序最后输出什么？（   ）

#define Mul(x , y) ++x*y ++
  int main()
  {
int a = 2;
int b = 4;
int c = 8;
  printf(“%d”,Mul(a+b，b+c));
  return 0;
}

A.  84

B.  27

C.  33

D.  18

++a+b*b+c++=3+16+8=27

正确答案：A

12、以下关于HTTP返回码的描述正确的是（   ）。

A.  403表示服务器接受了请求，但却拒绝处理

B.  5xx这种5开头的错误，都是服务器错误

C.  ajax请求，返回数据正确时，返回码是201而不是200

D.  301和307表示服务器要求重定向

参考答案：B

13、客户端C和服务器S之间建立了一个TCP连接，TCP最大段长度为2KB，客户端C当前的拥塞窗口是16KB，向服务器S连续发送2个最大段之后，成功接收到服务器S发送的第一段确认段，确认段中通告的接收窗口大小是8KB，那么此时客户端C还可以向服务器S发送最大字节数是（   ）。

A.  16KB

B.  14KB

C.  8KB

D.  6KB

E.  4KB

参考答案：D

min(16,8)-2=8-2=6

14、请选择可以正确将pBase指向对象的num_list1数组初始化为0的方式。（   ）

Class Base{
 int num_list1[10];
 public:
 virtual void Func(){memset(num_list1, 0, sizeof(num_list1));}
};
class Derived : public Base{
 int num_list2[10];
public:
 virtual Func(){memset(num_list2, 0, sizeof(num_list2));}
};
Base*pBase = new Derived();

A.  memset(pBase->num_list1, 0, sizeof(int)*10);

B.  pBase->Func();

C.  memset(pBase, 0, sizeof(Base));

D.  memset(pBase, 0, sizeof(Derived));

E.  pBase->Base::Func();

正确答案：A

15、如果主存容量为2G，硬盘容量为64G，计算机地址寄存器是32位，则虚存的最大容量是以下哪个？（   ）

A.  2G

B.  4G

C.  64G

D.  66G

参考答案：B

2^32=4G

16、以下关于链表的描述哪个正确？（  ）

A.  链表的元素在内存中不可以连续存放

B.  链表可用于实现栈、队列、字典、数组等数据类型

C.  链表中一定存在唯一一个没有前驱的元素，以及唯一一个没有后继的元素

D.  在链表中插入元素效率比数组低

E.  以上都不正确

参考答案：E

17、请问下列代码输出的结果可能是哪些？（   ）

 #include<stdint.h>
 #include<stdio.h>
 union  X
{
  int 32_t a;
  struct
 {
   int16_t b;
   int16_t c;
};
 };
int main()
{
  X  x;
  x.a = 0x08172017;
  printf(“%x,%x\n”, x.b, x.c);
  return 0;
}

A.  2017, 817

B.  817, 2017

C.  70817, 201

D.  20170, 817

参考答案：A、B

18、将二叉树的概念推广到三叉树，则一颗有364个结点的完全二叉树（只有根节点的树高度为1）的高度是（   ）。

A.  4

B.  5

C.  6

D.  7

E.  8

参考答案：C

题目应该为“则一棵有364个节点的完全3叉树的高度是”。

[Log3(364)]+1=5+1=6

19、请选择下列程序的输出（   ）。

#include<stdio.h>
 int mian()
{ 
  const int N = 10;
  const int M = 2;
  int* a = new int[N];
  for(int i=0;i<N;++i)
   a[i] = (0 ==i%2)?(i+2):(i+0);
  int(*b)[N/M] = (int(*)[N/M])a;
  for(int i = 0;i<M;++i)
   for(int j = 0;j<N/M;++j)
printf(“%d”,b[i][j]);
  return 0;
}

A.  2143658719

B.  2446688101

C.  3254769811

D.  2143668710

E.  21436587109

参考答案：E

a[]={2,1,4,3,6,5,8,7,10,9}

20、下面关于进程和线程说法正确的是（   ）。

A.  线程是CPU调度的基本单位

B.  进程是CPU调度的基本单位

C.  进程中多个线程可并发执行

D.  一个线程可以创建另一个线程

参考答案：A、C、D

编程题

1、拼凑硬币

 时间限制:（每个case）2s      空间限制：128MB

小Q十分富有，拥有非常多的硬币，小Q拥有的硬币是有规律的，对于所有的非负整数K，小Q恰好各有两个面值为2^K的硬币，所以小Q拥有的硬币就是1,1,2,2,4,4,8,8,…。小Q有一天去商店购买东西需要支付n元钱，小Q想知道有多少种方案从他拥有的硬币中选取一些拼凑起来恰好是n元（如果两种方案某个面值的硬币选取的个数不一样就考虑为不一样的方案）。

输入：

输入包括一个整数n(1<=n<=10^18)，表示小Q需要支付多少钱。注意n的范围。

输出：

输出一个整数，表示小Q可以拼凑出n元钱放的方案数。

【请注意：javascrip语言不支持调试，请同学们优先考虑使用其他语言，谢谢】

样例输入：6

样例输出：3

2、魔法城市

时间限制:（每个case）2s      空间限制：128MB

小Q来到一个魔法王国，这个王国一共有n个城市，分别是0~n-1号魔法城市，任意两个城市都有一条魔法通道连通（无向边），每条魔法通道都需要一定的时间才能通过。小Q现在在0号城市，他希望通过穿梭魔法通道到达1号魔法城市。

小Q为了更快到达1号魔法城市在魔法商店购买了一把魔力扫把，使用魔力扫把在一条魔法通道飞行的时候可以让该条魔法通道话费的时间减半，但是魔法扫把最多只能使用k次，小Q想知道他从0号魔法城市到1号魔法城市需要多少时间。

输入：

输入包括n+1行。

第一行中有两个正整数n, k(2<=n<=50, 0<=k<=50)，分别代表城市数量和魔力扫把可以使用的次数，以空格分割。

接下类n行，每行一个长度为n的字符串dis[i], dis[i][j](‘0’<=dis[i][j]<=’9’)表示从i号魔法城市到j号魔法城市需要的时间。

对于所有合法的i和j满足dis[i][j]=dis[j][i]

对于合法的i满足dis[i] = 0

输出：

输出一个实数表示小Q从0号魔法城市到1号魔法城市最少需要的时间，答案保留1位小数。

【请注意：javascrip语言不支持调试，请同学们优先考虑使用其他语言，谢谢】

样例输入：3  2

          094

          904

          440

样例输出：4.0

3、数字转换机

时间限制:（每个case）2s      空间限制：128MB

小Q从牛博士那里获得了一个数字转换机，这台数字转换机必须同时输入两个正数a和b，并且这台数字转换机有一个红色的按钮和一个蓝色的按钮：

当按下了红色按钮，两个数字同时加1。

当按下了蓝色按钮，两个数字同时乘2。

小Q现在手中有四个整数a，b，A，B，他希望将输入的两个整数a和b变成A，B（a对应A，b对应B）。因为牛博士允许小Q使用数字转换机的时间有限，所以小Q希望按动按钮的次数越少越好。请你帮帮小Q吧。

输入：

输入包括一行，一行中有四个正整数a，b，A，B，（1<=a，b，A，B<=10^9）。

输出：

如果小Q可以完成转换，输出最少需要按动按钮的次数，否则输出-1。

【请注意：javascrip语言不支持调试，请同学们优先考虑使用其他语言，谢谢】

样例输入：100  1000  202  2002

样例输出：2