13. 在正实数构成的数字三角形排列形式如图所示,第一行的数为 a11;第二行的数从左到
右依次为 a21,a22;…第 n 行的数为 an1,an2,…,ann。从 a11 开始,每一行的数 aij 只有两
条边可以分别通向下一行的两个数 a(i+1)j 和 a(i+1)(j+1)。用动态规划算法找出一条从 a11
向下通到 an1,an2,…,ann 中某个数的路径,使得该路径上的数之和达到最大。
令 C[i,j]是从 a11 到 aij 的路径上的数的最大和,并且 C[i,0]=C[0,j]=0,则 C[i,j]=( )。
A. max{C[i-1,j-1],C[i-1,j]}+aij
B. C[i-1,j-1]+c[i-1,j]
C. max{C[i-1,j-1],C[i-1,j]}+1
D. max{C[i,j-1],C[i-1,j]}+aij
14. 小明要去南美洲旅游,一共乘坐三趟航班才能到达目的地,其中第 1 个航班准点的概率
是 0.9,第 2 个航班准点的概率为 0.8,第 3 个航班准点的概率为 0.9。如果存在第 i 个
(i=1,2)航班晚点,第 i+1 个航班准点,则小明将赶不上第 i+1 个航班,旅行失败;除了
这种情况,其他情况下旅行都能成功。请问小明此次旅行成功的概率是( )。
A. 0.5 B. 0.648 C. 0.72 D.0.74
15. 欢乐喷球:儿童游乐场有个游戏叫“欢乐喷球”,正方形场地中心能不断喷出彩色乒乓
球,以场地中心为圆心还有一个圆轨道,轨道上有一列小火车在匀速运动,火车有六节车厢。
假设乒乓球等概率落到正方形场地的每个地点,包括火车车厢。小朋友玩这个游戏时,只能
坐在同一个火车车厢里,可以在自己的车厢里捡落在该车厢内的所有乒乓球,每个人每次游
戏有三分钟时间,则一个小朋友独自玩一次游戏期望可以得到( )个乒乓球。假设乒乓球喷
出的速度为 2 个/秒,每节车厢的面积是整个场地面积的 1/20。
A. 60 B. 108 C. 18 D. 20
二、不定项选择题(共 5 题,每题 1.5 分,共计 7.5 分;每题有一个或多个正确选项,多选
或少选均不得分)
1. 以下排序算法在最坏情况下时间复杂度最优的有( )。
A. 冒泡排序 B. 快速排序
C. 归并排序 D. 堆排序
2. 对于入栈顺序为 a, b, c, d, e, f, g 的序列,下列()不可能是合法的出栈序列。
A. a,b,c,d,e,f,g B. a,d,c,b,e,g,f
C. a,d,b,c,g,f,e D.g,f,e,d,c,b,a