1.1 下面代码中有问题的是哪个？

A.  char* const p;
B.  char const *p;
C.  const char *p;
D.  const *char p;

1.2 下面哪一项定义一个返回值为int，参数为char*的函数指针

A. *foo int (char*)
B. typedef int (*foo) (char*)
C. int (*foo) (char*)
D. typedef int (*) (char*) foo

1.3 现有如下函数

1:  int foo(int a, int b)
2:  {
3:     return a + b;
4:  }

A. 4
B. 10
C. 7
D. 6 

1.4 下面的代码输出是什么？

1:  #include <stdio.h>
2:  int main()
3:  {
4:      unsigned int a = 6;
5:      int b = -20;
6:      (a+b > 6)? puts("> 6"): puts("<= 6");

7:      return 0;
8:  }

A.  > 6
B.  < 6
C.  >= 6
D.  <= 6

1.5 malloc()申请内存处于

A. 静态存储区
B. 栈 (stack)
C. 堆 (heap)
D. 代码区 (text)

2.1 请讲一下你对头文件的理解，头文件里面应该都放些什么。

2.2 设有

int var1;
double var2;

2.3 在 32 位的操作系统下，请计算以下的 sizeof，并解释一下原因

1:  int f(char str[100])
2:  {
3:      return sizeof(str); // = ?
4:  } 

1:  char *str = (char*)malloc(100);    
2:  sizeof(str); // = ?
3:  sizeof(*str); // = ?

1:  char str[100];
2:  sizeof(str); // = ?

3.1 阅读下面的程序

1:  void test1()
2:  {
3:      char string[10];
4:      char* str1 = "0123456789";
5:      strcpy( string, str1 );

6:  } 

1:  char* strcpy(char *dest, const char *src);

3.2 阅读下面程序

1:  void foo(int *a, int *b)
2:  {
3:      *a = *a + *b;
4:      *b = *a - *b;

5:      *a = *a - *b;
6:  }

3.3 请写出以下程序片段的输出

 1:  #include <iostream>

 2:  using namespace std;
 3:  
 4:  class Base {
 5:  public:
 6:      void printA()
 7:      {

 8:          cout << "Base printA." << endl;
 9:      }
10:      virtual void printB()
11:      {

12:          cout << "Base printB." << endl;
13:      }
14:  };
15:  
16:  class Derived : public Base{
17:  public:

18:      void printA()
19:      {
20:          cout << "Derived printA." << endl;
21:      }
22:      virtual void printB()

23:      {
24:          cout << "Derived printB." << endl;
25:      }
26:  };
27:  

28:  int main()
29:  {
30:      Base *p_1 = new Base();
31:      Derived *p_2 = new Derived();
32:      Base *p_3 = new Derived();
33:  
34:      p_1->printA();

35:      p_2->printA();
36:      p_3->printA();
37:      cout << endl;
38:  
39:      p_1->printB();

40:      p_2->printB();
41:      p_3->printB();
42:      return 0;
43:  }
44:  

4.1 写一个函数实现字符串的左循环

void leftRotate(char *str, int n);

例如：

leftRotate("abcdefg", 3); "abcdefg" => "defgabc"

本题没有要求时间和空间复杂度，很多同学都是用了新开辟的一个同样大小的数组再复制，其实可以实现O（n）的时间，O（1）的空间

 1:  #include <stdio.h>
 2:  #include <string.h>
 3:  #include <math.h>

 4:  
 5:  void leftRotate(char *str, int n)
 6:  {
 7:      int length = strlen(str),
 8:          current = 0,

 9:          next = 0,
10:          floorNum = 0;
11:  
12:      char temp = str[0];
13:      for (int i = 0; i != length - 1; ++i){
14:          next = (current + n) % length;

15:  
16:  //      floorNum = floor(double(current + n) / length);
17:  //      next = (current + n) - length * floorNum;
18:  
19:          str[current] = str[next];
20:          current = next;
21:      }

22:      str[current] = temp;
23:  }
24:  
25:  int main()
26:  {
27:      char str[] = "abcdefg";
28:      leftRotate(str, 2);

29:      puts(str);
30:      return 0;
31:  }

• 如果想要实现参数为负数的时候会造成右旋。

  就把 for 语句中第一句注释掉

  把原来注释的两行恢复

  • 下面讲解

  例如： abcdefg 左旋 2 变成 cdefgab

  	0	1	2	3	4	5	6
  src	a	b	c	d	e	f	g
  dest	c	d	e	f	g	a	b

  • 发现有如下替换

  dest[0] = src[2]
  dest[1] = src[3]
  dest[2] = src[4]
  ...
  dest[x] = src[y]

  x 与 y 的关系就是

  y = (x + 2) % length

  也就是

  y = (x + n) % length

  但是按照这样的顺序赋值会 丢失信息

  如第一句就丢失 dest[0 ] 的内容

  所以调整复制的顺序

int temp =  dest[0];
dest[0] = src[2]
dest[2] = src[4]
dest[4] = src[6]
dest[6] = src[1]
dest[1] = src[3]
dest[3] = src[5]
// 上面赋值了 length - 1 次，于是最后
dest[5] = temp

• 上面程序中的 x, y 就是最终程序中的　current, next

  • 下面附加讨论当 n 为负数的时候变成右旋。
  • 先扩展一下有关于负数除法的小知识

    -1 / 5 = ?

    计算机程序在计算带有负数的正数除法的时候有两种结果

    首先除出小数 -0.2

    这时 如果答案为向 0 趋近的整数就叫做 truncate 除 （结果为 0 ）

    如果答案为向 负无穷 趋近的整数就叫做 floor 除 （结果为 -1）

    除法结果不同导致取余结果也不同，利用下面式子推余数

    a / b = x —— y

    a = b * x + y

    c++ 平台相关，但实际实验之后得到为 truncate 除

    数学的模运算，python 使用 floor 除

  • 返回题目

    我们期望的结果是

  例如： abcdefg 左旋 -2 变成 fgabcde

  	0	1	2	3	4	5	6
  src	a	b	c	d	e	f	g
  dest	f	g	a	b	c	d	e

  即

int temp =  dest[1];
dest[0] = src[5]
dest[5] = src[3]
dest[3] = src[1]
dest[1] = src[6]
dest[6] = src[4]
dest[4] = src[2]
// 上面赋值了 length - 1 次，于是最后
dest[2] = temp

• 同样是上面的赋值，同样是

  y = (x + n) % length

  就看第一项，若直接使用 c++ 的 truncate 除

  则 y = (0 - 2) / 7 = 0 —— -2

  但如果是 floor 除就刚好可以得出需要的结果

  y = (0 - 2) % 7 = -1 —— 5

  再看一下原来注释的代码就知道了 其实是在模拟 floor 除的方法 …

4.2 给定单链表如下

1:  typedef struct Node Node;
2:  struct Node{
3:      int data;
4:      Node *next;
5:  };
6:  Node *head;

• answers 1
  • 可以采用龟兔赛跑的方法，定义快指针与慢指针，每次循环块指针走两步，慢指针走一 步。如果两指针相遇则是有环，如果快指针到达了链表尾，则说明没有环。

bool HasCycle(List list) {
  // 用快的迭代器去“追”慢的迭代器
  if (!list->head)
	return false;
  Link slow = list->head, fast = list->head->next;
  while (fast && fast->next) { // 到头了，没环路
    if (fast == slow || fast->next == slow)
      return true;  // “追”上了，有环路
    slow = slow->next;
    fast = fast->next->next;
  }
  return false;
}

• answers ２
  • 下面的讨论与本次考试题目无关，只是我的一点心得
  • 如果链表想要很好的析构掉，必须要得到是否是环的信息，如果是环还必须 要知道节点在哪里才可以，不然删除到尾巴时会造成删除已经删除过的节点。
  • 所以问题变得更加复杂，即需要找到交点的位置。请参考下图

    

    假设链表进入环之前的长度为 x ，环本身的长度为 y 。假设交点为 A ，快慢点相 遇点为 B 。

  • 先讲一下大概方法，同样是两个节点一块一慢，相遇到 B 之后，就把一个节点放到 链表首，然后两个节点同时一次走一步，最后两个节点相遇之时就是节点 A 。
  • 下面进行证明
    • 慢点无法在环内绕圈

      即使极限情况，慢点与快点在环内一开始处于重合状态，即快点需要追一整个圈才 能追上慢点，快点也可以在慢点刚好走完一圈的时候追上。

    • 设慢点走了 x + m

      则快点走了 2 * (x + m) = x + m + k * y （k 为快点在相遇之前在环内转的圈 数）

      可以推出 m + x = k * y

    • 后来把一点放回起始点之后就同步前进，这意味着两点所走路程之差始终是 m + x 即 k * y 。所以当放回起点的点到达 A 时，必然另一点也到达 A 。

5.1 请说出你看过的技术相关书籍名称，以及看完之后的感想。

5.2 请说出 linux 的根目录底下文件有哪些，你知道的 linux 发行版名称。

5.3 随便说说你将来的理想，打算搞哪方面的技术，如果加入 c++ 小组，最希望学到的知识？