首页 > 试题广场 >

下列哪些容器可以使用数组，但不能使用链表来实现?

[单选题]

下列哪些容器可以使用数组，但不能使用链表来实现? 

  • 队列
  • 栈
  • 优先级队列
  • Map或者Dict
查看答案及解析
添加回答
lishuhuakai头像 lishuhuakai
优先队列一般利用堆来实现,堆用数组来做的话,确实可以快很多,体现在用数组可以很快定位到父子节点,而链表的话,就没有那么方便了,但是这并不意味着链表不能做,可以,只是时间复杂度会比较高而已.

说一下字典吧,字典一般要求最好能在O(1)的时间就定位到要查询的值,如果采用链表的话,是不可能有这个好的时间复杂度的,字典一般用hash表来实现,在不碰撞的情况下,能够达到这么好的复杂度,用红黑树实现的map,查找的复杂度在log(N)左右. 用链表的话,硬要说的话,可以实现字典,但是效率不够,它在查找,插入等各种操作上都没有优势.
编辑于 2017-08-15 23:49:23 回复(0)
小威羊头像 小威羊
Map或者Dict是可以按key索引值，这个只有数组能实现，链表不能
发表于 2017-08-15 09:34:25 回复(0)
大星星和小猩猩头像 大星星和小猩猩
优先队列是带自动排序功能的队列，一般用大根堆（小根堆）来实现，因此可以使用链表来实现。
而Map/Dic是一种映射关系，根据key值找到value值，一般使用hash表来实现，然后有一种解决哈希地址冲突的数据结构叫做HashMap，这里面需要用到链表的知识，但这已经不是原本意义的那个链表了~
发表于 2018-05-07 16:11:35 回复(0)
梦境迷离头像 梦境迷离
Dictionary是字典。。我
编辑于 2017-11-29 15:44:50 回复(0)
露啦啦哩头像 露啦啦哩
**题目
发表于 2018-11-29 10:17:11 回复(0)
提交观点

问题信息

C++工程师 2017 搜狗 链表
来自：搜狗2017校招C++...
上传者：阿奻_
难度：
5条回答 6225浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号