【笔试面试】四道有点难笔试题（数据结构）

这四道题来自一个公司的笔试题，我一道也打不上于是拍照后走人。回来之后仔细百度了一下，研究完答案之后，我真是不知道为什么出这种题，这题考的是java数据结构，比如二叉树。但姑且放在这里也算供大家学习了。

 

答案都是总结百度结果自己写的答案，欢迎喷。

 

1：给定一个正整数序列比如int[] data={6,42,34,12,35,75,323},请构造一个树的数据结构，将这些整数依次插入到树中，插入时大的数放右边，小的数放左边最后请将排序后的整数序列输出，比如输出3  5  6  12  34  42  75  323  

 注：二叉排序树（Binary Sort Tree）又称二叉查找树，它或者是一棵空树，或者是具有下列性质的二叉树，

（1）若左子树不为空，则左子树上所有节点的值均小于它的根节点的值。

（2）若右子树不为空，则右子树上所有节点的值均大于它的根节点的值。

（3）左右子树也分别为二叉排序树。

 

2：从一批数据（比如10万个随机数）中取出最大的100个数据。

 

3：已知带头节点的动态链表中的节点是按照整数增值排列的，请自定义写一个数据结构实现链表，不要使用java.util.List等实现，写个函数将值为x的节点插入到该链表中，使链表仍有序，同时返回该数值x在该链表中是否存在，已经存在返回true，否则返回false

 

4：实现一个栈  其中的元素的值是int数据，满足min() pop() push()方法的时间复杂度都为0(1).(min()返回栈中最小元素)栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶（top）,另一端为栈底(bottom);栈低固定，而栈顶浮动；栈中元素个数为零时称为空栈，插入一般称为进栈（push），删除则称为退栈（pop），栈也称为后进先出表。

时间复杂度，简单来说就是关键代码重复执行的次数

 

 

1：首先第一题，我想排序就是冒泡排序呗，结果不是，实际上人家让实现的是二叉树，然后递归升序输出二叉树。

其中对初级程序员比较难的应该是递归吧，

public class BinarySortTree {
	public static Tree tree;

	public static void main(String[] args) {
		int[] data = { 6, 42, 34, 12, 3 , 5, 75, 323 };
		tree = new Tree();
		tree.value = data[0];
		for (int i = 1; i < data.length; i++) {
			tree.makeTree(data[i]);
		}
		perPrintTree(tree);
	}

	// 升序输出
	public static void perPrintTree(Tree tree) {
		if (tree.left != null)
			perPrintTree(tree.left);
		System.out.print(tree.value + "  ");
		if (tree.right != null)
			perPrintTree(tree.right);
	}
}

class Tree {
	public int value;
	public Tree left;
	public Tree right;

	// 构造
	public void makeTree(int value) {
		if (value < this.value) {
			if (this.left == null) {
				this.left = new Tree();
				this.left.value = value;
			} else {
				this.left.makeTree(value);
			}
		} else if (value > this.value) {
			if (this.right == null) {
				this.right = new Tree();
				this.right.value = value;
			} else {
				this.right.makeTree(value);
			}
		}

	}
}

 

2：网上找了一段代码自己测一下，效率不低。我找不到其他的例子所以姑且用这个。

仔细看了一下，怎么觉得逻辑没有什么，就是一个LinkedList按大小往里放，超过100个就removeLast，因为这里频繁的插入操作，所以LinkedList效率比较高嘛，目测细节尚有提升空间

 

import java.util.LinkedList;
import java.util.Random;

public class MaxFinderTest {
	public static void main(String[] args) {
		long time01 = System.currentTimeMillis();
		MaxFinder maxFinder = new MaxFinder(100);
		Random random = new Random();
		System.out.println("ADDING...");
		for (int i = 0; i < 100000; i++) {
			maxFinder.addNum(random.nextInt());
		}
		int[] array = maxFinder.getArray();
		for (int i = 0; i < array.length; i++) {
			System.out.println((i + 1) + " : " + array[i]);
		}
		long time02 = System.currentTimeMillis();
		System.out.println("这段代码运行了:" + (time02 - time01) + "毫秒!");
	}
}

class MaxFinder {
	private int count;
	public LinkedList<Integer> list;

	public MaxFinder(int count) {
		this.count = count;
		this.list = new LinkedList<Integer>();
	}

	public void addNum(int num) {
		int addIndex = findAddIndex(num);
		list.add(addIndex, num);
		if (list.size() > count)
			list.removeLast();
	}

	private int findAddIndex(int num) {
		for (int i = 0; i < list.size(); i++) {
			if (num >= list.get(i))
				return i;
		}
		return list.size();
	}

	public int[] getArray() {
		int[] array = new int[list.size()];
		for (int i = 0; i < array.length; i++) {
			array[i] = list.get(i);
		}
		return array;
	}

}

 

 3：特么专科非计算机专业伤不起呀，不懂数据结构啊！！什么叫动态链表什么叫头结点啊。。。。

 头结点：在单链表的第一个结点之前附设一个结点，称之为头结点。头结点的数据域可以不存储任何信息，头结点的指针域存储指向第一个结点的指针（即第一个元素结点的存储位置）。头结点的作用是使所有链表（包括空表）的头指针非空，并使对单链表的插入、删除操作不需要区分是否为空表或是否在第一个位置进行，从而与其他位置的插入、删除操作一致。

动态链表：这种链表在初始时必须分配足够的空间, 也就是空间大小是静态的, 在进行插入和删除时则不需要移动元素, 修改指针域即可,所以仍然具有链表的主要优点，链表结构可以是动态地分配存储的，即在需要时才开辟结点的存储空间，实现动态链接。

貌似都看懂了，头结点就是链表第一位放一个结点，不放数据，动态链表类似数据库连接池，先放一些链接在那。

 

这个代码没百度到，是自己写的，估计和标准答案有一定差距，欢迎喷。。。。

 

public class LinkTest {
	public static void main(String args[]) {
		Link l = new Link();
		l.addnode("1");
		l.addnode("2");
		l.addnode("3");
		l.addnode("4");
		l.addnode("5");
		l.printnode();
		l.deletenode("2");
		l.deletenode("3");
		System.out.println("");
		l.printnode();
		System.out.println("");
		System.out.println("查询节点:" + l.contains("4"));
	}
}

class Link {
	class Node {
		private String data;
		private Node next;

		// 设置节点信息
		public Node(String data) {
			this.data = data;
		}

		// 增加一个add操作
		public void add(Node newnode) {
			if (this.next == null)
				this.next = newnode;
			else
				this.next.add(newnode);
		}

		// 打印节点信息
		public void print() {
			System.out.print(this.data + " ");
			if (this.next != null)
				this.next.print();
		}

		public boolean search(String data) {
			if (data.equals(this.data))
				return true;
			else if (this.next != null)
				return this.next.search(data);
			else
				return false;
		}

		public void delete(Node previous, String data) {
			if (data.equals(this.data))
				previous.next = this.next;
			else if (this.next != null)
				this.next.delete(this, data);
		}
	}

	private Node root;

	// 增加根节点信息
	public void addnode(String data) {
		Node newnode = new Node(data);
		if (this.root == null)
			this.root = newnode;
		else
			this.root.add(newnode);
	}

	public void printnode() {
		if (this.root != null)
			this.root.print();
	}

	public boolean contains(String name) {
		return this.root.search(name);
	}

	public void deletenode(String data) {
		if (this.contains(data))
			if (this.root.data.equals(data))
				this.root = this.root.next;
			else
				this.root.next.delete(root, data);
	}
}

 

4：实在懒得做了，将来在评论中更新吧。