本简介提供了一套针对报考暨南大学计算机应用技术专业博士学位考试的学生复习资料和试题解析，涵盖数据结构、操作系统等核心课程内容。
根据暨南大学博士考试试题中的计算机应用技术部分，可以提炼出多个重要的IT知识点，主要涵盖以下方面：
### 一、离散数学
#### 1. 主析取范式与主合取范式
- **定义**：在命题逻辑中，主析取范式（MDNF）和主合取范式（MCNF）是布尔表达式的特定形式，能精确表示任何给定的布尔函数。
- **求法**：
- **主析取范式**：将给定的布尔函数转换为包含所有使得函数值为真的最小项的析取式。
- **主合取范式**：将给定的布尔函数转换为包含所有使得函数值为假的最大项的合取式。
#### 2. 自然推理系统中的证明
- **定义**：自然推理系统（Natural Deduction System）是一种用于验证命题逻辑或谓词逻辑有效性的形式化方法。
- **归谬法**：通过假设结论的否定，推导出矛盾来证明某个结论的有效性的一种技术。
### 二、算法分析与设计
#### 1. 程序段执行频度分析
- **定义**：程序中某操作重复次数是评估算法效率的重要指标。
- **计算方法**：通过识别循环结构中的基本操作，进而确定其执行次数来完成分析。
#### 2. 顺序搜索的平均搜索次数
- **定义**：顺序搜索是一种直接检查列表元素直到找到目标或遍历完整个列表为止的方法。
- **计算公式**：对于长度为n的数组，如果目标等概率出现在每个位置，则平均搜索次数是(n + 1) / 2。
#### 3. 回溯法与分支限界法
- **定义**：
- **回溯法**：通过尝试解决子问题并在发现不可行时撤销选择的过程。
- **分支限界法**：限制探索空间以寻找最优解的方法，通常用于优化问题中。
- **区别**：回溯更侧重于求所有可能的解集；而分支限界则更侧重于找到最优解。
#### 4. 程序结果分析
- **定义**：通过代码分析预测程序运行时的行为和输出。
#### 5. 图灵机模型
- **确定性图灵机**：每一步操作都是确定的。
- **非确定性图灵机**：在每步中选择多个可能的操作路径。
- **P类问题与NP类问题**：
- **P类问题**：由确定性图灵机能多项式时间解决的问题。
- **NP类问题**：解可被验证为正确的，且能在多项式时间内非确定性地求解。
#### 6. Fibonacci数列的递归实现
- **定义**：Fibonacci序列从0和1开始，并后续每一项都等于前两项之和。
- **递归实现**：使用递归函数来计算该序列中的值。
### 三、排序算法
#### 快速排序
- **描述**：一种高效的通过分治策略将数组分成两部分，分别对这两部分进行排序的算法。选择一个“基准”元素使得左边的所有项都小于它，右边的所有项都大于或等于它。
### 四、贪心算法
#### 贪心定义与应用
- **定义**：一种在每一步选择局部最优解以期望达到全局最优的方法。
- 应用实例：“构建最大相容活动集合”——给定一系列时间段的活动，选择最多数量的互不重叠的活动。
### 五、最大子段和问题
#### 定义与算法实现
- **定义**：在整数序列中寻找连续子序列使其总和最大。
- **方法**：可以使用动态规划或Kadane算法高效解决此问题。
5星
