作者irene6524 (Irene)
看板CSSE
标题[请益] 资料结构堆叠伫列搜寻
时间Sat May 21 01:48:57 2011
有3个小问题，麻烦帮我解解，明天就要考试了。
1. 有一笔1、2、3三笔资料，此三笔资料分别经过堆叠，其输出顺序可能有很多种，
例如1、2、3及3、2、1，当有四笔资料1、2、3、4时，共有几种正确的输出顺序?
ans:14
Q:为甚麽原来三笔资料的6种(3!)要扣掉312，为甚麽4种数字时，有一些又不行，
2.将资料1、2、3、4、5、6、7以由小到大之次序输入到双向伫列，则输出次序有可能
是以下哪个?(复选)
A:2135467
B:1347256
C:5174236
D:1325647
ans:ABD
Q:为甚麽ABD可以，C就不行。
3. 有一串数字:1、4、7、8、10、12、13、15、16、18、19、22、23、25、27、30，
利用二元搜寻法搜寻哪一笔资料所需要次数最少?
A:1
B:8
C:16
D:30
ans:16
Q:为甚麽是16，有16笔资料，第一个搜寻到应该是15，第2笔应该是8或22，16应该
是最後一个搜寻到的吧!
谢谢各位了~
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.142.195.12
※ 编辑: irene6524 来自: 220.142.195.12 (05/21 02:44)
1F：推 retinitis:第一题为catalan number 05/21 14:36
3F：→ irene6524:喔!原来有公式，找了好久都看不懂知识家的回答， 05/21 15:11
4F：→ irene6524:那为甚麽3!时312不行，今天考试过关了，但还是很想知道 05/21 15:18
5F：→ irene6524:拜托！拜托！ 05/21 15:20
6F：推 Huangs:3第一个出来，代表stack里有 12，2一定会比1先出来 05/21 21:50
7F：→ Huangs:所以312是不可能的。 05/21 21:50
8F：→ irene6524:还是不太懂呢? 2一定会比1先出来吗? 05/22 01:46