数组测试题

转自：http://bbs.yingjiesheng.com/thread-37806-1-1.html

对数组,指针,数据结构,算法,字符串,文件操作等问题都有覆盖.主要以c语言的实现为主,也有c++的题.大家可以先做做这10道题,测试一下自己的水平.
1. 下面这段代码的输出是多少(在32位机上).
    char *p;
    char *q[20];
    char *m[20][20];
    int (*n)[10];
    struct MyStruct
{
char dda;
double dda1;
int type ;
}；
MyStruct k;
 printf("%d %d %d %d",sizeof(p),sizeof(q),sizeof(m),sizeof(n),sizeof(k));
答案：4，80，1600，4，24
           n是指向一维数组的指针变量；k中不要忘了考虑对齐问题，这里dda为4个字节。

2.
(1)
char a[2][2][3]={{{1,6,3},{5,4,15}},{{3,5,33},{23,12,7}} };
for(int i=0;i<12;i++)
printf("%d ",_______);
在空格处填上合适的语句，顺序打印出a中的数字
答 案：a[i/6][(i/3)%2][i%3]；这道题目是多维数组的输出问题，这里要考虑的是每维数字的取值顺序问题：第一维，前六次循环都取0，后六 次取1，于是i/6可以满足要求；第二维，前3次为0，再3次为1，再3次为0，再3次为1，用量化的思想，i/3把12个数字分为4组每组3个，量化为 0、1、2、3，为要得到0、1、0、1我们这里就需要对（0、1、2、3）％2＝（0、1、0、1），于是(i/3)%2；最后一维我们需要的是（0、 1、2；0、1、2；0、1、2；0、1、2；）我们就i%3。
 (2)
char **p, a[16][8]; 
问：p=a是否会导致程序在以后出现问题？为什么？
答案：这个不会导致出现问题，但是要注意p的使用，如a[1][2] 等价的为 *(*(p+1)+2)而不是*(p+11),
3.用递归方式,非递归方式写函数将一个字符串反转.
   函数原型如下:char *reverse(char *str);
答案：
非递归方式：
char *reverse(char *str)
{
 int len = strlen(str);
 char temp;
 for(int i=0; i<len/2; i++)
 {
  temp = *(str+i);
  *(str+i) = *(str+len-1-i);
  *(str+len-1-i) = temp;
 }
 return str;
}
递归方式：???

4.strcpy函数和memcpy函数有什么区别?它们各自使用时应该注意什么问题?
答案：strcpy是字符串拷贝，遇 '\0' 则停。  
           memcpy是内存拷贝，要指定拷贝的长度。  
           当要拷贝二进制数据（比如说一个结构），只能用memcpy
5.写一个函数将一个链表逆序.
一个单链表，不知道长度，写一个函数快速找到中间节点的位置.
写一个函数找出一个单向链表的倒数第n个节点的指针.(把能想到的最好算法写出).
答案：
把一个链表中的接点顺序倒排
typedef struct linknode
{
int data;
struct linknode *next;
}node;
//将一个链表逆置
node *reverse(node *head)
{
node *p,*q,*r;
p=head;
q=p->next;
while(q!=NULL)
{
r=q->next;
q->next=p;
p=q;
q=r;
}
head->next=NULL;
head=p;
return head;
}

6.用递归算法判断数组a[N]是否为一个递增数组。
7.
有一个文件(名为a.txt)如下,每行有4项,第一项是他们的名次,写一个c程序,将五个人的名字打印出来.并按名次排序后将5行数据仍然保存到a.txt中.使文件按名次排列每行.

2,07010188,0711,李镇豪,
1,07010154,0421,陈亦良,
3,07010194,0312,凌瑞松,
4,07010209,0351,罗安祥,
5,07010237,0961,黄世传,
8.写一个函数,判断一个unsigned char 字符有几位是1.
  写一个函数判断计算机的字节存储顺序是升序(little-endian)还是降序(big-endian).
 9.微软的笔试题.
Implement a string class in C++ with basic functionality like comparison, concatenation, input and output. Please also provide some test cases and using scenarios (sample code of using this class).
Please do not use MFC, STL and other libraries in your implementation.
10.有个数组a[100]存放了100个数,这100个数取自1-99,且只有两个相同的数,剩下的98个数不同,写一个搜索算法找出相同的那个数的值.(注意空间效率时间效率尽可能要低).
这十道题还是能够看出自己的水平如何的.如果你能不假思索地做出这10道题,估计去国外大公司是没有问题了,呵呵.
答案我在整理中,以后陆续发布.................
下面有些题也不错,可以参考.
１．下面的代码输出是什么，为什么？
       void foo(void)
       {
            unsigned int a = 6;
            int b = -20;
            (a+b>6)?puts(">6"):puts("<=6");//puts为打印函数
       }
输出 >6．
就是考察隐式转换．int型变量转化成unsigned int,　b成了正数．
2. b)运行下面的函数会有什么结果？为什么？
       void foo(void)
          {
               char string[10],str1[10];
               int i;
               for(i=0;i<10;i++)
               {
                    str1 = 'a';
               }
               strcpy(string, str1);
           printf("%s",string);
          }
首先搞清strcpy函数的实现方法，
char * strcpy(char * strDest,const char * strSrc)
{
 　if ((strDest　==　NULL)　||　(strSrc　==　NULL))
 　　 throw "Invalid argument(s)";
 　char * strDestCopy　=　strDest;
 　while ((*strDest++　=　*strSrc++)　!=　'\0');
　 return strDestCopy;
}
由于str1末尾没有‘\0’结束标志，所以strcpy不知道拷贝到何时结束．
printf函数，对于输出char* 类型，顺序打印字符串中的字符直到遇到空字符（＇＼０＇）或已打印了由精度指定的字符数为止．

下面是微软的两道笔试题....
3. Implement a string class in C++ with basic functionality like comparison, concatenation, input and output. Please also provide some test cases and using scenarios (sample code of using this class).
Please do not use MFC, STL and other libraries in your implementation.
我的实现方案如下,这道题真地对c++的主要特性都进行了较好地考察.
String.h:
#ifndef STRING_H
#define STRING_H
#include <iostream>
using namespace std;
class String{
   public:
    String();
       String(int n,char c);
    String(const char* source);
    String(const String& s);
    //String& operator=(char* s);
    String& operator=(const String& s);
    ~String();
    char& operator[](int i){return a;}
    const char& operator[](int i) const {return a;}//对常量的索引.
    String& operator+=(const String& s);
    int length();
   friend istream& operator>>(istream& is, String& s);//搞清为什么将>>设置为友元函数的原因.
   //friend bool operator< (const String& left,const String& right);
   friend bool operator> (const String& left, const String& right);//下面三个运算符都没必要设成友元函数,这里是为了简单.
   friend bool operator== (const String& left, const String& right);
   friend bool operator!= (const String& left, const String& right);
   private:
    char* a;
    int size;
};
#endif

String.cpp:

#include "String.h"
#include <cstring>
#include <cstdlib>
String::String(){
    a = new char[1];
    a[0] = '\0';
    size = 0;
}
String::String(int n,char c){
 a = new char[n + 1];
 memset(a,c,n);
 a[n] = '\0';
 size = n;
}
String::String(const char* source){
 if(source == NULL){
  a = new char[1];
  a[0] = '\0';
  size = 0;
 }
 else
 {   size = strlen(source);
  a = new char[size + 1];
  strcpy(a,source);
 }
}
String::String(const String& s){
 size = strlen(s.a);//可以访问私有变量.
 a = new char[size + 1];
 //if(a == NULL)
 strcpy(a,s.a);
}
 
String& String::operator=(const String& s){
 if(this == &s)
  return *this;
 else
 {
  delete[] a;
        size = strlen(s.a);
  a = new char[size + 1];
  strcpy(a,s.a);
  return *this;
 }
}
String::~String(){
 delete[] a;//    
}
String& String::operator+=(const String& s){
  int j = strlen(a);
  int size = j + strlen(s.a);
  char* tmp = new char[size+1];
  strcpy(tmp,a);
  strcpy(tmp+j,s.a);
 delete[] a;
 a = tmp;
 return *this;
 }
int String::length(){
 return strlen(a);
}
main.cpp:
#include <iostream>
#include "String.h"
using namespace std;
bool operator==(const String& left, const String& right)
{
 int a = strcmp(left.a,right.a);
    if(a == 0)
  return true;
 else
  return false;
}
bool operator!=(const String& left, const String& right)
{
 return  !(left == right);
}
ostream& operator<<(ostream& os,String& s){
 int length = s.length();
 for(int i = 0;i < length;i++)
  //os << s.a;这么不行,私有变量.
  os << s;
 return os;
}

String operator+(const String& a,const String& b){
 String temp;
 temp = a;
 temp += b;
 return temp;
}
bool operator<(const String& left,const String& right){
 
 int j = 0;
 while((left[j] != '\0') && (right[j] != '\0')){
  if(left[j] < right[j])
   return true;
  else
  {
   if(left[j] == right[j]){
    j++;
    continue;
   }
   else
    return false;
  }
 }
 if((left[j] == '\0') && (right[j] != '\0'))
  return true;
 else
  return false;
}
bool operator>(const String& left, const String& right)
{   int a = strcmp(left.a,right.a);
    if(a > 0)
  return true;
 else
  return false;
 
}
istream& operator>>(istream& is, String& s){
 delete[] s.a;
 s.a = new char[20];
 int m = 20;
    char c;
 int i = 0;
 while (is.get(c) && isspace(c));
    if (is) {
  do {s.a = c;
       i++;
    /*if(i >= 20){
      cout << "Input too much characters!" << endl;
      exit(-1);
    }*/
    if(i == m - 1 ){
     s.a = '\0';
     char* b = new char[m];
     strcpy(b,s.a);
                 m = m * 2;
        s.a = new char[m];
     strcpy(s.a,b);
     delete[] b;
    }
  }
  while (is.get(c) && !isspace(c));
        //如果读到空白,将其放回.
  if (is)
   is.unget();
 }
 s.size = i;
 s.a = '\0';
 return is;
}

int main(){
 String a = "abcd";
 String b = "www";
 //String c(6,b);这么写不对.
    String c(6,'l');
 String d;
 String e = a;//abcd
 String f;
 cin >> f;//需要输入...
 String g;
 g = a + b;//abcdwww
 if(a < b)
  cout << "a < b" << endl;
 else
  cout << "a >= b" << endl;
 if(e == a)
  cout << "e == a" << endl;
 else
  cout << "e != a" << endl;
 
 b += a;
 
 cout << a << endl;
 cout << b << endl;
    cout << c << endl;
 cout << d << endl;
 cout << e << endl;
 cout << f << endl;
 cout << g << endl;
 cout << g[0] << endl;
 return 0;
}
 
 
4. Implement a single-direction linked list sorting algorithm. Please first define the data structure of linked list and then implement the sorting algorithm.
 
5.编写一个函数，返回两个字符串的最大公串！例如，“adbccadebbca”和“edabccadece”,返回“ccade”