第一部分(必做):

　　計算機科學(xué)基礎(chǔ)l

　　(單選)軟件設(shè)計中模塊劃分應(yīng)該遵循的準則是:

　　低內(nèi)聚低耦合 B。高內(nèi)聚低耦合 C。低內(nèi)聚高耦合 D。高內(nèi)聚高耦合

　　(單選)最壞情況下時間復(fù)雜度不是n(n-1)/2的排序算法是:

　　快速排序 B。冒泡排序 C。直接插入排序 D。堆排序

　　3。 哈希表中解決沖突的方法通�？梢苑譃閛pen addressing和chaining兩類，請分別解釋這兩類沖突解決方法的大致實現(xiàn)原理

　　4。 簡單的鏈表結(jié)構(gòu)擁有很好的插入 刪除節(jié)點性能，但隨機定位(獲取鏈表第n個節(jié)點)操作性能不佳，請你設(shè)計一種改進型的鏈表結(jié)構(gòu)優(yōu)化隨機定位操作的性能，給出設(shè)計思路及其改進后隨機定位操作的時間復(fù)雜度

　　5。 什么是NP問題?列舉典型的NP問題(至少兩個)?對于一個給定的問題你通常如何判斷它是否為NP問題?

　　6。 以下是一個tree的遍歷算法，queue是FIFO隊列，請參考下面的tree，選擇正確的輸出。

　　1

　　/ \

　　2 3

　　/ \ / \

　　4 5 6 7

　　queue。push(tree。root)

　　while(true){

　　node=queue。pop();

　　output(node。value);//輸出節(jié)點對應(yīng)數(shù)字

　　if(null==node)

　　break;

　　for(child_node in node。children){

　　queue。push(child_node);

　　}

　　}

　　1234567

　　1245367

　　1376254

　　1327654

　　第二部分(選作): C/C++程序設(shè)計l

　　有三個類A B C定義如下，請確定sizeof(A) sizeof(B) sizeof(C)的大小順序，并給出理由

　　struct A{

　　A() {}

　　~A() {}

　　int m1;

　　int m2;

　　};

　　struct B{

　　B() {}

　　~B() {}

　　int m1;

　　char m2;

　　static char m3;

　　};

　　struct C{

　　C() {}

　　virtual~C() {}

　　int m1;

　　hort m2;

　　};

　　請用C++實現(xiàn)以下print函數(shù),打印鏈表I中的所有元素，每個元素單獨成一行

　　void print(const std::list &I){

　　}

　　假設(shè)某C工程包含a。c和b。c兩個文件,在a。c中定義了一個全局變量foo，在b。c中想訪問這一變量時該怎么做?

　　C++中的new操作符通常完成兩個工作，分配內(nèi)存及其調(diào)用相應(yīng)的構(gòu)造函數(shù)初始化

　　請問:

　　如何讓new操作符不分配內(nèi)存，只調(diào)用構(gòu)造函數(shù)?

　　這樣的用法有什么用?

　　下面這段程序的輸出是什么?為什么?

　　class A{

　　public:

　　A(){p();}

　　virtual void p(){print("A")}

　　virtual ~A(){p();}

　　};

　　class B{

　　public:

　　B(){p();}

　　void p(){print("B")}

　　~B(){p();}

　　};

　　int main(int，char*){

　　A* a=new B();

　　delete a;

　　}

　　6。 什么是C++ Traits? 并舉例說明

　　第四部分(選作): Linux應(yīng)用與開發(fā)

　　寫出完成以下功能的Linux命令:

　　在當(dāng)前目錄及其子目錄所有的。cpp文件中查找字符串"example"，不區(qū)分大小寫;

　　使用sed命令，將文件xyz中的單詞AAA全部替換為BBB;

　　用一條命令創(chuàng)建aa bb cc三個子目錄

　　mount cdrom。iso至/dev/cdrom目錄

　　5) 設(shè)置ulimit使得程序在Segment fault等嚴重錯誤時可以產(chǎn)生coredump;

　　2。 設(shè)umask為002，則新建立的文件的權(quán)限是什么?664

　　A。 -rw-rwr—

　　B。 rwxrwx-w-

　　C。 -------w-

　　D。 rwxrwxr-x

　　上面第三題，aa bb cc 目錄是嵌套的子目錄么，要是同一級的話應(yīng)該下面這樣

　　1 #grep -i -r example 。/*。cpp

　　2 #sed 's/AAA/BBB/g ' xyz

　　3 #mkdir aa bb cc

　　4 #mount -o loop 。/cdrom。iso /mnt/cdrom

　　5 C

　　3。 用戶HOME目錄下的。bashrc和。bash_profile文件的功能有什么區(qū)別?

　　4。 寫出完成以下功能的gdb命令(可以使用命令簡寫形式):

　　1) 使用gdb調(diào)試程序foo，使用coredump文件core。12023;

　　2) 查看線程信息

　　3) 查看調(diào)用堆棧

　　4) 在類ClassFoo的函數(shù)foo上設(shè)置一個斷點

　　5) 設(shè)置一個斷點，當(dāng)表達式expr的值被改變時觸發(fā)