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

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

　　Point2：线性表、线性链表和循环链表

　　出题趋势

　　考试日期06-4　06-9　09-3　10-9

　　出题次数1　　　1　　　1　　　1

　　考点精讲

　　1、如果在一个数据结构中一个数据元素都没有，则称为空的数据结构。根据数据结构中各数据元素之间的前后件关系的复杂程度，分为线性结构与非线性结构。

　　2、如果一个非空的数据结构满足下列两个条件：①有且只有一个根结点；②每一个结点最多有一个前件，也最多有一个后件，则称该数据结构为线性结构。线性表是一个典型的线性结构。常见的有：线性表，栈，队列，循环队列和线性链表等。

　　3、不满足线性结构条件的数据结构，就是非线性结构。常见的有：数组、广义表、树、二叉树和图都是非线性结构。

　　4、在计算机内，线性表的存储结构有两种：顺序存储（称为线性表）和链式存储（线性链表）。线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构。

　　真题分析

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

　　A)循环队列是非线性结构

　　B)有序线性表既可以采用顺序存储结构，也可以采用链式存储结构

　　C)栈是“先进先出”的线性表

　　D)队列是“先进后出”的线性表

　　解析：主要考查了栈、队列、循环队列的概念，栈是“先进后出”的线性表，队列是“先进先出”的线性表。根据数据结构中各数据元素之问的前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。循环队列也是线性结构。有序线性表既可以采用顺序存储结构，又可以采用链式存储结构。

　　答案：B

　　【真题2】数据结构分为线性结构和非线性结构，带链的队列属于__【5】__结构。（2006年9月）

　　解析：数据结构分为线性结构和非线性结构，其中队列属于线性结构。队列有两种存储结构，一种是顺序存储结构，称为顺序队列；另一种是链式存储结构，称为带链队列。题目中所说的带链的队列就是指带链队列。无论队列采取哪种存储结构，其本质还是队列，仍属于一种线性结构。因此，本题的正确答案是线性结构。

　　答案：线性

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

　　A)双向链表是非线性结构

　　B)只有根结点的二叉树是线性结构

　　C)线性链表是线性表的链式存储结构

　　D)栈与队列是非线性结构

　　解析：线性链表是线性表的链式存储结构。栈与队列是特殊的线性表，它们也是线性结构；双向链表是线性表的链式存储结构，其对应的逻辑结构也是线性结构，而不是非线性结构；二叉树是非线性结构，而不是线性结构。

　　一个非空的数据结构如果满足下列两个条件：

　　(1)有且只有一个根结点；

　　(2)每一个结点最多有一个前件，也最多有一个后件，则称之为线性结构。

　　答案：C

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

　　A)线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构

　　B)上述三种说法都不对

　　C)线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的

　　D)线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构

　　解析：可以从存储密度的角度，比较链式存储结构和顺序存储结构的存储空间：所谓存储密度是指结点数据本身所占的存储量除以结点结构所占的存储总量所得的值。这个值越大，存储空间利用率越高。顺序表是静态分配的，其存

　　储密度为1；而链式存储是动态分配的，其存储密度小于1。

　　答案：D

　　#ff0000>