作者befdawn (蜜蜂P助)
看板Grad-ProbAsk
标题[理工] 资结 binary search
时间Thu Oct 25 12:00:39 2018
https://i.imgur.com/uB8iexF.jpg
请问这题的 1 3 4
1。 duplicative keys 是指说像是两个重复的 5 出现之情况吗？不太理解 primary
keys 的意思
3。ISAM 好像是资料库的内容？我有上网找了一下介绍，但没看到比较重点的部分，这
部分不知道有什麽区别
4。资料量少不利，是因为 linear search 的 algorithm 步骤比较少（比较简单）之
故？
谢谢！！
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 1.200.53.105
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1540440041.A.A38.html
1F：推 sdfg014025xx: 4的话 BS还要先排序过 所以资料笔数少时不见得比LS 10/25 17:29
2F：→ sdfg014025xx: 好 10/25 17:29
3F：→ Ricestone: 1.keys指的是资料库中具有区分性的资料，假如是学生名 10/26 04:03
4F：→ Ricestone: 单，那姓名、学号、住址、...都可能是key 10/26 04:04
5F：→ Ricestone: Primary key是实际被选出来当作代表的那一栏(或者数栏) 10/26 04:05
6F：→ Ricestone: 因为需要区分性，所以不希望它里面有重复的值 10/26 04:06
7F：→ Ricestone: 但这题问的事情是，如果有重复的，那BS还可以用吗？ 10/26 04:06
8F：→ Ricestone: 会这样问，是因为有不能用的状况，也就是Hash Table 10/26 04:07
9F：→ Ricestone: key如果需要讲详细一点，像是姓名的话，虽然机率很低 10/26 04:09
10F：→ Ricestone: 但还是有可能有人同名，所以它不是个好PK；不过如果它 10/26 04:10
11F：→ Ricestone: 再加上住址，那应该就会够好。不过这里面最明显的当然 10/26 04:10
12F：→ Ricestone: 是学号。 10/26 04:11
13F：→ Ricestone: 我想了一下，Hash Table理论上应该还是可以用才对 10/26 09:07
14F：→ Ricestone: 不能用的应该是Binary Search Tree 10/26 09:08
15F：推 skyHuan: BST洪1好像有举例过有一样的key的解决方法耶只是并不常 10/26 11:43
16F：→ skyHuan: 见 10/26 11:43
17F：推 skyHuan: 4的话像排序data量小用插入排序也不一定比Qsort慢，而且 10/26 11:46
18F：→ skyHuan: 用的空间还比较少，所以data量少的时候看复杂度不准 10/26 11:46
19F：推 gpsmelody07: 借问一下第2题，False是因为BST的worst case为O(n)的 10/26 14:26
20F：→ gpsmelody07: 缘故吗？ 10/26 14:26
21F：→ skyHuan: 回楼上，对BST有可能skew 10/26 14:41
22F：→ skyHuan: BST != binary search 10/26 14:41
23F：→ gpsmelody07: 谢谢~ 10/26 15:09
24F：→ Ricestone: 我也是觉得应该几乎都有办法修正...不知道该举什麽例了 10/26 17:13