【网络】期末试卷 (转载) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

【网络】期末试卷 (转载)

【网络】期末试卷 (转载)# Joke - 肚皮舞运动

G*A2013-01-18 08:01

1 楼

给一个string，无空格，无特殊字符，全小写字母。给字典。问总共有多少种可能的断
词方式，so that 每个词都能在字典里查到。
我只想到了dfs.

C*o2013-01-18 08:01

2 楼

【以下文字转载自 Military 讨论区】
发信人: GoBlue (Wolverines), 信区: Military
标题: 【网络】期末试卷 (转载)
发信站: BBS 未名空间站 (Thu Jan 17 23:47:28 2013, 美东)
发信人: GoBlue (Wolverines), 信区: WaterWorld
标题: 【网络】期末试卷
发信站: BBS 未名空间站 (Thu Jan 17 23:46:57 2013, 美东)
期末试卷（满分100分，答卷时间100分
钟）
一、选择题。（每小题2分，共20分。）
1、王石婚变后，谁火了？（）
A、潘石屹 B、田朴珺 C、长江商学院 D、张欣
2、方舟子被谁赶出了新浪微博？（）
A、韩寒 B、不加V C、孙海峰 D、罗永浩
3、以下人物中，哪一位是表哥？（）
A、芮成钢 B、杨达才 C、李德金 D、蔡彬
4、雷政富床上功夫的记录是？（）
A、18秒 B、18分 C、12秒 D、12分
5、四川什邡的那个胖子叫什么名字？（）
A、金正恩 B、刘波 C、张兵 D、蒋皓月
6、2012年伦敦奥运会男子110米栏的赛场上，谁在等待见证奇迹的时刻？（）
A、刘翔 B、央视 C、领导 D、观众
7、在吴法天与周燕约架的讨论中，以下谁的账号没有被注销过？（）
A、吴祚来 B、叶匡政 C、点子正 D、变态辣椒
8、以下哪一位没有被禁言过？
A、徐昕 B、袁裕来律师 C、司马南 D、慕容雪村
9、以下物品中，价值最高的是？（）
A、黄金 B、白银 C、钻石 D、切糕
10、向别人询问意见时，你会问谁？（）
A、苍老师 B、元芳 C、杜甫 D、李白
二、填空题。（每小题1分，共15分。）
1、中华民族的复兴已完成______%。
2、在新浪微博上一本正经的让人随时受不了的博主叫@____________。
3、最流行的style是_______style和_______style。
4、最好听的声音是_____________。
5、央视最粗暴的提问是___________。
6、北京特大暴雨后，红十字会收到最多的是__________。
7、被劳教的村官是_____________。被劳教的母亲是___________。
8、在十八大直播报道中尴尬忘词，编不下去了的央视女记者叫____________。
9、就异地高考问题单挑上海人的女生是@__________。
10、盘锦征地事件中下意识开枪的民警叫___________。
11、幼师虐童案发生在_________。
12、今年，中国为__________降了半旗。
13、天津蓟县莱德商厦大火网传发生在__________（美国的一个城市）。
14、被小秘书秒杀的国外领事馆微博是_____________。
15、_______反PX项目的散步中，广场上的民众被禁止唱国歌。
三、判断题。（每小题1分，共5分。）
1、中国是法制社会。
2、三聚氰胺是无毒的。
3、因为爱国就可以打砸抢烧。
4、桥道倾覆是由于车辆超载造成。
5、房屋倒塌是因为天气干湿交替所致。
四、名词解释。（每小题2分，共10分。）
1、屌丝。
2、表哥。
3、正能量。
4、适度腐败。
5、理论准备不足。
五、问答题。（共10分，该题无标准答案。）
1、周克华死了吗？
2、你幸福吗？
3、中央电视台是哪个国家的媒体？
4、哪里是法外之地？
六、阅读理解。（共10分。）
请阅读下面一段文字，回答有关问题。
两个美国人，在中国的地盘，养着900名中国孤儿，还为3000个做了手术，竟然潜
伏了20年。距北京只有70多公里的地方，把本该政府干的活全抢了。让政府无事可做，
只好强拆、拦访、抓小贩……
1、这两个美国人要不要脸？
2、你认为外国人干这种事，其用心就是想丢中国人的脸的吗？请说明理由。
3、到底谁不要脸？
七、作文（共30分。）
请以《莫言》为题，写一篇作文，要求不少于800字，文体不限，诗歌除外。

w*p2013-01-18 08:01

3 楼

这个和DFS 没关系啊。典型的DP题啊。 CC 150 上有答案。

【在 G****A 的大作中提到】

: 给一个string，无空格，无特殊字符，全小写字母。给字典。问总共有多少种可能的断
: 词方式，so that 每个词都能在字典里查到。
: 我只想到了dfs.

x*w2013-01-18 08:01

4 楼

二爷的标准说法是 dfs+cache

【在 w********p 的大作中提到】

: 这个和DFS 没关系啊。典型的DP题啊。 CC 150 上有答案。

b*n2013-01-18 08:01

5 楼

DFS和DP本质上一样吧，DP存了已经查找过的结果，DFS每次要重新找

h*e2013-01-18 08:01

6 楼

cache 应该用 trie 。

k*e2013-01-18 08:01

7 楼

貌似是DP

【在 G****A 的大作中提到】

: 给一个string，无空格，无特殊字符，全小写字母。给字典。问总共有多少种可能的断
: 词方式，so that 每个词都能在字典里查到。
: 我只想到了dfs.

G*A2013-01-18 08:01

8 楼

手头刚好没有cc150，你说的解法类似这个么？还有没有其他解法？
void sentence(string input, int left, int right, string output, mapbool> dict)
{
if (left > right)
cout<else{
for (int i=left; i<=right; i++){
std::string sub = input.substr(left, i-left+1);
if (dict.find(sub) != dict.end())
sentence(input, i+1, right, output + sub + " ", dict);
}
}
}

【在 w********p 的大作中提到】

: 这个和DFS 没关系啊。典型的DP题啊。 CC 150 上有答案。

n*w2013-01-18 08:01

9 楼

这个是递归解。至少指数级复杂度。
DP是n^2

【在 G****A 的大作中提到】

: 手头刚好没有cc150，你说的解法类似这个么？还有没有其他解法？
: void sentence(string input, int left, int right, string output, map: bool> dict)
: {
: if (left > right)
: cout<: else{
: for (int i=left; i<=right; i++){
: std::string sub = input.substr(left, i-left+1);
: if (dict.find(sub) != dict.end())

w*p2013-01-18 08:01

10 楼

你倒是提醒我了。
首先dict 是给你的没错，但是它是个什么样的字典呢？你要考虑
最佳答案是 Trie. 和DP 结合起来用。
Trie 在分析词汇的时候有三种可能
1）没有
2）是的
3）部分存在。
所以简化你的方法，要快一点。

【在 G****A 的大作中提到】

j*22013-01-18 08:01

11 楼

150里就是trie+dp

【在 w********p 的大作中提到】

: 你倒是提醒我了。
: 首先dict 是给你的没错，但是它是个什么样的字典呢？你要考虑
: 最佳答案是 Trie. 和DP 结合起来用。
: Trie 在分析词汇的时候有三种可能
: 1）没有
: 2）是的
: 3）部分存在。
: 所以简化你的方法，要快一点。