(全)面试题2023数据结构和算法10道题(附解题思路).docx

上传人:王** 文档编号:389288 上传时间:2023-07-26 格式:DOCX 页数:7 大小:20.94KB
下载 相关 举报
(全)面试题2023数据结构和算法10道题(附解题思路).docx_第1页
第1页 / 共7页
(全)面试题2023数据结构和算法10道题(附解题思路).docx_第2页
第2页 / 共7页
(全)面试题2023数据结构和算法10道题(附解题思路).docx_第3页
第3页 / 共7页
(全)面试题2023数据结构和算法10道题(附解题思路).docx_第4页
第4页 / 共7页
(全)面试题2023数据结构和算法10道题(附解题思路).docx_第5页
第5页 / 共7页
(全)面试题2023数据结构和算法10道题(附解题思路).docx_第6页
第6页 / 共7页
(全)面试题2023数据结构和算法10道题(附解题思路).docx_第7页
第7页 / 共7页
亲,该文档总共7页,全部预览完了,如果喜欢就下载吧!
资源描述

《(全)面试题2023数据结构和算法10道题(附解题思路).docx》由会员分享,可在线阅读,更多相关《(全)面试题2023数据结构和算法10道题(附解题思路).docx(7页珍藏版)》请在优知文库上搜索。

1、数据结构和算法10道题(附解题思路)题目1变量X、y的值互换题:在不借助第三个变量的情况下,把两个int的变量X、Y的值互换,用任何自己熟悉的编程语言完成参考答案:思路如下X=x+Y;Y=x-Y;X=X-Y;具体编程语言完成情况由面试官检查。考察点:基本算法、语言基础。题目2:文件查找优化问题:文件查找优化背景:百度每天都有大量搜索,如果有一个大文本文件(保存各种词语),每次搜索都必须要检查查询词是否在这个大文件中,请问有什么方式能够提高查找效率要求:先讲解所使用的算法,然后用自己最熟悉的编程语言,在3分钟内予以实现参考答案:基本方法:采用hash签名,提高匹配效率;建立多叉树保存文件数据,提

2、高查找速度。如有列举出更多签名算法或更好数据结构形式,可加分较优方法:在上面基础上,将文本文件转化为key-value的二进制文件,提高文件操作和查找速度更优方法:在上面基础上,开辟内存做cache,保存高频率查询词,提高整体查找效率。如能完整给出cache的更新机制,加分;考察点:基本数据结构;灵活采取算法处理实际问题的能力;快速编程能力;在给出一定提示情况下,检查学习能力和知识应用能力。题目3:栈的结构题目描述:函数VOidlog(intfchar,long)调用时栈的结构是什么样的?考察点:参数压栈的顺序,字节对齐等答案:从右到左的压栈顺序,注意高地址和低地址,压栈时以机器字为单位且所有

3、参数字对齐。请见下图的说明。题目4:成绩单最优数据存储题目:有一份成绩单,只有两个字段:姓名.成绩;数据量在百万级别。要求用最优的数据存储方式,能通过姓名快速查找出成绩。(5分钟)参考答案:存储方式采用对姓名做hasho考察点:数据结构题目5:找出单向链表的中间节点问题:找出单向链表的中间节点参考答案:link*mid(link*head)(link*plp2;pl=p2=head;if(head=NULLhead-next=NULL)returnhead;dopl=pl-next;p2=p2-next-next;while(p2&p2-next);returnpl;)考察点:算法基础链表题目

4、6:快速排序的时间复杂度问题:快速排序的平均时间复杂度是多少?最坏时间复杂度是多少?在哪些情况下会遇到最坏的时间复杂度。(4分钟)参考答案:快速排序时间复杂度为O(Mogn),最坏时间复杂度是0(n平方),在待排序列正序或者逆序的情况下会出现最坏时间复杂度考察点:此题主要考察:对数据结构的掌握题目7(本题答案不全):找到至少出现两次的整数问题:给定43亿个32位整数的顺序文件,请问如何可以找到一个至少出现两次的整数?考察:算法相关(IOmin)参考答案:用二分查找发。细节点:43亿大于int的最大值,说明肯定有重复的数字题目8:如何判断一个单链表是有环的如何判断一个单链表是有环的(不能用标志位

5、,最多只能用两个额外指针)(6分钟)考察点:算法及数据结构参考答案:可以只给出算法思路,一种O(n)的办法就是(两个指针,一个每次递增一步,一个每次递增两步,如果有环的话两者必然重合,反之亦然)structnodecharval;node*next;boolcheck(constnode*head)/returnfalse:无环;true:有环boolcheck(constnode*head)(if(head=NULL)returnfalse;node*low=headz*fast=head-next;while(fast!=NULL&fast-next!=NULL)low=low-next;

6、fast=fast-next-next;if(low=fast)returntrue;)returnfalse;)题目9:把一维数据某一位置的数值改成-1题目:有一个一维数组inta100r里面存储的是1到100的这100个数,不过是乱序存储;这时把其中某一位置的数值改成-1;请用最优的空间复杂性和时间复杂性求出该位置和值(6分钟)参考答案:遍历一遍数组得到-1的位置并记录,同时把非-1的值相加得到sum被改变的值为:50*(100-1)-sum时间复杂性0(n),空间复杂性0(1)考察点:程序设计、逻辑思维能力问题:求两个相同大小已排序数组的中位数:设aO.ml和bO.n-l是两个已经排好序的数组,设计一个算法,找出a和b的2n个数的中位数。要求给出算法复杂度并C语言实现。参考答案:较优的是O(Ign)的,折半。考察点:算法基础+基础C编程能力。

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 资格/认证考试 > 公务员考试

copyright@ 2008-2023 yzwku网站版权所有

经营许可证编号:宁ICP备2022001189号-2

本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知装配图网,我们立即给予删除!