宝典——数据结构和设计模式

数组方式:

当i=1时， f(m,k,i)=(m+k−1)

当i!=1时，f(m,k,i)=(f(m−1,k,i−1)+k)

链表方式：

假设两个栈a和b，且都为空。栈a提供<code>push()</code>功能，栈b提供<code>pop()</code>功能。

入队列：入栈a。- 出队列：

如果栈b不为空，直接弹出b的元素。

如果栈b为空，则依次弹出栈a的元素并压入栈b中，再弹出b中的元素。

经常需要操作的内存可分为以下几个类别：

栈区：由编译器自动分配和释放，存放函数的参数值、局部变量的值等。

堆区：一般由程序员分配和释放，若程序员不释放，程序结束时可能由操作系统回收。（它与数据结构中的堆是两回事，分配方式类似于链表）

全局区（静态区）：全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域，未初始化的全局变量和未初始化的静态变量在相邻的另一块区域，程序结束后由系统释放。

文字常量区：常量字符串就是放在这里的。

程序代码区：存放函数体的二进制代码。

heap是堆，stack是栈。

stack的空间由操作系统自动分配/释放，heap上的空间手动分配/释放。

stack的空间有限，heap有很大的自由存储区。

c中的malloc函数分配的内存空间即在堆上，c++对应的new操作符。

程序在编译期对变量和函数分配内存都是在栈上进行，且程序运行过程中函数调用时参数的传递也在栈上进行。

stack的存取效率较快。

stack申请效率比较快，heap比较慢，而且容易产生碎片，不过用起来方便。

4∗n−(n−1)=3n+1

排序是否稳定：待排序文件中，具有相同关键字的记录，经过排序后记录之间的相对次序是否保持不变。

内部排序：整个文件都是放在内存中处理，排序时不涉及数据的内、外存交换。

外部排序：排序过程中要涉及内、外存交换。

分治法：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归的解决这些子问题，然后将这些子问题的解组合为原问题的解。

去掉不必要的安全检查，可以提高性能。

使用<code>strncpy()</code>需要手动在最后加上<code>'\0'</code>。

输出为：123456789, 5789

如果交换d和s的定义顺序，则输出结果为123456789, 123456789

指在程序的执行过程中动态的分配或者回收存储空间的内存分配方法。相对于静态内存分配的特点：

1. 不需要预先分配存储空间

2. 分配的空间可以根据程序的需要扩大和缩小

void *malloc(unsigned int size);

void free(void *p);

代码1：

代码2：

代码3：

自动化测试可以让测试人员从枯燥无味的手工重复性测试中解放出来，并且提高工作效率，通过自动化测试结果来分析功能和性能上的缺陷。

一个测试结束的标准可以查看已提交的bug是否已经全部解决并已验证关闭，一般来说，bug验证率在95%以上，并且没有大的影响功能的bug处于未解决状态，就可以测试通过。

在一个测试计划中可以包含需要测试的产品的特点和主要功能模块，列出需要测试的功能点，并标明侧重点；测试的策略和记录（测试工具的确认，测试用例等文档模板，测试方法的确定）；测试资源配置（确定测试每一阶段的任务和所需资源）。

功能测试主要是黑盒测试，由测试人员进行，主要验证产品是否符合需求设计的要求；可用性测试主要是由用户（或者测试人员模拟用户行为）来进行的测试，主要是对产品的易用性进行测试，包括有效性（effectiveness）、效率（efficiency）和用户主观满意度（satisfication）。其中有效性指用户完成特定任务和达到特定目标时所具有的正确和完整程度；效率指用户完成任务的正确和完整程度与所使用资源（如时间）之间的比率；满意度指用户在使用产品过程中所感受到的主观满意和接受程度。

白盒测试有几种测试方法：条件覆盖、路径覆盖、语句覆盖、分支覆盖。其中分支覆盖又称判定覆盖，使得程序中每个判断的取真分支和取假分支至少经历一次，即判断的真假均曾被满足。