786
零零總總的麵試題（1）
FROM:qitian0008(https://blog.csdn.net/qitian0008);
一. 問題描述：兩個數組a[N]，b[N]，其中A[N]的各個元素值已知，現給b[i]賦值，b[i] = a[0]*a[1]*a[2]...*a[N-1]/a[i]；
要求：
1.不準用除法運算
2.除了循環計數值，a[N],b[N]外，不準再用其他任何變量（包括局部變量，全局變量等）
3.滿足時間複雜度O（n），空間複雜度O（1）
int main(int argc, char* argv[])
{
int i;
int a[10] = {1, 2, 1, 2, 1, 2, 1, 2, 1, 2};
int b[10];
b[0] = 1;
for(i = 1; i < 10; i++)
{
b[0] *= a[i - 1];
b[i] = b[0];
}
b[0] = 1;
for(i = 8; i > 0; i--)
{
b[0] *= a[i + 1];
b[i] *= b[0];
}
b[0] *= a[1];//注意哦親
for(i = 0; i < 10; i++)
{
cout << b[i] << " ";
}
cout << endl;
return 0;
}二. 二分查找
public int binarySearch(int[] dataset, int data) {
int beginIndex = 0;
int endIndex = dataset.length - 1;
int midIndex = -1;
if (data < dataset[beginIndex] || data > dataset[endIndex]|| beginIndex > endIndex)//這個也是相當的重要
return -1;
while (beginIndex <= endIndex) {
midIndex = (beginIndex + endIndex) >>> 1; //相當於midIndex = (beginIndex + endIndex) / 2，但是效率會高些
if (data < dataset[midIndex]) {
endIndex = midIndex - 1;
} else if (data > dataset[midIndex]) {
beginIndex = midIndex + 1;
} else {
return midIndex;
}
}
return -1;
}三. 字符串翻轉
四.
1、計數排序；
2、堆排序；
3、大數據量的處理；
4、快速排序；
5、兩個鏈表的公共節點；
6、一個單鏈表，不知道頭指針，隻知道中間元素i的指針，現在刪除指針i指向的元素；
7、單鏈表的反轉。
五. 下麵的C++代碼，哪個是正確的？
A:
int *f()
{
int a[3]={4,2,3};
return a;
}
B:
void f3(int * ret)
{
int a[3]={1,2,3};
ret=a;
return;
}
C:
vector<int> f()
{
vector<int> v(3);
return v;
}
D:
int f4()
{
int *a=new int(3);
return *a;
}
E: None of above
這個選擇C。為什麼？
以為vector有自動析構的功能。所以不用我們來釋放他申請的空間。故不會造成內存的泄露！
In the following，at least one correct answer to each question
1. Suppose that a selection sort of 80 items has completed 32 iterations of the main loop.How many items are now guaranteed to be in their final spot(never to be moved again?)
A. 16
B. 31
C. 32
D. 39
E. 40
Answer：C
2. Which synchronization mechanism(s) is/are used to avoid race conditions among processed/threads in operating systems?
A. Mutex
B. Mailbox
C.Semaphore
D. Local procedure call
Answer：AC
四種進程同步的方法（Mailbox隻能通信，不能同步？）：
1、臨界區:通過對多線程的串行化來訪問公共資源或一段代碼，速度快，適合控製數據訪問。
2、互斥量:為協調共同對一個共享資源的單獨訪問而設計的。
3、信號量:為控製一個具有有限數量用戶資源而設計。
4、事 件:用來通知線程有一些事件已發生，從而啟動後繼任務的開始。
3. There is a sequence of n numbers 1,2,3,...,n and a stack which can keep m numbers at most.Push the n numbers into the stack following the sequence and pop out randomly.Suppose n is 2 and m is 3,the output sequence may be 1,2 or 2,1, so we get 2 different sequences. Suppose n is 7 and m is 5,please choose the output sequences of the stack.
A. 1,2,3,4,5,6,7
B. 7,6,5,4,3,2,1
C. 5,6,4,3,7,2,1
D. 1,7,6,5,4,3,2
E. 3,2,1,7,5,6,4
Answer：AC
4. What is the result of binary number 01011001 after multiplying by0111001 and adding1101110?
A. 0001010000111111
B. 0101011101110011
C. 0011010000110101
Answer：A
5. What is output if you compile and execute the following c code?
void main()
{
int i=11;
int const *p=&i;
p++;
printf("%d",*p);
}
A. 11
B. 12
C. Garbage value
D. Compiler error
E. None of above
Answer：C
6. Which of following C++ code is correct:
A. int f()
{
int *a = new int(3);
return *a;
}
B. int *f()
{
int a[3] = {1,2,3};
return a;
}
C. vector<int> f()
{
vector<int> v(3);
return v;
}
D. void f(int *ret)
{
int a[3]={1,2,3};
ret = a;
return;
}
Answer：C
其它會有野指針，導致內存泄露
7. Given that the 180-degree rorated image of a 5-digit number is another 5-digit number and the difference between the number is 78633, what is the original 5-digit number?
A. 60918
B. 91086
C.18609
D.10968
E. 86901
Answer：D
8. Which of the following statements are ture?
A. We can create a binary tree from given inorder and preorder traversal sequences.
B. We can create a binary tree from given preorder and postorder traversal sequences.
C. For an almost sorted array, Insertion sort can be more effective than Quicksort.
D. Suppose T(n) is the runtime of resolving a problem with n elements, T(n)=O(1) if n=1; T(n)=2*T(n/2)+O(n) if n>1; so T(n) is O(n*logn).
E. None of above.
Answer：ACD
9. Which of the following statements are true?
A. Insertion sort and bubble sort are not efficient for large data sets.
B. Quick sort makes O(n^2) comparisons in the worst case .
C. There is an array:7,6,5,4,3,2,1. If using selection sort(ascending), the number of swap operation is 6.
D. Heap sort uses two heap operations: insertion and root deletion.
E. None of above.
Answer：ABD
10. Assume both x and y are integers ,which one of the following returns the minimum of the two integers?
A. y^((x^y)&-(x<y)).
B. y^(x^y).
C. x^(x^y)
D. (x^y)^(y^x)
E. None of above
Answer：A
11. The Orchid Pavilion(蘭亭集序) is well known as the top of "行書" in history of Chinese literature. The most fascinating sentence is "Well I know it is a lie to say that life and death is the same thing and that longevity and early death make no difference Alas!"("固知一生死為虛誕，齊彭殤為妄作。"). By counting the characters of the whole content (in Chinese version), the result should be 391(including punctuation). For these charaters written to a text file ,please select the possible size without any data corrupt.
A. 782 bytes in UTF-16 encoding
B. 784 bytes in UTF-16 encoding
C. 1173 bytes in UTF-8 encoding
D. 1176 bytes in UTF-8 encoding
E. None of above
Answer：BCD
UTF-16兩字節表示一個漢字，有Big Endian和Little Endian兩種，必須要加BOM兩字節。UTF-8通常三字節一個漢字，有加BOM和不加BOM兩種方式。
12. Fill the blanks inside class definition
Class Test
{
public:
_____ int a;
_____ int b;
public:
Test::Test(int _a, int _b):a(_a)
{
b = _b;
}
};
int Test::b;
int _tmain(int argc, _TCHAR * argv[])
{
Test t1(0, 0), t2(1, 1);
t1.b = 10;
t2.b = 20;
printf("%u %u %u %u", t1.a ,t1.b ,t2.a, t2.b);
return 0;
}
Running result: 0 20 1 20
A. static/const
B. const/static
C. --/static
D.const static/static
E. None of the above
Answer：BC
13. A 3-order B-tree has 2047 key words, what is the maximum height of the tree?
A. 11 B. 12 C. 13 D. 14
Answer：A
定理9.1 若n≥1，m≥3，則對任意一棵具有n個關鍵字的m階B-樹，其樹高h至多為：
logt((n+1)/2)+1。
這裏t是每個(除根外)內部結點的最小度數，即
14. In C++, which of the following keyword(s) can be used on both a variable and a function?
A. static B. virtual C. extern D.inline E. const
Answer：ACE
15. what is the result of the following program?
char * f( char * str, char ch)
{
char * it1 =str;
char * it2=str;
while(* it2 != '\0' )
{
while (* it2 ==ch)
{
it2++;
}
*it1++ = *it2++;
}
return str;
}
void main( int argc, char *argv[])
{
char * a = new char[10];
strcpy(a, "abcdcccd");
count << f(a, 'c');
}
A. abdcccd
B. abdd
C. abcc
D. abddcccd
E. Access violation
Answer：D
16. Consider the following definition of a recursive function ,power ,that will perform exponentiation.
int power(int b, int e)
{
if(e==0) return 1;
if(e%2 == 0) return power(b*b, e/2);
return b*power(b*b,e/2);
}
A. logarithmic
B. linear
C. quadratic
D. exponentical
Answer：A
17.Assume a full deck of cards has 52 cards, 2 black suits(spade and club) and 2 red suits(diamond and heart). If you are given a full deck, and half deck(with 1 red suit and a black suit), what's the possiblility for each one getting 2 red cards if taking 2 cards?
A. 1/2,1/2 B. 25/102,12/50 C. 50/51, 24/25 D. 25/51,12/25 E. 25/51,1/2
Answer：B
18. There is a stack and a sequence of n numbers (i.e. 1,2,3,...,n). Push the n numbers into the stack following the sequence and pop out randomly. How many different sequences of the n number we may get? Suppose n is 2,the output sequence may 1,2 or 2,1, so we get 2 different sequences.
A. C_2n^n
B. C_2n^n-C_2n^(n+1)
C. ((2n)!)/(n+1)n!n!
D. n!
E. none of the above
Answer：B?
19. Longest Increasing Subsequence(LIS) means a sequence containing some elements in another sequence by the same order, and the values of elements keep increasing.
For example, LIS of (2,1,4,2,3,7,4,6) is (1,2,4,6), and its LIS length is 5.
Considering an array with N element ,what is the lowest time and space complexity to get the length of LIS?
A. Time:N^2, Space:N^2;
B. Time:N^2, Space:N;
C. Time:NlogN, Space:N;
D. Time:N, Space:N;
E. Time:N, Space:C
Answer：C
20.What is the output of the follow piece of C++ code?
#include <iostream>
using namespace std;
struct Item
{
char c;
Item *next;
};
Item * Routine1( Item* x)
{
Item *prev = NULL,
curr = x;
while(curr)
{
Item *next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
void Routine2(Item *x)
{
Item *curr = x;
while(curr)
{
cout<<curr->c<<" ";
curr = curr->next;
}
}
void _tmain(void)
{
Item *x,
d = {'d', NULL},
c = {'c', &d},
b = {'b', &c},
a = {'a', &b};
x = Routine1(&a);
Routine2(x);
}
A. c b a d B. b a d c C. d b c a D. a b c d E. d c b a
Answer：E
六.
static int ack(int m,int n){
if(m==0){
return n+1;
}
else if(n==0){
return ack(m-1,1);
}
else{
return ack(m-1,ack(m,n-1));
}
}
求ack(2,29)是多少？
我們來看下 ack(1,n)=ack(0,ack(1,n-1))=ack(1,n-1)+1=...=ack(1,0)+n
我們推知ack(1,0)=2
故 ack(1,n)=n+2；
ack(2,n)=ack(1,ack(2,n-1))=ack(2,n-1)+2=...=ack(2,0)+2n
我們推知ack(2,0)=3
故ack(2,n)=2n+3
所以上麵的結果就是 2*29+3=61
關於這題，我們需要注意的有以下幾點：
1）根據字符串第一個字符，判斷正負數；
2）判斷每一個字符是否是數字；
3）判斷是否會越界。
2.定義 char a[]="hello";
char *s="hello";
那麼下麵的寫法對嗎：
a[1]='H';
*s++='H';
char a[]="hello"; //將字符串存儲在a開辟的棧存儲區域，即a[0]='h',....a[6]='\0',棧的存儲區是可讀可修改的。char *s="hello"; //"hello“是存儲在字符串常量存儲區域，s為其收地址，該區域是不能修改的。
那麼下麵的寫法對嗎：
a[1]='H'; //正確
*s++='H'; //錯誤！
3.單鏈表的逆序
4.大數據量的問題：一億大小的文件，裏麵有N行記錄，每行最長100字符，內存大小1M，給出合理的方式，求出裏麵重複率最大的那個記錄
最後更新：2017-04-03 18:52:09