- 相關(guān)推薦
網(wǎng)易2015校招筆試題
、佟⑺惴
最壞情況下時(shí)間復(fù)雜度為O(nlogn)的排序算法有( )
A:基數(shù)排序
B:歸并排序
C:堆排序
D:快速排序
答案:BC
解析:基數(shù)排序是考慮多個(gè)關(guān)鍵字的排序方法,同樣關(guān)鍵字內(nèi)可以選擇任意一種合適的排序,關(guān)鍵字之間再次排序,時(shí)間復(fù)雜度可以寫成O(n*r),其中,n為數(shù)據(jù)數(shù)目,r為基的數(shù)目。歸并排序是基于分治策略的方法,其基本點(diǎn)是合并兩個(gè)有序的隊(duì)列,其最壞,平均和最好的時(shí)間復(fù)雜度都是 O(nlogn),但是需要一個(gè)輔助的空間。堆排序是借助于堆的排序,利用堆的性質(zhì),堆排序最壞,平均和最好時(shí)間復(fù)雜度都是 O(nlogn)?焖倥判蛞彩腔诜种尾呗缘姆椒,最壞情況的時(shí)間復(fù)雜度是O(n^2),平均時(shí)間和最好時(shí)間復(fù)雜度是O(nlogn)。
、、數(shù)據(jù)結(jié)構(gòu)
以下說法正確的有( )
A:在m階B-樹中,所有的非終端節(jié)點(diǎn)至少包含m/2個(gè)節(jié)點(diǎn)
B:若一個(gè)葉節(jié)點(diǎn)是某二叉樹中的中序遍歷的最后一個(gè)節(jié)點(diǎn),同時(shí)它也是該二叉樹前序遍歷的最后一個(gè)節(jié)點(diǎn)
C:插入排序,堆排序,快速排序算法中,快速排序的速度是最快的,所需的附加空間也是最少的
D:n個(gè)數(shù)中已知有k個(gè)關(guān)鍵字hash值相同,若用線性探測(cè)法將他們存入散列表中,至少需要進(jìn)行k(k+1)/2次探測(cè)
答案:B
解析:B-樹是一種多叉平衡查找樹。一個(gè)m階的B樹中,根節(jié)點(diǎn)至少有2個(gè)孩子;除了根節(jié)點(diǎn)和葉子節(jié)點(diǎn)外,其他內(nèi)部節(jié)點(diǎn)至少包含⌈ m/2⌉個(gè)孩子節(jié)點(diǎn)。若考慮根節(jié)點(diǎn)可以只有2個(gè)孩子,則選項(xiàng)A不正確。二叉樹中序遍歷的順序是左子樹-根-右子樹,前序遍歷的順序是根-左子樹-右子樹。若中序遍歷的最后結(jié)點(diǎn)是葉結(jié)點(diǎn),則它的父結(jié)點(diǎn)是它的前驅(qū)遍歷結(jié)點(diǎn),該葉結(jié)點(diǎn)是父節(jié)點(diǎn)的右孩子;因此在前序遍歷時(shí),該葉節(jié)點(diǎn)必然仍然是最后遍歷的?焖倥判蛐枰o助空間,最好和平均情況下的空間復(fù)雜度為O(logn)。在哈希表中存入第一個(gè)同義關(guān)鍵字后,后面至少連續(xù)有k-1個(gè)單元為空,故按照線性探測(cè)法可以依次存入剩余的k-1個(gè)關(guān)鍵字,至少需要1+2+ ...+ k-1= k(k-1)/2 次。
【網(wǎng)易校招筆試題】相關(guān)文章:
網(wǎng)易筆經(jīng)11-11
銀行校招筆試題目11-21
搜狗2015校招筆試題11-22
阿里巴巴校招筆試題,試題分享02-25
?低曅U泄P試題11-28
阿里巴巴校招筆試題11-29
阿里巴巴校招筆試題目11-29
浙商銀行2014校招筆試題11-21
網(wǎng)易北郵筆試題11-21
網(wǎng)易游戲筆試題目11-30