2011年计算机二级考试公共基础知识冲刺复习笔记（18）

文章作者 100test 发表时间 2011:03:18 18:47:57
来源 100Test.Com百考试题网

　　Point4：线性链表、双向链表与循环链表

　　出题趋势

　　考试日期05-4　05-9　07-9　08-9

　　出题次数2　2　1　1

　　考点精讲

　　1、数据结构中，每个数据存储在一个存储单元中，这个存储单元称为结点。在链式存储方式中，要求每个结点由两部分组成：—部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点(即前件或后件)。

　　2、线性链表：线性表的链式存储结构，称为线性链表。

　　(1)对于大的线性表，特别是元素变化频繁的线性表不宜采用顺序存储结构，而要用链式存储结构。

　　(2)数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。

　　(3)结点由两部分组成：(1)用于存储数据元素值，称为数据域；(2)用于存放指针，称为指针域，用于指向前一个或后一个结点。

　　(4)在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。

　　(5)链式存储方式既可用于表示线性结构，也可用于表示非线性结构。

　　(6)线性链表，HEAD称为头指针，HEAD=NULL(或0)称为空表。

　　线性链表的基本运算：查找、插入、删除。

　　3、双向链表：两指针：左指针(Llink)指向前件结点，右指针(Rlink)指向后件结点。4、循环链表的两个特点：

　　(1)增加了一个表头结点。

　　(2)最后一个结点的指针域不是空，而是指向表头结点。

　　真题分析

　　【真题1】下列叙述中正确的是________。（2008年9月）

　　A)顺序存储结构能存储有序表，链式存储结构不能存储有序表

　　B)链式存储结构比顺序存储结构节省存储空间

　　C)顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的

　　D)顺序存储结构只针对线性结构，链式存储结构只针对非线性结构

　　解析：顺序存储方式主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。而链式存储结构的存储空间不一定是连续的。

　　链式结构的结点由两部分组成，一部分是数据信息，另一部分是地址域，因此在存储空间上要多于顺序存储所占用的空间。

　　答案：C

　　【真题2】下列叙述中正确的是________。（2007年9月）

　　A)程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构

　　B)三种说法都不对

　　C)数据的逻辑结构与存储结构必定是一一对应的

　　D)由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构

　　解析：数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结构)。一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用

　　的存储结构有顺序、链接、索引等。

　　答案：B

　　【真题3】下列叙述中正确的是________。（2005年9月）

　　A)一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率

　　B)一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率

　　C)一个逻辑数据结构只能有一种存储结构

　　D)数据的逻辑结构属于线性结构，存储结构属于非线性结构

　　解析：一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。而采用不同的存储结构，其数据处理的效率是不同的。

　　答案：B

　　【真题4】数据结构分为逻辑结构和存储结构，循环队列属于__【5】__结构。（2005年9月）

　　解析：数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结构)。所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。可知，循环队列应当是存储结构。

　　答案：存储

　　【真题5】数据的存储结构是指________。（2005年4月）

　　A)数据在计算机中的顺序存储方式

　　B)数据的逻辑结构在计算机中的表示

　　C)存储在外存中的数据

　　D)数据所占的存储空间量

　　解析：数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构，也称数据的物理结构。

　　答案：B

　　【真题6】下列对于线性链表的描述中正确的是________。（2005年4月）

　　A)存储空间必须连续，且前件元素一定存储在后件元素的前面

　　B)存储空间必须连续，且各元素的存储顺序是任意的

　　C)存储空间不一定是连续，且各元素的存储顺序是任意的

　　D)存储空间不一定是连续，且前件元素一定存储在后件元素的前面

　　解析：在链式存储结构中，存储数据的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，数据元素之问的逻辑关系，是由指针域来确定的。

　　答案：C

　　#ff0000>