※ 引述《qoojordon (颖川琦)》之铭言：
: 有4个问题和四个观念确认 , 麻烦有空的版友回答了
: (或是提供关键字也可以)
: 4题截取图片 =>http://ppt.cc/5VHL
: [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,计算前序或后序算式值
: 其实想法上是一样的,只是由左至右还是由右至左的差别 , 不过这题也限制方向与次数
: 有请高手帮忙)
Java code:http://ideone.com/M6EF6f
应该是对的(吧)
: [NTUEE 97 19]
: 是从load factor下手吗 ? 不清楚从哪个方向讨论
(A)True
(B)?
(C)?
(D)应该是O(n)?
(E)该应不会是(1)吧..但也不知道是几
: [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 ?
疴 false?
给定指标了
singly的操作:
now->data = now->next->data
node* temp = now->next->next
delete(now->next)
now->next = temp
doublly则要两次(一个往前一个往后)
: [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?
觉得是false
Rehashing就是处理collision的方法
包含linear probing , quadratic probing , double hashing 等
double hashing可以避免 , 其他两个则否
: [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你
cormen本有分析 但是太复杂了看不懂XD
只知道阿法很小 比lg(f)还小