第二章数据结构习题作业.doc

2.6数据的存储结构主要有哪两种？它们之间的本质区别是什么？答：主要有：顺序存储结构和链式存储结构两种。区别: 顺序存储结构是借助元素在存储器的相对位置来表示数据间的逻辑关系，而链式存储结构是借助指针来表示数据间的逻辑关系。2.7 设数据结构的集合为D=d1,d2,d3,d4,d5,试指出下列各关系R所对应的数据结构B=(D,R)中哪些是线性结构，哪些是非线性结构。（1）R=(d1,d2),(d2,d4),(d4,d2),(d2,d5),(d4,d1); ( 2 ) R=(d5,d4),(d4,d3),(d3,d1),(d1,d2); ( 3 ) R=(di,di+1)|i=4,3,2,1; ( 4 ) R=(di,dj)|in时，无叶子结点，则i500，所以501到1000的结点为叶子结点，有500个叶子结点。（2） 。有499个度为2的结点（3） 有1个结点只有非空左子树。2.30 设一棵二叉树其中序和后序遍历为中序：BDCEAFHG 后序：DECBHGFA画出这棵二叉树的逻辑结构，并写出先序遍历结果。 其逻辑结构如下：