C/C++软件工程师笔试题！！！

Question

1，程序设计（可以用自然语言来描述，不编程）：C/C++源代码中，检查花括弧（是“（”与
“）”，“{”与“}”）是否匹配，若不匹配，则输出不匹配花括弧所在的行与列。
2，巧排数字，将1,2,...,19,20这20个数字排成一排，使得相邻的两个数字之和为一个素数，且
首尾两数字之和也为一个素数。编程打印出所有的排法。
3，打印一个N*N的方阵，N为每边字符的个数（ 3〈N〈20 ），要求最外层为“X”，第二层为“Y”，从第三层起每层依次打印数字0，1，2，3，...
例子：当N =5，打印出下面的图形：
 X X X X X
 X Y Y Y X
 X Y 0 Y X
 X Y Y Y X
 X X X X X 

Answer 1

#第一题
可以用一个栈进行匹配#第二题
首先构造一个图G, 图的顶点是1-20这些数字，如果两个数字的和是素数就相连。分别从1-20开始，对
图进行周游，结果就是。#第三题
N最大能取到19，不妨设此时从最外层到内层的符号分别是base[]= {X, Y, 0, 1, 2, 3, 4, 5, 6, 7},设mid = (N+1)/2, 第i行第j列的值恰好是base [ min(i%m,j%m) + 1]。
const int max_n = 19;
const int min_n = 4;
static char base[(max_n+1)/2] = {'X', 'Y', '0', '1', '2', '3', '4', '5', ..., '7'};
void print(int n ) 
{ 
// assume that n is valid 
int i, j, t, m;

m = (n + 1) / 2;
for (i = 0; i < max_n; ++i) {
for (j = 0; j < max_n; ++j) {
cout << base [ min(i%m,j%m) + 1];
}
cout << "\n";
} 
}

Answer 2

"第i行第j列的值恰好是base [ min(i%m,j%m) + 1]。"
xl5338870(xlix)真是强!第一题还好
第二题涉及到图和回溯,凭空在纸上写代码实在是不是一件容易的事情...
第三题若没有找到上面的巧妙解法,要作出漂亮的代码也不容易...顺便问一下,这是什么公司的招聘题目啊?

Answer 3

"第i行第j列的值恰好是base [ min(i%m,j%m) + 1]。"
xl5338870(xlix)真是强!---------------------------方法确实好，可我总觉得有点不大对劲，调了半天没调出来，
谁来帮帮调试结果正确

Answer 4

xl5338870(xlix)的想法，却实好。：）
Thanks.

Answer 5

第三题不知道是不是这样的效果
#include "iostream.h"
#include "windows.h"
void main()
{
int num,i,j,k;
int uppervalue;
char a[20][20];
char ch[1];
ch[0]=' ';
for (j=0;j<20;j++)
for ( k=0;k<20;k++)
a[j][k]=' ';


cout<<"input number:";
cin>>num; if (num%2==0)
uppervalue=num/2;
else
uppervalue=num/2+1;
for ( i=0;i<num;i++)
for ( j=0;j<num;j++)
{
if (i==0||j==0||i==num-1||j==num-1)
a[i][j]='X';
else if (i==1||j==1||i==num-2||j==num-2)
a[i][j]='Y';
else
{
for (k=2;k<=uppervalue;k++)
{
if (i==k||j==k||i==num-1-k||j==num-1-k)
{
itoa(k-2,ch,10);
a[i][j]=ch[0];
break;
}
}
}

} for (j=0;j<num;j++)
{
for ( k=0;k<num;k++)
{
cout<<a[j][k];
cout<<"  ";
}
cout<<"\n";
}}

Answer 6

1，程序设计（可以用自然语言来描述，不编程）：C/C++源代码中，检查花括弧（是“（”与
“）”，“{”与“}”）是否匹配，若不匹配，则输出不匹配花括弧所在的行与列。#include <list>
#include <iostream>
#include <fstream>void main()
{
using namespace std; fstream file; //read source
file.open("test.cpp", ios::in);
if( !file)
{
return;
}
int iLineNum = 1;
char s; //character 
list<int> lstbracket; //{}
list<int> lstParenthesis; //()
while(!file.eof())
{
file.get(s);
if( s == '\n' )
{
// new line
iLineNum++;
}
// {}
if( s == '{')
{
lstbracket.push_back(iLineNum); //record linenum
}
if( s == '}')
{
if( lstbracket.empty())
{
cout<<"No Matching '}'  in "<<iLineNum<<endl;
}
else
{
lstbracket.pop_back();
}
} //()
if( s == '(')
{
lstParenthesis.push_back(iLineNum);

}
if( s == ')')
{
if( lstParenthesis.empty())
{
cout<<"No Matching  ')' in "<<iLineNum<<endl;
}
else
{
lstParenthesis.pop_back();
}
}
}
file.close();
int i = 0;
for( i = 0; i < lstbracket.size(); i++)
{
iLineNum = lstbracket.back();
cout<<"No Matching '{' in "<<iLineNum<<endl;
lstbracket.pop_back();
} for( i = 0; i < lstParenthesis.size(); i++)
{
iLineNum = lstParenthesis.back();
cout<<"No Matching '(' in "<<iLineNum<<endl;
lstParenthesis.pop_back();
} cout<<"end"<<endl;}

Answer 7

xl5338870(xlix) 
不错。

Answer 8

第二题用第归蛮好理解！
完整程序：
#include <iostream.h>
#include <windows.h>
#include <process.h>
const int max_n = 19;
static char base[(max_n+1)/2+1] = {' ','X', 'Y', '0', '1', '2', '3', '4', '5', '6', '7'};char getElem(int i,int j,int n)
{
int m=(n+1)/2;
if(i<=m)
{
if(j<=m)
{
if(i>=j)
return base[j];
else
return base[i];
}
else return getElem(i,n+1-j,n);
}
if(i>m)
{
if(j<=m)return getElem(n+1-i,j,n);
if(j>m)return getElem(i,n+1-j,n);
}
}void printElem(int n) 
{
for(int nRow=1;nRow<=n;nRow++)
{
for(int nCol=1;nCol<=n;nCol++)
cout<<getElem(nRow,nCol,n)<<" ";
cout<<endl;
}
}void main()
{
int n;
cout<<"输入边长：";
cin>>n;
if(n<=3 || n>=19)
{
MessageBox(NULL,"N不能小于3并且不能大于19！","输入错误",MB_OK);
return;
}
system("cls");
printElem(n);}

Answer 9

这三道题能摆平,我认为工作已经到手...
基础算法,是软件开发最基础和最核心的东东.
特别是第二题,很能体现专业和非专业的区别.说来惭愧,我虽然有把握作出来,但是时间上......
TNND,还真没构建过图的数据结构看来基础还是需要恶补......

Answer 10

1.
FILE *fp ;//源文件
unsigned int row = 0, col = 0 ;
//读入一字符，更新row, col,错误时返回EOF，处理转义符(\0返回0,etc).
int read_char() {return EOF;}
//matching为0时输出源文件符号匹配，否则输出row,col.
int out( int mathching ) ;//返回0表示源文件括号匹配，（小括号内不许有大括号）
int match()
{
char ch ;
static char SL[] = "({", SR[] = ")}" ;
static int b1 = 0, b2 = 0 ;
while( EOF != (ch = read_char()) && b1>=0 && b2>=0 ) 
switch( ch ) {
case '(': ++b1 ; break ;
case ')': --b1 ; break ;
case '{': b1 ? b2 = -1 : ++b2 ; break ;
case '}': --b2 ; break ;
}
return b1 || b2 ;
}
//括号有很多种且有次序要求时可改用下面的检测程序：（宏参数中设定为数学表达式的括号格式）
//CHECK(/* const char* */expr)的返回值为0则表达式括号匹配
//大括号里必须有中括号。中括号内必须有小括号。
//小括号内不能有中括号。中括号内不能有大括号。
//小/中括号最多1层，大括号最多100层。即不允许(()),但允许{{()[()]}}.
#define COUNT 3
const char *expr ;
int matching( int idx, int depth ) 
{
static const char SL[COUNT+1] = "([{", SR[COUNT+1] = ")]}" ;
static const int  D[COUNT] = { 1, 1, 100 } ;
char ch ;
int i, m =  -1 ;
while( ch = *expr++ ) {
if( ch == SR[idx] )  return idx-m-1 ;
for( i = 0 ; i < COUNT && ch != SL[i] && ch != SR[i] ; ++i ) ;
if( i >= COUNT ) continue ;
if( m < i ) m = i ;
if( (idx >= COUNT && matching(i, D[i]-1)) || ( idx <  COUNT && ( ch == SR[i] ||
i > idx || i == idx && (--m, --depth) < 0 || i < idx && (depth = D[i]-1) < 0 ||
matching( i, depth )  ) ) )
return 1 ;
}
return idx < COUNT ;
}#define CHECK(exp) (expr = exp, matching(COUNT,1))
2.数的可能排列太多了，理论上的上限应该是13的20次方。因此下面程序返回的存在的合格排列数应该是溢出后的错误结果。
#define NC 20
int P[NC+NC] = { //1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37
0, 1, 1, 1, 0, 1, 0, 1, 0, 0,
0, 1, 0, 1, 0, 0, 0, 1, 0, 1,
0, 0, 0, 1, 0, 0, 0, 0, 0, 1,
0, 1, 0, 0, 0, 0, 0, 1, 0, 0
} ;
int R[NC] = { 0 } ;
int output(int *p, int c) {
while( c-- ) printf( "%d ", *p++ ) ;
return printf( "\n" ) ;
}
unsigned long search( int idx, int max )
{
int i, j ;
static unsigned long c = 0 ;
if( idx == max ) return P[R[idx-1]+1] ? output(R,max) : 0;
for( i = 2; i <= NC ; ++i ) {
for( j = 0 ; j < idx && i != R[j]; ++j ) ;
if( j == idx && P[R[idx-1]+i]) 
R[idx] = i, c += search( idx+1, max ) ;
}
return c;
}
int main()
{
  printf( "count:%d\n", search(0) );
}
3。xl5338870(xlix)的有些计算方法好像有误。r行c列的值在字符数组中的下标不是base [ min(r%m,c%m) + 1]，而是min(min(r,n-r-1),min(c,n-c-1));#define MAX_N 19
#define MIN_N 4
const char * const CH = "XY0123456789" ;
int min(int m, int n ) { return m < n ? m : n ; } 
void print(int n ) 
{ 
int r, c ;
for( r = 0 ; r < n; ++r, printf( "\n" ) )
for( c = 0 ; c < n ; ++c )
printf( "%c", CH[min(min(r,n-r-1),min(c,n-c-1))]);
}

Answer 11

第一题也可以这样解：顺序查找{，逆序查找}，统计差值。第二题这样做更好：找出2-39以内的所有素数，数量少于19，判定无解。否则：从小素数开始构建1-20的加法算式组合。次小素数构建不包含最小算式数字的加法算式。依次递加。将找出的所有算式统计分析1-20中不重复的排列。这样在计算复杂度上达到最小。
遍历节点在数字比较大的时候计算会很慢。第三题也可以这样做：先定义二维字符数组，对最小的矩形进行字符串赋值。再对次小的矩形进行赋值。
然后print就可以了吧。

Answer 12

更正一个初值：2题中for循环中i的初值由2改为1: for( i = 1; i <= NC ; ++i ) {
我最后一次测试将第一个数人为设定成1以减小结果数量，忘记改回来，55555~~~~~2.数的可能排列太多了，理论上的上限应该是13的20次方。因此下面程序返回的存在的合格排列数应该是溢出后的错误结果。
#define NC 20
int P[NC+NC] = { //1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37
0, 1, 1, 1, 0, 1, 0, 1, 0, 0,
0, 1, 0, 1, 0, 0, 0, 1, 0, 1,
0, 0, 0, 1, 0, 0, 0, 0, 0, 1,
0, 1, 0, 0, 0, 0, 0, 1, 0, 0
} ;
int R[NC] = { 0 } ;
int output(int *p, int c) {
while( c-- ) printf( "%d ", *p++ ) ;
return printf( "\n" ) ;
}
unsigned long search( int idx, int max )
{
int i, j ;
static unsigned long c = 0 ;
if( idx == max ) return P[R[idx-1]+1] ? output(R,max) : 0;
for( i = 1; i <= NC ; ++i ) {
for( j = 0 ; j < idx && i != R[j]; ++j ) ;
if( j == idx && P[R[idx-1]+i]) 
R[idx] = i, c += search( idx+1, max ) ;
}
return c;
}
int main()
{
  printf( "count:%d\n", search(0) );
}

Answer 13

int main()
{
  printf( "count:%d\n", search(0), NC );
}
search并不搜索20个数的所有排列，它只若前idx个数被证实不合格，它将放弃搜索还没找出的数字。

Answer 14

int main()
{
  printf( "count:%d\n", search(0), NC );
}
search并不搜索20个数的所有排列，它只若前idx个数被证实不合格，它将放弃搜索还没找出的数字。

Answer 15

第三题的一个笨办法:
int _tmain(int argc, _TCHAR* argv[])
{
char ch[20][20];
int  N;
for(int k=0; k<20; k++)
memset(ch[k], 0, sizeof(ch[k]));
cout<<"Please input n(Less than 20): ";
cin>>N; for(int i=0; i<N; ++i){
for(int j=0; j<N; ++j){
if(i==0||j==0||i==N-1||j==N-1)
printf("X");
else if(i==1||j==1||i==N-2||j==N-2)
printf("Y");
else if(i==2||j==2||i==N-3||j==N-3)
printf("0");
else if(i==3||j==3||i==N-4||j==N-4)
printf("1");
else if(i==4||j==4||i==N-5||j==N-5)
printf("2");
else if(i==5||j==5||i==N-6||j==N-6)
printf("3");
else if(i==6||j==6||i==N-7||j==N-7)
printf("4");
else if(i==7||j==7||i==N-8||j==N-8)
printf("5");
else if(i==8||j==8||i==N-9||j==N-9)
printf("6");
else if(i==9||j==9||i==N-10||j==N-10)
printf("7");
//else if(i==10||j==10||i==N-11||j==N-11)
// printf("8");
//else if(i==11||j==11||i==N-12||j==N-12)
// printf("9");
//else if(i==12||j==12||i==N-13||j==N-13)
// printf("10");
else
printf("%d", ch[i][j]);
}
cout<<endl;
}
return 0;
}

Answer 16

太Easy!@!!%&$%$*^(%$^&$^O%^^(&%^$^&$#$%^R^*&)

Answer 17

第三题不难嘛。#include <iostream.h>int Min(int x,  int y)
{
if (x < y)
return x;
return y;
}int Max(int x,  int y)
{
if (x > y)
return x;
return y;
}int main()
{
int arr_nBase[] = {'X', 'Y', 0, 1, 2, 3, 4, 5, 6, 7};
int n = 19;
int nNum = 0;
for (int i=0; i<n; i++)
{
for (int j=0; j<n; j++)
{
if (i + j < n)
{
nNum = arr_nBase[Min(i, j)];
}
else
{
nNum = arr_nBase[n - 1 - Max(i, j)];
}
if (nNum == 'X' || nNum == 'Y')
cout << (char)nNum << " ";
else
cout << nNum << " ";
}
cout << endl;
} cin >> n;
return 0;
}