※ 引述《forris (乔巴)》之铭言： : 1. 将 1234567 七个数目依某顺序插入一个空的二元搜寻树 (Binary Search Tree) 後， : 所得的二元搜寻数如下图所示： : 4 : ／ ＼ : 2 6 : ／ ＼ ／ ＼ : 1 3 5 7 : 总共有几种可能的插入顺序？ : (a) 40 种 (b) 48 种 (c) 80 种 (d) 96 种 不会，留给高手吧 : 2. 某二元搜寻树内存有 10 到 50 之间的数目。自此二元搜寻树搜寻数目 30 时， : 其搜寻过程中比对过的数目，不可能是下列哪一个顺序？ : (a) 15,43,18,39,20,36,27,30 : (b) 38,10,19,37,21,33,31,30 : (c) 24,48,44,25,40,33,26,34,30 : (d) 42,39,12,13,23,35,28,32,30 : 为什麽是选 c ? 因为是二元搜寻树，所以树中的各节点，必定排序过了 a / \ a左半边子树的值必定全小於a, 右半边子树的值必定全大於a b c 可以用最简单的方式判断 以选项(c)为例 24为根节点，30为搜寻值，向右子树拜访，因此，接下来所有的值都必须大於24 (此部份都还吻合) 下一个拜访的节点为48，30<48，故往48的左子树拜访 接下来经过的所有节点都必须小於48 下一个节点为44，30<44，再往44的左子树拜访 接下来经过的所有节点都须小於44 . . . (以上类推) 问题会出现在 33这个节点，30<33，所以要往33的左子树拜访 理论上，後续要拜访的三个节点(26.34.30)都必须要小於33 但题目中出现了34这个不符合的节点，所以c是错的 : 3. 在二元树上，依照节点所在的层次，由最上层至最下层一层层走动 (traverse) 时， : 需要用到哪一种资料结构？ : (a) stack (b) queue (c) hash table (d) heap : 为何要选 b 而不是 d ? 依照题意由上层至下层一层层走动，为广度优先搜寻，使用queue应无误 若为深度优先搜寻需要使用stack 不知为何会想选择heap (如解题有误，烦请赐教) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 218.163.226.50