887数据结构与软件工程
PART1：数据结构
一、单项选择题
15道，每道2分，总计30分，没记住，略
二、综合应用题
1、KMP模式匹配：
(1)、求解模式串T的next数组，并与主串S进行模式匹配；画出每一趟的比较过程；
(2)求解匹配成功后，总共的字符间的比较次数。
2、使用Prim算法求解图的最小生成树
3、构造散列表
(1)散列表长A[11]，散列采用Key mod 11，解决冲突采用平方探测法
(2)求解平均查找成功（ASL成功）/平均查找失败长度（ASL失败）
4、 求一个有序数组a[n]中两个值相加为k的数字，打印输出这两个数字的值，且只需找出一对即可；要求时间复杂度O(n)，空间复杂度O(1)
【题源：https://blog.csdn.net/hehongonghh/article/details/82663726】
5、求中序遍历非递归算法求中序遍历序列下第k个结点的关键字值：int InOrder_k(BiNode* T, int k)
PART2：软件工程
一、单项选择题
略
二、综合应用题
1、给出设计模式中——组成模式的UML，问使用这种设计模式有什么特点？（优点缺点的分析）
2、
(1)敏捷开发中使用TDD（测试驱动开发）有什么好处？
(2)TDD是黑盒测试还是白盒测试？
【参考度娘百科：https://baike.baidu.com/item/TDD/9064369?fr=aladdin】
3、某校学生——班级分配系统：绘制最简判定表：
如果总成绩超过700分，并且单科成绩每门超过90分或学科竞赛获奖，可以进入实验班，否则分配入普通班
4、绘制检测站的状态图：系统初始进入正常状态，若变量x大于a，则进入报警状态；当变量小于b又恢复正常状态
5、给出java程序段
(1)绘制程序流程图，要求流程图做到结构化和判断运算原子化（没有符合判定框）
(2)计算McCabe环形复杂度
(3)确定独立路径条数，并为每一条可执行的路径设计测试用例：即输入和预期输出结果
6、绘制机场登机系统的用例图
(1)工作人员开启贵宾/商务通道，并使用广播与大屏幕通知贵宾/商务旅客登机
(2)工作人员开启经济舱通道，并使用广播与大屏幕通知经济舱旅客登机
(3)飞机起飞20分钟前工作人员对还没有登机的旅客催促登机，使用广播与大屏幕通知
(3)飞机起飞15分钟前工作人员关闭登机闸口
(4)工作人员核验旅客的登机牌和有效身份证件，如有问题需要协助解决
要求系统的用例图中包含两个actor，标明用例与actor之间的关系、用例之间的关系 |
|
|
