《数据结构与算法基础面试题解析》由会员分享，可在线阅读，更多相关《数据结构与算法基础面试题解析（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的 数列需要进行从小
2、到大排序，数列特征是基本逆序（多数数字从大到小，个别乱序），以下哪种排序算法在事先不了解数列特征 的情况下性能大概率最优（不考虑空间限制）_。A 冒泡排序 B 改进冒泡排序 C 选择排序 D 快速排序 E 堆排序 F 插入排序正确答案：E题目解析：个数约为50K，一般的冒泡，改进冒泡，选择，插入等基本的排序都不是理想的方法，加上数列的特征是基本逆序，而快速排序的worst case就是基本逆序或者基本有序的情况。综上所述，堆排序应该是大概率最优的。3 计算三个稠密矩阵A、B、C的乘积ABC，假定三个矩阵的尺寸分别为m*n, n*p, p*q，且m<n<p<q，以下计算顺序效率
3、最高的是： ？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
4、，很显然选项1的效率高于选项2。4 已知前序和中序求后续遍历结果A HGFEDCBA B EDCHBGFA C BGFHEDCA D EDCBGHFA E BEGHDFCA FBGHFEDCA正确答案：B题目解析：首先要明确一个基础的问题，前序遍历的顺序是：根、左、右；中序遍历的顺序是：左、根、右；后序遍历的顺序是：左、右、根。所以这里的前中后都是指的根的位置。分析过程如下：（1）前序顺序为根左右，根据前序知道：A为根节点，然后观察A在中序遍历中的结果得到：DEC为A的左子树的中序遍历结果，HFBG为A的右子数的中序遍历结果。（2）紧接着上面的分析，回到前序遍历来观察DEC（左子数的中序）对应
5、的前序为：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
6、步长为 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域中，而开始结点
7、无前趋，故应设头指针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题目解析：A,B,C选项受限于K如果只分布于某个区间，那么没法平均映射到整个N空间中，造成不均匀。10 下面排序算法中，初始数据集的排列顺序对算法的性能无影响的是：A 堆排序 B 插入排序 C 冒泡排
8、序 D 快速排序正确答案：A题目解析：插入排序：最优时间复杂度O(n)最差时间复杂度O(n2)平均时间复杂度O(n2)冒泡排序：最优时间复杂度O(n)最差时间复杂度O(n2)平均时间复杂度O(n2)快速排序：最优时间复杂度O(nlogn)最差时间复杂度O(n2)平均时间复杂度O(nlogn)堆排序：最优时间复杂度O(nlogn)最差时间复杂度O(nlogn)平均时间复杂度O(nlogn)11 一个栈的入栈序列式ABCDE则不可能的出栈序列是:A DECBA B DCEBA C ECDBA D ABCDE正确答案：C题目解析：栈是后进先出的数据结构，c选项不可能是C先于D先出。下面算法的时间复杂
9、度为：Int f(unsigned int n)If(n=0|n=1)Return 1;ElseReturn n*f(n-1);A O(1) B O(n) C O(N*N) D O(n!)正确答案：B题目解析：题目算得是n！，但是复杂度确实O（n）13 对于一个具有n个顶点的无向图，若采用邻接表数据结构表示，则存放表头节点的数组大小为：A n B n+1 C n-1 D n+边数正确答案：A题目解析：1714 对于顺序存储的线性数组，访问节点和增加节点删除节点的时间复杂度为：A O(n),O(n) B O(n),O(1) C O(1),O(n) D O(n),O(n)正确答案：C题目解析：对于
10、线性数据，查询复杂度为O(1)；新增修改删除操作为O(n)15 递归式的先序遍历一个n节点，深度为d的二叉树，则需要栈空间的大小为：A O(n) B O(d) C O(logn) D (nlogn)正确答案：B题目解析：先序遍历保存的数据长度最多为二叉树的深度，即为o(d)16 关于排序算法的以下说法，错误的是A 快速排序的平均时间复杂度O(nlogn),最坏O(N2) B 堆排序平均时间复杂度O(nlogn)，最坏O(nlogn) C 冒泡排序平均时间复杂度O(n2),最坏O(n2) D 归并排序的平均时间复杂度O(nlogn),最坏O(n2)正确答案：D题目解析：A 13 B 15 C 2
11、8 D 58正确答案：C题目解析：关键路径通常(但并非总是)是决定项目工期的进度活动序列。它是项目中最长的路径，即使很小浮动也可能直接影响整个项目的最早完成时间。关键路径的工期决定了整个项目的工期，任何关键路径上的终端元素的延迟在浮动时间为零或负数时将直接影响项目的预期完成时间（例如在关键路径上没有浮动时间）。2 但特殊情况下，如果总浮动时间大于零，则有可能不会影响项目整体进度。18 若一棵二叉树的前序遍历为a, e, b, d, c，后序遍历为b, c, d, e, a，则根节点的孩子节点为()A 只有e B 有e、b C 有e、c D 无法确定正确答案：A题目解析：根据前序和后续遍历没法反
12、推中序，这里可以通过画图方式枚举。19 若一颗二叉树的前序遍历为a,e,b,d,c,后序遍历为b,c,d,e,a，则根节点的孩子节点（）A 只有e B 有e，b C 有e，c D 不确定正确答案：A题目解析：前序遍历第一个是根节点，所以a是根节点假设a有两个孩子节点，则前序遍历a后面为e,所以e必定属于a的左子树中的节点后续遍历中a的前面挨着是e，所以e必定是a的右子树中的节点，相互矛盾。因此a只有一个孩子节点。在a只有一个孩子节点，也就是只有左子树或者只有右子树的情况下，前序遍历首先是根节点a,然后紧接着就是子树的跟节点，也就是a的唯一的孩子节点，所以e是a的子节点。2022下图是个二叉树的
13、图：入栈序列是：a1，a3，a5，a2，a4，a6出栈序列是：a5，a4，a2，a6，a3，a1，则栈的容量最小是多少()A 2 B 3 C 4 D 5正确答案：C题目解析：根据出栈顺序，a5先出，那么入栈的时候必须a1.a3.a5已经进入，然后a5出栈，然后a2，a4入栈，此时容量必须大于等于4，然后a4出栈，a2出栈，此时只有2个元素，a6入栈，容量要求为3.所以整个过程栈容量最小要是4.21 已知的一个无向图（边为正数）中顶点A,B的一条最短路P，如果把各个边的权重（即相邻两个顶点的距离）变为原来的2倍，那么在新图中，P仍然是A,B之间的最短路，以上说法是（）A 错误 B 正确正确答案：
14、B题目解析：如果将各条边的权值按从小到大排序的话，权值乘以2之后的排序不变，也就是权重的相对关系不变，p仍是最短路径。int foo(int n)if (n<=1) return 1;return n*foo(n-1);上面算法时间复杂度是()A 0(log2n) B 0(n) C 0(nlog2n) D 0(n2)正确答案：B题目解析：(1) 递归执行过程例子：求N!。这是一个简单的"累乘"问题，用递归算法也能解决。n! = n * (n - 1)! n > 10! = 1, 1! = 1 n = 0,1因此，递归算法如下：Java代码fact(int n) if(n = 0 | n = 1)return 1;elsereturn n * fact(n - 1);23以n=3为例，看运行过程如下：fact(3) - fact(2) - fact(1)
