本试卷共6道题。试题一至试题四是必答题，试题五和试题六选答一题。每题15分，满分75分。

试题一

【说明】某停车场运营方为了降低运营成本，减员增效，提供良好的停车体验，欲开发无人值守停车系统，该系统的主要功能是：

    1、信息维护。管理人员对车位(总数、空余车位数等)计费规则等基础信息进行设置。

    2、会员注册。车主提供手机号、车牌号等信息进行注册，提交充值信息(等级、绑定并授权支付系统进行充值或交费的支付账号)不同级别和充值额度享受不同停车折扣点。

    3、车牌识别。当车辆进入停车场时，若有(空余车位数大干1)，自动识别车牌号后进行道闸控制，当车主开车离开停车场时，识别车牌号，计费成功后，请求道闸控制。

    4、计费。更新车辆离场时间，根据计费规则计算出停车费用，若车主是会员，提示停车费用：若储存余额够本次停车费用，自动扣费，更新余额，若储值余额不足，自动使用授权缴费账号请求支付系统进行支付，获取支付状态。若非会员临时停车，提示停车费用，车主通过扫描费用信息中的支付码调用支付系统自助交费，获取支付状态。

    5、道闸控制。根据道闸控制请求向道闸控制系统发送放行指令和接收道闸执行状态。若道闸执行状态为正常放行时，对入场车辆，将车牌号及其入场时间信息存入停车记录，修改空余车位数；对出厂车辆更新停车状态，修改空余车位 ……此处隐藏13988个字…… 用到的辅助空间记录中间解有2个数组m[i][j]和S[i][j]，都是二维数组，空间复杂度的量级为O(n2)。

    最后分析代码填空部分。

    第(1)空，r表示的是子问题规模，规模划分已知从r=2开始，子问题最大应该能够取到N，因此本空填写r＜=N或其等价表示形式。

    第(2)空缺失的是j的初始化赋值，本空较难。代码计算前边界为i，链长为r的链的后边界取值，结果为i+r-1，即本题填写j=i+r-1或其等价表示形式。

    第(3)空缺失判断条件，此时注释明确说明此处判断最小值，判断后，m[i][j]值进行修改并修改为temp，也就是意味着m[i][j]此时记录的不是最优解(最小值)，需要进行修正改为最小，即填写temp＜m[i][j]或其等价表示形式(某一个数值比最小值还小，则修改最小值)。

    第(4)空缺失的是打印参数，结合代码上下文进行分析，上文打印print_triangle(i,S[i][j]);即截断的前一部分编号，下面print_triangle((4));打印的应该是截断的后一部分，即填写s[i][j]+1,j。12、动态规划法

    O(n3)

    O(n2)