51cto算法与数据结构面试题_THE_XX

http://blog.sina.com.cn/u/3549514553

首页博文目录关于我

个人资料

微博

加好友发纸条

写留言加关注

博客等级：
博客积分：

博客访问：
关注人气：
获赠金笔：0支
赠出金笔：0支
荣誉徽章：

正文字体大小：大中小

51cto算法与数据结构面试题

(2015-10-26 15:11:27)

标签：

值得收藏

51cto算法与数据结构

面试题

一、单选题（共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之间的最短路.

正确

错误

阅读┊ 收藏 ┊ 喜欢 ▼ ┊打印┊举报/Report

前一篇：《圣经》里最经典的309句话【中英对照】---- 不管你信不信仰，你都能有所收获

新浪BLOG意见反馈留言板　欢迎批评指正