还剩4页未读,继续阅读
文本内容:
数据结构和算法道题(附解题思10路)、题目变量X的值互换题在不借助第三个变量的情况下,把两个的变1y int量、的值互换,用任何自己熟悉的编程语言完成X Y参考答案思路如下具体编程语言完成情况由面试官检X=X+Y;Y=X-Y;X=X-Y;考察点基本算法、语言基础查题目:文件查找优化2问题文件查找优化背景:百度每天都有大量搜索,如果有一个大文本文伟保存各种词语),每次搜索都必须要检蛰查询词是否在这个大文件中,请问有什么方式能够提高杳找效率要求先讲解所使用的算法,然后用自己最熟悉的编程语言,在分钟内予以实现3参考答案基本方法采用签名,提高匹配效率;建立多叉树保存文件数据,hash提高查找速度如有列举出更多签名算法或更好数据结构形式,可加分较优方法在上面基础上,将文本文件转化为的二进制文key-value件,提高文件操作和查找速度更优方法在上面基础上,开辟内存做,保存高频率查询词,提高整体查cache找效率如能完整给出的更新机制,加分;cache考察点基本数据结构;灵活采取算法处理实际问题的能力;快速编程能力;在给出一定提示情况下,检查学习能力和知识应用能力题目:栈的结构3描述函数调用时栈的结构是什么样void logintchar,longf的?考察点参数压栈的顺序,字节对齐等答案从右到左的压栈顺序,注意高地址和低地址,压栈时以机器字为单位且所有参数字对齐请见下图的说明题目:成绩单最优数据存储4:有一份成绩单,只有两个字段姓名、成绩;数据量在百万级别要求用最优的数据存储方式,能通过姓名快速直找出成绩分钟参考答案:存5储方式采用对姓名做hash考察点数据结构题目:找出单向链表的中间节点5问题找出单向链表的中间节点参考答案:link*midlink*head link*pL*p2;二pl p2=head;ifhead==NULL||head-next==NULL returnhead;do{pl=pl-next;p2=p2-next-next;}whilep2p2-next;return pl;考察点算法基础——链表题目:快速排序的时间复杂度6问题快速排序的平均时间复杂度是多少?最坏时间复杂度是多少?在哪些情况下会遇到最坏的时间复杂度分钟4参考答案快速排序时间复杂度为最坏时间复杂度是平方,在待排Onlogn,0n序列正序或者逆序的情况下会出现最坏时间复杂度考察点此题主要考察对数据结构的掌握题目本题答案不全:找到至少出现两次的整数7问题给定亿个位整数的顺序文件,请问如何可以找到一个至4332少出现两次的整数?考察:算法相关lOmin参考答案用二分查找发细节点亿大于的最大值,说明肯定有重复的数字43int题目:如何判断一个单链表是有环的8如何判断一个单链表是有环的不能用标志位,最多只能用两个额外指针分钟6考察点算法及数据结构参考答案可以只给出算法思路,一种的办法就是两个指针,一个每次递增一步,一个每次递增两步,如果0n有环的话两者必然重合,反之亦然struct node{char val;node*next;}无环;有环bool checkconstnode*head{}//return false:true:bool checkconstnode*headifhead==NULL return false;node*low=head,*fast=head-next;whilefast!=NULLfast-next!=NULL low=low-next;fa st=fa st-next-next;
(二二)if lowfast returntrue;)returnfalse;题目:把一维数据某一位置的数值改成9-1有一个一维数组里面存储的是到的这int a
[100]1100100f个数,不过是乱序存储;这时把其中某一位置的数值改成;请用最优-1的空间复杂性和时间复杂性求出该位置和值分钟参考答案遍历一遍数组得6到的位置并记录,同时把非的值相加得到被改变的值为-1-1sum50*100-1-sum时间复杂性,空间复杂性On01考察点程序设计、逻辑思维能力问题求两个相同大小已排序数组的中位数设和是两个已a[O..n-l]b[O..n-l]经排好序的数组,设计一个算法,找出和的个数的中位数要求给出算a b2n法复杂度并语言实现C参考答案较优的是的,折半Olgn考察点算法基础+基础编程能力C。