第一部分(必做):
計算機科學基礎l
(單選)軟件設計中模塊劃分應該遵循的準則是:
低內(nèi)聚低耦合 B。高內(nèi)聚低耦合 C。低內(nèi)聚高耦合 D。高內(nèi)聚高耦合
(單選)最壞情況下時間復雜度不是n(n-1)/2的排序算法是:
快速排序 B。冒泡排序 C。直接插入排序 D。堆排序
3。 哈希表中解決沖突的方法通常可以分為open addressing和chaining兩類，請分別解釋這兩類沖突解決方法的大致實現(xiàn)原理
4。 簡單的鏈表結(jié)構(gòu)擁有很好的插入 刪除節(jié)點性能，但隨機定位(獲取鏈表第n個節(jié)點)操作性能不佳，請你設計一種改進型的鏈表結(jié)構(gòu)優(yōu)化隨機定位操作的性能，給出設計思路及其改進后隨機定位操作的時間復雜度
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é)點對應數(shù)字
if(null==node)
break;
for(child_node in node。children){
queue。push(child_node);
}
}
1234567
1245367
1376254
1327654
第二部分(選作): C/C++程序設計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){
}
假設某C工程包含a。c和b。c兩個文件,在a。c中定義了一個全局變量foo，在b。c中想訪問這一變量時該怎么做?
C++中的new操作符通常完成兩個工作，分配內(nèi)存及其調(diào)用相應的構(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應用與開發(fā)
寫出完成以下功能的Linux命令:
在當前目錄及其子目錄所有的。cpp文件中查找字符串"example"，不區(qū)分大小寫;
使用sed命令，將文件xyz中的單詞AAA全部替換為BBB;
用一條命令創(chuàng)建aa bb cc三個子目錄
mount cdrom。iso至/dev/cdrom目錄
5) 設置ulimit使得程序在Segment fault等嚴重錯誤時可以產(chǎn)生coredump;
2。 設umask為002，則新建立的文件的權(quán)限是什么?664
A。 -rw-rwr—
B。 rwxrwx-w-
C。 -------w-
D。 rwxrwxr-x
上面第三題，aa bb cc 目錄是嵌套的子目錄么，要是同一級的話應該下面這樣
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上設置一個斷點
5) 設置一個斷點，當表達式expr的值被改變時觸發(fā)
