[资工] 数题资结(tree/hash/电机丙97/交大102)
楼主: qoojordon (颖川琦) 2014-12-18 14:42:14
有4个问题和四个观念确认 , 麻烦有空的版友回答了
(或是提供关键字也可以)
4题截取图片 =>
![]()
[NTUEE 103 1]
Horowitz有翻到BST的三个动作,不过不确定自己解读正不正确....
threeWayJoin:给两棵树的root(small,big)和一个mid值 , 把它们合成BST
twoWayJoin:给两棵树的root(small,big),合出一颗BST
split:给你树,k值, 依k把树拆成small,mid,big
不过都没图例 =口=....我依自己估狗到的蔡老师投影片,做出下面的树
s→3 b
／|＼ ↙
2 | 12
／ | ／|＼
1 4 | 13
|＼| ＼
| 11 16
|／| ／
7 | 15
／＼ /／
6 / 9/14
／ ／＼\
5 8 ↑10
mid
[NTUEE 102 3]
用queue , 又有stack pointer ... operation又是stack动作 , infix转prefix..
不知道怎么下手
(目前只知道利用stack做到: 1,中序转前序或后序 2,计算前序或后序算式值
其实想法上是一样的,只是由左至右还是由右至左的差别 , 不过这题也限制方向与次数
有请高手帮忙)
[NTUEE 97 19]
是从load factor下手吗 ? 不清楚从哪个方向讨论
[NTHU 103 5&6]
配分很重 , 有几个答题上的问题
Q1 : storage mechanism 和 index structure是分开的吗 ?
Q2 : 有实作王可以提供作答上的想法吗?
[NTUEE 98 6(d)]
T or F :
Given the pointer to the node to be deleted , the node deleting operation
of a doubly-linked-list has lower complexity than that of a singly-linked-list.
如果给指定data值于 link-list删除 , 两者都要花O(n)
如果给定node指标于 link-list做删除 , singly O(n) , doubly O(1)
固此叙述应该是T ?
[NTUEE 98 11(c)]
T or F :
Rehashing is a way to overcome primary clustering, which is when record begin
to accumulate in long string of adjacent positions instead of being uniformly
distributed throughout the table
Rehashing 和 double hash讲的是同一件事情吗 ?
还是rehashing只是广义的collision Resolution的通称?
i,e, linear probing , quadratic probing ....包含于 rehash?
[NTUEE 98 20(e)]
请问当在hash table中删除key值通常是怎么做 ?
e.g. 考虑hash table有5个bucket , 每个bucket皆只有一个slot , 发生collision采
linear probing , 依序插入 5,10,15,20 , 再删除15应该会得到哪种hash table?
index content index content
0 5 0 5
1 10 1 10
2 x 2 20
3 20 3 x
4 x 4 x
主要想问的是删除之后 , rehash path之后的key值会递补上来吗 ?
(如果是的话,越复杂的rehash机制会费很多功夫在修正上...)
[NTUEE 98 17]
讨论Disjoint Sets的 Union & Find , Weighting Rule和Collapsing Rule是改善两者
performance的方式 , 能让 Find效率提升为 O(log n)
Q1:
讨论类似的问题时 , 是否都是以一个set就是一个点做讨论 ?
否则点数总共为n的Union & Find , 我取
T1: n1 T2: nth (第n个点独立一个set)
↑
n2
.
.
.
第n-1个点
Union(T1,T2) 树高是 n-1
即使采用上面的rule , 树高也会是O(n)?
Q2: 做u次 Union ,f次 Find , 过程中皆遵守两个Rule , 则复杂度是Θ(u+f)
原文书是写 α(f) , 我自己的解读是:
仅有几个深度够的点会花到O(logn) , 但会顺便完成path compression , 可以让
后续path上的find只要O(1)完成 , 分摊下来后几乎只要常数就能完成find ?
这次积的有点多 , 先谢谢有看过der你
(或是提供关键字也可以)
4题截取图片 =>
[NTUEE 103 1]
Horowitz有翻到BST的三个动作,不过不确定自己解读正不正确....
threeWayJoin:给两棵树的root(small,big)和一个mid值 , 把它们合成BST
twoWayJoin:给两棵树的root(small,big),合出一颗BST
split:给你树,k值, 依k把树拆成small,mid,big
不过都没图例 =口=....我依自己估狗到的蔡老师投影片,做出下面的树
s→3 b
／|＼ ↙
2 | 12
／ | ／|＼
1 4 | 13
|＼| ＼
| 11 16
|／| ／
7 | 15
／＼ /／
6 / 9/14
／ ／＼\
5 8 ↑10
mid
[NTUEE 102 3]
用queue , 又有stack pointer ... operation又是stack动作 , infix转prefix..
不知道怎么下手
(目前只知道利用stack做到: 1,中序转前序或后序 2,计算前序或后序算式值
其实想法上是一样的,只是由左至右还是由右至左的差别 , 不过这题也限制方向与次数
有请高手帮忙)
[NTUEE 97 19]
是从load factor下手吗 ? 不清楚从哪个方向讨论
[NTHU 103 5&6]
配分很重 , 有几个答题上的问题
Q1 : storage mechanism 和 index structure是分开的吗 ?
Q2 : 有实作王可以提供作答上的想法吗?
[NTUEE 98 6(d)]
T or F :
Given the pointer to the node to be deleted , the node deleting operation
of a doubly-linked-list has lower complexity than that of a singly-linked-list.
如果给指定data值于 link-list删除 , 两者都要花O(n)
如果给定node指标于 link-list做删除 , singly O(n) , doubly O(1)
固此叙述应该是T ?
[NTUEE 98 11(c)]
T or F :
Rehashing is a way to overcome primary clustering, which is when record begin
to accumulate in long string of adjacent positions instead of being uniformly
distributed throughout the table
Rehashing 和 double hash讲的是同一件事情吗 ?
还是rehashing只是广义的collision Resolution的通称?
i,e, linear probing , quadratic probing ....包含于 rehash?
[NTUEE 98 20(e)]
请问当在hash table中删除key值通常是怎么做 ?
e.g. 考虑hash table有5个bucket , 每个bucket皆只有一个slot , 发生collision采
linear probing , 依序插入 5,10,15,20 , 再删除15应该会得到哪种hash table?
index content index content
0 5 0 5
1 10 1 10
2 x 2 20
3 20 3 x
4 x 4 x
主要想问的是删除之后 , rehash path之后的key值会递补上来吗 ?
(如果是的话,越复杂的rehash机制会费很多功夫在修正上...)
[NTUEE 98 17]
讨论Disjoint Sets的 Union & Find , Weighting Rule和Collapsing Rule是改善两者
performance的方式 , 能让 Find效率提升为 O(log n)
Q1:
讨论类似的问题时 , 是否都是以一个set就是一个点做讨论 ?
否则点数总共为n的Union & Find , 我取
T1: n1 T2: nth (第n个点独立一个set)
↑
n2
.
.
.
第n-1个点
Union(T1,T2) 树高是 n-1
即使采用上面的rule , 树高也会是O(n)?
Q2: 做u次 Union ,f次 Find , 过程中皆遵守两个Rule , 则复杂度是Θ(u+f)
原文书是写 α(f) , 我自己的解读是:
仅有几个深度够的点会花到O(logn) , 但会顺便完成path compression , 可以让
后续path上的find只要O(1)完成 , 分摊下来后几乎只要常数就能完成find ?
这次积的有点多 , 先谢谢有看过der你