Skip to content

Instantly share code, notes, and snippets.

@sagnitude

sagnitude/fdu_961_2019.md

Last active April 19, 2019 09:01
Show Gist options
  • Save sagnitude/77b8a7b3fa988aae052547ec2eb86f34 to your computer and use it in GitHub Desktop.
Save sagnitude/77b8a7b3fa988aae052547ec2eb86f34 to your computer and use it in GitHub Desktop.
Download ZIP
2019 FDU MSE 961
Raw
fdu_961_2019.md

数据结构与算法(60')

  1. 为何单向链表只能在尾部入，头部出？如果要使得尾部和头部都能以O(1)进行插入和删除操作，需要做什么改造？
  2. Dijkstra算法填空
  3. 写一个高效的构建二叉堆的算法，分析其复杂度，并给出结果
  4. 写一个算法，统计二叉树中有2个非空子树的节点，并分析复杂度
  5. 写一个算法，从输入的数字序列中，提取最小的k个元素，并达到O(N)的复杂度，如果达不到O(N)的复杂度，会酌情给分

软件工程(60')

  1. 分4小问，4×4分=16分
  • 简述CMMI
  • 简述需求获取的途径
  • 简述抽象和逐步求精的关系
  • 怎样判断用例的好坏？
  1. 23分
  • 给定一个需求，画出状态机图：台灯有灭-弱光-强光状态，有接通电源和使用内置充电电池两种能量来源，只有一个按钮，按按钮会使得在 灭-弱光-强光 三个状态中切换，如果没有接通电源也没有足够的电量，按按钮没反应；如果是亮的状态，却没有接通电源，当内置电池电量用完的时候会灭掉
  • 给定一个考试管理系统，给出顶层和0层图，0层分解为考试报名系统和成绩管理系统
  1. (15') 给定一个CBubbleSorter类中的Sort方法，问
  • 什么是内聚性？这个方法符合内聚性吗？为什么？怎样提高这个方法的内聚性？
  • 如果这个类是继承自CSorter类，画一个类图来表示这两个的关系
  • 根据上面的类图，怎样设计才能方便地切换为其他的排序算法？你的改动体现了什么设计规则？
  1. 2×3=6分
  • 白盒测试的覆盖标准，至少列出三个
  • 有人说：“测试就是检查程序的正确性”，对吗？解释下

ICS(30')

  1. 三问，3×10=30分
  • 流水线的分段划分方法非常影响流水线的性能，简述一下怎么个影响法；阐述下基于分段的流水线处理器中，什么是加速比；简述下怎么分段才能使加速比趋向于理想中的加速比？
  • 流水线的停顿非常影响性能，一般有什么原因会出现停顿？一般用什么策略解决停顿问题？
  • 现代CPU中，分层存储结构如何影响流水线的性能？存储层级结构是基于什么原理设计的？为降低存储对CPU的影响，应该采取什么措施进行优化？
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment