大。
令Cij是从a11到aij的路径上的数的最大和，并且Ci0C0j0，则Cij。
AmaxCi1j1Ci1jaij
BCi1j1ci1j
CmaxCi1j1Ci1j1
DmaxCij1Ci1jaij

14小明要去南美洲旅游，一共乘坐三趟航班才能到达目的地，其中第1个航班准点的概率是09，第2个航班准点的概率为08，第3个航班准点的概率为09。如果存在第i个（i12）航班晚点，第i1个航班准点，则小明将赶不上第i1个航班，旅行失败；除了这种情况，其他情况下旅行都能成功。请问小明此次旅行成功的概率是。
A05
B0648
C072
D074

15欢乐喷球：儿童游乐场有个游戏叫“欢乐喷球”，正方形场地中心能不断喷出彩色乒乓球，以场地中心为圆心还有一个圆轨道，轨道上有一列小火车在匀速运动，火车有六节车厢。假设乒乓球等概率落到正方形场地的每个地点，包括火车车厢。小朋友玩这个游戏时，只能坐在同一个火车车厢里，可以在自己的车厢里捡落在该车厢内的所有乒乓球，每个人每次游戏有三分钟时间，则一个小朋友独自玩一次游戏期望可以得到个乒乓球。假设乒乓球喷出的速度为2个秒，每节车厢的面积是整个场地面积的120。
A60
B108
C18
D20

二、不定项选择题（共5题，每题15分，共计75分；每题有一个或多个正确选项，多选或少选均不得分）

1以下排序算法在最坏情况下时间复杂度最优的有。
A冒泡排序
B快速排序
C归并排序
D堆排序

2对于入栈顺序为abcdefg的序列，下列不可能是合法的出栈序列。
Aabcdefg
Badcbegf
Cadbcgfe
Dgfedcba
f
3下列算法中，是稳定的排序算法。
A快速排序
B堆排序
C希尔排序
D插入排序

4以下是面向对象的高级语言的是。
A汇编语言
BC
CForta
DJava
5以下和计算机领域密切相关的奖项是。
A奥斯卡奖B图灵奖C诺贝尔奖D王选奖
三、问题求解（共2题，每题5分，共计10分）1如图所示，共有13个格子。对任何一个格子进行一次操作，会使得它自己以及与它上下左右相邻的格子中的数字改变由1变0，或由0变1。现在要使得所有的格子中的数
字都变为0，至少需要3次操作。
2如图所示，A到B是连通的。假设删除一条细的边的代价是1，删除一条粗的边的代价是2，要让A、B不连通，最小代价是42分，最小代价的不同方案数是93分。（只要有一条删除的边不同，就是不同的方案）
四、阅读程序写结果（共4题，每题8分，共计32分）1i
cludeusi
g
amespacestdi
tr