【数据结构与算法】概论

1. (多选题, 3分)设n为算法中的问题规模，通常用（）渐进符号表示算法的执行时间与n之间的一种增长关系。
   A. Ο
   B. Θ
   C. Ω
   D. Σ
   E. Φ
   正确答案: ABC

• 解析：
  Ο是渐进上界，Ω是渐进下界。Θ需同时满足大Ο和Ω，故称为确界（必须同时符合上界和下界）。Ο极其有用，因为它表示了最差性能。
  Θ，读音：西塔；既是上界也是下界(tight)，等于的意思。
  Ο，读音：大偶；表示上界(tightness unknown)，小于等于的意思。
  ο，读音：小欧；表示上界(not tight)，小于的意思。
  Ω，读音：欧米伽（大写）；表示下界(tightness unknown)，大于等于的意思。
  ω，读音：欧米伽（小写）；表示下界(not tight)，大于的意思。

2. (多选题, 3分)对算法与数据结构关系的描述，正确包括（）。
   A. 数据结构是算法设计的基础。
   B. 一种数据结构只支持一种算法设计。
   C. 算法是编程思想，数据结构则是这些思想的逻辑基础
   D. 算法设计就是在选定的存储结构上设计一个满足要求的好算法。
   正确答案: ACD
   解析：
   （1）数据结构只是静态的描述了数据元素之间的关系；
   （2）高效的程序需要在数据结构的基础上设计和选择算法。
   （3）程序 = 数据结构 + 算法
3. (多选题, 3分)算法操作的对象是数据，数据间的（）就是数据的数据结构。
   A. 逻辑关系
   B. 存储方式
   C. 处理方式
   D. 控制关系
   正确答案: ABC:逻辑关系; 存储方式; 处理方式;
4. (多选题, 3分)算法设计应满足以的目标包括（）。
   A. 输入输出性
   B. 正确性
   C. 可使用性
   D. 可行性
   E. 健壮性
   正确答案: BCE
   解析：算法设计应满足以下几个目标。
   （1）正确性：要求算法能够正确地执行预先规定的功能和性能要求。这是最重要也是最基本的标准。
   （2）可使用性：要求算法能够很方便地使用。这个特性也叫用户友好性。
   （3）可读性：算法应该易于使人理解，也就是可读性好。为了达到这个要求，算法的逻辑必须是清晰的、简单的和结构化的。
   （4）健壮性：要求算法具有很好的容错性，即提供异常处理，能够对不合理的数据进行检查，不经常岀现异常中断或死机现象。
   （5）高效率与低存储量需求：通常算法的效率主要指算法的执行时间。对于同一个问 题，如果有多种算法可以求解，执行时间短的算法效率高。算法存储量指的是算法执行过程 中所需的最大存储空间。效率和存储量都与问题的规模有关。

一个算法必须满足5大特性：
1、有穷性：一个算法必须执行有穷步后结束、
2、确定性：对于每种情况下所应执行的操作，在算法中都应该有确切的规定，不会产生二义性，使得算法的执行者和阅读者都能明确其含义以及如何执行。
3、可行性：算法中的所有操作都可以通过已经实现的基本操作运算执行有限次来实现
4、输入：一个算法应该有0个、一个或多个输入。
5、输出：一个算法应该有一个或多个输出

5. (单选题, 2分)一切合法的输入数据都能得出满足要求的结果，包括典型的、苛刻的输入数据也能够得出满足要求的结果。这个含义对应算法的（）。
   A. 可靠性
   B. 正确性
   C. 有效性
   D. 可用性
   正确答案: B
   解析：
   正确性：对合法的输入有满足要求的结果
   健壮性：对非法的输入有适当的处理
6. (单选题, 2分)算法要对异常情况进行适当的处理，就是算法的（）。
   A. 正确性
   B. 可用性
   C. 健壮性
   D. 可行性
   正确答案: C
7. (判断题, 1分)如果一个算法对其每一个输入实例，都能输出正确的结果并停止，则称它是可靠的。
   A. 对
   B. 错
   正确答案: 错
   解析：
   正确性：合法的输入的处理
8. (判断题, 1分)算法是把人类找到的求解问题的方法，用算法要素过程化、形式化、机械化地表示出来。
   A. 对
   B. 错
   正确答案: 对
9. (判断题, 1分)算法分析是分析算法占用计算机资源的情况，即分析算法的时间复杂度。
   A. 对
   B. 错
   正确答案: 错
   解析：时间复杂度和空间复杂度。
10. (判断题, 1分)一个算法的时间用Ω符号表示时，总是采用最有价值的g(n)表示，称之为“紧凑下界”或“紧确下界”。
    A. 对
    B. 错

10.下列哪个函数是O(N)的？ (2分)
选项
A (logN)2
B (NlogN)/1000
C N(logN)2
D N2​​/1000
解析：(logN)2 < N < (NlogN)/1000 < N(logN)2 < N2​​/1000。
11.下列函数中，哪个函数具有最快的增长速度？ (2分)
选项
A N2​​ logN
B N(logN)4
C N3
D NlogN2
解析：NlogN2 < N2​​logN < N(logN)4 < N3。
13.下列函数中，哪个函数具有最慢的增长速度：(2分)
选项
A N1.5
B NlogN2
C N2​​ logN
D N(logN)2
解析：NlogN2 < N1.5 < N(logN)2 < N2​​logN。