大数据结构c版课后习题解析汇报

word第 1 章绪论11.1 本章导学11.2 习题解析2第 2 章线性表92.1 本章导学92.2 习题解析10第 3 章栈和队列193.1 本章导学193.2 习题解析20第 4 章字符串和多维数组264.1 本章导学264.2 习题解析27第 5 章树和二叉树325.1 本章导学325.2 习题解析33第 6 章图436.1 本章导学436.2 习题解析44第 7 章查找技术567.1 本章导学567.2 习题解析57第 8 章排序技术678.1 本章导学678.2 习题解析68第 9 章索引技术789.1 本章导学789.2 习题解析7881 / 83第 1 章 绪 论1.1 本章导学1. 知识结构图 本章的知识结构如图1-1所示，其中第二层的椭圆代表本章的学习主线。数据数据元素数据结构抽象数据类型逻辑结构数据结构的分类存储结构常用存储方法算法算法特性评价算法描述算法问题规模基本语句时间复杂度大O记号图1-1 知识结构图绪 论数据结构算 法基本概念逻辑结构存储结构基本概念算法分析关 系2. 学习要点对本章的学习要从两条主线出发，一条主线是数据结构，包括数据结构的相关概念及含义，另一条主线是算法，包括算法的相关概念、描述方法以及时间复杂度的分析方法。在学习数据结构时要抓住两个方面：逻辑结构和存储结构，并注意把握二者之间的关系。在学习算法时，要以算法的概念和特性为基本点，并在以后的学习中注意提高算法设计的能力。对于算法时间性能的分析，要将注意力集中在增长率上，即基本语句执行次数的数量级，在设计算法时，养成分析算法时间性能的习惯，进而有效地改进算法的效率。1.2 习题解析1. 填空（1）（ ）是数据的基本单位，在计算机程序常作为一个整体进行考虑和处理。【解答】数据元素（2）（ ）是数据的最小单位，（ ）是讨论数据结构时涉及的最小数据单位。【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。（3）从逻辑关系上讲，数据结构主要分为（ ）、（ ）、（ ）和（ ）。【解答】集合，线性结构，树结构、图结构（4）数据的存储结构主要有（ ）和（ ）两种基本方法，不论哪种存储结构，都要存储两方面的容：（ ）和（ ）。【解答】顺序存储结构，存储结构，数据元素，数据元素之间的关系（5）算法具有五个特性，分别是（ ）、（ ）、（ ）、（ ）、（ ）。【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性（6）算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四种，其中，（ ）被称为算法语言。【解答】自然语言，程序设计语言，流程图，伪代码，伪代码（7）在一般情况下，一个算法的时间复杂度是（ ）的函数。【解答】问题规模（8）设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（ ），若为2n*log25n + 8n，则表示成数量级的形式为（ ）。【解答】(1)，(nlog2n)【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。2. 选择题（1）顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，存储结构中的数据元素之间的逻辑关系是由（ ）表示的。A 线性结构 B 非线性结构 C 存储位置 D 指针【解答】C，D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。（2）假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承遗产。则表示该遗产继承关系的最合适的数据结构应该是（ ）。A 树 B 图 C 线性表 D 集合【解答】B【分析】将丈夫、妻子和子女分别作为数据元素，根据继承关系画出逻辑结构图如图1-2丈夫妻子子女n子女1图1-2 遗产继承逻辑结构图所示。（3）计算机所处理的数据一般具有某种在联系，这是指（ ）。A 数据和数据之间存在某种关系 B 元素和元素之间存在某种关系C 元素部具有某种结构 D 数据项和数据项之间存在某种关系【解答】B【分析】数据结构是指相互之间存在一定关系的数据元素的集合，数据元素是讨论数据结构时涉及的最小数据单位，元素部各数据项一般不予考虑。（4）对于数据结构的描述，下列说法中不正确的是（ ）。A 相同的逻辑结构对应的存储结构也必相同B 数据结构由逻辑结构、存储结构和基本操作三方面组成C 对数据结构基本操作的实现与存储结构有关D 数据的存储结构是数据的逻辑结构的机实现【解答】A【分析】相同的逻辑结构可以用不同的存储结构实现，一般来说，在不同的存储结构下基本操作的实现是不同的，例如线性表可以顺序存储也可以存储，在顺序存储和存储结构下插入操作的实现截然不同。（5）可以用（ ）定义一个完整的数据结构。A 数据元素 B 数据对象 C 数据关系 D 抽象数据类型【解答】D【分析】抽象数据类型是一个数据结构以及定义在该结构上的一组操作的总称。（6）算法指的是（ ）。A 对特定问题求解步骤的一种描述，是指令的有限序列。B 计算机程序 C 解决问题的计算方法 D 数据处理【解答】A【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。所以，只有A是算法的准确定义。（7）下面（ ）不是算法所必须具备的特性。A 有穷性 B 确切性 C 高效性 D 可行性【解答】C【分析】高效性是好算法应具备的特性。（8）算法分析的目的是（ ），算法分析的两个主要方面是（ ）。A 找出数据结构的合理性 B 研究算法中输入和输出的关系C 分析算法的效率以求改进 D 分析算法的易读性和文档性E 空间性能和时间性能 F 正确性和简明性G 可读性和文档性 H 数据复杂性和程序复杂性【解答】C，E3. 判断题 算法的时间复杂度都要通过算法中的基本语句的执行次数来确定。【解答】错。时间复杂度要通过算法中基本语句执行次数的数量级来确定。 每种数据结构都具备三个基本操作：插入、删除和查找。【解答】错。如数组就没有插入和删除操作。此题注意是每种数据结构。 所谓数据的逻辑结构指的是数据之间的逻辑关系。【解答】错。是数据之间的逻辑关系的整体。 逻辑结构与数据元素本身的容和形式无关。【解答】对。因此逻辑结构是数据组织的主要方面。 基于某种逻辑结构之上的基本操作，其实现是唯一的。【解答】错。基本操作的实现是基于某种存储结构设计的，因而不是唯一的。4. 分析以下各程序段，并用大O记号表示其执行时间。 i = 1; k = 0; while (i <= n) k = k + 10 * i;i+; i = 1; k = 0; do k = k + 10 * i;i+; while (i <= n); y = 0; while (y + 1) *(y + 1) <= n) y = y + 1; i = 1; j = 0;while (i + j <= n) if (i > j) j+; else i+; for (i = 1; i <= n; i+) for (j = 1; j <= i; j+) for (k = 1; k <= j; k+) x+;【解答】 基本语句是k=k+10*i，共执行了n-2次，所以T(n)=O(n)。 基本语句是k=k+10*i，共执行了n次，所以T(n)=O(n)。 分析条件语句，每循环一次，i+j整体加1，共循环n次，所以T(n)=O(n)。 设循环体共执行T(n)次，每循环一次，循环变量y加1，最终T(n)=y，即：(T(n)+1)2n，所以T(n)=O(n1/2)。x+是基本语句，所以 5解答下列问题（1）设有数据结构（D，R），其中D = 1, 2, 3, 4, 5, 6，R = (1, 2),(2, 3),(2, 4),(3, 4),(3, 5),(3, 6),(4, 5),(4, 6)。试画出其逻辑结构图并指出属于何种结构。142563图1-3 逻辑结构图【解答】其逻辑结构图如图1-3所示，它是一种图结构。（2）为整数定义一个抽象数据类型，包含整数的常见运算，每个运算对应一个基本操作，每个基本操作的接口需定义前置条件、输入、功能、输出和后置条件。【解答】整数的抽象数据类型定义如下： ADT integer Data 整数：可以是正整数(1, 2, 3, )、负整数(-1, -2, -3, )和零 Operation Constructor 前置条件：整数a不存在 输入：一个整数b 功能：构造一个与输入值相同的整数 输出：无 后置条件：整数a具有输入的值 Set 前置条件：存在一个整数a 输入：一个整数b 功能：修改整数a的值，使之与输入的整数值相同 输出：无 后置条件：整数a的值发生改变 Add 前置条件：存在一个整数a 输入：一个整数b 功能：将整数a与输入的整数b相加 输出：相加后的结果 后置条件：整数a的值发生改变 Sub 前置条件：存在一个整数a 输入：一个整数b 功能：将整数a与输入的整数b相减 输出：相减的结果 后置条件：整数a的值发生改变 Multi 前置条件：存在一个整数a 输入：一个整数b 功能：将整数a与输入的整数b相乘 输出：相乘的结果 后置条件：整数a的值发生改变 Div 前置条件：存在一个整数a 输入：一个整数b 功能：将整数a与输入的整数b相除 输出：若整数b为零，则抛出除零异常，否则输出相除的结果 后置条件：整数a的值发生改变 Mod 前置条件：存在一个整数a 输入：一个整数b 功能：求当前整数与输入整数的模，即正的余数 输出：若整数b为零，则抛出除零异常，否则输出取模的结果 后置条件：整数a的值发生改变 Equal 前置条件：存在一个整数a 输入：一个整数b 功能：判断整数a与输入的整数b是否相等 输出：若相等返回1，否则返回0 后置条件：整数a的值不发生改变endADT（3）求多项式A(x)的算法可根据下列两个公式之一来设计：A(x)=anxn+an-1xn-1+a1x+a0A(x)=(anx+an-1)x+a1)x)+a0根据算法的时间复杂度分析比较这两种算法的优劣。【解答】第二种算法的时间性能要好些。第一种算法需执行大量的乘法运算，而第二种算法进行了优化，减少了不必要的乘法运算。（4）选择和评价数据结构的标准与方法是什么？【解答】首先，对给定的实际问题可以建立不同的数据结构；其次，对于给定的数据结构，可以选择不同的存储实现，即采用不同的存储结构；再次，在给定数据结构和存储结构的条件下，对同一基本操作可以设计出不同算法。因此，数据的逻辑结构、存储结构和操作（特别是基本操作）的实现这三者是密切相关的。一般地，在建立数据结构时应该考虑以下三个方面： 确定表示问题所需的数据及其特性； 确定必须支持的基本操作，并度量每种操作所受的时、空资源限制，某些重要的操作，例如查找、插入和删除的资源限制通常决定了数据结构的选择； 选择（或设计）最接近这些开销的数据结构。6. 算法设计（要求：用伪代码和C+描述两种方法描述算法，并分析时间复杂度） 对一个整型数组An设计一个排序算法。【解答】下面是简单选择排序算法的伪代码描述。 1. 对n个记录进行n-1趟简单选择排序： 1.1 在无序区i，n-1中选取最小记录，设其下标为index； 1.2 将最小记录与第i个记录交换； 下面是简单选择排序算法的C+描述。void SelectSort(int r , int n) for (i = 0; i < n - 1; i+) /对n个记录进行n-1趟简单选择排序 index = i; for (j = i + 1; j < n; j+) /在无序区中选取最小记录 if (rj < rindex) index = j; if (index != i) ririndex; /交换元素 简单选择排序算法SelectSort 分析算法，有两层嵌套的for循环，所以，。 找出整型数组An中元素的最大值和次最大值。【解答】算法的伪代码描述如下： 1. 将前两个元素进行比较，较大者放到max中，较小者放到nmax中； 2. 从第3个元素开始直到最后一个元素依次取元素Ai，执行下列操作： 2.1 如果Ai>max，则Ai为最大值，原来的最大值为次最大值；2.2 否则，如果Ai>nmax，则最大值不变，Ai为次最大值；3. 输出最大值max，次最大值nmax； 算法的C+描述如下：void Max_NextMax(int A , int n, int & max, int & nmax)if (A0 >= A1) max = A0; nmax = A1;else max = A1; nmax = A0; for (i = 2; i < n; i+) if (Ai >= max) nmax = max; max = Ai; else if (Ai > nmax) nmax = Ai; cout<<"最大值为："<<max<<"n次最大值为："<<nmax<<endl;最大值和次最大值算法Max_NextMax 分析算法，只有一层循环，共执行n-2次，所以，T(n)=O(n)。第 2 章 线性表2.1 本章导学1. 知识结构图 本章的知识结构如图2-1所示，其中第二层的椭圆代表本章的学习主线。线 性 表逻辑结构存储结构基本概念抽象数据类型定义线性表定义逻辑特征ADT定义基本操作顺序存储结构存储结构其他存储方法顺序表类定义基本操作的实现及时间性能单链表循环链表双链表比 较静态链表间接寻址图2-1 知识结构图2. 学习要点本章虽然讨论的是线性表，但涉及的许多问题都具有一定的普遍性，因此，本章是本课程的重点之一，也是其它后续章节的重要基础。对于本章的学习要从两条明线、一条暗线出发。两条明线是线性表的逻辑结构和存储结构，一条暗线是算法（即基本操作的实现）。注意线性表的ADT定义、顺序表类定义和单链表类定义三者之间的关系；注意在不同的存储结构下，相同操作的不同实现算法；注意对顺序表和链表从时间性能和空间性能等方面进行综合对比，在实际应用中能为线性表选择或设计合适的存储结构。2.2 习题解析1. 填空 在顺序表中，等概率情况下，插入和删除一个元素平均需移动（ ）个元素，具体移动元素的个数与（ ）和（ ）有关。【解答】表长的一半，表长，该元素在表中的位置 顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（ ）。【解答】108【分析】第5个元素的存储地址=第1个元素的存储地址(51)×2=108 设单链表中指针p指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（ ）。【解答】p->next=(p->next)->next 单链表中设置头结点的作用是（ ）。【解答】为了运算方便【分析】例如在插入和删除操作时不必对表头的情况进行特殊处理。 非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（ ）。【解答】p->next=head【分析】如图2-8所示。heada1a2an p图2-8 尾结点p与头指针head的关系示意图 在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是（ ）；删除开始结点的操作序列为（ ）。【解答】s->next=rear->next;rear->next=s;rear =s; q=rear->next->next; rear->next->next=q->next; delete q;【分析】操作示意图如图2-9所示：a1a2an rear sq图2-9 带尾指针的循环链表中插入和删除操作示意图rear 一个具有n个结点的单链表，在指针p所指结点后插入一个新结点的时间复杂度为（ ）；在给定值为x的结点后插入一个新结点的时间复杂度为（ ）。【解答】(1)，(n)【分析】在p所指结点后插入一个新结点只需修改指针，所以时间复杂度为(1)；而在给定值为x的结点后插入一个新结点需要先查找值为x的结点，所以时间复杂度为(n)。 可由一个尾指针唯一确定的链表有（ ）、（ ）、（ ）。【解答】循环链表，循环双链表，双链表2. 选择题 线性表的顺序存储结构是一种（ ）的存储结构，线性表的存储结构是一种（ ）的存储结构。A 随机存取 B 顺序存取 C 索引存取 D 散列存取【解答】A，B【分析】参见2.2.1。 线性表采用存储时，其地址（ ）。A 必须是连续的 B 部分地址必须是连续的C 一定是不连续的 D 连续与否均可以【解答】D【分析】线性表的存储是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以连续，也可以不连续，甚至可以零散分布在存中任意位置。 单循环链表的主要优点是（ ）。A 不再需要头指针了 B 从表中任一结点出发都能扫描到整个链表；C 已知某个结点的位置后，能够容易找到它的直接前趋；D 在进行插入、删除操作时，能更好地保证链表不断开。【解答】B 链表不具有的特点是（ ）。A 可随机访问任一元素 B 插入、删除不需要移动元素C 不必事先估计存储空间 D 所需空间与线性表长度成正比【解答】A 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋，则采用（ ）存储方法最节省时间。A 顺序表 B 单链表 C 双链表 D 单循环链表【解答】A【分析】线性表中最常用的操作是取第i个元素，所以，应选择随机存取结构即顺序表，同时在顺序表中查找第i个元素的前趋也很方便。单链表和单循环链表既不能实现随机存取，查找第i个元素的前趋也不方便，双链表虽然能快速查找第i个元素的前趋，但不能实现随机存取。 若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（ ）存储方法最节省时间。A 单链表 B 带头指针的单循环链表 C 双链表D 带尾指针的单循环链表【解答】D【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址，所以，单链表、带头指针的单循环链表、双链表都不合适，考虑在带尾指针的单循环链表中删除第一个结点，其时间性能是O(1)，所以，答案是D 。 若链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（ ）存储方法最节省运算时间。A 单链表 B 循环双链表 C单循环链表 D 带尾指针的单循环链表【解答】B【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址，所以，单链表、单循环链表都不合适，删除最后一个结点需要知道终端结点的前驱结点的地址，所以，带尾指针的单循环链表不合适，而循环双链表满足条件。 在具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ ）。A O(1)B O(n)C O(n2)D O(nlog2n)【解答】B【分析】首先应顺序查找新结点在单链表中的位置。 对于n个元素组成的线性表，建立一个有序单链表的时间复杂度是（ ）。A O(1)B O(n)C O(n2)D O(nlog2n)【解答】C【分析】该算法需要将n个元素依次插入到有序单链表中，而插入每个元素需O(n)。 使用双链表存储线性表，其优点是可以（ ）。A 提高查找速度 B 更方便数据的插入和删除C 节约存储空间 D 很快回收存储空间【解答】B【分析】在链表中一般只能进行顺序查找，所以，双链表并不能提高查找速度，因为双链表中有两个指针域，显然不能节约存储空间，对于动态存储分配，回收存储空间的速度是一样的。由于双链表具有对称性，所以，其插入和删除操作更加方便。 在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行（ ）操作。A s->next=p->next; p->next=s; B q->next=s; s->next=p;C p->next=s->next; s->next=p; D p->next=s; s->next=q;【解答】B【分析】注意此题是在q和p之间插入新结点，所以，不用考虑修改指针的顺序。 在循环双链表的p所指结点后插入s所指结点的操作是（ ）。A p->next=s;s->prior=p; p->next->prior=s; s->next=p->next; B p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;C s->prior=p;s->next=p->next;p->next=s; p->next->prior=s;Ds->prior=p; s->next=p->next;p->next->prior=s;p->next=s【解答】D【分析】在链表中，对指针的修改必须保持线性表的逻辑关系，否则，将违背线性表的逻辑特征，图2-10给出备选答案C和D的图解。(a) 备选答案C操作示意图(第4步指针修改无法进行) (b) 备选答案D操作示意图 图2-10 双链表插入操作修改指针操作示意图sai-1aixpsai-1aixp（13）用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中某结点，则j后移的操作语句为（ ）。A j=rj.next B j=j+1 C j=j->next D j=rj-> next【解答】A【分析】注意next是数组下标，因此排除C和D，对于备选答案B，假设工作指针j指向某结点p，则j+1不一定指向结点p的后继结点。（14）设线性表有n个元素，以下操作中，（ ）在顺序表上实现比在链表上实现的效率更高。A 输出第i（1in）个元素值 B 交换第1个和第2个元素的值C 顺序输出所有n个元素 D 查找与给定值x相等的元素在线性表中的序号【解答】A【分析】在顺序表上输出第i（1in）个元素值需要O(1)时间，在链表上输出第i（1in）个元素值需要O(n)时间；在顺序表上和链表上交换第1个和第2个元素的值都需要O(1)时间；在顺序表上和链表上顺序输出所有n个元素都需要O(n)时间；在顺序表上和链表上查找与给定值x相等的元素都需要进行顺序查找，需要O(n)时间。3. 判断题 线性表的逻辑顺序和存储顺序总是一致的。【解答】错。顺序表的逻辑顺序和存储顺序一致，链表的逻辑顺序和存储顺序不一定一致。 线性表的顺序存储结构优于存储结构。【解答】错。两种存储结构各有优缺点。 设p，q是指针，若p=q，则*p=*q。【解答】错。p=q只能表示p和q指向同一起始地址，而所指类型则不一定相同。 线性结构的基本特征是：每个元素有且仅有一个直接前驱和一个直接后继。【解答】错。每个元素最多只有一个直接前驱和一个直接后继，第一个元素没有前驱，最后一个元素没有后继。 在单链表中，要取得某个元素，只要知道该元素所在结点的地址即可，因此单链表是随机存取结构。【解答】错。要找到该结点的地址，必须从头指针开始查找，所以单链表是顺序存取结构。4请说明顺序表和单链表各有何优缺点，并分析下列情况下，采用何种存储结构更好些。 若线性表的总长度基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素。 如果n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化。 描述一个城市的设计和规划。【解答】顺序表的优点： 无需为表示表中元素之间的逻辑关系而增加额外的存储空间； 可以快速地存取表中任一位置的元素（即随机存取）。顺序表的缺点： 插入和删除操作需移动大量元素； 表的容量难以确定； 造成存储空间的“碎片”。单链表的优点： 不必事先知道线性表的长度； 插入和删除元素时只需修改指针，不用移动元素。单链表的缺点： 指针的结构性开销； 存取表中任意元素不方便，只能进行顺序存取。 应选用顺序存储结构。因为顺序表是随机存取结构，单链表是顺序存取结构。本题很少进行插入和删除操作，所以空间变化不大，且需要快速存取，所以应选用顺序存储结构。 应选用存储结构。链表容易实现表容量的扩充，适合表的长度动态发生变化。 应选用存储结构。因为一个城市的设计和规划涉及活动很多，需要经常修改、扩充和删除各种信息，才能适应不断发展的需要。而顺序表的插入、删除的效率低，故不合适。5算法设计 设计一个时间复杂度为(n)的算法，实现将数组An中所有元素循环左移k个位置。【解答】算法思想请参见主教材第一章思想火花。下面给出具体算法。void Converse(int A , int n, int k) Reverse(A, 0, k-1); Reverse(A, k, n-1); Reverse(A, 0, n-1);void Reverse(int A , int from, int to) /将数组A中元素从from到to逆置 for (i = 0; i < (to from + 1)/2; i+)Afrom + iAto - i; /交换元素 循环左移算法Converse 分析算法，第一次调用Reverse函数的时间复杂度为O(k)，第二次调用Reverse函数的时间复杂度为O(n-k)，第三次调用Reverse函数的时间复杂度为O(n)，所以，总的时间复杂度为O(n)。 已知数组An中的元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为(n)。【解答】从数组的两端向中间比较，设置两个变量i和j，初始时i=0，j=n-1，若Ai为偶数并且Aj为奇数，则将Ai与Aj交换。具体算法如下： void Adjust(int A , n) i = 0; j = n - 1; while (i < j) while (Ai % 2 != 0) i+; while (Aj % 2 = 0) j- if (i < j) AiAj; 数组奇偶调整算法Adjust 分析算法，两层循环将数组扫描一遍，所以，时间复杂度为(n)。 试编写在无头结点的单链表上实现线性表的插入操作的算法，并和带头结点的单链表上的插入操作的实现进行比较。【解答】参见2.2.3。 试分别以顺序表和单链表作存储结构，各写一实现线性表就地逆置的算法。【解答】顺序表的逆置，即是将对称元素交换，设顺序表的长度为length，则将表中第i个元素与第length-i-1个元素相交换。具体算法如下： template <class T> void Reverse(T data , int length) for (i = 0; i <= length/2; i+) temp = datai; datai = datalength i - 1; datalength i - 1 = temp;顺序表逆置算法Reverse单链表的逆置请参见2.2.4算法2-4和算法2-6。 假设在长度大于1的循环链表中，即无头结点也无头指针，s为指向链表中某个结点的指针，试编写算法删除结点s的前趋结点。【解答】利用单循环链表的特点，通过指针s可找到其前驱结点r以及r的前驱结点p，然后将结点r删除，如图2-11所示，具体算法如下：template <class T>void Del(Node<T> *s) p = s; /工作指针p初始化，查找s的前驱结点的前驱结点，用p指示 while (p->next->next != s) p = p->next; r = p->next; /r为p的前驱结点，q为r的前驱结点 p->next = s; /删除r所指结点 delete r; 循环链表删除算法Dela1a2an 图2-11 删除结点s的前驱结点操作示意图a3a4spr 已知一单链表中的数据元素含有三类字符：字母、数字和其他字符。试编写算法，构造三个循环链表，使每个循环链表中只含同一类字符。【解答】在单链表A中依次取元素，若取出的元素是字母，把它插入到字母链表B 中，若取出的元素是数字，则把它插入到数字链表D中，直到链表的尾部，这样表B，D，A中分别存放字母、数字和其他字符。具体算法如下：template <class T>void Adjust(Node<T> *A, Node<int> *D, Node<char> *B) D = new Node<int> D->next = D; /创建空循环链表D，存放数字 B = new Node<char> B->next = B; /创建空循环链表B，存放字符 p = A; q = p->next; /工作指针q初始化 while (q != NULL) if ('A'<=q->data)&&(q->data>='Z')|('a' <=q->data)&&(q->data>='z') p->next = q->next; q->next = B->next; B->next = q; /采用头插法插在循环链表B的头结点的后面 else if ('0'<=q->data)&&(q->data>='9') p->next = q->next; q->next = D->next; D->next = q; /采用头插法插在循环链表D的头结点的后面 else p = q; q = p->next;p->next = A; R = A; /将链表A构造为循环链表，为除字母和数字的其他字符单链表拆分算法Adjust 设单链表以非递减有序排列，设计算法实现在单链表中删去值相同的多余结点。【解答】从头到尾扫描单链表，若当前结点的元素值与后继结点的元素值不相等，则指针后移；否则删除该后继结点。具体算法如下：void Purge(Node<T> *first) p = first->next; while (p->next != NULL) if (p->data = p->next->data) q = p->next; p->next = q->next; delete q; else p = p->next; 单链表删除相同值算法Purge 判断带头结点的双循环链表是否对称。【解答】设工作指针p和q分别指向循环双链表的开始结点和终端结点，若结点p和结点q的数据域相等，则工作指针p后移，工作指针q前移，直到指针p和指针q指向同一结点（循环双链表中结点个数为奇数），或结点q成为结点p的前驱（循环双链表中结点个数为偶数）。如图2-12所示。a1an-1anfirstpq图2-12 判断循环双链表对称的操作示意图template <class T>struct DulNode T data; DulNode<T> *prior, *next;template <class T>bool Equal (DulNode<T> *first) p = first->next; q = first->prior; while (p != q && p->prior != q) if (p->data = q->data) p = p->next; /工作指针p后移 q = q->prior; /工作指针q前移 else return 0; return 1; 判断双链表对称算法Equal第 3 章 栈和队列3.1 本章导学1. 知识结构图 本章的知识结构如图3-1所示，其中第二层的椭圆表示本章的学习主线。特殊线性表 栈队 列栈的定义操作特性ADT定义队列定义操作特性ADT定义顺序栈链栈循环队列链队列逻辑结构存储结构逻辑结构存储结构比 较图3-1 知识结构图比较比较基本操作的实现时间性能基本操作的实现时间性能2. 学习要点对于本章的学习要从两条主线出发，一条主线是栈，另一条主线是队列，要以栈和队列的操作特性为切入点，并注意将栈和队列进行对比。这部分有较多的经典应用，如汉诺塔问题、迷宫问题、八皇后问题、车厢重排问题、开关盒布线、舞伴问题等等。要有意识地接触这些经典问题，深刻理解栈和队列在程序设计中的重要作用，在实践中培养数据结构应用能力和算法设计能力。3.2 习题解析1. 填空 设有一个空栈，栈顶指针为1000H，每个元素需要1个单位的存储空间，则执行push、push、pop、push、pop、push、push后，栈顶指针为（ ）。【解答】1003H 栈结构通常采用的两种存储结构是（ ）；其判定栈空的条件分别是（ ），判定栈满的条件分别是（ ）。【解答】顺序存储结构和存储结构（或顺序栈和链栈），栈顶指针top= -1和top=NULL，栈顶指针top等于数组的长度和存无可用空间（ ）可作为实现递归函数调用的一种数据结构。【解答】栈【分析】递归函数的调用和返回正好符合后进先出性。 表达式a*(b+c)-d的后缀表达式是（ ）。【解答】abc+*d-【分析】将中缀表达式变为后缀表达式有一个技巧：将操作数依次写下来，再将算符插在它的两个操作数的后面。 栈和队列是两种特殊的线性表，栈的操作特性是（ ），队列的操作特性是（ ），栈和队列的主要区别在于（ ）。【解答】后进先出，先进先出，对插入和删除操作限定的位置不同 循环队列的引入是为了克服（ ）。【解答】假溢出 数组Qn用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素的位置，计算队列中元素个数的公式为（ ）。【解答】（rear-front+n）% n【分析】也可以是（rear-front）% n，但rear-front的结果可能是负整数，而对一个负整数求模，其结果在不同的编译器环境下可能会有所不同。用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是（ ）和（ ）。【解答】(1)，(n)【分析】在带头指针的循环链表中，出队即是删除开始结点，这只需修改相应指针；入队即是在终端结点的后面插入一个结点，这需要从头指针开始查找终端结点的地址。2. 选择题（1）一个栈的入栈序列是1、2、3、4、5，则栈的不可能的输出序列是（ ）。A 54321 B 45321 C 43512 D 12345 【解答】C【分析】此题有一个技巧：在输出序列中任意元素后面不能出现比该元素小并且是升序（指的是元素的序号）的两个元素。（2）若一个栈的输入序列是1，2，3，n，输出序列的第一个元素是n，则第i个输出元素是（ ）。A 不确定 B n-i C n-i-1 D n-i+1【解答】D【分析】此时，输出序列一定是输入序列的逆序。（3）若一个栈的输入序列是1，2，3，n，其输出序列是p1, p2, , pn，若p1=3，则p2的值（ ）。A 一定是2 B 一定是1 C 不可能是1 D 以上都不对【解答】C【分析】由于p1=3，说明1, 2, 3均入栈后3出栈，此时可能将当前栈顶元素2出栈，也可以继续执行入栈操作，因此p2的值可能是2，但一定不能是1，因为1不是栈顶元素。 设计一个判别表达式中左右括号是否配对的算法，采用（ ）数据结构最佳。 A 顺序表 B 栈 C 队列 D 链表【解答】B【分析】每个右括号与它前面的最后一个没有匹配的左括号配对，因此具有后进先出性。 在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（ ）结构。 A 栈 B队列 C 数组 D线性表【解答】B【分析】先进入打印缓冲区的文件先被打印，因此具有先进先出性。 一个队列的入队顺序是1，2，3，4，则队列的输出顺序是（ ）。 A 4321 B 1234 C 1432 D 3241【解答】B【分析】队列的入队顺序和出队顺序总是一致的。 栈和队列的主要区别在于（ ）。 A 它们的逻辑结构不一样 B 它们的存储结构不一样C 所包含的运算不一样 D 插入、删除运算的限定不一样【解答】D【分析】栈和队列的逻辑结构都是线性的，都有顺序存储和存储，有可能包含的运算不一样，但不是主要区别，任何数据结构在针对具体问题时包含的运算都可能不同。 设数组Sn作为两个栈S1和S2的存储空间，对任何一个栈只有当Sn全满时才不能进行进栈操作。为这两个栈分配空间的最佳方案是（ ）。A S1的栈底位置为0，S2的栈底位置为n-1B S1的栈底位置为0，S2的栈底位置为n/2C S1的栈底位置为0，S2的栈底位置为nD S1的栈底位置为0，S2的栈底位置为1【解答】A【分析】两栈共享空间首先两个栈是相向增长的，栈底应该分别指向两个栈中的第一个元素的位置，并注意C+中的数组下标是从0开始的。（9）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（）。A 6 B 4 C 3 D 2【解答】C【分析】由于队列具有先进先出性，所以，此题中队列形同虚设，即出栈的顺序也是e2、e4、e3、e6、e5、e1。3. 判断题 有n个元素依次进栈，则出栈序列有(n-1)/2种。【解答】错。应该有种。 栈可以作为实现过程调用的一种数据结构。【解答】对。只要操作满足后进先出性，都可以采用栈作为辅助数据结构。 在栈满的情况下不能做进栈操作，否则将产生“上溢”。【解答】对。 在循环队列中，front指向队头元素的前一个位置，rear指向队尾元素的位置，则队满的条件是front=rear。【解答】错。这是队空的判定条件，在循环队列中要将队空和队满的判定条件区别开。 循环队列中至少有一个数组空间是空闲的。【解答】错。如果假定循环队列满足条件(rear + 1) % Maxsize = front时为队满，则循环队列中至少有一个数组空间是空闲的。4. 解答下列问题（1）设有一个栈，元素进栈的次序为A，B，C，D，E，能否得到如下出栈序列，若能，请写出操作序列，若不能，请说明原因。 C，E，A，B，D C，B，A，D，E【解答】不能，因为在C、E出栈的情况下，A一定在栈中，而且在B的下面，不可能先于B出栈。可以，设I为进栈操作，为入栈操作，则其操作序列为IIIOOOIOIO。（2）举例说明顺序队列的“假溢出”现象。rear E D C43210front图3-5 顺序队列的假溢出【解答】假设有一个顺序队列，如图3-5所示，队尾指针rear=4，队头指针front=1，如果再有元素入队，就会产生“上溢”，此时的“上溢”又称为“假溢出”，因为队列并不是真的溢出了，存储队列的数组中还有2个存储单元空闲，其下标分别为0和1。（3）在操作序列push(1)、push(2)、pop、push(5)、push(7)、pop、push(6)之后，栈顶元素和栈底元素分别是什么？（push(k)表示整数k入栈，pop表示栈顶元素出栈。）【解答】栈顶元素为6，栈底元素为1。其执行过程如图3-6所示。2 1 75 165 1(a) push(1)，push(2) (b) pop，push(5)，push(7) (c) pop，push(6)