首页 > 试题广场 >

下列说法错误的是（）

[不定项选择题]

下列说法错误的是（）

已知一颗二叉树的前序遍历顺序和后序遍历顺序，可以唯一确定这棵二叉树

将一个递归算法改为非递归算法时，通常使用队列作为辅助结构

快速排序和堆排序都是不稳定排序

二分查找法，平均时间复杂度为O(n)

查看答案及解析

若只如初见201803011505196

考研好痛苦，情绪不稳定，快(快速排序)些(希尔排序)选(选择排序)一堆(堆排序)朋友来聊天吧，我这样记的，其余的都是稳定排序

发表于 2018-08-29 22:49:40 回复(17)

路人43

前序中序后序这三个两辆组合必须要有中序才能唯一确定一棵二叉树前与后不能唯一确定

递归算法改为非递归算法时，通常使用队列作为辅助结构   是栈  递归调用肯定是需要栈啊   先进后出啊是不是 

一次二分剩下：n/2
两次二分剩下：n/2/2 = n/4
。。。
m次二分剩下：n/(2^m)
在最坏情况下是在排除到只剩下最后一个值之后得到结果，所以为
 n/(2^m)=1;
2^m=n;
所以时间复杂度为：log2(n)

发表于 2017-08-11 18:17:44 回复(0)

striving_qi

A：已知一颗二叉树的前序遍历顺序和后序遍历顺序不能唯一确定这棵二叉树，确定一颗二叉树必须知道这一颗二叉树的中序遍历，知道前序中序或者知道后序和中序才可以确定这颗二叉树；

B：递归算法改为非递归算法不是采用队列做辅助结构，而是栈；

D：二分查找平均时间复杂度是O(logn)，只有在最坏的情况下才是O(n)，所以通常情况下是快于顺序查找，但是不能绝对的说二分查找就一定优于顺序查找，在最坏的情况下是不优于顺序查找的。

所以，答案是ABD

编辑于 2017-08-11 22:23:57 回复(8)

wallflower11

稳定的排序：冒泡、插入、归并、计数、计数、桶排序
不稳定排序：选择、快速、希尔、堆排序

发表于 2017-08-16 14:04:45 回复(0)

左庶长

快选希堆不稳（是不稳定的排序），
基选归堆不变（运行时间不发生变化，与初始状态无关）

发表于 2017-11-20 21:58:54 回复(0)

牛客812466158号

A：前序+中序 or 后序+中序，才能唯一确定一棵树

B：递归算法改为非递归算法，栈；

D：二分查找时间复杂度是O(logn)

发表于 2021-11-18 21:41:46 回复(0)

少年乖

先序和后序所包含的信息是一样的

发表于 2017-08-16 11:37:20 回复(0)

学术废物

B选项可用可不用栈

发表于 2022-03-18 18:52:55 回复(0)

强无畏

一直没明白时间复杂度

发表于 2022-02-01 21:40:07 回复(0)

迷路的修仙少女

递归算法改为非递归算法时，通常使用队列作为辅助结构是栈递归调用肯定是需要栈啊先进后出啊是不是一次二分剩下：n/2 两次二分剩下：n/2/2 = n/4 。。。 m次二分剩下：n/(2^m) 在最坏情况下是在排除到只剩下最后一个值之后得到结果，所以为 n/(2^m)=1; 2^m=n; 所以时间复杂度为：log2(n)

发表于 2020-07-27 18:19:58 回复(0)

阿mini默

不仔细看题的后果，完全反了

发表于 2020-02-29 16:44:01 回复(0)

和风气

必有中序递归改非递归是用栈实现的

发表于 2019-12-16 19:39:34 回复(0)

here6

将一个递归算法改为非递归，不是用栈作为辅助吗？

发表于 2019-12-05 15:41:06 回复(0)

codeor

递归改为非递归分情况: 1:单向递归，尾递归利用迭代实现非递归 2:其他情况利用栈

发表于 2019-07-22 20:52:29 回复(0)

阳光下的米雪

递归表达式是F(n)=F(n-1)+F(n-2)就是要计算F(n),必须先知道F(n-1)，F(n-2)这两个值，这两个值肯定比F(n)先出来，存在队列里，就是先进先出，不明白为啥要用栈

发表于 2019-04-21 17:26:04 回复(0)

小妖～～

快速排序和堆排序都是不稳定排序，所以答案应该全选；确定一颗二叉树，必须知道中序排序和前后排序中的一种

发表于 2019-03-26 09:54:49 回复(0)

嘿~菜鸟

关于稳定排序和不稳定排序可参考这篇文章：https://baijiahao.baidu.com/s?id=1602011058247698952&wfr=spider&for=pc

发表于 2019-02-20 21:51:31 回复(0)

ting9210120

快选希堆不稳（是不稳定的排序），基选归堆不变（运行时间不发生变化，与初始状态无关）

发表于 2018-12-22 09:55:08 回复(0)

嗯好啊

递归的时候用栈，非递归的时候为什么也用栈😒

发表于 2018-09-05 10:38:12 回复(1)

脑回路不正常患者

不是吧，堆排序在最坏情况下时间复杂度都是O(nlog₂n)。构造大顶堆后，还有一个排序过程，在排序后，第二个49依然在第一个49之后（清华大学出版的数据结构书上的例子）。这个是稳定的。

也就是说大顶堆在排序操作后对应的是升序序列，小顶队在排序后对应的是降序序列。

void HeapAdjust(SqList &L, int now_loc, int length){//É¸Ñ¡
	KeyType sentry = L.key[now_loc];
	for (int i = now_loc * 2; i <= length; i *= 2){
		if (i < length && L.key[i] < L.key[i + 1]){
			i++;
		}
		if (L.key[i] <= sentry){
			break;
		}
		L.key[now_loc] = L.key[i];
		now_loc = i;
	}
	L.key[now_loc] = sentry;
}
void HeapSort(SqList &L){
	for (int i = L.length / 2; i >= 1; i--){//构造堆
		HeapAdjust(L, i, L.length);
	}
	for (int i = L.length; i > 1; i--){//进行排序
		KeyType tmp = L.key[1];
		L.key[1] = L.key[i];
		L.key[i] = tmp;

		HeapAdjust(L, 1, i - 1);
	}
}

发表于 2017-09-05 11:01:01 回复(1)

提交观点

问题信息

C++工程师 2017 搜狗树排序

来自：搜狗2017校招C++...

上传者：阿奻_

难度：

20条回答 634收藏 7877浏览

下列说法错误的是（）

问题信息

热门推荐

相关试题