算法与编程
1、说明生活中遇到的二叉树,用java 实现二叉树
我有很多个(假设10 万个)数据要保存起来,以后还需要从保存的这些数据中检索是否存在
某个数据,(我想说出二叉树的好处,该怎么说呢?那就是说别人的缺点),假如存在数组中,
那么,碰巧要找的数字位于99999 那个地方,那查找的速度将很慢,因为要从第1 个依次往
后取,取出来后进行比较。平衡二叉树(构建平衡二叉树需要先排序,我们这里就不作考虑
了)可以很好地解决这个问题,但二叉树的遍历(前序,中序,后序)效率要比数组低很多,
原理如下图:
代码如下:
package com.huawei.interview;
public class Node {
public int value;
public Node left;
public Node right;
public void store(int value)
{
if(value<this.value)
{
if(left == null)
{
left = new Node();
left.value=value;
}
else
{
left.store(value);
}
}
else if(value>this.value)
{
if(right == null)
{
right = new Node();
right.value=value;
}
else
{
right.store(value);
}
}
}
public boolean find(int value)
{
System.out.println("happen " + this.value);
if(value == this.value)
{
return true;
}
else if(value>this.value)
{
if(right == null) return false;
return right.find(value);
}else
{
if(left == null) return false;
return left.find(value);
}
}
public void preList()
{
System.out.print(this.value + ",");
if(left!=null) left.preList();
if(right!=null) right.preList();
}
public void middleList()
{
if(left!=null) left.preList();
System.out.print(this.value + ",");
if(right!=null) right.preList();
}
public void afterList()
{
if(left!=null) left.preList();
if(right!=null) right.preList();
System.out.print(this.value + ",");
}
public static void main(String [] args)
{
int [] data = new int[20];
for(int i=0;i<data.length;i++)
{
data[i] = (int)(Math.random()*100) + 1;
System.out.print(data[i] + ",");
}
System.out.println();
Node root = new Node();
root.value = data[0];
for(int i=1;i<data.length;i++)
{
root.store(data[i]);
}
root.find(data[19]);
root.preList();
System.out.println();
root.middleList();
System.out.println();
root.afterList();
}
}
1、从类似如下的文本文件中读取出所有的姓名,并打印出
重复的姓名和重复的次数,并按重复次数排序:
1,张三,28
2,李四,35
3,张三,28
4,王五,35
5,张三,28
6,李四,35
7,赵六,28
8,田七,35
程序代码如下(答题要博得用人单位的喜欢,包名用该公司,面试前就提前查好该公司
的网址,如果查不到,现场问也是可以的。还要加上实现思路的注释):
package com.huawei.interview;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.TreeSet;
public class GetNameTest {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
//InputStream ips =
GetNameTest.class.getResourceAsStream("/com/huawei/interview/info.txt
");
//用上一行注释的代码和下一行的代码都可以,因为info.txt与GetNameTest类在
同一包下面,所以,可以用下面的相对路径形式
Map results = new HashMap();
InputStream ips =
GetNameTest.class.getResourceAsStream("info.txt");
BufferedReader in = new BufferedReader(new
InputStreamReader(ips));
String line = null;
try {
while((line=in.readLine())!=null)
{
dealLine(line,results);
}
sortResults(results);
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
static class User
{
public String name;
public Integer value;
public User(String name,Integer value)
{
this.name = name;
this.value = value;
}
@Override
public boolean equals(Object obj) {
// TODO Auto-generated method stub
//下面的代码没有执行,说明往treeset中增加数据时,不会使用到equals方
法。
boolean result = super.equals(obj);
System.out.println(result);
return result;
}
}
private static void sortResults(Map results) {
// TODO Auto-generated method stub
TreeSet sortedResults = new TreeSet(
new Comparator(){
public int compare(Object o1, Object o2) {
// TODO Auto-generated method stub
User user1 = (User)o1;
User user2 = (User)o2;
/*如果compareTo返回结果0,则认为两个对象相等,新的对象不
会增加到集合中去
* 所以,不能直接用下面的代码,否则,那些个数相同的其他姓
名就打印不出来。
* */
//return user1.value-user2.value;
//return
user1.value<user2.value?-1:user1.value==user2.value?0:1;
if(user1.value<user2.value)
{
return -1;
}else if(user1.value>user2.value)
{
return 1;
}else
{
return user1.name.compareTo(user2.name);
}
}
}
);
Iterator iterator = results.keySet().iterator();
while(iterator.hasNext())
{
String name = (String)iterator.next();
Integer value = (Integer)results.get(name);
if(value > 1)
{
sortedResults.add(new User(name,value));
}
}
printResults(sortedResults);
}
private static void printResults(TreeSet sortedResults)
{
Iterator iterator = sortedResults.iterator();
while(iterator.hasNext())
{
User user = (User)iterator.next();
System.out.println(user.name + ":" + user.value);
}
}
public static void dealLine(String line,Map map)
{
if(!"".equals(line.trim()))
{
String [] results = line.split(",");
if(results.length == 3)
{
String name = results[1];
Integer value = (Integer)map.get(name);
if(value == null) value = 0;
map.put(name,value + 1);
}
}
}
}
第1题:
2、已知二叉树用二叉链表存储,则若实现二叉树实现左右子树交换,可以借助改写()遍历算法实现。
A.先序遍历
B.中序遍历
C.后序遍历
D.以上三种都可以
第2题:
关于二叉树的遍历说法不正确的是()
A.二叉树的遍历算法不能应用到哈夫曼树(最优二叉树)
B.任意二叉树都可以应用先根遍历算法
C.后根遍历算法得到的节点序列中,根节点一定在最后
D.根据中根遍历序列和后根遍历序列,可以画出二叉树
第3题:
1、二叉树的按层次遍历算法可以采用递归算法实现。
第4题:
二叉树的按层次遍历算法可以采用递归算法实现。
第5题:
栈结构不适用于下列应用中的( )。
A.表达式求值
B.树的层次次序周游算法的实现
C.二叉树对称序周游算法的实现
D.快速排序算法的实现
第6题:
栈结构不适用于下列应用中的( )。
A.表达式求值
B.树的层次次序周游算法的实现
C.二叉树对称周游算法的实现
D.快速排序算法的实现
第7题:
实现任意二叉树的后序遍历的非递归算法用栈结构,最佳方案是二叉树采用______存储结构。
A.二叉链表
B.顺序存储结构
C.三又链表
D.广义表存储结构
第8题:
栈结构不适用于下列( )应用?
A)表达式求值
B)快速排序算法的实现
C)树的层次次序周游算法的实现
D)二叉树对称序周游算法的实现
第9题:
( 9 )栈结构不适用与下列哪一种应用?
A) 表达式求值
B) 树的层次次序周游算法的实现
C) 二叉树对称序周游算法的实现
D) 快速排序算法的实现