《数据结构》作业参考答案

《《数据结构》作业参考答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》作业参考答案《数据结构》作业参考答案一、选择题1．ab2．c3．　b4．　a,d5．b6．d7．　b8．D9．D10．B11．C12．C　13．c14．d15．a16．b17．c18．d19．c20．b21．b22．c23．c24．d25．d26．c二、填空题1．2．343．2k-1,2k-1,2k-2+14．v1,v3,v2,v4,v55．46．数据项7．结点的直接前驱结点，结点的直接后继结点8．ST.top==-19．参加比较的两个字符串长度相同10．11．120第12页共12页《数据结构》作业参考答案三、算法应用题1．623725191812139104567

2、解答：WPL=4*4+5*4+6*3+7*3+10*3+12*2+18*2=9*4+23*3+30*2=36+69+60=1652．解答：和已知序列对应的二叉树是：FACDGJKHIBE3．第12页共12页《数据结构》作业参考答案4．解答：各关键字的哈希函数值见下表：key190123145520842768111077H(key)=key%136110137613111012采用开放地址法的线性探测再散列方法解决冲突，已知其装填因子，对上表中的关键字序列构造所得哈希表如下：地址01234567891011121314151617key011455276819208423111

3、077比较次数121431131132在等概率情况下，其查找成功时的平均查找长度是：5．和已知序列对应的森林如下图示：ABDGCEFHIKLJ第12页共12页《数据结构》作业参考答案6．解答：设这8个字母的权重为7，19，2，6，32，3，21，101111111000000023561110717282119403260100由上图的哈夫曼树知这8个字母的哈夫曼编码分别为0010，10，00000，0001，01，00001，11，00117．解答：①如图所示的无向带权图的邻接矩阵如下图示：12345610615∞∞2605∞3∞315056445∞50∞25∞36∞066∞

4、∞4260按Prim算法求得的最小生成树如下图(f)所示（树中结点用粗黑实线表示）：假设初始时，树中只有一个顶点，不含有任何一条边，下图（a）～(f)为用Prim算法求其最小生成树的过程。6246355165V1V2V3V4V5V6(a)2463551656V1V2V3V4V5V6(b)62463551V1V2V3V4V5V665（c）65V1V2V3V4V5V662435165(d)6V56243551V1V2V3V4V665(e)6246355165V1V2V3V4V5V6(f)第12页共12页《数据结构》作业参考答案②如图所示的无向带权图的邻接表如下图示：V1V2V3V4

5、V5V6012345123NULL024NULL013NULL025NULL125NULL234NULL按照Kruskal算法求得的最小生成树如下图（f）所示（树中结点用粗黑实线表示），假设初始时，树中含有全部顶点，但不含有任何一条边，下图（a）～(f)为用Kruskal算法求最小生成树的过程。6246355165V1V2V3V4V5V66246355165V1V2V3V4V5V6(b)62463551V1V2V3V4V5V665（c）56365V1V2V3V4V5V624165(d)63624551V5V1V2V3V4V665(e)6246355165V1V2V3V4V5V6

6、(f)(a)8．解答：①　快速排序的最好情况是指，排序所需的“关键字间的比较次数”和“记录的移动次数”最少的情况，在n=7时，至少需要进行2趟排序。因此，当n=7时在最好情况下需进行的比较次数是10次。②　n=7时的一个最好情况的初始排列实例是：4，7，5，6，3，1，2第12页共12页《数据结构》作业参考答案9．解答：对长度为20的有序表进行斐波那契查找的判定树如下图示：1381851116203710121517192469141其等概率查找时查找成功的平均查找长度为：10．a9=4a8=7a7=9a5=1a4=1a3=5a2=4a1=6V11V21V31V41V51V61

7、V71V81V91a6=2a10=2a11=4解答：上图所示AOE网中各顶点事件的最早发生时间Ve(i)和最迟发生时间Vl(i)如下表示：V1V2V3V4V5V6V7V8V9Ve(i)064577161418Vl(i)0668710161418上图所示AOE网中各活动的最早开始时间e(i)和最迟开始时间l(i)如下表示：a1a2a3a4a5a6a7a8a9a10a11e(i)0006457771614l(i)02366877101614有上表的可见活动a1,a4,a7,a8,a10,a11的