n**********2
发帖数: 214 | 1 题目明明说是连续修改，选2却是错的，为什么？
Q.3) To store a collection of values in sorted order, where you expect the
collection to be continuously modified, it would be best to use which of the
following?
A. Array
B. Linked list
C. Binary search tree (Correct Answer)
D. Hashtable |
S**I
发帖数: 15689 | 2 sorted order
the
【在 n**********2 的大作中提到】
: 题目明明说是连续修改，选2却是错的，为什么？
: Q.3) To store a collection of values in sorted order, where you expect the
: collection to be continuously modified, it would be best to use which of the
: following?
: A. Array
: B. Linked list
: C. Binary search tree (Correct Answer)
: D. Hashtable
|
n**********2
发帖数: 214 | 3 我想偏了，看来，呵呵。
【在 S**I 的大作中提到】
: sorted order
:
: the
|
L*****e
发帖数: 8347 | 4 不觉得你想偏了。。。
前半句话“To store a collection of values in sorted order”是说要把数据
sorted地存到某个数据结构中去；后半句“where you expect the collection to be
continuously modified”说以后要对这个数据结构中的数据continously modify。
insert的时候，Binary search tree比linked list快是显然的，但是continous
access的时候，显然linked list要比BST要快。如果是insert是一次性的，而以后
modification是大量的话，应该选择linked list。
不过，题目模糊的地方是，没有说清楚所谓的modify collection是modify什么，
modify的东西是不是要re-sort？
不知道你做的是什么题，从你贴出来的另外两道题看，这套题的质量不高。。。
【在 n**********2 的大作中提到】
: 我想偏了，看来，呵呵。
|
s***o
发帖数: 2191 | 5 I think 'continuously' means 'constantly' or 'frequently' here in the
context
be
【在 L*****e 的大作中提到】
: 不觉得你想偏了。。。
: 前半句话“To store a collection of values in sorted order”是说要把数据
: sorted地存到某个数据结构中去；后半句“where you expect the collection to be
: continuously modified”说以后要对这个数据结构中的数据continously modify。
: insert的时候，Binary search tree比linked list快是显然的，但是continous
: access的时候，显然linked list要比BST要快。如果是insert是一次性的，而以后
: modification是大量的话，应该选择linked list。
: 不过，题目模糊的地方是，没有说清楚所谓的modify collection是modify什么，
: modify的东西是不是要re-sort？
: 不知道你做的是什么题，从你贴出来的另外两道题看，这套题的质量不高。。。
|
L*****e
发帖数: 8347 | 6 哦，你这么一解释有道理了。。。不过这样的话，后半句完全没有增加可以影响design
选择的信息，题目质量还是不高。。。
【在 s***o 的大作中提到】
: I think 'continuously' means 'constantly' or 'frequently' here in the
: context
:
: be
|
g*****g
发帖数: 34805 | 7 In order traversal for BST is as fast as linkedlist.
be
【在 L*****e 的大作中提到】
: 不觉得你想偏了。。。
: 前半句话“To store a collection of values in sorted order”是说要把数据
: sorted地存到某个数据结构中去；后半句“where you expect the collection to be
: continuously modified”说以后要对这个数据结构中的数据continously modify。
: insert的时候，Binary search tree比linked list快是显然的，但是continous
: access的时候，显然linked list要比BST要快。如果是insert是一次性的，而以后
: modification是大量的话，应该选择linked list。
: 不过，题目模糊的地方是，没有说清楚所谓的modify collection是modify什么，
: modify的东西是不是要re-sort？
: 不知道你做的是什么题，从你贴出来的另外两道题看，这套题的质量不高。。。
|
L*****e
发帖数: 8347 | 8 怎么会? 且不说in order traversal for bst要占额外的memory，就单说时间，
traversal bst的worst case也是OlogN。。。(continuous access不一点是从头到尾，
可能只要求你access第123到第125。)
【在 g*****g 的大作中提到】
: In order traversal for BST is as fast as linkedlist.
:
: be
|
p**o
发帖数: 3409 | 9
Below is some BST C code that I wrote in the past.
In the iterative version (O(1) space), finding the successor
of a given node is definitely not an O(1) time operation.
Recursion would trade space for time though.
/* Binary Search Tree struct */
typedef struct node {
int value;
struct node * parent;
struct node * left;
struct node * right;
} node_t;
/* Find the smallest node from a given subtree. */
node_t * min (node_t * n)
{
if (!n) return NULL;
while (n->left) n = n->left;
return n;
}
/* Find the in-order successor ("next") of a given node. */
node_t * next (node_t * n)
{
if (n->right) {
return min(n->right);
}
node_t * p = n->parent;
while (p && p->right==n) {
n = p;
p = p->parent;
}
return p;
}
/* Iterative version of in-order traversal. */
void print_inorder (node_t * n)
{
n = min(n);
while (n) {
printf("%d ", n->value);
n = next(n);
}
}
/* Alternatively, recursive in-order traversal. */
void print_inorder_recursive (node_t * n)
{
if (n) {
print_inorder_recursive (n->left);
printf("%d ", n->value);
print_inorder_recursive (n->right);
}
}
/*
* Here is an example of search/traversal order of the next() function
*
* E.g. 7
* / \
* 3 10
* / \ / \
* 1 5 9 12
* \ / \ / /
* 2 4 6 8 11
*
* 'next' examples when no right child:
* 8->9, 2->1->3, 6->5->3->7, 12->10->7->NULL
*
*/
【在 g*****g 的大作中提到】
: In order traversal for BST is as fast as linkedlist.
:
: be
|
f******y
发帖数: 2971 | 10 是我想太简单了吗？linked list access/modify 是线性的时间复杂度，BST是log（N
）的。选哪个当然很明显。
the
【在 n**********2 的大作中提到】
: 题目明明说是连续修改，选2却是错的，为什么？
: Q.3) To store a collection of values in sorted order, where you expect the
: collection to be continuously modified, it would be best to use which of the
: following?
: A. Array
: B. Linked list
: C. Binary search tree (Correct Answer)
: D. Hashtable
|
|
|
g*****g
发帖数: 34805 | 11 Of course BST is faster. That's why it's "search tree".
N
【在 f******y 的大作中提到】
: 是我想太简单了吗？linked list access/modify 是线性的时间复杂度，BST是log（N
: ）的。选哪个当然很明显。
:
: the
|
n**********2
发帖数: 214 | 12 题目明明说是连续修改，选2却是错的，为什么？
Q.3) To store a collection of values in sorted order, where you expect the
collection to be continuously modified, it would be best to use which of the
following?
A. Array
B. Linked list
C. Binary search tree (Correct Answer)
D. Hashtable |
S**I
发帖数: 15689 | 13 sorted order
the
【在 n**********2 的大作中提到】
: 题目明明说是连续修改，选2却是错的，为什么？
: Q.3) To store a collection of values in sorted order, where you expect the
: collection to be continuously modified, it would be best to use which of the
: following?
: A. Array
: B. Linked list
: C. Binary search tree (Correct Answer)
: D. Hashtable
|
n**********2
发帖数: 214 | 14 我想偏了，看来，呵呵。
【在 S**I 的大作中提到】
: sorted order
:
: the
|
L*****e
发帖数: 8347 | 15 不觉得你想偏了。。。
前半句话“To store a collection of values in sorted order”是说要把数据
sorted地存到某个数据结构中去；后半句“where you expect the collection to be
continuously modified”说以后要对这个数据结构中的数据continously modify。
insert的时候，Binary search tree比linked list快是显然的，但是continous
access的时候，显然linked list要比BST要快。如果是insert是一次性的，而以后
modification是大量的话，应该选择linked list。
不过，题目模糊的地方是，没有说清楚所谓的modify collection是modify什么，
modify的东西是不是要re-sort？
不知道你做的是什么题，从你贴出来的另外两道题看，这套题的质量不高。。。
【在 n**********2 的大作中提到】
: 我想偏了，看来，呵呵。
|
s***o
发帖数: 2191 | 16 I think 'continuously' means 'constantly' or 'frequently' here in the
context
be
【在 L*****e 的大作中提到】
: 不觉得你想偏了。。。
: 前半句话“To store a collection of values in sorted order”是说要把数据
: sorted地存到某个数据结构中去；后半句“where you expect the collection to be
: continuously modified”说以后要对这个数据结构中的数据continously modify。
: insert的时候，Binary search tree比linked list快是显然的，但是continous
: access的时候，显然linked list要比BST要快。如果是insert是一次性的，而以后
: modification是大量的话，应该选择linked list。
: 不过，题目模糊的地方是，没有说清楚所谓的modify collection是modify什么，
: modify的东西是不是要re-sort？
: 不知道你做的是什么题，从你贴出来的另外两道题看，这套题的质量不高。。。
|
L*****e
发帖数: 8347 | 17 哦，你这么一解释有道理了。。。不过这样的话，后半句完全没有增加可以影响design
选择的信息，题目质量还是不高。。。
【在 s***o 的大作中提到】
: I think 'continuously' means 'constantly' or 'frequently' here in the
: context
:
: be
|
g*****g
发帖数: 34805 | 18 In order traversal for BST is as fast as linkedlist.
be
【在 L*****e 的大作中提到】
: 不觉得你想偏了。。。
: 前半句话“To store a collection of values in sorted order”是说要把数据
: sorted地存到某个数据结构中去；后半句“where you expect the collection to be
: continuously modified”说以后要对这个数据结构中的数据continously modify。
: insert的时候，Binary search tree比linked list快是显然的，但是continous
: access的时候，显然linked list要比BST要快。如果是insert是一次性的，而以后
: modification是大量的话，应该选择linked list。
: 不过，题目模糊的地方是，没有说清楚所谓的modify collection是modify什么，
: modify的东西是不是要re-sort？
: 不知道你做的是什么题，从你贴出来的另外两道题看，这套题的质量不高。。。
|
L*****e
发帖数: 8347 | 19 怎么会? 且不说in order traversal for bst要占额外的memory，就单说时间，
traversal bst的worst case也是OlogN。。。(continuous access不一点是从头到尾，
可能只要求你access第123到第125。)
【在 g*****g 的大作中提到】
: In order traversal for BST is as fast as linkedlist.
:
: be
|
p**o
发帖数: 3409 | 20
Below is some BST C code that I wrote in the past.
In the iterative version (O(1) space), finding the successor
of a given node is definitely not an O(1) time operation.
Recursion would trade space for time though.
/* Binary Search Tree struct */
typedef struct node {
int value;
struct node * parent;
struct node * left;
struct node * right;
} node_t;
/* Find the smallest node from a given subtree. */
node_t * min (node_t * n)
{
if (!n) return NULL;
while (n->left) n = n->left;
return n;
}
/* Find the in-order successor ("next") of a given node. */
node_t * next (node_t * n)
{
if (n->right) {
return min(n->right);
}
node_t * p = n->parent;
while (p && p->right==n) {
n = p;
p = p->parent;
}
return p;
}
/* Iterative version of in-order traversal. */
void print_inorder (node_t * n)
{
n = min(n);
while (n) {
printf("%d ", n->value);
n = next(n);
}
}
/* Alternatively, recursive in-order traversal. */
void print_inorder_recursive (node_t * n)
{
if (n) {
print_inorder_recursive (n->left);
printf("%d ", n->value);
print_inorder_recursive (n->right);
}
}
/*
* Here is an example of search/traversal order of the next() function
*
* E.g. 7
* / \
* 3 10
* / \ / \
* 1 5 9 12
* \ / \ / /
* 2 4 6 8 11
*
* 'next' examples when no right child:
* 8->9, 2->1->3, 6->5->3->7, 12->10->7->NULL
*
*/
【在 g*****g 的大作中提到】
: In order traversal for BST is as fast as linkedlist.
:
: be
|
|
|
f******y
发帖数: 2971 | 21 是我想太简单了吗？linked list access/modify 是线性的时间复杂度，BST是log（N
）的。选哪个当然很明显。
the
【在 n**********2 的大作中提到】
: 题目明明说是连续修改，选2却是错的，为什么？
: Q.3) To store a collection of values in sorted order, where you expect the
: collection to be continuously modified, it would be best to use which of the
: following?
: A. Array
: B. Linked list
: C. Binary search tree (Correct Answer)
: D. Hashtable
|
g*****g
发帖数: 34805 | 22 Of course BST is faster. That's why it's "search tree".
N
【在 f******y 的大作中提到】
: 是我想太简单了吗？linked list access/modify 是线性的时间复杂度，BST是log（N
: ）的。选哪个当然很明显。
:
: the
|
N********n
发帖数: 8363 | 23
严格的说这四个答案都不对，正确答案应该是BALANCED SEARCH TREE。
【在 n**********2 的大作中提到】
: 题目明明说是连续修改，选2却是错的，为什么？
: Q.3) To store a collection of values in sorted order, where you expect the
: collection to be continuously modified, it would be best to use which of the
: following?
: A. Array
: B. Linked list
: C. Binary search tree (Correct Answer)
: D. Hashtable
|
j********x
发帖数: 2330 | 24 traversal最慢也就是2n，再多只能是为多而多
【在 L*****e 的大作中提到】
: 怎么会? 且不说in order traversal for bst要占额外的memory，就单说时间，
: traversal bst的worst case也是OlogN。。。(continuous access不一点是从头到尾，
: 可能只要求你access第123到第125。)
|
