三级数据库考点分析：数据结构与算法

1、数据

　　在计算机系统中，数据不仅包含了通常的数值概念，还有更广泛的含义我们把采用计算机对客观事物进行识别、存储和加工所做的描述，统称为数据。简言之，数据就是计算机化的信息
 数据的基本单位是数据元素。数据元素可由一个或多个数据项组成。数据项是数据的不可分割的最小单位，又称为关键码，其值能够唯一确定一个数据元素的数据项。

2、数据结构

 　　数据结构包括3个方面的内容：数据之间的逻辑关系、数据在计算机中的存储方式，以及在这些数据上定义的运算的集合。

　　(1)数据的逻辑结构。数据的逻辑结构与数据在计算机中的存储方式无关，它用来抽象地反映数据元素之间的逻辑关系。逻辑结构可分为线性结构和非线性结构。最常见的线性结构是线性表，最典型的非线性结构是树型结构。
　　(2)数据的存储结构。数据的存储结构实现了数据的逻辑结构在计算机内的存储问题，存储结构又称为物理结构。存储结构分为顺序存储结构与链式存储结构。
　　(3)数据的运算。数据的各种逻辑结构都有相对应的运算，每一种逻辑结构都有一个运算的集合。数据运算主要包括查找（检索）、排序、插人、更新及删除等。

考点2　主要的数据存储方式
 
　　实现数据的逻辑结构到计算机存储器的映像有多种不同的方式。顺序存储结构和链式存储结构是两种最主要的存储方式。

   1、顺序存储结构

　　 顺序存储结构是将逻辑上相邻的数据元素存储在物理上相邻的存储单元里，节点之间的关系由存储单元的相邻关系来决定，它主要用于存储线性结构的数据。顺序存储结构的主要特点如下。
　　(1)由于节点之间的关系由物理上的相邻关系决定，所以节点中没有链接信息域，只有自身的信息域，存储密度大，空间利用率高。
 　　(2)数据结构中第i个节点的存储地址乙可由下述公式计算求得：
　　 Li＝L0＋（i－1）×K   
　　L0为第一个节点存储地址，左为每个节点所占的存储单元数。
 　　(3)插人、删除运算会引起相应节点的大量移动各节点的物理地址是相邻的，每一次插人、删除运算会引起相应节点物理地址的重新排列。

2、链式存储结构
 
　　链式存储结构打破了计算机存储单元的连续性，可以将逻辑上相邻的两个数据元素存放在物理上不相邻的存储单元中链式存储结构的每个节点中至少有一个节点域，来体现数据之间逻辑上的联系。
 　　链式存储结构的主要特点包括以下几个方面。
　　(1)　节点中除自身信自、外，还有表示链接信息的指针域，因此比顺序存储结构的存储密度小，存储空间利用率低。
　　(2)　罗辑上相邻的节点物理上不一定相邻，可用于线性表、树、图等多种逻辑结构的存储表示。
　　(3)　插人、删除等操作灵活方便，不需要大量移动节点，只需将节点的指针值修改即可。

考点3算法设计与分析

　　 在计算机领域，一个算法实质上是针对所处理问题的需要，在数据的逻辑结构和存储结构的基础上施加的一种运算，它是解决特定问题的方法。一个算法所占用的计算机资源包括时间代价和空间代价两个方面时间代价的含义是：当问题的规模以某种单位由1增至n时，解决该问题的算法运行时所耗费的时间也以某种单位由f( 1)增至f(n)，则称该算法的时间代价为f(n)。
 　　空间代价的含义是：当问题的规模以某种单位由1增至n时，解决该问题的算法实现时所占用的空间也以某种单位由到g（1）增至g（n），则称该算法的空间代价为g（n）。

[1] [2] [3] 下一页

2．2线性表

　　线性表的逻辑结构是由n个数据元素组成的一个有限序列。线性表中所包含元素的个数叫线性表的长度．它是可变的．可同线性表中增加或删除元素。线性表包括顺序表、链表、散列表和串等。

　　线性表的基本运算有：置表空、求表长、读表元素、插人、删除及检索等操作。

考点4　顺序表和一维数组

　　线性表的顺序存储是线性表的一种最简单的存储结构。其存储方法是：在内存中为线性表开辟一块连续的存储空间，该存储空间所包含的存储单元数要大于或等于线性表的长度，让线性表的第一个元素存储在这个存储空间的第一个单元中，第二个元素存储在第二个单元中，其他元素依次类推。一般情况下，若长度为n的顺序表，在任何位置土插入或删除的概率相等，元素移动的平均次数均为n/2。

考点5链　表

　　链表分为线性链表和非线性链表二线性链表是线性表的链式存储表示，非线性链表是非线性数据结构树和图的链式存储表示。

1、线性链表
　　线性链表也称为单链表，其每个一节点中只包含一个指针域。对链表进行插人、删除运算时只需改变节点中指针域的值。
　　（1） 在指针一P后插人指针9的关键运算步骤：        
q ↑. link：＝P↑．link：
        p ↑. link：＝q；
　　（２）删除指针P后继节点q的关键运算步骤：
        q：＝p↑ . link；
        p↑. link：＝q↑．link；
　　（3）在第一个节点（或称头节点）前插人一个指针P的关键运算步骤：
        p↑. link：＝head；
          head：二P；
　　（４）删除表中头节点的关键运算步骤：
        head：＝head↑ . link：

 2、双链表
　　在双链表中，每个节点中设置有两个指针域，分别用以指向其前驱节点和后继节点。rlink指向节点的后继，llink指向节点的前驱，这样的结构方便向后和向前查找。
　　（l）若要在双链表中删除指针P所指的节点时，只需修改其前驱的rlink字段和后继的Mink字段，步骤如下：
        p↑ . llink↑. rlink：＝p↑. rlink；
        P↑T．rlink↑. llink：＝P↑．llink；
　　 (2)如果要在指针P后面插人指针q所指的新节点，只需修改P指针所指节点的rlink字段和原来后继均Ilink字段，并重新设置q所指节点的Mink和rlink值，步骤如下：
        q ↑. Mink：＝P：
        q↑．rlink：＝P↑．rlink;
        P↑．rlink r. Rink：＝q；
        p↑．rlink：＝q;
 
3、可利用空间表
 
　　可利用空间表的作用是管理可用于链表插人和删除的节点，当链表插人需要一个新节点时，就从可利用空间表中删除第一个节点，用这个节点去做链表插人；当从链表中删除一个节点时，就把这个节点插人到可利用空间表的第一个节点前面。

上一页  [1] [2] [3] 下一页

考点6　栈

　　栈又称为堆栈，它是一种运算受限的特殊的线性表，仅允许在表的一端进行插人和删除运算，可进行运算的一端为栈顶( top)，另一端为栈底( bottom)。表中无任何元素的栈称为空栈。由于栈的插人和删除运算仅在栈顶进行，后进栈的元素必定先被删除，所以又把栈称为“后进先出”（LIFO）表。
　　栈的基本操作有：
　　（1） push(S,X)。往栈S中插人（或称推人）一个新的栈顶元素x，即进栈。
　　（2）pop（S）。从栈S中删除（或称弹出）栈顶元素，即出栈。
　　（3）lop(S，X)：把栈S的栈顶元素读到变量x中，栈保持不变。
　　（４）empty（S）。判断栈S是否为空栈，是则返回值为真。
　　（5）makempty。（S）将栈S设置为空。
　　栈既然是一种线性表，所以线性表的存储结构同样也适用于栈。栈通常用顺序存储方式来存储，分配一块连续的存储区域存放栈中元素，用一个变量来指向当前栈顶。

考点7　队列
　　队列简称为队，它也是一种运算受限的线性表，队列的限定是仅允许在表的一端进行插入，而在另一端进行删除。进行删除操作的一端称做队列的头，进行插人操作的一端称为队列的尾.
　　队列的基本操作有：
    （1) enq（Q, X)。往队列口中插人一个新的队尾元素x，即人队。
    （2）deq（口）从队列Q中删除队头元素，即出队。
    （3 ) front口,x)将队列口的队头元素值读到变量x中，队列保持不变。
    （4）empty ( Q )．判断队歹，l口是否为空，是则返回值为真。
    （5）makempty（口）将队列口置为空队