一、單選題
1、在常用的網絡協議中,___是面向連接的、有重傳功能的協議。
A、IP B、TCP C、UDP D、DXP
2、500張多米諾骨牌整齊地排成一列,依順序編號為1、2、3……499、500。第一次拿走所有奇數位置上的骨牌,第二次再從剩余骨牌中拿走所有奇數位置上的骨牌,依此類推。請問最後剩下的一張骨牌的編號是多少?
A、128 B、250 C、256 D、500
3、兩個線程並發執行以下代碼,假設a是全局變量,那麼以下輸出______是不可能的?
++
A、3 2 B、2 3 C、3 3 D、2 2
4、某系統采用36進制數表示一字符串,36個字符0-9 a-z分別由數字0~35表示,則10進制數字872581表示字符串____?
A、imac B、ipad C、iphone D、ipod
5、以下代碼輸出的是__?
foo( x,(x<=||y<=) *foo(x-,y/<<foo(,)<<endl;
A、81 B、27 C、9 D、3
6、以下數據結構說法,錯誤的是___?
A、紅黑樹插入操作的平均時間復雜度為O(logn),最壞時間復雜度為O(logn)
B、B+樹插入操作的平均時間復雜度為O(logn),最壞時間復雜度為O(logn)
C、Hash表插入操作的平均時間復雜度為O(logn),最壞時間復雜度為O(n)
D、排序鏈表插入操作的平均時間復雜度為O(n),最壞時間復雜度為O(n)
7、哈弗曼編碼是一種無損二進制熵編碼算法,其加權路徑長度最小,字符串“alibaba”的二進制哈弗曼編碼有___位(bit)
A、11 B、12 C、13 D、14
8、節點按中序遍歷為xyz的二叉樹可能有幾種?
A、2 B、3 C、4 D、5
9、在4個元素的集合上可定義的互不相同的劃分有___個。
A、14 B、15 C、16 D、17
10、下列關於C語言中指針的說法錯誤的是:___
A、指針的值是一個地址
B、非法指針是指該指針的值不是一個已經分配的內存地址
C、兩個指向同類型地址的指針之間做減法是沒有意義的
D、指針的指針占用的內存空間和其他指針占用的內存空間相同
二、不定項選擇
11、設A、B、C為任意集合,下面的命題為真的是____
A、如果A-B=∅,則A=B
B、如果A-C=B-C,則A∩^C=B∩^C
C、如果A∪B=A∪C,則B=C
D、如果A∩B=A∩C,則B=C
E、∅是∅的子集
12、一個棧的入棧序列為ABCDE,則不可能的出戰序列為___
A、ECDBA B、DCEAB C、DECBA D、ABCDE E、EDCBA
13、以下關於內存洩漏說法正確的是____(注:此題不太確定,歡迎補充)
A、內存洩漏是操作系統內存管理出錯導致的問題
B、單線程程序不可能內存洩漏
C、如果一個進程在運行過程中占用的內存無限制上升,那麼該進程有內存洩漏
D、只要進程在退出之前釋放了所有分配的內存,那麼就不會內存洩漏
E、內存洩漏是僅僅出現在C/C++程序的問題,Java程序不會內存洩漏
14、關於進程和線程,下列說法正確的是___
A、線程是資源分配和擁有的單位
B、線程和進程都可並發執行
C、在linux系統中,線程是處理器調度的基本單位
D、線程的粒度小於進程,通常多線程比多進程並發性更高
E、不同的線程共享相同的棧空間
第三項目組 填空與題目
15、某遞歸算法的算法復雜度滿足如下關系:T(n)=0,(n<=1);T(n )=1+T(n/2)+n2,(n>=2),那麼該算法復雜度表示為大0為:
16、某種物理機一年的無故障概率為p,每台物理機經由過程虛擬技巧可以虛擬出v台虛擬機,假定在物理機沒呈現故障的景象下虛擬機不會呈現故障,那麼每台虛擬機一年無故障的概率為___p___。若是有m台如許的物理機,虛擬出mv台虛擬機,經由過程某種分布式容錯技巧,可以使基於這些虛擬機搭建的辦事只要有一台虛擬機無故障,這個辦事便可以無故障。那麼這個辦事一年的無故障概率為__1-(1-p)m_。若是想經由過程同樣數量的虛擬機實現更高的無故障概率,但不限制物理機的數量,可以采取的辦法是:通過增加物理機,然後降低每台物理機虛擬出虛擬機的數量
17、宿捨內5個同學一起玩對戰游戲,每場比賽有一些人作為紅方,另一些人作為藍方,請問至少需要多少場比賽,才能使任意兩個人之間有一場紅方對藍方和一場藍方對紅方的比賽?請寫出思路及成果。
18、讀取並處理一個文件中的記錄,每條記錄處理會產生一個對應的結果,不同記錄之間的處理過程之間互不依賴,結果輸出到另一個文件中,某程序猿實現了該處理程序的單線程版本,運行時發現CPU應用率達到80%。
(1)為何CPU應用率不是100%?
(2)假定程序運行的機器的核數在4到16不等,如何設計程序,使該處理程序運行的最快?
(3)在一個n核機器上,速度最快是原來程序的多少倍?
19、請實現一個程序,能對點分字符串按段翻轉。如"www.taobao.com”翻轉為“com.taobao.www”,”sports.sina.com.cn”翻轉為”cn.com.sina.sports”。請求時間復雜度為O(n),空間復雜度為O(1),結果保存在參數指針所指的空間中。
解答:
#include <iostream><cstring> ReverseString( *str, (str == NULL || len <= *p = str + len - (str < t = **str = **p =++-- ReverseWord( *(str == len = *p =(*str != (*str >= && *str <= && *str != ++-= ++ main( str[] = <<str<<
第四項目組 綜合題
某B2C網站有1億用戶和200萬商品,每一個用戶都有自己喜愛若干件商品,若是兩個用戶都喜好同一件商品,我們定義中兩個用戶有一個“同好商品”,“同好度”為兩個用戶的同好商品數和這兩個用戶中至少有一人喜好的商品數的比值。同好度衡量了兩個用戶之間的商品喜好的接近程度,這在商品推薦,SNS等領域有著重要用途。
請設計一個算法,計算每一個用戶的同好用戶集合及同好度。
輸入數據:多個文件,每個文件的數據有多行,每一行的數據格式如下:用戶ID喜好的商品ID1 喜好的商品ID2 .......喜好的商品n,此頂用戶ID和商品ID均為32位整數,中心以空格分隔。
如:
16 1001 1002 3003
輸出數據:一個或多個文件,每一行的數據格局如下:
用戶ID 同好用戶ID1:同好度 同好用戶ID2:同好度......同好用戶IDn:同好度
中心以空格隔開。算法可以描述為偽代碼。