李春葆数据结构习题与解析

所需积分/C币:35 2013-11-16 12:50:28 4.51MB PDF
收藏 收藏
举报

李春葆:数据结构习题与解析(C语言版)pdf有数据结构所有讲解以及习题 习题解析
(京)新登字158号 内容提宴 本书根据效据结构课程的教学大纲的耍求提供了作者多年教学中积、收集与验证的 有关数据结构的基本内容及相关题解。全书共分13章每章先啥出内容概述蠡后出该章 的题解,題解分为基本题和习题解析两部分前者由选择题和填空题两种题型组成,直接给出 容案后者对每个习题的解答给出了完整的过程 本书概念清晰,习题盖面广,既收集了较容易的题目,也收集了难度遹中和较高难的 题目如一些高校计算机专业招收硫土研究生的《数据绪构】试题 本书可作为计算视专业本,专科学生的学习参考书,也是报考计算凯专业硕士研究生的 考生必读参考书还造用于自学专试的读者和计算机等级(三级或四级)考试者研习 配权所有版必究。 本书封面附有新华火学出版社激兰防伪标签,无标签者不得嫌入各书店。 书名:数据结构习题与解析C语言篇 作者:李春葆 出版者:清华大学出版社(北京清华大学校内,邮编10084) http://www.tup,tsinghuaedu,cn 印剧者:北京门头沟胶印厂 发行:新华书店总店北京科技发行所 开本:787×1092116印张:22宇数4535千字 版次:2000年1月第1版200年1月第1次印刷 印]数:0001~5000 书号:IBN73902-03786-8/TP·220 定价:28.0元 计算机编程中加工处理的对象是数据而数据具有一定的组织结构,所以学习编写计算 机程序仅仅∫解计算枧语是不够的,还必须掌握数据组纵、存储和运算的一般方法,这便 是数裾结构课中所学习和研究的内谷,也是我们綱写计算机程序的重要基础,由于它对计 算机学科起到承前后的作用,因此本课程被列为计算机等相关专业最重要的专业基础课 得 由于欻据结树的婛理科箅法较抽象、而该课程一般在卒科低年级开设,对于具有一些计 算机程序设计知识的初学者理解和掌握其中的原理就困难了。在解答数锯结构习题时,往 往感到无队下予,作者冇多伻的教学卬慼受颇滐,夲人通过长期的实践.收集与整理编写了 这本《数据结构习题与解析》一书、其目的是:通过对习题的解答使学生充分掌据数据结构 的原理以及求解数据结构问题的思路与方法,深化对基木概念的理解,提高分析与解决问题 的能力 本遵循数据结构课程的教学大纲的要求从内容上分为13章第1章足慨述,讨论数 据结构的基本概念及相关题解:第2章是顺序表,讨论基本顺序表即向量、栈和队殘的基本 内容及相关解第3章是链表,计论各种链表的基本内容及相关题解;第4章是中,讨论串 的基本内容及相关题解:第莎章是数组和稀疏矩阵讨论数组和稀疏矩阵的基本内容及相关 题解:第6章是递讨论基本递归设计方法及相关题解;第7章是广义表,讨论广义表的基 本内睿及相关题解:第8章是树形结构讨论树和二叉树的基本内容及相关题解:第9章是 图讨论图的基本内谷及悒关题解第10是查找讨论基木奁扰方法及相关题斛;第11章 是内排序,讨论基木内排序方法及柜关题解:第12章是文件,讨论基本文件组织结构及相关 题解:第13章是外排序,讨论基本外排序方法及相关题解。 每章的内容介绍与以题相关精选了该章所讨论的数据靖构的慨念、存储方式和基本运 算莓章的题解分为基小题和题解析两部分前者由选择题和填空题两种题型组成,由于 这部分习題是-些基和慨念卢面的题日.民中只给出答案;題解析是对每个习趣的解答并 给出求解思路和解答的完整的过这部分內寳中包含一些难度较大的习题,也包含·些高 恔计算机专业招收硕上研究生的欻据结构试題、这部分习题前面加有“”号,书中介绍的程 序在 Turbo c系统调试通过 本书习题覆盖面「、既收集了较容易的题H也收集了难度和较高难度的题日。因 此.本书不仅叮以作为计算机校业本、专科生数锯结构课程的学习参考书·也是报考汁算机 专业硕上研究生的考卡必读复习书同时通合于数据结构课程自学者和计算机等级(一级或 四级)专试者研以 在鏑写乍书时作者力求从方法上提高解騵的能力,例如,递归问题是学生较难理解的 知识点,但在计算机欤收知识中又经常遇到的问题为此作者专门编写了递乐一章较深人 地分所∫递的执行过提出∫从递刂模型到递刂设计的步骤。在其他几音中,也采用∫ 关似的解题力法 杄」題较多.解誶丨旴能忭仼不够整利疏漏处,内容绗排上也叮能冇在小够合理 的地方,敬请了大读者批评指t 作者 19:5 录 第1章概述 1··卩『甲·■;··日●甲;日·即·日■·■日1·■·唱司即D■■■唱身口聊■日鲁■■■●唱p即■口b■■p·自■b■自血自pD 1) 基4概念 1.1.1数据结构 …………(1) 1.1.2存诸方式…………………………………………………………(2 1.1.3算法及其评价MA"44!MA(3) 1.2基本恶·………*………………s……"…s……"……""……(5) 单选择题 1.2.2填魎(将正确的答案填在相应的室中)…… ( l.3习题解析 ……(8 第2章顺序表 (14) 2.1基木概念和运算……………………+4**(14 21.1问t………19 2.1.2钱…………sw……………………………………………………(16 2.1.3队列…………”…"”……*"…"…r*…" 22基本题………………………………………………"………(2c) 2.2.1单项迷择题………………………………… ■■■■ ………"…………(2C 2.2.2填空题将正确的答案填在相应的空中 D 23习题解析……………………23) 3.1向量 幽咖■自●自自■看血咖自咖上■● 2.3.2找……………………………… 4b44+++.+4(28) 3.3队列 ↓■·■d·如自bb司↓●h↓b山b●bt t 4441431441846831161444181841144(35) 第3量链表 跏■咖■q■咖●·咖●『即●司 ………(47) 3.1基本慨念和运算…………”;……… 〔47 3.1.1单链表… 鲁D导中省 ■■■■西■ hL{47) 3.1.2链表…………… ■■■■■■省口■口■ 郾■_pb郾L4b看■p甲看卩L■品甲■■■■品■■■■口备■■ (52) 3.1.3链栈和链队… 〔56 3.基本题…… ■L■■口口山L自d血 〔59〕 单项选择题 ………………………………〔59) 3.22填空题(将正确的答裳填在相应的空中 甲鲁P■曾■■日自日日■ 口■通b (62〕 3.3习题解析………… =======.44·品B自4吾日目鲁 64 3.3.1单链表 口■■■唱口■■■■口一■ 〔64 3.3.9以链表………-……………………… 〔7〕 第4章串…………………………"""(94 1,1毕的存媚及其运 4 百录 41.1顺序存储及其基本运算……………………"",……””…(94) 1.].z链接存储及其基本运算…Mb P■■鲁鲁■■自■■■■鲁噜■■自血 97 42基本题…………………………………1…4101) 生.2.1单项选择题 ■嗇斷■酽■■■斷鱼鲁自幽■自■個酽■鲁■■自自會■■■■血血自■鲁鲁■■會自备■個自鲁自■■备■血■T會自會【會◆曾P (101 生.2.2填空题(将正确的答填在相应的空中)……………4t(101) 43习题解恬………………………………(102) 第5章数组和矩阵 罪p鱼自即口自即口即自■■罪自■b十 a(118) 51基本慨念和运算 山聊■■■■面 ■d● h…b口4如4(皇18 51.1多锥数组 〔118) 5.12稀蔬矩阵…… 〓■■昌哂b尋db看·■罪罪■p即晶 命血“…(20 基本题……*4幽…*“"…s!…"…,………k…….(126) 5.2.1单项选择题〔其中A[,门表示下标从i到jM(126) 5.2.2填空题〔将正确的答案填在相应的空中)…….4(28 5.3习题解析 唱口自如咖血司日即即■■命■聊■●D■■鲁■■■自■■■·■會凸■■■晋會目·日曾P會早◆曾會·F 〔k29) 第6章递归 ■■‘凸■■晷看■▲即看易唱■4昌昂唱↓聊自看 bp咖司即■山b●●b最看 (148) 6.2道归设计方法 ■■福b山■■+普■P番 昏甲【冒■日 ▲*【r4R) 6.1.I递归模型……· r:!r!-……--(148) 61.2递归的执行过程…… 中自咖血■■司 a4卜!"(148 6.13递归设计 血■命命■●驴●■■馨 (149 6.1.4遵归到非递归的转换……………-….…...s"!"(148) 62基本题 ■■命血—自·■■血曹■P冒 中■日甲 44〔L51 6.2.1单项选择…………………+4*+w(151) 6.22填空题〔将正确的答案填在相应的空中)……… 幽斗女圆(152 6.3习题解析 (154 第7章广义衰 曝■■bp■p甲d司司■ ………………………………………"""(179) 7.1广义表的表示及其运算………,……………t,f(E79) 7.1.1广义表时表示·…… 1■血血画■血■■幽■血血曲■ 7.1.2广义表的基本运算 …r……-…(180 2基题…,………………""(183 7.2.1单项选择题… ↓山凸■b晶■↓山■哥日币山着■■↓即■看↓聊■■■易■■小■■■ 幽〔I83 7.22填空题将正确的答案填在相应的坐中)………………(84) 73习题解析◆·:………! 看司听司■即罪■■↓聊目口■血■自自日會會自即国自■早国曾?甲即 185〕 第8章树形结构………(19) g,1基本概念和运算°… ●[■ 命a·自Ⅱb〔196〕 8,1树….…………………………"s"sa,! +.FB+F+rTw,r:(196) R.]2二叉树… ■看品■■●国◆卧自司命和 …““限""(198) 8.1.3二义排序树………………6203 民.14树和森林 s·(206) 目录 8.1-5 Huffman忖…………," ■罪會■b …(20? 82基本题 208〕 8.2.]单选择题 ……………………………………"…t208 8.22填空题(将正确的案填在相应的空中)………4144(213〕 B、3习题解析 …………(21 第9章图 會會曾‘會會P會■會會甲■■_鲁個曾「■會?曾号鲁■冒■4日日·上冒?■■■曾 P自自冒甲甲 -〔264) 9.1图的存储及其运算……64 5.L.]图的基本术语 ……"……h…h4(261) 9.1.2图的在巒方式…… ■t晋LL■■4■ ……25 9.1.3图的基太运算 出-▲(26 9.2基本题……-…… T■管山4}P■晶44h■早■■■■■■晶■ 9.2.1单项选择题 …-………"(277) 9.2.2填空題(将正确的答案坝在相应的空中 +(275 9.3习题解析… 昏■■噜自■■看4會4鲁■會自自_P噜早血L自鲁PP日命日■會早早日鲁 279 第10章查我 〔291) 10,1基本查找方法M**W!(291) 1Q.1.I顺序查投… ■■↓L■暴 …s…"(291 0.1.2二分查扰……………r 10.1.3分块查找“………………… ■口口■會 293 ](.1.4哈希表查找…………………x….r,h(29 10.1.5背包可题及其求解函数 (296〕 10.2基木题… 4点国(299 10.2.l单项选择 bb↓bBb↓L “…t"""“……(〔299) 10.2.2填空题(将确的答案坞在桕应的空中 ………………4…,……(aOU 10.3习题解析… 〔301 第11章内排序 …4s(313 11.1基本排序方法 ……………(13) 11.1.1插入排存 ……"…,…x…r"……"·〔313 l1.1.2希尔ll排序…"… 血■ 4[34 11.1,3起泡排序… 4·(3l5) 11.1.!快速排厅·… 3l5) 11.【.选择排序…“"…"……”〔316) 堆排 〔317 1.2.7归并排序…… ………….……(318 11.1.8基数排序 ■d■■■1冒 而m口■『■冒ba■ F■【 (39 11.2基本题 』●d■■电聊■面身■日目■■■■4b↓■4司p看h■晶晶晶■■■■晋■P■會■自看P导■自■目目日萨导 〔32C 11.2.1单颂先择题· ■■■p口●■p4p唱■■b咖即■■斷■■■■■■■↓■甲晷卜1中 320 11.2.2填空题(将正确的答案填在根应的空中) 322〕 11.3丁题解析"… 323 第12章文件……………………-…-…" (335) 12.1基本文件组织方式",!411"t--……w(335) 12.1.1版序文件………………………………x-…(335) 12.1.2索引文件……… 早十P早P早告-4管目宁日P看鲁 1(35) 12.1.3直接存取文件4… 〔337} 12.1.4多关键字文件………………………………………”…*(337) 122基本题 ■■■■■鲁■即■■音口■■■烟 血甲甲p罪中中甲 咖D唱中■园即 337 12.21单项选择题 :s“〔337 12.2.2填空题(将正确的答案填在相应的空中)……………………………(33 123习题解析……:"…………………-……:…………………33) 第13章外排序 ▲■■■凸■凸晶山 ……(344 131基本归并排序法……44) 13.1.1磁盘文件归并排序 ●罪命4p即■■咖p●命命口pq■●中命口■血 ·B··!单“〔344) 13.1.2磁带文件归并操序…………………(346) 132基本题……………………………,…………………………………………(348〕 13.2.1单项选择题…… 吧甲甲零甲可早鄂唱唱甲零 m〔348) 13.22填空题《将正确的答案填在相应的空中〕M"M·(348) 13.3习题解析…………n,…m-…(348) 参多文献 “(353) 第1章慨述 第1章概述 自从1946年第一台计算机问世以来讨算机技术的发展日新月异。其应用已不再局限 于科学讦算,而是更多地用于控制、眢理及数据处理等非数值计算的处理工作与此相应,计 机加工处理的对象由纯粹的数值发辰到字符、表格和图像等各种具有一定结构的数据数 据结构就是研究数据组织、存储和运算的一般方法的学科,本章讨论数据结构的基本概念及 桕关题解 1.!基本概念 数据是信息的载体在计算机科学中是指所有能输入到计算机中井由计算机程序处理 的符号的总称 1.1数据结构 数据特构是指同一数据元素类中各数据元素之问存在的关系。数据结构又可以分为下 述三个组成部分,它们分别是数据的逻辑结构数据的存储结构和数据的运算。 数据的逻辑结构是对数据之间关系的措述,所以有时就把数据的逻辑结构简称为数据 吉构、逻辑结构形式上用一个二元组 B=(K,R〕 来表示,其中K是结点即数据元素的有限集合,即K是由有限个结点所构成的集合R是K 上的关系的有限集合,即R是由有限个关系所构成的集合,而每个关系都是从K到K的关 系。设r是一个K到K的关系,r∈R,若k,k∈K,且<kk>∈r则称k是k的后续,k是 k'的前驱,这时k和k是相邻的结点(相对r而吉);如果不存在一个k'使<kk'>∈r,则 称k为r的终端结点;如果不存在一个k使<k',k>∈r,则称k为r的开始结点;如果k既 不是终端结点也不是开始结点则称k是内部结点 数据的存储结构是数据的逻辑结构在计算机存储器中的实现,逻辑结构是从逻辑关系 上观察数据,它与数据的存储无关,即独立于计箅机,而存储结构是依赖于计算机的计算机 存储器是由有限多个存储单元组成的每个存储单元有唯一的地址,各存储单元的地址是连 续编码的每个存储单元Z都有唯一的后续单元Z'=suc(Z),Z和Z称为相邻单元。片 相邻的存储单元的整体叫做存储区域,记做M。把B存储在计算机中首先必须建立一个从 K的结点到M的单元的映象SK→M即对于每一个k∈K,郁有唯一的z∈M使得S(k)= Z.Z为K中结点所占存储空间中的起始单元。通常有四种基本的存储映象方法,即顺序方 去链接方法、索引方法和散刘方法。 数据的运算是在数据的逻辑结构上定义的操作算法,如检索插入、删除、更新和排序

...展开详情
试读 127P 李春葆数据结构习题与解析
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    李春葆数据结构习题与解析 35积分/C币 立即下载
    1/127
    李春葆数据结构习题与解析第1页
    李春葆数据结构习题与解析第2页
    李春葆数据结构习题与解析第3页
    李春葆数据结构习题与解析第4页
    李春葆数据结构习题与解析第5页
    李春葆数据结构习题与解析第6页
    李春葆数据结构习题与解析第7页
    李春葆数据结构习题与解析第8页
    李春葆数据结构习题与解析第9页
    李春葆数据结构习题与解析第10页
    李春葆数据结构习题与解析第11页
    李春葆数据结构习题与解析第12页
    李春葆数据结构习题与解析第13页
    李春葆数据结构习题与解析第14页
    李春葆数据结构习题与解析第15页
    李春葆数据结构习题与解析第16页
    李春葆数据结构习题与解析第17页
    李春葆数据结构习题与解析第18页
    李春葆数据结构习题与解析第19页
    李春葆数据结构习题与解析第20页

    试读已结束,剩余107页未读...

    35积分/C币 立即下载 >