在当前无序区R[1 H]中任取一个数据元素作为比较的基准(不妨记为X),用此基准将当前无序区划分为左右两个较小的无序区:R[1 I-1]和R[I+1 H],且左边的无序子区中数据元素均小于等于基准元素,右边的无序子区
两两比较待排序数据元素的大小,发现两个数据元素的次序相反时即进行交换,直到没有反序的数据元素为止。设想被排序的数组R[1 N]垂直竖立,将每个数据元素看成有重量的气泡,根据轻气泡不能在重气泡之下的原则,
每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最前,直到全部待排序的数据元素排完。例,使用选择排序对3、4、2、1、5 按照从小到大的顺序排序。排序过程分析:第一趟 1
在排序技术方面,主要考查插入排序、选择排序、冒泡排序、快速排序和堆排序等方法。1.插入排序每次将一个待排序的数据元素插入到前面已经排好序的数列中的适当位置,使数列依然有序,直到待排序数据元素全部插入
二分法查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列(即从小到大,但允许相邻元素值相等)。设有序线性表的长度为n,被查元素为x,则二分查找的方法如下。将x与线性表的中间
所谓查找是指在一个给定的数据结构中查找某个指定的元素。在查找的过程中,涉及查找的方法等问题,通常,根据不同的数据结构,应采用不同的查找方法。1.顺序查找顺序查找又称顺序搜索。顺序查找一般是指在线性表
所谓遍历二叉树,就是遵从某种次序,访问二叉树中的所有节点,使得每个节点仅被访问一次。(1)前序遍历前序遍历是指在访问根节点、遍历左子树与遍历右子树这三者中,首先访问根节点,然后遍历左子树,最后遍历右
二叉树(Binary Tree)是由n(n≥0)个节点的有限集合构成,此集合或者为空集,或者由一个根节点及两棵互不相交的左右子树组成,并且左右子树都是二叉树,如图1-7所示。二叉树可以是空集合,根可以有空的左子
本节要求考生掌握树和二叉树的基本定义,重点考查二叉树的基本性质和二叉树的遍历。1.树的定义树是由n(n≥0)个节点组成的有限集合。若n=0,称为空树;若n>0,则:1)有一个特定的称为根(Root)的节点。它
双向链表也叫双链表,是链表的一种,它的每个数据节点中都有两个指针,分别指向直接后继节点和直接前驱节点,如图1-5所示。所以,从双向链表中的任意一个节点开始,都可以很方便地访问它的前驱节点和后继节点。(
双向链表也叫双链表,是链表的一种,它的每个数据节点中都有两个指针,分别指向直接后继节点和直接前驱节点,如图1-5所示。所以,从双向链表中的任意一个节点开始,都可以很方便地访问它的前驱节点和后继节点。(
本节主要考查线性链表的存储方式和基本操作。1.线性表的链式存储在定义的链表中,若只含有一个指针域来存放下一个元素地址,称这样的链表为单链表或线性链表,如图1-4所示。在链式存储方式中,要求每个节点由两
队列(Queue)是只允许在一端删除、在另一端插入的顺序表。允许删除的一端叫作队头(Front),允许插入的一端叫作队尾(Rear),如图1-3所示。(1)队列的运算当队列中没有元素时称为空队列。在空队列中依次加入
栈和队列都是特殊的线性表,其定义符合线性表的定义,其操作也类似于线性表的操作,只不过增加了一些限定而已。1.栈的定义与操作栈(Stack)是一种特殊的线性表。栈是只能在表的一端进行插入和删除运算的线性表
线性表的顺序存储指的是用一组地址连续的存储单元依次存储线性表的数据元素。线性表的顺序存储又叫作顺序表。(1)线性表的顺序存储基本概念线性表的顺序存储结构具备以下两个基本特征:1)线性表中的所有元素所
本节主要考查线性表的基本概念,以及线性表的顺序存储方式。1.线性表概述线性表是一种常用的数据结构。在实际应用中,线性表都是以栈、队列、字符串、数组等特殊线性表的形式来使用的。由于这些特殊线性表都具有
根据数据结构中各数据元素之间前后件关系的复杂程度,一般将数据结构分为两大类型:线性结构与非线性结构。线性结构满足以下条件:1)有且只有一个根节点。2)每一个节点最多有一个前件,也最多只有一个后件。如
数据结构的表示除了用二元关系表示外,还可以直观地用图形表示。在数据结构的图形表示中,对于数据集合D中的每一个数据元素用中间标有元素值的方框表示,一般称之为数据节点,简称为节点。为了进一步表示各数据元
数据结构(Data Structure)是指相互之间存在一种或多种特定关系的数据元素的集合。数据(Data)是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(D
算法复杂度分为空间复杂度和时间复杂度。(1)算法的时间复杂度算法的时间复杂度是指执行算法所需要的计算工作量。同一个算法用不同的语言实现,或者用不同的编译程序进行编译,或者在不同的计算机上运行,效率均