目录 第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,且<k,k>∈r,则称k是k的后续,k是 k'的前驱,这时k和k是相邻的结点(相对r而言);如果不存在一个k使<k,k>∈r,则 称k为r的终端结点;如果不存在一个k'使<k',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中结点所占存储空间中的起始单元。通常有四种基本的存储映象方法,即顺序方 法,链接方法、索引方法和散列方法 数据的运算是在数据的逻辑结构上定义的操作算法,如检索、插入、删除、更新和排序