目录目录前言第章绪论知识点串讲典型例题详解课后习题与解答第章线性表知识点串讲典型例题详解课后习题与解答第章栈和队列知识点串讲典型例题详解课后习题与解答第章串知识点串讲典型例题详解课后习题与解答第章数组和广义表知识点串讲典型例题详解课

Size: px

Start display at page:

Download "目录目录前言第章绪论知识点串讲典型例题详解课后习题与解答第章线性表知识点串讲典型例题详解课后习题与解答第章栈和队列知识点串讲典型例题详解课后习题与解答第章串知识点串讲典型例题详解课后习题与解答第章数组和广义表知识点串讲典型例题详解课"

锵匡
5 years ago
Views:

1 数据结构语言版例题详解与课程设计指导主编秦锋袁志祥副主编陈学进王森玉郑啸程泽凯合肥

2 目录目录前言第章绪论知识点串讲典型例题详解课后习题与解答第章线性表知识点串讲典型例题详解课后习题与解答第章栈和队列知识点串讲典型例题详解课后习题与解答第章串知识点串讲典型例题详解课后习题与解答第章数组和广义表知识点串讲典型例题详解课后习题与解答第章树和二叉树知识点串讲典型例题详解课后习题与解答第章图知识点串讲典型例题详解课后习题与解答第章查找知识点串讲典型例题详解课后习题与解答

3 数据结构语言版例题详解与课程设计指导第章排序知识点串讲典型例题详解课后习题与解答第章课程设计指导课程设计基本要求课程设计范例参考文献

4 内容简介本书力求对每题严格按照知识点全面分析并详细解答本书由两部分组成第一部分是典型例题详解和习题解答基本上涵盖数据结构的知识点第二部分通过经典的课程设计案例详解给出课程设计的实践指导本书希望通过对基础理论和概念的归纳总结典型例题的详细分析课后习题的详尽解答课程设计的实例分析帮助读者深化对基本概念的理解熟练掌握数据结构基本原理进一步提高算法设计和分析能力本书语言流畅内容通俗易懂例题经典解答详尽本书是数据结构语言版秦锋主编中国科学技术大学出版社出版的参考教材同时又自成体系可作为高等院校计算机专业的学习辅导书也可作为参加自学考试研究生入学考试程序员水平考试计算机国家等级考试的复习参考书图书在版编目数据数据结构语言版例题详解与课程设计指导秦锋袁志祥主编合肥中国科学技术大学出版社数秦袁数据结构高等学校教学参考资料语言程序设计高等学校教学参考资料中国版本图书馆数据核字第号出版中国科学技术大学出版社安徽省合肥市金寨路号邮编网址!"# #$%&&'&" % ' 印刷合肥现代印务有限公司发行中国科学技术大学出版社经销全国新华书店开本印张字数千版次年月第版印次年月第次印刷印数册定价元

5 前言前言数据结构是计算机专业最为重要的核心基础课程之一学好数据结构既能提高程序设计能力又能为后续课程操作系统数据库技术编译原理算法设计与分析等的学习打下良好的基础由于数据结构内容比较抽象对于具有程序设计基础的学生来说理解其中的概念和原理也许并不困难但在真正做习题时尤其是做算法设计题时往往困难重重有时甚至无从下手这在编者多年的教学中感受颇深这本参考教材是编者在长期的教学实践中收集并整理的目的就是通过对基础理论和概念的归纳总结典型例题的详细分析课后习题的详尽解答和课程设计的实例分析帮助读者深化对基本概念的理解熟练掌握数据结构基本原理以提高算法设计和分析的能力本书力求对每道例题都严格按照知识点全面分析并详细解答本书由两部分组成第一部分是典型例题详解和配套教材的课后习题解答全面涵盖了数据结构知识体系的各知识点第二部分是课程设计的实践指导列出了几个经典的课程设计案例分析全书共分章第章回顾数据结构基本概念评价算法优劣的主要指标及时间复杂度和空间复杂度第章介绍线性表的逻辑特性详细阐述顺序表和链表的存储结构及基本操作算法第章分别是栈与队列串数组和广义表第章是树与二叉树通过例题详解阐述二叉树的存储结构和常见算法操作第章是图阐述图的存储结构及相关理论的具体实现方法与过程第章和第章介绍广泛运用的两类算法查找和排序第章是课程设计实例详解每个实例按照问题描述设计思路数据结构设计功能函数设计界面设计编码实现运行与测试进行说明同时对学生提出明确的设计要求并对设计过程给予指导本书既是数据结构语言版秦锋主编中国科学技术大学出版社的配套教材每章内容与之对应且有习题解答同时又自成体系可作为高等学校计算机专业的学习辅导书也可作为参加自学考试研究生入学考试程序员水平考试计算机国家等级考试的复习参考书本书在编写过程中收集整理并少量引用了其他书籍的例题在此对原作者表示谢意并对程娜同学提供的课程设计实例代码和样式表示感谢本书由秦锋教授和袁志祥副教授担任主编陈学进王森玉郑啸程泽凯担任副主编其中第章第章第章由程泽凯编写第章第章由郑啸编写第章由秦锋编写第章由袁志祥编写第章第章由王森玉编写第章由陈学进编写秦锋教授对全书策划修改并统稿袁志祥完成全书的编排和整理工作因编者水平有限书中难免有不足甚至错误之处敬请广大读者批评指正编者年月

6 第章绪论第章绪论数据结构主要研究四个方面的问题数据的逻辑结构数据的物理结构基本操作与运算算法的分析本章主要内容是掌握数据结构概念和相关术语掌握算法描述和分析的方法知识点串讲相关术语数据元素数据对象数据项数据结构逻辑结构存储结构线性结构非线性结构集合线性结构树形结构图状结构顺序存储链式存储索引存储散列存储数据类型抽象数据类型原子类型结构类型算法时间复杂度空间复杂度算法描述算法 ()*+$,"! 是对特定问题求解步骤的描述是指令的有限序列其中每条指令表示一个或多个操作一个算法必须具备下列五个特性有穷性一个算法对于任何合法的输入必须在执行有穷步骤之后结束且每步都可在有限时间内完成确定性算法的每条指令必须有确切含义不能有二义性在任何条件下算法只有惟一的一条执行路径即对相同的输入只能得出相同的结果可行性算法是可行的即算法中描述的操作均可通过已经实现的基本运算的有限次执行来实现输入一个算法有零个或多个输入这些输入取自算法加工对象的集合输出一个算法有一个或多个输出这些输出应是算法对输入加工后符合逻辑的结果通常对算法的评价按照下面四个指标来衡量正确性 +$$% " %&& 可读性 -%../,),"0 健壮性 -+/'&" %&&

7 数据结构语言版例题详解与课程设计指导时空效率 1,,% 0 算法分析时间复杂度算法中所有语句的频度之和空间复杂度算法对输入数据进行运算所需的辅助工作单元和存储为实现计算所需信息的辅助空间重点掌握对一般算法的时间复杂度和空间复杂度的分析典型例题详解选择题不是算法的基本特征 ( 可行性长度有限在规定的时间内完成确定性分析与解答本题主要考查算法的个特征算法应满足有穷性确定性可行性输入和输出个基本特性长度有限并不是算法的特性之一因而答案为下列关于算法的说法正确的是 ( 算法最终必须由计算机程序实现算法的可行性是指指令不能有二义性为解决某问题的算法与为该问题编写的程序含义是相同的程序一定是算法分析与解答本题考查关于算法的概念 ( 选项是错误的算法不一定用计算机程序实现它只是对特定问题求解步骤的一种描述选项是错误的算法的确定性是指指令不能有二义性选项是正确的其含义是用程序实现了相应的算法选项显而易见是错误的有死循环的程序不能满足有穷性故本题的正确答案是下面说法中错误的是 ( 空间效率为的算法不需要任何额外的辅助空间在相同的规模下时间复杂度为的算法在时间上总是优于时间复杂度为的算法所谓时间复杂度是指在最坏情况下估算算法执行时间的一个上界同一个算法实现语言的级别越高执行的效率不一定越低分析与解答选项 ( 是错误的空间效率为的算法是指算法所需的辅助空间并不依赖于问题的规模并不是不需要任何额外的辅助空间选项是正确的从时间复杂度角度上看这句话是正确的选项是正确的这是时间复杂度的一般定义选项是正确的同一个算法实现语言的级别同执行效率并没有严格的比例关系故本题的正确答案是 ( 以下关于数据的存储结构的叙述中正确的有 ( 顺序存储方式只能用于存储线性结构

8 第章绪论顺序存储方式的优点是存储密度大且插入删除运算效率高链表的每个节点中都恰好包含一个指针散列法存储的基本思想是由关键字的值决定数据的存储地址 1 散列表的节点只包含数据元素自身的信息不包含任何指针分析与解答本题考查数据的存储结构概念有一定的综合性选项 ( 是错误的如二叉树可以采用顺序存储方式存储选项是错误的顺序存储由于是一组连续的存储单元按顺序存储插入和删除需大量移动记录执行效率低选项是错误的如双向链表有两个指针选项是正确的散列法就是用散列函数作用于关键字值产生数据存储地址选项 1 是错误的散列表在处理冲突时可用拉链法这样需用一个指针综上所述故本题的答案是某算法仅含程序段和程序段程序段的执行次数为程序段的执行次数为则该算法的时间复杂度为 ( 分析与解答算法的时间复杂度取指数项最大的算式本题答案以下说法正确的是 ( 数据结构的逻辑结构独立于其存储结构数据结构的存储结构独立于该数据结构的逻辑结构据结构的逻辑结构惟一地决定了该数据结构的存储结构数据结构仅由其逻辑结构和存储结构决定分析与解答数据的存储结构是指数据在计算机内的表示方法是逻辑结构的具体实现因此存储结构应包含两个方面的内容即数据元素本身的表示与数据元素间逻辑关系的表示因此显然选项的说法有问题而选项有错因为数据结构是由其逻辑结构存储结构以及附加在存储结构上的运算构成本题答案 ( 以下说法正确的是 ( 数据元素是具有独立意义的最小标识单位原子类型的值不可再分解原子类型的值由若干个数据项值组成结构类型的值不可以再分解分析与解答数据项是具有独立含义的最小标识单位故选项 ( 是错误的结构类型的值是可再分解的故选项是错误的本题答案为设有如下遗产继承规则丈夫和妻子可以互相继承遗产子女可以继承父亲和母亲的遗产子女间不能相互继承则表示该遗产继承关系最合适的数据结构应该是 ( 树图线性表集合分析与解答用排除法由于元素间有次序关系故排除选项集合而元素可能存在多个前驱或后继结点故排除选项该数据结构虽是层次关系但可能不存在树根故选项 ( 的树型结构不合要求本题的答案是选项图形结构判断题数据元素是数据的最小单位答案错误分析数据项是具有独立含义的最小标识单位而数据元素是数据的基本单位一个数据

9 数据结构语言版例题详解与课程设计指导元素可能由若干数据项组成数据的逻辑结构是指各数据元素之间的逻辑关系与物理结构无关答案正确分析由逻辑结构的定义不难判断算法的时间效率和空间效率往往相互冲突有时很难两全其美答案正确分析在算法设计中常常会牺牲时间换取空间有时也会牺牲空间换取时间运算的定义依赖于逻辑结构运算的实现也依赖于逻辑结构而与存储结构无关答案错误分析数据运算即对数据施加的操作运算的定义直接依赖于逻辑结构但运算的实现必依赖于存储结构即只有在确定了存储结构之后才能讨论运算是如何实现的数据结构是指相互之间存在一种或多种关系的数据元素的全体答案错误分析数据结构是指数据的逻辑结构物理结构以及数据的运算操作从逻辑关系上讲数据结构主要分为两大类线性结构和非线性结构答案正确分析对数据结构的逻辑结构而言数据结构分为集合线性结构树形结构图状结构四种其中树形结构和图状结构属于非线性结构算法和程序都应具有下面一些特征有输入有输出确定性有穷性有效性答案错误分析程序不需要具有有穷性填空题数据的逻辑结构被分为和种答案集合线性结构树形结构图形结构次序可以调换分析本题考查数据的逻辑结构的概念在图形结构中每个结点的前驱结点和后续结点数可以答案任意多个分析本题考查图形结构的特点时间和空间复杂度在最好和最坏情况下分别是和答案分析本题考查算法的时间和空间效率最好情况是时空效率与问题的规模无关最坏情况下时空效率是问题规模的指数关系一种抽象数据类型包括和两个部分答案数据操作当问题的规模趋向无穷大时算法执行时间的数量级被称为算法的答案时间复杂度

10 第章绪论应用题简述数据的逻辑结构和存储结构的区别与联系它们如何影响算法的设计与实现分析与解答若用结点表示某个数据元素则结点与结点之间的逻辑关系就称为数据的逻辑结构数据在计算机中的存储表示称为数据的存储结构可见数据的逻辑结构是反映数据之间的固有联系而数据的存储结构是数据在计算机中的存储表示尽管因采用的存储结构不同逻辑上相邻的结点其物理地址未必相邻但可通过结点的内部信息找到其相邻的结点从而保留了逻辑结构的特点采用的存储结构不同对数据的操作在灵活性算法复杂度等方面差别较大考查下列两段描述它们是否满足算法的特征如不满足说明违反了哪些特征 +, %.!,)% 2 3 #$, " , %. 0 0 #$, " 分析与解答不满足算法的特征是一个死循环违反了算法的有穷性特征不满足算法的特征包含除零错误违反了算法的可行性特征指出下列算法的功能并求出其时间复杂度, " $, %, ", ",, ", "&5$"!,)%33,, 2, /$%.6,, $%"'$ %)&% $%"'$ 分析与解答该算法的功能是判断是否是一个素数若是则返回数值否则返回当为素数时令槡且 2, 则循环语句!,)% 至少执行次因此该算法的时间复杂度为槡

11 数据结构语言版例题详解与课程设计指导某数据结构的二元组表示为 &%" 其中该结构为何种类型结构分析与解答在数据结构 &%" 中只存在有元素的集合关系为空这表明只考虑表中的每条记录不考虑它们之间的任何关系具有此种特点的数据结构称为集合结构集合结构中的元素可以任意排列无任何次序某数据结构的二元组表示为 ), %.$,"0 其中该结构为何种类型结构分析与解答本题所表示的图形如图所示图第题的数据结构示意图在数据结构 ), %.$,"0 中数据元素之间是有序的每个数据元素有且仅有一个直接前驱元素除结构中第一个元素外有且仅有一个直接后继元素除结构中最后一个元素外这种数据结构的特点是数据元素之间的对联系即线性关系具有这种特点的数据结构叫做线性结构某数据结构的二元组表示为 "$%% 其中该结构为何种类型结构分析与解答本题所表示的图形如图所示图的形状像一棵倒置的树最上面的一层没有前驱只有后继的结点叫做树根结点最下面一层的只有前驱没有后继的结点叫做树叶结点除此之外的结点叫做树枝结点在一棵树中每个结点有且只有一个前驱结点除树根结点外但可以有任意多个后继结点树叶结点可看作为含个后继结点这种数据结构的特点是数据元素之间的对联系即层次关系我们把具有这种特点的数据结构叫做树结构简称树图第题的数据结构示意图某数据结构的二元组表示为 *$.#! 其中

12 第章绪论该结构为何种类型结构分析与解答本题所表示的图形如图所示从图可以看出是上的对称关系可以把和这两个对称序偶简化为无序对或在图中把结点和结点之间两条相反的有向边用一条无向边来代替关系可改写为所表示的图形如图所示图图的数据结构示意图图图的等价表示从图或图可以看出结点之间的联系是对联系即网状关系也就是说每个结点可以有任意多个前驱结点和任意多个后继结点具有这种特点的数据结构叫做图结构简称图由题题和题可知树结构是图结构的特殊情况即的情况线性结构是树结构的特殊情况即的情况为了区别于线性结构可把树结构和图结构统称为非线性结构假设为的乘幂并且试求下列算法的时间复杂度及变量 +' " 的值以的函数形式表示, ", %, " +' "!,)% +' "33 $%"'$ +' " 分析与解答该算法的时间复杂度主要为循环语句!,)% 执行次数假设乘法的执行次数为则 3 当时则退出循环体即 3 对 3 进行整理获得 )+* 该题算法的时间复杂度为 )+* 所返回的 +' " 值就是 )+* 对任一算法只要得到与该算法对应问题规模的函数便可求得该算法的时间复杂度而算法对应问题规模的函数通常与循环次数有关

13 数据结构语言版例题详解与课程设计指导课后习题与解答选择题以下说法错误的是 ( 用数字式计算机解决问题的实质是对数据的加工处理程序设计的实质是数据处理数据的逻辑结构表达了数据之间的内在关系数据处理方式总是与数据的逻辑结构相联系根据数据元素之间关系的不同特性以下四类基本的逻辑结构反映了四类基本的数据组织形式解释错误的是 ( 集合中任何两个结点之间都有逻辑关系但组织形式松散线性结构中结点按逻辑关系依次排列形成一条锁链树形结构具有分支层次特性其形态有点像自然界中的树图状结构中的各个结点按逻辑关系互相缠绕任何两个结点都可以邻接关于逻辑结构以下说法错误的是 ( 逻辑结构与数据元素本身的形成内容无关逻辑结构与数据元素的相对位置有关逻辑结构与所含结点个数无关一些表面上很不相同的数据可以有相同的逻辑结构 1 逻辑结构是数据组织的某种本质性的东西一个算法应该是 ( 程序问题求解步骤的描述要满足五个基本特性 ( 和下面关于算法说法错误的是 ( 算法最终必须由计算机程序实现为解决某问题的算法同为该问题编写的程序含义是相同的算法的可行性是指指令不能有二义性以上几个都是错误的程序段 +$,,, +$ , ( 7!( 73! ( 7! 与 ( 73! 对换其中为正整数则最后一行的语句频度在最坏情况下是 ()+* 以下说法正确的是 ( 数据元素是数据的最小单位数据项是数据的基本单位

14 第章绪论原子类型不可再分解数据项只能是原子类型参考答案 ( 填空题通常从等几方面评价算法的包括程序的质量对于给定的个元素可以构造出的逻辑结构有四种存储结构主要有四种抽象数据类型的定义仅取决于它的一组而与无关即不论其内部结构如何变化只要它的不变都不影响其外部使用一个算法具有个特性有零个或多个输入有一个或多个输出参考答案正确性可读性健壮性时空效率集合线性关系树形关系图状关系顺序存储链式存储索引存储散列存储逻辑特性存储结构数学特性有穷性确定性可行性判断题数据元素是数据的最小单位数据的逻辑结构是指数据的各数据项之间的逻辑关系算法的优劣与算法描述语言无关但与所用计算机有关程序一定是算法数据的物理结构是指数据在计算机内的实际存储形式数据结构的抽象操作的定义与具体实现有关数据的逻辑结构表达了数据元素之间的关系它依赖于计算机的存储结构

15 数据结构语言版例题详解与课程设计指导参考答案错误错误错误错误正确错误错误应用题解释下列概念数据数据元素数据类型数据结构逻辑结构存储结构线性结构非线性结构算法算法的时间复杂度算法的空间复杂度数据的逻辑结构有哪几种常用的存储结构有哪几种试举一个数据结构的例子叙述其逻辑结构存储结构和运算三方面的内容什么叫算法它有哪些特性设为正整数用记号将下列程序段的执行时间表示为的函数, "&', ", ",# & +$,,,33 #, &3 # $%"'$ &, "&', ", "#&, ",7 +$,,,33 # +$7 7,733 # 7 &3 # $%"'$ &, " ', ", ", &!,)%& &3 33, $%"'$,

16 第章绪论参考答案略略可以用日常生活中的一种物质水来说明数据结构的三个方面水是由许多水分子组成一个水分子由氢和氧两种元素组成这与外界的环境无关相当于数据的逻辑结构水在日常生活中有液态气态固态三种不同形态相当于数据有三种存储结构对水进行升温降温等操作相当于对数据所施加的操作其他的例子略略该算法的功能是计算的值函数中 +$ 循环的次数是时间复杂度为该算法的功能是计算的值函数中有双重循环外层循环的执行次数为次内层循环的执行次数为次总的循环次数为因此时间复杂度为该算法的功能是求出满足不等式的最小值当循环体执行第次时为当循环体执行第次时为当循环体执行第次时为依此类推不妨假设当循环体执行第次时退出循环体则有整理式得槡因此本题的时间复杂度为槡算法设计题写一算法从键盘输入若干个非整数以作结束标志找出其中最大和最小的数并分析算法的时间复杂度输入数据不需保存设计求解下列问题的类语言算法并分析其最坏情况下的时间复杂度在数组! 中查找值为的元素若找到则输出其位置否则输出作为标志找出数组! 中元素的最大值和次最大值分析与解答设两个变量和每次从键盘输入的数与和比较若大于则存入若小于则存入直到输入的数为为止算法省略分析从! 开始依次遍历数组的各个元素看该值是否等于若相等则将值保留若遍历结束还未找到值为的数则返回算法描述如下, "8, "9, "(!, ", "6, ",

17 数据结构语言版例题详解与课程设计指导!,)%(,! 6::, 遍历数组 ( 并判断元素值是否为 6,33,, $%"'$ 未找到 $%"'$, 本算法的最坏情况是遍历完数组所以时间复杂度是设定个变量与分别表示最大值和次最大值从! 开始依次遍历数组的各个元素! 先与比较若! 大于则与交换! 存入若! 小于而大于则! 存入其余条件下不处理算法描述如下, "8, "., "(!, ", ". (!. (!. 中保留最大值. 中保留次大值 +$,,,33, (,!. 与最大值. 比较... (,! %)&%, (,!. 与次大值比较. (,! 算法的时间复杂度是

18 第章线性表第章线性表线性表是一种最常用的数据结构其数据元素之间的关系表现为除第一个元素无前驱元素最后一个元素无后继元素外其余元素均有且仅有一个前驱和一个后继元素线性表的存储结构有两种实现方式顺序存储和链式存储本章要求掌握线性表两种不同存储结构以及插入删除检索等操作能设计算法解决与线性表相关的各类应用问题知识点串讲知识结构图本章的主要知识点结构如图所示顺序表特点顺序存储结构线性表的应用插入删除线性表单链表链式存储结构循环链表插入删除双向链表图线性表的知识结构图相关术语顺序表链表单链表循环单链表循环双向链表静态链表结点数据域指针域头结点首结点头指针指针变量插入删除动态空间分配静态空间分配线性表的顺序存储结构线性表的顺序存储是计算机中最简单最常用的一种存储方式即用一组地址连续的存储单元依次存放线性表中的元素该结构的特点是逻辑相邻的数据元素在物理上也相邻用顺序存储方法存储的线性表简称为顺序表

19 数据结构语言版例题详解与课程设计指导顺序表类型定义如下 %, %;( 1 "0#% % &"$' " + %.". 0#%.". ;( 1!, ")% *"! %5,&" %5),&" 对上述定义顺序表类型 %5,&" 要特别注意的是数组的下标从开始而不是从开始线性表改变时要及时修改其中 )% *"! 成员变量的值顺序表的基本操作主要是插入操作运算顺序表的插入运算时间主要消耗在数据的移动上在第个位置上插入从到都要向后移动一个位置共需要移动 3 个元素在等概率情况下平均移动数据元素的次数为插入操作算法的时间复杂度均为删除操作运算与插入运算相同其时间主要消耗在移动表中元素上删除第个元素时其后面的元素 3 都要向前移动一个位置共移动了个元素所以在等概率情况下平均移动数据元素的次数为删除操作算法的时间复杂度均为线性表的链式存储结构链表的概念链表就是把线性表中每个元素的值和该表中下一个元素的地址放在一起这两部分信息组成一个结点若干个这种结点构成了线性链表单链表单链表中每个结点由数据域和指针域两部分组成结点形式如下.". % " 其中.". 部分称为数据域用于存储线性表的一个数据元素结点 % " 部分称为指针域或链域用于存放一个指针该指针指向本结点所含数据域元素的直接后继所在的结点单链表的类型定义如下 "0#% % &"$' " + %.". 0#%.". 每个元素数据信息 &"$' " + % % " 存放后继元素的地址 + %, 6,&" 单链表分为带头结点其 % " 域指向第一个结点和不带头结点两种类型头结点的设置可简化运算的实现过程

20 第章线性表设置头结点的好处是便于处理首结点使得在创建链表和删除结点时可以将首结点与其他结点同等对待对于不带头结点的链表在插入和删除操作时需要每次对首结点进行判断这样十分繁琐可利用头结点的数据域存储链表相关信息如链表的长度等这样可以不需要通过遍历整个链表获得这些消息提高算法的效率在单链表上实现线性表基本运算的函数如下初始化函数设计思想用于创建头结点由指针!%. 指向它该结点的 % " 域为空.". 域未设定任何值其时间复杂度为插入函数设计思想创建一个.". 域值为的新结点 # 然后插入到!%. 所指向的单链表的第个结点之前为保证插入正确有效必须查找到指向第个结点的前一个结点的指针主要的时间耗费在查找上因而在长度为的线性单链表上进行插入操作的时间复杂度为删除函数设计思想线性链表中元素的删除要修改被删元素前驱的指针回收被删元素所占的空间主要的时间耗费在查找上因而在长度为的线性单链表上进行删除操作的时间复杂度为查找函数设计思想线性链表中查找元素要找元素前驱的指针在长度为的线性单链表上进行删除操作的时间复杂度为求单链表长度函数设计思想通过遍历的方法从头数到尾即可得到单链表长双向链表双向链表的结点中包含有两个指针域一个是指向其前驱的 #$,+$ 指针域另一个是指向其后继的 % " 指针域结点形式如下双向链表的类型描述如下 "0#% % &"$' " + %.". 0#%.". &"$' " + %#$,+$ % " + %, 6,&" #$,+$.". % " 双向链表的优点可以正反两个方向查找当链表中一个链破坏时可以用另一个链修复链表循环链表循环链表可分为循环单链表和循环双链表循环单链表是将单链表最后一个结点的 % " 域的指针改为指向它的头结点所得到的链表循环双链表是将双向链表的头结点和尾结点链接起来所得到的链表特别需要注意的是循环链表中没有指针涉及遍历操作时其终止条件就不再是像非循环链表

21 数据结构语言版例题详解与课程设计指导那样判别 # 或 # % " 是否为空而是判别它们是否等于某一指定指针如头指针或尾指针等在单链表中从一已知结点出发只能访问到该结点及其后续结点无法找到该结点之前的其他结点而在单循环链表中从任一结点出发都可访问到表中所有结点这一优点使得某些运算在单循环链表上易于实现例如用带有指向尾结点指针的单循环链表来实现队列操作线性表的顺序和链式存储结构的比较顺序表的存储空间是静态分配的在程序执行之前必须明确规定它的存储规模也就是说事先对 ;( 1 要有合适的设定过大造成浪费过小造成溢出如果对线性表的长度或存储规模难以估计时不宜采用顺序表链表不用事先估计存储规模但链表的存储密度较低存储密度是指一个结点中数据元素所占的存储单元和整个结点所占的存储单元之比在顺序表中按序号访问元素的时间性能为而链表中按序号访问的时间性能是所以如果经常做的运算是按序号访问数据元素显然顺序表优于链表而在顺序表中做插入删除时需移动元素当数据元素的信息量较多且表较长时这一点是不应忽视的在链表中做插入删除虽然也要找插入位置但主要是比较操作从这个角度考虑显然链表较优顺序表容易实现任何高级语言中都有数组类型链表的操作是基于指针的有些语言不支持指针类型并且相对指针来讲顺序表较简单总之两种存储结构各有长短选择哪一种存储方式应由实际问题决定通常较稳定的线性表选择顺序存储而频繁做插入删除的即动态性较强的线性表宜选择链式存储典型例题详解选择题线性表在链式存储中各结点之间的地址 ( 必须连续部分地址必须连续不能连续连续与否无所谓分析与解答本题主要考查链式存储结构的特点线性链表的逻辑地址相邻但其物理地址未必相邻链表是靠指向后继指针来找其后继的正确答案为将两个各有个元素的有序线性表归并成一个有序线性表最少的比较次数是 ( 分析与解答当一个表的最小元素大于另一个表的最小元素时比较的次数最少为表的长度故本题答案是 ( 有关线性表的正确说法是 ( 每个元素都有一个直接前驱和一个直接后继线性表至少要求一个元素表中的元素必须按由小到大或由大到小排序

22 第章线性表除了第一个和最后一个元素外其余元素都有一个且仅有一个直接前驱和直接后继分析与解答根据线性表的特点线性表中第一个元素没有直接前驱最后一个元素没有直接后继故选项 ( 是错误的线性表允许为空表故选项是错误的线性表中的元素是任意的无大小排序之分故选项是错误的由选项 ( 的分析可知正确答案为以下说法错误的是 ( 求表长定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低顺序存储的线性表可以随机存取由于顺序存储要求连续的存储区域所以在存储管理上不够灵活线性表的链接存储结构优于顺序存储结构分析与解答本题考查线性表的存储结构的特点线性表的顺序存储结构和链式存储结构各有优缺点应根据实际情况选用不能笼统说哪一个好故本题答案是在有个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是 ()+* 分析与解答本题考查链表基本算法的时间复杂度结合本题算法的主要开销在于查找适合插入的位置平均查找长度为故选项为正确答案下述哪一条是顺序存储结构的优点 ( 存储密度大插入运算方便删除运算方便可方便地用于各种逻辑结构的存储表示分析与解答本题主要考查顺序存储结构的基本特点均是链式存储结构的优点只有 ( 是顺序存储结构的优点故本题答案为 ( 对单链表表示法以下说法错误的是 ( 数据域用于存储线性表的一个数据元素指针域用于存放一个指向本结点所包含数据元素的直接后继所在结点的指针所有数据通过指针的链接而组织成单链表单链表中各结点地址不可能连续分析与解答本题考查单链表的基本概念答案是若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算则利用存储方式最节省时间 ( 顺序表双链表带头结点的双循环链表单循环链表分析与解答本题考查线性表存储结构的选择随机存储是顺序存储结构的优点其缺点是插入删除操作需移动大量的元素由题可知要求在最后的元素插入和删除故选用顺序存储结构比较好本题答案为 ( 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素则采用存储方式最节省运算时间 ( 单链表仅有头指针的单循环链表双链表仅有尾指针的单循环链表分析与解答本题考查线性表存储结构的选择题目要求对最后一个元素和第一个元素分别进行插入和删除操作故选用循环链表结构比较好选用尾指针可以快速找到最后一个元

23 数据结构语言版例题详解与课程设计指导素而头指针却不行故本题答案为设一个链表最常用的操作是在末尾插入结点和删除尾结点则选用最节省时间 ( 单链表单循环链表带尾指针的单循环链表带头结点的双循环链表分析与解答本题考查线性表存储结构的选择与上题不同之处在于本题要求删除最后一个结点这样要求找到倒数第二个结点若选用带尾指针的单循环链表的话需要遍历整个链表时间效率比较低在双循环链式结构可以快速找到倒数第二个结点符合本题要求故本题答案为静态链表中指针表示的是 ( 内存地址本元素的数组下标后继的数组下标左右孩子地址分析与解答本题考查静态链表的基本概念不难得到本题答案为下列说法错误的是 ( 对循环链表来说从表中任一结点出发都能通过前后移动操作扫描整个循环链表对单链表来说只有从头结点开始才能扫描表中全部结点双向链表的特点是查找结点的前驱和后继都很容易对双向链表来说结点的存储位置既存放在其前驱结点的后继指针域中也存放在它的后继结点的前驱指针域中分析与解答本题考查循环链表的基本概念和原理循环链表分单循环链表和双循环链表两种双向循环链表有指向前驱结点和后继结点的两个指针域以空间代价换取时间代价而单循环链表只有指向后继的一个指针域从任一结点访问整个线性表需要从表头开始故本题答案是 ( 线性表以链式方式存储时访问第个元素的时间复杂性为 ( 分析与解答本题考查线性表算法的时间复杂度链式存储方式下访问第个元素需从第个结点开始依次访问时间复杂度是本题答案为非空的循环单链表!%. 的尾结点 # 满足 (# ), 6!%. # ), 6 # #!%. 分析与解答本题考查非空的循环单链表的特点答案为 ( 对于顺序存储的线性表结点的插入和删除操作的时间复杂度为 ( 分析与解答本题考查线性表算法的时间复杂度答案为判断题顺序表可以用一维数组表示因此顺序表与一维数组在结构上是一致的可以通用答案错误

24 第章线性表分析顺序表和一维数组是两个不同的概念链接存储表示的存储空间一般在程序的运行过程中动态分配和释放且只要存储器中还有空间就不会产生存储溢出的问题答案正确分析由链式存储的特点不难得到链式存储在插入和删除时需要保持数据元素原来的物理顺序不需要保持原来的逻辑顺序答案错误分析链式存储结构是线性结构的一种逻辑顺序是要保证的在链式存储表中存取表中的数据元素时不一定要按顺序访问答案错误分析链式存储结构下不能随机访问只能从表头结点开始按顺序访问在单链表表尾插入结点与在表中插入结点处理的方法不同答案错误分析在单链表表尾插入结点与在表中插入结点处理的方法是可以统一的链表中的头结点仅起到标识的作用答案错误分析头结点并不仅起标识作用并且使操作统一另外头结点数据域可记录链表长度或作监视哨顺序存储方式插入和删除时效率太低因此它不如链式存储方式好答案错误分析线性表的两种存储结构各有优缺点应根据实际情况选用不能笼统说哪一个好取线性表的第个元素的时间同的大小有关答案错误分析线性表的顺序存储结构中取线性表的第个元素的时间同的大小无关在不带头结点的单链表中首结点的插入或删除与在其他位置的结点插入或删除操作过程是相同的答案错误分析在不带头结点的单链表中当链表为空时新插入的结点即为单链表的首结点无需任何操作而当在其他位置进行插入时需要调整改变结点的指针域值显然首结点的插入与其他位置的结点操作是不同的类似情况首结点的删除操作同样与其他位置的结点删除操作是不一样的通常在单链表中设置头结点的目的是为了首结点与其他位置结点的插入和删除操作一致填空题顺序存储结构使线性表中逻辑上相邻的数据元素在物理上也相邻因此这种表便于访问是一种答案随机随机存取

25 数据结构语言版例题详解与课程设计指导在链表的结点中数据元素所占的存储量和整个结点所占的存储量之比称作答案存储密度已知是无表头结点的单链表且结点既不是首结点也不是尾结点试添加合适的语句序列结点后插入结点的语句序列是在结点前插入结点的语句序列是在表首结点之前插入结点的语句序列是在表尾结点之前插入结点的语句序列是答案 % " # % "# % " #$%!,)%#$% % " #$% #$% % " % " #$% % "#$% % " % "!,)%# % " % " % " % " % " % " 分析在结点后插入结点其操作过程如图所示图在结点前插入结点首先必须获得结点的前驱结点 #$% 然后在结点 #$% 之后完成对结点的插入操作本小题的关键是找到结点的前驱 #$%!,)%#$% % " #$% #$% % " 在表首结点之前插入结点首先完成 % " 其次是在表尾结点之前插入结点首先要获得表尾结点之前结点的指针变量 # 然后再完成对结点的插入操作即可已知结点是某双向链表的中间结点试添加合适的语句序列完成以下要求结点后插入结点的语句序列是在结点前插入结点的语句序列是删除结点的直接后继结点的语句序列是删除结点的直接前驱结点的语句序列是删除结点的语句序列是答案 % " # % " #$,+$ % " #$,+$ % " % " #$,+$ #$,+$ #$,+$ % " #$,+$ % " % " % " % " #$,+$ $%%

26 第章线性表 #$,+$ #$,+$ #$,+$ #$,+$ % " $%% #$,+$ % " % " % " #$,+$ #$,+$ $%% 分析根据图所示的双向循环链表示意图完成题目所要求的操作即可所需要注意的是在链表中删除或者插入某个结点必须获得该结点的指针变量或者其前驱结点的指针变量因此在单链表中获取某个结点的前驱结点需要执行遍历单链表操作在双向链表中获取某个结点的前驱结点则不需要遍历单链表因为双向链表中的结点存在指向其前驱或后继结点的指针域图第题的示意图对于双向链表在两个结点之间插入一个新的结点时需要修改的指针共有个单链表为个答案分析对于双向链表在两个结点之间插入一个新结点时需要修改前一结点的 % " 域后一个结点的 #$,+$ 域插入结点的 % "#$,+$ 域所以共修改个指针对于单链表在两个结点之间插入一个新结点时需要修改前一结点的 % " 域插入结点的 % " 域所以共修改个指针在下面数组中链接存储着一个线性表如图所示其中表头指针为.! % " 则该线性表的存储序列为.". % " 图线性表的存储结构图答案分析本题考查静态链式存储结构的基本概念与前面所讲的单链表中的指针不同的是静态链表的指针是结点的相对地址数组的下标在一个长度为的单链表上设有头尾两个指针有以下操作删除单链表中的第一个元素删除单链表中最后一个元素在单链表第一个元素前插入一个新元素在单链表最后一个元素后插入一个新元素执行操作与链表的长度无关答案分析设有头尾指针的单链表如图所示要删除单链表中的第一个元素仅需要执行 %.. % " 操作当删除单链表中最后一个元素后需要知道. 结点所在的位置这样则要遍历整个单链表要在单链表第一个元素前插入一个新元素结点 & 执行 & % "

27 数据结构语言版例题详解与课程设计指导 %. %. & 在单链表最后一个元素后插入一个新元素结点 & 仅执行.,) % " &.,) & 从上面的分析可知仅当删除单链表中的最后一个元素时需要遍历单链表操作的时间复杂度为因此操作执行时间与链表的长度相关图带头尾指针的单链表若某链表中最常用的操作是在最后结点之后插入结点和删除最后结点则采用存储方式最节省运算时间答案带头结点的循环双链表分析根据节第题中的分析可知双循环链表容易找到最后一个结点和其前驱结点时间复杂度均为而单链表或循环单链表则要遍历整个链表时间复杂度为应用题指出带头结点的单链表和不带头结点的单链表的区别分析与解答带头结点的单链表和不带头结点的单链表的区别主要体现在其结构上和算法操作上在结构上带头结点的单链表不管链表是否为空均含有一个头结点而不带头结点的单链表不含头结点在操作上带头结点的单链表的初始化为申请一个头结点且在任何结点位置进行的操作算法一致而不带头结点的单链表让头指针为空同时其他操作要特别注意空表和第一个结点的处理与单链表相比双向循环链表有哪些优点分析与解答双向循环链表设置了指向前驱和后继的指针所用的地址空间增加以空间复杂度代价换取时间复杂度的提高双向循环链表可以从任一结点开始遍历整个链表在动态内存管理中应用双向循环链表可以从上次查找过的结点开始继续查找可用结点而单链表却每次都需要从表头开始查找相比之下双向循环链表的时间效率更高写出如图所示的双向链表中对换值为和的两个结点相互位置时修改指针的有关语句结点结构为 #$,+$.". % " 图双向链表分析与解答设 5 # #$,+$ 则 5 % " # % "# % " #$,+$ 5 # #$,+$ 5 #$,+$5 #$,+$ % " ## % " 55 #$,+$ #

28 第章线性表阅读下列算法并回答问题设顺序表写出执行 %. #)%: 之后的设顺序表写出执行 %. #)%: 之后的简述算法的功能 +, %. #)% %5,&".". 0#%, ", 7!,)%, )% *"!::.".,!,33,, )% *"!::.".,! +$7,37 )% *"!733.".7!.".7! )% *"! %)&% +$7 )% *"!7,7.".7!.".7!.".,! )% *"!33 分析与解答解答这类问题的关键是仔细阅读程序按照程序代码的执行过程记录并观察数据变化规律以确定该程序代码实现的具体功能在顺序表中查找数若找到则删除若没找到则在适当的位置插入插入后依然有序阅读下列算法并回答问题, 6,&" 0 +"%, 6,&" 是不带头结点的单链表的头指针, :: % " 5 % " #!,)%# % " # # % "% # % " 5 $%"'$ 5 % " %

29 数据结构语言版例题详解与课程设计指导请回答下列问题说明语句的功能说明语句组的功能设链表表示的线性表为写出算法执行后的返回值所表示的线性表分析与解答语句组用来从当前结点开始遍历到链表的尾结点语句组将第一个结点链接到链表的尾部作为新的尾结点返回的线性表为下列函数的功能是对以带头结点的单链表作为存储结构的两个递增有序表表中不存在值相同的数据元素进行如下操作将所有在 / 表中存在而. 表中不存在的结点插入到. 中其中. 和 / 分别为两个链表的头指针请在空缺处填入合适内容使其成为一个完整的算法 +, ',+, 6,&"., 6,&" / 本算法的功能是将所有 / 表中存在而. 表中不存在的结点插入到. 表中, 6,&"#$%.5, 6,&"#.. % ", 6,&"#/ / % " $%% /!,)%#.::#, #..".#/.". #$% #. #. #. % " %)&%, #..". #/.". #$% #/ #/ #/ % " %)&% 5 #/ #/ #/ % " $%%5, #/ 分析与解答指针 #. 指向. 指针 #/ 指向 / 分别遍历. 和 / 依次比较 #. 和 #/ 所

Microsoft Word - 专升本练习2：线性表.doc

Microsoft Word - 专升本练习2：线性表.doc 第二章线性表一选择题 1. 线性表是 ( ) A. 一个有限序列, 可以为空 B. 一个有限序列, 不能为空 C. 一个有限序列, 可以为空 D. 一个无序序列, 不能为空 2. 对顺序存储的线性表, 设其长度为 n, 在任何位置上插入或删除操作都是等概率插入一个元素时大约要移动表中的 ( ) 个元素, 删除一个元素时大约要移动表中的 ( ) 个元素 A. n/2 B. (n+1)/2 C.