PPLive笔试题

第一部分 基础题 每道题目中只有一个答案是正确的，请选择您认为最合适的答案。  


1.      系统为了管理文件，设置了专门的数据结构——文件控制块(FCB)。FCB是在执
行下列哪一个系统调用时建立的? (   )
A. create；     B. open；       C. read；              D. write
FCB，可以想到这部分数据是在执行"打开"操作之后由操作系统填入的。我们前面说过执行打开操作的意义就是让操作系统寻找被处理文件并且取得这个文件的特征信息，这些信息就存放在打开的FCB中。
2.         下面哪种排序法对12354最快（   ）
A. quick sort ；B. bubble sort ；C. merge sort；

3.         下面关于通道的叙述中,正确的是(   )
Ⅰ.通道相当于一个功能简单的处理机  对
Ⅱ.通道完成数据输入输出工作
Ⅲ.通道与CPU共用一个内存
A. Ⅰ和Ⅱ；B. Ⅰ和Ⅲ；C. Ⅱ和Ⅲ；D. 都是

 

查看：http://hi.baidu.com/meilei/blog/item/81e1aa645bd954f7f73654cd.html/cmtid/adc67acb58007214be09e63a


6.         所谓“变号操作”是指将一个整数变成绝对值相同但符号相反的另一个整数。
假设使用补码表示的8位整数X=10010101，则经过变号操作后结果为：(   )
A. 1101010； B. 10101；     C. 11101010；       D. 1101011

7.         设有一个用数组Q[1..m」表示的环形队列，约定f为当前队头元素在数组中的
位置，r为队尾元素的后一位置(按顺时针方向)，若队列非空，则计算队列中元素个数的公
式应为：(   )
A. r-f；  B. (m+r-f) mod m；     C. (m-r+f)mod m；      D. (m-r-f) mod m

8.         下面列出的四种存储器中，易失性存储器是(   )
A. RAM；B. ROM；C. PROM；D. CD-ROM
ROM在系统停止供电的时候仍然可以保持数据，而RAM通常都是在掉电之后就丢失数据，典型的RAM就是计算机的内存。因此，是非易失性存储器




第二部分 简述题 

11.     请描述TCP/IP 建立连接的过程， TCP协议中一个TCP连接断开有那几种事件序列可能？ 

12.     请就一个具体的操作系统描述网络编程的几种socket模型，并阐述在大规模的网络系统中采取怎样的方式可提供更高的性能；
一：select模型
二：WSAAsyncSelect模型
三：WSAEventSelect模型
四：Overlapped I/O 事件通知模型
五：Overlapped I/O 完成例程模型
六：IOCP模型

13.     什么是回调函数，简述其功能和使用场景？

14.     试从算法、控制策略或 网络传输过程等方面之一描述一到两款你熟悉的P2P软件
；

第三部分 综合题

1.       对任意输入的正整数N，编写C程序求N!的尾部连续0的个数，并指出计算复杂度
。如：18！＝6402373705728000，尾部连续0的个数是3。

2.       写一个函数bitcount(short input)，返回一个输入对应二进制原码表示的位数
，如bitCount(7)= 3， bitCount(2543) = 9， bitCount(11111) = 9 

3.       谈谈你对P2P技术当前和未来发展的看法？ 


一、问答
1、实模式与保护模式。为什么要设计这两种模式？好处在什么地方？分别写出各自寻址的
过程。
答：
1. 实模式，又叫实地址模式，CPU完全按照8086的实际寻址方法访问从00000h--FFFFFh（1MB大小）的地址范围的内存，在这种模式下，CPU只能做单任务运行；寻址公式为：物理地址=左移4位的段地址+偏移地址，即：物理地址是由16位的段地址和16位的段内偏移地址组成的。
2.保护模式，又叫内存保护模式，寻址采用32位段和偏移量，最大寻址空间4GB，在这种模式下，系统运行于多任务，设计这种模式的原因和好处是：保护模式增加了寻址空间，增加了对多任务的支持，增加了段页式寻址机制的内存管理（分段机制使得段具有访问权限和特权级，各应用程序和操作系统的代码和核心是被保护的，这也是多任务支持的实现关键和保护这个名字的由来）。寻址过程为：物理地址=由段地址查询全局描述符表中给出的段基址+偏移地址，即：物理地址由影像寄存器中的基址加上16位或者32位的偏移组成。


2、请阅读以下一段程序，并给出答案。

class A
{
public:
    A(){ doSth(); }
    virtual void doSth(){printf("I am A");}
};
class B:public A
{
public:
    virtual void doSth(){ printf("I am B");}
};
B b;

执行结果是什么？为什么？
答：执行结果是I am A
因为b对象构造时调用基类A的构造函数A()，得此结果。

3、在STL的应用中 map这种key-value的应用很多，如果key的类型是GUID，该如何处理？

答：谁知道怎么处理补上吧。

4、一个内存变量a=5，有5个线程需要对其进行操作，其中3个对a进行加1操作，2个对a进
行减1操作，为了保证能够得到正常结果6，需要使用什么方法？（列出越多越好）
答：即要求列出线程同步方法，具体答案可见下面一题。

5、描述并比较以下对象：事件，信标，临界区，互斥对象。
答：这些对象都是用于线程同步的对象。
临界区：一种保证在某一时刻只有一个线程能访问数据的简便办法。它只可以在同一进程
内部使用。主要API函数有，产生临界区：InitializeCriticalSection，删除临界区：De
leteCriticalSection，进入临界区：EnterCriticalSection，退出临界区：LeaveCritic
alSection。
互斥对象：互斥对象跟临界区相似，但它不仅仅能够在同一应用程序不同线程中实现资源
的安全共享，而且可以在不同应用程序的线程之间实现对资源的安全共享，当然下面两者
也有这个特点。主要API函数有，创建互斥量： CreateMutex，打开一个存在的互斥量：
OpenMutex，释放互斥量的使用权：ReleaseMutex，关闭互斥量： CloseHandle。
信标：使用信号量（信标）最重要用途是：信号允许多个线程同时使用共享资源，它指出
了同时访问共享资源的线程最大数目。它的API函数和使用方法都与互斥对象相似，如创建
信号灯：CreateSemaphore，传入的参数可以指定信号灯的初始值。
事件：用来通知其他进程/线程某件操作已经完成。API函数有创建，打开事件对象等，特
殊点的是可以用函数SetEvent人工设置事件为有无信号状态，因此创建事件对象时可以有
两种方式，一种为自动重置，一种为人工重置。只有人工重置方式创建的事件对象才能正
确使用函数SetEvent。
鉴于本套题考的是VC，有必要说明的是在MFC中对于各种同步对象都提供了相对应的类CCt
iticalSection,CMutex,CSemaphore ,CEvent，另外为使用等待功能封装了两个类：CSing
leLock和CMultiLock。这些类方便了使用这些同步对象。

6、cdecl、stdcall、fastcall是什么？哪种可以实现个数不定的入口参数，为什么？
答：三者都是函数调用的约定。
cdecl：c declare（C调用约定）的缩写，是C和C++程序的缺省调用方式，规则是，按从右
至左的顺序压参数入栈，由调用者把参数弹出栈，对于传送参数的内存栈是由调用者来维
护的，正因为如此，只有这种调用方式可实现个数不定的入口参数（可变参数）。
stdcall：是Pascal程序的缺省调用方式，规则是，按从右至左的顺序压参数入栈，被调用
的函数在返回前清理传送参数的内存栈。
上两者的主要区别是前者由调用者清理栈，后者由被调用的函清理栈。当然函数名的修饰
部分也是不同的。
fastcall：采用寄存器传递参数，特点就是快了。

二、程序设计（以下题目请写出实现代码）
1、有一段文本，统计其中的单词数。例如：
As a technology , "HailStorm" is so new that it is still only known by its
code name.
注意：单词间的间隔不一定是一个空格。
答：可执行程序代码如下，假设该文本已存入text这个数组里。

void main()
{
  char text[1000]={"As a technology , 'HailStorm' is so new that it is still o
nly known by its code name."};
  int i=0,count=0;
  bool flag=true;
  while (text[i]&&i<1000)
  {
    if (text[i]==' ')
    {
      flag=true;
    }
    else if (flag==true && ((text[i]>='a'&&text[i]<='z')||(text[i]>='A'&&text[
i]<='Z')))
    {  // 前有空格，接着出现字母，表示出现一个单词。
      count++;
      flag=false;
    }
    i++;
  }
  cout<}

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
－－－－－－－
插播广告啦：版权所有：朱科 欢迎光临我的网站：，各位转贴别删，劳
动成果啊
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
－－－－－－－

2、国际象棋有8×8格，每个格子可放一个棋子。皇后的规则是可以横、竖、斜移动。在一
个棋盘放置8个皇后，并使它们互相无法威胁到彼此。
答：以下是可执行C代码，采用非递归解法，你如果想了解皇后问题的算法的详细过程可看
下面网址：

不过下面的代码是以列优先进行试探的，不是上面网址介绍的那样以行优先的，当然本质
是一样的。

#include
#define QUEEN 8  //皇后数量
int queen[QUEEN] ;  //下标代表所在列号,值代表所在行号，
          //如queen[1]=2表示第1列第2行有个皇后
bool row_YN[QUEEN] ;      //棋局的每一行是否有棋,有则为1,无为0 ;
bool passive_YN[2*QUEEN-1] ;  //斜率为1的斜线方向上是否有棋,共有2*QUEEN-1个斜线

bool negative_YN[2*QUEEN-1] ; //斜率为负1的斜线方向上是否有棋
//用全局变量,因全局数组元素值自动为0
int main()
{
  int row = 0 ;//游标,当前移动的棋子(以列计)
  bool flag = false ;   //当前棋子位置是否合法
  queen[0] = -1 ;      //第0列棋子准备,因一开始移动的就是第0列棋子
  int count = 0 ;      //一共有多少种解法的计数器 ;

  while(row>=0 ) //跳出条件是回溯到无法回溯时
  {
    queen[row]++ ;      //row列上的皇后走到下一行试试
    if(queen[row] >= QUEEN) //当前列全部走完
    { 
      queen[row] = -1 ; //当前列棋子置于准备状态
      row-- ;        //回溯到上一列的棋子
      if(row>=0)      //回溯时要清理如下行，斜线的标志位  
      {
        row_YN[queen[row]] = false ;
        passive_YN[queen[row] + row] = false ;
        negative_YN[QUEEN-1 + row - queen[row]] = false ;
      }
    }
    else
    {
      //先判断棋子所在行没有棋子
      if(row_YN[queen[row]] == false)
      {
        flag = true ;
        //以下检查当前棋子是否与之前的棋子斜线相交
        if( passive_YN[queen[row] + row] == true || negative_YN[QUEEN-1 + row
- queen[row]] == true) 
          flag = false ;
        else    
          flag = true ;
        if(flag)  // flag为真表示位置合法
        { 
          if(row == QUEEN-1)  //列到达最后，即最后一个皇后也找到位置，输出解

          {
            count++ ;  //解法的数目加一 ;
            cout<<"***第"<            for(int i=0;i              cout<<"第"<          }
          row_YN[queen[row]] = true ;// 当前行设为有棋子
          passive_YN[queen[row] + row] = true ;//当前行正斜率方向有棋子
          negative_YN[QUEEN-1 + row - queen[row]] = true ; //当前行负斜率方向上
也有棋子
          row++ ;
          if(row >= QUEEN)
          {  // 找到解后再次回溯找另外的解，这同上面无解回溯是一样的
            row-- ;
            row_YN[queen[row]] = false ;
            passive_YN[queen[row] + row] = false ;
            negative_YN[QUEEN-1 + row - queen[row]] = false ;//原理同回溯
          }     
          flag = false ;    
          }
      }
    }
  }
  cout<  return 0 ;
}


3、输入二个64位的十进制数，计算相乘之后的乘积。
答：以下代码为网上别人贴出的，输入任意位数十进制数（包括小数，负数）都可以得出
正确结果。
思路是：将大数当作字符串进行处理，也就是将大数用10进制字符数组进行表示，然后模
拟人们手工进行“竖式计算”的过程编写乘法。

#include
#define MAX 100
int str_num(char str[]) //计算字符串的长度,等效于strlen(str);
{
  int i=0,num_str=0;
  while(str[i]!=0)
  {num_str++;
  i++;
  }
  return(num_str);
}
void place(int num_str,char str[]) //将字符串高低颠倒。
{
  int temp=0,i=0,j=0;
  for(i=0,j=num_str-1;i  {temp=str[j];
  str[j]=str[i];
  str[i]=temp;
  }
}
void transition(unsigned int a[],char str1[]) //数字字符转化为数字。
{
  int i=0;
  while(str1[i]!=0)
  {a[i]=str1[i]-'0';
  i++;
  }
}
void multiply_int(unsigned int a[],unsigned int b[],unsigned int c[]) //大数相
乘算法，入口为整形数组。
{
  int i=0,j=0;
  for(i=0;i  for(j=0;j  {
    c[i+j]+=a[i]*b[j];
    c[i+j+1]+=c[i+j]/10;
    c[i+j]%=10;
  }
}
void output(int sign,unsigned int c[],int quan) //数据输出。
{
  int sign_temp=0,i=0;
  cout<<"The result is: ";
  if(sign==1)
  cout<<"-";
  for(i=MAX-1;i>-1;i--)
  {
    if(sign_temp==0)
    {if(c[i]!=0)
    sign_temp=1;
    }
    if(sign_temp==1)
    {
      if(i==quan-1)
      cout<<".";
      cout<      c[i]=0;
    }
  }
  cout<}
void multiply_string(char str1[],char str2[],unsigned int c[]) //大数相乘，入口
为字符串。
{
  unsigned int a[MAX]={0},b[MAX]={0};
  int sign=0;
  transition(a,str1);
  transition(b,str2);
  multiply_int(a,b,c);
}
int sign_comp(char str1[],char str2[]) //符号判断，如果为负数将作相应处理。
{
  int i=0,sign_num=0;
  if(str1[0]==45)
  {sign_num=!sign_num;
  for(i=0;i  str1[i]=str1[i+1];
  }
  if(str2[0]==45)
  {sign_num=!sign_num;
  for(i=0;i  str2[i]=str2[i+1];
  }
  return (sign_num);
}
int format(char str[]) //将输入的字符串进行格式化。以得到字符的一些标志信息和相
应格式的新数据串。
{
  int point=0,quan=0,i=0,j,k=0,sign_point=0,num_str=0;
  num_str=str_num(str);
  while(str[i]!=0)
  {
    if(str[i]<'0'||str[i]>'9')
    if(str[i]!='.')
    {cout<<"data error"<    return(-1);
    }
    else
    {point++;
    sign_point=i;
    }
    if(point>1)
    {cout<<"data error"<    return(-1);
    }
    i++;
  }
  if(point==1)
  {
    for(j=sign_point;j    str[j]=str[j+1];
    num_str--;
    quan=num_str-sign_point;
  }
  place(num_str,str);
  return(quan);
}
void clear(char str[]) //清空函数。
{
  int i;
  for(i=0;i  {
    str[i]=0;
  }
}

void main(void) //主函数。
{
  char str1[MAX]={0},str2[MAX]={0};
  int quan1=0,quan2=0,sign=0;
  unsigned int c[MAX*2+1]={0};
  do
  {
    cout<<"Please input the first number:";
    cin>>str1;
    cout<<"Please input the second number:";
    cin>>str2;
    sign=sign_comp(str1,str2);
    quan1=format(str1);
    quan2=format(str2);
    if(quan1==-1||quan2==-1)
    {
      clear(str1);
      clear(str2);
    }
  }while(quan1==-1||quan2==-1||str1[0]==0||str2[0]==0);
  multiply_string(str1,str2,c);
 output(sign,c,quan1+quan2);
}