跳转至

导论期中卷纸和我的解答

这份卷纸2020，2021，2022，2023级都在用

我的成绩：95 前面的题全对，就最后一个设计题扣了点分

Introduction to Data Science and Engineering (Middle term)

Multiple Choice Questions (\(3' \times 6 = 18'\))

1. Which of the following is not contained in a CPU?

A. Instruction register

B. Program counter

C. General-purpose register

D. Memory cell

我的解答： D

2. In which of the following locations is information most readily available for manipulation by the CPU?

A. General-purpose registers

B. Main memory

C. Mass storage

我的解答： A

3. Which of the following is the binary representation of \(4\ 5/8\)?

A. 100.11

B. 10.011

C. 110.101

D. 100.101

我的解答： D

4. When searching within the list

Lewis, Maurice, Nathan, Oliver, Pat, Quincy, Roger, Stan, Tom

which of the following entries will be found most quickly using the binary search algorithm?

A. Lewis

B. Pat

C. Tom

我的解答： B

5. In general, an algorithm in which of the following categories is considered more efficient?

A. \(\Theta(lg\ n)\)

B. \(\Theta(n)\)

C. \(\Theta(n\ lg\ n)\)

D. \(\Theta(n^2)\)

我的解答： A

6. Which of the following is not an activity performed entirely within a CPU?

A. Fetch instructions

B. Perform Boolean operations

C. Perform arithmetic operations

D. Move data between registers

我的解答： A

Fill-in-the-blank (\(3' \times 9 = 27'\))

1. In a relational database, information is presented as though it were stored in tables called _, each of which has columns called _ and rows called __.

我的解答： relation, attribute, tuple

2. Given the two relations X and Y below

X:

A B
2 s
5 z

Y:

C D
t 1
r 3
w 2

what values would be in the tuple produced by the following statement?

Result ← JOIN X and Y where \(X.A < Y.D\)

我的解答： 2 s r 3

3. Write the answer to each of the following logic problems.

10101010 OR 11110000 = __

10101010 XOR 11110000 = __

我的解答：

OR的结果为：11111010

XOR的结果为：01011010

4. If the patterns 101.11 and 1.011 represent values in binary notation, what is the binary representation of their sum?

我的解答： 111.001

5. What sequence of values will be printed when the following instructions are executed?

\(x \leftarrow 5\)

while (\(x < 7\)) do (print the value of \(x\); \(x \leftarrow x + 1\))

print the value of \(x\);

while (\(x > 2\)) do (print the value of \(x\); \(x \leftarrow x - 2\))

我的解答： 5 6 7 7 5 3

6. At most, how many entries in a list of 5000 names will be interrogated when using the binary search algorithm?

我的解答： 13

Short-answer Questions (\(5' \times 2 = 10'\))

1. The factorial of 0 is defined to be 1. The factorial of a positive integer is defined to be the product of that integer times the factorial of the next smaller nonnegative integer. We use the notation \(n!\) to express the factorial of the integer \(n\). Thus the factorial of 3 (written \(3!\)) is \(3 \times 2! = 3 \times (2 \times 1!) = 3 \times (2 \times (1 \times 0!)) = 6\).

Design a recursive algorithm that computes the factorial of a given value.

我的解答：

int func (int n){
    if (n == 0) { return 1; }
    else return func(n - 1) * n;
}

2. From the following list, extract a collection of numbers whose sum is 3165. How efficient is your approach to the problem?

26, 39, 104, 195, 403, 504, 793, 995, 1156, 1677

我的解答：

使用动态规划的思想求解，时间复杂度为 \(O(n)\)。

详细伪代码略

问答题 (\(5' \times 5 = 25'\))

1. 计算思维和数据思维的内容是什么？它们之间是什么关系？举出2个你认为是数据思维的实例。

我的解答：

  • 计算思维： 将问题分解为可解决的、更小的、更易处理的子问题的思维方法。
  • 数据思维： 使用数据证明，依托于数据导向型的数据分析的最直接体现。
  • 实例：
  • 零售业的库存优化，分析历史销售数据、季节性变化因素等，提升盈利能力。
  • 金融领域的信用评分，分析用户的信用历史、收入、支出等数据，决定是否放贷。

2. 数据模型是什么？它和数据结构之间的关系是什么？举出你熟悉的5种数据模型。

我的解答：

① 数据模型是对现实世界中某个系统或问题促成的抽象描述，用来表示数据、数据之间的关系以及对数据的约束。

② 数据结构是数据模型实现的基础，不同的数据模型需要不同的数据结构来约束。

熟悉的5种数据模型：层次模型、关系模型、面向对象模型、实体-关系模型、文档模型。

3. 画出一个典型的冯·诺依曼模型，并简要说明个组成部分的功能。

我的解答：

(注：试卷中绘制了结构图，以下为其文字说明部分)

包含五个主要部分：

  • 运算器 (ALU)： 完成各种算术与逻辑运算。
  • 控制器 (CU)： 从内存中取指令，翻译指令，分析指令，然后向有关部件发送控制指令。
  • 存储器： 存储各种数据和程序，在运行时自动方便地存储。
  • 输入设备： 向计算机输入数据。
  • 输出设备： 输出计算结果。

4. 一个典型的程序执行周期包括哪几个方面？以“2+3=5”为例简要说明程序的执行过程。

我的解答：

包含方面：取指令、指令解码、执行指令、写回结果。

执行过程实例：计算机从存储器中获得了一条加法指令；计算机解码加法指令，确定了加法运算的两个操作数地址；从存储位置读取了2、3，然后送入寄存器，并相加得到5；最后写回5到指定的位置。

5. 怎么理解“程序 = 数据结构 + 算法”？通过一个实例来说明数据结构和算法的关系。

我的解答：

① 程序的基本构成要素是数据结构和算法，即一个良好的程序需要合适的数据结构来组织和存储数据，并且需要有效的算法对数据进行处理。

② 例如堆排序：当我们想要快速地解决排序大量数字的问题时，可以维护一个堆（数据结构），它的性质是最顶层元素最小；然后不断执行取出顶层元素，并把末尾元素放入顶层，再反复下沉调整的操作（算法）。

设计题 (\(10' \times 2 = 20'\))

1. 假定你是一个数据架构师，希望能给华东师范大学设计一个校园网搜索引擎，可以针对学校里面的各种网站信息进行搜索（官方网站、各院系网站、BBS、实验室网站等等）。试从系统的角度给出一个完整的搜索引擎系统架构，并针对数据全生命周期，给出每个部分可行的实现技术。

(提示：数据的全生命周期包括数据的采集、存储、管理、计算、分析、以及展示。)

我的解答：

  • 采集： 使用网络爬虫定期抓取学校内网站的内容。
  • 存储： 使用分布式的数据库，如 Apache Cassandra 等存储爬取到的内容。
  • 管理： 使用 ETL 工具，确保数据的一致性和准确性。
  • 计算/分析： 使用分布式的计算框架，采用合理的算法，对网页进行重要性分析。
  • 展示： 使用前端框架 Vue.js 等构建用户友好的界面，使用可视化工具展示数据结果（如 Tableau）。而搜索引擎的核心可利用搜索引擎 Elasticsearch。

2. 还是上面的场景，如果除了需要搜索网页信息外，还希望搜索图片和视频，试从存储系统的角度，设计一个面向这种网页、图片、视频数据的存储方案。

*提示：可以从结构化数据、非结构化数据，以及集中式与分布式的角度进行思考)

我的解答：

① 对于网页数据，我们可以采用结构化数据存储，使用 MySQL 存储网页的元信息。

② 对于图片、视频等非结构化数据，我们可以采用对象存储的方式，每个图片和视频文件都作为对象，使用 Amazon S3 等进行存储。

③ 因此，我们最好采用分布式的数据库系统，利用好其特性，确保数据在不同节点上的高可用性和负载均衡。