腾讯2012425实习生招聘笔试题.pdf

1 计算表达式 x6 4x4 2x3 x 1 最少需要做 次乘法 A 3 B 4 C 5 D 6 2 给定 3 个 int 类型的正整数 x y z 对如下 4 组表达式判断正确的选项 int a1 x y z int b1 x y z int a2 x z y int b2 x z y int c1 x z int d1 x int c2 x z y int d2 x z A a1 一定等于 a2 B b1 一定定于 b2 C c1 一定等于 c2 D d1 一定等于 d2 3 程序的完整编译过程分为是 预处理 编译 汇编等 如下关于编译阶段的编译优化的 说法中不正确的是 A 死代码删除指的是编译过程直接抛弃掉被注释的代码 B 函数内联可以避免函数调用中压栈和退栈的开销 C For 循环的循环控制变量通常很适合调度到寄存器访问 D 强度削弱是指执行时间较短的指令等价的替代执行时间较长的指令 4 如下关于进程的描述不正确的是 A 进程在退出时会自动关闭自己打开的所有文件 B 进程在退出时会自动关闭自己打开的网络链接 C 进程在退出时会自动销毁自己创建的所有线程 D 进程在退出时会自动销毁自己打开的共享内存 5 在如下 8 6 的矩阵中 请计算从 A 移动到 B 一共有多少种走法 要求每次只能向上挥 着向右移动一格 并且不能经过 P A 492 B 494 C 496 D 498 6 SQL 语言中删除一个表的指令是 A DROP TABLE B DELETE TABLE C DESTROY TABLE D REMOVE TABLE 7 某产品团队由美术组 产品组 client 程序组和 server 程序组 4 个小组构成 每次构 建一套完整的版本时 需要各个组发布如下资源 美术组想客户端提供图像资源 需要 10 分钟 产品组向 client 组合 server 提供文字内容资源 同时进行 10 分钟 server 和 client 源代码放置在不同工作站上 其完整编译时间均为 10 分钟切编译过程不依赖于任 何资源 client 程序 不包含任何资源 在编译完毕后还需要完成对程序的统一加密过程 10 分钟 可以请问 从要完成一次版本构建 client 与 server 的版本代码与资源齐备 至少需要多少时间 A 60 分钟 B 40 分钟 C 30 分钟 D 20 分钟 8 如下关于编译链接的说法错误的是 A 编译优化会使得编译速度变慢 B 预编译头文件可以优化程序的性能 C 静态链接会使得可执行文件偏大 D 动态链接库会使进程启动速度偏慢 9 如下关于链接的说法错误的是 A 一个静态库中不能包含两个同名全局函数的定义 B 一个动态库中不能包含两个同名全局函数的定义 C 如果两个静态库都包含一个同名全局函数 他们不能同时被链接 D 如果两个动态库都包含一个同名全局函数 他们不能同时被链接 10 排序算法的稳定是指 关键码相同的记录排序前后相对位置不发生改变 下面哪种排 序算法是不稳定的 A 插入排序 B 冒泡排序 C 快速排序 D 归并排序 11 下列说法中错误的是 A 插入排序某些情况下复杂度为 O n B 排序二叉树元素查找的复杂度可能为 O n C 对于有序列表的排序最快的是快速排序 D 在有序列表中通过二分查找的复杂度一定是 O n log2n 12 在程序设计中 要对两个 16K 16K 的多精度浮点数二维数组进行矩阵求和时 行优 先读取和列优先读取的区别是 A 没区别 B 行优先快 C 列优先快 D 2 种读取方式速度为随机值 无法判断 13 字符串 所有非空子串 两个子串如果内容相同则只算一个 个数是 A 1024 B 1018 C 55 D 50 14 TCP 的关闭过程 说法正确的是 A TIME WAIT 状态称为 MSL Maximum Segment Lifetime 等待状态 B 对一个 established 状态的 TCP 连接 在调用 shutdown 函数之前调用 close 接口 可以让主动调用的一方进入半关闭状态 C 主动发送 FIN 消息的连接端 收到对方回应 ack 之前不能发只能收 在收到对方回复 ack 之后不能发也不能收 进入 CLOSING 状态 D 在已经成功建立连接的 TCP 连接上 如果一端收到 RST 消息可以让 TCP 的连洁端绕 过半关闭状态并允许丢失数据 15 操作系统的一些特别端口要为特定的服务做预留 必须要 root 权限才能打开的端口描 述正确的是 A 端口号在 64512 65535 之间的端口 B 所有小于 1024 的每个端口 C RFC 标准文档中已经声明特定服务的相关端口 例如 http 服务的 80 端口 8080 端口 等 D 所有端口都可以不受权限限制打开 16 找工作的季节马上就到了 很多同学去图书馆借阅 面试宝典 这本书 现在图书馆 外有 6 名同学排队 其中 3 名同学要将手中的 面试宝典 还至图书馆 有 3 名同学希望 从图书馆中可以借到 面试宝典 若当前图书馆内已无库存 面试宝典 要保证借书的 3 名同学可以借到书 请问这 6 位同学有多少种排队方式 A 60 B 120 C 180 D 360 二 填空题 1 除了 10 进制 2 进制之外 16 进制表达式在计算机领域中也经常使用 例如各种字符 集的定义描述 下式 2012 10 AF1 16的结果是 请用 10 进制表示 2 ack 3 3 的执行结果是多少 1 int ack int m int n 2 3 if m 0 4 return n 1 5 else if n 0 6 return ack m 1 1 7 else 8 return ack m 1 ack m n 1 9 3 某互联网产品 例如 一款网络游戏 同时在线曲线 Average Concurrency Users ACU 24 小时数据如下图所示 现已知全天平均在线人数为 5000 人 玩家每次登陆后平 均在线时长为 2 小时 请你估计一下 平均下来每分钟约有 个玩家登录 4 如下 SQL 语句是需要列出一个论坛版面第一页 每页显示 20 个 的帖子 post 标 题 title 并按照发布 create time 降序排列 SELECT title FROM post create time DESC 0 20 5 为了某项目需要 我们准备构造了一种面向对象的脚本语言 例如 对所有的整数 我 们都通过 Integer 类型的对象来描述 在计算 1 2 时 这里的 1 2 和结果 3 分别为 一个 Integer 对象 为了降低设计复杂度 我们决定让 Integer 对象都是只读对象 也即 在计算 a a b 后 对象 a 引用的是一个新的对象 而非改 a 所指对象的值 考虑到性能 问题 我们又引入两种优化方案 1 对于数值相等的 Integer 对象 我们不会重复创建 例如 计算 1 1 这里两个 1 的引用的是同一个对象 这种设计模式叫做 2 脚本语言解析器启动时 默认创建数值范围 1 32 的 32 个 Integer 对象 现在 假设我 们要计算表达式 1 2 3 40 在计算过程需要创建的 Integer 对象个数是 6 甲 乙两个人在玩猜数字游戏 甲随机写了一个数字 在 1 100 区间之内 将这个 数字写在了一张纸上 然后乙来猜 如果乙猜的数字偏小的话 甲会提示 数字偏小 一旦乙猜的数字偏大的话 甲以后就再也不会提示了 只会回答 猜对 或 猜错 问 乙至少猜 多少次 猜可以准确猜出这个数字 在这种策略下 乙猜的第一个数 字是 7 仔细阅读以下函数 Int fuc int m int n if m n 0 return n else return fuc n m n 请问 func 2012 2102 的结果是 加分题 1 给定一个数组 a N 我们希望构造数组 b N 其中 b i a 0 a 1 a N 1 a i 在构造过程 不允许使用除法 要求 O 1 空间复杂度和 O n 时间复杂度 除遍历计数器与 a N b N 外 不可使用新的变量 包括栈临时变量 对空间和全局静态变 量等 请用程序实现并简单描述 2 20 世纪 60 年代 美国心理学家米尔格兰姆设计了一个连锁信件实验 米尔格兰姆把信 随即发送给住在美国各城市的一部分居民 信中写有一个波士顿股票经纪人的名字 并要求 每名收信人把这封信寄给自己认为是比较接近这名股票经纪人的朋友 这位朋友收到信后再 把信寄给他认为更接近这名股票经纪人的朋友 最终 大部分信件都寄到了这名股票经纪人 手中 每封信平均经受 6 2 词到达 于是 米尔格兰姆提出六度分割理论 认为世界上任 意两个人之间建立联系最多只需要 6 个人 假设 QQ 号大概有 10 亿个注册用户 存储在一千台机器上的关系数据库中 每台机器存储 一百万个用户及其的好友信息 假设用户的平均好友个数大约为 25 人左右 第一问 请你设计一个方案 尽可能快的计算存储任意两个 QQ 号之间是否六度 好友是 1 度 可达 并得出这两位用户六度可达的话 最短是几度可达 第二问 我们希望得到平均每个用户的 n 度好友个数 以增加对用户更多的了解 现在如 果每台机器一秒钟可以返回一千条查询结果 那么在 10 天的时间内 利用给出的硬件条件 可以统计出用户的最多几度好友个数 如果希望得到更高的平均 n 度好友个数 可以怎样 改进方案 3 段页式虚拟存储管理方案的特点 参考答案 欢迎讨论 参考答案 欢迎讨论 转载请注明来转载请注明来 源源 选择题 1 A 原式 x 2 x 4 4 x 2 2 x x 1 x 2 用一次乘法 x 4 看成是 x 2 2 这样用掉第二次乘法 外面的 x 2 是第三次乘法 所有常系数乘 法都展开成连加 2 A 一开始觉得 A 肯定不对 因为会溢出 但不知道其实正如微机原理课上原的 溢出会有标识位 连加减的时候会考虑到这个标识位的作用 这样 A 就对了 3 A 死代码是指永远不会执行到的代码 不是注释 比如 if 0 大括号里的就 是死代码 4 D 共享内存销毁了 会对其他正在使用这段内存的进程造成破坏 5 A A 走到 B 共需要 12 步 其中 7 步必须向右 5 步必须向上 但次序可以不同 因此是 C 7 12 要求 P 不能走 那么走到 P 的可能次数是 C 3 6 从 P 走到 B 的可能 次数是 C 4 6 因此结果是 C 7 12 C 3 6 C 4 6 492 6 A 7 D 除了加密以外 剩下的事情在第一个 10 分钟内可以并发完成 8 B 9 C 10 C 快排选主元会打乱原次序 11 C A 当数据完全有序时就是 O n B 当数退化成线性表时 只有一叉时 出现 C 快排只对无序 随机序列有优势 D 是对的 12 B 13 D 长度 1 的子序列有 10 2 1 1 6 个 长度 2 子序列有 9 1 8 个 长度 3 有 8 个 长度 4 有 7 个 长度 10 有 1 个 加起来就是 50 14 D 15 C 16 C 卡特兰数 C n 2n n 1 n 是入栈元素的个数 这里 n 3 C 3 6 4 5 同学彼此是不同的 因此要全排列一下 结果为 5 3 3 180 填空题 1 4813 2 61 这个有规律的 只要耐心一点就行了 ack 1 x 2 x ack 2 x 3 x 2 ack 3 0 5 ack 3 1 ack 3 0 2 3 13 ack 3 2 ack 3 1 2 3 29 ack 3 3 ack 3 2 3 2 61 3 不会 4 ORDER BY LIMIT 5 享元模式 40 1 到 7 以及他们的和是不用创建的 从 8 开始 28 是 1 到 7 的 和 8 36 36 需要创建 36 9 45 45 需要创建 依次类推 在加数是 32 之前 含 32 需要创建的对象是 32 8 1 25 某数 32 某数之后 33 至 40 所表示的加数也要创 建 这样有 8 个加数 8 个和 共有 16 个数需要创建 注意 加数中包含 36 这个我们 已经创建了 所以有 25 8 8 1 40 个数的对象需要创建 6 14 次 第一次猜测数字为 14 思想是 每次猜大后 尝试猜测的总次数是相等的 第一次猜测时 在 1 到 100 之间选择某个数 N1 后 有三种情况 一是直接选中了 这个 概率比较小 对研究没有意义 二是选择偏大了 这时不再提示了 只能在 1 至 N1 1 之 间一个一个地选了 三是选择偏小了 这时还有提示 可以继续在 N1 1 100 中选择另外 的数 N2 可以知道 若第一次就猜错了 那么尝试总次数是 N1 1 1 N1 次 因为是在 1 N1 1 之间逐一取值 且 N1 本身用掉一次 若第一次猜得偏小 但第二次猜大了 尝试总次数是 N1 1 N2 1 的元素个数加 2 加 2 是 N2 和 N1 本身猜用掉一次 即为 N2 N1 1 次 根据思想 每次猜错后