数据结构与算法基础面试题解析
32页1、数据结构与算法1 假设某算法的时间复杂度符合递推关系式T(n)=2T(n/2)+n,那么该算法的时间复杂度相当于A O(n) B O(lgn) C O(nlgn) D O(n2)正确答案:C题目解析:解析:由时间代价严格推出时间复杂度比较复杂,对于这种题,可用特例验证,不过需要注意的是特例不能取太少,至少n取到5,这样规律基本就可以确定了。T(1)=1T(2)=2T(1)+2=4T(3)=2T(1)+3=5T(4)=2T(2)+4=12T(5)=2T(2)+5=13很容易排除D选项,其递增速率介于O(n)和O(n2)之间,实际上可以参考归并排序的递推公式。2 个数约为50K的 数列需要进行从小到大排序,数列特征是基本逆序(多数数字从大到小,个别乱序),以下哪种排序算法在事先不了解数列特征 的情况下性能大概率最优(不考虑空间限制)_。A 冒泡排序 B 改进冒泡排序 C 选择排序 D 快速排序 E 堆排序 F 插入排序正确答案:E题目解析:个数约为50K,一般的冒泡,改进冒泡,选择,插入等基本的排序都不是理想的方法,加上数列的特征是基本逆序,而快速排序的worst case就是基本逆序或者
2、基本有序的情况。综上所述,堆排序应该是大概率最优的。3 计算三个稠密矩阵A、B、C的乘积ABC,假定三个矩阵的尺寸分别为m*n, n*p, p*q,且m<n<p<q,以下计算顺序效率最高的是: ?A (AB)C B A(BC) C (AC)B D (BC)A E (CA)B F 以上效率相同正确答案:A题目解析: 根据简单的矩阵知识,可以排除后面四项,因为A*B,A的列数必须和B的行数相等。 再看选项1和选项2,如下图所示,一个m*n的矩阵A乘以n*q的矩阵B。我们会用矩阵A的第一行,乘以矩阵B的第一列并相加。这一运算需要耗费n次乘法以及n-1次加法,矩阵B有q列,矩阵A有m行,所以A*B的复杂度为m*(2n-1)*q。 根据上面的分析,我们可以知道选项1的复杂度为m*(2n-1)*p + m*(2p-1)*q,而选项2的复杂度为m*(2n-1)*q+n*(2p-1)*q,很显然选项1的效率高于选项2。4 已知前序和中序求后续遍历结果A HGFEDCBA B EDCHBGFA C BGFHEDCA D EDCBGHFA E BEGHDFCA FBGHFEDCA正确答案
3、:B题目解析:首先要明确一个基础的问题,前序遍历的顺序是:根、左、右;中序遍历的顺序是:左、根、右;后序遍历的顺序是:左、右、根。所以这里的前中后都是指的根的位置。分析过程如下:(1)前序顺序为根左右,根据前序知道:A为根节点,然后观察A在中序遍历中的结果得到:DEC为A的左子树的中序遍历结果,HFBG为A的右子数的中序遍历结果。(2)紧接着上面的分析,回到前序遍历来观察DEC(左子数的中序)对应的前序为:CDE,所以左子数的根节点为C,同样的道理,回到中序结果HFBG,知道H为左子树,BG为F右字数。依照这种规律分析下去,可以完整的分析出这棵树的结构,然后就可以得到后序结果了。5 在一个单链表中,q 的前一个节点为 p,删除 q 所指向节点,则执行next;delete q正确答案:D题目解析:单链表删除某个节点,需要修改前一个节点引用的后一个节点改为被删除节点的下一个节点6 有字符序列 Q,H,C,Y,P,A,M,S,R,D,F,X ,新序列F,H,C,D,P.A.M,Q,R,S,Y,X,是下列 排序算法一趟扫描的结果A 二路归并排序 B 快速排序 C 步长为 4 的希尔排序 D
4、步长为 2 的希尔排序 E 冒泡排序 F 堆排序正确答案:B题目解析:很显然是拿Q作为pivot的一趟扫描的结果。我们看看其他选项,比如C,如果是步长为4的希尔排序,那么Q将和P相比,P要排在Q前面,和新序列不符。其它依次类推,考试的时候,选B就可以啦。肯定是对的。7 在一个双向循环链表中,指针p所指向的节点(非尾节点)之后插入指针s所指向的节点,其修改指针的操作是()prev=s;正确答案:D题目解析:8 带头节点的单链表head为空的判断条件是next)=null;正确答案:B题目解析:头指针head和终端结点指针域的表示单链表中每个结点的存储地址是存放在其前趋结点next域中,而开始结点无前趋,故应设头指针head指向开始结点。注意:链表由头指针唯一确定,单链表可以用头指针的名字来命名。终端结点无后继,故终端结点的指针域为空,即NULL。129 假设把整数关键码K散列到N个槽列表,以下哪些散列函数是好的散列函数A h(K)=K/N; B h(K)=1; C h(K)=K mod N; D h(K)=(K+rand(N) mod N, rand(N)返回0到N-1的整数正确答案:D
《数据结构与算法基础面试题解析》由会员一***分享,可在线阅读,更多相关《数据结构与算法基础面试题解析》请在金锄头文库上搜索。
2021年三年级语文下册期末测试题及答案
2021年一年级数学下册期末测试题和答案
2021年六年级语文下册期末测试题及答案
基于Web的银行客户关系管理系统的分析与设计
基于Web的单位工资管理系统的设计与实现
基于SSH架构的档案管理系统的设计与实现
学生成绩管理系统毕设论文正文
基于ssh框架的员工管理系统
基于SSH框架的学生信息管理系统的设计与实现
基于SSH的图书借阅管理系统的研究与设计
基于SSH框架的大学后勤保障系统的设计与实现
基于SSH的银行VIP客户关系管理系统的分析与设计
基于SSH的小区物业管理系统设计与实现
基于ssh框架的企业人力资源管理信息系统设计与实现
基于SSH框架的教务管理系统设计与实现
基于SSM的高校排课系统的研究与应用论文
基于SSM框架的B2C网上商城系统的设计与实现
基于SSH框架的学生信息管理系统的研究与实现
基于SSH的网上订餐系统的设计与实现
基于ssh框架的在线考试系统设计与实现
2023-09-25 37页
2023-09-25 10页
2023-09-25 33页
2023-09-25 26页
2023-04-03 8页
2023-04-03 4页
2023-04-03 8页
2023-03-29 10页
2023-03-22 10页
2023-03-20 8页