Access等级考试公共基础试题含答案.doc

第1章 数据结构与算法
考点1：算法 ★★
考点点拨：重要考查算法的基本概念，算法的时间复杂度和空间复杂度。

【试题1】算法的时间复杂度是指 。
A) 执行算法程序所需要的时间
B) 算法程序的长度
C) 算法执行过程中所需要的基本运算次数
D) 算法程序中的指令条数
答案：C
分析：所谓算法的时间复杂度，是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量=f(n)。
其中n是问题的规模。例如，两个n阶矩阵相乘所需要的基本运算(即两个实数的乘法)次数为n3，即计算工作量为n3，也就是时间复杂度为n3。

理论链接：算法时间复杂度
在详细分析一个算法的工作量时，还会存在这么的问题：对于一个固定的规模，算法所执行的基本运算次数还也许与特定的输入有关，而实际上又不也许将所有也许情况下算法所执行的基本运算次数都列举出来。例如，“在长度为n的一维数组中查找值为x的元素”，若采取次序搜索法，即从数组的第一个元素开始，逐一与被查值x进行比较。显然，假如第一个元素恰为x，则只需要比较1次。但假如x为数组的最后一个元素，或者x不在数组中，则需要比较n次才能得到成果。因此，在这个问题的算法中，其基本运算(即比较)的次数与详细的被查值x有关。

【试题2】算法的空间复杂度是指 。
A) 算法程序的长度
B) 算法程序中的指令条数
C) 算法程序所占的存储空间
D) 算法执行过程中所需要的存储空间
答案：D
分析：一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间(例如，在链式结构中，除了要存储数据自身外，还需要存储链接信息)。假如额外空间量相对于问题规模来说是常数，则称该算法是原地(in place)工作的。在许多实际问题中，为了减少算法所占的存储空间，一般采取压缩存储技术，尽也许减少无须要的额外空间。
【试题3】一个算法一般由两种基本要素组成：一是对数据对象的运算和操作，二是算法的 。
答案：控制结构
分析：一个算法一般由两种基本要素组成：一是对数据对象的运算和操作，二是算法的控制结构。
(1) 算法中对数据的运算和操作
每个算法实际上是按解题要求从环境能进行的所有操作中选择适宜的操作所组成的一组指令序列。因此，计算机算法就是计算机能处理的操作所组成的指令序列。
一般，计算机能够执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。计算机程序就是按解题要求从计算机指令系统中选择适宜的指令所组成的指令序列。在一般的计算机系统中，基本的运算和操作有如下四类。
l 算术运算：重要包括加、减、乘、除等运算；
l 逻辑运算：重要包括“与”、“或”、“非”等运算；
l 关系运算：重要包括“不小于”、“小于”、“等于”、“不等于”等运算；
l 数据传输：重要包括赋值、输入、输出等操作。
(2) 算法的控制结构
一个算法的功效不但取决于所选用的操作，并且还与各操作之间的执行次序有关。算法中各操作之间的执行次序称为算法的控制结构。算法的控制结构给出了算法的基本框架，它不但决定了算法中各操作的执行次序，并且也直接反应了算法的设计是否符合结构化标准。描述算法的工具一般有老式流程图、N-S结构化流程图、算法描述语言等。一个算法一般都能够用次序、选择、循环三种基本控制结构组合而成。
【试题4】在同一个问题规模下，假如算法执行所需的基本运算次数取决于某一特定输入时，能够用平均性态和 两种措施来分析算法的工作量。
答案：最坏情况复杂性
分析：所谓平均性态分析，是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。设x是所有也许输入中的某个特定输入，p(x)是x出现的概率(即输入为x的概率)，t(x)是算法在输入为x时所执行的基本运算次数，则算法的平均性态定义为

A(n)=

其中Dn表示当规模为n时，算法执行时所有也许输入的集合。这个式子中的t(x)能够通过度析算法来加以确定；而p(x)必须由经验或用算法中有关的某些特定信息来确定，一般是不能解析地加以计算的。假如确定p(x)比较困难，则会给平均性态的分析带来困难。
所谓最坏情况复杂性分析，是指在规模为n时，算法所执行的基本运算的最大次数。它定义为

W(n)={t(x)}

显然，W(n)的计算要比A(n)的计算以便得多。因为W(n)实际上是给出了算法工作量的一个上界，因此，它比A(n)更具备实用价值。
【试题5】算法设计基本措施重要有 、归纳法、递推、递归和减半递推技术。
答案：列举法
分析：算法设计基本措施重要有列举法、归纳法、递推、递归和减半递推技术。
(1) 列举法
列举法的基本思想是，依照提出的问题，列举所有也许的情况，并用问题中给定的条件检查哪些是需要的，哪些是不需要的。列举法的特点是算法比较简单。但当列举的也许情况较多时，执行列举算法的工作量将会很大。列举原理是计算机应用领域中十分重要的原理。列举算法是一个比较笨拙而原始的措施，其运算量比较大，但在有些实际问题中(如寻找途径、查找、搜索等问题)，局部使用列举法却是很有效的。因此，列举算法是计算机算法中的一个基础算法。
(2) 归纳法
归纳法的基本思想是，通过列举少许的特殊情况，通过度析，最后找出一般的关系。显然，归纳法要比列举法更能反应问题的本质，并且能够处理列举量为无限的问题。从本质上讲，归纳就是通过观测某些简单而特殊的情况，最后总结出一般性的结论。归纳是一个抽象，即从特殊现象中找出一般关系。
(3) 递推
所谓递推，是指从已知的初始条件出发，逐次推出所要求的各中间成果和最后成果。其中初始条件或是问题自身已经给定，或是通过对问题的分析与化简而确定。递推本质上也属于归纳法，工程上许多递推关系式实际上是通过对实际问题的分析与归纳而得到的，因此，递推关系式往往是归纳的成果。递推算法在数值计算中是极为常见的。不过，对于数值型的递推算法必须要注意数值计算的稳定性 问题。
(4) 递归
递归的基础也是归纳。在工程实际中，有许多问题就是用递归来定义的，数学中的许多函数也是用递归来定义的。递归在可计算性理论和算法设计中占有很重要的地位。递归分为直接递归与间接递归两种。假如一个算法P显式地调用自己则称为直接递归。假如算法P调用另一个算法Q，而算法Q又调用算法P，则称为间接递归调用。
递归过程能将一个复杂的问题归结为若干个较简单的问题，然后将这些较简单的问题再归结为更简单的问题，这个过程能够一直做下去，直到最简单的问题为止。
(5) 减半递推技术
实际问题的复杂程度往往与问题的规模有着亲密的联系。因此，利用分治法处理此类实际问题是有效的。所谓分治法，就是对问题分而治之。工程上常用的分治法是减半递推技术。所谓“减半”，是指将问题的规模减半，而问题的性质不变；所谓“递推”，是指重复“减半”的过程。
考点2：数据结构的基本概念 ★★
考点点拨：重要考查数据结构的定义、数据结构的图形表示、线性结构与非线性结构的基本概念。

【试题6】下列论述中，错误的是 。
A) 数据的存储结构与数据处理的效率亲密有关
B) 数据的存储结构与数据处理的效率无关
C) 数据的存储结构在计算机中所占的空间不一定是连续的
D) 一个数据的逻辑结构能够有多个存储结构
答案：B
分析：数据处理是计算机应用的一个重要领域，在实际进行数据处理时，被处理的各数据元素总是被存储在计算机的存储空间中，各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的，一般也不也许相同。
数据的逻辑结构在计算机存储空间中的存储形式称为数据的存储结构(也称数据的物理结构)。一般来说，一个数据的逻辑结构依照需要能够表示成多个存储结构，常用的存储结构有次序、链接、索引等存储结构。而采取不一样的存储结构，其数据处理的效率是不 同的。
【试题7】所谓 ，是指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，也包括对数据元素进行分析。
答案：数据处理
分析：所谓数据处理，是指对数据集合中的各元素以各种方式进行运算。在数据处理领域中，建立数学模型有时并不十分重要，实际上，许多实际问题是无法表示成数学模型的。人们最感兴趣的是懂得数据集合中各数据元素之间存在什么关系，应怎样组织它们，即怎样表示所需要处理的数据元素。
【试题8】数据结构是指相互有关联的 的集合。
答案：数据元素
分析：数据结构是指相互有关联的数据元素的集合。例如，向量和矩阵就是数据结构，在这两个数据结构中，数据元素之间有着位置上的关系。又如，图书馆中的图书卡片目录，则是一个较为复杂的数据结构，对于列在各卡片上的各种书之间，也许在主题、作者等问题上相互关联，甚至一本课自身也有不一样的有关成份。
数据元素具备广泛的含义。一般来说，现实世界中客观存在的一切个体都能够是数据元素。在数据处理领域中，每一个需要处理的对象都能够抽象成数据元素。数据元素一般简称为元素。
【试题9】数据元素之间的任何关系都能够用 关系来描述。
答案：前驱和后继
分析：前驱和后继关系是数据元素之间的一个基本关系，但前驱和后继关系所示的实际意义随详细对象的不一样而不一样。一般来说，数据元素之间的任何关系都能够用前驱和后继关系来描述。
【试题10】常用的存储结构有次序、链接、 等存储结构。
答案：索引
分析：一般来说，一个数据的逻辑结构依照需要能够表示成多个存储结构，常用的存储结构有次序、链接、索引等存储结构。而采取不一样的存储结构，其数据处理的效率是不一样的。因此，在进行数据处理时，选择适宜的存储结构是很重要的。
【试题11】在数据结构中，没有前驱的结点称为 。
A) 终端结点 B) 根结点 C) 叶子结点 D) 内部结点
答案：B
分析：在数据结构中，没有前驱的结点称为根结点；没有后继的结点称为终端结点(也称为叶子结点)。数据结构中除了根结点与终端结点外的其他结点一般称为内部结点。
【试题12】在数据结构中，结点及结点间的相互关系是数据的逻辑结构。数据结构按逻辑关系的不一样，一般可分为 两类。
A) 动态结构和静态结构 B) 紧凑结构和非紧凑结构
C) 线性结构和非线性结构 D) 内部结构和外部结构
答案：C
分析：在数据结构中，结点及结点间的相互关系有线性结构和非线性结构。例如线性表是线性结构，树和图是非线性结构。

理论链接：线性结构、非线性结构
一个非空的数据结构满足如下两点：
l 有且只有一个根结点；
l 每一个结点最多有一个前驱，也最多有一个后继。
则称该数据结构为线性结构。线性结构又称线性表。在线性结构中，各数据元素之间的前驱和后继关系是很简单的。在一个线性结构中插入或删除任何一个结点后还应是线性结构。
假如一个数据结构满足上述两个条件，但当在此数据结构中插入或删除任何一个结点后就不满足这两个条件了，则该数据结构不能称为线性结构。假如一个数据结构不是线性结构，则称之为非线性结构。

在非线性结构中，各数据元素之间的前驱和后继关系要比线性结构复杂，因此，对非线性纬构的存储与处理比线性结构要复杂得多。
线性结构与非线性结构都能够是空的数据结构。一个空的数据结构到底是属于线性结构还是属于非线性结构，这要依照详细情况来确定。假如对该数据结构的运算是按线性结构的规则来处理的，则属于线性结构；否则属于非线性结构。
考点3：线性表及其次序存储结构 ★★★
考点点拨：重要考查线性表的基本概念、线性表的次序存储结构、次序表的插入与删除运算。

【试题13】给定一个有n个元素的线性表。若采取次序存储结构，则在等概率前提下，向其插入一个元素需要移动的元素个数平均为 。
A) n+l B) n/2 C) (n+1)/2 D) n
答案：B
分析：假设Pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素是所需移动元素的期望值(平均次数)，即为：

假如在线性表上任何一个位置中插入元素的概率相等，即

则

【试题14】在稍微复杂的线性表中，一个数据元素能够由若干个数据项组成，在这种情况下，常把数据元素称为 。
A) 数据单元 B) 统计 C) 统计项 D) 数据项
答案：B
分析：线性表是最简单、最常用的一个数据结构。由一组数据元素组成。至于每个数据元素的详细含义，在不一样的情况下各有不一样，它能够是一个数，或一个符号，也能够是一页书，甚至更复杂的信息。在稍微复杂的线性表中，一个数据元素能够由若干个数据项组成，在这种情况下，常把数据元素称为统计(record)，含有大量统计的线性表又称文献(file)。
理论链接：线性表结构特性
线性表是一个线性结构。数据元素在线性表中的位置只取决于它们自己的序号，即数据元素之间的相对位置是线性的。
非空线性表有如下某些结构特性：
l 有且只有一个根结点a1，它无前驱；
l 有且只有一个终端结点an，它无后继；
l 除根结点与终端结点外，其他所有结点有且只有一个前驱，也有且只有一个后继。线性表中结点的个数n称为线性表的长度。当n=0时，称为空表。
【试题15】在计算机中存储线性表，一个最简单的措施是 。
答案：次序存储
分析：在计算机中存储线性表，一个最简单的措施是次序存储，也称为次序分派。
线性表的次序存储结构具备如下两个基本特点：
(1) 线性表中所有的数据元素所占的存储空间是连续的；
(2) 线性表中各数据元素在存储空间中是按逻辑次序依次存储的。
能够看出，在线性表的次序存储结构中，其前后继两个元素在存储空间中是紧邻的，且前驱元素一定存储在后继元素的前面。
在线性表的次序存储结构中，假如线性表中各数据元素所占的存储空间(字节数)相等，则要在该线性表中查找某一个元素是很以便的。
假设线性表中的第一个数据元素的存储地址(指第一个字节的地址，即首地址)为ADR(a1)，每一个数据元素占k个字节，则线性表中第i个元素ai在计算机存储空间中的存储地址为ADR(ai)=ADR(a1)+(i－1)k
即在次序存储结构中，线性表中每一个数据元素在计算机存储空间中的存储地址由该元素在线性表中的位置序号惟一确定的。
【试题16】在程序设计语言中，一般定义一个 来表示线性表的次序存储空间。
答案：一维数组
分析：在程序设计语言中，一般定义一个一维数组来表示线性表的次序存储空间。因为程序设计语言中的一维数组与计算机中实际的存储空间结构是类似的，这就便于用程序设计语言对线性表进行各种运算处理。
在用一维数组存储线性表时，该一维数组的长度一般要定义得比线性表的实际长度大某些，以便对线性表进行各种运算，尤其是插入运算。在一般情况下，假如线性表的长度在处理过程中是动态变化的，则在开辟线性表的存储空间时要考虑到线性表在动态变化过程中也许达成的最大长度。假如开始时所开辟的存储空间太小，则在线性表动态增加时也许会出现存储空间不够，而导致无法再插入新的元素；但假如开始时所开辟的存储空间太大，而实际上又用不着那么大的存储空间，则会导致存储空间的浪费。在实际应用中，能够依照线性表动态变化过程中的一般规模来决定开辟的存储空间量。
考点4：栈和队列 ★★★★
考点点拨：重要考查栈及其基本运算、队列及其基本运算。

【试题17】下列有关栈的论述中正确的是 。
A) 在栈中只能插入数据 B) 在栈中只能删除数据
C) 栈是先进先出的线性表 D) 栈是先进后出的线性表
答案：D
分析：在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的另一端称为栈底。栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。即栈是按照“先进后出”(FILO，First In Last Out)或“后进先出”(LIFO，Last In First Out)的标准组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。由此能够看出，栈具备记忆作用。

理论链接：栈的基本概念
栈实际上也是线性表，是一个特殊的线性表。在这种特殊的线性表中，其插入与删除运算都只能在线性表的一端进行。即在这种线性表的结构中，一端是封闭的，不允许进行插入与删除元素；另一端是开口的，允许插入与删除元素。在次序存储结构下，对这种类型线性表(栈)的插入与删除运算是不需要移动表中其他数据元素的。
一般用指针top来指示栈顶的位置，用指针bottom指向栈底。
往栈中插入一个元素称为入栈运算，从栈中删除一个元素(即删除栈顶元素)称为退栈运算。栈顶指针top动态反应了栈中元素的变化情况。

【试题18】栈的基本运算有三种：入栈、退栈与 。
答案：读栈顶元素
分析：栈的基本运算有三种：入栈、退栈与读栈顶元素。
(1) 入栈运算
入栈运算是指在栈顶位置插入一个新元素。这个运算有两个基本操作：首先将栈顶指针进一(即top加1)，然后将新元素插入到栈顶指针指向的位置。
当栈顶指针已经指向存储空间的最后一个位置时，阐明栈空间已满，不也许再进行入栈操作。这种情况称为栈“上溢”错误。
(2) 退栈运算
退栈运算是指取出栈顶元素并将该元素赋给一个指定的变量。这个运算有两个基本操作：首先将栈顶元素(栈顶指针指向的元素)赋给一个指定的变量，然后将栈顶指针退一(即top减1)。
当栈顶指针为0时，阐明栈空，不也许进行退栈操作。这种情况称为栈“下溢”错误。
(3) 读栈顶元素
读栈顶元素是指将栈顶元素赋给一个指定的变量。必须注意，这个运算不删除栈顶元素，只是将它的值赋给一个变量，因此，在这个运算中，栈顶指针不会变化。当栈顶指针为0时，阐明栈空，读不到栈顶元素。
【试题19】下列有关队列的论述中正确的是 。
A) 在队列中只能插入数据 B) 在队列中只能删除数据
C) 队列是先进先出的线性表 D) 队列是先进后出的线性表
答案：C
分析：队列(queue)是指允许在一端进行插入、而在另一端进行删除的线性表。允许插入的一端称为队尾，一般用一个称为尾指针(rear)的指针指向队尾元素，即尾指针总是指向最后被插入的元素；允许删除的一端称为队头，一般也用一个排头指针(front)指向队头元素的前一个位置。显然，在队列这种数据结构中，最先插入的元素将最先能够被删除，反之，最后插入的元素将最后才能被删除。因此，队列又称为“先进先出”(FIFO，First In First Out)或“后进后出”(LILO，Last In Last Out)的线性表，它体现了“先来先服务”的标准。在队列中，队尾指针rear与队头指针front共同反应了队列中元素动态变化的情况。
往队列的队尾插入一个元素称为入队运算，从队列的排头删除一个元素称为退队运算。与栈类似，在程序设计语言中，用一维数组作为队列的次序存储空间。
【试题20】下列数据结构具备记忆功效的是 。
A) 队列 B) 循环队列 C) 栈 D) 次序表
答案：C
分析：栈也被称为“先进后出”表或“后进先出”表，具备记忆作用。
【试题21】给定一个足够长的栈，若入栈元素的序列为a、b、c，则 是不也许的出栈序列。
A) b、c、a B) a、c、b C) c、a、b D) b、a、c
答案：C
分析：栈也被称为“先进后出”表或“后进先出”表。入栈元素的序列为a、b、c。则c、a、b不也许为出栈序列。
【试题22】循环队列重要有两种基本运算：入队运算与退队运算。每进行一次入队运算，队尾指针就 。
答案：进一
分析：循环队列重要有两种基本运算：入队运算与退队运算。
每进行一次入队运算，队尾指针就进一。当队尾指针rear=m+1时，则置rear=1。每进行一次退队运算，排头指针就进一。当排头指针front=m+1时，则置front=1。

理论链接：循环队列的两种基本运算
(1) 入队运算
入队运算是指在循环队列的队尾加入一个新元素。这个运算有两个基本操作：首先将队尾指针进一(即rear=rear+1)，并当rear=m+1时置rear=l；然后将新元素插入到队尾指针指向的位置。
当循环队列非空(s=1)且队尾指针等于队头指针时，阐明循环队列已满，不能进行入队运算，这种情况称为“上溢”。
(2) 退队运算
退队运算是指在循环队列的排头位置退出一个元素并赋给指定的变量。这个运算有两个基本操作：首先将排头指针进一(即front=front+1)，并当front=m+l时置front=1；然后将队头指针指向的元素赋给指定的变量。
当循环队列为空(s=0)时，不能进行退队运算，这种情况称为“下溢”。

【试题23】应用程序在执行过程中，需要通过打印机输出数据时，一般先形成一个打印作业，将其存储在硬盘中的一个指定 中。当打印机空闲时，就会按先来先服务的方式从中取出待打印的作业进行打印。
A) 栈 B) 队列 C) 数组 D) 字符串
答案：B
分析：依照数据结构对队列先进先出的定义，打印作业应当存储在队列中。
【试题24】递归算法一般需要利用 实现。
A) 栈 B) 队列 C) 循环链表 D) 双向链表
答案：A
分析：递归是指一个过程直接或间接地调用自己。在递归算法运行的过程中，需要利用栈保存递归过程的运算成果、各种参数和返回地址等工作统计，从而使递归过程得以顺利进行。
【试题25】对长度为n的线性表进行插入一个新元素或删除一个已经有的元素时，在最坏情况下所需要的比较次数为 。
A) n+l B) n C) (n+1)/2 D) n/2
答案：B
分析：在一般情况下，要在次序存储的线性表中插入一个新元素或删除一个元素时，为了确保插入或删除后的线性表仍然为次序存储，则在插入或删除过程中需要移动大量的数据元素。在平均情况下，为了在次序存储的线性表中插入或删除一个元素，需要移动线性表中约二分之一的元素；在最坏情况下，则需要移动线性表中所有的元素。因此，对于大的线性表，尤其是在元素的插入或删除很频繁的情况下，采取次序存储结构是很不以便的，插入与删除运算的效率会很低。
【试题26】在一个容量为25的循环队列中，若头指针front＝16，尾指针rear＝9，则该循环队列中共有 个元素。
答案：18
分析：在循环队列中，用队尾指针rear指向队列中的队尾元素，用队头指针front指向队头元素的前一个位置，因此，从队头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素。依照题意，该循环队列中共有元素数为： 25－16+9=18个。
考点5：线性链表 ★★★★★
考点点拨：重要考查线性链表的基本概念、线性链表的基本运算、循环链表及其基本运算。

【试题27】下列论述中，正确的是 。
A) 线性链表中的各元素在存储空间中的位置必须是连续的
B) 线性链表中的表头元素一定存储在其他元素的前面
C) 线性链表中的各元素在存储空间中的位置不一定是连续的，但表头元素一定存储在其他元素的前面
D) 线性链表中的各元素在存储空间中的位置不一定是连续的，且各元素的存储次序也是任意的
答案：D
分析：线性链表是链式存储结构，在链式存储结构中，存储数据结构的存储空间能够不连续，各数据结点的存储次序与数据元素之间的逻辑关系能够不一致，而数据元素之间的逻辑关系是由指针域来确定的。
链式存储方式既可用于表示线性结构，也可用于表示非线性结构。在用链式结构表示较复杂的非线性结构时，其指针域的个数要多某些。
【试题28】在链式存储方式中，要求每个结点由两部分组成：一部分用于存储数据元素值，称为 ；另一部分用于存储数据元素的指针，称为 。
答案：数据域，指针域
分析：在链式存储方式中，要求每个结点由两部分组成：一部分用于存储数据元素值，称为数据域；另一部分用于存储指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点(即前驱或后继)。

理论链接：线性表的链式存储结构
线性表的链式存储结构称为线性链表。
为了适应线性表的链式存储结构，计算机存储空间被划分为一个个的小块，每一小块占若干字节，一般称这些小块为存储结点。
为了存储线性表中的每一个元素，首先要存储数据元素的值，另首先要存储各数据元素之间的前驱后继关系。为此目标，将存储空间中的每一个存储结点分为两部分：一部分用于存储数据元素的值，称为数据域；另一部分用于存储下一个数据元素的存储序号(即存储结点的地址)，即指向后继结点，称为指针域。由此可知，在线性链表中，存储空间的结构如图1.1所示。
在线性链表中，用一个专门的指针HEAD指向线性链表中第一个数据元素的结点(即存储线性表中第一个数据元素的存储结点的序号)。线性表中最后一个元素没有后件，因此，线性链表中最后一个结点的指针域为空(用NULL或0表示)，表示链表终止。线性链表的逻辑结构如图1.2所示。

存储序号
数据域
指针域
1

2

…

i

…

m

图1.1 线性链表的存储空间

图1.2 线性链表的逻辑结构
【试题29】数据结构分为逻辑结构与物理结构(存储结构)，线性链表属于 。
答案：物理结构(存储结构)
分析：数据结构作为计算机的一门学科，重要研究和讨论如下3个方面的问题：
l 数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；
l 在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；
l 对各种数据结构进行的运算。
数据的逻辑结构在计算机存储空间中的存储形式称为数据的存储结构(也称数据的物理结构)。线性链表属于存储结构。
【试题30】在 中，每一个结点只有一个指针域，由这个指针只能找到后继结点，但不能找到前驱结点。
答案：线性单链表
分析：在线性单链表中，每一个结点只有一个指针域，由这个指针只能找到后继结点，但不能找到前驱结点。因此，在这种线性链表中，只能沿指针向链尾方向进行扫描，这对于某些问题的处理会带来不便，因为在这种链接方式下，由某一个结点出发，只能找到它的后件，而为了找出它的前驱，必须从头指针开始重新寻找。
为了填补线性单链表的这个缺陷，在某些应用中，对线性链表中的每个结点设置两个指针，一个称为左指针(Llink)，用以指向其前驱结点：另一个称为右指针(rlink)，用以指向其后继结点。这么的线性链表称为双向链表。
【试题31】与单向链表相比，双向链表的优点之一是 。
A) 更节约存储空间 B) 便于进行随机访问
C) 更轻易访问相邻结点 D) 能够省略头指针和尾指针
答案：C
分析：双向链表的每个结点设置两个指针，一个称为左指针(Llink)，用以指向其前件结点：另一个称为右指针(rlink)，用以指向其后件结点。这么在访问相邻结点时候要比单向链表以便的多。
【试题32】在实际应用中，带链的栈能够用来搜集计算机存储空间中所有空闲的存储结点，这种带链的栈称为 。
答案：可利用栈
分析：栈也是线性表，也能够采取链式存储结构。
在实际应用中，带链的栈能够用来搜集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可用栈。因为可用栈链接了计算机存储空间中所有的空闲结点，因此，当计算机系统或用户程序需要存储结点时，就能够从中取出栈顶结点，当计算机系统或用户程序释放一个存储结点(该元素从表中删除)时，则要将该结点放回到可用栈的栈顶。由此可知，计算机中的所有可用空间都能够以结点为单位链接在可用栈中。伴随其他线性链表中结点的插入与删除，可用栈处在动态变化之中，即可用栈常常要进行退栈与入栈操作。
【试题33】为了要在线性链表中插入一个新元素，首先要给该元素分派一个 ，用于存储该元素的值。
答案：新结点
分析：线性链表的插入是指在链式存储结构下的线性表中插入一个新元素。
为了要在线性链表中插入一个新元素，首先要给该元素分派一个新结点，以便用于存储该元素的值。新结点能够从可利用栈中取得。然后将存储新元素值的结点链接到线性链表中指定的位置。

理论链接：线性链表的插入
因为插入的新结点取自于可用栈，因此，只要可用栈不空，在线性链表插入时总能取到存储插入元素的新结点，不会发生“上溢”的情况。并且，因为可用栈是公用的，多个线性链表能够共享它，从而很以便地实现了存储空间的动态分派。另外，线性链表在插入过程中不发生数据元素移动的现象，只需变化有关结点的指针即可，从而提升了插入的 效率。

【试题34】在线性链表中删除一个元素后，只需变化被删除元素所在结点的前一个结点的 即可。
A) 指针域 B) 数据域 C) 结点域 D) 以上都不对
答案：A
分析：在线性链表中删除一个元素后，不需要移动表的数据元素，只需变化被删除元素所在结点的前一个结点的指针域即可。另外，因为可用栈是用于搜集计算机中所有的空闲结点，因此，当从线性链表中删除一个元素后，该元素的存储结点就变为空闲，应将该空闲结点送回到可用栈。
【试题35】在 中，只要指出表中任何一个结点的位置，就能够从它出发访问到表中其他所有的结点。
A) 线性单链表 B) 双向链表
C) 线性链表 D) 循环链表
答案：D
分析：在循环链表中，只要指出表中任何一个结点的位置，就能够从它出发访问到表中其他所有的结点，而线性单链表做不到这一点。
另外，因为在循环链表中设置了一个表头结点，因此，在任何情况下，循环链表中最少有一个结点存在，从而使空表与非空表的运算统一。
循环链表的插入和删除的措施与线性单链表基本相同。但由循环链表的特点能够看出，在对循环链表进行插入和删除的过程中，实现了空表与非空表的运算统一。
考点6：树与二叉树 ★★★★★
考点点拨：重要考查树的基本概念、二叉树及其基本性质、二叉树的存储结构、二叉树的遍历。

【试题36】设有二叉树如图1.3所示。

图1.3 二叉权
对此二叉树前序遍历的成果为 。
A) ZBTYCPXA B) ATBZXCYP
C) ZBTACYXP D) ATBZXCPY
答案：B
分析：二叉树的遍历是指不重复地访问二叉树中的所有结点。因为二叉树是一个非线性结构，因此，对二叉树的遍历要比遍历线性表复杂得多。遍历二叉树的措施实际上是要确定访问各结点的次序，以便不重不漏地访问到二叉树中的所有结点。在遍历二叉树的过程中，一般先遍历左子树，然后再遍历右子树。前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先遵照访问根结点，然后遍历左子树，最后遍历右子树。

理论链接：二叉树的遍历
在先左后右的标准下，依照访问根结点的次序，可将二叉树的遍历分为三种：前序遍历、中序遍历、后序遍历。下面分别简介这三种遍历的措施。
1. 前序遍历(DLR)
前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先遵照访问根结点，然后遍历左子树，最后遍历右子树。因此，前序遍历二叉树的过程是一个递归的过程。
下面是二叉树前序遍历的简单描述：
若二叉树为空，则结束返回。
否则：(1) 访问根结点；
(2) 前序遍历左子树；
(3) 前序遍历右子树。
在此尤其要注意的是，在遍历左右子树时仍然采取前序遍历的措施。
2. 中序遍历(LDR)
所谓中序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根结点，最后遍历右子树：并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。因此，中序遍历二叉树的过程也是一个递归的过程。
下面是二叉树中序遍历的简单描述：
若二叉树为空，则结束返回。
否则：(1) 中序遍历左子树；
(2) 访问根结点；
(3) 中序遍历左子树。
在此也要尤其注意的是，在遍历左右子树时仍然采取中序遍历的措施。
3. 后序遍历(LRD)
所谓后序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。因此，后序遍历二叉树的过程也是一个递归的过程。
下面是二叉树后序遍历的简单描述：
若二叉树为空，则结束返回。
否则：(1) 后序遍历左子树；
(2) 后序遍历右子树；
(3) 访问根结点。
在此也要尤其注意的是，在遍历左右子树时仍然采取后序遍历的措施。

【试题37】在深度为5的满二叉树中，叶子结点的个数为 。
A) 32 B) 31 C) 16 D) 15
答案：B
分析：所谓满二叉树是指这么的一个二叉树：除最后—层外，每一层上的所有结点都有两个子结点。这就是说，在满二叉树中，每一层上的结点数都达成最大值，即在满二叉树的第k层上有2k－1个结点，且深度为m的满二叉树有2m－1个结点。依照题意，深度为5的满二叉树中，叶子结点的个数为25－1=32－1=31个结点。
【试题38】设树T的度为4，其中度为1，2，3，4的结点个数分别为4，2，1，l。则T中的叶子结点数为 。
A) 8 B) 7 C) 6 D) 5
图1.4 试题38的树T结构图
答案：A
分析：依照题意，树T的结构如图1.4所示。
显然，T中的叶子结点数为8。

理论链接：树的度
在树结构中，一个结点所拥有的后继个数称为该结点的度。在树中，所有结点中的最大的度称为树的度。树在计算机中一般用多重链表表示。多重链表中的每个结点描述了树中对应结点的信息，而每个结点中的链域(即指针域)个数将随树中该结点的度而定。

【试题39】设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为 。
A) 12 B) 13 C) 14 D) 15
答案：B
分析：依照题意，能够得出有3个叶子结点，
图1.5 试题39的树T结构图
有8个度为1的结点树T的结构如图1.5所示
(满足条件的图尚有其他画法)。显然，
该二叉树中总的结点数为13。
【试题40】设一棵完全二叉树共有739个结点，则在该二叉树中有 个叶子结点。
答案：370
分析：所谓完全二叉树是指这么的二叉树：除最后一层外，每一层上的结点数均达成最大值；在最后一层上只缺乏右边的若干结点。更确切地说，假如从根结点起，对二叉树的结点自上而下、自左至右用自然数进