51cto算法与数据结构面试题
2015-10-26 15:11阅读：
一、单选题 （共24道题，每题2分）
1.假设某算法的时间复杂度符合递推关系式T(n)=2T(n/2)+n，那么该算法的时间
复杂度相当于（）
A.O(n)
B.O(lgn)
C.O(nlgn)
D.O(n2)
2.个数约为50K的数列需要进行从小到大排序，数列特征是基本逆序（多数数字从大到小，个别乱序），以下哪种排序算法在事先不了解数列特征的情况下性能大概率最优（不考虑空间限制）()。
A.冒泡排序
B.堆排序
C.插入排序
D.快速排序
3.计算三个稠密矩阵A、B、C的乘积ABC，假定三个矩阵的尺寸分别为m*nn*p
p*q，且m
A.(AB)C
B.A(BC)
C.(AC)B
D.以上效率相同
4.在一个单链表中，q的前一个节点为p，删除q所指向节点，则执行()
A.p->next=q->next;deleteq;
B.q->next=p->next;deleteq
C.p-next=q->next;deletep;
D.q->next=p->nerx;deletep;
5.有字符序列｛QHCYPAMSRDFX｝新序列{FHCDP.A.MQRSYX}，是下列()排序算法一趟扫描的结果.
A.二路归并排序
B.快速排序
C.步长为4的希尔排序
D.冒泡排序
6.在一个双向循环链表中，指针p所指向的节点（非尾节点）之后插入指针s所指向的节点，其修改指针的操作是（）.
A.p->next=s;s->prev=p;p->next->prev=s;s->next=p->next;
B.p->next->prev=s;p->next=s;s->prev=p;s->next=p->next;
C.s->next=p-
>next;s->prev=p;p->next=s;p->next->prev=s;
D.s->prev=p;s->next=p->next;p->next->prev=s;p->next=s;
7.带头节点的单链表head为空的判断条件是（）
A.head->next==null;
B.head->next==head;
C.*head==null;
D.*(head->next)==null;
8.假设把整数关键码K散列到N个槽列表，以下哪些散列函数是好的散列函数()
A.h(K)=K/N;
B.h(K)=1;
C.h(K)=KmodN;
D.h(K)=(K+rand(N))modNrand(N)返回0到N-1的整数
9.下面排序算法中，初始数据集的排列顺序对算法的性能无影响的是().
A.堆排序
B.插入排序
C.冒泡排序
D.快速排序
10.一个栈的入栈序列式ABCDE则不可能的出栈序列是()
A.DECBA
B.DCEBA
C.ECDBA
D.ABCDE
11.下面算法的时间复杂度为：Intf(unsignedintn){If(n==0n==1)Return1;ElseReturnn*f(n-1);}
A.O(1)
B.O(n)
C.O(N*N)
D.O(n!)
12.对于一个具有n个顶点的无向图，若采用邻接表数据结构表示，则存放表头节点的数组大小为().
A.n
B.n+1
C.n-1
D.n+边数
13.递归式的先序遍历一个n节点，深度为d的二叉树，则需要栈空间的大小为（）
A.O(n)
B.O(d)
C.O(logn)
D.(nlogn)
14.关于排序算法的以下说法，错误的是().
A.快速排序的平均时间复杂度O(nlogn)最坏O(N^2)
B.堆排序平均时间复杂度O(nlogn)，最坏O(nlogn)
C.冒泡排序平均时间复杂度O(n^2)最坏O(n^2)
D.归并排序的平均时间复杂度O(nlogn)最坏O(n^2)
15.若一棵二叉树的前序遍历为aebdc，后序遍历为bcdea，则根节点的孩
子节点为()。
A.只有e
B.有e、b
C.有e、c
D.无法确定
16.若一颗二叉树的前序遍历为aebdc后序遍历为bcdea，则根节点的孩
子节点（）.
A.只有e
B.有e，b
C.有e，c
D.不确定
17.入栈序列是：a1，a3，a5，a2，a4，a6出栈序列是：a5，a4，a2，a6，a3，a1，则栈的容量最小是多少().
A.2
B.3
C.4
D.5
18.intfoo(intn)
{
if(n<=1)return1;
returnn*foo(n-1);
}
上面算法时间复杂度是()
A.0(log2n)
B.0(n)
C.0(nlog2n)
D.0(n2)
19.如下程序的时间复杂度为（其中m>1e>0）（）
x=m;
y=1;
while（x-y>e）
{
x=(x+y)/2;
y=m/x;
}
print(x);
A.logm
B.m的平方
C.m的1/2方
D.m的1/3方
20.关于主对角线（从左上角到右下角）对称的矩阵为对称矩阵；如果一个矩阵中的各个元素取值为0或1，那么该矩阵为01矩阵，求大小为N*N的01对称矩阵的个数？（）
A.power(2，n)
B.power(2，n*n/2)
C.power(2，(n*n+n)/2)
D.power(2，(n*n-n)/2)
21.现有一个包含m个节点的三叉树，即每个节点都有三个指向孩子结点的指针，请问:在这3m个指针中有()个空指针。
A.2m
B.2m-1
C.2m+1
D.3m
22.以下操作中，数组比线性表速度更快的是().
A.原地逆序
B.返回中间节点
C.返回头部节点
D.选择随机节点
23.以下哪种排序算法需要开辟额外的空间().
A.选择排序
B.归并排序
C.快速排序
D.堆排序
24.下面属于构造散列函数的方法是（）。
A.直接定址法
B.数字分析法
C.乘余取整法
D.平方取中法
二、判断题 （共1道题，每题1分）
1.已知的一个无向图（边为正数）中顶点AB的一条最短路P，如果把各个边的权重（即相邻两个顶点的距离）变为原来的2倍，那么在新图中，P仍然是AB之间的最短路.
正确
错误
