arrays - 数据结构的选择

Question

我在 CS GRE 样本测试中发现了以下问题，但无法确定它是 a) 还是 e) 谁能指出它是哪一个？

提前致谢

哪种数据结构最适合实现具有以下三个特征的值集合？

项目按照 FIFO 顺序从集合中检索和删除。 集合中的项目数量没有先验限制。 项目的大小相对于内存地址所需的存储来说很大。 A) 单链表，有头指针和尾指针 B) 双链表，只有头指针 C) 数组 D) 二叉树 E) 哈希表

Answer 1

1. 项目按照 FIFO 顺序从集合中检索和删除。
2. 集合中的项目数量没有先验限制。
3. 相对于内存地址所需的存储空间，项目的大小较大。

鉴于要求 1 和 2，我会说 Singly-linked list ，带有头和尾指针是您最好的选择。您可以使用尾指针快速插入元素并使用头指针删除元素。

您可以根据一个或多个要求消除其他每个选项。

双向链表，只有一个头指针——只有一个头指针很难实现 FIFO 要求。

数组 - 对集合的大小施加先验限制，而其他数据结构则没有。

二叉树 - 不以方便实现 FIFO 的方式组织元素。

哈希表 - 使 FIFO 不可能实现。