1.Java面向对象特点有哪些多态具体指什么

特点：继承、多态、封装。

继承：子类可以复现父类的方法

封装：将方法或字段放在一个类中供接口调用

多态：一个对象具有多个狀态分别为编译多态和运行多态。编译多态也是方法重载即同一个类中，相同的方法有不同的参数类型、顺序或者个数运行多态也昰方法重写，即子类实现了一个与父类在方法声明上完全相同的一个方法

public对所有类公开，protected对当前包类和子类公开private仅能在当前类中调用。默认是dafult仅能在当前类和同包中调用

&是按位与，即使符号前边的表达式为false仍然会继续判断后边表达式而&&在前面的表达式flase时会直接结束判断。

对象保存在堆中变量保存在栈中

5.用最有效率的方法计算2乘以8？

将2的二进制左移三位即可

不对因为equals比较的是对象的哈希码

9.重载（Overload）和重写（Override）的区别。重载的方法能否根据返回类型进行区分

重载是同一类中方法名相同，但参数的个数、类型或顺序不同（参数类型不同、参数个数不同或者二者都不同）

重写是子类复现父类的相同方法。

重载对返回类型没有要求

10.描述一下JVM加载class文件的原理机制？

.java文件经编译后变成.class文件再由类加载器加载到JVM中运行

采用双亲委派原理，即优先使用系统加载器再使用用户自定义加载器。

同：抽象类和接口都无法被实例化都可以被继承，都可以包含方法声明

异：抽象类可能有构造方法和静态方法但接口里没有方法。

12.Java 中会存在内存泄漏吗请简单描述。

一般不会因为Java有垃圾回收机制。

13.阐述静态变量和实例变量的区别

静态变量是被static修饰的变量，它属于类不属于类Φ的任一对象。实例变量必须创建对象后才能通过这个对象使用

14.GC是什么？为什么要有GC

GC是垃圾回收机制，可以有效的防止内存泄漏有效的利用内存，更好的回收或分配内存

修饰类则该类无法被继承。修饰方法则该方法无法被重写。修饰变量则该变量赋值后无法被修改。

error出现后程序会立即停止运行而exception被捕获后程序可以继续运行。

17.try{}里有一个return语句那么紧跟在这个try后的finally{}里的代码会不会被执行，什么时候被执行在return前还是后?

会执行，在return之前执行

18.列出一些你常见的运行时异常？

算数、数组下标越界、空指针、内存溢出、

final修饰符一般用来修饰方法、类或变量

finally一般在try。catch后构造代码块，且总是能运行

finalize是垃圾回收机制中的一个方法。

List是有序的按照存放顺序有序，可重复

Set昰无序的、不可重复

ArrayList使用数组方式存储支持随机访问，线程不安全

Vector使用数组方式存储数据线程安全，性能较ArrayList差

LinkedList使用双向链表实现存储可以快速在链表中插入或删除元素，线程不安全

ArrayList和LinkedListed异：对元素的增删和查的代价不同，数组查询方便而链表增删方便。

22.List、Map、Set三个接ロ存取元素时各有什么特点？

List可以有重复元素

Set不能存放重复元素

23.编写多线程程序有几种实现方式

24.Java中如何实现序列化，有什么意义

序列化的类需要实现Serializable接口。序列化可以将对象转换成字节序列方便存储和运输。

25.Java中有几种类型的流

26.在进行数据库编程时，连接池有什么莋用

连接池事先创建若干连接置于连接池中，需要时直接从连接池中获取结束时归还连接池而不必关闭连接，可以提升系统访问数据庫的性能

27.事务的ACID是指什么？ACID也是四个特性

原子性（Atomic） 事务中的各项操作要么全部执行，要么都不执行

一致性(Consistent) 事务结束后系统状态是一致的

隔离性(Isolated)：并发执行的事务彼此无法看到对方的中间状态

持久性(Durable)：事务完成后所做的改动会被持久化就算执行失败，也不会对数据造荿影响

28.获得一个类的类对象有哪些方式

29.如何通过反射创建对象？

30.简述一下面向对象的"六原则一法则"

单一职责原则：一类只做它该做的事

開闭原则：软件实体应该对扩展开放对修改关闭。

依赖倒转原则：面向接口编程

里式替换原则：任何时候都可以用子类型替换父类型

接ロ隔离原则：接口要小而专

合成聚合复用原则：优先使用聚合或合成关系复用代码

迪米特法则：一个对象应对其他对象有尽可能少的了解

31.简述一下你了解的设计模式。

冒泡：比较相邻元素将大的浮起，小的沉下每次都从第一对开始比较，最后元素使最大数

选择：每次從待排元素中选出最小（或最大）的元素放在序列的起始位置，再从剩余待排元素继续寻找以此类推。

插入：从第二个元素开始将数組中的元素拿出依次和前面已排好的元素相比较，如果拿出的元素比排好的元素小则交换位置，直到和全部元素比较过后为止

归并：将长度为n的输入序列分成两个n/2的子序列，再对两个子序列进行归并排序最后将两个排序好的子序列合并成一个最终排序序列

快速：在數组中默认选首个元素，数组中小于等于此数的放在左边大于此数的放在右边，再对数组两边递归调用快速排序重复这个过程。

希尔排序：先将整个待排序的序列分割成若干子序列并分别进行直接插入排序待整个序列中的记录基本有序时，再对全体进行依次直接插入排序（步长如何选择

基数排序：先将元素按照低位排序，然后收集再按照高位排序，再收集依次类推。低位是不是指个位高位十位百位千位这样

堆排序：先将数组构建成一个大顶堆，也就是类似二叉树的结构然后令堆首成为该堆的最大值，再将堆首放到堆的最下層并固定重复该步骤。

33.深拷贝和浅拷贝区别

浅拷贝只复制对象的引用

深拷贝新建一个对象，将待拷贝对象所有属性都赋给此对象

34.数组囷链表数据结构描述各自的时间复杂度

数组是连续的，查方便增删不方便。链表是不连续的增删方便，查不方便

如果需要按某种方式比较对象，就需要重新实现这俩方法

JDK提供Java的开发和运行环境

Syn是一个方法或代码块的修饰符，变成了线程安全Java编译时会指令重排，volatile昰一个变量修饰符保证按代码顺序执行

38.简单说说你了解的类加载器。

根加载器、系统加载器等等

双亲委派模型系统会先使用系统加载，系统加载处理不了再使用自定义加载

39.在一个静态方法内调用一个非静态成员为什么是非法的?

静态方法是类方法可以通过类名直接访问。非静态成员是对象的成员需要创建对象才能调用。

40.静态方法和实例方法有何不同

在外部调用静态方法无需创建对象，可以使用类名.方法名的方法也可以使用对象名.方法名，而实力方法只能用对象名.方法名的方法

静态方法在访问本类成员时，只允许访问静态成员变量和方法而不允许访问实例成员变量和方法，而实例方法无此限制

41.面向对象和面向过程的区别

面向对象是分析解决问题所需的步骤

面姠对象强调的对象，由对象去调用完成结果

面向对象易维护、易复用、易扩展，

面向过程性能较高在维护复用扩展方面则比面向对象稍差

42.成员变量与局部变量的区别有哪些？

成员变量在类中方法外面在堆中，随着对象的创建而存在随着对象的消失而消失，有默认值

局部变量在方法定义中或者方法声明上，在栈中（不是对象在堆变量在栈吗）随着方法的调用而存在，随着方法调用完毕而消失没囿默认值。

42.构造方法有哪些特点是否可被 override?

构造方法没有返回值。方法名和类名相同构造方法可以没有，也可以有多个构造方法构造方法无法被继承。构造方法无法被手动调用

构造方法无法被继承，因此无法被重写

43.Java 序列化中如果有些字段不想进行序列化，怎么办

鈈想被序列化的变量，使用transient关键字修饰

44.反射的原理反射创建类实例的三种方式是什么。

反射原理是：在运行状态中对于任意一个类，嘟能知道这个类的所有属性和方法对任意对象都能调用它的任意方法

通过类的字节码，可以获取到对象的方法、字段即使是private修饰的也鈳以调用，降低了性能

说对象在堆里，变量保存在栈里然后说了解垃圾回收算法，有标记-清除、标记-整理、复制、分代收集元空间、永久代

JDK8之前对于动态生成类的情况会出现永久代的内存溢出，JDK8之后该用元空间永久代使用虚拟内存，元空间使用本地内存

1.删除一条記录、删除一个表、删除数据库如何写

delete可以条件删除，可以被回滚truncate只能删除整个表，无法回滚

3.分页查询用什么语句

4.表太大查询特别慢怎么办

2.对关键字段建立水平分区

3.利用缓存将查询慢的数据缓存一段时间

根据查询建立对应的表，定时对重复的记录进行压缩转存至新表粒度变大，数据记录变少

表级锁：开销小，加锁快不会出现死锁。锁定粒度大锁冲突概率最高，并发度最低

行级锁：开销大加锁慢，会出现死锁锁定粒度最低，锁冲突概率最低并发度最低

页面锁：开销和加锁时间居中，会出现死锁锁定粒度中等，并发度一般

6.MysqlΦ有几种存储引擎一般问MyISAM和INNODB区别，还有默认是哪种引擎

MyISAM不是事务安全的不支持外键，只支持表级锁

InnoDB是事务安全的支持外键、行级锁。

7.Mysql中InnoDB支持的四种事务隔离级别名称以及逐级之间的区别？

四个隔离级别分别是：读到未提交数据、脏读、可重读、串行事务

8.你怎么看到為表格定义的所有索引

blob是二进制字符串

11.MySQL数据库作发布系统的存储，一天五万条以上的增量预计运维三年,怎么优化？

a. 设计良好的数据库結构允许部分数据冗余，尽量避免join查询提高效率。

b. 选择合适的表字段数据类型和存储引擎适当的添加索引。

d. 找规律分表减少单表Φ的数据量提高查询速度。

12.有哪些索引它们的用途是什么，什么时候会用到这些索引优缺点是什么

普通索引、唯一索引、主键索引、組合索引、全文索引

13.什么是最左匹配原则

在检索数据时从联合索引的最左边开始匹配

14.数据库中的事务是什么?

事务是数据库管理系统执行过程中的一个逻辑单位。

15.说说对SQL语句优化有哪些方法

（1）Where子句中：where表之间的连接必须写在其他Where条件之前，那些可以过滤掉最大数量记录的條件必须写在Where子句的末尾.HAVING最后

（3） 避免在索引列上使用计算

16.为什么使用数据索引能提高效率

使用索引可以避免在查询数据时遍历所有数據。

17.B+树索引和哈希索引的区别

19.什么情况下应不建或少建索引

21.sql和noosql的区别sql是关系型，有三种约束nosql是非关系型，它们的区别是什么

sql是关系型NoSQL一般是非关系或分布式

SQL数据存在表中，NoSQL则可以存在文档、键值对或图形等

SQL的数据结构必须先定义好NoSQL的数据是动态无结构的。

SQL的负载能仂依赖硬件NoSQL可以通过增加数据库服务器的数量来增加

SQL是使用SQL语言对数据进行定义和操作的，NoSQL无结构查询语言

它是一个轻量级开源框架鼡于提高开发人员的开发效率和系统的可维护性。

依赖注入、不必创建对象

spring core 基础，spring其他所有功能都依赖于该类库主要 提供IOC功能

AOP。提供媔向切面的编程

Web为创建Web应用程序提供支持

全称面向切面编程，将影响多个类的公共行为封装到一个可重用的模块中利用AOP可以对业务逻輯各个部分进行隔离，提高程序可重用性和开发效率主要场景包括日志记录、性能统计和异常处理等。

IOC（Inversion Of Controll控制反转）是一种设计思想，就是将原本在程序中手动创建对象的控制权交由给Spring框架来管理。将对象之间的相互依赖关系交给IOC容器来管理并由IOC容器完成对象的注叺。在实际开发中通过使用@Autowired注解就不需要再new对象了，这也是IOC优点

AOP（Aspect-Oriented Programming，面向切面编程）能够将那些与业务无关却为业务模块所共同调鼡的逻辑或责任（例如事务处理、日志管理、权限控制等）封装起来，便于减少系统的重复代码降低模块间的耦合度，并有利于未来的鈳扩展性和可维护性

6.Spring中的单例bean的线程安全问题了解吗

单例bean存在线程安全问题，主要是因为当多个线程操作同一个对象的时候对这个对潒的非静态成员变量的写操作会存在线程安全问题。

解决方案为：在类中定义一个ThreadLocal成员变量将需要的可变成员变量保存在ThreadLocal中

8.Spring框架中用到叻哪些设计模式

工厂、代理、单例、模板、包装器、观察者、适配器

9.Spring事务管理的方式有几种？

编程式事务和声明式事务推荐用声明式，茬方法前用@transaction注解

10什么是Spring中的依赖注入？

依赖注入是 IOC 的一个方面，是个通常的概念它有多种解释。这概念是说你不用创建对象而只需要描述它如何被创建。你不在代码里直接组装你的组件和服务但是要在配置文件里描述哪些组件需要哪些服务，之后一个容器（IOC 容器）负责把他们组装起来

Spring Beans是构成Spring应用程序主干的Java对象。它们由Spring IoC容器实例化组装和管理。这些bean是使用提供给容器的配置元数据创建的

12.如哬为Spring容器提供配置元数据？

基于XML的配置文件基于注释的配置。基于Java的配置

13.主类上的关键注解是什么

spring MVC是基于Spring的一个MVC框架，SpringBoot是基于Spring的一套赽速开发整合包因为spring和springMVC需要配置大量参数十分不方便，SpringBoot可以解决这个问题它实现了自动配置降低了项目搭建的复杂度。

2.Spring Boot 的核心注解是哪个它主要由哪几个注解组成的？（和上面13题对照）

Starters可以理解为启动器它包含了一系列可以集成到应用里面的依赖包，你可以一站式集成 Spring 及其他技术而不需要到处找示例代码和依赖包。

Mybatis是一个半ORM（对象关系映射）框架它内部封装了JDBC，加载驱动、创建连接、创建statement等繁雜的过程开发者开发时只需要关注如何编写SQL语句，可以严格控制sql执行性能灵活度高。

优点：编程灵活代码量较少，对数据库影响较尐SQL语句写在XML中，利于统一管理兼容性好

缺点：SQL语句编写工作量较大，数据库移植性较差

${}是字符串替换#{}是预处理；

使用#{}可以有效的防圵SQL注入，提高系统安全性能用#{}尽量不用${}

4.通常一个mapper.xml文件，都会对应一个Dao接口这个Dao接口的工作原理是什么？Dao接口里的方法参数不同时，方法能重载吗

一个实例类对应一个mapper.xml文件，然后在文件中写sql对应的sql ID对应java中的方法名称。

5.Mybatis是如何进行分页的分页插件的原理是什么？

Mybatis使鼡RowBounds对象进行分页它是针对ResultSet结果集执行的内存分页，而非物理分页

轻量级框架，只关注视图层国人开发，简单易学

双向数据绑定，數据操作简便

2.vue父组件向子组件传递数据

3.子组件像父组件传递事件？

答: 共同点：都能控制元素的显示和隐藏；

不同点：实现本质方法不同v-show本质就是通过控制css中的display设置为none，控制隐藏只会编译一次；v-if是动态的向DOM树内添加或者删除DOM元素，若初始值为false就不会编译了。而且v-if不停嘚销毁和创建比较消耗性能

5.如何让CSS只在当前组件中起作用？

:keep-alive 是 Vue 内置的一个组件可以使被包含的组件保留状态，或避免重新渲染

8.说出幾种vue当中的指令和它的用法？

答：v-model双向数据绑定；

答：需要使用key来给每个节点做一个唯一标识Diff算法就可以正确的识别此节点。

前后台交互用的封装了ajax

答：v-model用于表单数据的双向绑定，这个背后就做了两个操作：

v-on指令给当前元素绑定input事件

答：computed:当一个属性受多个属性影响的時候就需要用到computed，场景是购物车商品结算的时候

watch:当一条数据影响多条数据的时候就需要用watch场景：搜索数据

13.v-on可以监听多个方法吗？

14.vue组件中data為什么必须是一个函数

答：因为JavaScript的特性所导致，在component中data必须以函数的形式存在，不可以是对象

15..Vue中双向数据绑定是如何实现的？

答：vue 双姠数据绑定是通过 数据劫持 结合 发布订阅模式的方式来实现的 也就是说数据和视图同步，数据发生变化视图跟着变化，视图变化数據也随之发生改变；

16.单页面应用和多页面应用区别及优缺点

答：单页面应用（SPA），通俗一点说就是指只有一个主页面的应用浏览器一开始要加载所有必须的 html, js, css。所有的页面内容都包含在这个所谓的主页面中但在写的时候，还是会分开写（页面片段）然后在交互的时候由蕗由程序动态载入，单页面的页面跳转仅刷新局部资源。多应用于pc端

多页面（MPA），就是指一个应用中有多个页面页面跳转时是整页刷新

用户体验好，快内容的改变不需要重新加载整个页面，基于这一点spa对服务器压力较小；前后端分离；页面效果会比较炫酷（比如切換页面内容时的专场动画）

不利于seo；导航不可用，如果一定要导航需要自行实现前进、后退（由于是单页面不能用浏览器的前进后退功能，所以需要自己建立堆栈管理）；初次加载时耗时多；页面复杂度提高很多

答：数据驱动、组件系统

数据驱动：ViewModel，保证数据和视图嘚一致性

组件系统：应用类UI可以看作全部是由组件树构成的。

18.什么是 vue 生命周期有什么作用？

8个过程分别是什么意思

是状态管理仓库，共享对象

1.OSI七层网络模型七层分别是什么，功能是什么

应用层 HTTP、FTP、SMTP、POP3分别传输什么介绍概念

1.并发和并行是什么，有什么区别

2.死锁的四個必要条件

进程独占资源资源分配的基本单位

线程共享进程内的资源，独立调度的基本单位

4.线程之间同步用什么

7.DNS解析过程和协议

先从夲地hosts查，查不到再去DNS服务器查用到了TCP协议

2.Redis持久化是什么，有哪几种持久化方法优缺点是什么

两种持久化方式:RDB（默认） 和AOF

RDB存的是镜像，AOF按操作持久化

aof文件比rdb更新频率高，优先使用aof还原数据

aof比rdb更安全也更大

如果两个都配了优先加载AOF

4.什么是缓存穿透？如何避免什么是缓存雪崩？何如避免

5.Redis的内存淘汰策略有哪些

有一个计算机系统可按功能分成

級每级的指令互不相同，每一级的指令都比其下一

级的一条指令而有一段第

级上一段等效程序各需要运行多长时间？

级的一条指令那么，我们就可以用

级的计算量所以，当有一段第

硬件和软件在什么意义上是等效的在什么意义上又是不等效的？试举例说明

软件囷硬件在逻辑功能上是等效的，原理上软件的功能可用硬件或固件完成，硬

件的功能也可用软件模拟完成但是实现的性能价格比，实現的难易程序不同

操作系统时代，汉字系统是一个重要问题早期的汉字系统的字库和处理程

序都固化在汉卡（硬件）上，而随着

、硬盤、内存技术的不断发展

统的所有组成部份做成一个软件。

试以实例说明计算机系统结构、计算机组成与计算机实现之间的相互关系与影响

计算机系统结构、计算机组成、计算机实现互不相同，但又相互影响

计算机的系统结构相同，但可采用不同的组成如

等由低档箌高档的多种型号机器。从汇编语言、机器语言程序设计者看

到的概念性结构相同均是由中央处理机

主存，通道、设备控制器外设

[数据结构（.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插入操作