数据结构JAVA语言描述习题答案(刘小晶等主编).pdf总复习.ppt

第1章 （1）数据结构：包括逻辑结构和存储结构； （2）逻辑结构有几类？存储结构有几类？ （3）算法的时间复杂度分析（关键操作） 第2章 n线性表的顺序和链式存储的定义及特点； n顺序表和链表上的基本操作； n课后习题一、二、三（2,5,8）. 第3章 n n 栈和队列的概念、特点；栈和队列的概念、特点； n n 栈和队列的顺序和链式存储，及定义在其上栈和队列的顺序和链式存储，及定义在其上 的基本操作；的基本操作； n n 习题一、二、三习题一、二、三(1,2)(1,2) 第4章 n n 串的概念；串的概念； n n 串的存储方式，掌握顺序串的基本操作。串的存储方式，掌握顺序串的基本操作。 n n 数组的顺序存储，已知基地址，求任意元素地址；数组的顺序存储，已知基地址，求任意元素地址； n n 特殊矩阵的压缩存储：对称阵、三角阵；特殊矩阵的压缩存储：对称阵、三角阵； n n 习题一、二、三习题一、二、三(7).(7). 例1假设按低下标优先存储整数数组A9358时， 第一个元素的字节地址是100，每个整数占 四个字节，问元素a3125的地址是什么？ LOC（a3125)= ？ 100+(3358+158+28+5)4 =1784 例2 设有数组A18,110，数组的每个元素占3 字节，数组从内存首地址BA开始以列序为主序顺 序存放，求数组元素 a5，8的存储首地址. LOC（a5,8)= BA+(78+4) 3= BA+180 第5章 n n 树和二叉树的基本概念；树和二叉树的基本概念； n n 二叉树的性质二叉树的性质154 154； ； n n 二叉树的顺序和链式存储；二叉树的顺序和链式存储； n n 二叉树的四种遍历方法，能写出正确的遍历序列；二叉树的四种遍历方法，能写出正确的遍历序列； n n 二叉树的建立：先根和中根，后根和中根。二叉树的建立：先根和中根，后根和中根。 n n 构造哈夫曼树和哈弗曼编码，求哈弗曼树的构造哈夫曼树和哈弗曼编码，求哈弗曼树的WPLWPL； n n 树、森林、二叉树之间的转换；树、森林、二叉树之间的转换； n n 习题一、二习题一、二 1. 将如下图的森林转换为二叉树 A BCD E F G K LM N H IJ 2. 假设用于通讯的电文仅由6个字母组成，字 母在电文中出现的频率分别为：7，9，2，6， 32，3。试为这6个字母设计哈夫曼编码。 第6章 n n 图的基本概念；图的基本概念； n n 图的存储结构：邻接矩阵和邻接表。定义在其上的基图的存储结构：邻接矩阵和邻接表。定义在其上的基 本操作。本操作。 n n 图的图的DFSDFS和和BFSBFS序列；序列； n n 最小生成树的构造：克鲁斯卡尔、普里姆算法过程；最小生成树的构造：克鲁斯卡尔、普里姆算法过程； n n 最短路径：迪杰斯特拉算法。最短路径：迪杰斯特拉算法。 n n 习题一、二、三习题一、二、三(1,3,4)(1,3,4) 例1：已知一个图，若从顶点v1出发分别写出 按深度优先搜索法进行遍历和按广度优先搜 索法进行遍历的一种可能得到的顶点序列。 V1 V2V3 V4 V5V6 深度优先搜索法遍历序列： V1,V2,V3,V5,V6,V4 广度优先搜索法遍历序列: V1,V2,V3,V4,V5,V6 例2：已知一个图的邻接表存储结构如下图，若从顶点 v1出发分别写出有向图按深度优先搜索法进行遍历和按 广度优先搜索法进行遍历的得到的顶点序列。 深度优先搜索法遍历序列： V1,V2,V3,V5,V6,V4 广度优先搜索法遍历序列: V1,V2,V3,V4,V5,V6 V1 V2 V3 V4 V5 V6 2 3 4 5 5 0 1 2 3 4 5 12 0 2 43 1 0 0 例题： 设有如下的两个网络, 分别用普里姆(Prim)算法 和克鲁斯卡尔(Kruskal)算法具体构造相应的最小生 成树。 写出过程。 a bd ef c 6 5 3 6 2 5 5 1 6 4 第7章 n n 各种内部排序算法的原理、执行过程、时间复杂度、各种内部排序算法的原理、执行过程、时间复杂度、 稳定性。稳定性。 n n 习题一、二；习题一、二； 例题 1.以关键字序列53，07，52，01，98，10，87， 25，63，46为例，手工执行直接插入排序、希尔排 序（增量为5，2，1）、快速排序、归并排序算法， 完成： （1）写出每一种排序的每一趟排序结束时的关 键字序列； （2）分析哪些排序是稳定的，哪些是不稳定， 并为每一种不稳定的排序方法举出一个不稳定的实例 。 第8章 n n 各种查找算法的原理；各种查找算法的原理； n n 求查找算法的求查找算法的ASLASL； n n 习题一、二；习题一、二； 例如: 关键字集合 19, 01, 23, 14, 55, 68, 11, 82, 36 设定哈希函数 H(key) = key MOD 11 ( 表长=11 ) 190123 145568 若采用线性探测再散列处理冲突 11 8236 1 1 2 1 3 6 2 5 1 查找次数 ASL(成功）= ASL(不成功）= 产生二次聚集 （4*1+2*2+3+5+6）/9=22/9 （10+9+1+1）/11=56/11 0 1 2 3 4 5 6 7 8 9 10 190123 1468 若采用二次探测再散列处理冲突 55 118236 例如: 关键字集合 19, 01, 23, 14, 55, 68