问题 单项选择题

在二叉树的顺序存储中,每个节点的存储位置与其父节点、左右子树节点的位置都存在一个简单的映射关系,因此可与三叉链表对应。若某二叉树共有n个节点,采用三叉链表存储时,每个节点的数据域需要d个字节,每个指针域占用4个字节,若采用顺序存储,则最后一个节点下标为k(起始下标为1),那么()时采用顺序存储更节省空间。

A.d<12n/(k-n)

B.d>12n/(k-n)

C.d<12n/(k+n)

D.d>12n/(k+n)

答案

参考答案:A

解析:

顺序存储所需空间为kd,三叉链存储所需空间为n(d+4×3),当kd<n(d+12),即时,顺序存储更节省空间。对完全二叉树,k等于n,显然不论d值大小,顺序存储更省空间。

多项选择题
填空题