《据结构习题与解析》（C语言版）

北京科海培训中心 李春葆编著 生啊 C语言篇) 习题与解新 2-44 清华大学出版社

北京科海培训中心 数据结构习题与解析 (C语言篇) 李春葆编著 清华大学出版社

(京)新登字158号 内容提裹 本书根据数据结构课程的教学大纲的要求,提供了作者多年教学中积累、收集与验证的 有关数据结构的基本内容及相关题解。全书共分13章每章先给出内容概述,然后给出该章 的题解题解分为基本题和习题解析两部分,前者由选择题和填空题两种题型组成,直接给出 答案后者对每个习题的解答给出了完整的过程。 本书概念清晰,习题覆盖面广,既收集了较容易的题目,也收集了难度适中和较高难度的 题目,如一些高校计算机专业招收硕士研充生的《数据结构》试题 本书可作为计算机专业本、专科学生的学习参考书也是报考计算机专业硕士研究生的 生必读参考书还适用于自学考试的读者和计算机等级(三级或四级)考试者研习。 所有 封面贴有消华大学出版社激光防伪标签,无标签者不得进入各书店 书名:数据结构习题与解析(C语言篇) 作者:李春葆 出版者:清华大学出版社(北京清华大学校内,郎编100084) http://www.tup.tsinghuaedu.cn 印刷者:北京门头沟胶印厂 发行:新华书店总店北京科技发行所 开本:787×10921/16印张:22字数:535千字 版次:2000年1月第1版2000年1月第1次印剧 印数:00001~5000 书号:IsBN7-302-03786-8/TP·2200 定价:28.00元

前言 计算机编程中加工处理的对象是数据.而数据具有一定的组织结构,所以学习编写计算 机程序仅仅了解计算机语亩是不够的,还必须掌握数据组织、存储和运算的一般方法,这便 是数据结构课程中所学习和研究的内容,也是我们编写讨算机程序的重要基础,由于它对计 算杋学科起到承前启后的作用.因此本课程被列为计算机等相关专业最重要的专业基础课 程 由于数据结构的原理和算法较抽象而该课程一般在车科低年级开设,对于具有一些计 算机程序没计知识的初学者,理解和掌握其中的原理就困难了。在解答数据结构习题时,往 往感到无从下手,作者在多年的教学中感受颇深,本人通过长期的实践收集与整理编写了 这本《数据结构习题与解析》一书,其目的是:通过对习题的解答.使学生充分掌据数据结构 的原理以及求解数据结构问题的思路与方法深化对基本概念的理解,提高分析与解决问题 的能力 本书遵循数据结构课程的教学大纲的要求,从内容上分为13章:第1章是概述,讨论数 据结构的基本概念及相关题解:第2章是颇序表,讨论基本顺序表即向量,栈和队列的基本 内容及相关题解;第3章是链表讨论各种链表的基本内容及相关题解;第4章是串,讨论串 的基本内容及相关题解:第5章是数组和稀疏矩阵,讨论数组和稀疏矩阵的基本内容及相关 题解:第6章是递归,讨论基本递归设计方法及相关题解;第7章是广义表,讨论广义表的基 本内容及相关題解:第8章是树形结构,讨论树和二叉树的基本内容及相关题解:第9章是 图,讨论图的基本内容及相关题解;第10章是查找讨论基本查找方法及相关题解;第11章 是内排序,讨论基本内排序方法及相关题解;第12章是文件、讨论基本文件组织结构及相关 题解:第13章是外排序讨论基本外排序方法及相关题解 每章的内容介绍与习题相关,精选了该章所讨论的数据结构的慨念、存储方式和基本运 算每章的题解分为基本题和习题解析两部分,前者由选择题和填空题兩种题型组成由于 这部分习題是一些基本概念方面的题目·阝中只给出答案;习題解析是对每个习题的解答并 给出求解思路和解答的完整的过程这部分内谷中包含一些难度较大的习题,也包含一些高 校计算机专业招收硕士研究生的数据结构试题,这部分习题前面加有”*”号书中介绍的程 序在 Turbo'系统中调试通过 本书习题覆盖面广,既收集了较容易的题日,也收集了难度适中和较商难度的题日:因 此.本书不仅叮以作为计算机专业本、专科生数据结构课程的学参考书·也是报考计算柷 专业硕士研究生的考生必读复习书同时遹合于数据结构课程自学者和计算机等级(一级或 四级)考试者研习 在編写乍书时,作者勹求从方法上提高解題的能力例如·递归间题是学生较难理解的 知识点,但在计算机专业知识中又经常遇到的问题.为此,作者专门编写了递归一章较深人 地分析∫递引的执行过程,提出了从递归模型到递归设计的步骤.在其他几章中,也采用了 类似的解题方法 由于习題较多,解答上叮能在不够完整和统漏之处·内谷编排上也叮能存在不够合理 的地方,敬请厂大读者批评指山 作者 19:9.8

目录 第1章概述 自自,·,鲁面自 …(1) 1.1基本概念 (1) 1.1.1数据结构… 1.1.2存储方式…………………………………… 1.1.3算法及其评价 …(3) 1.2基本题…………………………………… ………(5) 1.2.1单项选择题………………… 香着香4B4普看B音B普看,着BB普看普着B鲁看普 (5) 1.2.2填它题(将正确的答案填在相应的空中)…… 1.3习题解析 第2章顺序表 s(14) 2.1基本概念和运算 14) 2.1.1向量…… 14) 找 (16) …(18) 2.2基本题… 2.2.1单项选择题…… 2.2.2填空题(将正确的答案填在相应的空中) 2.3习题解析…… 2.3.1向量 2.3.2栈……… 2.3.3队列 第3章链………………… (47) 3.1基本慨念和运算…… 31.1单链表 3.1.2双链表……………………………………………………………(52) 3.1.3链找和链队 56 3.2基本题 32.1单项选择题 …(59) 3.2.2填空题(将正确的答案填在相应的空中 3.3习题解析………… 33.1单链表……… 3.3.2双链表…………… 第4章串 (94) 1.1串的存储及其运算…………………………………………

4,1.1顺序存储及其基本运算… 41.2链接存储及其基本运算…………………… 4.2基本题……… (101) 4.2.1单项选择题…………………………… …(101) 4.2.2填空题(将正确的答案填在相应的空中)………… 4.3习题解析… (102) 第5章数组和稀疏矩阵…… (118) 5.1基本概念和运算…… 5.1.1多维数组…… (118) 5.1.2稀疏矩阵……… 5.2基本题 …(126) 5.2.1单项选择题(其中A[i.门表示下标从i到j)… 5.2.2填空题(将正确的答案填在相应的空中) …(128) 5.3习题解析……… …………(129) 第6章递归………………………(148 6.1递归设计方法……… (148) 6.1.I递归模 …→………“…“…·…t·…“*…(148) 6.1.2递归的执行过程………………………… ………(148 6.1.3递归设计 由非省+aa在_aa命帝要导帝 …(149) 6.1.4递归到非递归的转换………………………(149 2基本题… 15 6.2.1单项选择题………… 6.2.2填空题(将正确的答案填在相应的空中 (152) 6.3习题解析…………… (154 第7章广义表… ………(179) 7.1广义表的表示及其运算…… …………(179) 7.1.1广义表的表示 q由s,d新,,、,,B,, 7.1.2广义表的基本运算………… 7.2基本题 183) 7.2.1单项选择题…………………………………………(183) 7.2.2填空题(将正确的答案填在棉应的空中) (184) 7.3习題解析 丶(185) 第8章树形结构…………………………… ……(196) 8.1基本概念和运算…………… 〔196 8.1.1树 8.1.2二叉树………………… 8.1.3二叉排序树 中上p护主国音帝业带面 8.1.4树和森林………… (206)

8.1.5 Huffman树…… 垂dd垂 8.2基本题……………………… 82.1单项选择题………… …(208 8.2.2填空题(将正确的答案填在相应的空中) …(213) 8.3习题解析 ……(219) 第9章图…… (264) 9.1图的存储及其运算 (264 9.1.1图的基本术语 (264) 9.1.2图的存麟方式 9.1.3图的基本运算 (269) 9.2基本题 9.2.1单项选择题… (277 9.2.2填空题(将正确的答案填在相应的空中) (279) 9.3习题解析… (279) 第10章查找 (291) 10.1基本查找方法 (291) 10.1.1顺序查找 10.1.2二分查找 10.1.3分块查找……… 1寻甲中,中、由 10.1.4哈希表查搜…… (294) 10.1.5背包问题及其求解函数 10.2基本题 0.2.1单项选择题… (299) 10.2.2填空题(将正确的答案填在相应的空中)…………………………………………(300) 10.3习题解析… (301) 第11章内排序……………… …(313) 11.1基本排序方法 (313 11.1.1插入排序 313 11.1.2希尔(Shel排序………… 3l4 11.1.3起泡排序… (315) 11.1.:快速排序 (315) 11.1.5选择排序 (316) 11.1.6堆排序 11.1.7归并排序… 11.1.8基数排序………… (319) 11.2基本题……… 11.2.1单项选择题………… 11.2.2填空题(将止确的答案填在相应的空中) 11.3习题解析… (323)

算12章文件……………………………………… (335) 12.1基本文件组织方式…………………………… 2.1.1顺序文件… 12.1.2索引文件………………………… 2.1.3直接存取文件 12.1.4多关键字文件……… (337) 122基本题 122.1单项选择题…… (337) 12.22填空题(将正确的答案填在相应的空中 (338) 12.3习题解析…………………………… (338 第13章外排序 (344) 131基本归并排序法…… ……(344) 131.1磁盘文件归并排序…… 中和虚 (344) 13.1.2磁带文件归并排序 346) 132基本题 13.2.1单项选择题 13.2.2填空题(将正确的答案填在相应的空中 13.3习题解析………………… (348) 参考文献… (353)

第1章概述 自从1946年第一台计算机问世以来,计算机技术的发展日新月异。其应用已不再局限 科学计算,而是更多地用干控制、管理及数据处理等非数值计算的处理工作,与此相应,计 算机加工处理的对象由纯粹的数值发展到字符、表格和图像等各种具有一定结构的数据数 据结构就是研究数据组织、存储和运算的一般方法的学科。本章讨论数据结构的基本概念及 相关题解。 1.1基本概念 数据是信息的载体,在计算机科学中是指所有能输入到计算机中并由计算机程序处理 的符号的总称。 1.1.1数据结构 数据结构是指同一数据元素类中各数据元素之间存在的关系。数据结构又可以分为下 述三个组成部分,它们分别是数据的逻辑结构数据的存储结构和数据的运算 数据的逻辑结构是对数据之间关系的描述,所以有时就把数据的逻辑结构简称为数据 结构。逻辑结构形式上用一个二元组 B=(KR) 来表示,其中K是结点即数据元素的有限集合,即K是由有限个结点所构成的集合,R是K 上的关系的有限集合即R是由有限个关系所构成的集合而每个关系都是从K到K的关 系。设r是一个K到K的关系,r∈R,若k,k∈K,且∈r,则称k是k的后续,k是 k'的前驱,这时k和k是相邻的结点(相对r而言);如果不存在一个k使∈r,则 称k为r的终端结点;如果不存在一个k'使∈r,则称k为r的开始结点;如果k既 不是终端结点也不是开始结点,则称k是内部结点。 数据的存储结构是数据的逻辑结构在计算机存储器中的实现,逻辑结构是从逻辑关系 上观察数据,它与数据的存储无关,即独立于计算机,而存储结构是依赖于计算机的计算机 存储器是由有限多个存储单元组成的,每个存储单元有唯一的地址,各存储单元的地址是连 续编码的每个存储单元Z都有唯一的后续单元Z=suc(Z),Z和Z’称为相邻单元。一片 相邻的存储单元的整体叫做存储区域,记做M。把B存储在计算机中,首先必须建立一个从 K的结点到M的单元的映象S:K→M即对于每一个k∈K,都有唯一的Z∈M使得S(k ZZ为K中结点所占存储空间中的起始单元。通常有四种基本的存储映象方法,即顺序方 法,链接方法、索引方法和散列方法 数据的运算是在数据的逻辑结构上定义的操作算法,如检索、插入、删除、更新和排序