1
我的问题:树、二叉树、搜索树,区别是什么?
你的回答:
树是最一般的层级结构,一个节点可以有多个子节点;二叉树要求每个节点最多有两个子节点;二叉搜索树 BST 在二叉树基础上进一步要求:
| |
所以可以理解为:
| |
二叉树主要限制“形状”,BST 还限制“数据的排列方式”,因此更适合搜索。
2
我的问题:堆结构呢?
你的回答:
堆通常指二叉堆,是一种满足特殊规则的完全二叉树。
最大堆:
| |
所以根节点一定是最大值。
最小堆:
| |
所以根节点一定是最小值。
它和 BST 的核心区别:
| |
BST 适合搜索某个值;堆适合快速获得最大值或最小值,优先队列通常就是用堆实现的。
3
我的问题:群聚类?
你的回答:
如果指“聚类 clustering”,它不是一种数据结构,而是一类算法/机器学习方法。
核心思想:
把相似的数据自动分到同一组。
常见方法包括 K-means、层次聚类、DBSCAN。
其中层次聚类的结果可以用树状结构表示,但“聚类”本身不是树这种数据结构。
4
我的问题:类中的 private 和 public,是不是前者只能在声明本类的程序文件里使用,而 public 可以在整个项目中使用?
你的回答:
不是。private/public 管的是类的访问权限,不是文件范围。
| |
通常只有这个类自己的成员函数以及 friend 可以直接访问。
即使 main() 和这个类写在同一个 .cpp 文件:
| |
仍然不能访问 private。
而:
| |
允许类外代码通过对象访问。
核心:
private/public管的是“类边界”,不是“文件边界”。
5
我的问题:模板是什么?PPT 里的代码怎么看?
你的回答:
模板的核心思想是:
把“数据类型”也作为参数,具体使用时再确定类型。
例如:
| |
这里 Type 是一个类型占位符。
使用:
| |
相当于 Type = int:
| |
使用:
| |
相当于:
| |
template<class Type> 和:
| |
这里基本等价。
类外定义模板成员函数时:
| |
意思是给 dataList<Type> 这个模板类定义成员函数。
模板内部使用:
| |
而不是:
| |
是因为这个类将来可能存 int、double 等不同类型。
另外,模板类型必须支持模板内部使用的操作。例如:
| |
意味着 Type 必须支持 < 运算。
6
我的问题:使用模板,是不是都得是一个数据类型?如果类里第一个数据是 int,第二个是 char 怎么定义?
你的回答:
不是。模板并不意味着整个类所有数据类型必须一样。
如果类型固定:
| |
只有 c 的类型由模板决定。
如果两个变量的类型都希望由使用者决定,可以定义多个模板参数:
| |
使用:
| |
此时:
| |
所以模板本质上是:
把需要变化的类型抽出来作为参数,而不是要求所有成员同一种类型。
7
我的问题:顺序搜索算法的代码怎么理解?函数传参语法是什么?
你的回答:
函数:
| |
有三个形参:
| |
核心算法:
| |
意思是从 a[0] 开始逐个找。
找到:
| |
返回下标。
没找到:
| |
因为合法数组下标不会是 -1。
int a[] 作为函数参数时,本质上近似于:
| |
函数本身不知道数组长度,因此还需要额外传入 n。
8
我的问题:函数定义了三个参数,实际调用时应该怎么传?
你的回答:
例如定义:
| |
调用:
| |
对应:
| |
也就是:
在
arr的前 4 个元素里寻找3。
函数定义时写类型:
| |
函数调用时只传实际数据:
| |
不能写:
| |
数组作为实参时直接写数组名。
9
我的问题:我自己写的顺序搜索程序哪里有问题?
你的回答:
主要有几个语法错误。
main:
| |
应该写:
| |
函数调用:
| |
应该写:
| |
因为函数调用时数组直接写数组名,而且语句末尾要有 ;。
由于定义的是:
| |
搜索函数最好对应写:
| |
表示搜索函数只读取数组、不修改数组。
另外:
| |
应该是:
| |
#include 后面不加分号。
10
我的问题:结合循环嵌套讲时间复杂度怎么计算?不同运算的时间复杂度是什么?
你的回答:
时间复杂度表示:
输入规模增大时,算法基本操作执行次数的增长速度。
最重要的规则:
| |
例如:
| |
外层 m 次,每次执行内层 n 次:
所以:
\[ O(mn) \]两个并列循环:
| |
最终只保留最高阶:
\[ O(n²) \]常见复杂度:
| 情况 | 时间复杂度 |
|---|---|
| 普通赋值、加减、数组下标访问 | O(1) |
| 单层完整循环 | O(n) |
| 每次规模减半 | O(log n) |
n 层工作中每次 log n | O(n log n) |
| 两层完整循环 | O(n²) |
| 三层完整循环 | O(n³) |
复杂度增长:
\[ O(1)11
我的问题:封装、继承、多态在面向对象中怎么定义?
你的回答:
封装:
把数据和操作数据的方法放在类内部,并控制外部如何访问。
主要体现:
| |
继承:
一个新类在已有类基础上获得并扩展其成员。
例如:
| |
表示 Dog 继承 Animal。
多态:
使用同一个接口面对不同类型的对象时,可以执行不同的实现。
例如:
| |
当 a 实际指向 Dog 时调用 Dog::speak();指向 Cat 时调用 Cat::speak()。
C++ 运行时多态主要通过:
| |
实现。
可以简记:
| |
12
我的问题:C 语言中的 << 是什么意思?
你的回答:
在 C 中,<< 是左移运算符。
例如:
| |
5 的二进制:
| |
左移一位:
| |
得到 10。
对非负整数可以粗略理解为:
\[ x << n \approx x\times2^n \]但要和 C++ 的:
| |
区分。
这里的 << 是 C++ 对运算符进行了重载,表示输出,不是在进行位移。
13
我的问题:多态感觉也挺麻烦,我还是要在子类里 override 一遍,它有什么优点?
你的回答:
多态的目的不是减少子类具体行为的代码,而是:
让使用这些对象的代码不需要针对每一种具体类型分别编写。
狗和猫的行为不同:
| |
这些具体实现当然必须分别写。
但使用它们的代码可以统一:
| |
甚至:
| |
数组中无论实际放的是 Dog、Cat 还是以后增加的 Bird,调用代码都可以不变。
所以多态真正的优势是:
增加新类型时,尽量不修改原来的调用代码。
另外,这里的 override 中文更准确叫重写/覆盖,不是重载。
14
我的问题:std:: 是什么意思?
你的回答:std:: 表示:
C++ 标准库的
std命名空间中的东西。
例如:
| |
其中:
| |
叫作用域解析运算符,可以简单理解为“属于”。
所以:
| |
就是:
std中的cout。
如果写:
| |
之后通常就可以直接写:
| |
而不用重复写 std::。