SDU CS 期末考回忆版合集

删除原有分散的版本，合订起来画个。
包括：机器学习、算法、图形学、操作系统、编译原理、软件工程、大数据分析管理、计算机体系结构等

2021 SDU机器学习期末考试

2019 计科

一、线性回归+牛顿法

给出了线性回归的Loss Function

1. 证明Hessian =
2. 证明牛顿法一次迭代结果 和 正规方程求解结果一样
3. 证明正则化的线性回归，用牛顿法一次迭代和正规方程求解结果一样

二、计算题

给了一个表 类似于下表

问 当A=0 B=0 C=1时输出y是多少

三、Soft Margin SVM

1. 给了soft Margin SVM的问题模型，但是没有 的约束，说明加不加约束都不影响目标函数的最优值，目标函数就是的目标函数
2. 求KKT条件
3. 求拉格朗日对偶问题

四、EM算法

给出了EM算法的基本步骤的公式，给了GEM的思想（类似于EM）

1. 证明GEM能够收敛:即

2. 证明 梯度下降求得结果一样 即KaTeX parse error: Undefined control sequence: \part at position 20: …la l(\theta) = \̲p̲a̲r̲t̲(式子) / \part(\t…

   应该是左右求导，ccc做错了

五、简答题

1. K-Means算法步骤
2. PCA算法步骤
3. Bias & Variance 和 模型复杂度关系

2021 SDU算法导论期末考试

2019 计科

计算题 三道 35’

1. (1) 画BFS树

   (2) 做DFS 说明各种边的分类

2. Floyd 求最短路径矩阵

3. 最大流以及最小割的求解(注意最小割怎么写)

证明题 两道 20’

1. 图有负环，证明不管做多少次 都有 成立(负环求和)

2. 证明 e 不在任何最小生成树中 等价于 G有环，e是最大的边(边权不同)

   (课后题)

辨析判断 两道 20’

1. 对于一个 问
   • 每一个MST 用且仅用一条中的边
   • 每一个MST 至少用一条中的边
2. 进行了若干次 之后有
   • 
   • 三角不等式

我写的是1.2 和 2.2是对的，但是感觉第一题不是很确定~

算法设计与分析题 两道 25’

1. 红蓝交替路径变式，即颜色交替路径，有RGB三种颜色，要求路径上相邻两点颜色不同，求s->t 的颜色路径有几条。(DP思想)

2. 完全单连通 即任意(u,v) u->v v->u 都是有且仅有一条简单路，给出判断算法以及算法正确性证明

   (我做的是 SCC强连通 + 单连通判断)

2021 SDU 操作系统期末考试回忆版

简答题(4 10 points)

1. (1) 进程切换的时机 以及 哪些能抢先

   (2) 好像是磁盘管理的一个题 忘记了

2. IO内核子系统、设备驱动程序、中断处理程序功能以及关系

3. 死锁的措施 以及 现在计算机主要怎么处理死锁

4. 文件管理方式 阐述有哪几种 以及 对应的改进方案以及意义

大题(3 10 points)

1. 给一个情景 说明是抖动 说明解决方案两种

2. 优先级调度算平均等待时间 以及 如何改善静态优先级

3. 页表题目 原题

   

设计题

1. 信号量题目 15 points

   王道 银行顾客营业员那个题

   

2. (15 points)

    OS实验里面模拟shell 
    
    给了三个命令  $./a.out \,\,\, \&$    $./ a.out > t.txt$      $./a.out | b.out | c.out$
    
    分别说明命令的意思 以及 用C语言模拟他们的思想、给出关键代码
   

复习指导

1. 看韩老师的PPT 很不错的 多和韩老师沟通
2. 学有余力 看看王道或者智库课本
3. 看看实验 貌似前年还考了个makefile 怎么写 signal_cat 函数怎么用… 今年最后一题属实被意外到了
4. 还是韩老师的ppt最香 没必要多复习别的

2021 SDU图形学期末

计算机学院2019计科

1. 选择题 5*2

1. Bresenham相比DDA 以及 中点画线法优化了一些操作，不包括在这些操作里面的是
2. 忘了不难
3. 主灭点最多的个数
4. 忘了不难
5. phong光照模型 代价最高的操作

2. 大题

1. 扫描填充伪代码 10分

2. 有哪些面消隐算法：画家、Zbuffer、只用一个ZB的zbuffer，扫描线Zbuffer，区间扫描Zbuffer，课本上还有一个 + 光线投射算法

3. Phong光照模型 示意图 以及 解释 以及 的推导过程

4. 给了三维空间一个三角形以及一个正方形，问有无交线段，求出来

5. 考了 变换矩阵 就是那个abcd 的那个，然后复合变化，比较简单

6. 给了四个控制点

   1. 写出三次Bezier的表示，就是带入点化成的形式，我猜的
   2. 转化为三次Bspline，求出控制点 不会啊！ 课本只有Bspline -> Bezier 倒推不太会
   3. 转化为三次Hermite，求 也挺难

7. 正常的透视投影 但是 加了一个世界坐标系和新坐标系的转化

   新坐标系定义：

   目测是原坐标系转化完了，然后平移一下就OK了

   三问

   1. 画示意图
   2. 给了一个点，求最后的投影+新坐标系的坐标
   3. 投影矩阵

复习意见

摆烂摆烂摆烂

图形学：说实话，我自己没学明白。一部分是这学期中间比较忙，没能课下再看看，期末就捉急了。第二，则是两位教授教授方向不太一样，一个偏向idea，一个偏向数学，给人割裂的感觉。 如果是”curve” 老师上课，建议好好听。如果是另一位教研型老师上课，则建议直接去curve上课 或者 看games101

但是，老师们都是很好的，这门课价值也很高，CG也没有CV、DL那么卷，但是就是部分很数学的部分学不明白，然后看games101的话体验感还是不错的，但是考试不考~

以上仅仅代表个人观感，不存在对老师任何意见以及偏见。

2022 编译原理 期末

SDU CS 2019

一、简答与计算

1. 画编译的各个过程
2. 二义文法
3. 找出句柄
4. 逆波兰式
5. FA => 正规式

二、综合题

1、词法分析，给定正规式，

构造NFA

确定化

最小化

2、LL(1)分析，给出文法

构造first、follow集

构造LL1分析表

分析句子

3、LR分析

构造拓广文法

构造LR(1)项目规范族

构造LR(1) 分析表

识别句子

4、给出基本块代码

构造DAG

写出优化之后的中间代码(CH 10)

写出DAG目标优化之后的中间代码(CH 11)

写出目标代码（根据活跃信息）

5、就是PPT的题，给你翻译模式，翻译成中间代码

三、感受

编译原理这门是一门好课，但是SDU课里面所教的内容实在过于抽象，如果你想获得一个好绩点，那么跟着上课不犯困就行OK。如果你想学明白点啥，还是得需要看一些其他地方的课，比如stanford CS 143/国防科大的课。这门课我真是没学明白，但是真的很重要，如果你以后想做数据库，建议专门学一下数据库的parser。

20222 大数据管理与分析 期末考试

SDU 2019 计科

题目

与往年差距比较大

1. 简述人们对大数据的认识和发展历程，以及大数据技术的发展过程
2. HDFS 存储数据有何优势
3. 写自然连接的MapReduce 伪代码 以及输入输出
4. 简述HBase 数据模型，以及如果高效查询数据
5. Hive 与 传统的关系型数据仓库相比的异同点，详细叙述一个HIVE的应用系统
6. KNN MapReduce伪代码，输入输出
7. Apriori算法的思想 以及Spark伪代码……
8. 唯一一道送分题
   1. 等深均分 + 边界光滑
   2. 正规化 num-min / max – min
9. 微博流数据，说明架构 写 实现方式，

按理说流数据用storm啊，哪写过storm