(2/17更新 感谢各位回文及推文的版友们QQ
我把大家说法跟我自己的一些观点整理一下)
这张几乎全部考我弱点...
我各种heap其实不是很熟XD
是非:
1.F(没特别说要怎么着色 应该False吧?)
jerry大说法:此题可能在问此问题是否为NPC
而考虑2-coloring即为False
FRAXIS大说法:若此题为True 则我们变成确定N!=NP
2.F
3.F
4.F(Fixed size让我有点犹豫...)
5.F(更正为T)
其实我觉得False的理由是因为不管是不是amortize分析都是O(1)
所以觉得他的语法有瑕疵
但是以事实来说的话应该是True
6.(更新为F)
应该可跑DFS看finish time解? O(V+E)
7.F
External Node要在同一层
有个好网站推荐给大家
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
可以看大部份会考的资料结构的操作过程
要选T也行
但是equal to 1的情况不会发生
就只能大家自行选择了
这些老师不能出的稍微好一点吗 QQ
8.T
9.T(吗??)
dddm49:complete graph至少砍n-1边
10.(更新为T)
这边还是不确定
但是答案是T基本上是肯定的
大家给的图都是bottom up的2-3 tree
但是top down的操作模式有点不同
https://www.youtube.com/watch?v=2679VQ26Fp4
我只能找到2-3-4的top down但是找不到2-3tree的
我照2-3-4的方法做会遇到尴尬的地方...
还是说对2-3来说两个会一样呢?
复选:
11.
BCDE
12.
CE(更新为ACE)
f1256421:Binomisl heap会存指向min的pointer
如果没有保存就需要用O(logn)
D:他是要合成两棵Binomial Tree变一棵Binomial Tree,那这选项应该没意义吧?
如果两棵树同level那O(1)就可以合并
若不同level则不一定可直接合并
而如果是合成两个Binomial Heap应是花O(logn)
13.
BC(更新为DE)
pups003:

str[i]<<(i*2)
为向左shift
14.
CE(D不确定)
D应该是False吧?
这题我考量的点在于他是问paths而不是path的长度
所以感觉比较像是穷举所有路径的组合数?
我英文烂烂不是很确定...
15.
CE(目前应该ABCE都是False所以删去法可能是D)
A:好像大于O(2^n)?
我跟jerry大一样建出O(n!)之tree
D:因为黑白建期望为logn高度 所以反过来看应该也是50%而不会greter than?
E:我看到这个就以为他是问别种问题XD
16.
DE
B:不太清楚,是八个吗?
E:感觉要用reduce 但是不知道怎么设计
感觉我这张错超多
希望各位高手指正QQ

明天早上才要写qq

那明天指教一下QQ

6 应该是 false O(n) 连 BFS 都不行了..

15 E是错的吧 全黑就没有红了 然后我写A是对的全满的node数是O(2^(n+1)-1)=O(2*(2^n)-1)=O(2^n) 我是这样看的QQ14 D我有写 O(log(max(na,nb)+1) 我就把1删了...12 我有写A Binomial Heap有指标会指向最小的node" target="_blank" rel="nofollow">
10的图7 我写T 因为看到can be =_=

15A没选 一题意他的full node的子点会随着level增加然后我就推出了一个n!的node数QQ 6.false跟F大一样

11B为什么错啊？？12A好像有两种说法，O(log n)是指没有指标只想最小node的版本，所以要checklist n个root,但是洪逸书上写的是有最小node指标的版本，只要O(1)13我是这样想 " target="_blank" rel="nofollow">
<<是shift left

13 e也是对的吧想问第5题 虽然我也是选F 但不太确定概念是否正确

13e我手误忘了写哈哈

11b 是因为要先找到last前一node. 要花O(n)

懂了，感谢d大，另外5我写true，wiki上也是写“work in constant amortized time”

insert 的 amortized complexity 是O(1) 但扣掉之后我就不太清楚分摊成本是多少了有看到Horowitz写复杂度是O(i+c+dk+(dm+d)logi)

6是true喔！如果是DAG就走一次topology即可

false吧 要O(V+E)不是吗

因为题目用can，我想说edge最少是(n-1)，所以就选了

7写T +1 想说小于等于叙述对12题c资结和演算不同 d我有写@@16题 b后来查是正八面体 一堆正三角形那个 顺便问一下16d

7是true吧2-3-4树 外部结点高度相等

可是7 两边高度不能相差1吧

有道理 那又是题意问题惹QQ

想问4为什么false 如果array是sort过的而且是递减 这样也没办法吗

如果sorted且知道最后一个为min那就可以但是一般来说不行我觉得即使用can也有点太牵强 不足以让我选T哈哈

题目讲的是一般的情况 所以不能自己加条件

15 所以台大的TREE高度要从0开始看喔@@

台大题目写起来都是这样的 或你直接用Fh+2-1来看更保险

可是Fh+2-1看也不能确定是0开始还1开始吧QQ

古代台大电机题目是假设root是1

只好看他会不会说了冏

像这题 就h=3 算F5-1 就避掉root是0还是1开始的问题了上一行讲错了这样必须要h=4 才会是7个node啊因为洪逸很常用h=5 12个点的例子 所以我看到7个点直觉就是 h是4才对

我写成F5=8了= =所以算错QQ