💯 CSC3200 Final Revision C++ 期末样卷

C++ Final Revision

CSC 3200 是一节 2025-26 学年的新增学科，不存在往年样卷，但 CSC 3002 也有 C++ 内容（区别是没有数据结构），以下是港中深 3002 这门课 2021 年的期末考卷：

以下是答案：


Key Takeaways

  1. Pointers, Reference and Array
  • 声明时的星号：char *p; 或 char* p (你想写多少个空格都没区别) 表示声明右边最近的一个变量为指针，指向左边数据类型的对象。所以，char *p, q; 中 q 不是指针。char const *p; 和 char *const p; 分别表示 ”指向常量的指针“ 和 ”常指针“，与星号的位置有关——⚠️星号右边形容指针，左边形容指向的对象。
  • 声明时的与号：char &r = o; 表示引用一个存在的变量 o，引用就是给 o 起小名叫 r，修改两者中任意一者，另外一个都随之改变。如果函数传参不用引用（不用指针时），就不会改外面的值；如果函数传回的临时变量属于引用类型，会导致数据被清除。char *&p 表示引用一个指针，反之 char &*p 不合法。
  • 作为运算符的星号、与号：*p 表示解引用，&v 表示取引用，*&v == v，&*p == p
  • 自增自减符号：++v 先自增后返回值；v++ 先返回值再自增，两者作为循环的 iterator 时没有区别。核心⚠️：*++p 表示先指向下一位再返回解指针；++*p 表示先解指针再返回值+1；*p++ 表示先返回解指针再指向下一位；(*p)++ 表示先返回解指针再把值+1。
  • 内存：函数中 char arr1[42]; 直接在 Stack 上申请内存；auto arr2 = new char[42]; 在 Heap 上申请内存。注意⚠️：new 一定会返回指向 Heap 上对象的指针 (arr2)，且这个指针本身默认存在 Stack 上。前者不用删，后者要手动析构：delete[] arr;。如果在函数/循环/判断体外，直接暴露在类中，char arr[42]; 这种声明会产生全局变量，存储在 Global/Static Area，在任意位置申请 static char 也会存在这里。
  • 数组：数组对象 char arr[42]; 会自动隐式衰退为指向第一个元素的指针，所以 *arr (第一个元素) 和 arr+n (第 n 个元素) 都是合法的。注意⚠️：arr++ 是不合法的，数组不等价于指针。反之，auto ptr = arr; 时，ptr[n] 是合法的访问。
  • 双重数组：char arr[][42] 代表一个元素为 “42 位字符数组” 的数组，只会衰退一层：char (*a)[42]，转变为指向第一个 “42 位字符数组” 的指针。双重数组与双重指针毫无关系，所以不能再衰退了。


  1. Time Complexity

  • 三种基础排序：

    Selection Sort 从左每次选第 n 小的元素与第 n 位交换； x 个元素时要比较 x-1 次才能知道最小项，总共 $(n-1)+(n-2)+…+1+0={n(n-1)\over 2}$ 次比较，稳定在 O(n2)。与有序性无关

    Insertion Sort 从左到右把每个元素左移到左边比自己小为止；类似上面，最多 ${n(n-1)\over 2}$ 次移动，平均/最差 O(n2)，当本身有序时只遍历一次最优 O(n)。越有序越快

    Bubble Sort 从左到右两两交换，一般需要多轮；最多 ${n(n-1)\over 2}$ 次交换，平均/最差 O(n2)，当本身有序时如果加检测模块可以做到最优 O(n)。越有序越快

  • 四种二分思路排序：

    Quick Sort 将中点作 pivot 左边放更小元素右边放更大元素，对左右区间递归；n 个元素放在二叉树中高 log2n，平均/最优 O(nlogn)，如果每次选择的 pivot 都是最大/最小值，退化为 Selection Sort，最差 O(n2)。与有序性无关，但与 pivot 有关

    BST Sort insert 到二叉树中然后中序遍历；同上，最优/平均 O(nlogn)，如果数列本身已经有序会退化为链表，最差 O(n2)。越有序越慢

    Merge Sort 递归地左右分组直到只有一个元素，回溯排序；因为不依靠选择中值也没用 BST 结构，不会退化并稳定在 O(nlogn)。 与有序性无关

    Heap Sort 建最小堆然后进行 n 次 deleteMin；建堆 O(n)，n 次 deleteMin 每次 O(logn)，稳定在 O(nlogn)。与有序性无关

  • 平均情况 Quick Sort ≲ Merge Sort ≲ Heap Sort ≲ BST Sort ≪ Insertion Sort ≲ Bubble Sort ≲ Selection Sort



  1. OOP

  • OOP 的三大核心：Encapsulation (将 method 和 data 打包成 class，防止泄露或干扰)；Polymorphism (分为 compile-time (overload) 通过不同签名实现函数同名，和 run-time (override) 子类覆盖父类的同名函数)；Inheritance (子类继承父类的成员)。

  • 重载：函数的参数类型、参数个数都算签名，但 ⚠️return 类型不算。

  • 继承：class Son : public Father 子类无法访问父类的 protected 字段，之外的字段降级为继承类型 (e.g. public inheritance 不变，private inheritance 全变 private) 。

    vitual inheritance： 可以解决 diamond inheritance (A-BC-D 菱形继承) 时 A 的二义性 ambiguity (D 里只生成一份虚拟 A 基类)。

    virtual function：父类中声明 virtual 的函数都会调用子类的非 virtual 同名函数，即发生 run-time polymorphism，反之未特别声明时，函数优先调用父类 (⚠️在子类中声明无效)。

  • 完全没有自定义参数的操作符重载是违法的，比如 operator+(char &a, char &b) {} 就无法编译；std::string，以及自定义的 struct、enum 或 class 都可以重载操作符。

  • class Example {int a; char* b;}; 的 Constructor 初始化部分可以简写为 public: Example (int x, char* y) : a(x), b(y) {}

  • 自定义类时，一般都要把成员变量放在 private 字段，并暴露 constructor、getter、setter 等接口 (interface) 来实现访问。但是，声明一个方法为 friend 可以在类外直接用/改 private 内容。注意⚠️：A 类的 private 部分声明friend class B 只是给 B 的成员开了“通行证”，仍不能在类外访问 A 的私有部分！

  • ⚠️C++ 默认的拷贝构造函数是 shallow copying 只拷贝值，指针也复制，导致复制后指向相同内存位置，逻辑类似于引用； deep copying 直接 new 一个新位置，不受母本印象。Rule of Three：只要定义其中一个，就要全部自定义：Copy Constructor (复制实例)、Copy Assgnment Operator (赋值)、Destructor (析构)。

  • namespace 是一层保护类的空间，通过 using namespace std; 或 using std::string 这类语句防止不同空间中重名函数的混淆。



  1. Basic Data Structure

  • Collection Class (容器类) 是一种 ADT。一般说数组、动态数组、链表、集合、表都算是经典的容器类，栈和堆是受限的容器。在 STD 中，容器类返回的容量参数 (接口一般叫 .size()) 是 size_t 类型的，不转换就不能直接当 int 使用。容器类的 .end() 函数一般返回最后一个元素的下一个空位。

  • 动态数组 std::vector 是可以自动/手动扩容的数组。实例化比如：new std::vector<int> arr(42)。典型的容器类，要求 effective size 永远小于等于 allocation size，也就是 arr.size() <= arr.capacity()。预留函数 .reserve(x) 扩容 a.s. 到 x，不改变 e.s.，且无法减小。扩容函数 .resize(x, v)将 e.s. 扩大到 x，并把未定义的项初始化为 v，可以减小，但不改变 a.s.。.push_back() 向数组尾部添加元素。动态数组的随机插入 O(n)，随机访问O(1)。


  • 链表 LinkedList 由节点类 class Node {T value; Node<T>* next;}; 以及表体类 class List {List () {}} 构成，每个旧节点的 next 成员指向新节点的内存位置。在 List 中常设置一个 private 的空占位节点，并在构造函数中初始化 dummyHead = new Node<T>(T(), nullptr);，这样就不需要每次插/删都检测是否空。


    .insert() 只需要传入前序节点的指针 prev，然后 prev->next = new Node<T>(v, prev->next); 即可 (新节点接 prev 原本的后节点，然后 prev 接新节点)。.delete() 先 find 前序节点 prev，然后 auto target = prev->next; prev->next = prev->next->next; delete target; 只要有链表结构，绕过被删除项前一定要做临时指针，否则绕过后想删除时就找不到它了。

    链表的所有节点都是 new 产生的，要逐个析构。链表的随机插入 O(1)，随机访问 O(n)，恰好与 (动态) 数组相反。


  • 栈 Stack 是 LIFO，只从一边操作 (top) 的受限数据类型。

    接口：push()、pop()、top()、isEmpty()

    数组栈：stack[] 数组中，用 top 索引栈顶的下一位；插 T& pop() {return stack[--top];}；删 void push(const T x) {stack[top++] = x;} ；是否空 bool isEmpty(){return !(top-1);}。

    链栈：类似于链表，需要 (Node 和 Stack) 两个类。与链表相反，新元素指向旧元素，从栈顶逐个指向栈底，用 topPtr 指向顶节点；操作与链表相似，不再赘述。


  • 队列 Queue 是 FIFO，只从两边操作 (back 进 front 出) 的受限数据类型。

    接口：enqueue()、dequeue()、isEmpty()、getFront()

    链队列：类似于链表，需要 (Node 和 Queue) 两个类。Queue 中 front 指向队头节点，back 指向队尾节点。与链表一样，旧元素指向新元素，从队头指向队尾。

    循环数组队列：利用 Circular-Array 首位衔接弥补数组难以整体移动。在插/删时无需整体移动同时做到防止超出索引。(1) 一种实现方式只能用数组大小 const MAX -1，front 索引队首，back 索引队尾的下一位。⚠️核心：enqueue 时先插入然后后移 back ( back = (back+1)%MAX;)，dequeue 时 front = (front+1)%MAX;，用求余把超出索引的位置绕回数组开头。⚠️限制条件：要入队不能满 if(!(back+1)&MAX == front)，要出队不能空 if(front != back)。永远有一位填不了，这个代价换来可以简单判断满/空的语句。(2) 另一种实现方式虽可以填满 MAX 位，但是要用一个全局变量来计数 (用填了多少位判断满/空)


  • 映射(字典) Map 存储 键值对 struct KeyValuePair {T1 key, T2 value};，key 用作索引故不可重复。轻量级的 map 可以用 (动态) 数组实现，用 map[index].key 形式访问键。

    哈希表 HashMap：比如 std::unordered_map，利用哈希函数将 key 映射到桶数组的索引，即：int BucketIdx = HashFunc(key) % Buckets.size();，良好的哈希函数尽量避免碰撞 (最好 key 对桶双射)，发生碰撞时用链表或数组将多个 KVP 挂在 Bucketa 数组中 (前者用桶数组存 Node，后者将桶数组做成二维数组)。无碰撞时除遍历全部 O(1)，KVP 全部碰撞到同个桶时哈希退化为链表，回到 O(n)。为避免退化，检测 KVP 数量与 Buckets 数量的比，过大时要 rehash (扩容Buckets 数组并重新计算哈希)。一般要求比例大约低于 0.7。


  • 集合 Set 无需不重复的数据集。可用 Hash、BST、链表等实现。

    Character Set(Bitset)：比如 std::bitset ，用二进制数表示某数据是否属于集合，一般用在连续的小集合上，如 ASCII 集合，0～1000整数集合。除遍历全部 O(1)。一种实现方式使用 unsigned long bSet[] 存储，(由于长整数大小有计算机多少 bit 决定，我们记作 bpL) 对于任意数 k，它存在第 k/bpL - 1 个元素的第 k%bpL 位。对 k 进行操作要用掩码 mask：return unsigned long(1) << k%bpL ⚠️因为位运算从右往左，1 等价于 000…01，所以是左移。取 k bSet[k/bpL] & mask；删 k bSet[k/bpL] &= ~mask。


  • 树 Tree 没有 cycle 或 loop (满足 |V|-1=|E|) 的简单有向且单向的平面图

    Root：没有父节点；leaf：没有子树；path：图中可行的通路；distance：路径上经过的边数；height：到最远叶子的距离 (空树高为 -1)；depth：到根的距离。BT：每个节点最多两个子树。Full BT：每个节点都有 0 或 2 个子节点的 BT；Complete BT：最后一层靠左排列其余层全满的 BT(Heap 就是一种 CBT)。

    函数 “order” 中，cout << p->data <<'\n'; 和 order (p->left); 和 order(p->right); 依次对应 “根”、“左”、“右”，以三种顺序排列这三个语句就形成了二叉树中的 preorder、 inorder 和 postorder。

    ⚠️对于 N 个节点，高为 h 的二叉树：节点最多 N ≤ 1x2x4x…2h = 2h+1-1，所以N∈[h+1, 2h+1-1]，反过来可以求出 h 的下限，h∈[⌈log2(N+1) - 1⌉, N-1]。


  • BST 二叉搜索树 满足对任意有左右子节点的节点 x， x->left->data < x->data; x->right->data < x->data; 的不重复的二叉树，其 inorder 是严格升序的。除遍历平均 O(logn)，退化为链表则全部 O(n)。

    接口：find()、findMin()、findMax()、insert()、remove()

    寻找 v 的函数从某处 x 开始递归，比右大就 find(x->right) 比左小就 find(x->left) 都不满足就比较 x 和 v，相等就返回其指针，不相等返回 nullptr。

    找最小项只需 从某处 x 开始一路往左递归到底 if(!x->left) {return x;} return findMin(x->left); 即可；找最大项则两处方向相反。

    插入 v 的函数 (不插重复值) 先类似于 find v，会遍历到某节点的左/右子节点是一个空节点，此时 new 一个叶节点即可。

    删除 v 的函数同样先 find v，找到 x 节点，如果 if(x->left && x->right) {} 有两个孩子，x->data = findMin(x->right)->data; remove(x->data, x->right); 就将中序后继值 (或前任值) 代替 x 的值并 递归删掉它，它作为右子树的最大值，必然是一个叶节点，套用一个孩子的情况就可以兼容：else {Node<t>* old = x; x = (x->left) ? t->left : t->right; delete old;} (左有节点就代替当前点，反之用右节点代替，没有节点相当于把当前节点悬空)



  1. Balanced BST

  • 用平衡条件让二叉搜索树不超过 logn 级别的高度，就不会退化。

  • AVL 要求任意节点的左右子树的高度差不超过 1，故而所有叶节点的深度波动不超出 ±1。这种情况下，随意 insert() 和 delete() 都有大概率破坏平衡。需要在节点类新增一个 height 变量和 height() 函数来记录和返回高度，LminusR() 来记录**平衡系数，如height(n->left) - height(n->right) ≤ ±1就正常，小于负一说明右子树过长，就需要重平衡**。

    ⚠️插/删会且只会影响当前节点到根的路径上的点的高度和平衡性！ 所以除了左右指针，我们还需要 parent 指针才能向上找问题。

    设想一个 reBalance 函数，在插/删之后原地调用，先更新当前点的高度，从这点开始往 parent 遍历到根：更新高度并检查每一个点的 LminusR()，出现的 ⚠️第一个失衡点处，如果 LminusR(n)>1，说明左树过长，检查 LminusR(n->left)，≥0 说明属于 LL 情况，右旋 n；<0 说明属于 LR 情况 先左旋 n->left 变成 LL 情况再右旋 n。反之 LminusR(n)<1 也一样分为 RR (左旋 n) 和 RL (右旋 n->right 变成 RR 再左旋 n) 两种情况。总体逻辑如下：

                                       / <-1(LR): node->left = lRotate(n->left);
             / >1:LminsR(n->left)〈              ↓ ↓ ↓ ↓ ↓(turns into LL)
            /                      \ ≥1(LL): return rRotate(n);
LminusR(n)〈                         / >1(RL): node->right = rRotate(n->right);
            \ <-1:LminusR(n->right)〈               ↓ ↓ ↓ ↓ ↓(turns into RR)
                                     \ ≤-1(RR): return lRotate(n);

    • 左旋就是 n 继承右子节点的左子树并成为右子节点的左子树 (继承为 n 的右子树)。相当于交换 n 和其右子节点，抬高了右子节点的右子树 (即所谓的 RR)

    • 右旋就是 n 继承左子节点的右子树并成为左子节点的右子树 (继承为 n 的左子树)。相当于交换 n 和其左子节点，抬高了左子节点的左子树 (即所谓的 LL)

    Node<T>* rRotate(Node<T> *n) {
	Node<T> *son = n->left, *rsT = son->right; 
	son->right = n;
	n->left = rsT; 
	n->height = height(n); son->height = height(son);
	return son;
}

    左右旋以及为何分一到两次旋转的意义不言而喻。


  • RBTree 红黑树 是 Stanford 研发的另一种平衡方式，目的相同，利用 enum COLOR {RED, BLACK};，所有新增节点初始化为红色。

    注意⚠️：红黑树中黑与空是等价的。红黑树中所谓的叶节点的概念与上文完全不同，现在叶代表 NIL(空占位节点)——任意节点如果没有左或右子节点就伸出 NIL，因为 黑 ≡ 空，NIL 都是黑的。

    红黑树的五大性质：node color: 所有节点非黑即红；root property：根永远黑；leaf property: 所有 NIL 都黑；red property: 不存在互为父子的红色节点；black property: 从任意节点到所有 NIL 的路径中经过的黑节点数量相等，称为 bh (black height)。

    ⚠️对于 N 个节点，高为 h 的红黑树：高度至少为 bh，所以N∈[2bh-1, 2h+1-1]，又因为 h ≤ 2 bh(最高也只能红黑相间)，可以得到 h∈[⌈log2(N+1) - 1⌉, ⌊2log2(N+1) - 1⌋]。很明显，相比二叉树，红黑树高度是有上限的，高度最多大约是 AVL 的 2 倍，无法退化到链表。

    红黑树也有一套类似 AVL 的重平衡机制，以下对于插入一个节点 node：

           / parent B/NIL：保证根 B，结束。
node 〈             / 叔 R：叔、父、祖父，颜色反转；并将祖父作为 node 递归；
       \ parent R 〈
                    \ 叔 B/NIL：回溯 node 的父、祖父：LR/RL双旋换色(后一次)；LL/RR单旋换色。

    父亲黑时没有问题，但如果这过节点本身是根，那就需要把它染黑来保证 black property。

    父亲红时必然会违反 red property，我们需要分的大情况是 “父亲是祖父的哪个孩子？” 在此之下讨论 uncle 的两种情况。

    • 其中 “父红叔黑” 的部分几乎与 AVL 是一样的，区别是**不需要往上找失衡点**，直接原地讨论：
    (Node<T>* gp  = node->parent->parent; Node<T>* p = node->parent;)                      
                                / 右子(LR): p = lRotate(p);
            / 左子，node 是 p 的〈            ↓ ↓ ↓ (turns into LL)
           /                    \ 左子(LL): rRotate(gp); 并换色
p 是 gp 的〈                    / 左子(RL): p = rRotate(p);
           \ 右子，node 是 p 的〈            ↓ ↓ ↓(turns into RR)
                               \ 右子(RR): lRotate(gp); 并换色
    • 另外一种 “父红叔红” 的部分，直接涂黑两者，把祖父涂红，这样问题就转嫁到祖父身上，将祖父作为 node 递归，我们总会遇到其它两种可解决的情况 (比如一路到节点，就属于 “父黑” 情况)

    删除的重平衡不完全相同，主要是 “double black” 思路。

    • 删红无所谓，如果删了黑节点，就会造成路径上黑节点缺少 1：用“这个位置是 double black”来表示；然后根据“兄弟节点的颜色、兄弟孩子的颜色”分类讨论

    • 兄弟为红：旋转父亲，交换父亲(B)和兄弟(R)，并把兄弟涂黑、父亲涂红。因为交换后的新兄弟节点是原本兄弟(R) 的子节点，一定黑或空，进入情况 (2)。

    • 兄弟为黑：兄弟孩子全黑或空：兄弟涂红，把 double black 上移；兄弟存在红孩子：类似于插入，根据这个红侄子与其父、祖父的关系的L/R 关系，旋转 1～2 次并调整颜色。



  1. Heap

  • 堆是 “按优先级处理元素” 的数据结构，所以又叫 Priority Queue。堆不同于 BST，它不把所有元素整体排序，但堆可以用 BST 实现。分为 MinHeap 和 MaxHeap，优先处理最小或最大项。依旧需要 left, right, parent (索引)，接口：insert()、push()、deleteMin() / deleteMax()。

  • 建立在 vector 基础上的二叉堆 Binary Heap 是最优解，插/删 O(log N)，findMin O(1)。二叉堆必须表现为一棵完全二叉树，并用动态数组形式存储 (⚠️不需要指针！)，二叉堆有两条性质：

    结构性：对于任意索引 i (⚠️存储在 vector 中，所以索引从 0 开始)，其父子节点可以直接计算：parent(i) = (i−1)/2；left(i) = 2i+1；right(i) = 2i+2，这样把二叉堆画成 二叉树后索引从左到右从上到下逐行增大，且为0～N 的连续整数表示。

    有序性 (heap-order property)：对 MinHeap，所有父节点小于子节点，MaxHeap 反之。堆只保证 “父子有序”，左右是无序的，故中序遍历不会得到升/降序列。

    ⚠️一棵高 h 的完全二叉树：N∈[2h, 2h+1-1]

    插入 v：先加入动态数组尾部 minH.push_back(v) 然后上滤 (siftUp)： std::swap(minHeap[idx], minHeap[parent(idx)]); idx = parent(idx); 也就是向 parent 方向反复交换直到 parent 小于自己。

    删除根 (deleteMin)：先用数组尾项代替根 minH[0] = minHeap.pop_back(); 然后下滤 (siftDown)：循环交换自己与左右孩子中较小的那个，直到左右孩子都比自己大。⚠️注意：每次交换先要确定左右孩子存在 left(idx) < size() 防止下标越界。

    buildHeap 建堆：先将元素写入动态数组 for (int i = 0; i < vec.size(); i++) {data_.push_back(vec[i]);}，然后从最后一个非叶节点开始下滤 for (int i = size() / 2 - 1; i >= 0; --i) {siftDown(i)} (数组末尾在 N-1，其父节点就在 N/2-1)。总共大约在O(N)。



  1. Graph

  • 树是没有循环的图，图是一种满足度数和为偶数的 G~(E, V) 结构。

    无向图有边的两点互成邻接，有向图 (digraph) 被指向的点邻接指向它的点。

    实现图可以用 adjacency list：每个顶点做一个数组/链表，再把顶点做成桶数组 (Map)，遍历复杂度 O(|V|+|E|)；也可以用 adjacnecy matrix：用 |V|x|V| 的二维数组 [i][j] 表示 i 到 j 有边，无向图是对角对称的，遍历复杂度 O(|V|2)。

    DFS：用 stack/递归 先走一条路径到底，然后回溯访问其他路径。思路类似于没有左右的 preorder

    BFS：用 queue 依次走距离近到远的点。

    最短路径问题：无权时用 BFS 遍历记下到根的层数；有权需要用 Dijkstra 算法：从 r 开始，对当前点所有相邻点，如果当前点到 r 的距离+边权重比记录值更小，就更新距离，如此多轮。

    Tropological Sorting： 对 DAG (有权无环图)，如果 (u, v) 有边，先访问 u (先访问所有前序点)。

comments powered by Disqus