数据结构与算法
第十章索引技术
任课教员：张铭
https://www.doczj.com/doc/ac11938068.html,/mzhang/DS/
mzhang@https://www.doczj.com/doc/ac11938068.html, 北京大学信息科学与技术学院网络与信息系统研究所?版权所有，转载或翻印必究
北京大学信息学院
?版权所有，转载或翻印必究
Page 2
主要内容
10.1 线性索引 10.2 静态索引 10.3 倒排索引 10.4 动态索引
10.5 动态、静态索引性能比较
北京大学信息学院?版权所有，转载或翻印必究Page 3基本概念
输入顺序文件 主码与辅码
索引与索引文件
稠密索引与稀疏索引
北京大学信息学院?版权所有，转载或翻印必究Page 4
输入顺序文件
输入顺序文件( entry-sequenced file )按照记录进入系统的顺序存储记录
一般说来,输入顺序文件的结构相当于一个磁盘中未排序的线性表
因此不支持高效率的检索
北京大学信息学院?版权所有，转载或翻印必究Page 5主码
主码( primary key )是数据库中的每条记录的唯一标识
例如，公司职员信息的记录的主码可以是职员的身份证号码
如果只有主码，不便于各种灵活检索
北京大学信息学院?版权所有，转载或翻印必究Page 6
辅码
辅码( secondary key )是数据库中可以出现重复值的码
辅码索引把一个辅码值与具有这个辅码值的每一条记录的主码值关联起来
大多数检索都是利用辅码索引来完成的
北京大学信息学院
?版权所有，转载或翻印必究
Page 7
索引
索引( indexing )是把一个关键码与它对应的数据记录的位置相关联的过程
索引技术是组织大型数据库的一种重要技术
数据库组织存储在外存中的大量记录
高效率的检索
插入、更新、删除
北京大学信息学院
?版权所有，转载或翻印必究
Page 8
索引文件
索引文件( index file )是用于记录这种联系（关键码与它对应的数据记录的位置）的文件组织结构。 索引文件的记录
（关键码，指针）对
指针指向主要数据库文件（也称为“主文件”）中的完整记录
北京大学信息学院?版权所有，转载或翻印必究Page 9索引文件
索引文件并不需要重新排列记录在磁盘中的顺序（不用重排主文件）
一个数据库可能有多个相关的索引文件
每个索引文件往往支持一个关键码字段
可以通过该索引文件高效访问记录中该关键码值
北京大学信息学院
?版权所有，转载或翻印必究
Page 10
稠密索引
对每一个记录建立一个索引项，这样建立的索引被称为稠密索引( dense index )
数据库文件中的记录不按照关键码的顺序排列时（比如按照加入的顺序排列）
北京大学信息学院?版权所有，转载或翻印必究
Page 11
稀疏索引
对一组记录建立一个索引项，这种索引称之为稀疏索引( spare index )
当记录在磁盘中是按照关键码的顺序存放
可以把记录分成多个组（块）
稀疏索引索引项的指针指向的是这一组记录在磁盘中的起始位置
北京大学信息学院?版权所有，转载或翻印必究Page 12
10.1 线性索引
基本概念
线性索引的优点 线性索引的问题 二级线性索引
北京大学信息学院?版权所有，转载或翻印必究Page 13基本概念
线性索引(linear index)的索引文件
一组简单的关键码(key)/指针(pointer)对的序列
北京大学信息学院?版权所有，转载或翻印必究Page 14
基本概念（续）
线性索引文件按照关键码的顺序进行排序
文件中的指针指向存储在磁盘上的文件记录起始位置或者主索引中主码的起始位置
37
55
73
92
92 73 37 55 线性索引文件
数据库记录
北京大学信息学院?版权所有，转载或翻印必究
Page 15
基本概念（续）
线性索引的索引文件
存储在内存中，把索引存储在内存中能大大地提高检索速度 存储在磁盘中
根据线性索引的文件大小和内存的空间限制
北京大学信息学院
?版权所有，转载或翻印必究
Page 16
线性索引的优点
对变长的数据库记录的访问 可以对数据进行高效检索
二分检索
顺序处理
比较操作
批处理的操作
节省空间(相对其它索引结构)
北京大学信息学院?版权所有，转载或翻印必究
Page 17
线性索引的问题
线性索引太大，存储在磁盘中
在一次检索过程中有可能多次访问磁盘，从而影响检索的效率 解决办法：使用二级线性索引
更新线性索引
在数据库中插入或者删除记录时
北京大学信息学院
?版权所有，转载或翻印必究
Page 18
二级线性索引
每一条二级线性索引记录对应于一个一级线性索引文件的磁盘块
关键码的值与对应的线性索引文件的磁盘块中第一条记录(从物理位置上看的第一条)的关键码的值相同
记录中的指针则指向相应线性索引文件的磁盘块的起始位置
北京大学信息学院?版权所有，转载或翻印必究
Page 19
二级线性索引
例如，磁盘块的大小是1024字节，每个关键码／指针记录需要8个字节
1024 / 8 = 128
每磁盘块可以存储128条这样的记录
假设线性文件索引中包含10000条记录
10000/128 = 78.1
那么一级线性索引占用79个磁盘块
相应的，二级线性索引文件中有79项记录
北京大学信息学院?版权所有，转载或翻印必究Page 20
二级线性索引的例子
关键码与相应磁盘块中第一条记录的关键码的值相同
指针指向相应磁盘块的起始位置
1
2003
5744
10723
1
2002 2003 5583 5744 9297 10723 13293
……
……
二级索引
线性索引 磁盘块
北京大学信息学院
?版权所有，转载或翻印必究
Page 21
二级线性索引检索
在检索时，线性索引文件并不被读入内存，被读入内存的是二级线性索引文件
由于二级索引往往存储内存，通常只需要访问两次磁盘即可：一次读入线性索引文件，一次读入数据库记录
北京大学信息学院
?版权所有，转载或翻印必究
Page 22
二级线性索引检索的例子
例如，检索关键码为2555的记录
首先在内存中的二级线性索引文件中找到关键码的值小于等于2555的最大关键码所在的记录——关键码为2003的记录
根据记录中的指针找到其对应的线性索引文件的磁盘块，并把该块读入内存
按照二分法对该块进行检索，找到所需要的记录在磁盘上的位置
最后把所需记录读入，完成检索操作
北京大学信息学院?版权所有，转载或翻印必究
Page 23
10.2 静态索引
10.2.1 多分树
10.2.2 ISAM
北京大学信息学院
?版权所有，转载或翻印必究
Page 24
基本概念
静态索引
索引结构在文件创建、初始装入记录时生成
一旦生成就固定下来，在系统运行(例如插入和删除记录)过程中索引结构并不改变
只有当文件再组织时才允许改变索引结构
北京大学信息学院
?版权所有，转载或翻印必究
Page 25
10.2.1 多分树
组织索引一般不用二叉树而采用多分树
大大减少访问外存的次数
北京大学信息学院
?版权所有，转载或翻印必究
Page 26
多分树图例
二叉树转换成多分树
北京大学信息学院?版权所有，转载或翻印必究Page 27上图访问一个叶结点
查找二叉树——访问六次外存 查找多分树——访问两次外存
北京大学信息学院?版权所有，转载或翻印必究Page 28
结点更大
以更少的外存访问次数来完成查找 需要较大的缓冲区
读入一个结点也需较多时间
一个结点最好能放在一个磁盘块中
北京大学信息学院?版权所有，转载或翻印必究Page 29
“数据基本区”
多分树的叶结点区域 存放数据记录
“索引区”
多分树的非叶结点区域
存放各子树结点中的最大(或最小)的关键码
北京大学信息学院
?版权所有，转载或翻印必究
Page 30
溢出、溢出区
新记录要插入的结点已满
把溢出的记录存放到另开辟的溢出区
不改变索引的结构
记录送入溢出区的两种方式
保持顺序，把最后一个记录送往溢出区
不保持顺序，把新插入的记录送入溢出区
北京大学信息学院?版权所有，转载或翻印必究Page 31
10.2.2 ISAM
ISAM是解决需要频繁更新的大型数据库的一个早期尝试
在采用基于B +树的VSAM技术之
前，IBM公司曾经广泛地采用ISAM技术
北京大学信息学院
?版权所有，转载或翻印必究
Page 32
多分树的应用
为磁盘存取而设计 结构采用多级索引
主索引 柱面索引 磁道索引
北京大学信息学院
?版权所有，转载或翻印必究Page 33
400 T 1 625 T 21000 T 3 80 C 1T 0 200 C 2T 0
400 C 3T 0 625 C 6T 0
1000
C 9T 0
T 0 T 1 T 2 T 3 嗫
40 T 1 40 T 1 80 T 2 80 T 2
… C 1
T 0 R 10 R 20 R 30 R 40R 50 R 60
R 70 R 80
嗫
T 1 T 2 T 7
嗫 柱面索引
主索引 基本区 磁道索引溢出区
C 0北京大学信息学院
?版权所有，转载或翻印必究Page 34
150T 1150T 1200T 2
200 T 2
…
890 T 1890T 11000 T 2
1000 T 2
… R 90 R 110
R 120 R 150R 160
R 175
R 190 R 200
R 830 R 840 R 880 R 890R 920
R 930
R 980 R 1000
T 1T 2T 7嗫
T 7
T 2嗫 T 1T 0T 0C 2 C 9
嗫
嗫基本区 磁道索引溢出区
基本区 磁道索引溢出区
嗫 北京大学信息学院?版权所有，转载或翻印必究
Page 35
ISAM 的查找
先查主索引，从主索引查出柱面索引的分布
主索引常驻内存
从柱面索引查出磁道索引的分布
柱面索引放在中间位置的柱面
从磁道索引查出所要找的记录的地址
北京大学信息学院?版权所有，转载或翻印必究Page 36
ISAM 的插入
磁道索引中，索引项的两个子项在记录插入之前是相同的，在插入记录后就要改变
例如，插入R165 以后：
150 T 1
150 T 1
190 T 2
200 T 7
…
北京大学信息学院
?版权所有，转载或翻印必究Page 37
如果有多个溢出记录，则这些溢出记录必须按顺序链接起来，在溢出索引项中是这些溢出记录的最大关键码和具有最小关键码的溢出记录所在磁道号
例如，再插入R168，R166以后：
150 T 1
150 T 1
168 T 2
200 T 6
…
北京大学信息学院
?版权所有，转载或翻印必究
Page 38
如果有多个溢出记录，则这些溢出记录必须按顺序链接起来，在溢出索引项中是这些溢出记录的最大关键码和具有最小关键码的溢出记录所在磁道号
例如，再插入R168，R166以后：
150 T 1
150 T 1
168 T 2
200 T 6
…
北京大学信息学院
?版权所有，转载或翻印必究
Page 39
在溢出区中，除了存放记录以外还存放链指针
柱面索引变化：
150 T 1 150 T 1 168 T 2 200 T 6 …
R 40 R 110 R 120 R 150 R 160
R 165
R 166
R 168
T 1 T 2
T 7
嗫
T 0 嗫
…
R 175 T 6RIII RX 1 P 1 R 200
Λ
RX 3
P 3
R 190 T 7RI
RX 2
P 2 T 6
基本区
溢出区
磁道索引C 2
北京大学信息学院?版权所有，转载或翻印必究Page 40
ISAM 插入的好处
在进一步查找时，容易判断要查找的记录是在基本区还是在溢出区
若在基本区，则指针指出了记录所在的磁道号；
若在溢出区，则指针指出了溢出记录链中第一个(关键码为最小)记录所在的磁道号及在磁道中的相对记录号，沿着该链可以找到要找的记录。
北京大学信息学院?版权所有，转载或翻印必究Page 4110.3 倒排索引
10.3.1 基于属性的倒排
10.3.2 对正文文件的倒排
北京大学信息学院?版权所有，转载或翻印必究Page 42
基本概念
不仅需要按关键码的值查找
还需要按照属性的值来查找记录
北京大学信息学院
?版权所有，转载或翻印必究
Page 43
基本概念
倒排索引——对某属性按属性值建立索引
（属性值，具有该属性值的各记录的地址列表）
不是由记录关键码来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引(inverted index)
这种属性往往是离散型的
对于连续型的索引，往往用B 树
北京大学信息学院
?版权所有，转载或翻印必究
Page 44
基本概念
倒排索引文件
带有倒排索引的文件
简称倒排文件(inverted file)
北京大学信息学院?版权所有，转载或翻印必究Page 4510.3.1 基于属性的检索
基于属性的检索
要求检索结构中某个或若干个属性满足一定条件的结点
北京大学信息学院?版权所有，转载或翻印必究
Page 46
3500
40
电器部
何江
0673
250026玩具部周兵0552250026电器部刘珍0375500047玩具部孙丽022*******服装部王卓020*******食品部王亮020*******服装部张伟0197400039服装部赵亮0193500043食品部刘阳0172400032玩具部李宇0100SAL AGE DEPT NAME EMP#例如，在某百货公司的职工文件中，有如下的记录格式：(EMP#，NAME ，DEPT ，AGE ，SAL)
该记录格式中的数据项其含义分别为职工号，姓名，所在部门，年龄，工资。北京大学信息学院
?版权所有，转载或翻印必究
Page 47
查询实例
对这样的职工文件进行下列类型的查询：（1）简单查询。例如：列出玩具部(即DEPT=“Toy ”)的所有职工记录
（2）范围查询。例如：列出工资在2000元和4000元之间(即2000≤SAL ≤4000)的所有职工记录
（3）逻辑查询。例如：列出玩具部中年龄在50岁以上或者工资在5000元以上的职工记录(DEPT=“Toy ”AND(AGE ≥50 OR SAL ≥5000))
北京大学信息学院?版权所有，转载或翻印必究Page 48
10.3.1 倒排表
倒排表(inverted list) 是基于属性的倒排
在保留原表的同时，对于感兴趣的（即可以用来作为检索参数的）每个属性的可能取值都建立一个称作倒排表的线性表
存放与此属性相对应的所有关键码值
北京大学信息学院?版权所有，转载或翻印必究
Page 49
10.3.1 倒排文件
索引项
一个具体的索引值
一组指针（例如记录的主码）
这些指针分别指向在该属性项上具有该具体值的各个记录
一个倒排表
一个索引项
倒排文件
倒排表组成的索引文件
北京大学信息学院
?版权所有，转载或翻印必究
Page 50
0375,0552********,06730100,01930172,
0201,0221
25003000350040005000
EMP#SAL list 0197,0375,0552
01000193,0204
067301720221020126323940434755EMP#AGE list 0100,0221,05520172,02010193,0197,0204
0375,0673
玩具部食品部服装部电器部EMP#DEPT list 北京大学信息学院
?版权所有，转载或翻印必究
Page 51
10.3.1 基于属性的倒排
列出玩具部(即DEPT=“Toy ”)的所有职工记录。
从关于属性DEPT 的索引中，取出属性值为“Toy ”的倒排表，此倒排表中包合的指针所指向的各记录即为所求。
北京大学信息学院
?版权所有，转载或翻印必究
Page 52
列出工资在2000元和4000元之间(即2000≤SAL ≤4000)的所有职工记录。从关于属性SAL 的索引中，找出属性值在2000与4000之间的倒排表，每个倒排表中含有一个记录指针集合。
对这些集合进行并的运算，其结果集合中包含的指针所指的各记录即为所求。
北京大学信息学院
?版权所有，转载或翻印必究
Page 53
列出玩具部中年龄在50岁以上或者工资在5000元以上的职工记录
(DEPT=“Toy ”AND(AGE ≥50 OR SAL ≥5000))。
先采用类似（1）、（2）的方法，分别找出满足条件DEPT=“Toy ”，AGE ≥50，和
SAL ≥5000的指针集合，然后对后两个指针集合求并，并且将结果集合与第一个指针集合求交，最后的结果集合中包含的指针所指的各记录即为所求。
北京大学信息学院?版权所有，转载或翻印必究Page 54
优点：能够对于基于属性的检索进行较高效率的处理
缺点：
花费了保存倒排表的存储代价 降低了更新运算的效率
北京大学信息学院
?版权所有，转载或翻印必究
Page 55
10.3.2 对正文文件的倒排
正文索引(Text Indexing)处理的就是“建立一个数据结构以提供对文本内容的快速检索”。 方法
词索引(word index)
全文索引(full-text index)
北京大学信息学院?版权所有，转载或翻印必究Page 56
词索引
基本思想：
把正文看作由符号和词所组成的集合，从正文中抽取出关键词，然后用这些关键词组成一些适合快速检索的数据结构。
适用于多种文本类型，特别是那些可以很容易就解析成一组词的集合的文本
适用于英文
不适用于中文等东方文字
北京大学信息学院?版权所有，转载或翻印必究Page 57全文索引
基本思想：
把正文看作一个长的字符串
在数据结构中记录的是子字符串的开始位置
查询就可以针对正文中的任何子字符串
可以对每一个字符建立索引，从而使查询词不再限于关键词
需要更大的空间
北京大学信息学院?版权所有，转载或翻印必究Page 58
词索引使用最广泛
一个已经排过序的关键词的列表
其中每个关键词指向一个倒排表（posting list ）
指向该关键词出现文档集合 在文档中的位置
北京大学信息学院?版权所有，转载或翻印必究
Page 59
40
3470113113
atoll 4351aspen 4529213196623
actor 5622212197199434
abacus 所在位置
所在文档
出现总次数
关键词
倒排文件的全文本索引
北京大学信息学院
?版权所有，转载或翻印必究
Page 60
简化的正文倒排文件
34
11atoll
5aspen 29192actor
22193abacus
所在文档
关键词
北京大学信息学院?版权所有，转载或翻印必究Page 61建立正文倒排文件
第一步，对文档集中的所有文件都进行分割处理，把正文分成多条记录文档。
切分正文记录取决于程序的需要
定长的块、段落、章节，甚至一组文档
北京大学信息学院?版权所有，转载或翻印必究Page 62
第二步，给每条记录赋一组关键词。
以人工或者自动的方式从记录中抽取关键词
停用词(Stopword) 抽词干(Stemming) 切词（segmentation ）
北京大学信息学院?版权所有，转载或翻印必究
Page 63
第三步，建立正文倒排表、倒排文件
得到各个关键词的集合
对于每一个关键词得到其倒排表 然后把所有的倒排表存入文件
记录在每个倒排表在索引文件中开始的位置以及每个表的大小（也可以记录每个关键词的出现次数）
北京大学信息学院?版权所有，转载或翻印必究Page 64
对关键词的检索
第一步，在倒排文件中检索关键词。
第二步，如果找到了关键词，那么获取文件中的对应的倒排表，并获取倒排表中的记录。
通常使用另一个索引结构（字典）进一步对关键词表进行有序索引
Trie
散列
北京大学信息学院
?版权所有，转载或翻印必究
Page 65
倒排文件优劣
高效检索，用于文本数据库系统 支持的检索类型有限
检索词有限
只能用索引文件中的关键词
倒排文件中的索引效率可能不高 需要的空间代价往往很高
北京大学信息学院?版权所有，转载或翻印必究Page 66
10.4 动态索引
10.4.1 B 树
10.4.2 B +树
10.4.3 VSAM
10.4.4 B 树的性能分析
北京大学信息学院?版权所有，转载或翻印必究Page 67基本概念
动态索引结构
索引结构本身也可能发生改变
在系统运行过程中插入或删除记录时
目的
保持较好的性能
例如较高的检索效率
北京大学信息学院?版权所有，转载或翻印必究Page 68
10.4.1 B 树
B 树(Balanced Tree) 一种平衡的多分树
北京大学信息学院?版权所有，转载或翻印必究
Page 69
m 阶B 树的结构定义
(1) 每个结点至多有m 个子结点；
(2) 除根结点和叶结点外，其它每个结点至少有
个子结点；
(3) 根结点至少有两个子结点
唯一例外的是根结点就是叶结点时没有子结点
此时B 树只包含一个结点
(4) 所有的叶结点在同一层；
(5) 有k 个子结点的非根结点恰好包含k-1个关键码。
/2m ????
北京大学信息学院?版权所有，转载或翻印必究Page 70
2. B树的性质
(1) 树高平衡，所有叶结点都在同一层；
(2) 关键码没有重复，父结点中的关键码是其子结点的分界；
(4) B树把（值接近）相关记录放在同一个磁盘页中，从而利用了访问局部性原理；
(5) B树保证树中至少有一定比例的结点是满的
这样能够改进空间的利用率
减少检索和更新操作的磁盘读取数目
北京大学信息学院?版权所有，转载或翻印必究Page 71 18 33
12 23 30
48
24 20 21 31 10 15 45 47 50 52
2-3树
北京大学信息学院
?版权所有，转载或翻印必究
Page 72
B 树的结点结构
B 树的一个包含j 个关键码，j+1个指针的结点的一般形式为：
其中K i 是关键码值，K 1 P i 是指向包括K i 到K i+1之间的关键码的子树的指针。 P 0， K 1， P 1， K 2， P 2， …， P j-1， K j ， P j 北京大学信息学院 ?版权所有，转载或翻印必究 Page 73 B 树结点抽象数据类型 template int n;//子结点的个数//指向父结点的指针BNode //存储关键码的数组，最多有MAXREC 个关键码Key key[MAXREC]; //指向子节点的指针，最多有MAXREC+1个指针BNode }; 北京大学信息学院 ?版权所有，转载或翻印必究 Page 74 template //用于在B 树中检索关键码的数据结构struct Triple{ //指向关键码所在结点的指针BNode //记录关键码在结点中的位置int i; //标识是否检索到了关键码char tag;}; 北京大学信息学院 ?版权所有，转载或翻印必究 Page 75 B 树抽象数据类型(续) template BNode BTree();//构造函数//检索关键码为x 的结点， //检索信息记录在结构Triple 中 Triple 北京大学信息学院 ?版权所有，转载或翻印必究 Page 76 //插入关键码x int Insert(const Key& x);//删除关键码x int Remove(const Key& x);private: //在结点A 中插入关键码x 和指针p int insertkey(BNode //转移结点A 中的部分关键码到结点B 中 int move(BNode 北京大学信息学院 ?版权所有，转载或翻印必究 Page 77 //调整结点的右兄弟和父节点 void LeftAdjust(BNode void RightAdjust(BNode void compress(BNode void merge(BNode 北京大学信息学院 ?版权所有，转载或翻印必究 Page 78 B 树的查找 交替的两步过程 1. 把根结点读出来，在根结点所包含的关键码K 1，…，K j 中查找给定的关键码值(当结点包含的关键码不多时，就用顺序检索；当结点包含的关键码数目较多时，可以用二分检索)， 找到则检索成功； 2. 否则，确定要查的关键码值是在某个K i 和K i+1之间，于是取p i 所指向的结点继续查找。 如果p i 指向外部结点，表示检索失败。 北京大学信息学院 ?版权所有，转载或翻印必究 Page 79 设B树的高度为h 那么在自顶向下检索到叶结点的过程中可能需要进行h 次读盘 北京大学信息学院 ?版权所有，转载或翻印必究 Page 80 B 树的插入 叶结点处在第I 层的B 树，插入的关键码总是在第I-1层 18 33 12 23 30 48 24 20 21 31 10 15 45 47 50 52 插入14 北京大学信息学院 ?版权所有，转载或翻印必究 Page 81 3阶B 树示例 外部结点处在第I 层的B 树，插入的关键码总是在第I-1层 插入14 18 33 12 23 30 48 24 20 21 31 10 14 15 45 47 50 52 北京大学信息学院 ?版权所有，转载或翻印必究 Page 82 插入可能导致B 树朝着根的方向生长 北京大学信息学院?版权所有，转载或翻印必究Page 83插入55,使得包含值50和52的页分裂，把值52提升到父结点 18 33 12 23 30 48 24 20 21 31 10 15 45 47 50 52 北京大学信息学院?版权所有，转载或翻印必究Page 84 55 18 33 12 23 30 48 52 24 20 21 31 10 15 45 47 50 插入55结果 北京大学信息学院 ?版权所有，转载或翻印必究 Page 85 插入引起3阶B 树根结点分裂的例子插入19 18 33 12 23 30 48 24 20 21 31 10 15 45 47 50 52 北京大学信息学院 ?版权所有，转载或翻印必究 Page 86 插入引起3阶B 树根结点分裂的例子 插入19 21 18 33 12 23 30 48 24 19 31 10 15 45 47 50 52 20 北京大学信息学院 ?版权所有，转载或翻印必究 Page 87 插入19 20 30 21 18 33 12 48 24 19 31 10 15 45 47 50 52 23 北京大学信息学院 ?版权所有，转载或翻印必究 Page 88 插入19 20 30 21 18 12 48 24 19 31 10 15 45 47 50 52 33 23 北京大学信息学院?版权所有，转载或翻印必究Page 89 B树插入 注意保持性质，特别是等高和阶的限制 1) 找到最底层，插入 2) 若溢出，则结点分裂，中间关键码连同新指针插入父结点 3) 若父结点也溢出，则继续分裂。 4) 分裂过程可能传达到根结点(则树升高一层)。 北京大学信息学院?版权所有，转载或翻印必究Page 90 B 树操作的访外次数 读盘次数与查找相同 写盘次数 最少写盘次数：如果不分裂，那么就是写一次：这个关键码所插入到的结点。 有结点分裂的情况下，插入操作最少写盘次数：只在最底层分裂一次，那么就是写3次：两个新结点，这两个结点的父结点。 北京大学信息学院 ?版权所有，转载或翻印必究 Page 91 一次插入操作最多读写次数 如果我们所用的内存工作区足够大，使得在向下检索时读入的结点在插入后向上分裂时不必再从磁盘读入 总共h 层，每层都需要分裂（包括根） 当分裂一个非根的结点时需要向磁盘写出2 个结点, 当分裂根结点时需要写出3 个结点。 需要读写磁盘的最多次数 = 找插入结点向下读盘次数++ 分裂非根结点时写盘次数++ 分裂根结点时写盘次数= h +2(h -1)+3 = 3h +1。 北京大学信息学院 ?版权所有，转载或翻印必究 Page 92 B 树的删除 删除的关键码不在叶结点层 先把此关键码与它在B 树里的后继对换位置，然后再删除该关键码 back 北京大学信息学院?版权所有，转载或翻印必究Page 93B 树的删除(续) 删除的关键码在叶结点层 删除后关键码个数不小于 直接删除 关键码个数小于 如果兄弟结点关键码个数不等于 从兄弟结点移若干个关键码到该结点中来 (父结点中的一个关键码要做相应变化) 如果兄弟结点关键码个数等于 合并 /21m ???? ?/21 m ?????/21m ???? ?/21 m ?????北京大学信息学院?版权所有，转载或翻印必究Page 94 6阶B 树 删除045 239240279 008 040052110135142212045112236 北京大学信息学院 ?版权所有，转载或翻印必究 Page 95 239240279 008040110135142212112236 先把右子树最小052 与045交换 再删除045 045052北京大学信息学院 ?版权所有，转载或翻印必究 Page 96 关键码个数 不足 从兄弟结点移动135补足 239240279 008040110 135142212052112 236 045 删除045 北京大学信息学院 ?版权所有，转载或翻印必究 Page 97 注意：兄弟结点中的135被移动到父结点中，被移动到叶结点中的是父结点中的 112 008040110 142212237240279 052236 112 135北京大学信息学院 ?版权所有，转载或翻印必究 Page 98 008040 110112142212237240279 052135236 删除 112 右兄弟结点关键码个数也不足关键码个数不足 左兄弟结点关键码个 数不足 北京大学信息学院 ?版权所有，转载或翻印必究 Page 99 合并 135 142212008040 237240279 052236 110 北京大学信息学院 ?版权所有，转载或翻印必究 Page 100 239240279 008 040052110135142212 045112236 4阶B 树删除045？ 北京大学信息学院 ?版权所有，转载或翻印必究 Page 101 B树删除 保持性质：等高、阶（上下界） 交换——删除——借关键码——合并 1) 保证所删除的位置在最底层(否则，与其后继关键码交换) 2) 若删除后，结点中关键码数目不够最低限(下溢出)，则先看左右兄弟有无多余的关键码可借，若有则该结点与它的一个兄弟结点的所有关键码，再加上父结点中的分界码，当成一个结点，类似于插入算法，再分为三部分； 3) 若其左右兄弟中关键码数目都处在最低限，则把该结点和它的一个兄弟，以及父结点中它俩的分界关键码一起合并成一个结点；(父结点中关键码数目减少一个) 4) 此合并过程可能传递到根(则树降低一层)。 北京大学信息学院 ?版权所有，转载或翻印必究 Page 102 10.4.2 B +树 是B 树的一种变形 在叶结点上存储信息的树 所有的关键码均出现在叶结点上 各层结点中的关键码均是下一层相应结点中最大关键码（或最小关键码）的复写 北京大学信息学院 ?版权所有，转载或翻印必究 Page 103 B +树的结构定义 m阶B +树的结构定义如下： (1)每个结点至多有m个子结点； (2)每个结点(除根外)至少有个子结点； (3)根结点至少有两个子结点； (4)有k个子结点的结点必有k个关键码。 ??? ???2m 北京大学信息学院?版权所有，转载或翻印必究Page 104 2阶B +树的例子 70 95 10203540445165 70 85 919395 20405170 9195 4070 95 北京大学信息学院 ?版权所有，转载或翻印必究 Page 105 B +树的抽象数据类型 template class PAIR //用于存储关键码和指向磁盘块的指针的数据结构{ public: void* ptr; //对于叶结点是指向磁盘块的指针 //而对非叶节点是指向子结点的指针Key key;}; 北京大学信息学院 ?版权所有，转载或翻印必究 Page 106 template //存储关键码的数组 PAIR 北京大学信息学院 ?版权所有，转载或翻印必究Page 107//BPTree class template BPNode //检索关键码K bool Search(Key K,Elem*& e)//插入关键码K bool insert(Key K,Elem*& e)//删除关键码K bool remove(Key K,Elem*& e)} 北京大学信息学院 ?版权所有，转载或翻印必究 Page 108 B +树的查找 查找应该到叶结点层 在上层已找到待查的关键码，并不停止 而是继续沿指针向下一直查到叶结点层的这个关键码 B +树的叶结点一般链接起来，形成一个双链表 适合顺序检索（范围检索） 实际应用更广 北京大学信息学院?版权所有，转载或翻印必究Page 109B +树的插入 插入——分裂 过程和B 树类似 注意保证上一层结点中有这两个结点的最大关键码（最小关键码） 北京大学信息学院?版权所有，转载或翻印必究Page 110 m=3 1023 33 35 2335 插入15 北京大学信息学院 ?版权所有，转载或翻印必究 Page 111 10 15 23 33 35 23 35 插入15后 北京大学信息学院 ?版权所有，转载或翻印必究 Page 112 1023 插入16 15 23 1015 16 2333 35 2335 结点满，需要分裂 北京大学信息学院 ?版权所有，转载或翻印必究 Page 113 10 15 33 35 15 23 35 16 23插入17 北京大学信息学院 ?版权所有，转载或翻印必究 Page 114 插入19 16 17 23 1015 33 35 15 23 35 16 17 19 23 北京大学信息学院 ?版权所有，转载或翻印必究 Page 115 10 15 33 35 15 23 35 16 17 19 23 结点满，需要分裂 北京大学信息学院 ?版权所有，转载或翻印必究 Page 116 10 1516 17 19 23 33 35 15 1723 35 结点满，需要分裂 北京大学信息学院 ?版权所有，转载或翻印必究 Page 117 10 15 16 17 19 23 33 35 15 17 23 35 17 35 树增加一层 北京大学信息学院 ?版权所有，转载或翻印必究 Page 118 B +树的删除 当关键码不满时，与左右兄弟进行 调整、合并的处理和B树类似 关键码在叶结点层删除后，其在上层的复本可以保留，做为一个“分界关键码”存在 也可以替换为新的最大关键码（或最小关键码） 北京大学信息学院 ?版权所有，转载或翻印必究 Page 119 m=3, 删除23 19 23 23被删除 但上层结点中的副本保 留 10 15 16 17 19 33 35 15 17 23 35 17 35 北京大学信息学院 ?版权所有，转载或翻印必究 Page 120 10.4.3 VSAM VSAM(Virtual Storage Access Method)—虚拟存储存取方法 B +树的应用 一种索引顺序文件的组织方式 与存储设备无关，存储单位是“逻辑”的 实验报告 课程名称:数据结构与算法 实验名称:树的应用 一、实验目的 ⑴、掌握二叉树的静态数组存放。 ⑵、掌握哈夫曼编码的基本概念。 ⑶、掌握哈夫曼编码树的构造方法。 ⑷、掌握哈夫曼编码的构造和使用。 ⑸、理解前缀编码的概念。 二、实验内容 ⑴、按照字符出现概率构造一个哈夫曼树。要求输入为一个文本文件（可以限 制文本仅仅包含字母），通过统计字符出现的次数计算概率，在此基础上构造哈夫曼树。 ⑵、打印出每一个字母对应的哈夫曼编码。 三、实验环境 硬件：Windows XP计算机、鼠标、键盘、显示器 开发环境：Microsoft Visual C++ 6.0 四、实验步骤 ①、点击开始菜单中的程序-Microsoft Visual C++ 6.0 点击菜单栏中的文件—新建—文件—C++ Source File ，在文件名(N)中写入5.cpp,再点击确定. ②、编写程序如下： #include 《数据结构与算法设计》 实验报告 ——实验二 学院：自动化学院 班级： 学号： ： 一、实验目的 按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。 二、实验容 简单计算器。 请按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。要求： ①从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志。 ②输入表达式中的数值均为大于等于零的整数。中间的计算过程如果出现小数也只取 整。 例如，输入：4+2*5= 输出：14 输入：(4+2)*(2-10)= 输出：-48 三、程序设计 概要设计 1、宏定义 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 2、基本函数： （1）void InitStack_char(SqStack *S) //char型栈初始化 （2）void InitStack_int(sqStack *S) //int型栈初始化 （3）void Push_char(SqStack *S,char ch) //char型元素进栈 （4）void Push_int(sqStack *S,int num) //int型元素进栈 （5）char GetTop_char(SqStack *S) //取char型栈顶元素 （6）int GetTop_int(sqStack *S) //取int型栈顶元素 （7）Status In(char c) //判断是否为运算符，若是运算符则返回，否则返回 （8）char Precede(char a,char b) //判断两运算符的先后次序 （9）Status Pop_char(SqStack *S,char &x) //char型栈出栈 （10）Status Pop_int(sqStack *S,int &x) //int型栈出栈 （11）int Operate(int a,char theta,int b) //计算a和b运算结果 3、流程图 《数据结构与算法》期末复习题 一、选择题。 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i 习题参考答案 一．选择题 1.从逻辑上可以把数据结构分为（C)两大类。 A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造型结构 2.在下面的程序段中，对x的斌值语句的频度为（C)。 for( t＝1；k＜＝n;k＋＋） for（j=1;j＜＝n; j＋＋） x=x十1； A. O(2n) B. O (n) C. O (n2)． D. O（1og2n) 3.采用链式存储结构表示数据时，相邻的数据元素的存储地址（C)。 A.一定连续B．一定不连续 C.不一定连续 D.部分连续，部分不连续 4.下面关于算法说法正确的是（D）。 A.算法的时间复杂度一般与算法的空间复杂度成正比 B.解决某问题的算法可能有多种，但肯定采用相同的数据结构 C.算法的可行性是指算法的指令不能有二义性 D.同一个算法，实现语言的级别越高，执行效率就越低 5.在发生非法操作时，算法能够作出适当处理的特性称为（B）。 A.正确性 B.健壮性 C.可读性 D.可移植性 二、判断题 1.数据的逻辑结构是指数据的各数据项之间的逻辑关系。（√） 2.顺序存储方式的优点是存储密度大，且插人、删除运算效率高。（×） 3.数据的逻辑结构说明数据元素之间的次序关系，它依赖于数据的存储结构。（×） 4.算法的优劣与描述算法的语言无关，但与所用计算机的性能有关。（×） 5.算法必须有输出，但可以没有输人。（√） 三、筒答题 1．常见的逻辑结构有哪几种，各自的特点是什么？常用的存储结构有哪几种，各自的特点是什么？ 【答】常见的四种逻辑结构： ①集合结构：数据元素之间是“属于同一个集合” ②线性结构：数据元素之间存在着一对一的关系 ③树结构：数据元素之间存在着一对多的关系 ④结构：数据元素之间存在着多对多的关系。 常见的四种存储结构有： ①顺序存储：把逻辑上相邻的元素存储在物理位置相邻的存储单元中。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。 ②链接存储：对逻辑上相邻的元素不要求物理位置相邻的存储单元，元素间的逻辑关系通过附设的指针域来表示。 ③索引存储：通过建立索引表存储结点信息的方法，其中索引表一般存储结点关键字和一个地点信息，可通过该地址找到结点的其他信息。 ④散列存储：根据结点的关键字直接计算出该结点的存储地址的方法。 2．简述算法和程序的区别。 【解答】一个算法若用程序设计语言来描述，则它就是一个程序。算法的含义与程序十分相 2.3 课后习题解答 2.3.2 判断题 1．线性表的逻辑顺序与存储顺序总是一致的。（×） 2．顺序存储的线性表可以按序号随机存取。（√） 3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。（×） 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。（√） 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（×） 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（√）7．线性表的链式存储结构优于顺序存储结构。（×） 8．在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。（√） 9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（√）10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（×） 11．静态链表既有顺序存储的优点，又有动态链表的优点。所以它存取表中第i个元素的时间与i无关。（×） 12．线性表的特点是每个元素都有一个前驱和一个后继。（×） 2.3.3 算法设计题 1．设线性表存放在向量A[arrsize]的前elenum个分量中，且递增有序。试写一算法，将x 插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。【提示】直接用题目中所给定的数据结构（顺序存储的思想是用物理上的相邻表示逻辑上的相邻，不一定将向量和表示线性表长度的变量封装成一个结构体），因为是顺序存储，分配的存储空间是固定大小的，所以首先确定是否还有存储空间，若有，则根据原线性表中元素的有序性，来确定插入元素的插入位置，后面的元素为它让出位置，（也可以从高下标端开始一边比较，一边移位）然后插入x ，最后修改表示表长的变量。 int insert (datatype A[],int *elenum,datatype x) /*设elenum为表的最大下标*/ {if (*elenum==arrsize-1) return 0; /*表已满，无法插入*/ else {i=*elenum; while (i>=0 && A[i]>x) /*边找位置边移动*/ {A[i+1]=A[i]; i--; } A[i+1]=x; /*找到的位置是插入位的下一位*/ (*elenum)++; return 1; /*插入成功*/ } } 时间复杂度为O(n)。 数据结构与方法 1、算法的基本特征:可行性、确定性、有穷性、拥有足够的情报 2、算法的基本运算与操作:算术运算、逻辑运算、关系运算、数据传输 3、算法的基本控制结构:顺序结构、选择结构、循环(重复)结构 4、算法设计的基本方法:列举法、归纳法、递推、递归、减半递推技术、回溯法 5、算法的复杂度主要包括:时间复杂度、空间复杂度 6、算法的时间复杂度:指执行算法所需要的计算工作量 7、算法的空间复杂度:指执行这个算法所需要的内存空间 8、数据结构主要研究:数据的逻辑结构、数据的存储结构、对各种数据结构进行的运算 9、数据结构研究的目的:提高数据处理的效率 10、数据处理的效率:数据处理的速度、减少处理过程中占用计算机的存储空间 11、数据处理:指对数据集合中的各元素以各种方式进行运算 12、数据元素:指在数据处理中,每一个需要处理的对象都可以抽象成数据元素 13、数据结构:指反映数据元素之间关系的数据元素集合的表示 14、数据的逻辑结构:指反映数据元素之间逻辑关系的数据结构,两要素:数据元素的集合、数据元素在集合上的关系 15、数据的存储结构:指数据的逻辑结构在计算机存储空间的存放形式,常用的存储结构有:顺序、链接、索引等 16、数据结构的图形表示中每个元素加上方框成为结点 17、数据结构一般分为:线性结构、非线性结构 18、线性结构满足:有且仅有一个根结点、每个结点最多有一个前件与后件、在一个线性结构中插入与删除任何一个结点后还就是线性结构 19、线性表定义:线性表就是由n个数据元素a1、a2、a3、a4……an组成的一个有限序列,表中每一个数据元素,除了第一个外,有且仅有一个前件,除了最后一个外,有且仅有一个后件20、非线性表的特征:有且只有一个根节点a1,它无前件、有且只有一个终结点an,它无后件、除了第一个与最后一个外,其她所有结点只有一个前件与一个后件 21、线性表的长度:线性表中的结点的个数n成为线性表的长度,当n=0时,成为空表 22、线性表的顺序存储的特点:所有元素所占的存储空间就是连续的、各数据元素在存储空间中就是按逻辑顺序一次存放的 23、线性表的随机存取地址计算公式:ADD(ai)=ADD(a1)+(i-1)*k 24、线性表的主要操作:插入、删除、查找、排序、分解、合并、复制、逆转 25、栈的定义:栈就是限定在一端进行插入与删除的线性表,它按照“先进后出,后进先出”的原则组织数据 26、栈的顺序存储:在程序设计语言中,一般一维数组S(1:m)作为栈的顺序存储空间,其中m 为栈的最大容量 27、栈的基本运算:入栈、退栈、读栈顶元素 28、入栈运算:首先将栈顶指针(top)加1,然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时,说明栈空间已满,称为“上溢”错误 29、退栈运算:首先将栈顶元素赋给一个指定的变量,然后将栈顶指针(top)减1。当栈顶指针为0时,说明栈空,成为“下溢”错误 30、队列的定义:队列就是指允许在一端进行插入,而在另一端进行删除的线性表,它按照“先进先出”的原则组织数据 31、循环队列:在实际应用中,队列的顺序存储结构一般采用循环队列的形式。所谓循环队列, 西安科技大学 2013年硕士研究生入学考试试题A ───────────────────────────────── 科目编号：824 科目名称： 数据结构与算法设计 考生须知： 1、 答案必须写在答题纸上，写在试题或草稿纸上不给分。 2、 答题须用蓝、黑色钢笔或圆珠笔，用铅笔、红色笔者不给分。 3、 答题必须写清题号，字迹要清楚，卷面要保持整洁。 4、 试题要随答题纸一起交回。 一、单项选择题（每小题2分，共30分） （1）并归排序的时间复杂度是（ ）。 A ．O(n 2) B ．O(nlog 2n) C ．O(n) D ．O(log 2n) （2）设一个链表最常用的操作是在末尾插入结点和删除尾结点，选用（ ）存储结构最节省时间。 A ．单链表 B ．单循环链表 C ．带尾指针的单循环链表 D ．带头结点的双循环链表 （3）散列文件是一种（ ）。 A ．顺序文件 B ．索引文件 C ．链接文件 D ．计算机寻址文件 （4）常用于函数调用的数据结构是（ ）。 A ．栈 B ．队列 C ．数组 D ．链表 （5）两个矩阵sn ms B A ,相乘的时间复杂度是（ ）。 A ．O(n 2) B ．O(s 2) C ．O(msn) D ．O(mn) （6）图的广度优先搜索遍历使用的数据结构是（ ）。 A ．栈 B ．队列 C ．集合 D ．树 （7）在单链表中，每个存贮结点有两个域，即数据域和指针域，指针域指向该结点的（ ）。 A ．直接前驱 B ．直接后继 C ．开始结点 D ．终端结点 （8）在已知头指针的单链表中，要在其尾部插入一个新结点，其时间复杂度是（ ）。 A ．O(n 2) B ．O(1) C ．O(n) D ．O(log 2n) （9）在链队列中执行入队操作，（ ）。 A ．需判断队是否为空 B ．限定在链表头p 进行 C ．需判断队是否为满 D ．限定在链表尾p 进行 （10）对序列（95，83，62，70）进行冒泡排序（由小到大），第2趟排序后的结果为（ ）。 A ．（70，83，62，95） B ．（70，62，83，95） 四川大学期末考试试题 （2008-2009学年第1学期） 课程号：课程名称：数据结构与算法分析（B卷）任课教师： 1．数据类型为（）。 A）数据项的集合B）值的集合及定义在其上的一组操作的总称 C）数据元素的集合D）关键字的集合 2．链表不具有的特点是（）。 A）可随机直接访问任一元素B）插入删除不需要移动元素 C）不必事先估计元素个数D）所需空间与线性表长度成正比 3．设一个栈的入栈序列是ABCD，则借助于一个栈所得到的出栈序列不可能是（）。 A）ABCD B）DCBA C）ABCD D）DABC 4．将对称矩阵A nxn压缩存储在一维数组B[m]中，则m的值至少为（）。 A）n(n+1)/2 B）n(n-1)/2 C）n(n+1) D）n2 5．设二叉树中有n2个度为2的结点，n1个度为1的结点，n0个叶子结点，则此二叉树中空指针域个数为（）。 A）n0+n1+n2 B）n2+n1+2n0 C）2n2+n1D）2n0+n1 6．对于具有n个顶点的强连图，其弧条数的最小值为（）。 A）n+1 B）n C）n-1 D）n-2 7．一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（）个结点。 A）2k-1-1 B）2k-1C）2k-1+1 D）2k-1 8．归并排序的时间复杂度是（）。 A）O(1) B）O(n) C）O(n2) D）O(nlogn) 9．每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是（）。 A）冒泡排序B）简单选择排序C）希尔排序D）直接插入排序10．按照二叉树的定义，具有3个结点的不同形态（相似）的二叉树有（）种。 A）3 B）4 C）5 D）6 二、（本题10分） 利用两个栈S1、S2模拟一个队列（如客户队列）时，如何用栈的运算实现队列的插入、删除运算，请简述算法思想。 三、（本题10分） 已知一棵二叉树的先序序列与中序序列分别如下，试画出此二叉树。 先序序列：ABCDEFGH IJ 中序序列：CBEDAGHFJI 注：试题字迹务必清晰，书写工整。本题2页，本页为第1页 教务处试题编号： 数据结构与算法基础知识总结 1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 3 线性表及其顺序存储结构 线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。 线性表的顺序存储结构具有以下两个基本特点： （1）线性表中所有元素的所占的存储空间是连续的； （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为：adr(ai)=adr(a1)+(i-1)k,，adr(a1)为第一个元素的地址，k代表每个元素占的字节数。 顺序表的运算：插入、删除。（详见14--16页） 4 栈和队列 栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。 栈按照“先进后出”（filo）或“后进先出”（lifo）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。 栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。 队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。rear指针指向队尾，front指针指向队头。 队列是“先进行出”（fifo）或“后进后出”（lilo）的线性表。 队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。循环队列：s=0表示队列空，s=1且front=rear表示队列满 2.3 课后习题解答 选择题 1、A 2、A 3、D 4、C 5、D 6、B 7、C 8、B 9、A 10、D 11、B 12、D 2.3.2 判断题 1．线性表的逻辑顺序与存储顺序总是一致的。（×） 2．顺序存储的线性表可以按序号随机存取。（√） 3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。（×） 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。（√） 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（×） 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（√）7．线性表的链式存储结构优于顺序存储结构。（×） 8．在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。（√） 9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（√）10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（×） 11．静态链表既有顺序存储的优点，又有动态链表的优点。所以它存取表中第i个元素的时间与i无关。（×） 12．线性表的特点是每个元素都有一个前驱和一个后继。（×） 2.3.3 算法设计题 1．设线性表存放在向量A[arrsize]的前elenum个分量中，且递增有序。试写一算法，将x 插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。【提示】直接用题目中所给定的数据结构（顺序存储的思想是用物理上的相邻表示逻辑上的相邻，不一定将向量和表示线性表长度的变量封装成一个结构体），因为是顺序存储，分配的存储空间是固定大小的，所以首先确定是否还有存储空间，若有，则根据原线性表中元素的有序性，来确定插入元素的插入位置，后面的元素为它让出位置，（也可以从高下标端开始一边比较，一边移位）然后插入x ，最后修改表示表长的变量。 int insert (datatype A[],int *elenum,datatype x) /*设elenum为表的最大下标*/ {if (*elenum==arrsize-1) return 0; /*表已满，无法插入*/ else {i=*elenum; while (i>=0 && A[i]>x) /*边找位置边移动*/ {A[i+1]=A[i]; i--; } A[i+1]=x; /*找到的位置是插入位的下一位*/ (*elenum)++; return 1; /*插入成功*/ } 北京交通大学考试试题（A卷） 课程名称:数据结构与算法2011-2012学年第一学期出题教师:张勇 (请考生注意:（1）本试卷共有六道大题，（2）答案一律写在答题纸上，（3）试卷不得带出考场) 1. 在顺序表中访问任意一个元素的时间复杂度均为，因此顺序表也称为 的数据结构。 2．三维数组a[4][3][2](下标从0开始)，假设a[0][0][0]的地址为50，数据以行序优先方式存储，每个元素的长度为2字节，则a[2][1][1]的地址是。 3. 直接插入排序用监视哨的作用是。 4. 已知广义表Ls=(a, (b, c), (d, e)), 运用head和tail函数取出Ls中的原子d的运算 是。 5．对有14个元素的有序表A[1..14]进行折半查找，当比较到A[4]时算法结束。被比较元素除A[4]外，还有。 6. 在AOV网中，顶点表示，边表示。 7. 有向图G可进行拓扑排序的判别条件是。 8. 若串S1=‘ABCDEFGHIJK’,S2=‘451223’,S3=‘####’,则执行 Substring(S1,Strlength(S3),Index(S2,‘12’,1))的结果是。 二、选择题（每空2分，共20分） 1.在下列存储形式中，哪一个不是树的存储形式？（） A．双亲表示法B．孩子链表表示法 C．孩子兄弟表示法D．顺序存储表示法 2.查找n个元素的有序表时，最有效的查找方法是（）。 A．顺序查找B．分块查找 C．折半查找D．二叉查找 3.将所示的s所指结点加到p所指结点之后，其语句应为（）。 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; 4. 在有向图的邻接表存储结构中，顶点v 在链表中出现的次数是（ ）。 A. 顶点v 的度 B. 顶点v 的出度 C. 顶点v 的入度 D. 依附于顶点v 的边数 5. 算法的时间复杂度为O （nlog 2n ）、空间复杂度为O(1)的排序算法是（ ）。 A. 堆排序 B. 快速排序 C. 归并排序 D.直接选择 6. 设矩阵A 是一个对称矩阵，为了节省存储，将其 下三角部分（如右图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素ai,j(i ≤j), 在一维数组B 中下标k 的值是（ ）： Ａ．i(i-1)/2+j-1 Ｂ．i(i-1)/2+j Ｃ．i(i+1)/2+j-1 Ｄ．i(i+1)/2+j 7. 由一个长度为11的有序表，按二分查找法对该表进行查找，在表内各元素等概率情 况下，查找成功的平均查找长度是（ ）。 A ．29/11 B. 31/11 C. 33/11 D.35/11 8. AVL 树是一种平衡的二叉排序树，树中任一结点的（ ）。 A. 左、右子树的高度均相同 B. 左、右子树高度差的绝对值不超过1 C. 左子树的高度均大于右子树的高度 D. 左子树的高度均小于右子树的高度 9. 下列四种排序方法中，不稳定的方法是（ ）。 A. 直接插入排序 B. 冒泡排序 C. 归并排序 D. 堆排序 10. 设树的度为4，其中度为1,2,3,4的结点个数分别为4, 2, ,1, 1, 则T 中的叶子数为 （ ）。 A ．5 B ．6 C ．7 D ．8 三、 判断题（10分，每小题1分） 1. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（ ） 2. 数组不适合作任何二叉树的存储结构。（ ） 3. 广义表的取表尾运算，其结果通常是个表，但有时也可是个原子。（ ） 4. 在含有n 个结点的树中，边数只能是n-1条。（ ） 5. 所谓一个排序算法是否稳定，是指该算法在各种情况下的效率是否相差不大。（ ） 6. 简单选择排序在最好情况下的时间复杂度为O(n)。（ ） 7. 在二叉排序树中插入一个新结点，总是插入到叶结点下面。（ ） 8. 采用线性探测处理冲突，当从哈希表中删除一个记录时，不应将该记录所在位置置 空，因为这会影响以后的查找。（ ） 9. 有n 个数存放在一维数组A[1..n]中，在进行顺序查找时，这n 个数的排列有序或无 ?????? ? ???? ? ??=n n n n a a a a a a A ,2,1,2 ,21,21 ,1Λ Λ 《数据结构与算法分析》课程设计教学任务书 一、课程设计的目的 数据结构与算法课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。 学习数据结构与算法是为了将实际问题中涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的： 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 二、课程设计的基本要求 1. 独立思考，独立完成：课程设计中各任务的设计和调试要求独立完成，遇到问题可以讨论，但不可以拷贝。 2. 做好上机准备：每次上机前，要事先编制好准备调试的程序，认真想好调试步骤和有关环境的设置方法，准备好有关的文件。 3. 按照课程设计的具体要求建立功能模块，每个模块要求按照如下几个内容认真完成： a）需求分析： 在该部分中叙述，每个模块的功能要求 b）概要设计： 在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义） c）详细设计： 各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组程序，每个功能模块采用不同的函数实现） 源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释 d）调试分析： 测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些，问题如何解决？），算法的改进设想 课程设计总结：（保存在word文档中）总结可以包括：课程设计过程的收获、遇到的问题、解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对《数据结构》课程的认识等内容 4. 实现的结果必须进行检查和演示，程序源代码和程序的说明文件必须上交，作为考核内容的一部分。（上交时每人交一份，文件夹的取名规则为：“学号姓名”，如“09201199王五”。该文件夹下至少包括：“源代码”、“课程设计报告”、“可执行文件”。由学习委员收 2、3 课后习题解答 2、3、2 判断题 1.线性表的逻辑顺序与存储顺序总就是一致的。(×) 2.顺序存储的线性表可以按序号随机存取。(√) 3.顺序表的插入与删除操作不需要付出很大的时间代价,因为每次操作平均只有近一半的元素需要移动。(×) 4.线性表中的元素可以就是各种各样的,但同一线性表中的数据元素具有相同的特性,因此属于同一数据对象。(√) 5.在线性表的顺序存储结构中,逻辑上相邻的两个元素在物理位置上并不一定相邻。(×) 6.在线性表的链式存储结构中,逻辑上相邻的元素在物理位置上不一定相邻。(√) 7.线性表的链式存储结构优于顺序存储结构。(×) 8.在线性表的顺序存储结构中,插入与删除时移动元素的个数与该元素的位置有关。(√) 9.线性表的链式存储结构就是用一组任意的存储单元来存储线性表中数据元素的。(√) 10.在单链表中,要取得某个元素,只要知道该元素的指针即可,因此,单链表就是随机存取的存储结构。(×) 11.静态链表既有顺序存储的优点,又有动态链表的优点。所以它存取表中第i个元素的时间与i无关。(×) 12.线性表的特点就是每个元素都有一个前驱与一个后继。(×) 2、3、3 算法设计题 1.设线性表存放在向量A[arrsize]的前elenum个分量中,且递增有序。试写一算法,将x 插入到线性表的适当位置上,以保持线性表的有序性,并且分析算法的时间复杂度。 【提示】直接用题目中所给定的数据结构(顺序存储的思想就是用物理上的相邻表示逻辑上的相邻,不一定将向量与表示线性表长度的变量封装成一个结构体),因为就是顺序存储,分配的存储空间就是固定大小的,所以首先确定就是否还有存储空间,若有,则根据原线性表中元素的有序性,来确定插入元素的插入位置,后面的元素为它让出位置,(也可以从高下标端开始一边比较,一边移位)然后插入x ,最后修改表示表长的变量。 int insert (datatype A[],int *elenum,datatype x) /*设elenum为表的最大下标*/ {if (*elenum==arrsize-1) return 0; /*表已满,无法插入*/ else {i=*elenum; while (i>=0 && A[i]>x) /*边找位置边移动*/ {A[i+1]=A[i]; i--; } A[i+1]=x; /*找到的位置就是插入位的下一位*/ (*elenum)++; return 1; /*插入成功*/ } } 时间复杂度为O(n)。 2.已知一顺序表A,其元素值非递减有序排列,编写一个算法删除顺序表中多余的值相同的元素。 数据结构与算法试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为 (C ) A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时,要求占用的存储空间地址(D ) A 必须就是连续的 B 部分地址必须就是连续的 C 一定就是不连续的 D 可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时,搜索成功的平均搜索长度为( D )。 A n B n/2 C (n-1)/2 D (n+1)/2 4、在一个单链表中,若q结点就是p结点的前驱结点,若在q与p之间插入结点s,则执行( D )。 A s→link = p→link;p→link = s; B p→link = s; s→link = q; C p→link = s→link;s→link = p; D q→link = s;s→link = p; 5、如果想在4092个数据中只需要选择其中最小的5个,采用( C )方法最好。 A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序 6、设有两个串t与p,求p在t中首次出现的位置的运算叫做( B )。 A 求子串 B 模式匹配 C 串替换 D 串连接 7、在数组A中,每一个数组元素A[i][j]占用3个存储字,行下标i从1到8,列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中,则存放该数 组至少需要的存储字数就是( C )。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时,通常需要使用( A )。 A 栈 B 队列 C 循环队列 D 优先队列 9、一个队列的进队列顺序就是1, 2, 3, 4,则出队列顺序为( C )。 10、在循环队列中用数组A[0、、m-1] 存放队列元素,其队头与队尾指针分别为front与rear,则当前队列中的元素个数就是( D )。 A ( front - rear + 1) % m B ( rear - front + 1) % m C ( front - rear + m) % m D ( rear - front + m) % m 11、一个数组元素a[i]与( A )的表示等价。 A *(a+i) B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参,则应把形参变量说明为( B )参数。 A 指针 B 引用 C 值 D 变量 13、下面程序段的时间复杂度为( C ) for (int i=0;i 数据结构与算法设计知识点 试题类型： 本课程为考试科目（闭卷笔试），试题类型包括：概念填空题（10 %），是非判断题（10 %），单项选择题（40 %），算法填空题（10%），算法应用题（20 %)，算法设计题（10 %）。 第一章绪论 重点内容及要求： 1、了解与数据结构相关的概念（集合、数据、数据元素、数据项、关键字、元 素之间的关系等）。 数据：所有能被输入到计算机中，且能被计算机处理的符号的 集合。是计算机操作的对象的总称。是计算机处理的信息的某种特定 的符号表示形式。 数据元素：是数据（集合）中的一个“个体”，数据结构中的基本 单位，在计算机程序中通常作为一个整体来考虑和处理。 数据项：是数据结构中讨论的最小单位，数据元素可以是一个或 多个数据项的组合 关键码：也叫关键字（Key），是数据元素中能起标识作用的数 据项。 其中能起到唯一标识作用的关键码称为主关键码（简称主码）； 否则称为次关键码。通常，一个数据元素只有一个主码，但可以有多 个次码。 关系：指一个数据集合中数据元素之间的某种相关性。 数据结构：带“结构”的数据元素的集合。这里的结构指元素之 间存在的关系。 数据类型：是一个值的集合和定义在此集合上的一组操作的总 称。 2、掌握数据结构的基本概念、数据的逻辑结构（四种）和物理结构（数据元素 的表示与关系的表示、两类存储结构：顺序存储结构和链式存储结构）。 数据结构包括逻辑结构和物理结构两个层次。 数据的逻辑结构：是对数据元素之间存在的逻辑关系的一种抽象的描述，可以用一个数据元素的集合和定义在此集合上的若干关系来表示 逻辑结构有四种：线性结构、树形结构、图状结构、集合结构数据的物理结构：是其逻辑结构在计算机中的表示或实现，因此又称其为存储结构。 存储结构：顺序存储结构和链式存储结构 顺序存储结构：利用数据元素在存储器中相对位置之间的某种特定的关系来表示数据元素之间的逻辑关系； 链式存储结构：除数据元素本身外，采用附加的“指针”表示数据元素之间的逻辑关系。 3、了解算法分析的基本方法，掌握算法时间复杂度相关的概念。 算法：是为了解决某类问题而规定的一个有限长的操作序列 或处理问题的策略 一个算法必须满足以下五个重要特性：1．有穷性2．确定性3．可行性4．有输入5．有输出 设计算法时，通常还应考虑满足以下目标： 1.正确性， 2.可读性， 3.健壮性 4.高效率与低存储量需求 学院 《数据结构与算法》之实际应用 二零一三年三月十三日 目录 数据结构与算法在实际中的应用 (2) 摘要： (2) 一、定义：............................ 错误！未定义书签。 二、在各领域中的实际应用.............. 错误！未定义书签。 （一）、排队叫号系统（尾插法） (2) （二）、搜索引擎与数据结构算法 (4) （三）、图论应用 (5) （四）、最小生成树在城市高速公路问题中的应用 (5) 三、小结 (6) 四、参考文献 (6) 小组成员： 数据结构与算法在实际中的应用 摘要： 计算机科学是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的表示，信息的处理。何为信息，信息就是大量的数据，需要对大量的数据进行处理。进而我们需要《数据结构与算法》这门课作为基础，去发展计算机学科。数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。通过《数据结构与算法》的学习，我们能够解决很多学科问题、生活实际问题。 一、定义 《数据结构与算法》应该包括两个部分：数据结构、算法。 数据结构在计算机科学界至今没有标准的定义。根据各自的理解的不同而有不同的表述方法，数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。 算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用时间复杂度和空间复杂度衡量。 二、在各领域中的应用 在我们的日常生活中，应用到数据结构的地方有很多地方，实例到处都是，比如说，做搜索引擎，对字符串的各种查找、索引的算法就有很高要求；做人工智能，对模式识别、搜索的要求就很高；做数据库设计，对字典、内外排序、搜索与索引以及数据的连接方式都有很高要求；做通讯密码，对数论、Fourier分析有要求等等。 （一）、排队叫号系统（尾插法） 数据结构包含数的操作,排序和查找等一系列问题。其中，排序的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的排列。数据结构的排序有5种。 数据结构与算法课程设计报告 题目 两两相连的房间问题： 一所奇怪的房子，这所房子里有n个房间，每个房间里有一些门通向别的房间，可是这些门十分奇怪，它们只能从房间a开向房间b，也就是说，一扇从a开向b的门是不能让一个人从b房间走到a房间的。你能计算一下任意两个房间之间都互相相通吗？ 问题分析 此程序需要完成如下要求：在这所房子里，从任意一个房间开始，按照开门的方向，均能够找到一个合适的路线，使得一个人能够不重复的到达其他的每一个房间，所以，需以每一个房间都为一次起始点来走向其他的房间，以此来判断这所房子里的任意两个房间之间是否互相相通。 实现本程序需要解决以下问题： 1.如何表示每一个房间，即存储房间的信息，并且还要确定这所房子里的各个房间的位置。 2.各个房间之间的门，以及门是从哪个房间开向哪个房间的该如何表示和存储的。 3.从某一个房间开始，如何走到其他各个房间，即如何对房间进行遍历。 4.为了在遍历过程中，不重复的遍历每一个房间，该如何标记已被遍历过的房间，从而只 访问未走过的房间。 5.最后通过什么的遍历方式才能判断各个房间之间是否互相相通。 数据结构的选择和概要设计 通过对题目要求的理解，我们可以用图来表示这所房子，而房子中的各个房间就相当于图中的各个结点，由于房间的门是有方向的，一扇从a开向b的门是不能让一个人从b房间走到a 房间的，从而可知该图为有向图，那么门就相当于有向图中的弧，从一个门开向另一个门即代表有向图中弧的起始点和终止点。 对于图的存储，我采用邻接表的形式来存储，并将每一个房间进行编号，对于邻接表，则需要定义一个邻接表结点类型、邻接表表头结点类型，通过表头与结点的连接而将有向图中弧的信息存储起来。那么人从任意一个房间走向另一个房间，即相当于有向图中从一个结点按照弧的信息访问其他的结点，可以采用深度优先搜索遍历。如果从每一个结点以起始点开始一次遍历就都能访问到其他结点的话则说明有向图是连通图，即该房子里的各个房间能够互相相通。定义一个全局的整形变量flag，如果是连通图的话则flag=1，否则flag=0。数据结构与算法--树的应用
数据结构与算法设计实验
数据结构与算法C语言版期末复习题
数据结构与算法第1章参考答案
《数据结构与算法》课后习题答案
数据结构与算法知识点必备
824数据结构与算法设计A
计算机学院数据结构与算法分析期末试题(2007级B)_无答案
数据结构与算法基础知识总结
数据结构与算法第二版2-4章答案
北京交通大学数据结构与算法期末测验考试参考答案
天津科技大学数据结构与算法课程设计
《数据结构与算法》课后习题答案
数据结构与算法试题
数据结构与算法设计知识点
数据结构与算法实际应用
数据结构与算法课程设计程序与报告
相关主题
文本预览