数据结构JAVA语言描述习题答案刘小晶等主编pdf总复习学习教案.pptx

《数据结构JAVA语言描述习题答案刘小晶等主编pdf总复习学习教案.pptx》由会员分享，可在线阅读，更多相关《数据结构JAVA语言描述习题答案刘小晶等主编pdf总复习学习教案.pptx（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1数据结构数据结构JAVA语言描述语言描述(mio sh)习题习题答案刘小晶等主编答案刘小晶等主编pdf总复习总复习第一页，共17页。（1）数据结构：包括逻辑结构和存储结构；）数据结构：包括逻辑结构和存储结构；（2）逻辑结构有几类？存储结构有几类？）逻辑结构有几类？存储结构有几类？（3）算法）算法(sun f)的时间复杂度分析（关键操作）的时间复杂度分析（关键操作）第1页/共17页第二页，共17页。n线性表的顺序线性表的顺序(shnx)和链式存储的定义及特点和链式存储的定义及特点；n顺序顺序(shnx)表和链表上的基本操作；表和链表上的基本操作；n课后习题一、二、三（课后习题一、二、三（

2、2,5,8）.第2页/共17页第三页，共17页。第3页/共17页第四页，共17页。第4页/共17页第五页，共17页。例例1假设按低下标优先存储整数假设按低下标优先存储整数(zhngsh)数组数组A9358时，第一个元素的字节地址是时，第一个元素的字节地址是100，每个整，每个整数数(zhngsh)占占 四个字节，问元素四个字节，问元素a3125的地址是什么？的地址是什么？LOC（a3125)= ？100+(3358+158+28+5)4 =1784例例2 设有数组设有数组A1.8,1.10，数组的每个元素占，数组的每个元素占3字节字节(z ji)，数组从内存首地址，数组从内存首地址BA开始以列

3、序为主序顺序存放，开始以列序为主序顺序存放，求数组元素求数组元素 a5，8的存储首地址的存储首地址. LOC（a5,8)= BA+(78+4) 3= BA+180第5页/共17页第六页，共17页。第6页/共17页第七页，共17页。1. 1. 将如下将如下(rxi)(rxi)图的森林转换为二图的森林转换为二叉树叉树ABCDEFGK LM NHIJ2. 2. 假设用于通讯假设用于通讯(tngxn)(tngxn)的电文仅由的电文仅由6 6个字母组成个字母组成，字母在电文中出现的频率分别为：，字母在电文中出现的频率分别为：7 7，9 9，2 2，6 6，3232，3 3。试为这。试为这6 6个字母设计

4、哈夫曼编码。个字母设计哈夫曼编码。第7页/共17页第八页，共17页。第8页/共17页第九页，共17页。例例1：已知一个：已知一个(y )图，若从顶点图，若从顶点v1出发分别写出出发分别写出 按深度优先搜索法进行遍历和按广度优先搜按深度优先搜索法进行遍历和按广度优先搜 索法进行遍历的一种可能得到的顶点序列。索法进行遍历的一种可能得到的顶点序列。V1V2V3V4V5V6深度深度(shnd)优先搜索法遍历序列：优先搜索法遍历序列： V1,V2,V3,V5,V6,V4广度优先广度优先(yuxin)搜索法遍历序搜索法遍历序列列: V1,V2,V3,V4,V5,V6第9页/共17页第十页，共17页。例例2

5、：已知一个图的邻接表存储结构如下图，若从顶点：已知一个图的邻接表存储结构如下图，若从顶点v1出发分别写出有向图按深度优先搜索法进行出发分别写出有向图按深度优先搜索法进行(jnxng)遍历和按广度优先搜索法进行遍历和按广度优先搜索法进行(jnxng)遍历的得到的顶遍历的得到的顶点序列。点序列。深度深度(shnd)优先搜索法遍历优先搜索法遍历序列：序列： V1,V2,V3,V5,V6,V4广度优先搜索广度优先搜索(su su)法法遍历序列遍历序列: V1,V2,V3,V4,V5,V6V1 V2 V3 V4 V5V6 23455 01234512024 3100第10页/共17页第十一页，共17页。

6、 设有如下的两个网络设有如下的两个网络, 分别用普里姆分别用普里姆(Prim)算法和算法和克鲁斯卡尔克鲁斯卡尔(Kruskal)算法具体构造相应算法具体构造相应(xingyng)的最的最小生成树。小生成树。 写出过程。写出过程。abdefc6536255164第11页/共17页第十二页，共17页。第12页/共17页第十三页，共17页。第13页/共17页第十四页，共17页。第14页/共17页第十五页，共17页。例如例如(lr): 关键字集合关键字集合 19, 01, 23, 14, 55, 68, 11, 82, 36 设定设定(sh dn)哈希函数哈希函数 H(key) = key MOD 1

7、1 ( 表长表长=11 )190123145568若采用若采用(ciyng)线性探测再散列处理冲突线性探测再散列处理冲突1182361 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第15页/共17页第十六页，共17页。1901231468若采用二次探测再散列处理若采用二次探测再散列处理(chl)冲突冲突55118236例如例如(lr): 关键字集合关键字集合 19, 01, 23, 14, 55, 68, 11, 82, 36 设定设定(sh dn)哈希函数哈希函数 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第16页/共17页第十七页，共17页。