数据结构和设计模式
数据结构
1 约瑟夫环
数组方式:
当i=1时， f(m,k,i)=(m+k−1)
当i!=1时，f(m,k,i)=(f(m−1,k,i−1)+k)
int fun(int m, int k, int i);
int main()
{
for (int i = 1; i <= 10; i++)
{
cout<<fun(10, 3, i)<<" "; // 输出数值为[0,9]
//cout<<fun(10, 3, i) + 1<<" "; // 输出数值为[1,10]
}
}
int fun(int m, int k, int i)
{
if (i == 1)
{
return (m + k - 1) % m;
}
else
{
return (fun(m - 1, k, i - 1) + k) % m;
}
}
链表方式：
struct ListNode
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Josephus
{
public:
Josephus(int x)
{
n = x;
head = new ListNode(1);
ListNode *pre = head;
ListNode *cur;
for (int i = 2; i <= x; i++)
{
cur = new ListNode(i);
pre->next = cur;
pre = cur;
}
cur->next = head;
}
void performKilling(int d)
{
d %= n;
int count = 1;
ListNode *pre;
ListNode *cur = head;
while (count++ <= n) //while (cur->next != cur)
{
for (int i = 1; i < d; i++)
{
pre = cur;
cur = cur->next;
}
cout<<cur->val<<" ";
pre->next = cur->next;
delete cur;
cur = pre->next;
}
//cout<<cur->val;//delete cur;
}
private:
ListNode *head;
int n; //size of the linked list
};
int main()
{
Josephus *J = new Josephus(10);
J->performKilling(3);
}2 用两个栈实现一个队列的功能
假设两个栈A和B，且都为空。栈A提供push()功能，栈B提供pop()功能。
- 入队列：入栈A。- 出队列：
- 如果栈B不为空，直接弹出B的元素。
- 如果栈B为空，则依次弹出栈A的元素并压入栈B中，再弹出B中的元素。
3 heap和stack的区别
经常需要操作的内存可分为以下几个类别：
- 栈区：由编译器自动分配和释放，存放函数的参数值、局部变量的值等。
- 堆区：一般由程序员分配和释放，若程序员不释放，程序结束时可能由操作系统回收。（它与数据结构中的堆是两回事，分配方式类似于链表）
- 全局区（静态区）：全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域，未初始化的全局变量和未初始化的静态变量在相邻的另一块区域，程序结束后由系统释放。
- 文字常量区：常量字符串就是放在这里的。
- 程序代码区：存放函数体的二进制代码。
heap是堆，stack是栈。
stack的空间由操作系统自动分配/释放，heap上的空间手动分配/释放。
stack的空间有限，heap有很大的自由存储区。
C中的malloc函数分配的内存空间即在堆上，C++对应的new操作符。
程序在编译期对变量和函数分配内存都是在栈上进行，且程序运行过程中函数调用时参数的传递也在栈上进行。
stack的存取效率较快。
stack申请效率比较快，heap比较慢，而且容易产生碎片，不过用起来方便。
4 搜索引擎输入某个词时出来搜索建议，后台采用的数据结构是Trie树（字典树）。
5 一个包含n个节点的四叉树，每一个节点都有4个指向孩子节点的指针，这个四叉树有_____个空指针。
4∗n−(n−1)=3n+1
6 相关概念
排序是否稳定：待排序文件中，具有相同关键字的记录，经过排序后记录之间的相对次序是否保持不变。
内部排序：整个文件都是放在内存中处理，排序时不涉及数据的内、外存交换。
外部排序：排序过程中要涉及内、外存交换。
分治法：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归的解决这些子问题，然后将这些子问题的解组合为原问题的解。
字符串
1 整数转化为字符串，并且不使用itoa
#include <iostream>
#include <cstring>
using namespace std;
void reverse(char *ch)
{
char *p = ch;
char *q = ch + strlen(ch) - 1;
while (p < q)
{
char c = *p;
*p++ = *q;
*q-- = c;
}
}
//没有考虑非法输入
void itoa(int n, char *ch)
{
char *temp = ch;
bool minus = false;
if (n < 0)
{
n = -n;
minus = true;
}
if (n == 0)
{
*ch++ = '0';
*ch = '\0';
return;
}
while(n)
{
*temp++ = n % 10 + '0';
n /= 10;
}
if (minus)
{
*temp++ = '-';
}
*temp = '\0';
reverse(ch);
}
int main()
{
char ch[20] = {0};
itoa(-12035, ch);
cout<<ch<<endl;
}2 字符串转化为整数
#include <iostream>
#include <cassert>
using namespace std;
//没有考虑非法输入
int atoi(const char *ch)
{
assert(ch != NULL);
int flag = 1;
if (*ch == '-')
{
flag = -1;
ch++;
}
else if (*ch == '+')
{
ch++;
}
int num = 0;
while (*ch != '\0')
{
num = num * 10 + *ch++ - '0';
}
return num * flag;
}
int main()
{
int n = atoi("-123450");
cout<<n<<endl;
}3 strcpy()
去掉不必要的安全检查，可以提高性能。
使用strncpy()需要手动在最后加上'\0'。
#include <iostream>
#include <cassert>
using namespace std;
char* strcpy(char *strDest, const char *strSrc)
{
assert((strDest != NULL) && (strSrc != NULL));
char *temp = strDest;
while ((*strDest++ = *strSrc++) != '\0');
return temp;
}
char* strncpy(char *dest, const char *src, int n)
{
assert(dest != NULL && src != NULL);
char *temp = dest;
while (n != 0 && (*dest++ = *src++) != '\0')
{
n--;
}
while (n != 0)
{
*dest++ = '\0';
n--;
}
return temp;
}
int main()
{
char ch1[20] = "123456789";
char ch2[20];
char *ch = strncpy(ch2, ch1, 30);
cout<<ch<<endl;
}4 程序输出结果
int main()
{
char d[] = "123";
char s[] = "123456789";
strcpy(d, s);
cout<<d<<endl;
cout<<s<<endl;
}输出为：123456789, 5789
如果交换d和s的定义顺序，则输出结果为123456789, 123456789
5 动态内存分配
指在程序的执行过程中动态的分配或者回收存储空间的内存分配方法。相对于静态内存分配的特点：
1. 不需要预先分配存储空间
2. 分配的空间可以根据程序的需要扩大和缩小
void *malloc(unsigned int size);
void free(void *p);
6 把一个字符串循环向右移n位
代码1：
void loopMove(char *str, int step)
{
int len = strlen(str);
step %= len;
char *ch = new char[len + 1];
strcpy(ch, str);
for (int i = 0; i < len; i++)
{
str[i] = ch[(i - step + len) % len];
}
}代码2：
void loopMove(char *str, int step)
{
int len = strlen(str);
step %= len;
char *ch = new char[len + 1];
strcpy(ch, str + len - step);
strcpy(ch + step, str);
*(ch + strlen(str)) = '\0';
strcpy(str, ch);
}代码3：
void loopMove(char *str, int step)
{
int len = strlen(str);
step %= len;
char *ch = new char[len + 1];
memcpy(ch, str + len - step, step);
memcpy(ch + step, str, len - step);
memcpy(str, ch, strlen(ch));
}7 标准输入输出通道包括cin, cout, cerr，对应于彪悍尊输入流，标准输出流，标准错误流。
8 输入一行字符串，找出其中出现的相同且长度最长的字符串，输出它及其首字符的位置。例如，“yyabcdabjcabceg”，输出结果为abc和3.
#include <iostream>
#include <cstring>
#include <utility>
#include <string>
#include <vector>
using namespace std;
vector<pair<int, string>> fun(const string& str)
{
vector<string> subs;
vector<pair<int, string>> res;
int len = str.size();
for (int i = 0; i < len; i++)
{
subs.push_back(str.substr(i));
}
int count = 1;
int index = -1;
int subLen = 1;
string sub;
//i为子串的长度
for (int i = 1; i < len; i++)
{
for (int j = 0; j < len - 1; j++)
{
count = 1;
for (int k = j + 1; k < len && subs[k].size() >= i; k++)
{
if (subs[k].substr(0, i) == subs[j].substr(0, i))
{
count++;
break;
}
}
if (count >= 2)
{
if (i > subLen)
{
res.clear();
}
subLen = i;
index = j;
sub = subs[j].substr(0, i);
res.push_back(make_pair(j, sub));
}
}
}
return res;
}
int main()
{
string str;
vector<pair<int, string>> res;
while (cin>>str)
{
res = fun(str);
for (auto it = res.begin(); it != res.end(); it++)
{
cout<<it->second<<":"<<it->first<<endl;
}
}
return 0;
}9 strstr(),返回值是主字符串中字符子串的位置以后的所有字符。（不能使用任何C程序已有的函数）
#include <iostream>
using namespace std;
const char* strstr1(const char *str, const char *charset)
{
for (int i = 0; str[i] != '\0'; i++)
{
int j = i;
int k = 0;
while (str[j++] == charset[k++])
{
if (charset[k] == '\0')
{
return &str[i];
}
}
}
return NULL;
}
int main()
{
char *str = "123456123";
char *charset = "23";
cout<<strstr1(str, charset)<<endl;
return 0;
}10 将一句话里面的单词进行倒置，标点符号不倒换。例如“i come from tianjian.”变成“tianjin. from come i”。
#include <iostream>
#include <cstring>
using namespace std;
void reverse(char *str, int left, int right)
{
while (left < right)
{
char c = str[left];
str[left++] = str[right];
str[right--] = c;
}
}
int main()
{
char str[100];
while (cin.getline(str, 100))
{
reverse(str, 0, strlen(str) - 1);
int left = 0;
for (int i = 0; i <= strlen(str); i++)
{
if (str[i] == ' ' || str[i] == '\0')
{
reverse(str, left, i - 1);
left = i + 1;
}
}
cout<<str<<endl;
}
return 0;
}11 统计0到n之间1的个数
#include <iostream>
#include <cstring>
using namespace std;
int countOne(int n)
{
int current = 0;
int before = 0;
int after = 0;
int i = 1;
int count = 0;
while (n / i != 0)
{
current = n / i % 10;
before = n / (i * 10);
after = n - (n / i) * i;
if (current > 1)
{
count += (before + 1) * i;
}
else if (current == 0)
{
count += before * i;
}
else if (current == 1)
{
count += before * i + after + 1;
}
i *= 10;
}
return count;
}
int main()
{
int n;
while (cin>>n)
{
cout<<countOne(n)<<endl;
}
return 0;
}12 压缩字符串1233422222转化为1121324125.
#include <iostream>
#include <string>
using namespace std;
int main()
{
string str;
while(getline(cin, str))
{
char c = str[0];
int count = 1;
string temp = "";
for (int i = 1; i <= str.size(); i++)
{
if (str[i] != c || i == str.size())
{
temp += c;
temp += count + '0';
c = str[i];
count = 1;
}
else
{
count++;
}
}
cout<<temp.c_str()<<endl;
}
return 0;
}设计模式与软件测试
1 自动化测试为何重要？
自动化测试可以让测试人员从枯燥无味的手工重复性测试中解放出来，并且提高工作效率，通过自动化测试结果来分析功能和性能上的缺陷。
2 描述一个测试结束的准则
一个测试结束的标准可以查看已提交的bug是否已经全部解决并已验证关闭，一般来说，bug验证率在95%以上，并且没有大的影响功能的bug处于未解决状态，就可以测试通过。
3 在一个测试计划中能包含哪些内容（如可用的人力资源）？
在一个测试计划中可以包含需要测试的产品的特点和主要功能模块，列出需要测试的功能点，并标明侧重点；测试的策略和记录（测试工具的确认，测试用例等文档模板，测试方法的确定）；测试资源配置（确定测试每一阶段的任务和所需资源）。
4 请描述功能性测试和可用性测试之间的区别。
功能测试主要是黑盒测试，由测试人员进行，主要验证产品是否符合需求设计的要求；可用性测试主要是由用户（或者测试人员模拟用户行为）来进行的测试，主要是对产品的易用性进行测试，包括有效性（effectiveness）、效率（efficiency）和用户主观满意度（satisfication）。其中有效性指用户完成特定任务和达到特定目标时所具有的正确和完整程度；效率指用户完成任务的正确和完整程度与所使用资源（如时间）之间的比率；满意度指用户在使用产品过程中所感受到的主观满意和接受程度。
5 白盒测试
白盒测试有几种测试方法：条件覆盖、路径覆盖、语句覆盖、分支覆盖。其中分支覆盖又称判定覆盖，使得程序中每个判断的取真分支和取假分支至少经历一次，即判断的真假均曾被满足。
