1、給定一個N個整數元素的數組，元素分別為A1, A2, A3....AN，每個元素分別對應一個權重W1（小于1的float）, W2,W3....WN，其和為1，找出其中一個元素Ak，使所有小于Ak的元素的權重之和小于1/2，所有大于Ak的元素的權重之和>=1/2。
??????? 思路：首先將該數組按元素值的大小進行升序排列，同樣的那個權值數組也要對應的進行排序，因為原先的那個數組的下標和權值數組的下標是相對應的，如果權值數組不跟著變化的，那么就無法知道某一個數的權值是多少了，就無法對應起來了。。
??????? 核心代碼如下：

sum = w[1];//小于Ak的元素的權重之和 for(k=2;k<=n;k++) {if(sum>1/2)return -1; //沒有找到符合要求的元素Akif(sum < 1/2 && sum + w[k] <= 1/2) //sum < 1/2 保證使所有小于Ak的元素的權重之和小于1/2。 sum + w[k] <= 1/2，使得小于等于Ak的元素權重之和小于等于1/2，也就是所有大于Ak的元素的權重之和>=1/2。return A[k];sum += w[k]; }

2、給定一個N個元素的整數，元素分別為A1,A2,A3....AN，將數組變為A1<A2>A3<A4......的鋸齒狀數組，時間復雜度？
?????? 這個題目比排序更好點，將數組分為兩部分，前半部分的值全部小于后半部分的值，接下來從兩個起始位置逐個取數就可以了。

????? ?首先用nth_element把數組劃分，以中位數為分界點，所有小于中位數(x)的元素在x之前，大于x的元素在x之后。
?????? 然后從兩頭分別取一個小于x的數，大小x的數，保存到另一數組中。
?????? nth_element的時間復雜度是O(n)的。

?????? 例如:?
?????? 原數組?? 1 5 3 7 4 2 6
???????nth_后?? ?1 3 2 4 7 6 5 （只保證4在中間，前三個不一定有序，但都比4小）
?????? 新數組?? 1 7 3 6 2 5 4

代碼如下：

#include "iostream" #include "algorithm" using namespace std;int main(void) {int a[] = { 1, 5, 3, 7, 4, 2, 6 };int b[100];int size = sizeof( a ) / sizeof( a[0] );int mid = size / 2;nth_element( a, a+mid, a+size );int index1, index2, index3 = 0;for( index1 = 0, index2 = mid+1; index1 < mid; ++index1, ++index2 ){b[index3++] = a[index1];if( index2 < size )b[index3++] = a[index2];}b[index3] = a[mid];for( int i1 = 0; i1 < size; ++i1 ){cout << b[i1] << " ";}system("pause");return 0; }

3、10個人去看電影，其中5個人每人只有5元的鈔票，另外5個人每個人只有10元的鈔票，電影票的票價是5元，現在10個人排隊去買票，問有多少種排列的方法，使得每個人在買票的時候售票員都有錢找。

C（2n，n）/（n+1）
4、編寫C++中的兩個類，一個只能在棧中分配空間，一個只能在堆中分配。

#include<iostream> using namespace std;// 只在堆上的類 // 私有化析構函數，通過一個public函數來進行實際的析構。 class HeapOnly { public: HeapOnly(){cout << "constructor." << endl;}void destroy () const{delete this;} private:~HeapOnly(){} };int main(void) {HeapOnly *p = new HeapOnly;p->destroy(); // HeapOnly h; return 0; }#include<iostream> using namespace std;// 私有重載new即可，限制了不能建立在new出的堆上 class StackOnly { public:StackOnly(){cout << "constructor." << endl;}~StackOnly(){cout << "destructor." << endl;} private:void* operator new (size_t); };int main(void) {StackOnly s; //okay StackOnly *p = new StackOnly; //wrongreturn 0; } 5、static_cast 和 dynamaic_cast 的用法。
#include<iostream> using namespace std;class Base { public:Base( ) { }~Base( ) { }virtual void Output(int i){cout<<"Base::Output value is "<<i<<endl;} };class Derived1 : public Base { public:Derived1( ) { }~Derived1( ) { }virtual void Output(int i){cout<<"Derived1::Output value is "<<i<<endl;}void Output2(){cout<<"Dervied1:Output2"<<endl;}};class Dervied2 : public Base { public:Dervied2() { }~Dervied2() { }virtual void Output(int i){cout<<"Dervied2::Output value is "<<i<<endl;}void Output2(){cout<<"Dervied2:Output2"<<endl;} };int main(void) {Base *p = new Dervied2;Derived1 *p1 = static_cast<Derived1*>(p);if(p1){p1->Output(1);p1->Output2();}cout<<"=========================\n";p1 = dynamic_cast<Derived1*>(p);if(p1){p1->Output(2);p1->Output2();}return 0; } 6、以下代碼的輸出是什么？
#include<iostream> using namespace std;class human { public:human(){ human_num++;}; //默認構造函數static int human_num; //靜態成員~human(){human_num--;print();}void print(){cout<<"human num is: "<<human_num<<endl;} };int human::human_num = 0; //類中靜態數據成員在外部定義,僅定義一次human f1(human x) {x.print();return x; }int main(void) {human h1; // 調用默認構造函數,human_num變為1h1.print(); // 打印Human_man:1human h2 = f1(h1); // 先調用函數f1(),輸出human_num:1,而后輸出human_num為0,h2.print(); // 打印輸出:human_num:0return 0; } 輸出：
1
1
0
0
－1
－2
－－－－－－－－－－－－－－－－－－－－－－－－－－－－
分析：
human h1; ? ? ? ??????????????? // 調用構造函數,---hum_num = 1;
h1.print();?????????????????????? // 輸出:"human is 1"
human h2 = f1(h1);???????? // 再調用f1(h1)的過程中,由于函數參數是按值傳遞對象,調用默認的復制構造函數，h2并沒有調用定義的構造函數。

總結

以上是生活随笔為你收集整理的四道面试题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。