年前面趋逝科技的一套比试题求解
比试时间是2个小时 前面的智力题和后面的网络题都没记住 只记住了几道而已 大家做做看吧
题目1：（这题我没看懂英文）
There is binary search tree which is used to store characters 'A', 'B',
'C','D','E','F','G','H',which of the following is post-order tree walk
result? (有一个二叉搜索树用来存储字符'A', 'B', 'C','D','E','F','G','H'下
面哪个(些)结果是后序树遍历结果)
A. ADBCEGFH
B. BCAGEHFD
C. BCAEFDHG
D. BDACEFHG
E. All of above
题目2：
At time 0, process A has arrived in the system, in that order; at time
30, both progress B and C have just arrived; at time 90, both progress D
and E have also arrived.The quantum or timeslice is 10 units.
（在0时刻，进程A进入系统，按照这个顺序，在30时刻，进程B和进程C也抵达；在90时刻，进程D和进程E也抵达。一个时间片是10个单元）
Process A requires 50 units of time in the CPU;
Process B requires 40 units of time in the CPU;
Process C requires 30 units of time in the CPU;
Process D requires 20 units of time in the CPU;
Process E requires 10 units of time in the CPU;
进程A需要占用CPU50个单元;
进程B需要占用CPU40个单元;
进程C需要占用CPU30个单元;
进程D需要占用CPU20个单元;
进程E需要占用CPU10个单元;
Which of the process will be the LAST to complete, if scheduling policy
is preemptive SJF (Short Job First).please describe the principle.
(如果按照短作业优先级的方法，哪个进程最后结束。请描述原理)
题目3：Function club is used to simulate guest in a club. With 0 guests
initially and 50 as max occupancy, when guests beyond limitation, they need to wait outside;when some guests leave the waiting list will decrease. The function will print out number of guests in the club and waiting outside. The function declaration as follows:
void club(int x); positive x stands for guests arrived, nagative x stands for guests left from within the club
（club函数用来模拟一个俱乐部的顾客。初始化情况下是0个顾客，俱乐部最大规模只能有50个顾客，当用户超过了最大规模，他们必须等在外面。当一些顾客离开了等待队列将减少。这个club函数将打印在俱乐部里面的顾客人数，和外面的等待人数。函数声明如下：
void club(int x);正数x代表客人来了，负数x代表客人离开了俱乐部）
For example, club (40) prints 40,0; and then club (20) prints 50,10; and
then club (-5) prints 50,5; and then club (-30) prints 25,0; and then
club (-30) prints N/A; since it is impossible input.
（举例而言，club (40)打印40，0；接着club (20)打印50，10；接着club (-5)打印50，5；接着club (-30)打印25，0；接着club (-30)打印N/A；因为这是不可能实现的。）
Please write the void club(int x) with c++;
To make sure this function works as defined, we have following set of
data to pass into the function and check the result are correct.
(请用c++编程实现club函数。为了确保函数工作正常，我们使用下列数据来测试函数是否正常，你认为该选哪个选项)
a 60
b 20 50 -10
c 40 -30
d 60 -5 -10 -10 10
e 10 -20
f 30 10 10 10 -60
g 10 10 10
h 10 -10 10
A a d e g
B c d f g
C a c d h
D b d g h
E c d e f
题目4：The following C++ code tries to count occurence of each ASCII charcater
in given string and finally print out the occurrency numbers:（下面C++代码用来统计每个ASCII字符的出现次数，最后给出出现数值）
void histogram(char* src)
{
int i;
char hist[256];
for (i=0;i<256;i++)
{
hist[i]=0;
}
while(*src!='\0')
{
hist[*src]++;
}
for(i=0;i<=256;i++)
{
printf("%d\n", hist[i]);
}
}
If there may be some issue in the code above, which line(s) would be
（如果上面代码有错，将在哪行出现）
A 1 and 3
B 3 and 7
C 9
D 5 and 7
E 4 and 8
题目5：（说实话这道题我没看懂）
Consider the grammar （如下语法）
S--> aSbS|bSaS|V (S是变量)
where V means a terminator for grammar.（V是一个语法的终止符）
which statement(s) below is(are) corrects?（下列哪种说法是正确的）
1 This grammar is not an ambiguous grammar （这个语法不是一个含糊的语法）
2 Sentence 'abba' can be constructed by only one parse tree（语句abba能被构造成一个分析树）
3 This grammar construct sentence contain any 'a' (1 and more) and any 'b' (1 and more)（这个语法构造句包含一个或多个a和1个或多个b）
4 The grammar equals to regular expression "(a|b)?(a|b)+"（这个语法等于正则表达式(a|b)?(a|b)+）
A 1 B 2 3 C 3 D 1 3 E 2 4
题目6：
struct data
{
unsigned char x;
unsigned short y;
unsigned int z;
}
已知变量var类型为struct data;程序在32位上编，不考虑对齐，请补齐下面汇编语
言，以完成相应C语言功能
var.x=0;
LEA EBX, var
XOR EAX, ______
MOV [EBX], ______
var.y = (unsigned short) (var.z+1)
MOV ECX, ______
INC ECX
MOV ______, ______
var.z = var.y-1;
MOV DX, ______
AND EDX, ______
DEC, EDX
MOV ______, EDX
题目7：下列程序中能编译通过么？如果不能该如何修改使其通过。
是定义#define VOID_P 1 还是 #defineVOID_P 0，mem才能得到正确地址。
#include <iostream>
#define VOID_P 0
#if VOID_P
void allocm(void *pout, unsigned long size)
{
pout = malloc(size);
}
#else
void allocm(void **pout, unsigned long size)
{
*pout = malloc(size);
}
#elseif
int main(int argc, char *argv[]){
void *mem = 0;
#if VOID_P
allocm(mem, 100);
#else
allocm(&mem, 100);
#endif
return 0;
}
题目8：请编C++实现：函数可变长有序数组的插入（无重复数据节点）
int *head = NULL;
int Insert = (int **pHead, int n);
//参数：*pHead 数组首地址 n 插入数值
//返回值： 0成功， 1失败
[解决办法]
挺有意思
第4题
hist[*src]++;
改为
hist[*src++]++;
第6题貌似应该这么写：
var.x=0;
LEA EBX, var
XOR EAX, EAX
MOV [EBX], AL
var.y = (unsigned short) (var.z+1)
MOV ECX, dword ptr [EBX+3]
INC ECX
MOV [EBX+3], CX
var.z = var.y-1;
MOV DX, word ptr [EBX+1]
AND EDX, 0x0000ffff
DEC, EDX
MOV [EBX+3], EDX
第7题应该 #define VOID_P 1
[解决办法]
1 数据结构，二叉排序树，忘了
2 操作系统
A（50） 0-50
C（30） 50-80
B（40） 80-90
E（10） 90-100
D（20） 100-120
B（30） 120-150
3 c＋＋编程 、软件测试
C和D都可以吧，不太确定。
4 C语言的指针操作
C 如7楼所说，此处死循环
5 编译原理，自动机的内容，应该能考死很多人，
6 汇编语言，比较初级的，但是也考死我了
7 ＃define VOID_P 0,怎样用指针神情内存，此处为二级指针用法，我博客有一篇文章专门写这个（出自林锐博士的《高质量c＋＋编程指南》）。
编程的题，时间不够，回来再贴。
总之，这种题目才叫牛题目！！非是单纯的c和c++，操作系统，编译原理，汇编语言，软件测试都涵盖到，广度之外，深度也是有的。
瞻仰拿到趋势科技offer的牛人！！！
[解决办法]
第一题 二叉搜索树, 则必满足对树中任一非叶结点, 其左子树都小于该结点值, 右子树所有结点值都大于该结点值
结合二叉树后序遍历的特点, 最后一个肯定是根结点
A. ADBCEGFH
-> (H) 左子树(ADBCEGF), 右子树(空) (左子树必须都小于根H, 右子树都大于根H)
--> (F) 左子树 (ADBCE), 右子树(G)
---> (E) 左子树 (ADBC), 右子树(空)
----> (C) 剩下(ADB)不能区别左子树, 右子树, 所以选项A不成立
B. BCAGEHFD
->(D, (BCA), (GEHF))
--> GEHF, F为根, 剩下GEH不能根据F分成两个子段, 所以B不成立
C. BCAEFDHG
->(G, (BCAEFD), (H))
-->(G, (D, (BCA), (EF)), (H))
--->(G, (D, (A, (), (BC)), (F, (E), ())), (H))
---->(G, (D, (A, (), (C, (B), ())), (F, (E), ())), (H))
(G)
/ \
(D) (H)
/ \
(A) (F)
\ /
(C) (E)
/
(B)
选项(C)成立
D. BDACEFHG
-> (G, (BDACEF), (H))
--> (G, (F, (BDACE), ()), (H))
---> (G, (F, (E, (BDAC), ()), ()), (H))
----> BDAC子树, C为根, 据C不能将序列BDA划分为两个子序列, 使得左子序列全小于C, 右子序列全大于C
所以选项(D)不成立.
最终答案选C
[解决办法]
题二：140 units的时候最后一个进程B执行完毕：
60 90 100 130 140
A B E D E
[解决办法]
第三题选E。
因为是排错题，所以测试用例比需要能够尽可能多的覆盖所有情况。
a，g几乎不可能检测出出错的情况，所以排除ABCD。最后答案E
- C/C++ code
#include <iostream>#include <cstdlib>static int iPersIn = 0;static int iPersOut = 0;void club(int x);int main(){ int index = 0; // while((num = getchar()) != EOF) int nums[10] = {10,-20,0}; while(nums[index++] != 0) { club(nums[index-1]); } return 0;}void club(int x){ if(x > 0) { if((iPersIn+x) <= 50) { iPersIn += x; } else { iPersOut += iPersIn+x-50; iPersIn = 50; } std::cout<< "IN:"<< iPersIn<< std::endl; std::cout<< "OUT:"<< iPersOut << std::endl; } else { x = abs(x); if(iPersIn+iPersOut-x <= 0) { std::cout << "N/A" << std::endl; exit(0); } else { if(iPersOut > x) { iPersOut -= x; } else { iPersIn -= (x -iPersOut); iPersOut = 0; } } std::cout<< "IN:"<< iPersIn<< std::endl; std::cout<< "OUT:"<< iPersOut << std::endl; }}
[解决办法]
没想到已经有人先完成了第三题，不过我的实现方式不同，请大家指正。
答案：E
- C/C++ code
#include<iostream>#define MAX_NUM 50using namespace std;int iClubNum=0;int iOutSideNum=0;void club(int x){ if(x>=0) { iClubNum+=x; if(iClubNum>MAX_NUM) { iOutSideNum+=iClubNum-50; iClubNum=50; } } else { iClubNum+=x; //iOutSideNum+=x; if(iClubNum<50 && iOutSideNum>0) { if(iClubNum+iOutSideNum<=50) { iClubNum+=iOutSideNum; iOutSideNum=0; } else { iOutSideNum=iClubNum+iOutSideNum-50; iClubNum=50; } } }}void main(){ int x=0; char ch=0; while(1) { cout<<"Please input x:"<<endl; cin>>x; club(x); if(iClubNum>=0 && iOutSideNum>=0) { cout<<"In club has "<<iClubNum<<" people."<<endl; cout<<"OutSide club has "<<iOutSideNum<<" people."<<endl; } else { cout<<"N/A"<<endl; break; } cout<<"Continue?Y(Yes) or N(No)?"<<endl; cin>>ch; if(ch=='N' || ch=='n') break; }}
[解决办法]
题三：
跟测试有关，看有没有覆盖所有的边界条件
设A为成员， B为排队
C1 0 0
C2 <50(Up/Down) 0
C3 50 >0(Up/Down)
a 60 适用C3 *
b 20 50 -10 适用C2\C3
c 40 -30 适用C2 *
d 60 -5 -10 -10 10 适用C3\C2
e 10 -20 适用C1 *
f 30 10 10 10 -60 适用C1\C2\C3
g 10 10 10 适用C2
h 10 -10 10 适用C2
a e [c|g|h]
显然e一定要
所以我选A
A a d e g
B c d f g
C a c d h
D b d g h
E c d e f
[解决办法]
真是马虎，定义了一个宏，结果用者用着就忘了，这回改好了，方便修改，如果club扩展了，最大容100人了，改起来也方便
- C/C++ code
#include<iostream>#define MAX_NUM 50using namespace std;int iClubNum=0;int iOutSideNum=0;void club(int x){ if(x>=0) { iClubNum+=x; if(iClubNum>MAX_NUM) { iOutSideNum+=iClubNum-MAX_NUM; iClubNum=MAX_NUM; } } else { iClubNum+=x; if(iClubNum<MAX_NUM && iOutSideNum>0) { if(iClubNum+iOutSideNum<=MAX_NUM) { iClubNum+=iOutSideNum; iOutSideNum=0; } else { iOutSideNum=iClubNum+iOutSideNum-MAX_NUM; iClubNum=MAX_NUM; } } }}void main(){ int x=0; char ch=0; while(1) { cout<<"Please input x:"<<endl; cin>>x; club(x); if(iClubNum>=0 && iOutSideNum>=0) { cout<<"In club has "<<iClubNum<<" people."<<endl; cout<<"OutSide club has "<<iOutSideNum<<" people."<<endl; } else { cout<<"N/A"<<endl; break; } cout<<"Continue?Y(Yes) or N(No)?"<<endl; cin>>ch; if(ch=='N' || ch=='n') break; }}
[解决办法]
看了25楼的分析，我也说说，看看条件，第一感觉，肯定要包含e,因为只有他能测N/A的情况，一下就排除了B C D三项，再看A和E,差别在a和c,g和f的选取上，很显然，d包含a,f包含g,所以排除A,最终确定E
个人见解，请指正！
[解决办法]
题6:
- C/C++ code
#include <iostream>using namespace std;struct data { unsigned char x; unsigned short y; unsigned int z; };//var.x=0; //LEA EBX, var //XOR EAX, ______ //MOV [EBX], ______ //var.y = (unsigned short) (var.z+1) //MOV ECX, ______ //INC ECX //MOV ______, ______ //var.z = var.y-1; //MOV DX, ______ //AND EDX, ______ //DEC, EDX //MOV ______, EDX void dump(struct data& var){ cout << "x=" << (int)var.x << "\t" << "y=" << var.y << "\t" << "z=" << var.z << endl;}int _tmain(int argc, _TCHAR* argv[]){ struct data var = {1,1,1}; dump(var); //var.x = 0; __asm{ lea ebx, var; xor eax, eax; mov [ebx], eax } dump(var); //var.y = (unsigned short) (var.z+1) __asm{ mov ecx, dword ptr[var.z] inc ecx mov word ptr[var.y], cx } dump(var); var.y = 0; //var.z = var.y-1; __asm{ mov dx, var.y and edx, 0x0000ffff dec edx mov dword ptr[var.z], edx } dump(var); return 0;}
[解决办法]
第一次，贴乱了。不好意思。
- C/C++ code
/*
题目8：请编C++实现：函数可变长有序数组的插入（无重复数据节点）
int *head = NULL;
int Insert = (int **pHead, int n);
//参数：*pHead 数组首地址 n 插入数值
//返回值： 0成功， 1失败
*/
#include <iostream>
#include <cstdlib>
#include <cassert>
#include <cstring>
int len_used = 0;
int len_totoal = 20;
const int inc_per = 20;
bool isIn(int **pHead, int n)
{
int i;
for(i=0; i <len_used && (n > *(*pHead+i)); i++)
;
return (n == *(*pHead+i))?true:false;
}
int Insert(int **pHead, int n)
{
if(isIn(pHead, n))
{
std::cout < < n < <"already in." < < std::endl ;
return 1;
}
if(len_used >= len_totoal -1)
//array is not enouph
{
len_totoal += inc_per;
int *p = (int*)malloc(len_totoal*sizeof(int));
assert(p != NULL);
for(int i=0; i < len_used; i++)
{
*(p+i) = *(*pHead+i);
}
free(*pHead);
*pHead = p;
}
int i,j;
//brute sort, you can optimize the program here
for(i=0; i <len_used && (n > *(*pHead+i)) ; i++)
;
for(j=len_used-1; j>i-1; j--)
{
*(*pHead+j+1) = *(*pHead+j);
}
*(*pHead+i) = n;
len_used += 1;
return 0;
}
void printArray(int **pHead)
{
std::cout < < "array contains:";
for(int i=0; i <len_used; i++)
{
std::cout < <*(*pHead+i) < <'\t';
}
std::cout < < std::endl;
}
int main()
{
int *head = NULL;
head = (int*)malloc(len_totoal*sizeof(int));
assert(head != NULL);
int **pHead = &head;
memset(head, 0, len_totoal);
int num;
std::cin >> num;
while(num != 'q'-'0')
{
Insert(pHead, num);
printArray(pHead);
std::cin >> num;
}
free(head);
return 0;
}
[解决办法]
第三题实现：
- C/C++ code
#include <iostream>
using namespace std;
#define MAX_IN_CUSTOM (50)
void club(int x)
{
static int in_custom = 0; // 初始情况下，内部客人为0个
static int out_custom = 0; // 初始情况下，外部客人为0个
if ( x > 0 ) // 来人了
{
if ( x+in_custom > MAX_IN_CUSTOM ) // 需要将人留在外面
{
out_custom += x+in_custom - MAX_IN_CUSTOM; // 多于的人留在外面
in_custom = MAX_IN_CUSTOM;
}
else
{
out_custom = 0;
in_custom += x;
}
}
else if(x < 0) // 走人了
{
x = -x;// 转正
// 如果走的人比内部与外部之和的人还要多，那么就出现错误了！
// 在下面就表示为in_custom < 0
if ( out_custom > x ) // 外面人数更多（超过要走掉的人数）
{
out_custom -= x;
}
else
{
in_custom -= x-out_custom;
out_custom = 0;
}
}
// 打印输出结果
if ( in_custom < 0 )
{
std::cout < < "N/A" < < std::endl;
}
else
{
std::cout < < in_custom < < "," < < out_custom < < endl;
}
}
int main()
{
club(40);
club(20);
club(-5);
club(-30);
club(-30);
return 0;
}
[解决办法]
- C/C++ code
void histogram(char* src) { int i; char hist[256]; //char -128~127, unsigned char 0~255 for (i=0;i <256;i++) { hist[i]=0; } while(*src!='\0') { hist[*src]++; //没有自增，src++ } for(i=0;i <=256;i++) { printf("%d\n", hist[i]); } }
[解决办法]
第7题肯定是 #define xx 0
上部的那个没有完成传参，这很明显...