程序员_软考专用复习资料

### 基础知识点 #### 排序 - **冒泡排序**：两两比较相邻元素，如果前一个比后一个大就交换位置，直到没有更大的元素为止。 - **选择排序**：每次从未排序的部分选出最小（或最大）的一个元素，存放到序列的起始位置。 - **插入排序**：将一个记录插入到已排序好的有序表中，从而得到一个新的、记录增1的有序表。 - **希尔排序**：属于插入排序的一种，是将原始待排序的记录分割成多个小组进行插入排序，这些小组是根据一定增量k构成的。 - **快速排序**：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序。 - **堆排序**：利用堆这种数据结构所设计的一种排序算法，分为建堆和排序两个过程。 - **归并排序**：将两个（或两个以上）有序表合并成一个新的有序表。 - **基数排序**：通过键值的各个位上的值来处理数据，可以看作是桶排序的一种扩展。 - **稳定性**：排序算法中的“稳定”是指如果存在两个相同的元素，经过排序之后这两个元素的前后顺序保持不变，则称该排序算法是稳定的。例如，插入排序和归并排序是稳定的，而快速排序和堆排序则不是。 - **快速排序算法**：基于分治思想，选择一个基准元素，通过一趟排序将数据分成两部分，使得左边的数据都小于基准，右边的数据都大于基准，再递归地对左右两边的数据进行快速排序。 #### 查找 - **哈希查找**：基于关键字值与哈希地址的转换而进行的查找，关键是构造哈希函数。 - **二叉树查找**：在二叉搜索树中查找，通常的时间复杂度为O(log n)。 - **折半查找**：也称为二分查找，要求数组是有序的，每次比较中间元素，缩小查找范围直至找到目标或范围为空。 - **哈希映射和哈希表的区别**：哈希表是一种数据结构，用于存储键值对；哈希映射是一种抽象概念，描述了如何将键映射到哈希表的索引上。 #### 链表和数组 - **链表**：每个元素由数据和指向下一个元素的指针组成，适合频繁插入和删除操作。 - **数组**：一组相同类型的数据集合，通过索引访问元素，适合随机访问。 #### 栈和队列 - **栈**：先进后出（FILO）的数据结构，主要操作是压栈和弹栈。 - **队列**：先进先出（FIFO）的数据结构，主要操作是入队和出队。 #### 多态 - **多态**：允许子类对象对父类对象进行替换而不会出现任何错误或异常，通常通过虚函数实现。 - **重载（Overload）**：同一个类中，方法名相同但参数列表不同的多个方法。 - **覆盖（Override）**：子类重写父类的方法，方法签名完全一致。 #### 字符串操作 - **strcpy**：复制源字符串到目的字符串，不包括'\0'。 - **memcpy**：复制n个字节的内存块，可用于字符串也可以用于其他数据类型。 #### 继承 - **继承**：子类继承父类的属性和方法，支持代码复用。 - **多继承**：一个子类可以继承多个父类的特性。 #### 面向对象的优势 - **封装**：隐藏对象的内部细节，只暴露必要的接口。 - **继承**：实现代码复用。 - **多态**：提高程序的灵活性和可扩展性。 #### static关键字 - **静态变量**：生命周期与程序相同，即使对象销毁，静态变量仍然存在。 - **静态成员函数**：不属于特定的对象，可以通过类名直接调用。 - **静态局部变量**：定义在函数内部，但作用域仅限于定义它的函数，且生命周期与程序相同。 #### 虚函数、纯虚函数、虚析构函数 - **虚函数**：实现多态的基础，允许派生类重写基类的方法。 - **纯虚函数**：只有声明没有定义的虚函数，必须在派生类中实现。 - **虚析构函数**：确保对象通过基类指针删除时，能够正确执行派生类的析构函数。 #### 内存泄漏及解决方法 - **内存泄漏**：分配的内存没有被释放，导致程序运行过程中可用内存逐渐减少。 - **解决方法**：手动管理内存（如使用智能指针），或者使用自动垃圾回收机制（如Java）。 ### 网络部分 #### OSI模型与TCP/IP模型 - **OSI模型**：开放系统互连参考模型，分为七层，自底向上分别为物理层、数据链路层、网络层、传输层、会话层、表示层和应用层。 - **TCP/IP模型**：传输控制协议/互联网协议，分为四层，分别是网络接口层、网际层、传输层和应用层。 #### TCP与UDP - **TCP**：传输控制协议，提供面向连接的服务，可靠传输。 - **UDP**：用户数据报协议，无连接服务，不保证数据可靠传输，但速度快。 #### TCP建立连接 - **三次握手**：客户端发送SYN包到服务器，并进入SYN_SEND状态；服务器收到SYN包后发送ACK+SYN确认包；客户端收到服务器的SYN+ACK包后发送ACK包确认。 #### 香农定理 - 描述了在有随机噪声的信道上传输数据的最大速率与信道带宽和信号噪声比的关系。 ### 二叉树的非递归遍历算法 #### 先序遍历 ```c void PreOrderUnrec(Bitree t) { SqStack s; StackInit(s); Bitree p = t; while (p != null || !StackEmpty(s)) { while (p != null) { visit(p->data); push(s, p); p = p->lchild; } if (!StackEmpty(s)) { p = pop(s); p = p->rchild; } } } ``` #### 中序遍历 ```c void InOrderUnrec(Bitree t) { SqStack s; StackInit(s); Bitree p = t; while (p != null || !StackEmpty(s)) { while (p != null) { push(s, p); p = p->lchild; } if (!StackEmpty(s)) { p = pop(s); visit(p->data); p = p->rchild; } } } ``` #### 后序遍历 ```c void PostOrderUnrec(Bitree t) { SqStack s; stacknode x; StackInit(s); Bitree p = t; do { while (p != null) { x.ptr = p; x.tag = L; push(s, x); p = p->lchild; } while (!StackEmpty(s) && s.Elem[s.top].tag == R) { x = pop(s); p = x.ptr; visit(p->data); } if (!StackEmpty(s)) { s.Elem[s.top].tag = R; p = s.Elem[s.top].ptr->rchild; } } while (!StackEmpty(s)); } ``` 以上介绍了软考中常见的知识点，涵盖了数据结构、算法、编程语言特性和网络基础知识等方面。