附录G 练习题答案

G.1 各章练习

第3章

题目1

对应章节:3.7.1节

MessageBeep (0xFFFFFFFF);  // A simple beep. If the sound card is not available, the sound is ↙
    ↘ generated using the speaker.

题目2

对应章节:3.7.2节

#include <unistd.h>

int main()
{
        sleep(2);
};
第5章

题目1

对应章节:5.5.1节

如果未启用MSVC的优化编译功能,程序显示的数字分别是EBP的值、RA和argc。在命令行中执行相应的程序即可进行验证。

如果启用了MSVC的优化编译功能,程序显示的数字分别来自:返回地址RA、argc和数组argv[]。

GCC会给main() 函数的入口分配16字节的地址空间,所以输出内容会有不同。

题目2

对应章节:5.5.2节

这些都是打印UNIX时间的程序,其源代码如下所示:

#include 
#include 
 
int main(int argc, char*argv[])
{
  time_t vTime = time((time_t*)0);
  printf("%d\n", vTime); // <-- %d 在 MSVC 会报 warnning, 因为 time_t 在 MSVC 默认是8字节长度类型 
 
  return 0;
}
第7章

题目1

对应章节:7.4.1节

Linux下的GCC将所有文本字符串信息放置到.rodata数据段,它是显式只读的(“只读的数据”):

$ objdump –s 1

...
Contents of section .rodata:
 400600 01000200 52657375 6c743a20 25730a00  ....Result: %s..
 400610 48656c6c 6f2c2077 6f726c64 210a00    Hello, world!..
第13章

题目1

对应章节:13.5.1节

提示:函数printf() 只会被调用1次。

第14章

题目3

对应章节:14.4.3节

#include <stdio.h>

int main()
{
         for(int i = 100; i>0; --i)
         printf ("%d\n", i);
};

题目4

对应章节:14.4.4节

#include <stdio.h>

int main()
{
         int i;
         for (i=1; i<100; i=i+3)
                   printf ("%d\n", i);
};
第15章

题目1

对应章节:15.2.1节

这是一个统计C字符串中空格的程序,源代码如下:

int f(const char* aStr)
{
    const char* vEos = aStr;
    int vCount = 0;
    
    for(;!*vEos;++vEos)
    {
        if (*vEos == ' ') ++vCount;
    }
    
    return vCount;
}
第16章

题目1

对应章节:16.3.1节

int f(int a)
{
  return a*7;
}
第17章

题目2

对应章节:17.10.2节

计算5个双精度浮点数的平均值,源代码如下:

double f(double a1, double a2, double a3, double a4, double a5)
{
  return a1*a2*a3*a4*a5 / 5.0;
}
第18章

题目1

对应章节:18.9.1节

两个100x200矩阵的双精度加法运算程序,其源代码如下:

#define M    100
#define N    200
void s(double *a, double *b, double *c)
{
  for(int i=0;i<N;i++)
    for(int j=0;j<M;j++)
      *(c+i*M+j)=*(a+i*M+j) + *(b+i*M+j);
};

题目2

对应章节:18.9.2节

答案:两个矩阵(一个是100x200矩阵,另一个是100x300)的乘法运算程序,生成一个100x300的矩阵。其源代码如下所示:

#define M     100
#define N     200
#define P     300
void m(double *a, double *b, double *c)
{
  for(int i=0;i<M;i++)
    for(int j=0;j<P;j++)
    {
      *(c+i*M+j)=0;
      for (int k=0;k<N;k++) *(c+i*M+j)+=*(a+i*M+j) * *(b+i*M+j);
    }
};

题目3

对应章节:18.9.3节

double f(double array[50][120], int x, int y)
{
         return array[x][y];
};

题目4

对应章节:18.9.4节

int f(int array[50][60][80], int x, int y, int z)
{
        return array[x][y][z];
};

题目5

对应章节:18.9.5节

生成乘法九九表的程序

int tbl[10][10];

int main()
{
        int x, y;
        for (x=0; x<10; x++)
             for (y=0; y<10; y++)
                    tbl[x][y]=x*y;
};
第19章

题目1

对应章节:19.7.1节

这是一个改变32位数值字节序的函数,源代码如下:

unsigned int f(unsigned int a)
{
       return ((a>>24)&0xff) | ((a<<8)&0xff0000) | ((a>>8)&0xff00) | ((a<<24)&0xff000000);
};

题目2

对应章节:19.7.2节

这是一个把BCD封装的32位值转换为常规格式的函数,源代码如下:

#include <stdio.h>

unsigned int f(unsigned int a)
{
       int i=0;
       int j=1;
       unsigned int rt=0;
       for (;i<=28; i+=4, j*=10)
          rt+=((a>>i)&0xF) * j;
       return rt;
};
int main()
{
         // test
         printf ("%d\n", f(0x12345678));
         printf ("%d\n", f(0x1234567));
         printf ("%d\n", f(0x123456));
         printf ("%d\n", f(0x12345));
         printf ("%d\n", f(0x1234));
         printf ("%d\n", f(0x123));
         printf ("%d\n", f(0x12));
         printf ("%d\n", f(0x1));
};

题目3

对应章节:19.7.3节

#include <windows.h>

int main()
{
         MessageBox(NULL, "hello, world!", "caption",
                     MB_TOPMOST | MB_ICONINFORMATION | MB_HELP | MB_YESNOCANCEL);
};

题目4

对应章节:19.7.4节

这个函数把两个32位数相乘,返回64位的积。解答这种题目,根据输入输出进行判断的速度比较快。

#include <stdio.h>
#include <stdint.h>

// source code taken from
//http://www4.wittenberg.edu/academics/mathcomp/shelburne/comp255/notes/binarymultiplication.pdf

uint64_t mult (uint32_t m, uint32_t n)
{
    uint64_t p = 0; // initialize product p to 0
    while (n != 0) // while multiplier n is not 0
    {
      if (n & 1) // test LSB of multiplier
            p = p + m; // if 1 then add multiplicand m
        m = m << 1; // left shift multiplicand
        n = n >> 1; // right shift multiplier
    }
    return p;
}

int main()
{
    printf ("%d\n", mult (2, 7));
    printf ("%d\n", mult (3, 11));
    printf ("%d\n", mult (4, 111));
};
第21章

题目1

对应章节:21.7.1节

这个程序将显示文件所有人的user ID。其源代码如下所示:

#include <sys/types.h>
#include <sys/stat.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
    struct stat sb;

    if (argc != 2)
    {
        fprintf(stderr, "Usage: %s <pathname>\n", argv[0]);
        return 0;
    }
    if (stat(argv[1], &sb) == -1)
    {
        // error
        return 0;
    }

    printf("%ld\n",(long) sb.st_uid);
}

题目2

对应章节:21.7.2节

提示:研究的侧重点应当放在Jcc、MOVSx和MOVZX指令。

#include <stdio.h>

struct some_struct
{
        int a;
        unsigned int b;
        float f;
        double d;
        char c;
        unsigned char uc;
};

void f(struct some_struct *s)
{
           if (s->a > 1000)
           {
                    if (s->b > 10)
                    {
                                      printf ("%f\n", s->f * 444 + s->d * 123);
                                      printf ("%c, %d\n", s->c, s->uc);
                    }
                    else
                    {
                                      printf ("error #2\n");
                    };
           }
           else
           {
                    printf ("error #1\n");
           };
};
第41章

题目1

对应章节:41.6节

int f(int a)
{
         return a/661;
};
第50章

题目1

对应章节:50.5.1节

源代码:

#include <stdio.h>

int is_prime(int number)
{
    int i;
    for (i=2; i<number; i++)
    {
      if (number % i == 0 && i != number)
             return 0;
    }
    return 1;
}

int main()
{
    printf ("%d\n", is_prime(137));
};

G.2 初级练习题

G.2.1 练习题1.1

这是一个返回2个数中最大值的函数。

G.2.2 练习题1.4

程序源代码如下:

#include <stdio.h>

int main()
{
    char buf[128];

    printf ("enter password:\n");
    if (scanf ("%s", buf)!=1)
       printf ("no password supplied\n");
    if (strcmp (buf, "metallica")==0)
       printf ("password is correct\n");
    else
       printf ("password is not correct\n");
};

G.3 中级练习题

G.3.1 练习题2.1

这个函数可根据牛顿法计算平方根,其算法摘自Harold Abelson, Gerald Jay Sussman, and Julie Sussman:《Structure and Interpretation of Computer Programs》(1996)。

程序源代码如下所示:

// algorithm taken from SICP book

#include <math.h>

double average(double a, double b)
{
    return (a + b) / 2.0;
}

double improve (double guess, double x)
{
    return average(guess, x/guess);
}

int good_enough(double guess, double x)
{
    double d = abs(guess*guess - x);
    return (d < 0.001);
};

double square_root(double guess, double x)
{
    while(good_enough(guess, x)==0)
     guess = improve(guess, x);
    return guess;
};

double my_sqrt(double x)
{
    return square_root(1, x);
};

int main()
{
    printf ("%g\n", my_sqrt(123.456));
};
G.3.2 练习题2.4

答案:函数strstr() 。其源代码如下所示:

char * strstr (
          const char * str1,
          const char * str2
          )
{
          char *cp = (char *) str1;
          char *s1, *s2;

          if ( !*str2 )
               return((char *)str1);

          while (*cp)
          {
                    s1 = cp;
                    s2 = (char *) str2;

                    while ( *s1 && *s2 && !(*s1-*s2) )
                         s1++, s2++;

                    if (!*s2)
                        return(cp);

                    cp++;
          }

          return(NULL);

}
G.3.3 练习题2.6

提示:使用google搜索程序中的常量。

答案:程序采用的是TEA(Tiny Encryption Algorithm)加密算法。

C语言源代码摘自http://en.wikipedia.org/wiki/Tiny_Encryption_Algorithm

void f (unsigned int* v, unsigned int* k) {
     unsigned int v0=v[0], v1=v[1], sum=0, i;            /* set up */
     unsigned int delta=0x9e3779b9;                      /* a key schedule constant */
     unsigned int k0=k[0], k1=k[1], k2=k[2], k3=k[3];    /* cache key */
     for (i=0; i < 32; i++) {                            /* basic cycle start */
          sum += delta;
          v0 += ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
          v1 += ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
     }                                                   /* end cycle */
     v[0]=v0; v[1]=v1;
}
G.3.4 练习题2.13

答案:线性反馈位移寄存器。详细资料请参见:https://en.wikipedia.org/wiki/Linear_feedback_ shift_register

程序源代码如下所示:

// reworked, from https://en.wikipedia.org/wiki/Linear_feedback_shift_register

#include <stdint.h>

uint16_t f(uint16_t in)
{
    /* taps: 16 14 13 11; feedback polynomial: x^16 + x^14 + x^13 + x^11 + 1 */
    unsigned bit  = ((in >> 0) ^ (in >> 2) ^ (in >> 3) ^ (in >> 5) ) & 1;
    return (in >> 1) | (bit << 15);
};

//#define C 0xACE1u
#define C 0xBADFu

int main(void)
{
    uint16_t lfsr = C;
    unsigned period = 0;

    do
    {
      lfsr=f(lfsr);
      printf ("period=0x%x, lfsr=0x%x\n", period, lfsr);
      ++period;
    } while(lfsr != C);

    return 0;
}
G.3.5 练习题2.14

程序采用的是计算最大公因数GCD的算法。源代码可参见:http://beginners.re/exercise-solutions/2/14/GCD.c

G.3.6 练习题2.15

这是一个使用蒙特卡罗法计算圆周率的程序,源代码可参见:http://beginners.re/exercise-solutions/2/15/monte.c

G.3.7 练习题2.16

阿克曼(Ackermann)函数(https://en.wikipedia.org/wiki/Ackermann_function

)。

int ack (int m, int n)
{
         if (m==0)
                 return n+1;
         if (n==0)
                 return ack (m-1, 1);
                 return ack(m-1, ack (m, n-1));
};
G.3.8 练习题2.17

程序采用了第110号初等元胞自动机的原理。这种算法的介绍可参见:https://en.wikipedia.org/ wiki/Rule_110

程序源代码可参见:http://beginners.re/exercise-solutions/2/17/CA.c

G.3.9 练习题2.18

程序源代码可参见:http://beginners.re/exercise-solutions/2/18/

G.3.10 练习题2.19

程序源代码可参见:http://beginners.re/exercise-solutions/2/19/

G.3.11 练习题2.20

提示:可参考Hint: On-Line Encyclopedia of Integer Sequences(OEIS))。

答案:考拉兹猜想。请参考源代码中的注释。

程序源代码可参见:http://beginners.re/exercise-solutions/2/20/collatz.c

G.4 高难度练习题

G.4.1 练习题3.2

程序采用的是表查询的简易算法。

源代码请参见:go.yurichev.com/17156。

G.4.2 练习题3.3

源代码请参见:go.yurichev.com/17157。

G.4.3 练习题3.4

源代码和解密后的文件请参见:go.yurichev.com/17158。

G.4.4 练习题3.5

提示:我们可以看到,用户名称的字符串并没有占用整个文件。在偏移量 0x7F 之前的、以零终止的字节被程序忽略了。

源代码请参见:go.yurichev.com/17159。

G.4.5 练习题3.6

源代码请参见:go.yurichev.com/17160。

结合其他练习,您可以掌握修补这个web服务器所有漏洞的方法。

G.4.6 练习题3.8

源代码请参见:go.yurichev.com/17161。

G.5 其他练习题

G.5.1 “扫雷(Windows XP)”

请参见本书第76章。

提示:留意边界字节(0x10)。