Arrays store homogeneous elements (same type) with natural ordering by index. Records can store heterogeneous elements (different types) without requiring a natural ordering among fields. Records can form hierarchical structures through nested records, unlike simple linear arrays. All three statements correctly distinguish arrays from records.