腾讯2011年10月15日校招笔试+答案解析

2024-01-29 17:18

本文主要是介绍腾讯2011年10月15日校招笔试+答案解析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1、下面的排序算法中,初始数据集的排列顺序对算法的性能无影响的是()

A、插入排序                B、堆排序                 C、冒泡排序               D、快速排序

2、以下关于Cache的叙述中,正确的是()

A、CPU中的Cache容量应大于CPU之外的Cache容量

B、Cache的设计思想是在合理成本下提高命中率

C、Cache的设计目标是容量尽可能与主存容量相等

D、在容量确定的情况下,替换算法的时间复杂度是影响Cache命中率的关键因素

3、数据存储在磁盘上的排列方式会影响I/O服务的性能,一个圆环的磁道上有10个物理块,10个数据记录R1------R10存放在这个磁道上,记录的安排顺序如下表所示:

物理块

1

2

3

4

5

6

7

8

9

10

逻辑记录

R1

R2

R3

R4

R5

R6

R7

R8

R9

R10

假设磁盘的旋转速度为20ms/周,磁盘当前处在R1的开头处,若系统顺序扫描后将数据放入单缓冲区内,处理数据的时间为4ms(然后再读取下个记录),则处理这10个记录的最长时间为()

A、180ms                B、200ms              C、204ms                     D、220ms

4、随着IP网络的发展,为了节省可分配的注册IP地址,有一些地址被拿出来用于私有IP地址,以下不属于私有IP地址范围的是()

A、10.6.207.84            B、172.23.30.28            C、172.32.50.80               D、192.168.1.100

5、下列关于一个类的静态成员的描述中,不正确的是()

A、该类的对象共享其静态成员变量的值                          B、静态成员变量可被该类的所有方法访问                

C、该类的静态方法只能访问该类的静态成员变量                 D、该类的静态数据成员变量的值不可修改

6、已知一个线性表(38,25,74,63,52,48),假定采用散列函数h(key) = key%7计算散列地址,并散列存储在散列表A【0....6】中,若采用线性探测方法解决冲突,则在该散列表上进行等概率成功查找的平均查找长度为()

A、1.5                  B、1.7                           C、2.0                       D、2.3

7、表达式“X=A+B*(C--D)/E”的后缀表示形式可以为()

A、XAB+CDE/-*=                     B、XA+BC-DE/*=                      C、XABCD-*E/+=                         D、XABCDE+*/=

8、()设计模式将抽象部分与它的实现部分相分离。

A、Singleton(单例)                                      B、 Bridge(桥接)                    

C、 Composite(组合)                                   D、 Facade(外观)

9、下面程序的输出结果为多少?

  1. void Func(char str_arg[100]) 
  2.     printf("%d\n",sizeof(str_arg)); 
  3.  
  4. int main(void) 
  5.     char str[]="Hello"; 
  6.     printf("%d\n",sizeof(str)); 
  7.     printf("%d\n",strlen(str)); 
  8.     char *p = str; 
  9.     printf("%d\n",sizeof(p)); 
  10.     Func(str); 

10、C++将父类的析构函数定义为虚函数,下列正确的是哪个?
A、释放父类指针时能正确释放子类对象
B、释放子类指针时能正确释放父类对象
C、这样做是错误的
D、以上全错

11、下列哪一个不属于关系数据库的特点?
A、数据冗余度小
B、数据独立性高
C、数据共享性好
D、多用户访问

12、下面程序的输出结果为多少?

  1. void Func(char str_arg[2]) 
  2.     int m = sizeof(str_arg);   
  3.     int n = strlen(str_arg);      
  4.     printf("%d\n",m); 
  5.     printf("%d\n",n); 
  6. int main(void) 
  7.     char str[]="Hello"; 
  8.     Func(str); 

 

13、typedef char *String_t; 和 #define String_d char * 这两句在使用上有什么区别?

 

 

14、到商店里买200的商品返还100优惠券(可以在本商店代替现金)。请问实际上折扣是多少?

 

 

 

15、题目:已知rand7() 可以产生 1~7 的7个数(均匀概率),利用rand7()  产生rand10()   1~10(均匀概率)

 

 

 

 

16、给定能随机生成整数1到5的函数,写出能随机生成整数1到7的函数。

 

 

 

 

17、对一个正整数作如下操作:如果是偶数则除以2,如果是奇数则加1,如此进行直到1时操作停止,求经过9次操作变为1的数有多少个?

 

 

 

 

算法编程题:

1、给定一个字符串,求出其最长的重复子串。

 

参考答案(欢迎讨论)转载请注明来源http://www.cnblogs.com/jerry19880126/

  1. B。若序列事先已经基本有序,则插入法和冒泡法会明显减少比较次数,快速排序法与主元的选择有关,若一般选子序列左侧第一个元素比较,则第一个元素最好是大小居中的,以使得分成的两个子数组长度大致相等,性能才能最佳,所以快速排序也与初始输入集有关的。堆排序受数据集输入顺序影响最小。
  2. B。Cache(高速缓冲器)容量小于主存,但速度快于主存,慢于CPU,相当于CPU和主存间的一个缓冲器,Cache中存放最近使用过的内存内容(基于最近使用过的内容很可能被再次使用的原理)。若CPU寻访的内容在Cache中存放,则优先从Cache中读取,称为命中,否则称为脱靶,脱靶只能从主存中读取内容了。当Cache存储满的时候,用替换算法清理掉不用的内容,保留下最新或最常使用的内容,称为替换。Cache设计目标是提高命中率。替换算法确实是影响Cache命中率,但还有Cache容量、存储单元大小、组数多少、地址比较方法、写操作方法等都会影响Cache命中率。
  3. C。这道题终于会做了。是这样的原理,磁盘会一直朝某个方向旋转,不会因为处理数据而停止。本题要求顺序处理R1到R10,起始位置在R1,一周是20ms,共10个记录,所以每个记录的读取时间为2ms。首先读R1并处理R1,读R1花2ms,读好后磁盘处于R1的末尾或R2的开头,此时处理R1,需要4ms,因为磁盘一直旋转,所以R1处理好了后磁盘已经转到R4的开始了,这时花的时间为2+4=6ms。这时候要处理R2,需要等待磁盘从R5一直转到R2的开始才行,磁盘转动不可反向,所以要经过8*2ms才能转到R1的末尾,读取R2需要2ms,再处理R2需要4ms,处理结束后磁盘已经转到R5的开头了,这时花的时间为2*8+2+4=22ms。等待磁盘再转到R3又要8*2ms,加上R3自身2ms的读取时间和4ms的处理时间,花的时间也为22ms,此时磁盘已经转到R6的开头了,写到这里,大家已经可以看到规律了,读取并处理后序记录都为22ms,所以总时间为6+22*9=204ms。
  4. C。见实习生笔试里的解释。
  5. D。静态成员只要不是const的,每个对象都对其进行可以修改,但注意静态成员只有一份,修改后所有对象再访问的时候,都是最近修改后的数值了。
  6. C。解释如下,先分别求这六个数的余7后的结果,分别为3,4,4,0,3,6。列出一个表格,如下所示:

位置

0

1

2

3

4

5

6

记录

63

48

 

38

25

74

52

查找次数

1

3

 

1

1

2

4

38的余数是3,所以放在3号位置对应的记录里,25放在位置4,74求余的结果也是4,这就出现冲突了,线性探测就是往后移一格再存,所以放在5号位置了,按照这个方法依次放置到相应的位置。查找时,比如此时查找52,余数是3,本应位于3号位置,但3号位置被38占了,所以继续向后查找,4号位置没有,5号位置也没有,6号位置才查到,所以查找次数就是4次了。平均查找长度就是各数查找次数之和/6。

7. C。后缀形式,复习一下,其实不难的,注意运算优先级,”=”应是最后做的。

8. B。看看设计模式的书。

9. 6,5,4,4。第一个是求数组的大小,不要忘了’\0’,第二个是求字符串长度,注意strlen返回的长度是不包括’\0’的,指针的sizeof都是4字节(32位系统)。函数中形参虽是数组的形式,但实际传入的是指针(数组首地址),所以后面[100]其实没有用,还是4字节。

10. A。虚析构函数,C++多态。

11. D。

12. 4,5。同第9题解释,函数中的[2]其实是没有用的,因为只传数组首地址,就是指针,所以sizeof(指针)=4(32位系统),求strlen时是遇’\0’停止计数的,且不包括’\0’,所以是5。

13. 前者声明一个类型的别名,在编译时处理,有类型检查;后者是一个简单的替换,在预编译时处理,无类型检查。从使用上来说,String_t a,b; a和b都是char* 类型的,但String_d a,b; 只有a是char*类型的,b是char型的。

14. 需要自己去完善条件。比如优惠券本次消费是否就可以使用,还是要等到下次消费才可用,优惠券在消费多少时才可以使用等。举个简单的例子,比如只能下次消费使用,且满200才可以使用其中的50元优惠券,这样实际折扣为(200+200-50)/400=8.9折,继续买下去,折扣可以在8折左右。

15.如下:

复制代码
 1 int rand10()
 2 {
 3 int temp;
 4 int temp2;
 5 do 
 6 {
 7 temp = rand7();
 8 } while (temp > 5);//temp 1到5
 9 do 
10 {
11 temp2 = rand7();
12 while (temp2 > 2);//temp2 1到2
13 return temp + (temp2 - 1) * 5;
14 }
复制代码

16. 解法同15。

17. 最后一个必是2/2=1,前一个也必是4/2=2,再往前可以自己推几个,可以发现从9th到5th间隔内的分叉数依次是0,1,1,2,3,5,每次分叉就会多出一个可能的数,找规律可以推测是Fabbonaci数列,所以结果应该1+1+2+3+5+8+13=33,别忘了即使是0分叉也包含了自身一个数,所以最终结果是34。

18. 如下:

复制代码
 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <vector>
 5 
 6 using namespace std;
 7 
 8 class LongestCommonString
 9 {
10     vector<string> suffixArray;
11     size_t len;
12 public:
13 
14     //构造方法
15     LongestCommonString(string s)
16     {
17         //构造后缀数组
18         for(size_t i = 0; i < s.length(); ++i)
19         {
20             suffixArray.push_back(s.substr(i));
21         }
22         //排序
23         sort(suffixArray.begin(), suffixArray.end());
24         len = suffixArray.size();
25     }
26 
27     //两两比较,返回最长长度的子串
28     string lcpCompare()
29     {
30         size_t maxLength = 0;
31         size_t index = 0;
32         for(size_t i = 0; i < len - 1; ++i)
33         {
34             size_t temp = lcp(suffixArray.at(i), suffixArray.at(i+1));
35             if(temp > maxLength)
36             {
37                 maxLength = temp;
38                 index = i;
39             }
40         }
41         return suffixArray.at(index).substr(0, maxLength);
42     }
43 
44     //返回重复的长度
45     size_t lcp(const string& a, const string& b)
46     {
47         size_t i = 0;
48         while(a[i] == b[i])
49         {
50             ++i;
51         }
52         return i;
53     }
54 };
55 
56 int main()
57 {
58     string h = "hello";
59     //cout << h.substr(2, 3);
60     string word = "aacaagmtttacaagmc";
61     LongestCommonString slcp(word);
62     cout << "最长重复子串为:" << slcp.lcpCompare() << endl;
63 }
复制代码
转自: http://www.cnblogs.com/jerry19880126/archive/2012/08/05/2623954.html

这篇关于腾讯2011年10月15日校招笔试+答案解析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/657617

相关文章

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库,完全使用 Python 语言编写,它对 XPath表达式提供了良好的支 持,因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块,该模块专门用来解析 HTML/XML 文档,下面来介绍一下 lxml 库

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

这15个Vue指令,让你的项目开发爽到爆

1. V-Hotkey 仓库地址: github.com/Dafrok/v-ho… Demo: 戳这里 https://dafrok.github.io/v-hotkey 安装: npm install --save v-hotkey 这个指令可以给组件绑定一个或多个快捷键。你想要通过按下 Escape 键后隐藏某个组件,按住 Control 和回车键再显示它吗?小菜一碟: <template

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

poj 3104 二分答案

题意: n件湿度为num的衣服,每秒钟自己可以蒸发掉1个湿度。 然而如果使用了暖炉,每秒可以烧掉k个湿度,但不计算蒸发了。 现在问这么多的衣服,怎么烧事件最短。 解析: 二分答案咯。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <c

OWASP十大安全漏洞解析

OWASP(开放式Web应用程序安全项目)发布的“十大安全漏洞”列表是Web应用程序安全领域的权威指南,它总结了Web应用程序中最常见、最危险的安全隐患。以下是对OWASP十大安全漏洞的详细解析: 1. 注入漏洞(Injection) 描述:攻击者通过在应用程序的输入数据中插入恶意代码,从而控制应用程序的行为。常见的注入类型包括SQL注入、OS命令注入、LDAP注入等。 影响:可能导致数据泄

从状态管理到性能优化:全面解析 Android Compose

文章目录 引言一、Android Compose基本概念1.1 什么是Android Compose?1.2 Compose的优势1.3 如何在项目中使用Compose 二、Compose中的状态管理2.1 状态管理的重要性2.2 Compose中的状态和数据流2.3 使用State和MutableState处理状态2.4 通过ViewModel进行状态管理 三、Compose中的列表和滚动

Spring 源码解读:自定义实现Bean定义的注册与解析

引言 在Spring框架中,Bean的注册与解析是整个依赖注入流程的核心步骤。通过Bean定义,Spring容器知道如何创建、配置和管理每个Bean实例。本篇文章将通过实现一个简化版的Bean定义注册与解析机制,帮助你理解Spring框架背后的设计逻辑。我们还将对比Spring中的BeanDefinition和BeanDefinitionRegistry,以全面掌握Bean注册和解析的核心原理。

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

一、题目阅读 (最大值之和)给定整数序列 a0,⋯,an−1,求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。 一个序列的非空连续子序列可以用两个下标 ll 和 rr(其中0≤l≤r<n0≤l≤r<n)表示,对应的序列为 al,al+1,⋯,ar​。两个非空连续子序列不同,当且仅当下标不同。 例如,当原序列为 [1,2,1,2] 时,要计算子序列 [

多线程解析报表

假如有这样一个需求,当我们需要解析一个Excel里多个sheet的数据时,可以考虑使用多线程,每个线程解析一个sheet里的数据,等到所有的sheet都解析完之后,程序需要提示解析完成。 Way1 join import java.time.LocalTime;public class Main {public static void main(String[] args) thro