经典数据结构面试题（含答案）

{

if(a[0]==0 || a==NULL) return; int insert=1,current=1; while(a[current]!=0) {

if(a[current]!=a[current-1]) {

a[insert]=a[current]; insert++; current++; } else

current++; }

a[insert]=0; }

9,如何判断一棵二叉树是否是平衡二叉树 问题：判断一个二叉排序树是否是平衡二叉树 解决方案：

根据平衡二叉树的定义，如果任意节点的左右子树的深度相差不超过1，那这棵树就是平衡二叉树。

首先编写一个计算二叉树深度的函数，利用递归实现。 template

static int Depth(BSTreeNode* pbs) {

if (pbs==NULL) return 0; else {

int ld = Depth(pbs->left); int rd = Depth(pbs->right); return 1 + (ld >rd ? ld : rd); } }

下面是利用递归判断左右子树的深度是否相差1来判断是否是平衡二叉树的函数： template

static bool isBalance(BSTreeNode* pbs) {

if (pbs==NULL)

return true;

int dis = Depth(pbs->left) - Depth(pbs->right); if (dis>1 || dis<-1 )

return false;

else

return isBalance(pbs->left) && isBalance(pbs->right); 4.abstract class Something {

private abstract String doSomething (); }

该段代码有错吗？

答案: 错。abstract的methods不能以private修饰。abstract的methods就是让子类implement(实现)具体细节的，怎么可以用private把abstract method封锁起来呢? (同理，abstract method前不能加final)。

5.看看下面的代码段错在哪里？

public class Something { void doSomething () { private String s = \ int l = s.length(); } }

答案: 错。局部变量前不能放置任何访问修饰符 (private，public，和protected)。final可以用来修饰局部变量

(final如同abstract和strictfp，都是非访问修饰符，strictfp只能修饰class和method而非variable)。

6. 下面该段代码是否有错，若是有错错在哪里？ abstract class Name { private String name;

public abstract boolean isStupidName(String name) {} }

答案: 错。abstract method必须以分号结尾，且不带花括号。