《数据结构JAVA语言描述习题答案(刘小晶等主编).pdf总复习》由会员分享，可在线阅读，更多相关《数据结构JAVA语言描述习题答案(刘小晶等主编).pdf总复习（17页珍藏版）》请在金锄头文库上搜索。
1、第1章（1）数据结构：包括逻辑结构和存储结构；）数据结构：包括逻辑结构和存储结构；（2）逻辑结构有几类？存储结构有几类？）逻辑结构有几类？存储结构有几类？（3）算法的时间复杂度分析（关键操作）算法的时间复杂度分析（关键操作）第2章n线性表的顺序和链式存储的定义及特点；线性表的顺序和链式存储的定义及特点；n顺序表和链表上的基本操作；顺序表和链表上的基本操作；n课后习题一、二、三（课后习题一、二、三（2,5,8）.第3章n n栈和队列的概念、特点；栈和队列的概念、特点；n n栈和队列的顺序和链式存储，及定义在其上栈和队列的顺序和链式存储，及定义在其上的基本操作；的基本操作；n n习题一、二、三习题
2、一、二、三(1,2)第4章n n串的概念；串的概念；n n串的存储方式，掌握顺序串的基本操作。串的存储方式，掌握顺序串的基本操作。n n数组的顺序存储，已知基地址，求任意元素地址；数组的顺序存储，已知基地址，求任意元素地址；n n特殊矩阵的压缩存储：对称阵、三角阵；特殊矩阵的压缩存储：对称阵、三角阵；n n习题一、二、三习题一、二、三(7).例例1假假设设按按低低下下标标优优先先存存储储整整数数数数组组A9358时时，第一个元素的字节地址是第一个元素的字节地址是100，每个整数占，每个整数占 四个字节，问元素四个字节，问元素a3125的地址是什么？的地址是什么？LOC（a3125)= ？100
3、+(3358+158+28+5)4 =1784例例2 设设有有数数组组A1.8,1.10，数数组组的的每每个个元元素素占占3字字节节，数数组组从从内内存存首首地地址址BA开开始始以以列列序序为为主主序序顺顺序存放，求数组元素序存放，求数组元素 a5，8的存储首地址的存储首地址. LOC（a5,8)= BA+(78+4) 3= BA+180第5章n n树和二叉树的基本概念；树和二叉树的基本概念；树和二叉树的基本概念；树和二叉树的基本概念；n n二叉树的性质二叉树的性质二叉树的性质二叉树的性质154154； n n二叉树的顺序和链式存储；二叉树的顺序和链式存储；二叉树的顺序和链式存储；二叉树的顺序
4、和链式存储；n n二叉树的四种遍历方法，能写出正确的遍历序列；二叉树的四种遍历方法，能写出正确的遍历序列；二叉树的四种遍历方法，能写出正确的遍历序列；二叉树的四种遍历方法，能写出正确的遍历序列；n n二叉树的建立：先根和中根，后根和中根。二叉树的建立：先根和中根，后根和中根。二叉树的建立：先根和中根，后根和中根。二叉树的建立：先根和中根，后根和中根。n n构造哈夫曼树和哈弗曼编码，求哈弗曼树的构造哈夫曼树和哈弗曼编码，求哈弗曼树的构造哈夫曼树和哈弗曼编码，求哈弗曼树的构造哈夫曼树和哈弗曼编码，求哈弗曼树的WPLWPL；n n树、森林、二叉树之间的转换；树、森林、二叉树之间的转换；树、森林、二叉
5、树之间的转换；树、森林、二叉树之间的转换；n n习题一、二习题一、二习题一、二习题一、二1. 1. 将如下图的森林转换为二叉树将如下图的森林转换为二叉树ABCDEFGK LM NHIJ2.2. 假设用于通讯的电文仅由假设用于通讯的电文仅由6 6个字母组成，字个字母组成，字母在电文中出现的频率分别为：母在电文中出现的频率分别为：7 7，9 9，2 2，6 6，3232，3 3。试为这。试为这6 6个字母设计哈夫曼编码。个字母设计哈夫曼编码。第6章n n图的基本概念；图的基本概念；n n图的存储结构：邻接矩阵和邻接表。定义在其上的基图的存储结构：邻接矩阵和邻接表。定义在其上的基本操作。本操作。 n
6、 n图的图的DFS和和BFS序列；序列； n n最小生成树的构造：克鲁斯卡尔、普里姆算法过程；最小生成树的构造：克鲁斯卡尔、普里姆算法过程；n n最短路径：迪杰斯特拉算法。最短路径：迪杰斯特拉算法。 n n习题一、二、三习题一、二、三(1,3,4)例例1：已知一个图，若从顶点：已知一个图，若从顶点v1出发分别写出出发分别写出 按深度优先搜索法进行遍历和按广度优先搜按深度优先搜索法进行遍历和按广度优先搜 索法进行遍历的一种可能得到的顶点序列。索法进行遍历的一种可能得到的顶点序列。V1V2V3V4V5V6深度优先搜索法遍历序列：深度优先搜索法遍历序列： V1,V2,V3,V5,V6,V4广度优先搜
7、索法遍历序列广度优先搜索法遍历序列: V1,V2,V3,V4,V5,V6例例2：已知一个图的邻接表存储结构如下图，若从顶点：已知一个图的邻接表存储结构如下图，若从顶点v1出发分别写出有向图按深度优先搜索法进行遍历和按出发分别写出有向图按深度优先搜索法进行遍历和按广度优先搜索法进行遍历的得到的顶点序列。广度优先搜索法进行遍历的得到的顶点序列。深度优先搜索法遍历序列：深度优先搜索法遍历序列： V1,V2,V3,V5,V6,V4广度优先搜索法遍历序列广度优先搜索法遍历序列: V1,V2,V3,V4,V5,V6V1 V2 V3 V4 V5V6 23455 01234512024 3100例题：例题：
8、设有如下的两个网络设有如下的两个网络, 分别用普里姆分别用普里姆(Prim)算法算法和克鲁斯卡尔和克鲁斯卡尔(Kruskal)算法具体构造相应的最小生算法具体构造相应的最小生成树。成树。 写出过程。写出过程。abdefc6536255164第7章n n各种内部排序算法的原理、执行过程、时间复杂度、各种内部排序算法的原理、执行过程、时间复杂度、稳定性。稳定性。n n习题一、二；习题一、二；例题例题 1. 1.以关键字序列以关键字序列53，07，52，01，98，10，87，25，63，46为例，手工执行为例，手工执行直接插入排序直接插入排序、希尔排希尔排序序（增量为（增量为5 5，2 2，1 1
9、）、）、快速排序快速排序、归并排序归并排序算法，算法，完成：完成： （1 1）写出每一种排序的每一趟排序结束时的关）写出每一种排序的每一趟排序结束时的关键字序列；键字序列； （2 2）分析哪些排序是稳定的，哪些是不稳定，）分析哪些排序是稳定的，哪些是不稳定，并为每一种不稳定的排序方法举出一个不稳定的实例。并为每一种不稳定的排序方法举出一个不稳定的实例。第8章n n各种查找算法的原理；各种查找算法的原理；n n求查找算法的求查找算法的ASL；n n习题一、二；习题一、二；例如例如: 关键字集合关键字集合 19, 01, 23, 14, 55, 68, 11, 82, 36 设定哈希函数设定哈希函
10、数 H(key) = key MOD 11 ( 表长表长=11 )190123 145568若采用线性探测再散列处理冲突若采用线性探测再散列处理冲突11 82361 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 10190123 1468若采用二次探测再散列处理冲突若采用二次探测再散列处理冲突55118236例如例如: 关键字集合关键字集合 19, 01, 23, 14, 55, 68, 11, 82, 36 设定哈希函数设定哈希函数 H(key) = key MOD 11 ( 表长表长=11 )ASL(成功）成功）=1 1 2 1 2 1 4 1 3 （1*5+2*1+3+4）/9=14/9 0 1 2 3 4 5 6 7 8 9 10
