首页 > 试题广场 >

以下说法中正确的有（）

[不定项选择题]

以下说法中正确的有（）

二叉树中有两个孩子的节点数一定等于叶子节点减一

若一个叶节点是某二叉树中的中序遍历的最后一个节点，同时它也是该二叉树前序遍历的最后一个节点

C++中 std:map 查找一个数据的复杂度是 O(1)

n个关键字中已知有k个关键字哈希值相同，若用线性探测法将它们存入散列表，至少需要进行k(k-1)/2次探测

查看正确选项

牛客网弟中弟

map中查找一个数据的复杂度为o(logn)

发表于 2019-03-14 12:39:40 回复(2)

已注销

关于B选项，要看清楚叶节点的设定！

发表于 2019-04-11 15:38:59 回复(0)

牛客4938kunn

map, set, multimap, and multiset
上述四种容器采用红黑树实现，红黑树是平衡二叉树的一种。不同操作的时间复杂度近似为:
插入: O(logN)
查看:O(logN)
删除:O(logN)

hash_map, hash_set, hash_multimap, and hash_multiset
上述四种容器采用哈希表实现，不同操作的时间复杂度为：
插入:O(1)，最坏情况O(N)。
查看:O(1)，最坏情况O(N)。
删除:O(1)，最坏情况O(N)。

发表于 2021-06-21 14:22:53 回复(0)

我的天鸭

D选项的线性探测法难道不是K(K+1)/2次探测？第1个探测1次，第K个探测K次

发表于 2019-08-27 16:38:41 回复(6)

泉州码农

D选项

对于线性探测法解决哈希冲突的散列表，当有k个关键字的哈希值相同时，需要进行一系列的探测来找到可用的槽位。

在线性探测法中，当发生哈希冲突时，会依次检查下一个槽位，直到找到一个空槽位来存储关键字。因此，在这种情况下，第一个关键字不需要进行探测，但后续的k-1个关键字需要进行探测。

探测的次数可以看作是一个等差数列，其中首项为1，公差为1，末项为k-1。根据等差数列求和公式，可以得到探测的总次数为：

S = (k-1) * (1 + (k-1)) / 2 = k(k-1) / 2

因此，至少需要进行 k(k-1)/2 次探测来将这k个关键字存入散列表中，以确保它们不发生冲突并找到可用的槽位。

发表于 2023-09-26 14:22:53 回复(0)

荒天灬

D选项中线性探测法探测次数为0,1,2,3,4，……，m-1次，所以D选项正确

发表于 2021-12-28 23:31:35 回复(0)

优秀的社畜孤寡孤寡

A：为什么对，空二叉树不就不满足这个关系吗？

发表于 2022-09-23 10:52:27 回复(1)

salanderyzw

对于B选项，若叶子节点是中序遍历（左根右）的最后一个元素，则叶节点一定为其父节点的右孩子（左孩子就不会是中序遍历最后一个元素），故也是前序遍历（根左右）的最后一个元素。

发表于 2022-09-14 14:22:25 回复(0)

咸咸咸咸_鱼

D说的是至少多少次，不是平均多少次，为啥还选D呢？

发表于 2022-04-14 18:05:56 回复(0)

牛客445608548号

A怎么错了

发表于 2020-09-26 16:20:51 回复(0)

whalefall97

B选项可以画一个二叉树验证一下就行了

发表于 2020-09-07 13:24:34 回复(0)

淇神

map不用散列设置吗

发表于 2020-05-07 11:55:00 回复(1)

DosonMu

<p>D选项现象探测是什么玩意，打错了吧</p>

发表于 2020-04-26 08:23:18 回复(1)

提交观点

问题信息

小米集团树 2019

来自：小米2019秋招算法笔...

上传者：小小

难度：

13条回答 310收藏 2839浏览

以下说法中正确的有（）

问题信息

热门推荐

相关试题