趨勢科技2011校招筆試題+答案解析

1、下面程式的輸出是多少？

void GetMemory(char *p)
{
p = (char *)malloc(11);
}
int main(void)
{
　　char *str = "Hello";
　　GetMemory(str);
　　strcpy(str,"Hello World");
　　printf("%s",str);
　　return 0;
}

A、Hello B、Hello World C、Hello Worl D、Run time error/Core dump

2、下面哪個會使這段程式編譯錯誤？

class A
{
public:
A()
{
}
};
class B:public A
{

　　10. public:

　　11. B()

　　12. {

　　13. }

　　14. };

　　15. A *pb = new B();

　　16. B b;

A、 A *pa = dynamic_cast<A *>(pb);

B、 A *pa = static_cast<A *>(pb);

C、 A a = static_cast<A >(b);

D、 A a = dynamic_cast<A >(b);

E、None of above

3、下面程式執行的結果是（）

void main()
{
char s[] = "abcde";
s += 2;
printf("%c\n",s[0]);
}

A、a B、b C、c D、編譯錯誤

4、下面程式執行的結果是（）

int main(void)
{
char matrix[3][3]={{'a','b','c'},{'d','e','f'},{'g','h','i'}};
printf("%c",matrix[1][4]);
return 0;
}

A、c B、f C、g D、h

二、算法題

1、如何用兩個棧來實作一個隊列，并分析有關隊列操作的運作時間。

2、如何用兩個隊列實作一個棧，并分析有關棧操作的運作時間。

參考答案（歡迎讨論）轉載請注明來源 http://www.cnblogs.com/jerry19880126/

選擇題：

D。GetMemory(str)并不會為str新配置設定空間，因為str和形參的p雖然指向相同，但它們自身的位址是不同的，p在執行malloc之後就指向不同的位置了，随後因為是局部變量而被釋放（但malloc的空間沒有析構，成為無法被引用的空間了）。str一直都是指向”Hello”的。str不是字元串數組（隻是一個指向字元串常量首位址的指針），沒有可用的連續空間，不能用strcpy。
D。用dynamic_cast進行轉換時，待轉換的類型隻能是指針或引用（更詳細的總結我會近期更新在部落格裡）。
D。數組的首位址是常量，不可以變更，若char* p = s. p是允許有p+=2的操作的。
D。數組是連續存儲的，元素在空間是連續排布的。

算法題：

隊列的操作主要有：入隊，出隊，傳回隊列長度，傳回隊首元素，判斷隊列是否為空。若用兩個stack實作，可以令其中一個inStack專門處理入隊操作，另一個outStack專門處理出隊操作。對于入隊而言，可以直接把元素加入到inStack中，複雜度為O(1)，出棧的時候需要做些處理，因為隊列是先入後出的，而棧是先入先出，是以輸出應該反序，比如inStack接收到的元素順序為1, 2, 3，棧頂元素是3，但出隊希望讓1先出。解決方法是把inStack裡的元素放到outStack中，這樣outStack接收到的元素順序就是3, 2, 1了，棧頂元素就是我們想要的1，時間複雜度為O(N)。更具體地，入隊直接inStack.push(元素)，出隊先判斷outStack是否為空，若不為空，則直接outStack.pop()，若為空，則把inStack元素導入到outStack裡，再執行outStack.pop()。其他操作都比較簡單，具體參考CPP程式，複制到visual studio中可以直接運作的。

用兩個棧實作隊列

趨勢科技2011校招筆試題+答案解析

1 #include <stack>
  2 #include <string>
  3 #include <iostream>
  4 #include <cassert>
  5 using namespace std;
  6 
  7 
  8 template <class T>
  9 class myQueue
 10 {
 11 private:
 12     stack<T> inStack; // 用于入隊操作
 13     stack<T> outStack; // 用于出隊操作
 14 public:
 15     void enqueue(const T& element); // 入隊
 16     T dequeue(); // 出隊
 17     T top(); // 檢視隊首元素，并不令之出隊
 18     bool empty() const; // 判斷隊列是否為空
 19     size_t size() const; // 傳回隊列元素的個數
 20 };
 21 
 22 /************************************************************************/
 23 /*
 24 入隊操作，算法複雜度為O(1)
 25 */
 26 /************************************************************************/
 27 template <class T>
 28 void myQueue<T>::enqueue(const T& element)
 29 {
 30     inStack.push(element);
 31 }
 32 
 33 /************************************************************************/
 34 /*
 35 出隊操作，算法複雜度為O(N)
 36 */
 37 /************************************************************************/
 38 template <class T>
 39 T myQueue<T>::dequeue()
 40 {
 41     assert(!empty());// 若隊列為空，則抛出異常
 42     if(outStack.empty())
 43     {
 44         // outStack為空，則将inStack裡的元素放入outStack裡面
 45         while(!inStack.empty())
 46         {
 47             T temp = inStack.top();
 48             inStack.pop();
 49             outStack.push(temp);
 50         }
 51     }
 52     T temp = outStack.top();
 53     outStack.pop();
 54     return temp;
 55 }
 56 
 57 /************************************************************************/
 58 /*
 59 檢視隊首元素，算法複雜度為O(N)，與出隊操作相比，隻是少了一次彈出操作而已
 60 */
 61 /************************************************************************/
 62 template <class T>
 63 T myQueue<T>::top()
 64 {
 65     assert(!empty());// 若隊列為空，則抛出異常
 66     if(outStack.empty())
 67     {
 68         // outStack為空，則将inStack裡的元素放入outStack裡面
 69         while(!inStack.empty())
 70         {
 71             T temp = inStack.top();
 72             inStack.pop();
 73             outStack.push(temp);
 74         }
 75     }
 76     T temp = outStack.top();
 77     return temp;
 78 }
 79 
 80 /************************************************************************/
 81 /*
 82 判斷隊列是否為空，算法複雜度O(1)
 83 */
 84 /************************************************************************/
 85 template <class T>
 86 bool myQueue<T>::empty() const
 87 {
 88     return size() == 0;
 89 }
 90 
 91 /************************************************************************/
 92 /*
 93 傳回隊列的長度，算法複雜度為O(1)
 94 */
 95 /************************************************************************/
 96 template <class T>
 97 size_t myQueue<T>::size() const
 98 {
 99     return inStack.size() + outStack.size();
100 }
101 
102 
103 // 測試樣例
104 int main()
105 {
106     myQueue<string> q;
107     cout << "隊列現在是否空 " << q.empty() << endl; 
108     q.enqueue("hello");
109     q.enqueue("world");
110     q.enqueue("how");
111     q.enqueue("are");
112     q.enqueue("you");
113     cout << "隊列長度為 " << q.size() << endl;
114     cout << "隊首元素為 " << q.top() << endl;
115     cout << "隊列長度為 " << q.size() << endl;
116     q.dequeue();
117     q.dequeue();
118     q.dequeue();
119     cout << "删除三個元素後，隊列長度為 " << q.size() << endl;
120     cout << "隊首元素為 " << q.top() << endl;
121     q.dequeue();
122     q.dequeue();
123     cout << "再删除兩個元素後，隊列長度為 " << q.size() << endl;
124     cout << "隊列是否空 " << q.empty() << endl;
125     q.enqueue("Good");
126     q.enqueue("Bye");
127     cout << "入隊兩個元素後，隊首元素為 " << q.top() << endl;
128     cout << "隊列是否空 " << q.empty() << endl;
129     return 0;
130 
131 }

趨勢科技2011校招筆試題+答案解析

棧的操作主要有：入棧，出棧，傳回棧頂元素，傳回棧長度以及判斷棧是否為空。若用兩個queue實作（可以定義成queue的數組queue q[2]），可以增加一個currentIndex來指向目前選中的queue。入棧操作可以直接把元素加到queue裡，即queue[currentIndex].push(element)，時間複雜度為O(1)，出棧操作要複雜一些，還是因為棧和隊列元素的出入順序不同，處理方法是将size()-1個元素從q[currentIndex]轉移到空閑隊列q[(currentIndex + 1)%2]中，q[currentIndex]最後一個剩下的元素恰對應棧頂元素，之後更新一下currentIndex即可，時間複雜度為O(N)。其他操作都比較簡單，具體參考CPP程式，複制到visual studio中可以直接運作的。

用兩個隊列實作棧

趨勢科技2011校招筆試題+答案解析

1 #include <iostream>
  2 #include <cassert>
  3 #include <queue>
  4 
  5 using namespace std;
  6 
  7 
  8 template <class T>
  9 class myStack
 10 {
 11 private:
 12     queue<T> q[2];
 13     int currentIndex;
 14 
 15 public:
 16     myStack():currentIndex(0){}
 17     bool empty() const;
 18     size_t size() const;
 19     void push(const T& element);
 20     void pop();
 21     T top();    
 22 };
 23 
 24 
 25 /************************************************************************/
 26 /*
 27 判斷棧是否為空，算法複雜度為O(1)
 28 */
 29 /************************************************************************/
 30 template <class T>
 31 bool myStack<T>::empty() const
 32 {
 33     return size() == 0;
 34 }
 35 
 36 /************************************************************************/
 37 /*
 38 傳回棧的大小，算法複雜度為O(1)
 39 */
 40 /************************************************************************/
 41 template <class T>
 42 size_t myStack<T>::size() const
 43 {
 44     return q[0].size() + q[1].size();
 45 }
 46 
 47 
 48 /************************************************************************/
 49 /*
 50 入棧操作，算法複雜度為O(1)
 51 */
 52 /************************************************************************/
 53 template <class T>
 54 void myStack<T>::push(const T& element)
 55 {
 56     q[currentIndex].push(element); // 入隊
 57 }
 58 
 59 
 60 /************************************************************************/
 61 /* 
 62 出棧操作，算法複雜度為O(N)
 63 */
 64 /************************************************************************/
 65 template <class T>
 66 void myStack<T>::pop()
 67 {
 68     assert(!empty()); // 若棧為空，則抛出異常
 69     int nextIndex = (currentIndex + 1) % 2;
 70     while(q[currentIndex].size() > 1)
 71     {
 72         // 從一個隊列搬移到另一個隊列
 73         T element = q[currentIndex].front();
 74         q[currentIndex].pop();
 75         q[nextIndex].push(element);
 76     }
 77     // 最後一個元素彈出
 78     q[currentIndex].pop();
 79     currentIndex = nextIndex;
 80 }
 81 
 82 
 83 /************************************************************************/
 84 /*
 85 傳回棧頂元素，算法複雜度為O(1)
 86 */
 87 /************************************************************************/
 88 template <class T>
 89 T myStack<T>::top()
 90 {
 91     assert(!empty()); // 若棧為空，則抛出異常
 92     int nextIndex = (currentIndex + 1) % 2;
 93     T element;
 94     while(q[currentIndex].size() > 0)
 95     {
 96         // 從一個隊列搬移到另一個隊列
 97         element = q[currentIndex].front();
 98         q[currentIndex].pop();
 99         q[nextIndex].push(element);
100     }
101     // 傳回最後一個元素
102     currentIndex = nextIndex;
103     return element;
104 }
105 
106 
107 // 測試程式
108 int main()
109 {
110     myStack<int> s;
111     for(int i = 0; i < 5; ++i)
112     {
113         s.push(i);
114     }
115     for(int i = 0; i < 5; ++i)
116     {
117         cout << s.top() << endl;
118         s.pop();
119     }
120     cout << "棧目前是否空 " << s.empty() << endl;
121     s.push(2);
122     cout << "插入一個元素後，棧目前是否空 " << s.empty() << endl;
123     s.push(-4);
124     cout << "插入-4後，棧目前大小 " << s.size() << endl;
125     cout << "棧頂元素為 " << s.top() << endl;
126     return 0;
127 }

趨勢科技2011校招筆試題+答案解析

趨勢科技2011校招筆試題+答案解析

繼續閱讀

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

Android – ListView 中添加按鈕，動态删除添加ItemView的操作

七牛雲-C#SDK-上傳-前期準備

IE8 CSS設定DIV居中，添加“margin:0 auto”

Small tricks

C++ 第十五周報告1--《冒泡法排序》

[轉]iOS微信小視訊優化心得

[轉]九大排序算法——C語言實作及詳解

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

QR碼編碼原理三（日本漢字和中文編碼）

測試面試題整理

hdu7108哈希