数据结构习题解析与实验指导(txt+pdf+epub+mobi电子书下载)

作者：李冬梅 张琪

出版社：人民邮电出版社有限公司

格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT

数据结构习题解析与实验指导试读：

前言

本书的主教材《数据结构（C语言版）第2版》（ISBN978-7-115-37950-4）自2015年2月出版至今，已经多次印刷，印数10万余册，深受读者的好评。主教材中包含部分经典习题，但未给出相应解答，读者一直期待出版一本与教材配套的习题和实验指导。为了满足广大读者的迫切需求，编者总结多年“数据结构”课程的理论教学和实验教学、研究生入学考试的命题和试卷评阅的经验，并结合学生学习的实际需求，编写了本书。

全书由两篇组成。

第一篇分为8章，每章包括知识提要和习题解答，第二篇为实验指导。本书主要特色如下。（1）知识提要部分结构直观、考点清晰

每章首先以树状的知识导图形式给出本章的主要知识点，直观易读。然后以简洁的语言明确地指出了本章应该掌握的知识要点，对知识点进行了凝练和升华，以帮助学生梳理知识点。（2）习题解析部分内容全面、解答精细

围绕知识提要中要求掌握的重要知识点，结合研究生入学考试大纲的要求，在习题部分设计了选择题、应用题和算法设计题。每种题型首先给出的是主教材中的全部习题，然后按年代顺序依次给出了2009—2016年全国统考考研试题（在题号后面以【20**年第*题】形式标注）。为了保证覆盖每章的全部重要考点，某些章同时精选了其他一些经典试题。题目内容全面，解题思路清晰，解答过程详尽。对于算法设计题，首先以文字形式给出算法思想，再以类C语言形式给出相应的算法描述。（3）实验指导部分面向实际、模式创新

根据各章的教学重点和难点，结合了具体的实际应用，有针对性地编写了课程实验与课程设计题目。总计包括8个实验题目，涵盖了线性表、栈、串、树和图的基本数据结构和算法，最后还给出了1个综合性较强的课程设计题目，涵盖了重要的查找和排序算法。值得一提的是实验模式的创新，编者将实验教学中传统的以算法为主线的体系结构改为以问题为主线的体系结构，将传统的实验题目改编为ACM试题形式，通过具体问题描述给出实验题目。8个实验题目可在北京林业大学ACM在线评测系统（http://101.200.220.237）上完成。系统可自动评判，进而能够减轻教师的负担，系统可显示每道题目的提交情况，进而能够提高学生的积极性和主动性。实验题目已在北京林业大学信息学院2015级计算机类和信息专业类的教学中使用，测试数据已得到全面验证，准确无误，这种创新的实验模式得到了学生的一致认可和好评。

本书的编写宗旨是力图通过大量的典型习题解析和实验指导，帮助学生快速掌握并灵活运用数据结构的基本理论和算法，辅助教师讲授课程和指导学生实践。本书给出了包括主教材中所有习题在内的习题参考答案和解析，这些解答只供学习者作为参考，切不可完全依赖于它。如果在未做习题之前就先看答案，那就与编者的初衷背道而驰了，为此编者特将答案与题目相分离，希望学习者在深入思考后再查看解析。另外，有关算法设计题目的解答有多种，本书提供的解答并不一定是唯一的。学习者可以针对题目多加思考，设计出不同的程序，并加以比较和分析。

在本书的编写过程中，北京林业大学信息学院的研究生苏翔同学特此为全国统考考研试题的8道算法设计真题制作了算法动态演示，檀稳、刘建波、李东远、李鹭、庄婷婷、纪芳、闫楚依、赵培雯等同学参加了有关程序的调试工作和文字校对工作，张宇奇、韦立宁、孙涛同学参加了实验题目的改写工作，吴顶立同学在结合我们的习题学完数据结构之后，感触颇深，赋词一首，在此表示衷心的感谢！

因编者水平有限，书中错误在所难免，恳请读者批评指正。《青玉案-数据结构习题解析与实验指导》

数构习题创新作。

据精细，点脉络。

结取实验相指导。

构筑基础，通习算法，一朝终学成。

要点疑难全攻破。

多往线上解评测。

做题勿畏DEBUG。

题多练习，习多不惑，古来完全策。第一篇 习题

第1章 绪论

第2章 线性表

第3章 栈和队列

第4章 串、数组和广义表

第5章 树和二叉树

第6章 图

第7章 查找

第8章 排序第1章 绪论【知识导图】【学习目标】

1.掌握数据结构相关的基本概念，包括数据、数据元素、数据项、数据对象、数据结构等，明确数据元素和数据项的关系。

2.掌握数据结构所含两个层次（逻辑结构和存储结构）的具体含义及其相互关系。逻辑结构是从具体问题抽象出来的数学模型，它与数据的存储无关。存储结构是逻辑结构在计算机中的存储表示，其中，顺序存储结构借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述；链式存储结构无需占用一整块存储空间，通常借助程序设计语言的指针类型来描述，用指针来存放后继元素的存储地址。

3.算法是为了解决某类问题而规定的一个有限长的操作序列。理解算法五个特性的含义和明确算法优劣的四个评价标准。

4.算法分析的两个主要方面是分析算法的时间复杂度和空间复杂度，以考察算法的时间和空间效率。掌握算法时间复杂度和空间复杂度的分析方法。一般情况下，鉴于运算空间较为充足，故将算法的时间复杂度作为分析的重点。1.1 习题一、单项选择题

1.在数据结构中，从逻辑上可以把数据结构分成（　）。

A.动态结构和静态结构

B.紧凑结构和非紧凑结构

C.线性结构和非线性结构

D.内部结构和外部结构

2.与数据元素本身的形式、内容、相对位置、个数无关的是数据的（　）。

A.存储结构

B.存储实现

C.逻辑结构

D.运算实现

3.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（　）。

A.数据具有同一特点

B.不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致

C.每个数据元素都一样

D.数据元素所包含的数据项的个数要相等

4.以下说法正确的是（　）。

A.数据元素是数据的最小单位

B.数据项是数据的基本单位

C.数据结构是带有结构的各数据项的集合

D.一些表面上很不相同的数据可以有相同的逻辑结构

5.算法的时间复杂度取决于（　）。

A.问题的规模

B.待处理数据的初态

C.计算机的配置

D.A和B

6.以下数据结构中，（　）是非线性数据结构。

A.树

B.字符串

C.队列

D.栈

7.【2011年第1题】设n是描述问题规模的非负整数，下面程序段的时间复杂度是（　）。

A.O(logn)2

B.O(n)

C.O(nlogn)22

D.O(n)

8.【2014年第1题】下面程序段的时间复杂度是（　）。

A.O(logn)2

B.O(n)

C.O(nlogn)22

D.O(n)2

9.某算法的语句执行频度为（3n+nlogn+n+8），其时间复杂度2表示（　）。

A.O(n)

B.O(nlogn)22

C.O(n)

D.O(logn)2

10.以下程序段中语句“x++;”的语句频度为（　）。

A.

B.

C.

D.

11.以下程序段中语句“m++;”的语句频度为（　）。

A.n(n+1)

B.n

C.n+12

D.n

12.设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（　）。

A.O(n)

B.O(nlogn)2

C.O(1)2

D.O(n)

13.下面说法错误的是（　）。（1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复n杂度O(2)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界22（4）某算法的时间复杂度为O(n)，表明该算法的执行时间与n成正比

A.（1）

B.（1），（2）

C.（1），（4）

D.（3）

14.下面算法将一维数组a中的n个数逆序存放到原数组中，空间复杂度为（　）。

A.O(1)

B.O(n)

C.O(logn)22

D.O(n)

15.下面算法将一维数组a中的n个数逆序存放到原数组中，空间复杂度为（　）。

A.O(1)

B.O(n)

C.O(logn)22

D.O(n)

16.下列叙述中正确的是（　）。

A.一个算法的空间复杂度大，则其时间复杂度也必定大

B.一个算法的空间复杂度大，则其时间复杂度必定小

C.一个算法的时间复杂度大，则其空间复杂度必定小

D.上述三种说法都不对

17.数据结构是指（　）。

A.数据元素的组织形式

B.数据类型

C.数据存储结构

D.数据定义

18.树形结构是数据元素之间存在的一种（　）。

A.一对一关系

B.多对多关系

C.多对一关系

D.一对多关系

19.设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（　）。

A.线性结构

B.树结构

C.图

D.集合

20.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（　）。

A.存储结构

B.逻辑结构

C.链式存储结构

D.顺序存储结构

21.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（　）。

A.低

B.高

C.相同

D.不确定

22.顺序存储结构中数据元素之间的逻辑关系是由（　）表示的。

A.线性结构

B.非线性结构

C.存储位置

D.指针

23.链式存储结构中的数据元素之间的逻辑关系是由（　）表示的。

A.线性结构

B.非线性结构

C.存储位置

D.指针

24.以下与数据的存储结构有关的术语是（　）。

A.有序表

B.链表

C.有向图

D.树

25.抽象数据类型的三个组成部分分别为（　）。

A.数据对象、数据关系和基本操作

B.数据元素、逻辑结构和存储结构

C.数据项、数据元素和数据类型

D.数据元素、数据结构和数据类型

26.算法是（　）。

A.计算机程序

B.解决问题的计算方法

C.排序算法

D.解决问题的有限运算序列

27.下面关于算法说法错误的是（　）。

A.算法最终必须由计算机程序实现

B.为解决某问题的算法同为该问题编写的程序含义是相同的

C.算法的可行性是指指令不能有二义性

D.以上几个都是错误的

28.算法分析的两个主要方面是（　）。

A.空间复杂度和时间复杂度

B.正确性和简单性

C.可读性和文档性

D.数据复杂性和程序复杂性

29.对一个算法的评价，不包括如下（　）方面的内容。

A.健壮性和可读性

B.并行性

C.正确性

D.时空复杂度

30.通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量，以下解释错误的是（　）。

A.正确性算法应能正确地实现预定的功能

B.易读性算法应易于阅读和理解，以便调试、修改和扩充

C.健壮性指当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果

D.高效性即达到所需要的时间性能二、应用题

1.简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

2.试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。

3.简述逻辑结构的四种基本关系并画出它们的关系图。

4.存储结构由哪两种基本的存储方法实现？

5.试分析下列各算法的时间复杂度。（1）（2）（3）（4）（5）（6）1.2 答案及解析一.单项选择题

1.【答案】C【考点】逻辑结构【解析】

数据的逻辑结构是从逻辑关系上描述数据，可以看作从具体问题抽象出来的数学模型。根据数据元素之间关系的不同特性，逻辑结构通常划分为集合结构、线性结构、树结构和图结构。其中集合结构、树结构和图结构都属于非线性结构。因此，逻辑结构又可以分为线性结构与非线性结构两大类。

2.【答案】C【考点】逻辑结构【解析】

逻辑结构是从具体问题抽象出来的数学模型，从逻辑关系上描述数据，它与数据的存储无关，也就是说与数据本身的具体形式、内容、相对位置、个数都无关。

3.【答案】B【考点】数据元素与数据项的定义【解析】

数据项是组成数据元素的、有独立含义的、不可分割的最小单位，同一逻辑结构中的数据元素所包括数据项的个数要相同，且要求对应数据项的类型也要一致。例如，对于学生基本信息表这种线性表结构，其中数据元素为所有的学生，数据项为学号、姓名、性别等，这里学号、姓名、性别的数据类型必须一致。因此，选项B是正确的。

4.【答案】D【考点】数据、数据元素与数据项的定义【解析】

数据元素是数据的基本单位，数据项是数据的最小单位，数据结构是带有结构的各数据元素的集合。因此，选项A、B和C都是错误的。选项D是正确的，因为逻辑结构是从逻辑关系上描述数据，它与数据本身的具体形式无关。例如，学生表和图书表都可以看作线性结构，而学生数据和图书数据表面上是完全不同的数据。所以答案选择D。

5.【答案】D【考点】时间复杂度【解析】

算法的时间复杂度不仅与问题的规模有关，还与问题的其他因素有关。如某些排序的算法，其执行时间与待排序记录的初始状态有关。因此，有时会对算法有最好、最坏以及平均时间复杂度的评价。

6.【答案】A【考点】逻辑结构【解析】

非线性结构包括树结构、图结构和集合结构，而字符串、队列和栈都属于线性结构。

7.【答案】A【考点】时间复杂度【解析】k

设程序中基本语句“x=2*x;”执行的次数为k，执行k次时：x=2+1k+1。由循环结束条件x

8.【答案】C【考点】时间复杂度【解析】

内层循环条件j≤n与外层循环的变量无关，每次循环j自增1，每次内层循环都执行n次。所以内层循环的时间复杂度是O(n)。外层循环k条件为k≤n，增量定义为k*=2，可知循环次数为2≤n，即k≤logn。所2以外层循环的时间复杂度是O(logn)。对于嵌套循环，根据乘法规则2可知，该段程序的时间复杂度T(n)=T1(n)*T2(n)=O(n)*O(logn)=O(nlogn)。22

9.【答案】C【考点】时间复杂度【解析】

时间复杂度具体计算数量级时，可以遵循以下定理：mm-1

若f(n)=an+an+…+an+a是一个m次多项式，则mm-110mT(n)=O(n)。

上述定理说明，在计算算法时间复杂度时，可以忽略所有低次幂项和最高次幂项的系数。

10.【答案】D【考点】时间复杂度【解析】“x++;”的语句频度为:

11.【答案】A【考点】时间复杂度【解析】“m++;”的语句频度为:

12.【答案】C【考点】时间复杂度【解析】

读取第i个数组元素可以直接通过数组的下标定位，与n无关，因此平均时间复杂度为O(1)。

13.【答案】A【考点】时间复杂度和空间复杂度【解析】

原地工作指算法执行时所需要的辅助空间，其相对于输入量而言是个常数，语句(1)错误，其他语句的描述均正确，因此答案选择A。

14.【答案】B【考点】空间复杂度【解析】

算法的空间复杂度只需分析该算法在实现时所需要的辅助空间与问题规模n的函数关系。该算法需要另外借助一个大小为n的辅助数组b，所以其空间复杂度为O(n)。

15.【答案】A【考点】空间复杂度【解析】

该算法仅需要另外借助一个变量t，与问题规模n大小无关，所以其空间复杂度为O(1)。

16.【答案】D【考点】时间复杂度和空间复杂度【解析】

算法的时间复杂度和空间复杂度没有直接关系。

17.【答案】A【考点】数据结构【解析】

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。因此，数据结构是指数据元素的组织形式。

18.【答案】D【考点】逻辑结构【解析】

树结构中数据元素之间存在一对多的关系。

19.【答案】C【考点】逻辑结构【解析】数据元素之间存在多对多的关系，因此是图结构。

20.【答案】C【考点】存储结构【解析】

数据对象在计算机中的存储表示称为数据的存储结构，由于链式存储结构不要求逻辑上相邻的元素在物理位置上也相邻，因此无需占用一整块存储空间。为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址。

21.【答案】B【考点】存储结构【解析】

顺序存储结构要求所有的元素依次存放在一段连续的存储空间中，必须预先分配；而链式存储结构用一组任意的存储单元存储数据元素，这组存储单元可以是连续的，也可以是不连续的，不需要预先分配空间。因此，在存储空间使用的灵活性上，链式存储更高。

22.【答案】C【考点】存储结构【解析】

顺序存储结构借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，其逻辑关系由存储位置（即元素在数组中的下标）表示的。

23.【答案】D【考点】存储结构【解析】

链式存储结构无需占用一整块连续的存储空间。但为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址。所以链式存储结构通常借助程序设计语言的指针类型来描述。

24.【答案】B【考点】存储结构【解析】

有序表、有向图、树是与数据的逻辑结构有关的术语，不涉及数据的存储情况，只有B选项链表与数据的存储结构有关。

25.【答案】A【考点】抽象数据类型的定义【解析】

抽象数据类型一般指由用户定义的、表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称，具体包括三部分：数据对象、数据对象上关系的集合以及对数据对象的基本操作的集合。

26.【答案】D【考点】算法的定义及特性【解析】

算法是为了解决某类问题而规定的一个有限长的操作序列。

27.【答案】D【考点】算法的定义及特性【解析】

算法是为了解决某类问题而规定的一个有限长的操作序列，不是必须由计算机实现的，因此选项A是错误的。为解决某问题的算法与为该问题编写的程序含义是不同的，因为程序的编写与具体的语言有关，而算法与语言无关，所以选项B也是错误的。算法的可行性是指算法中的所有操作都可以通过已经实现的基本操作运算执行有限次来实现，显然，选项C错误。因此答案选择D。

28.【答案】A【考点】评价算法优劣的基本标准【解析】

时间高效是指算法设计合理，执行效率高，可以用时间复杂度来度量；空间高效是指算法占用存储容量合理，可以用空间复杂度来度量。时间复杂度和空间复杂度是衡量算法的两个主要指标。

29.【答案】B【考点】评价算法优劣的基本标准【解析】

一个算法优劣应该从以下几方面来评价：正确性、可读性、健壮性和高效性。选项D中的“时空复杂度”属于高效性评价的指标，因此答案选择B。

30.【答案】D【考点】评价算法优劣的基本标准【解析】

高效性包括时间和空间两个方面，而不应该仅指时间性能高效。二、应用题

1.解答

数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录、树中棋盘的一个格局（状态）、图中的一个顶点等。

数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如，整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作从具体问题抽象出来的数学模型。

存储结构：是数据对象在计算机中的存储表示，也称为物理结构。

抽象数据类型：是由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。

2.解答

例如，有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生的基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。对于整个表来说，只有一个开始结点（它的前面无记录）和一个终端结点（它的后面无记录），其他的结点则各有一个也只有一个直接前驱和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。

这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元（如用数组表示）来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。

即相同的逻辑结构，可以对应不同的存储结构。

3.解答

数据的逻辑结构有两个要素：一是数据元素；二是关系。其中，关系是指数据元素间的逻辑关系。根据数据元素之间关系的不同特性，通常有四类基本结构关系，如图1.1所示。它们的复杂程度依次递进。图1.1 四类基本逻辑结构关系（1）集合结构

数据元素之间除了“属于同一集合”的关系外，别无其他关系。例如，确定一名学生是否为班级成员，只需将班级看作一个集合结构。（2）线性结构

数据元素之间存在一对一的关系。例如，将学生信息数据按照其入学报到的时间先后顺序进行排列，将组成一个线性结构。（3）树结构

数据元素之间存在一对多的关系。例如，在班级的管理体系中，班长管理多个组长，每位组长管理多名组员，从而构成树形结构。（4）图结构或网状结构

数据元素之间存在多对多的关系。例如，多位同学之间的朋友关系，任何两位同学都可以是朋友，从而构成图形结构或网状结构。

其中，集合结构、树结构和图结构都属于非线性结构。

4.解答（1）顺序存储结构

顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述。（2）链式存储结构

顺序存储结构要求所有的元素依次存放在一段连续的存储空间中，而链式存储结构无需占用一整块存储空间，但为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址。所以链式存储结构通常借助程序设计语言的指针类型来描述。

5.解答（1）O(1)

程序中基本语句“y--;”或“x++;”执行的次数是由x和y决定的，而x和y都是一个常数。所以，T(n)=O(1)。（2）O(n×m)

由于程序为嵌套循环，外层循环的执行次数为n，内层循环的执行次数为m。所以，T(n)=O(n×m)。2（3）O(n)

由于程序为嵌套循环，外层循环的执行次数为n，内层循环的执2行次数也为n。所以，T(n)=O(n)。（4）O(logn)3f(n)

设基本语句“i=i*3;”的执行次数为f(n)，则有：3≤n。因此，T(n)=O(logn)。32（5）O(n)

基本语句“x++;”的执行次数为：n-1+n-2+…+1=n(n-1)/2。因此，2T(n)=O(n)。（6）O()2

设基本语句“y++;”的执行次数为f(n)，则x≥(f(n)+1)，又由于x=n，所以f(n)≤-1，即T(n)=O()。第2章 线性表【知识导图】【学习目标】

1.线性表的顺序存储结构即顺序表是一种随机存取结构，可借助数组来表示。给定数组的下标，便可以存取相应的元素。而线性表的链式存储结构即链表是一种顺序存取结构，链表结点的存取都要从头指针开始，顺链而行。要求能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合，明确它们各自的优缺点。

2.掌握顺序表和链表的查找、插入和删除以及链表的创建（前插和后插）等基本操作，并能够设计出线性表应用的常用算法，比如线性表的合并、有序表的合并等算法。

3.除了单链表外，掌握不同形式链表（循环链表和双向链表）的特点、插入和删除等基本操作的实现及其应用场合。2.1 习题一、单项选择题

1.顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（　）。

A.110

B.108

C.100

D.120

2.在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（　）。

A.访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）

B.在第i个结点后插入一个新结点（1≤i≤n）

C.删除第i个结点（1≤i≤n）

D.将n个结点从小到大排序

3.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（　）。

A.8

B.63.5

C.63

D.7

4.链接存储的存储结构所占存储空间（　）。

A.分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针

B.只有一部分，存放结点值

C.只有一部分，存储表示结点间关系的指针

D.分两部分，一部分存放结点值，另一部分存放结点所占单元数

5.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（　）。

A.必须是连续的

B.部分地址必须是连续的

C.一定是不连续的

D.连续或不连续都可以

6.线性表L在（　）情况下适用于使用链式结构实现。

A.需经常修改L中的结点值

B.需不断对L进行删除插入

C.L中含有大量的结点

D.L中结点结构复杂

7.单链表的存储密度（　）。

A.大于1

B.等于1

C.小于1

D.不能确定

8.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（　）。

A.n

B.2n-1

C.2n

D.n-1

9.在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动（　）个元素。

A.n-i

B.n-i+1

C.n-i-1

D.i

10.线性表L=(a,a,…,a)，下列说法正确的是（　）。12n

A.每个元素都有一个直接前驱和一个直接后继

B.线性表中至少有一个元素

C.表中诸元素的排列必须是由小到大或由大到小

D.除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继

11.创建一个包括n个结点的有序单链表的时间复杂度是（　）。

A.O(1)

B.O(n)2

C.O(n)

D.O(nlogn)2

12.以下说法错误的是（　）。

A.求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低

B.顺序存储的线性表可以随机存取

C.由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活

D.线性表的链式存储结构优于顺序存储结构

13.在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（　）。

A.s->next=p+1; p->next=s;

B.(*p).next=s; (*s).next=(*p).next;

C.s->next=p->next; p->next=s->next;

D.s->next=p->next; p->next=s;

14.在双向链表存储结构中，删除p所指的结点时须修改指针（　）。

A.p->prior->next=p->next; p->next->prior=p->prior;

B.p->next=p->next->next; p->next->prior=p;

C.p->prior->next=p; p->prior=p->prior->prior;

D.p->prior=p->next->next; p->next=p->prior->prior;

15.在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（　）。

A.p->next=q; q->prior=p; p->next->prior=q; q->next=q;

B.p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;

C.q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;

D.q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;

16.【2013年第1题】已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是（　）。

A.O(n)

B.O(m×n)

C.O(min(m,n))

D.O(max(m,n))

17.【2016年第1题】已知表头元素为c的单链表在内存中的存储状态如图2.1所示。现将f存放于1014H处并插入到单链表中，若f在逻辑上位于a和e之间，则a，e，f的“链接地址”依次是（　）。图2.1 单链表的存储状态

A.1010H，1014H，1004H

B.1010H，1004H，1014H

C.1014H，1010H，1004H

D.1014H，1004H，1010H

18.【2016年第2题】已知一个带有表头结点的双向循环链表L，结点结构为prev data next，其中，prev和next分别是指向其直接前驱和直接后继结点的指针。现要删除指针p所指的结点，正确的语句序列是（　）。

A.p->next->prev=p->prev; p->prev->next=p->prev; free (p);

B.p->next->prev=p->next; p->prev->next=p->next; free (p);

C.p->next->prev=p->next; p->prev->next=p->prev; free (p);

D.p->next->prev=p->prev; p->prev->next=p->next; free (p);

19.将两个长度为n的递增有序表归并成一个长度为2n的递增有序表，最少需要进行关键字比较（　）次。

A.2

B.n-1

C.n

D.2n

20.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（　）。

A.O(1)

B.O(n)

C.O(m)

D.O(m+n)

21.若线性表最常用的操作是存取第i个元素及其前驱的值，则采用（　）存储方式节省时间。

A.单链表

B.双链表

C.单循环链表

D.顺序表

22.在线性表的下列运算中，不改变数据元素之间结构关系的运算是（　）。

A.插入

B.删除

C.排序

D.定位

23.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（　）。

A.head==NULL

B.head->next==NULL

C.head->next==head

D.head!=NULL

24.对于单链表表示法，以下说法错误的是（　）。

A.数据域用于存储线性表的一个数据元素

B.指针域或链域用于存放一个指向本结点的直接后继结点的指针

C.所有数据通过指针的链接而组织成单链表

D.NULL称为空指针，它不指向任何结点，只起标志作用

25.线性表(a,a,…,a)以链接方式存储时，访问第i个位置上元素12n的时间复杂度为（　）。

A.O(i)

B.O(1)

C.O(n)

D.O(i-1)

26.访问单链表中当前结点的后继和前驱的时间复杂度分别是（　）。

A.O(n)和O(1)

B.O(1)和O(1)

C.O(1)和O(n)

D.O(n)和O(n)

27.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是（　）。

A.O(1)

B.O(n)

C.O(nlogn)22

D.O(n)

28.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（　）最节省时间。

A.单链表

B.单循环链表

C.带尾指针的单循环链表

D.带头结点的双循环链表

29.在一个以L为头指针的单循环链表中，p指针指向链尾的条件是（　）。

A.p->next==L

B.p->next==NULL

C.p->next->next==L

D.p->data=-1

30.在循环链表中，将头指针改设为尾指针（rear）后，其首元结点和尾结点的存储位置分别是（　）。

A.rear和rear->next->next

B.rear->next和rear

C.rear->next->next和rear

D.rear和rear->next二、应用题

1.线性表有两种存储结构：一是顺序表，二是链表。试问：（1）如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？（2）若线性表的元素总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？

2.在单链表和双向链表中，能否从当前结点出发访问到任一结点？

3.说明在线性表的链式存储结构中，头指针与头结点之间的根本区别，头结点与首元结点的关系。

4.线性表(a,a,…,a)，采用顺序存储结构。试问：12n（1）在等概率的前提下，平均每插入一个元素需要移动的元素个数为多少？（2）若元素插在a与a之间（0≤i≤n-1）的概率为，则平ii+1均每插入一个元素所要移动的元素个数又是多少？

5.线性表(a,a,…,a)用顺序映射表示时，a与a（1≤i

1.将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其他的存储空间。表中不允许有重复的数据。

2.将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其他的存储空间。表中允许有重复的数据。

3.已知两个链表A和B分别表示两个集合，其元素递增排列。请设计一个算法，用于求出A与B的交集，并存放在A链表中。

4.已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出两个集合A和B的差集（即仅由在A中出现而不在B中出现的元素所构成的集合），并以同样的形式存储，同时返回该集合的元素个数。

5.设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B和C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A中的元素为非零整数，要求B、C表利用A表的结点）。

6.设计一个算法，通过一趟遍历确定长度为n的单链表中值最大的结点，返回该结点的数据域。

7.设计一个算法，将链表中所有结点的链接方向“原地”逆转，即要求仅利用原表的存储空间，换句话说，要求算法的空间复杂度为O(1)。

8.设计一个算法，删除递增有序链表中值大于mink且小于maxk（mink和maxk是给定的两个参数，其值可以和表中的元素相同，也可以不同）的所有元素。

9.已知p指向双向循环链表中的一个结点，其结点结构为data、prior、next三个域，写出算法Exchange(p)，交换p所指向的结点及其前驱结点的顺序。

10.已知长度为n的线性表A采用顺序存储结构，请写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法可删除线性表中所有值为item的数据元素。

11.【2009年第42题】已知一个带有表头结点的单链表，结点结构为（data，link），假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。要求：（1）描述算法的基本设计思想；（2）描述算法的详细实现步骤；（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C、C++或Java语言实现），关键之处请给出简要注释。

12.【2010年第42题】设将n（n>1）个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法，将R中保存的序列循环左移p（0

13.【2011年第42题】一个长度为L（L≥1）的升序序列S，处在第个位置的数称为S的中位数。例如，若序列S1=(11，13，15，17，19)，则S1的中位数是15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=(2，4，6，8，20)，则S1和S2的中位数是11。现有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。

要求：（1）给出算法的基本设计思想；（2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释；（3）说明你所设计算法的时间复杂度和空间复杂度。

14.【2012年第42题】假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，“loading”和“being”的存储映像如图2.2所示。

试读结束[说明：试读内容隐藏了图片]

下载完整电子书