2011山西省JAVA版数据结构考试技巧与口诀

Java数据结构和算法一、数组于简单排序 (1)二、栈与队列 (4)三、链表 (7)四、递归 (22)五、哈希表 (25)六、高级排序 (25)七、二叉树 (25)八、红—黑树 (26)九、堆 (36)十、带权图 (39)一、数组于简单排序数组数组（array）是相同类型变量的集合，可以使用共同的名字引用它。

数组可被定义为任何类型，可以是一维或多维。

数组中的一个特别要素是通过下标来访问它。

数组提供了一种将有联系的信息分组的便利方法。

一维数组一维数组（one-dimensional array ）实质上是相同类型变量列表。

要创建一个数组，你必须首先定义数组变量所需的类型。

通用的一维数组的声明格式是：type var-name[ ];获得一个数组需要2步。

第一步，你必须定义变量所需的类型。

第二步，你必须使用运算符new来为数组所要存储的数据分配内存，并把它们分配给数组变量。

这样Java 中的数组被动态地分配。

如果动态分配的概念对你陌生，别担心，它将在本书的后面详细讨论。

数组的初始化（array initializer ）就是包括在花括号之内用逗号分开的表达式的列表。

逗号分开了数组元素的值。

Java 会自动地分配一个足够大的空间来保存你指定的初始化元素的个数，而不必使用运算符new。

Java 严格地检查以保证你不会意外地去存储或引用在数组范围以外的值。

Java 的运行系统会检查以确保所有的数组下标都在正确的范围以内（在这方面，Java 与C/C++ 从根本上不同，C/C++ 不提供运行边界检查）。

多维数组在Java 中，多维数组（multidimensional arrays ）实际上是数组的数组。

你可能期望，这些数组形式上和行动上和一般的多维数组一样。

然而，你将看到，有一些微妙的差别。

定义多维数组变量要将每个维数放在它们各自的方括号中。

例如，下面语句定义了一个名为twoD 的二维数组变量。

int twoD[][] = new int[4][5];简单排序简单排序中包括了：冒泡排序、选择排序、插入排序；1.冒泡排序的思想：假设有N个数据需要排序，则从第0个数开始，依次比较第0和第1个数据，如果第0个大于第1个则两者交换，否则什么动作都不做，继续比较第1个第2个…，这样依次类推，直至所有数据都“冒泡”到数据顶上。

计算机等级考试中常见的数据结构题解题方法数据结构是计算机科学中十分重要的一门学科，它研究的是数据的组织、存储方式以及数据之间的关系等。

在计算机等级考试中，数据结构题目常常涉及到不同的数据结构的使用和解题方法。

本文将介绍一些常见的数据结构题解题方法，帮助考生更好地应对这类题目。

一、栈（Stack）栈是一种具有“先进后出”特点的数据结构，常用的操作有入栈（push）、出栈（pop）以及获取栈顶元素（top）等。

在计算机等级考试中，栈常常被用于处理括号匹配、表达式求值、深度优先搜索等问题。

下面以括号匹配为例，介绍解题方法。

1. 括号匹配括号匹配是栈的经典应用，题目通常要求判断输入的括号序列是否合法。

解题思路如下：- 创建一个空栈；- 从左到右遍历括号序列；- 如果是左括号，则入栈；- 如果是右括号，且栈为空，则返回不合法；- 如果是右括号，且栈不为空，则出栈；- 最后判断栈是否为空，若为空则表示序列合法，若不为空则表示序列不合法。

二、队列（Queue）队列是一种具有“先进先出”特点的数据结构，常用的操作有入队（enqueue）、出队（dequeue）以及获取队首元素（front）等。

在计算机等级考试中，队列常常用于解决与时间有关的问题，如进程调度、排队等。

下面以进程调度为例，介绍解题方法。

1. 短作业优先调度算法短作业优先调度算法是一种常用的进程调度算法，它根据各个进程的执行时间长度来进行排序，并让执行时间最短的进程先执行。

解题步骤如下：- 将所有进程按照执行时间从小到大进行排序；- 依次执行排序后的进程。

三、链表（Linked List）链表是一种非连续存储结构，每个节点包含数据元素和指向下一个节点的指针。

链表的常用操作有插入、删除、查找等。

在计算机等级考试中，链表常常用于解决节点间关系较为复杂的问题，如查找中间节点、反转链表等。

下面以查找中间节点为例，介绍解题方法。

1. 查找中间节点题目要求查找链表中的中间节点，解题思路如下：- 使用两个指针，一个快指针和一个慢指针；- 快指针每次移动两个节点，慢指针每次移动一个节点；- 当快指针到达链表末尾时，慢指针就指向了中间节点。

数据结构的精髓：掌握常用数据结构的15个要点数据结构是计算机科学中的重要基础知识，它描述了数据元素之间的关系以及对这些关系进行操作的方法。

掌握常用数据结构的关键要点，将有助于我们更好地理解和应用这些数据结构，提高程序的效率和性能。

以下是常用数据结构的15个要点，它们分别是：数组、链表、栈、队列、树、二叉树、堆、图、哈希表、集合、树状数组、字典树、并查集、线段树和红黑树。

1.数组：数组是由相同类型的元素组成的集合，使用连续的内存地址进行存储和访问。

数组的要点包括访问任意位置的时间复杂度为O(1)，插入和删除元素的时间复杂度较高为O(n)。

2.链表：链表通过节点之间的指针连接来存储数据，可以实现动态存储和删除数据元素。

链表的要点包括插入和删除元素的时间复杂度为O(1)，访问任意位置的时间复杂度较高为O(n)。

3.栈：栈是一种后进先出（LIFO）的数据结构，只允许在栈顶进行插入和删除操作。

栈的要点包括插入和删除元素的时间复杂度为O(1)，只能访问栈顶元素。

4.队列：队列是一种先进先出（FIFO）的数据结构，允许在队尾插入元素，在队头删除元素。

队列的要点包括插入和删除元素的时间复杂度为O(1)，只能访问队头和队尾元素。

5.树：树是一种非线性数据结构，由节点和边组成。

树的要点包括节点之间存在唯一的一对多关系，节点之间通过边相连，树的深度为根节点到叶子节点的最长路径。

6.二叉树：二叉树是一种特殊的树结构，每个节点最多有两个子节点。

二叉树的要点包括左子树和右子树的顺序不可颠倒，可以为空树。

7.堆：堆是一种特殊的二叉树结构，一般指的是二叉堆。

二叉堆的要点包括堆的顶部元素为最小值或最大值，插入和删除操作的时间复杂度为O(log n)。

8.图：图是一种非线性数据结构，由节点和边组成。

图的要点包括节点之间存在多对多关系，边可以有权重，可以是有向的或无向的。

9.哈希表：哈希表是一种基于哈希函数的数据结构，用于存储键值对。

JAVA面试的面试技巧1.深入了解所申请的职位和公司：在面试前，要对所申请的职位和公司有一个深入的了解。

了解公司的业务领域、发展方向、产品或服务等相关信息，以及该职位的具体要求、技术栈等。

这样能够更好地准备面试答案，同时也为自己决定是否适合这个职位和公司提供了参考。

2. 温故知新，复习基础知识：Java技术涉及广泛，面试中可能会涉及到各个方面的知识点，包括基础知识、数据结构与算法、多线程、网络编程、数据库等。

在面试前，要对基础知识进行复习，特别是数据结构和算法。

可以通过阅读书籍、参加培训课程、刷题等方式进行复习。

3.多练习面试题：在准备面试过程中，多练习一些常见的面试题可以帮助提高应对面试的能力。

可以通过查阅相关的面试题集、网站上的面试题等资源进行练习。

熟悉常见的面试题，能够更好地准备面试答案，提高应变能力。

4.个人项目准备：在面试中，面试官可能会询问个人项目经验，这就需要自己提前准备一些有代表性的项目，用于展示自己的技术能力和解决问题的能力。

可以挑选一到两个自己参与过的项目，对其中的关键环节和技术点进行深入理解和准备，可以准备一些代码片段以及相关的技术文档用于面试时展示。

5.反复回顾简历和准备面试答案：面试官通常会根据简历进行提问，所以要对自己的简历进行反复回顾，了解每个项目中的细节和技术点。

同时，对于常见的面试问题，要提前准备好相应的答案。

可以通过查找和学习他人的面试经验，整理出常见的面试问题，并准备相应的回答。

面试前可以尝试进行模拟面试，以便提高回答问题的流畅性和自信心。

6.保持积极的态度：面试是一个双向选择的过程，虽然您是应聘者，但也要保持积极的态度和自信心。

在面试过程中要展示自己对技术的热情和对公司的兴趣，同时也要尊重面试官，积极回答问题和与面试官进行互动。

7.提前了解面试流程：在面试前，可以提前了解面试的整个流程，包括面试方式、面试环节、面试时间等方面的信息。

了解面试的流程可以让自己心里有数，做好相应的准备，同时也可以提前规划好自己的时间和行程。