综述ppt的问题

1

我的问题:树、二叉树、搜索树,区别是什么?

你的回答:
树是最一般的层级结构,一个节点可以有多个子节点;二叉树要求每个节点最多有两个子节点;二叉搜索树 BST 在二叉树基础上进一步要求:

1
左子树所有节点 < 根节点 < 右子树所有节点

所以可以理解为:

1
树 ⊃ 二叉树 ⊃ 二叉搜索树

二叉树主要限制“形状”,BST 还限制“数据的排列方式”,因此更适合搜索。


2

我的问题:堆结构呢?

你的回答:
堆通常指二叉堆,是一种满足特殊规则的完全二叉树。

最大堆:

1
父节点 >= 子节点

所以根节点一定是最大值。

最小堆:

1
父节点 <= 子节点

所以根节点一定是最小值。

它和 BST 的核心区别:

1
2
BST:左 < 根 < 右
堆:只保证父子之间的大小关系

BST 适合搜索某个值;堆适合快速获得最大值或最小值,优先队列通常就是用堆实现的。


3

我的问题:群聚类?

你的回答:
如果指“聚类 clustering”,它不是一种数据结构,而是一类算法/机器学习方法。

核心思想:

把相似的数据自动分到同一组。

常见方法包括 K-means、层次聚类、DBSCAN。

其中层次聚类的结果可以用树状结构表示,但“聚类”本身不是树这种数据结构。


4

我的问题:类中的 private 和 public,是不是前者只能在声明本类的程序文件里使用,而 public 可以在整个项目中使用?

你的回答:
不是。private/public 管的是类的访问权限,不是文件范围。

1
2
private:
    int x;

通常只有这个类自己的成员函数以及 friend 可以直接访问。

即使 main() 和这个类写在同一个 .cpp 文件:

1
obj.x = 10;

仍然不能访问 private。

而:

1
2
public:
    int x;

允许类外代码通过对象访问。

核心:

private/public 管的是“类边界”,不是“文件边界”。


5

我的问题:模板是什么?PPT 里的代码怎么看?

你的回答:
模板的核心思想是:

把“数据类型”也作为参数,具体使用时再确定类型。

例如:

1
2
3
4
template <class Type>
class dataList {
    Type* Element;
};

这里 Type 是一个类型占位符。

使用:

1
dataList<int> a;

相当于 Type = int:

1
int* Element;

使用:

1
dataList<double> b;

相当于:

1
double* Element;

template<class Type> 和:

1
template<typename Type>

这里基本等价。

类外定义模板成员函数时:

1
2
template<class Type>
void dataList<Type>::Swap(...)

意思是给 dataList<Type> 这个模板类定义成员函数。

模板内部使用:

1
Type temp;

而不是:

1
int temp;

是因为这个类将来可能存 int、double 等不同类型。

另外,模板类型必须支持模板内部使用的操作。例如:

1
Element[a] < Element[b]

意味着 Type 必须支持 < 运算。


6

我的问题:使用模板,是不是都得是一个数据类型?如果类里第一个数据是 int,第二个是 char 怎么定义?

你的回答:
不是。模板并不意味着整个类所有数据类型必须一样。

如果类型固定:

1
2
3
4
5
6
template<class T>
class A {
    int a;
    char b;
    T c;
};

只有 c 的类型由模板决定。

如果两个变量的类型都希望由使用者决定,可以定义多个模板参数:

1
2
3
4
5
template<class T1, class T2>
class A {
    T1 a;
    T2 b;
};

使用:

1
A<int, char> x;

此时:

1
2
T1 = int
T2 = char

所以模板本质上是:

把需要变化的类型抽出来作为参数,而不是要求所有成员同一种类型。


7

我的问题:顺序搜索算法的代码怎么理解?函数传参语法是什么?

你的回答:
函数:

1
int seqsearch(int a[], const int n, const int x)

有三个形参:

1
2
3
a → 要搜索的数组
n → 数组长度
x → 要搜索的目标值

核心算法:

1
2
3
4
5
6
7
8
9
int i = 0;

while (i < n && a[i] != x)
    i++;

if (i ** n)
    return -1;

return i;

意思是从 a[0] 开始逐个找。

找到:

1
return i;

返回下标。

没找到:

1
return -1;

因为合法数组下标不会是 -1。

int a[] 作为函数参数时,本质上近似于:

1
int* a

函数本身不知道数组长度,因此还需要额外传入 n。


8

我的问题:函数定义了三个参数,实际调用时应该怎么传?

你的回答:
例如定义:

1
int seqsearch(int a[], const int n, const int x)

调用:

1
2
3
int arr[] = {5, 8, 3, 9};

int result = seqsearch(arr, 4, 3);

对应:

1
2
3
a ← arr
n ← 4
x ← 3

也就是:

在 arr 的前 4 个元素里寻找 3。

函数定义时写类型:

1
int seqsearch(int a[], const int n, const int x)

函数调用时只传实际数据:

1
seqsearch(arr, 4, 3);

不能写:

1
seqsearch(arr[], 4, 3);

数组作为实参时直接写数组名。


9

我的问题:我自己写的顺序搜索程序哪里有问题?

你的回答:
主要有几个语法错误。

main:

1
int main

应该写:

1
int main()

函数调用:

1
search(list[], 10, 6)

应该写:

1
search(list, 10, 6);

因为函数调用时数组直接写数组名,而且语句末尾要有 ;。

由于定义的是:

1
const int list[]

搜索函数最好对应写:

1
int search(const int a[], const int n, const int target)

表示搜索函数只读取数组、不修改数组。

另外:

1
#include <iostream>;

应该是:

1
#include <iostream>

#include 后面不加分号。


10

我的问题:结合循环嵌套讲时间复杂度怎么计算?不同运算的时间复杂度是什么?

你的回答:
时间复杂度表示:

输入规模增大时,算法基本操作执行次数的增长速度。

最重要的规则:

1
2
3
顺序执行 → 相加
嵌套执行 → 通常相乘
最后忽略常数和低阶项

例如:

1
2
3
for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
        ...

外层 m 次,每次执行内层 n 次:

\[ m\times n \]

所以:

\[ O(mn) \]

两个并列循环:

1
O(n) + O(n²)

最终只保留最高阶:

\[ O(n²) \]

常见复杂度:

情况时间复杂度
普通赋值、加减、数组下标访问O(1)
单层完整循环O(n)
每次规模减半O(log n)
n 层工作中每次 log nO(n log n)
两层完整循环O(n²)
三层完整循环O(n³)

复杂度增长:

\[ O(1)

11

我的问题:封装、继承、多态在面向对象中怎么定义?

你的回答:

封装:

把数据和操作数据的方法放在类内部,并控制外部如何访问。

主要体现:

1
2
private
public

继承:

一个新类在已有类基础上获得并扩展其成员。

例如:

1
class Dog : public Animal

表示 Dog 继承 Animal。


多态:

使用同一个接口面对不同类型的对象时,可以执行不同的实现。

例如:

1
2
Animal* a;
a->speak();

当 a 实际指向 Dog 时调用 Dog::speak();指向 Cat 时调用 Cat::speak()。

C++ 运行时多态主要通过:

1
2
virtual
override

实现。

可以简记:

1
2
3
封装:怎么藏
继承:怎么复用
多态:同一个调用怎么产生不同表现

12

我的问题:C 语言中的 << 是什么意思?

你的回答:
在 C 中,<< 是左移运算符。

例如:

1
5 << 1

5 的二进制:

1
00000101

左移一位:

1
00001010

得到 10。

对非负整数可以粗略理解为:

\[ x << n \approx x\times2^n \]

但要和 C++ 的:

1
cout << x;

区分。

这里的 << 是 C++ 对运算符进行了重载,表示输出,不是在进行位移。


13

我的问题:多态感觉也挺麻烦,我还是要在子类里 override 一遍,它有什么优点?

你的回答:
多态的目的不是减少子类具体行为的代码,而是:

让使用这些对象的代码不需要针对每一种具体类型分别编写。

狗和猫的行为不同:

1
2
Dog::speak()
Cat::speak()

这些具体实现当然必须分别写。

但使用它们的代码可以统一:

1
2
Animal* a;
a->speak();

甚至:

1
2
for (int i = 0; i < n; i++)
    animals[i]->speak();

数组中无论实际放的是 Dog、Cat 还是以后增加的 Bird,调用代码都可以不变。

所以多态真正的优势是:

增加新类型时,尽量不修改原来的调用代码。

另外,这里的 override 中文更准确叫重写/覆盖,不是重载。


14

我的问题:std:: 是什么意思?

你的回答:
std:: 表示:

C++ 标准库的 std 命名空间中的东西。

例如:

1
2
3
std::cout
std::cin
std::string

其中:

1
::

叫作用域解析运算符,可以简单理解为“属于”。

所以:

1
std::cout

就是:

std 中的 cout。

如果写:

1
using namespace std;

之后通常就可以直接写:

1
2
3
cout
cin
string

而不用重复写 std::。

使用 Hugo 构建
主题 Stack 由 Jimmy 设计