单选题 在二叉树的顺序存储中，每个结点的存储位置与其父结点、左右子女结点的位置都存在一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有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
【答案解析】[解析] 在三叉链表中，每个结点占用的字节数是d+4×3=d+12。若二叉树有n个结点，总共三叉链表需要(d+12)×n个字节。相应的顺序存储情形下，若最后一个结点下标为k(起始下标为1)，则需要d×k个字节，只有当d×k＜(d+12)×n，即d＜12n/(k-n)时使用顺序存储才更节省空间。