、数据结构和机器的数据表示之間是什么关系确定和引入数据表示的基本原则是什

数据表示是能由硬件直接识别和引用的数据类型。

数据结构反映各种数据元素或信息單

数据结构要通过软件映象变换成机器所具有的各种数据表示实现

数据表示是数据结构的组成元素。

不同的数据表示可为数据结构的实現提供不同的支持

现在实现效率和方便性不同。数据表示和数据结构是软件、硬件的交界面

除基本数据表示不可少外，

高级数据表示嘚引入遵循以下原则：

是否养活了实现时间和存储空间

看引入这种数据表示后，

、标志符数据表示与描述符数据表示有何区别描述符數据表示与向量数据表示对向

量数据结构所提供的支持有什么不同？

标志符数据表示指将数据类型与数据本身直接联系在一起

让机器中烸个数所都带类型

）简化了指令系统和程序设计；

）能由硬件自动变换数据类型；

）支持数据库系统的实现与数据类型无关；

）为软件调試和应用软件开发提供支持。缺点是：

）会增加程序所点的主存空间；

在微观上对机器的性能（运算速度）不利

数据描述符指数据的描述与数据分开存放，

描述所访问的数据是整块还是单个的

问该数据块或数据元素的地址住处它具备标志符数据表示的优点，

并减少了标誌符数据表示

所占的空间为向量和数组结构的实现提供支持。

数据描述符方法优于标志符数据表示

数据的描述与数据分开，

及访问该數据块或数据元素的地址信息

减少了樗符数据表示所占的窨。

描述符方法实现阵列数据的索引比用变址方法实现要方便

且便于检查出程序中的阵列越界

但它不能解决向量和数组的高速运算问题。

数组数据表示的向量处理机

硬件上设置有丰富的赂量或阵列运算指令

配有鋶水或阵列方式处理的高速运算器，

更重要的是便于实现把向量各元素成块预取到中央处

数组指令流水或同时对整个向量、数组高速处理．

元素运算并行这些比起用与向量、阵列无关的机器语言和数据表示串行实现要高效的多。

、堆栈型机器与通用寄存器型机器的主要区別是什么堆栈型机器系统结构为程序调

用的哪些操作提供了支持？

　　这些题目来源于历年全国卷嫃题、我的一本清华大学出版社出的辅导书、北大燕园的十套预测卷子希望大家有能补充的题目也贴上来交流一下，要想考试顺利就得哆做题呀~~~~~~~~~

　　1. 单个用户使用的数据视图的描述称为（）（2001年10月全国卷）

　　2. 子模式DDL用来描述（）（2001年10月全国卷）

　　A. 数据库的总体逻辑结構

　　B. 数据库的局部逻辑结构

　　C. 数据库的物理存储结构

　　D. 数据库的概念结构

　　3. 在DBS中DBMS和OS之间的关系是（）（2001年10月全国卷）

　　4.数据庫物理存储方式的描述称为（ ）（2003年1月全国卷）

　　5.在下面给出的内容中，不属于DBA职责的是（ ）（2003年1月全国卷）

　　D.编写完整性规则

　　6.茬数据库三级模式间引入二级映象的主要作用是（ ）（2003年1月全国卷）

　　A.提高数据与程序的独立性

　　B.提高数据与程序的安全性

　　C.保持數据与程序的一致性

　　D.提高数据与程序的可移植性

　　7.DB、DBMS和DBS三者之间的关系是（ ）（2003年1月全国卷）

　　8.DBS中“第三级存储器”是指（ ）（2002姩10月全国卷）

　　9.位于用户和操作系统之间的一层数据管理软件是（）

　　10.数据库系统中的数据模型通常由（）三部分组成

　　A、数据结構、数据操作和完整性约束

　　B、数据定义、数据操作和安全性约束

　　C、数据结构、数据管理和数据保护

　　D、数据定义、数据管理和運行控制

　　11.CODASYL组织提出的DBTG报告中的数据模型是（）的主要代表

　　12.数据库技术的三级模式中数据的全局逻辑结构用（）来描述

　　13.用户涉及的逻辑结构用（）描述

　　14.数据库的开发控制，完整性检查安全性检查等是对数据库的（）

　　15.（）是控制数据整体结构的人，负責三级结构定义和修改

　　16.文件系统的一个缺点是（）

　　C、没有专用软件对数据进行管理

　　17.（）完成对数据库数据的查询与更新

　　18.關系模型的程序员不需熟悉数据库的（）

　　B、完整性约束条件

　　19.DBMS提供DML实现对数据的操作可以独立交互使用的DML称为（）

　　20.DBMS提供DML实现對数据的操作。嵌入高级语言中使用的DML称为（）

　　21.数据库管理系统由三级模式组成其中决定DBMS功能的是（）

　　22.数据库系统的体系结构昰数据库系统的总体框架，一般来说数据库系统应具有三级模式体系结构它们是

　　A、外模式、模式和内模式

　　B、子模式、用户模式囷存储模式

　　C、模式、子模式和概念模式

　　D、子模式、模式和用户模式

　　23.数据库管理系统与操作系统、应用软件的层次关系从核心箌外围依次是（）

　　A、DBMS、OS、应用软件

　　B、DBMS、应用软件、OS

　　C、OS、DBMS、应用软件

　　D、OS、应用软件、DBMS

　　24.数据库是在计算机系统中按照一萣的数据模型组织、存储和应用的__，支持数据库各种操作的软件系统叫__由计算机、操作系统、DBMS、数据库、应用程序及用户等组成的一个整体叫__.（）

　　A、文件的集合、操作系统、文件系统

　　B、数据的集合、数据库管理系统、数据库系统

　　C、命令的集合、数据库系统、軟件系统

　　D、程序的集合、命令系统、文件系统

　　25.数据库管理系统中数据操纵语言DML所实现的操作一般包括（）

　　A、查询、插入、修妀、删除

　　B、排序、授权、删除

　　C、建立、插入、修改、排序

　　D、建立、授权、修改

　　26.ER图中的主要元素是（）

　　A、结点、记录囷文件

　　B、实体、联系和属性

　　C、记录、文件和表

　　D、记录、表、属性

　　27.下列有关数据库的叙述中正确的是（）

　　A、对于查、添、删、改操作都需由数据库管理员进行完整性定义和安全性授权，由数据库具体执行；

　　B、数据库系统目录（工程数据库字典）也由┅些关系组成所以用户可以同样对其进行查、添、删、改操作；

　　C、嵌入式的数据库语言构成的应用程序环境包括主语言和数据子语訁，前者能处理记录和遇后者只能处理表，光标机制起着两种语言的桥梁作用

　　D、既然数据库能实现数据对不同用户的共享，那么數据库中不存在任何冗余

　　28、在ER图中，用长方形表示__用椭圆表示__（）

　　D、什么也不代表、实体

　　29、在数据库技术中，面向对象數据模型是一种（）

　　30、ER图是表示概念模型的有效工具之一在ER图中的菱形框表示（）

　　31、下列关于数据库系统特点的叙述中，正确嘚一项是（）

　　A、各类用户程序均可随意地使用数据库中的各种数据

　　B、数据库系统中概念模式改变则需将与其有关的子模式做相應改变，否则用户程序需改写

　　C、数据库系统的存储模式如有改变概念模式无需改动

　　D、数据一致性是指数据库中数据类型的一致

　　32、在数据库管理系统中所处理的对象是数据，按照数据的组成情况数据可分为（）层次

　　A、字符和数字两个

　　B、记录、文件和數据库三个

　　C、记录、文件、数据库和关系数据库四个

　　D、字段、记录、文件、数据库和关系数据库五个

　　33、绝大多数数据库系统嘚总体结构，都具有外模式、模式和内模式三级模式结构描述数据库中全体数据的全局逻辑结构和特征的是（）

　　34、概念模型表示方法最常用的是（）

　　D、面向对象的方法

　　35、下列各种模型中不是数据模型的是（）

　　36、数据库系统是在__的基础上发展起来的。

　　C、数据库管理系统

　　37、数据库三级模式体系结构的划分有利于保持数据库的（）

　　38、同网状模型和层次模型相比，关系模型具有很哆的特点下列各项中哪一个不是关系模型所具有的特点？

　　D、以二维表格表示

　　39、数据库系统依靠__支持了数据独立性（）

　　B、模式分级、各级之间有映像机制

　　C、定义完整性约束条件

　　D、DDL语言和DML语言互相独立

　　1. 五种基本关系代数运算是（）（2001年10月全国卷）

　　A. ∪-，×，π和σ

　　B. ∪-，∞π和σ

　　C. ∪，∩×，π和σ

　　D. ∪，∩∞，π和σ

　　2. 当关系R和S自然联接时能够把R和S原该舍弃的え组放到结果关系中的操作是（）（2001年10月全国卷）

　　3.设有关系R和S，与R-S等价的元组关系演算表达式是（ ）（2003年1月全国卷）

　　4.设关系R（AB，C）和S（AD），与自然连接RS等价的关系代数表达式是（ ）（2003年1月全国卷）

　　B.R（等值连接1=1）S

　　5.在关系模型中关系的“元数”（arity）是指（ ）（2002年10月全国卷）

　　6.有关系R和S，R∩S的运算等价于（ ）（2002年10月全国卷）

　　7.设关系R和S的属性个数分别为r和s则（R×S）操作结果的属性个數为（ ）（2002年10月全国卷）

　　9.下列运算中（）不是关系代数的基本操作。

　　10.在关系中能唯一标识元组的属性集称为关系模型的（）

　　11.当两个关系没有公共属性时，其自然联接表现为（）

　　12.σF1（σF2（E））与（）等价。

　　A、σ（F1∧F2）（E）

　　D、σ（F1∨F2）（E）

　　13.关系代数的四个组合操作是：交、自然联接、联接和（）

　　14.在关系R和关系S进行自然联接时只把R中原该舍弃的元组保存到新关系中，这种操作称为（）

　　A、从R中选择值为2的分量小于第4个分量值的元组组成的关系

　　B、从R中选择第2个分量值小于第4个分量值的元组组成的关系

　　C、从R中选择第2个分量的值小于4的元组组成的关系

　　D、从R中选择第2个分量小于第4个分量值的元组组成的关系

　　16.在下列查询语言中，与关系代数最接近的语言是（）

　　17.四元关系R的属性A、B、C、D下列叙述中正确的是（）

　　A、∏B，C（R）表示取值为BC的两列组成的关系

　　B、∏2，3（R）表示取值为23的两列组成的关系

　　C、∏B，C（R）与∏23（R）表示的是同一个关系

　　D、∏B，C（R）与∏23（R）表示的不是同┅个关系

　　18.如果F只涉及X中的属性，则∏X（σF（E））等价于（）

　　C、∏F（σX（E））

　　D、σF（∏X（E））

　　19.对关系R进行投影运算后得箌关系S，则（）

　　A、关系R的元组数等于关系S的元组数

　　B、关系R的元组数小于关系S的元组数

　　C、关系R的元组数大于关系S的元组数

　　D、关系R的元组数大于或等于关系S的元组数

　　20.关系R与关系S只有一个公共属性T1是R与S等值联接的结果，T2是R与S等值自然联接的结果则（）

　　A、T1的属性个数等于T2的属性个数

　　B、T1的属性个数小于T2的属性个数

　　C、T1的属性个数大于T2的属性个数

　　D、T1的属性个数大于或等于T2的属性個数

　　21.在关系代数表达式优化策略中，应尽可能早执行（）操作

　　22.关系数据库的查询语言是一种（）语言

　　23.如下两个关系R1和R2，它們进行（）运算后得到R3. R1： R2： R3：

　　24.下面哪一个不是一种关系数据库语言（）

　　25.定义在{12}和{1，2}上的二元关系数为（）

　　26.关系代数、元组關系演算和域关系演算这三种数据库语言之间的关系是（）

　　要查找选修“COMPUTER”课程的女学生的姓名将涉及到关系（）

　　28.在关系代数Φ，对一个关系做操作后新关系的元数个数（）原来关系的元素个数。

　　29.一般情况下当对关系R和S使用自然联接时，要求R和S至少含有┅个共同的（）

　　30.在关系数据模型中通常可以把__称为属性，而把__成为关系模式（）

　　B、字段、记录类型

　　31.下列各种对关系数据庫的基本操作中，__是从表中取出满足某种条件的属性成分操作即从列的方向进行选择所需的值；__是表中选取满足某种条件的元组的操作，相当于在横向进行选择

　　1. 下列聚合函数中不忽略空值 （null） 的是（）（2001年10月全国卷）

　　2. SQL中，下列涉及空值的操作不正确的是（）（2001年10月全国卷）

　　3.视图是一个“虚表”，视图的构造基于（ ）（2003年1月全国卷）

　　4.SQL语言中SELECT语句的执行结果是（ ）（2003年1月全国卷）

　　A.包括20岁和30岁

　　B.不包括20岁和30岁

　　C.包括20岁但不包括30岁

　　D.包括30岁但不包括20岁

　　6.为了使索引键的值在基本表中唯一，在建立索引的语句中應使用保留字（ ）（2002年10月全国卷）

　　7.在SQL语言中用户可以直接操作的是（）

　　8.在SQL的SELECT语句中，与选择运算对应的命令动词是（）

　　9.在數据库与宿主语言之间传递信息是通过（）

　　10.在SQL语言中对输出结果排序的是（）

　　11.在SELECT语句中使用*，表示（）

　　13.在SELECT语句中使用MAX（列洺）时列名应该（）

　　C、必须是数值型或字符型

　　D、不限制数据类型

　　A、在WHERE中出现

　　B、在FROM中出现

　　15.在嵌入式SQL中，当SQL语句中引鼡宿主语言的程序变量时程序变量应（）

　　16.在SELECT语句中，对应关系代数中“投影”运算的语句是（）

　　17.视图建立后在数据字典中存放的是（）

　　D、产生视图的表的定义

　　18.在SQL语言中，DELETE语句的作用是（）

　　C、删除基本表和视图

　　D、删除基本表和视图的元组

　　19.在SQL語言中使用FOREIGN KEY时与之配合的语句是（）

　　A、删除基本表S中的所有元组

　　B、把基本表S及产生的一切视图全部删除

　　C、当没有由S中的列產生的视图或约束时将表S删除

　　D、删除表S，将引用表S的视图中的一切视图的属性值置为空值

　　21.下列关于视图与基本表的对比正确的是（）

　　A、视图的定义功能强于基本表

　　B、视图的操作功能强于基本表

　　C、视图的数据控制功能弱于基本表

　　D、上面提到的三种功能二者均相当

　　今向S表插入如下行时哪一行可以被插入

　　23.下列关于视图的说法错误的是（）

　　A、视图是从一个或多个基本表导出嘚表，它是虚表

　　B、某一用户可以定义若干个视图

　　C、视图一经定义就可以和基本表一样被查询、删除和更新

　　D、视图可以用来定義新的视图

　　24.下列关于关系数据库语言SQL语言的说法不正确的是（）

　　A、SQL支持数据库的三级模式结构

　　B、SQL的功能包括查询、操作、定義和控制等四个方面

　　C、SQL是作为独立语言由联机终端用户在交互环境下使用的命令语言它不能嵌入高级语言内

　　D、SQL除应用在数据库領域外，还在软件工程、人工智能领域有广泛的应用

　　25.SQL与C语言处理记录的方式是不同的当将SQL语句嵌入到C语言程序时，为协调两者而引叺（）

　　27.对所有的视图都可以进行下面哪一个操作（）

　　28.SQL语言具有数据定义、数据操纵和数据控制的功能，它的一次查询的结果是┅个（）

　　29.SQL的DDL语句不包括（）

　　30.索引的描述存放在下列哪一项所指示的对象中（）

　　31.试图是由下面哪两者导出的表（）

　　C、基本關系、关系

　　D、内模式、外模式

　　32.SQL语言具有多种优点那么SQL是（）成为关系数据库语言的国际标准的。

　　33.在下列的SQL语句中属于数據控制的是（）

　　34.SQL语言具有两种使用方式，它们在使用的细节上会有些差别特别是SELECT语句。这两种不同使用方式的SQL分别称为交互式SQL和（）

　　A. 是无损联接，也是保持FD的分解

　　B. 是无损联接但不保持FD的分解

　　C. 不是无损联接，但保持FD的分解

　　D. 既不是无损联接也不保歭FD 的分解

　　2. 关系模式R分解成ρ = {R1，…Rk}，F是R上的一个FD集那么R中满足F的每一个关系r，与其投影联接表达式mρ（r） 间的关系满足 （）（2001年10月铨国卷）

　　A. r包含于mρ（r）

　　B. mρ（r）包含于r

　　3.在关系模式R（AB，C）中有函数依赖集F={（A，B）→C（B，C）→A}则R最高达到（ ）（2003年1月全國卷）

　　那么分解ρ具有无损联接性的充分必要条件为（ ）（2003年1月全国卷）

　　5.设有关系模式R（A，BC，D）F是R上成立的FD集，F={B→CC→D}，则屬性C的闭包C+为（ ）（2002年10月全国卷）

　　6.关系模式分解的无损联接和保持函数依赖两个特性之间的联系是（ ）（2002年10月全国卷）

　　A.前者成立蘊涵后者成立

　　B.后者成立蕴涵前者成立

　　C.同时成立或者同时不成立

　　D.没有必然的联系

　　7.在关系模式R（U）中，如果X→Y和X→Z成立那么X→YZ也成立。这条推理规则称为（）

　　8.设有关系模式R（AB，C）F是R上成立的FD集，F={A→BC→B}，则相对于F关系模式R的主键为（）

　　9.设有關系模式R（A，BC），F是R上成立的FD集F={A→C，B→C}那么F在模式R上的投影πAB（F）为（）

　　D、不存在非平凡的FD

　　10.设有关系模式R（A，BC），F是R上荿立的FD集F={A→B，B→C}那么F在模式R上的投影πAC（F）为（）

　　D、不存在非平凡的FD

　　11.设有关系模式R（A，BC），F是R上成立的FD集F={B→C，C→A}那么ρ={AB，BC}相对于F（）

　　A、是无损联接分解，也是保持FD的分解

　　B、是无损联接分解但不保持FD

　　C、不是无损联接分解，但保持FD

　　D、既鈈是无损联接分解也不保持FD

　　12.在关系模式R（U，F）中如果X→Y，存在X的真子集X1使X1→Y，称函数依赖X→Y为（）

　　13.在关系模式R（UF）中，洳果X→U则X是R的（）

　　14.在关系模式R（U，F）中如果F是最小函数依赖集，则（）

　　D、R的规范化程度与F是否最小函数依赖集无关

　　15.在关系模式R（UF）中，R中任何非主属性对键完全函数依赖是R∈3NF的（）

　　D、既不充分也不必要条件

　　16.在二元关系模式R（UF）中，XY都是单一屬性，如果X→Y则R最高可以达到（）

　　17.设有关系模式R（A，BC，D）F是R上成立的FD集，F={B→CD→C}，属性集AB的闭包（AB）+为（）

　　18.设有关系模式R（AB，CD），F是R上成立的FD集F={A→D，C→D}则相对于F，关系模式R的主键为（）

　　19.规范化理论是关系数据库进行逻辑设计的理论依据根据这個理论，关系数据库中的关系必须满足其每一属性都是（）

　　20.关系模式R（AB，CD，E）中有下列函数依赖：A→BCD→E，C→D.下述分解中哪一个（或哪些）分解可保持R所有的函数依赖关系（）

　　I（AB，C）（CD，E） II（AB）（A，CD，E）

　　21.下列关于规范化理论各项中正确的是（）

　　A、对于一个关系模式来说规范化越深越好

　　B、满足二级范式的关系模式一定满足一级范式

　　C、一级范式要求一非主码属性完全函數依赖关键字

　　D、规范化一般是通过分解各个关系模式实现的，但有时也有合并

　　22.根据关系数据库规范化理论关系数据库中的关系偠满足第一范式，下面“部门”关系中因哪个属性而使它不满足第一范式（）

　　部门（部门号，部门名部门成员，部门总经理）

　　23.在下面的两个关系中职工号和部门号分别为职工关系和部门关系的主键（或称主码）

　　职工（职工号、职工名、部门号、职务、工資）

　　部门（部门号、部门名、部门人数、工资总额）

　　在这两个关系的属性中，只有一个属性是外键（或称外来键、外码、外来码）它是（）

　　A、职工关系的“职工号”

　　B、职工关系的“部门号”

　　C、部门关系的“部门号”

　　D、部门关系的“部门号”

　　24.關系模式R（A，BC，DE）中有下列函数依赖：A→BC，D→EC→D.下面对R的分解中哪一个（或哪一些）是R的无损连接分解（）

　　I（A，BC）（C，DE） II（A，B）（AC，DE）

　　25.在一个关系R中，若每个数据项都是不可分割的那么关系R一定属于（）

　　26.对于关系R，第三范式是R中的每个非主属性应满足（）

　　A、与主关键字存在单值依赖关系 B、与主关键字存在多值依赖关系 C、函数传递依赖主关键字 D、非函数传递依赖主关键字

　　27.在关系模式R（姓名年龄，职位出生日）中最有可能做主关键字的是（）

　　28.设有关系模式W（C，PS，GT，R）其中各属性的含义是：C課程，P教师S学生，G成绩T时间，R教室根据定义有如下数据依赖集

　　D={C→G，（SC）→G，（TR）→C，（TP）→R，（TS）→R}关系模式W的一个關键字是__，W的规范化程度最高达到__（）

　　A、（S，C）1NF

　　B、（T，R）3NF

　　C、（T，P）4NF

　　D、（T，S）2NF

[数据结构（.cn邮编:100084 总机:客户服 务: 责任编辑:付弘字 甲刷者:北京密云胶印厂 装订者:三河市李旗庄少明装订厂 发行者:新华书店总店北京发行所 版次:2005年7月第1版2005年7月第1次印刷 号:IsBNX/TP·7179 印数:I-4000 萣价:29.00元 FOREWORD 前言 设计解决实际问题的计算机软件系统,首先需要建立被处理对象的 数据模型数据和世上万物一样,都是具有结构的。因此,人们很洎然 地用数据结构表示应用领域的被处理对象为了模拟实际问题的求解 程和现实对象的行为,还必须提供对数据结构的相应操作。数据结構的 实现是由下一层数据结构表示上一层数据结构,直至由程序没计语言提 供的基本数据类型表示的过程评价数据结构表示优劣的标准主偠是其 能否方便且有效地实现需要的操作,而实现操作的算法设计及其效率高 低也依赖于数据结构表示。因此,数据结构的定义、表示以及操莋的实 现相互关联,都是数据结构研究的重要内容 计算机软件系统可看成是通过不同层次的数据结构及其操作实现 的。通过多层表示,完成計算机对应用领域问题的求解过程在此,中 层数据结构起着核心作用。数据结构的研究产生了一批通用性强、具 有很高实用价值的中间层數据结构,如数组、字符串、集合、线性表 栈、队列、链表、树、图、符号表等这些结构不仅为我们提供了设计 次件系统的有用工具,而且姠我们展示了在广泛的应用领域表示与解决 题的精巧思路和技术。系统地学习和握数据结构知识和方法,对于 提高设计与开发软件系统尤其昰复杂软件系统的能力,无疑是十分重要 的因此,数据结构早已戌为计算机科学与技术和软件工程等专业的核 心课程 数据结构课程内容丰富,涵盖了计算机科学与技术的许多重要的成 分析问题和解决问题的思路和方法新颖,创新点多,技巧性强,对 学生专业素质的培养作用明显,但同时吔是一门较难学习的课程。我校 计算机科学与工程系开设的“数据结构”课程一直采用美国南加州大学 教授E. Horowitz等编著的(数据结构基础》作为敎材该书注重培养学 生分析问题、解决问题的能力,在数据结构和算法设计以及时空复杂性 分析的深度和广度方面特色明显。但在教学中吔感到该书内容的表达形 数据结构( 术) 式学生较难理解,方法和技术的论述还不够简明扼要,有的内容不够精炼,部分章节存 在一些小错误,教学效果较多依赖于教师的讲解为此,编者在充分继承该书体系结构 和内容优点的基础上,吸收其他教材长处,进行优化整合,并结合自身多年的教学妀革 与实践经验,编写了这本教材,力图使其系统全面,内容深刻,表达简洁,易于理解, 以适应计算机科学与技术及相关专业的教学需要。 本书共分為8章第1章论述数据结构的基本概念和方法,包括数据结构与软件系 统,数据抽象与封装,算法,递归,性能分析、性能测量,以及效率与权衡等。特別引 入了代价分摊分析方法,将相关的操作序列联系起来分析,从而得到更接近实际代价的 结果此外,还从软件重用的角度描述了C++的模板机制。 第2章介绍线性表的概念及其顺序表示方法,讨论了通过线性表表示的多项式、稀 疏矩阵和字符串等结构在描述著名的字符串模式匹配算法KMP时,采用了简明易懂的 图示方法。还通过两个字符串的最长公共子序列问题的求解,展示了利用动态规划改进 算法效率的方法由于栈和队列是受限的线性表,因此也被整合到这一章。此章不仅给 出了通用栈和队列的实现方法,还分别通过求解迷宫问题、表达式计算以及机场模拟問 题描述了栈和队列的应用 第3章论述以链表形式实现线性表的方法和技术,讨论了遍历通用模板类容器对象 的游标技术还介绍了广义表的功能及其实现方法,并结合C++的动态类型,讨论了异 构表的实现方法。 第4章介绍最基本的非线性结构—树,包括树和森林的概念、二叉树、二叉树嘚 遍 历及应用、线索二叉树、胜者树、败者树、森林的二叉树表示及遍历、树在并查集问 题中的应用和二叉树计数等特别给出了有一定难喥的中序线素二叉树的后序遍历算法 还给出了生成所有可能的二叉树的算法 第5章介绍支持各种优先队列的堆结构,包括最大堆、最大最小堆、双堆、左偏树、 项式堆和斐波纳契堆在分析二项式堆和斐波纳契堆的性能时,采用了代价分摊方法。 第6章介绍更普遍的非线性结构一一圖,包括图的定义和表示方法、图的遍历 的连通性、最小代价生成树、最短路径和传递闭包以及活动网络等特别讨论了应用斐 波纳契堆改進最短路径算法性能的技术。 在数据结构中,数据元素之间的次序是一种重要的关系按照数据元素的特定属性 对其进行排序是最频繁的计算任务之一。第7章介绍各种典型的排序方法,包括插入排 序、希尔排序、快速排序、归并排序、堆排序、基数排序、基于链表和映射表排序結果 的顺序化以及外排序 第8章介绍符号表概念以及实现符号表的各种结构,包括二叉查找树、AML树、2-3 树、Sply树、B树、B+树、Trie、静态散列和动态散列等,特别分析了二叉查找树的平 均性能在分析Sply树的性能时,采用了代价分摊方法。此外,还论述了上述结构的 演变关系,帮助读者理解其设计思想 本书可供各种层次的读者选用,既适用于教学,也可供从事相关工作的科技与工程 人员参考可以按“数据结构基础”(64学时,必修)和“高级数據结构”(24~32学 时,选修}两门课组织教学。本书的24、2.9、3.10、4.5、4.84.9、5.2~5.6、6.4、 78、84、8.5、8.7和8.9节可作为“高级数据结构”课程的内容,其余作为“数据结构 基础”课程的内容 本书引用了数据结构研究的大量先进成果,在此,作者谨向这些成果的原创者表示 崇高的敬意和衷心的感谢。同时,对本书所引用的參考文献的作者也表示衷心的感谢 在本书的写作过程中,作者与徐宝文、孙志挥、王莤、徐冬梅、王树梅、吉根林和 张丽晖老师开展了卓有荿效的讨论,并由此得到很多启发南京大学计算机科学与技术 系陈道蓄教授认真审读了全部书稿,并提出了十分宝贵的修改意见,在此对他们表示最 诚挚的谢意。感谢清华大学出版社的鼓励与支持感谢东南大学教学改革基金的资助。 丕要感谢作者的众多学生,他们在数据结构课程学习过程中表现出的热情与执着给了作 者很大的鼓励,与他们的讨论和交流使作者对教学内容和教学方法的改进有了更深刻的 限于作者水岼,书中难免有错误或不足之处,恳请广大读者扰评指正来信请发至 ypjin@seu. edu 2004年12月于东南大学 CONTENTS 目录 第1章基本概念和方法 L.1数据结构与软件系统…… 12数据抽象与封装… 1.3算法定义………… 14递归算法 15性能分析……… 151空间复杂性 1.52时间复杂性 …10 1.53O表示法………… 154代价分摊 16 155实际可行的复杂性 性能测量… 1.7C++Φ的模板 18效率与权衡 习题1 第2章线性表 2线性表与数组…… 22多项式 221多项式的表示 2.2.2多项式相加 23.1稀疏矩阵的表示………… 232稀疏矩阵的转置 0122 24字符串……… VIII 数据结构(C+描述) 241字符串模式匹配的简单算法……………………………………36 24.2字符串模式匹配的KMP算法 243两个字符串的最长公共子序列 25栈…… 2.6隊列…… 27迷宫问题 28表达式计算………… 281表达式… 282后缀表示……… …51 283将中缀转化为后缀……… 29机场模拟 习题2…………………………………………… 第3章链表 31单链表 3.1.1单链表的表示… 31.2基本操作 32可重用链表类 3.21用模板定义链表 323链表操作 3.3环链表 34链式栈和队列 3.5链式多项式 3.51多项式表示… 352多项式相加……… 3.53删除多项式 354环链多项式 等价 37稀疏矩阵的链表实现 37.1稀疏矩阵表示 3.72输入稀疏矩阵……………… 80924 3.7.3删除稀疏矩阵· 链表 391广义表的概念忣表示… 392递归算法 393引用计数、共享与递归表… …100 3.10动态类型与异构表 习题3……… 第4章树… 41树和森林的概念及其表 4.2.1二叉树定义… ……11 422二叉树的性质 …12 423二叉树表示… 114 43二叉树遍历与树游标 43.1中序遄历…………… 4.32前序遍历 117 4.3.3后序遍历………………………………… 118 中序游标 后序游标 ……120 6按层佽遍历 44满足性问题 ……122 45线索二叉树… 4.5.1线索… …25 452中序遍历线索二叉树……… 4.53后序遍历线索二又树… 454将结点插入线索二叉树 46选择树 133 46.1胜者树………… 462败者树 4.7森林的二叉树表示及遍历 4.8集合表示 4.8.1并查集 4.82在等价类问题中的应用…… 49二叉树计数……………… 习题 第5章堆结构……… 51最大堆 51.1优先队列与最大堆…………… …152 5.1.2插入操作