文章

363

粉丝

0

获赞

4

访问

68.0k

头像
2026年(408)计算机学科专业基础综合试题 - 第42题回答
数据结构
发布于2026年5月12日 04:35
阅读数 116

第一个序列不能得到,第二个序列可以得到。 Pj​<Pk​<Pi​ .  5 

已知当 n=k−1 时,栈可得到的出栈序列总数为

Ck−1​=M

其中 Cn​ 为第 n 个卡特兰数。以 1 开头的出栈序列个数: M​  以 2 开头的出栈序列个数: C(k−1)​−C(k−2)​​ 出栈序列总数: (k+1)分之2(2k−1)​M​


评分及理由

(1)得分及理由(满分2分)
学生回答“第一个序列不能得到,第二个序列可以得到”,与标准答案中“不能,6先出栈后5、4的顺序必须逆序;能得到”一致,正确。但学生未给出理由说明,不过题目问题未要求写出理由,且判断正确,所以不扣分。得分:2分。

(2)得分及理由(满分2分)
标准答案为\( P_i > P_k > P_j \),学生回答“Pj < Pk < Pi”,等价于\( P_j < P_k < P_i \),与标准答案完全一致。逻辑正确,得分:2分。

(3)得分及理由(满分2分)
标准答案为5个,具体为2143、2134、2341、2314、2431。学生回答“5”,正确。得分:2分。

(4)得分及理由(满分4分)
标准答案:以1开头的出栈序列有M个,以2开头的出栈序列有M个,全部出栈序列有\(\frac{C_{2k}^k}{k+1}\)个。学生回答:以1开头个数为M(正确);以2开头个数为“C(k-1) - C(k-2)”,而标准答案是M个,由于M = 第k-1个卡特兰数 = \( \frac{C_{2(k-1)}^{k-1}}{k} \),学生表达式与此不等价,逻辑错误;出栈序列总数写为“ (k+1)分之2(2k-1)M ”,与标准答案的卡特兰数表达式不符,且未明确推导正确,逻辑错误。因此(4)小题全错,得分:0分。

题目总分:2+2+2+0=6分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发