第一部分(必做):

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

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

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

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

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

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

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

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

　　6。 以下是一個(gè)tree的遍歷算法，queue是FIFO隊(duì)列，請(qǐng)參考下面的tree，選擇正確的輸出。

　　1

　　/ \

　　2 3

　　/ \ / \

　　4 5 6 7

　　queue。push(tree。root)

　　while(true){

　　node=queue。pop();

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

　　if(null==node)

　　break;

　　for(child_node in node。children){

　　queue。push(child_node);

　　}

　　}

　　1234567

　　1245367

　　1376254

　　1327654

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

　　有三個(gè)類(lèi)A B C定義如下，請(qǐng)確定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;

　　};

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

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

　　}

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

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

　　請(qǐng)問(wèn):

　　如何讓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? 并舉例說(shuō)明

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

　　寫(xiě)出完成以下功能的Linux命令:

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

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

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

　　mount cdrom。iso至/dev/cdrom目錄

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

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

　　A。 -rw-rwr—

　　B。 rwxrwx-w-

　　C。 -------w-

　　D。 rwxrwxr-x

　　上面第三題，aa bb cc 目錄是嵌套的子目錄么，要是同一級(jí)的話應(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。 寫(xiě)出完成以下功能的gdb命令(可以使用命令簡(jiǎn)寫(xiě)形式):

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

　　2) 查看線程信息

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

　　4) 在類(lèi)ClassFoo的函數(shù)foo上設(shè)置一個(gè)斷點(diǎn)

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