作者polomoss (小泽)
看板Grad-ProbAsk
标题Re: [理工] [DS]-几题小问题
时间Thu Jan 7 23:32:37 2010
※ 引述《assassin88 (AI)》之铭言：
: 一、In binary tree, the number of null pointers is more than one unit than
: the number of nun-null pointers.
: 这题不是应该是True吗？ no=n2+1？
你没有考虑n1的点数，non-null包括n1，所以不会差1
: 二、What's max number of comparison when we search of an item in AVL tree with
: 1000 nodes.
用费氏数列去算，F h+2 -1 <=1000 ,h=14
: 请问一下这题该怎麽算阿？我本来是想log(1000+1)=10..但是没这个答案= =
: 三、如果要把(A+B^C^D*E)/F/(G*H)转成後序最少需要几个stack？
: 我怎麽画都是三个耶..可以指导一下吗XD
我怎麽画都是4个耶
最多的时候stack : ( + ^ ^
: 四、26,5,3,1,4,7,30,33,35,12 画成 min leftist heap？
: 问题有点多..麻烦了~感谢！
这题答案给的是错的，但我也不确定我画得是否正确
请别的高手回答
--
学长学长!那边有飙车族 学长学长!那边刚好像有女生 学长学长~那边有人红灯右转
砍人 被压上车 ψQSWEET
鸽 ◥ 鸽 ◥ 鸽 ◥ 鸽 ◥ 鸽 ◥他妈的◤ 鸽
◤◎ ◎ 喔~~ ◤︶ ︶ ◤◎ ◎ 喔~~ ◤︶ ︶ ◤◎ ◎ 拦下来呀!⊙ ⊙◥
◥ ◤ ◥ █◤ ◥ ◤ ◥ 3◤╯ξ
◥ ◤没王法了◥皿 ◤
◥ ◥◥ (哈欠)◤ ◥◤ ◥ ◥◥ (烟~) ◤ ◥ ◤￣ ◥ ◥◥是不是?!(
◥ ◤ ◤)
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 122.116.14.2
1F：→ james1815:第四题应该是 把每个点 视为独立点 一一进行COMBINE 01/08 00:54
2F：→ james1815:麻烦原PO自己TRY 看看吧 01/08 00:55
3F：推 cansister:第一题 应该会差2而不是1，你可以将node用○表示 而null 01/08 01:30
4F：→ cansister:的地方补上□，这样一来，这棵树就变成只有n2和n0的tree 01/08 01:31
5F：→ cansister:□数=○数+1，除了root以外的○node都有一个pointer指向 01/08 01:32
6F：→ cansister:它，□数=(Root以外的○)数+2。注null point会连上□喔 01/08 01:35