数据结构相关问题及答案.docx

数组和链表的区别

数组：数据顺序存储，固定大小

链表：数据可以随机存储，大小可动态改变

队列和栈有什么区别？

答：队列先进先出，栈后进先出

什么是平衡二叉树？

答：左右子树都是平衡二叉树且左右子树的深度差值的绝对值不大于1。

以下是两个n阶方阵的乘积C=A*B，求出该算法的时间复杂度。#defineMAX10

voidmatmult(intn,floatA[MAX][MAX],floatB[MAX][MAX],floatC[MAX][MAX]){inti,j,k;

floatx;

for(i=1;i=n;i++)

//(1)

for(j=1;j=n;j++)

{

x=0;

//(2)

//(3)

}

}

解答：

for(k=1;k=n;k++) //(4)x+=A[i][k]*B[k][j]; //(5)

C[i][j]=x; //(6)

在该算法中，语句（1）的循环控制变量i要增加到n+1,故它的频度是n+1,但是它的循环体却只能执行n次。语句（2）作为语句（1）的循环体内的语句应执行n次，但语句（2）本身要执行n+1次，所以语句（2）的频度是n(n+1)。

同理得到语句（3）（4）（5）（6）的频度分别是n^2、n^2*(n+1)、n^3、n^2。则本算法的时间复杂度T(n)=n+1+n(n+1)+n^2+n^2*(n+1)+n^3+n^2=2n^3+3n^2+2n+1=O(2*n^3)

5、通常情况下我们所说的时间复杂度指的是什么情况下的复杂度（平均情况？最好情况？还是最坏情况）？

最坏情况

冒泡排序算法的时间复杂度是什么？分别在什么情况下，冒泡排序的效率最高和最低？时间复杂度是O(n^2)。

对待排序序列已按照要求排好序时效率最高。

通常在待排序元素数量比较大时，在8种排序算法中可以选择哪几种？

快速、归并、堆、基数

如果待排序元素是double型的，在8种排序方法中不能使用哪种方法？基数排序

下面的程序是用来删除单链表的首元素的函数，请找出其中的问题并加以纠正。【中国某著名综合软件公司2005年面试题】

voidRemoveHead(structnode*head)

{

free(head);

head=head-next;

}

答：

voidRemoveHead(structnode*head)

{

structnode*p;p=head-next;

head-next=p-next;free(p);

}

如果一棵二叉树节点的前序序列是A、B、C，后序序列是C、B、A，则该二叉树的中序序列是什么？【中国某著名计算机金融软件公司2005年面试题】

答案不唯一，可能是B、C、A，也可能是C、B、A。由前序和后序序列是无法唯一确定一个中序序列的。

A A A A

B 或 B 或 B 或 BC C C C

补充：已知

先序：ABCDEFGH

中序：DCBEAGHF，求后序(答案：DCEBHGFA)。