Interview--C Basic Problems

Posted on | In

C Language Classic Problems

最大公约数 最小公倍数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
int main(){
    int num1, num2;
    scanf("%d%d", &num1, &num2);
    int n = num1, m = num2, temp = 0;
    // make m < n
    if(m > n){
        temp = m;
        m = n;
        n= temp;
    }
    while(m != 0){
        temp = n % m;
        n = m;
        m = temp;
    }
    printf("最大公约数:%d\n", n);
    printf("最小公倍数:%d", num1 * num2 / n);
}

递归方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
int GCD(int m, int n){
    if(m % n == 0)
        return n;
    else return GCD(n, m%n);
}
int main(){
    int m,n,temp;
    printf("Please input m and n\n");
    scanf("%d %d", &m, &n);
    if(m < n){ // ensure m > n
        temp = m;
        m = n;
        n = temp;
    }
    printf("The greatest common divisor of (%d,%d) is %d\n", m, n, GCD(m,n));
    return 0;
}

isPrime

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
#include <stdbool.h>
bool is_prime(int n){
    int divisor;
    if(n <= 1)
        return false;
    for(divisor = 2; divisor * divisor <= n; divisor++)
        if(n % divisor == 0)
            return false;
    return true;
}
int main(void){
    int n;
    printf("Enter a number:");
    scanf("%d", &n);
    if(is_prime(n))
        printf("isPrime\n");
    else
        printf("notPrime\n");
    return 0;
}

quickSort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <stdio.h>
void swap(int *a, int *b){
    int t = *a;
    *a = *b;
    *b = t;
}
int partition(int arr[], int low, int high){
    int pivot = arr[high];
    int i = (low - 1);
    for(int j = low; j <= high - 1; j++){
        if(arr[j] < pivot){
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i+1], &arr[high]);
    return (i+1);
}
void quickSort(int arr[], int low, int high){
    if(low < high){
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi-1);
        quickSort(arr, pi+1, high);
    }
}
int main(){
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    quickSort(arr, 0, n-1);
    printf("Sorted array: ");
    for(int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

illustration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
arr[] = {10, 80, 30, 90, 40, 50, 70}
Indexes:  0   1   2   3   4   5   6 
low = 0, high =  6, pivot = arr[h] = 70
Initialize index of smaller element, i = -1
Traverse elements from j = low to high-1
j = 0 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 0 
arr[] = {10, 80, 30, 90, 40, 50, 70} // No change as i and j 
                                     // are same
j = 1 : Since arr[j] > pivot, do nothing
// No change in i and arr[]
j = 2 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 1
arr[] = {10, 30, 80, 90, 40, 50, 70} // We swap 80 and 30 
j = 3 : Since arr[j] > pivot, do nothing
// No change in i and arr[]
j = 4 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 2
arr[] = {10, 30, 40, 90, 80, 50, 70} // 80 and 40 Swapped
j = 5 : Since arr[j] <= pivot, do i++ and swap arr[i] with arr[j] 
i = 3 
arr[] = {10, 30, 40, 50, 80, 90, 70} // 90 and 50 Swapped 
We come out of loop because j is now equal to high-1.
Finally we place pivot at correct position by swapping
arr[i+1] and arr[high] (or pivot) 
arr[] = {10, 30, 40, 50, 70, 90, 80} // 80 and 70 Swapped 
Now 70 is at its correct place. All elements smaller than
70 are before it and all elements greater than 70 are after
it.

数组指针

有n个人围成一圈，顺序排号。从第一个人开始报数（从1到5报数），凡报到5的人退出圈子，后面的人接着从1报数，直到只剩最后一人，问最后留下的是原来第几号。提示：用数组实现，数组元素置为0表示该元素退出圈子。要求引入指针变量完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#define MAX 50
#include <stdio.h>
int main(){
    int i = 1, *p, k, m, n, num[MAX];
    scanf("%d", &n); // 共有多少人
    for(p = num; p < num+n; p++)
        *p = i++; //为每个人初始一个标号
    p = num;
    k = 0; // 报数
    m = 0; // 退出的人
    
    while(m < n-1){
        if(*p != 0)
            k++;
        if(k == 5){
            *p = 0;
            k = 0;
            m++;
        }
        p++;
        if(p == num+n)
            p = num;
    }
    for(p = num; p<num+n; p++)
        if(*p != 0)
            printf("%d is left\n", *p);
    return 0;
}

Armstrong数

一个n位数等于其个位数的n次方之和

Eg: $153 = 1^3+5^3+3^3$

找出2、3、4、5位的所有Armstrong数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdio.h>
#include <math.h>
int main(){
    printf("All 2 digit to 5 digit Armstrong integers are following:\n");
    
    for(int i=10; i<99999; i++){
        // 1.compute the length
        int temp = i, len=0;
        while(temp!=0){
            temp = temp/10;
            len++;
        }
        
        // 2.judge if armstrong integers
        int sum=0;
        temp = i;
        
        for(int j=0; j<len; j++){
            sum += (int)(pow(temp % 10, len));
            temp = temp/10;
        }
        if(sum == i)
            printf("%d\t", sum);
    }
}
#output:
153     370     371     407     1634    8208    9474    54748   92727   93084

3个等比数1：2：3

将1~9共9个数分成3组，组成3个3位数，且使着3个数字构成1：2：3的比例

Eg: 192: 384: 576

求出所有满足条件的3个3位数

如何验证3个3位数为不同的数字：1~9

solution：9个数字之和为45，之积为362880

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
int main(){
    for(int i = 123; i < 329; i++){
        int j = i * 2;
        int k = i * 3;
        
        char buf[10];
        sprintf(buf, "%d%d%d", i, j, k);
        int timeRes = 1, addRes =  0;
        for(int m = 0; m < 9; m++){
            timeRes *= buf[m] - '0';
            addRes += buf[m] - '0';
        }
        if(timeRes == 362880 && addRes == 45)
            printf("%d, %d, %d\n", i, j, k);
    }
    return 0;
}

和尚挑水

寺里有7个和尚：轮流挑水，为了和其他任务不冲突，个人将有空天数列出，如下表：

和尚1：星期二、四

和尚2：星期一、六

和尚3：星期三、日

和尚4：星期五

和尚5：星期一、四、六

和尚6：星期二、五

和尚7：星期三、六、日

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <stdio.h>
struct st{
    int spare[8];
    int flag;
}monk[8];
int x[8], sum = 0; //共有多少种方案
// n -- days
// j -- monk travese
// x[j] -- monk
void findDays(int n){
    if(n > 7){
        sum++;
        printf("Solution %d:\n", sum);
        for(int j = 1; j <= 7; j++)
            printf("星期%d 和尚%d 挑水\n", j, x[j]);
        printf("\n");
    }else{
        for(int j = 1; j <= 7; j++){
            x[n] = j;
            if(monk[j].flag == 0 && monk[j].spare[n] == 1){
                monk[j].flag = 1;
                findDays(n+1);
                monk[j].flag = 0;
            }
        }
    }
}
int main(){
    for(int i = 1; i <= 7; i++){
        printf("Please input the spare time of the monk %d:\n", i);
        for(int j = 1; j <= 7; j++){
            scanf("%d", &monk[i].spare[j]);
        }
        monk[i].flag = 0;
    }
    findDays(1);
    printf("There are %d solutions", sum);
}

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
Please input the spare time of the monk 1:                                                                           
0 1 0 1 0 0 0                                                                                                        
Please input the spare time of the monk 2:                                                                           
1 0 0 0 0 1 0                                                                                                        
Please input the spare time of the monk 3:                                                                           
0 0 1 0 0 0 1                                                                                                        
Please input the spare time of the monk 4:                                                                           
0 0 0 0 1 0 0                                                                                                        
Please input the spare time of the monk 5:                                                                           
1 0 0 1 0 1 0 
Please input the spare time of the monk 6:                                                                           
0 1 0 0 1 0 0                                                                                                        
Please input the spare time of the monk 7:                                                                           
0 0 1 0 0 1 1                                                                                                        
Solution 1:                                                                                                          
星期1 和尚2 挑水                                                                                                     
星期2 和尚6 挑水                                                                                                     
星期3 和尚3 挑水                                                                                                     
星期4 和尚1 挑水                                                                                                     
星期5 和尚4 挑水                                                                                                     
星期6 和尚5 挑水                                                                                                     
星期7 和尚7 挑水                                                                                                     
                                                                                                               
Solution 2:                                                                                                          
星期1 和尚2 挑水                                                                                                     
星期2 和尚6 挑水                                                                                                     
星期3 和尚7 挑水                                                                                                     
星期4 和尚1 挑水                                                                                                     
星期5 和尚4 挑水                                                                                                     
星期6 和尚5 挑水                                                                                                     
星期7 和尚3 挑水                                                                                                                     
Solution 3:                                                                                                          
星期1 和尚5 挑水                                                                                                     
星期2 和尚6 挑水                                                                                                     
星期3 和尚3 挑水                                                                                                     
星期4 和尚1 挑水                                                                                                     
星期5 和尚4 挑水                                                                                                     
星期6 和尚2 挑水                                                                                                     
星期7 和尚7 挑水                                                                                                     
Solution 4:                                                                                                          
星期1 和尚5 挑水                                                                                                     
星期2 和尚6 挑水                                                                                                     
星期3 和尚7 挑水                                                                                                     
星期4 和尚1 挑水                                                                                                     
星期5 和尚4 挑水                                                                                                     
星期6 和尚2 挑水                                                                                                     
星期7 和尚3 挑水                                                                                                                                                                  There are 4 solutions

递归法求解数组最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
int max(int a[], int n){
    if(n == 0)
        return a[n];
    else
        return (a[n] > max(a, n-1) ? a[n] : max(a, n-1));
}
int main(){
    int a[] = {1,2,3,4,8,6,7,6};
    printf("The max element is %d\n", max(a, 7)); // second argument: 7 length of the array--8
    return 0;
}

自然数的拆分

任何一个大于1的自然数N，总可以拆分成若干个自然数之和，并且有多种拆分方法

Eg: n=5

5=1+1+1+1+1

5=1+1+1+2

5=1+2+2

5=1+4

5=2+3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<stdio.h>
// x[n] used to store the solutions
int x[1024] = {0}, cnt = 0;
void split(int n, int m){
    int rest;
    for(int i = 1; i <= n; i++){
        if(i >= x[m-1]){ // i is larger than the prior one, not to be duplicate
            x[m] = i;
            rest = n - i;
        
            if(rest == 0 && m > 1){
                cnt ++;
                printf("%d\t", cnt);
                for(int j = 1; j < m; j++)
                    printf("%d+", x[j]);
                printf("%d\n", x[m]);
            }else{
                split(rest, m+1);
            }
            x[m] = 0;
        }
    }
}
int main(){
    int n;
    printf("Please enter the natural number:\n");
    scanf("%d", &n);
    split(n, 1);
    printf("There are %d ways to split the number %d\n", cnt, n);
    return 0;
}

（以下两道为2016 C 复试）

结构体存储学生信息

建立一个结构体包含学生信息（学号，成绩），使用结构体数组和结构体指针，输入200个学生信息，以成绩从低到高排序，输出最高成绩的学生的学号和成绩（最高成绩可能有多名学生）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>
typedef struct Student{
    int num;
    int score;
}Stu;
int main(){
    Stu stu[200], tmp, *p, *q, *k;
    for(int i = 0; i < 200; i++, p++)
        scanf("%d%d", &p->num, &p->score);
    p = stu;
    for(int i = 0; i < 199; i++, p++){
        k = p;
        q = p + 1;
        for(j = i+1; j < 200; j++, q++){
            if(k->score > q->score)
                k = q;
        temp = *p;
        *p = *k;
        *k = temp;
        }
    }
    p = stu;
    for(int i = 0; i < 200; i++, p++){
        if(p->score > max)
            max = p->score;
    }
    p = stu;
    for(int i = 0; i < 200; i++, p++){
        if(p->score == max)
            printf("number:%5d, score:%5d\n",p->num, p->score)
    }
    return 0;
}

构建单向链表

输入20个数（整型或浮点型），逆序构建一个单向链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
    float num;
    struct Node *next;
}node;
int main(){
    node *s, *head;
    float t;
    int i;
    head = (node*)malloc(sizeof(node));
    head->num = 0;
    head->next = NULL;
    for(i = 0; i < 20; i++){
        scanf("%f", &t);
        s = (node*)malloc(sizeof(node));
        s->num = t;
        s->next = head->next;   //头插法
        head->next = s;
    }
    s = head->next;
    while(s){
        printf("%f\n", s->num);
        s = s->next;
    }
    return 0;
}

Wrong Questions

C语言数据类型

  • void
  • 指针类型
  • 构造类型
    • 数组
    • 结构体 struct
    • 共同体 union
  • 基本类型
    • 整型 short int long
    • 字符 char
    • 实型 char float double

转义字符 8进制或者16进制

\97 – a \65 – A \65– @

除法 / 参与运算均为整数时，结果为整数，如果有一个运算数为实型，则结果为实型

取余 % 运算对象必须为整型

  • 32位编译器

    char ：1个字节
    char*（即指针变量）: 4个字节（32位的寻址空间是2^32, 即32个bit，也就是4个字节。同理64位编译器）
    short int : 2个字节int： 4个字节
    unsigned int : 4个字节
    float: 4个字节
    double: 8个字节
    long: 4个字节
    long long: 8个字节
    unsigned long: 4个字节

  • 64位编译器
    char ：1个字节
    char*(即指针变量): 8个字节
    short int : 2个字节
    int：4个字节
    unsigned int : 4个字节
    float: 4个字节
    double: 8个字节
    long: 8个字节
    long long: 8个字节
    unsigned long: 8个字节

声明结构体变量时，系统分配的存储空间为 该结构体中所有成员所需存储空间的总和

数组赋值 字符串

char a[10];
1、定义的时候直接用字符串赋值

1
char a[10]="hello";

注意：不能先定义再给它赋值，如

1
2
char a[10];
a[10]="hello";

这样是错误的！

2、对数组中字符逐个赋值

1
char a[10]={'h','e','l','l','o'};

3、利用strcpy

1
2
char a[10];
strcpy(a, "hello");

易错情况：

1
2
char a[10]; 
a="hello";

这种情况容易出现，a虽然是指针，但是它已经指向在堆栈中分配的10个字符空间，现在这个情况a又指向数据区中的hello常量，这里的指针a出现混乱，不允许！

C程序有3种结构化程序设计方法，顺序结构、选择结构和循环结构

C程序中，int整型乘float结果为double

1
2
3
4
5
6
7
8
9
10
#include<stdio.h>
int main() {
   printf("%d\n", sizeof(2+'a'+2*3.4));
   printf("%d", (int)3.9);
}
#output:
#8
#3

运算符

位运算符
位运算符是指二进制位的运算

  • 位与（&）

  • 位或（|）

  • 异或（^）

  • 取反（~）

    C语言中位取反是~，C语言中的逻辑取反是!

    按位取反是将操作数的二进制位逐个按位取反（1变成0，0变成1）；而逻辑取反是真（在C语言中只要不是0的任何数都是真）变成假（在C语言中只有0表示假）、假变成真。

  • 左移（<<）

  • 右移（>>）

    左移位<< 与右移位>>
    C语言的移位要取决于数据类型。
    对于无符号数，左移时右侧补0（相当于逻辑移位）
    对于无符号数，右移时左侧补0（相当于逻辑移位）
    对于有符号数，左移时右侧补0（叫算术移位，相当于逻辑移位）
    对于有符号数，右移时左侧补符号位（如果正数就补0，负数就补1，叫算术移位）

switch语句

switch语句中，如果满足case条件，则直接从相应的case语句中输出，如果没有break语句，则不跳出switch语句，继续往下执行

文件指针

？

C语言的隐式类型转换发生的四种情况，并说明每种情况如何转换

  • 算术运算式中，低类型能够转换为高类型
  • 赋值表达式中，右边表达式的值自动隐式转为左边参数的类型，并赋值给他
  • 函数调用中参数传递时，系统隐式地将参数转换为形参的类型后，赋给形参
  • 函数有返回值时，系统将隐式地将返回表达式类型转换为返回值类型，赋给调用函数

从C语言执行效率方便，简述下C语言采取了哪些措施提高执行效率

1.使用指针：对于指针的理解简单点可以认为类似于汇编中的寻址方式，正是指针的存在使C语言威力无穷。有些程序用其他语言也可以实现，但C能够更有效地实现；有些程序无法用其它语言实现，如直接访问硬件，但C却可以。正因为指针可以拥有类似于汇编的寻址方式，所以可以使程序更高效。
2.使用宏函数：函数和宏函数的区别就在于，宏函数占用了大量的空间，而函数占用了时间。函数调用是要使用系统的栈来保存数据的，如果编译器里有栈检查选项，一般在函数的头会嵌入一些汇编语句对当前栈进行检查；同时，CPU也要在函数调用时保存和恢复当前的现场，进行压栈和弹栈操作，所以，函数调用需要一些CPU时间。而宏函数不存在这个问题。宏函数仅仅作为预先写好的代码嵌入到当前程序，不会产生函数调用，所以仅仅是占用了空间，而使程序可以高效运行。在频繁调用同一个宏函数的时候，该现象尤其突出。
3.使用位操作：位操作可以减少除法和取模的运算。在计算机程序中数据的位是可以操作的最小数据单位，理论上可以用”位运算”来完成所有的运算和操作。一般的位操作是用来控制硬件的，或者做数据变换使用，但是，灵活的位操作可以有效地提高程序运行的效率。
4.循环嵌套中将较长循环设为内存循环，较短循环设为外置循环，以减少cpu跨切循环层的次数，提高程序的运行效率。

1
2
3
4
5
6
7
8
9
typedef struct DATA{    
    char key[10];       // 结构体成员：key    
    char name[20];      // 结构体成员：name    
    int age;
}DATA;    
DATA data;              // 声明一个结构体变量
DATA *pdata;            // 声明一个指向结构体的指针  // 访问数据操作如下：
data.age = 24;          // 结构体变量通过点运算符( . )访问
pdata->age = 24;        // 指向结构体的指针通过箭头运算符( -> )访问

C语言除关键字外，还有标识符、运算符、常量和分隔符

存储类型关键字（4）：

  • auto：修饰局部变量
  • register：此变量存储在CPU的寄存器中，由于CPU访问寄存器比内存快，可以大大提高速度
  • static
  • extern：用在变量或者函数的声明前，用来说明“此变量/函数是在别处定义的，要在此处引用