【www.gbppp.com--行业知识】
百度SEM初级认证试题及答案（上）
百度搜索引擎营销认证旨在为整个行业梳理规范、储备潜在人才、构建积极健康的搜索营销生态圈，进一步促进搜索引擎营销的繁荣和可持续发展。百度搜索引擎营销认证主要是对操作人员百度竞价推广能力的一个评判，包括百度竞价的账户设置、创意编辑、匹配方式、出价原则、点击价格、转换成本等。认证对其能力和资质进行权威认可。共分为3个级别的认证：
百度认证搜索推广专员(初级认证)：面向搜索推广方案执行与账户操作人员。 百度认证搜索营销顾问(中级认证)：面向搜索营销策略制定与分析优化人员。 百度认证网络营销专家(高级认证)：面向数字营销战略规划人员。
下面是百度SEM初级认证试题及答案，由于内容比较长，所以分为3部分，以下是百度SEM初级认证试题及答案（上）：
1、某账户设定的消费额度为100元，在当天消费还未达限时，将消费额度修改为200元，请问账户当天预算消费完下线时，当天消费与下面哪一个金额最接近?
A：190
B：220
C：110
D：100
答案解析：正确答案是B，答案很简单，因为当日预算已经修改为200元，答案ACD都没有达到上限的标准，所以肯定是错误的。如果这个账户里有个关键词的单次点击价格是30元，在账户消费190元时被点击了，那被点击的费用也当然会被扣除了，所以最接近的是B。
2、小郑想看到网民通过搜索什么词触发的广告，他可以通过运行什么报告来实现? A：搜索词报告
B：关键词报告
C：创意报告
D：账户报告
答案解析：正确答案是A，只有搜索词报告可以查看网民通过哪些搜索词访问了推广结果。
3、在新风巢系统中，目前客户可以定制的报告不包括：
A：分地域报告
B：无效点击报告
C：搜索词报告
D：创意报告
答案解析：正确答案是C,因为在新风巢系统中搜索词报告可以直接生成，无需定制。
4、对下列关键词进行分组，哪一分组比较合理：汽车、商务轿车、大众腾迈、一汽大众、vlovo、沃尔沃、沃尔沃s801、volvoS40
A：汽车、商务轿车、大众腾迈
B：汽车、一汽大众、volvo
C：商务轿车、volvo、volvoS40
D：volvo、沃尔沃
答案解析：正确答案是D，因为A和B都包含“汽车”通用词和品牌词，C更是包含通用词、品牌和型号词无法更有针对性撰写创意，而D是品牌词和品牌的别称词，相对ABC来说D的组合更为合理。
5、境外旅游关键词组里现包含出国旅游，境外旅游景点等词，请问哪个关键词不适合放到该组?
A：出国旅游路线
B：境外旅游胜地
C：国外旅行
D：出境游报价
答案解析：正确答案是D，因为答案D尽管相关，但是为价格词，放在该组景点词里，创意撰写的针对性不强，特点不突出。应该放在价格组。
6、在游戏、视频等内容加载前或者暂停时，在窗口中央用图片或者动画的形式展现推广信息，是网盟推广的什么形式。
A：贴片
B：固定
C：文字链
D：悬浮
答案解析：正确答案是A。
悬浮：显示网页正文区域以外，且能够随着滚动条保持与浏览器绝对垂直位置的图片推广，称之为悬浮形式推广。
固定：显示于网页正文区域内，在页面中有固定位置的推广(即普通的文字和图片)称之
为固定形式推广。此与悬浮为相对概念。
贴片：显示在游戏、视频加载或者暂停时时，在窗口中央用图片或动画的方式展现，称之为贴片形式推广。
7、推广单元“理财保险-福禄双喜”创意如下：标题：中国人寿保险{福禄双喜保险}^,满期还本,享受分红;描述1：中国人寿保险福禄双喜集返还分红保障于一身,^生存保险金+满期保险金+身故保险金。描述2：规划财富人生,给您多重收益和生命保障。中国人寿,相知多年,值得托付! 以下哪组关键词不适合分到该组别中?
A：国寿福禄双喜保险、中国人寿福禄双喜
B：福禄双喜保险、福禄双喜两全保险
C：福禄双喜、福禄双喜两全
D：福禄双喜两全保险、福禄双喜分红保险
答案解析：正确答案是A，没能传递给客户更多有用的信息，在创意通顺的方面也有所影响。
8、小李用后台生成了一个报告，得到的数据如下表，请问问号处(CPM)是多少?
A. 100
B. 20
C. 50
D. 10
答案解析：正确答案为A，CPM为每千次印象费用。广告条每显示1000次(印象)的费用。CPM(千人成本)指的是广告投放过程中，听到或者看到某广告的每一人平均分担到多少广告成本。传统媒介多采用这种计价方式。比如说一个广告横幅的单价是1元/CPM的话，意味着每一千个人次看到这个Banner的话就收1元，如此类推，10，000人次访问的主页就是10元。CPM=消费/(展现量/1000)=(0.5*2000)/(10000/1000)=100
9、某推广商户从百度推广带来数据是展现量为10000，点击量为500，PV为2500，请问CTR为多少：
A：5%
B：10%
C：80%
D：6.25%
答案解析：正确答案是A，因为CTR是点击率的简称，计算公式：点击率=点击量/展现量*100%;而图中的现有点击量为500，曝光量也就是展现量为10000，流量(浏览次数)在计算点击率时无意义可以直接忽略。那么：500/10000*100%=5%
10、下列哪项建议对于需要提升咨询量的客户有直接的帮助?
A：提高电话接听人员的营销能力
B：将网站上的电话放在更明显的位置
C：针对客广问题做出专业解答
D：确保接到在线咨询时能快速做出反应
答案解析：正确答案是B，问题是要求为直接提升咨询量，而不是订单量，而答案ACD都是对提升订单量有帮助的，所以只有B可以有效提升咨询量。
11、本组关键词有“外汇模拟软件、外汇交易软件、外汇软件”，如下哪个关键词添加至该组最合适?
A：外汇交易
B：炒外汇
C：炒汇软件
D：外汇保证金模拟
答案解析：正确答案是C;因为本组关键词都是有关外汇软件方面的，外汇交易类的词语放在本组当然不合适了。
12、某推广商户撰写了创意如下，网民搜索“学生假期托管班”触发了商户所设置的关键词“假期托管班”，则推广信息在前台推广链接展示时应为：
A:比假期托管班更好的夏令营
专业师资,英语学习,户外活动,寓教于乐,即可登陆官网了解详情!
B:比托管更好的夏令营
专业师资,英语学习,户外活动,寓教于乐,即可登陆官网了解详情!
C:比学生假期托管班更好的夏令营
专业师资,英语学习,户外活动,寓教于乐,即可登录官网了解详情! 去{假期托管}不如参加学习夏令营真实的英语学习环境,快乐学习,祝您一臂之力.
D:比假期托管班更好的夏令营
专业师资,英语学习,户外活动,寓教于乐,即可登录官网了解详情!
答案解析：正确答案是D，这里需要了解的就是不管短语匹配还是广泛匹配，网民的搜索词并不会全部带入到推广创意中，被带入其中的关键词为搜索词所触发的关键词，明白了这个道理，我们只需要找出哪条创意带入了触发关键词，就能找到正确答案。
13、在多个层级进行同一功能设置，实际执行结果为高级别优先执行，这一规则适用于：
A：分地域投放
B：普通暂停
C：否定关键词
D：IP排除
答案解析：正确答案是A，因为答案BCD都是包含在内的多个层级同时生效的，而在这里高级别优先的概念是如果每个层级设置得不一样，各个层级间哪个层级的优先级更高，我们在设置投放地域时账户级别越小优先级就越高。
14、将“英文小说”这个词设定为否定精确匹配，潜在用户搜索如下哪些词，将看不到客户结果?
A：英文小说
B：小说英文版
C：英文小说下载
D：英文著名小说
答案解析：正确答案是A，否定关键词的否定模式，否定关键词分为两种：一、精确否定关键词(与搜索词完全一致时不会展现结果);二、否定关键词(搜索词中包含否定关键词时不会展现结果)。题目中的设置为精确否定关键词，所以正确答案为A。
15、某推广信息具体的展现与排名情况如下，则该推广信息的平均排名为多少?
A：3.5
B：3
C：2.9
D：3.33
答案解析：正确答案是B，这道题首先没有给定相应的关键词出价和质量度，只是给出排名情况和点击、展现次数，让计算平均的排名是多少，那么只需要：平均排名=(排名A+排名N)/个数=(4+2+3)/33。
百度给出的定义是：您可以在定制报告的关键词报告中查看关键词的平均排名。在每次展现时，我们的系统会按照质量度和出价计算得到您的推广结果的综合竞争力，并按照该综合竞争力自动得到您推广结果的排名。关键词的平均排名就是您的推广结果排名的一个平均表现。从整体上来说，平均排名越高，说明您的推广结果在展现时获得的排名位置越优，您的网站获得客户访问的次数也可能越多。值得注意的是，平均排名只是反映了当前关键词的整体表现，您推广结果的展现位置请以实际线上表现为准。
16、以下关于订单产生过程反映在搜索推广效果转化漏斗上的表述，说法不正确的是： A：“订单量”反映了“线下销售阶段”
B：“成交量”反映了“效果评估阶段”
C：“访问量和咨询量”反映了“企业网站阶段”
D：“展现量和点击量”反映了“百度推广阶段”
一、算法设计
1、设rand（s，t）返回[s,t]之间的随机小数，利用该函数在一个半径为R的圆内找随机n个点，并给出时间复杂度分析。 思路：这个使用数学中的极坐标来解决，先调用[s1，t1]随机产生一个数r，归一化后乘以半径，得到R*（r-s1）/（t1-s1），然后在调用[s2，t2]随机产生一个数a，归一化后得到角度：360*（a-s2）/（t2-s2）
2、为分析用户行为，系统常需存储用户的一些query，但因query非常多，故系统不能全存，设系统每天只存m个query，现设计一个算法，对用户请求的query进行随机选择m个，请给一个方案，使得每个query被抽中的概率相等，并分析之，注意：不到最后一刻，并不知用户的总请求量。
思路：如果用户查询的数量小于m，那么直接就存起来。如果用户查询的数量大于m，假设为m+i，那么在1-----m+i之间随机产生一个数，如果选择的是前面m条查询进行存取，那么概率为m/（m+i），如果选择的是后面i条记录中的查询，那么用这个记录来替换前面m条查询记录的概率为m/（m+i）*（1-1/m）=(m-1)/(m+i)，当查询记录量很大的时候，m/（m+i）== (m-1)/(m+i)，所以每个query被抽中的概率是相等的。
3、C++ STL中vector的相关问题： （1）、调用push_back时，其内部的内存分配是如何进行的？ （2）、调用clear时，内部是如何具体实现的？若想将其内存释放，该如何操作？ vector的工作原理是系统预先分配一块CAPACITY大小的空间，当插入的数据超过这个空间的时候，这块空间会让某种方式扩展，但是你删除数据的时候，它却不会缩小。 vector为了防止大量分配连续内存的开销，保持一块默认的尺寸的内存，clear只是清数据了，未清内存，因为vector的capacity容量未变化，系统维护一个的默认值。 有什么方法可以释放掉vector中占用的全部内存呢?
标准的解决方法如下 template < class T >
void ClearVector( vector< T >& vt ) { vector< T > vtTemp; veTemp.swap( vt ); } 事实上，vector根本就不管内存，它只是负责向内存管理框架acquire/release内存，内存管理框架如果发现内存不够了，就malloc，但是当vector释放资源的时候(比如destruct), stl根本就不调用free以减少内存，因为内存分配在stl的底层：stl假定如果你需要更多的资源就代表你以后也可能需要这么多资源(你的list, hashmap也是用这些内存)，所以就没必要不停地malloc/free。如果是这个逻辑的话这可能是个trade-off 一般的STL内存管理器allocator都是用内存池来管理内存的，所以某个容器申请内存或释放内存都只是影响到内存池的剩余内存量，而不是真的把内存归还给系统。这样做一是为了避免内存碎片，二是提高了内存申请和释放的效率——不用每次都在系统内存里寻找一番。
二、系统设计
正常用户端每分钟最多发一个请求至服务端，服务端需做一个异常客户端行为的过滤系统，设服务器在某一刻收到客户端A的一个请求，则1分钟内的客户端任何其它请求都需要被过滤，现知每一客户端都有一个IPv6地址可作为其ID，客户端个数太多，以至于无法全部放到单台服务器的内存hash表中，现需简单设计一个系统，使用支持高效的过滤，可使用多台机器，但要求使用的机器越少越好，请将关键的设计和思想用图表和代码表现出来。
三、求一个全排列函数： 如p([1,2,3])输出： [123]、[132]、[213]、[231]、[321]、[312] 求一个组合函数。
方法1：依次从字符串中取出一个字符作为最终排列的第一个字符，对剩余字符组成的字符串生成全排列，最终结果为取出的字符和剩余子串全排列的组合。 优点：该方法易于理解，但无法移除重复的排列，如：s="ABA"，会生成两个“AAB”。 方法2：利用交换的思想，具体见实例，但该方法不如方法1容易理解。 我们以三个字符abc为例来分析一下求字符串排列的过程。首先我们固定第一个字符a，求后面两个字符bc的排列。当两个字符bc的排列求好之后，我们把第一个字符a和后面的b交换，得到bac，接着我们固定第一个字符b，求后面两个字符ac的排列。现在是把c放到第一位置的时候了。记住前面我们已经把原先的第一个字符a和后面的b做了交换，为了保证这次c仍然是和原先处在第一位置的a交换，我们在拿c和第一个字符交换之前，先要把b和a交换回来。在交换b和a之后，再拿c和处在第一位置的a进行交换，得到cba。我们再次固定第一个字符c，求后面两个字符b、a的排列。 既然我们已经知道怎么求三个字符的排列，那么固定第一个字符之后求后面两个字符的排列，就是典型的递归思路了。 基于前面的分析，我们可以得到如下的参考代码： 如p([1,2,3])输出： [1]、[2]、[3]、[1,2]、[2,3]、[1,3]、[1,2,3] 这两问可以用伪代码。
北京 产品设计 笔试
纯文科背景，很简单的互联网产品经验，报百度纯粹是志趣所在。 笔试题与大家分享，如果是真心喜欢互联网行业的同学肯定觉得题目很简单。
1. 选一个你熟悉的百度产品，针对用户体验提出改进意见。
2. 设计一个在线音乐播放器的界面并说明设计思路。
3. 设计几个指标衡量百度图片所搜的用户体验。
4. 有一个手机通讯软件的添加好友界面，评述优点和确定，平提出建议。
5. 冰箱通常带有照明灯，请说明这一设计的必要性和适用场景。以及微波炉是否需要这一功能？为什么？
2013年百度商业业务分析笔试题
一、推理题
1、 根据已有信息判断正误
All people love running
Some people love cook（类似，记不清了）
Some people look like their masters
判断下面几句话正误
比如 all people loving run love cook
People love run look like their masters 等
2、 有2只红袜子、20只黄袜子，31只蓝袜子，问抽几只袜子，能确保抽到两只颜色一样的？
3、 有50个红球，50个蓝球，两个罐子，随机抽取一个罐子，随机抽取一个球放入罐子，问如何能让抽到红球的概率最大？（所有球的进入罐子）在这样的设计下，球数应该增多还是减少？
4、 象棋中，如果最后只剩下了将和帅，有多少种状态是没有结果的？
5、 推理题
8个将军射猎，其中一个人射中了鹿，但是国王让大家猜是谁射中的，8个人每人一句话，国王说只有三个人说的是对的，问谁射中了鹿？如果五个人说的是对的，那么是谁射中的？
6、 切金子问题
15cm长的金子，每天给工人1cm，三刀，如何切？若是16cm可以么？
7、 一个女生想找三高男，高个子、高收入、高学历，A、B、C、D只有一个满足要求，给了几个条件：
（1） A和B收入一样
（2） C和D身高情况相反
（3） 三个高个子，两个高收入，一个高学历（记不太清了，大概类似条件）
问谁是三高男？
二、选答题
1、 给出一个SNS网站推荐好友功能的策略设计。
2、 移动互联网与PC互联网的异同，在商业流量变现的角度看两者的优劣势，那么搜索推广如何？
3、 一个研究者对于广告页面绿色对点击率影响的统计，第一页和第二页都显示绿色会增加点击率，但综合统计显示没有明显关系，请问是为什么？采用什么统计方法进行分析？
4、 公交IC卡的一个问题，它不只是一个金融工具，也可以提供很多用户数据。从公交站、广告商等角度看广告的投放？（没仔细看。。）
【面经】
百度系统工程师（基础网络）北京
有点小惊讶，三次面试竟然全部都是电话面试。而且三次面试都是技术面试。但是个人觉得百度的网络岗位技术面试跟其他的公司很不一样。
1.百度重视基础知识，一些类似于传统的三次握手肯定是必问
2.百度重视应用，经常是给你一个拓扑，围绕着拓扑询问。从某个知识点出发，但是又不拘泥于这个知识点，遗憾的是这一部分掌握的不是很好
3.百度比较人性化，问你一些问题的时候会事先征求你的意见，例如问路由协议的话他会提前问你，你觉得那一块掌握的比较好。我觉得这一块我回答的挺不错的。
4.百度重视与面试者之间的互动。同百度的老师们沟通交流时很愉快的一件事情，因为不像【百度直接笔试】
其他公司搞的那么严谨，你在回答问题的时候有很多机会可以跟老师们沟通交流。有些方向你想歪了，面试官会温馨的提醒你。总之有点类似于学生跟老师沟通交流某个问题时候的感觉啊。
百度上海，开发测试，三面归来
一面：
预定时间是22号下午四点。 我回去东一把数据结构，西一把算法，都不知道复习什么好了。 因为知道百度刷人刷得挺狠的，之前同学面试笔试北京百度的时候，不少都尘沙折戟了。 第二天，心情沉重的过去了，结果三点多就轮到我了。 面我的是个很阳光清爽的GG。 开始让我自我介绍，说说学校的情况，以及简历上的实验室项目和实习项目。 然后他询问了一些感兴趣的部分，以及一些项目的细节，这些不在话下。
总体说来，一面问的东西蛮多的，也蛮全面的，好像一个小时二十多分钟，时间挺长的。包括一些常用的linux命令、网络编程（估计因为项目涉及，所以就问了）、指针、数组指针、C++内存分配、函数压栈、数据库等等。 大部分是我擅长的东西，自我感觉前面答得还不错，但是我回去之后核查了几个问题，发现有个内联函数的问题答得不太精确，难怪那位GG后来又问我宏定义的问题，好在宏定义上面没有弄错，估计那位GG以为我记得稍微模糊了点，所以放了我一马。 后面写了几个代码，如果平时在学校认真学，应该都没问题，没有传说中的那么恐怖，当然，也不排除我运气问题。 第一个是输出1-100中所有的素数； 第二个是链表反转 第三个是Y链表 可能因为第二个代码写得不太好，指针指来指去，把自己绕晕了，然后就有点紧张，再加上当时屋子里有好几对面试的，周围一直嗡嗡的响，后来那位GG可能看出来了我的状态了，就提示了几下，终于搞定。然后，又补问了第三个问题。 以为自己没戏了，挂在链表上了，回来路上就开始各种伤心，觉得链表逆序，那么经典基础的东西怎么可以不会呢，特别的自责，连地铁都坐过好多站。 没想到，晚上收到二面通知：22号三点。 兴奋又感激，看来那位GG看我前面回答的不错的份上，给了我第二次机会。 于是我把指针重点复习了一下，顺带着看了看二叉树部分，还扫了几眼B树，B+树之类的。 又临时抱佛脚的在网上找了半天的面经，有今年的，也有往年的。
二面： 忐忑过去二面。 二面到楼上，面试官先让自我介绍，然后问是一面还是二面（当天好像也有一面的人）。 我如实回答是二面。然后，因为是侧面坐的关系（一面是面对面），我看见他在电脑上调出我的资料，于是就进入了二面的正题。 第一个是循环指针的问题，幸亏我之前复习过一点，阿弥陀佛！ 第二个问题是树的遍历问题，也过关了。 然后就让写代码，输出一颗树的所有邻居节点对。 貌似那位哥哥对我的数据结构设计还比较满意，看了下程序，问了几个问题，肯定了我的答案之后，又问有没有更好的，建议让用递归的过程。我想了一会，没想出来，于是说，递归因为会影响性能，所以平常能不用就不用，我一时可能想不出来。 然后就扯了会编程风格的问题，这题算勉强通过了吧。 然后，那位GG说，下面再来一个难点的吧。 题目大概意思是，有一个容器，容量为S，还有N个物品，体积是个随机值，为Wn=ran(i)。问怎样用最快的方式把容器正好装满。 我当时用了贪心算法 和0-1背包问题的大致思想解决的，然后那位哥哥就让我求其复杂度。 后来那位哥哥说，用B树的方式速度更快，就给我分析原因。 我如实回答，基本没有用过B树，只是对其有个大概的印象。 本来以为还有第三题，或者过不了关，谁知道下面那位GG忽然就问我手头有
offer了没，以及对百度的印象啥的， 然后就让我回三楼等三面了。 我当时那个激动啊，差点没反应过来。
三面：
三面比较轻松，基本没有技术问题。 看样子应该是个manager之类的，问了些学校的情况，实习的情况，还有一些个人职业规划的问题，对个人履历又挑了些感兴趣的部分进行询问，还有一些模拟的情景问题，但不是不着边际的，一点也不刻意，估计是以后可能发生的事，比如关于加班的问题等等。 然后问我有什么问题问他没，我看时间不早了，早过了下班时间，也 没好意思多问，就问了几个我最关心的问题。 也挺佩服这个manager的（我猜他是manager），感觉像，一天下来，估计得面不少的人，跟我讲话的时候，一直保持亲切的笑容，一点疲惫的状态也没有。我最后咨询他的问题，他也很耐心细致的回答了，除了不告诉我 我究竟能不能过三面（吐舌~~~）
总体上，三面聊得还是比较愉快的。 我现在只担心，当时我的话太多了，会“言多必失”，说了不该说的了。 也可能这就是那个manager的高明之处吧，让你有话可说。就是不知道自己有没有不小心踩到“雷区”。
总结： 总得说来，百度的工作效率还是特别高的，除了三面过后，之前一直特别快（当然，三面慢，也不排除被秒杀的可能）。 面试的时候，前后三位面试官，人都很nice。 出题目的时候，会有适当的提醒与引导， 写代码之前，都会让你先复述一下你的想法，想法通过了，他们觉得有可行性了，再让你下笔。只考察他们想考察的部分，不会因为非考察重点部分，就给你一个叉叉。 这也许这也是他们没有二次笔试的原因吧。 面对面的交流，可以让他们更准确的筛选到他们想要的人。 我记得我那个百度的学长说过，他们想要的是聪明的人，不是死记硬背的人。 比如我第一天写那个链表逆序的时候，因为我前一天瞄过一眼，觉得那段代码写得挺好的，当时我就特别想把代码重现，结果记忆力跟不上，没重现了，然后就紧张，就更难静心写了。 其实当时，我已经有了大致的思想，那位面试GG也通过了我的想法了，我当时不用想着重现某本教材上的代码，只要自己按照自己的方式写就行了。 二面的时候我就吸取了这个教训，复习的时候，只看大体的思路，临场把想法想好，被面试官通过之后，自己重新设计数据结构，重新编写代码。可能速度上稍微慢了点，但是起码能把想法很好的表达出来。
一、算法设计
1、设rand（s，t）返回[s,t]之间的随机小数，利用该函数在一个半径为R的圆内找随机n个点，并给出时间复杂度分析。 思路：这个使用数学中的极坐标来解决，先调用[s1，t1]随机产生一个数r，归一化后乘以半径，得到R*（r-s1）/（t1-s1），然后在调用[s2，t2]随机产生一个数a，归一化后得到角度：360*（a-s2）/（t2-s2）
2、为分析用户行为，系统常需存储用户的一些query，但因query非常多，故系统不能全存，设系统每天只存m个query，现设计一个算法，对用户请求的query进行随机选择m个，请给一个方案，使得每个query被抽中的概率相等，并分析之，注意：不到最后一刻，并不知用户的总请求量。
思路：如果用户查询的数量小于m，那么直接就存起来。如果用户查询的数量大于m，假设
一、dijkstra最短距离算法
Java实现dijkstra算法： 地图中任意起点寻找最佳路径
import java.util.*; public class Dijkstra {
ArrayList <Node>Collection = ArrayList<Node>(); //储存所有的点 ArrayList <Node>Route = ArrayList<Node>(); //记录路径 ArrayList <Node>Waiting = ArrayList<Node>();//此轮候选的点 String current = null; int length = 0; boolean addNodes(){
Collection.add(new Node("A","B",20)); Collection.add(new Node("A","D",80)); Collection.add(new Node("A","G",90)); Collection.add(new Node("B","F",10)); Collection.add(new Node("C","F",50)); Collection.add(new Node("C","H",20)); Collection.add(new Node("C","D",10)); Collection.add(new Node("D","G",20)); Collection.add(new Node("D","C",10)); Collection.add(new Node("E","B",50)); Collection.add(new Node("E","G",30)); Collection.add(new Node("F","C",10)); Collection.add(new Node("F","D",40)); Collection.add(new Node("G","A",20)); return true; }
new new new
void setNext(String nt){ current = nt; }
void update(ArrayList<Node> wl){ ArrayList<Node> update = ArrayList<Node>(); for(Node a:wl){
for(Node b:wl){ if(a.getDest() == b.getDest()&&a.getDist()<b.getDist()){ update.add(b); }}}
for(Node c:update){ wl.remove(c); } }
void Remove(ArrayList<Node> coll,String nt){
ArrayList<Node> ArrayList<Node>(); for(Node a:coll){ if(nt == a.getDest()) move.add(a); } for(Node a:move){ if(coll.contains(a)) coll.remove(a);
} }
void linkRoute(ArrayList<Node> rt){
move
=
new new
ArrayList<Node> linkroute = new
ArrayList<Node>(); int last = rt.size()-1;
for(int i=rt.size()-2;i>-1;i--){
if(rt.get(last).getDep() != rt.get(i).getDest()){ linkroute.add(rt.get(i)); }else
if(rt.get(last).getDep()
==
rt.get(i).getDest()){ last = i; } }
for(Node a:linkroute){ rt.remove(a);
} }
void toWait(String nt){ Remove(Collection,current); for(Node a:Collection){
if(nt == a.getDep()){ Waiting.add(new
Node(a.getDep(),a.getDest(),a.getDist()+length)); } }
for(Node b:Waiting){ if(Collection.contains(b)) Collection.remove(b); } update(Waiting); }
boolean selectNext(ArrayList<Node> wl){ if(wl.size() == 0){ System.out.println("done"); return false;
}else if(wl.size() == 1){ current = wl.get(0).getDest(); length = wl.get(0).getDist(); Route.add(Route.size(), wl.get(0)); wl.remove(wl.get(0)); }else{
Node s = wl.get(0); for(Node a:wl){
if(a.getDist()<s.getDist()){ s = a; } }
current = s.getDest();
length = s.getDist();
Route.add(Route.size(), s);
wl.remove(s);//将waiting list中的这一点删
去 }
return true; }
public void wrap(String start, String stop){ current = start; if(addNodes()){ for(int i=0;;i++){ if(stop == current){ //Route.add(); break;} toWait(current); if(selectNext(Waiting)) continue; else break; }
if(Route.size()!=0&&Route.get(Route.size()-1).getDest()==stop){
linkRoute(Route);
System.out.print(Route.get(0).getDep()+" -> ");
for(Node a:Route){
System.out.print(a.getDest()+" "); }
System.out.print("distance:
"+Route.get(Route.size()-1).getDist()+"\n"); } else
System.err.println("no fucking way"); } }
public static void main(String[] args){ new Dijkstra().wrap("A","G"); } }
class Node{ String From; String To;
int distance;
Node(String f, String t, int d){ this.From = f; this.To = t; this.distance = d; } public String getDep(){ return this.From; } public String getDest(){ return this.To; } public int getDist(){ return this.distance; } }
2、x数轴上有一系列的线段，求重合距离最大的两个线段。例如l1[1,8],l2[3,9],l3[8,10],那么重合距离最大的是l1和l2线段。最后分析算法的时间和空间复杂度。
import java.io.*;
假设要比较的数据存放在txt中，而且每行的存放格式为：11|1|8.
public class combine{
static String s[]=new String[3]; static double ss[][]=new double[3][3]; static String x[]=null; static double xx[][]=null; double temp=0;
public double compare(double ss[][]) {
if(!(ss[1][i]<ss[1][j]&&ss[2][i]<ss[2][j])||!(ss[1][j]<ss[1][i]&&
{
if(ss[2][i]<ss[2][j])
for(int i=0;i<3;i++) {
for(int j=i+1;j<3;j++)
ss[2][j]<ss[2][i]))
temp=Math.abs(ss[2][j]-Math.abs(ss[1][j]-ss[1][i])-Math.abs(ss[2]
else【百度直接笔试】
[j]-ss[2][i]));【百度直接笔试】
temp=Math.abs(ss[1][j]-Math.abs(ss[1][j]-ss[1][i])-Math.abs(ss[2][j]-ss[2][i]));
}
public static void main(String[] args) throws IOException{ File f=new File("d:\\0.txt"); FileReader fr=new FileReader(f);
BufferedReader br= new BufferedReader(fr); for(int j=0;j<3;j++) {
xx[i][j]=temp;
System.out.println(temp); System.out.println(i);
System.out.println(j); } }
return 0;
调用冒泡排序法，求出xx[i][j]中最大的，并输出i和j.
}
}
s[j]=br.readLine(); x=s[j].split("\\|",3);
ss[0][j]=Double.parseDouble(x[0]); ss[1][j]=Double.parseDouble(x[1]); ss[2][j]=Double.parseDouble(x[2]);
br.close(); fr.close();
combine c= new combine(); c.compare(ss); }
3、简答题
1）const的用法：char *const p，char const*p，和char const * const p有什么区别？ 答：const是一个c语言关键字，用于限定一个变量不允许被改变，也就是定义一个常量的作用。如const int a =5;
char *const p的意思是：定义一个常量p对应的指针，p不可变，*p可变。
char const*p的意思是：将指针p指向的数据定义为常量，即*p不可变，但p可变。 char const * const p的意思是：定义一个常量p对应的常指针，p不可变，*p也不可变。 2）现在有 int const a=10，请问有什么办法，能够改变a的内容。（C++）通过类似 int *p=&a 的方式，行吗？
3多任务管理系统，进程调用的原理；多个进程是如何并发执行的，用到了什么数据结构，用到了什么算法，能否用伪代码描述；
4堆、栈和队列的区别？
答：队列只能在队头做删除操作,在队尾做插入操作，先进先出，而栈只能在栈顶做插入和删除操作，属于后进先出；
堆是以逻辑上部分有序的树状数据结构形成的优先队列;栈是先进后出或后进先出队列； 1：从管理上来说：
栈：是系统管理的， 而堆是程序员通过new, delete来操作管理的。
2：结构上说：
栈：先进后出，从栈底向栈顶，也就使得push进后内存地址指针是减小的，pop后地址变大。堆没有这个特性。
3：存放内容：
栈：入口函数地址，local变量，函数参数等。堆一般放new的东西！
栈 和堆都是内存块，但栈 一般是先进后出，一般用来做临时变量的存储，系统自动维护，如函数中的局部变量。
堆是有序的内存块，一般需要程序员自己维护，如有malloc或new申请的内存会放在堆上。
4）多线程和多进程模式有什么区别？在用两种模型开发服务程序时，分别有什么优缺点？
采用长连接和短连接模式有什么区别？分别有什么优缺点？采用同步和异步模式有什么区别？分别有什么优缺点。 答：（1）启动进程的时候，操作系统会为进程分配资源，其中最主要的资源是内存空间，因为程序是在内存中运行的。在进程中，有些程序流程块是可以乱序执行的，并且这个代码块可以同时被多次执行。实际上，这样的代码块就是线程体。线程是进程中乱序执行的代码流程。当多个线程同时运行的时候，这样的执行模式成为并发执行。
对于一个进程中的多个线程来说，多个线程共享进程的内存块，当有新的线程产生的时候，操作系统不分配新的内存，而是让新线程共享原有的进程块的内存。因此，线程间的通信很容易，速度也很快。不同的进程因为处于不同的内存块，因此进程之间的通信相对困难。线程切换快，但实现稍复杂。进程易实现，较稳定，但性能与线程相比较差。
（2）所谓长连接，指在一个TCP连接上可以连续发送多个数据包，在TCP连接保持期间，如果没有数据包发送，需要双方发检测包以维持此连接，一般需要自己做在线维持。 短连接是指通信双方有数据交互时，就建立一个TCP连接，数据发送完成后，则断开此TCP连接，一般银行都使用短连接。
长连接多用于操作频繁，点对点的通讯，而且连接数不能太多情况，。每个TCP连接都需要三步握手，这需要时间，如果每个操作都是先连接，再操作的话那么处理速度会降低很多，所以每个操作完后都不断开，次处理时直接发送数据包就OK了，不用建立TCP连接。而像WEB网站的http服务一般都用短链接，因为长连接对于服务端来说会耗费一定的资源，而像WEB网站这么频繁的成千上万甚至上亿客户端的连接用短连接会更省一些资源，如果用长连接，而且同时有成千上万的用户，如果每个用户都占用一个连接的话，那可想而知吧。所以并发量大，但每个用户无需频繁操作情况下需用短连好。
（3）同步:调用方调用一个程序,等待返回,然后再继续下面的程序处理 异步: 调用方调用一个程序,不等待返回,继续执行下面的程序。
1)异步通信简单，双方时钟可允许一定误差。同步通信较复杂，双
本文来源：http://www.gbppp.com/sh/455393/
推荐访问:百度在线笔试 百度hr笔试