網易校招筆試題

時間：2024-06-10 02:37:08 面試筆試我要投稿

相關推薦

網易2015校招筆試題

　�、佟⑺惴�

網易2015校招筆試題

　　最壞情況下時間復雜度為O(nlogn)的排序算法有( )

　　A：基數排序

　　B：歸并排序

　　C：堆排序

　　D：快速排序

　　答案：BC

　　解析：基數排序是考慮多個關鍵字的排序方法，同樣關鍵字內可以選擇任意一種合適的排序，關鍵字之間再次排序，時間復雜度可以寫成O(n*r)，其中，n為數據數目，r為基的數目。歸并排序是基于分治策略的方法，其基本點是合并兩個有序的隊列，其最壞，平均和最好的時間復雜度都是 O(nlogn)，但是需要一個輔助的空間。堆排序是借助于堆的排序，利用堆的性質，堆排序最壞，平均和最好時間復雜度都是 O(nlogn)�？焖倥判蛞彩腔诜种尾呗缘姆椒�，最壞情況的時間復雜度是O(n^2)，平均時間和最好時間復雜度是O(nlogn)。

　�、�、數據結構

　　以下說法正確的有( )

　　A：在m階B-樹中，所有的非終端節點至少包含m/2個節點

　　B：若一個葉節點是某二叉樹中的中序遍歷的最后一個節點，同時它也是該二叉樹前序遍歷的最后一個節點

　　C：插入排序，堆排序，快速排序算法中，快速排序的速度是最快的，所需的附加空間也是最少的

　　D：n個數中已知有k個關鍵字hash值相同，若用線性探測法將他們存入散列表中，至少需要進行k(k+1)/2次探測

　　答案：B

　　解析：B-樹是一種多叉平衡查找樹。一個m階的B樹中，根節點至少有2個孩子;除了根節點和葉子節點外，其他內部節點至少包含⌈ m/2⌉個孩子節點。若考慮根節點可以只有2個孩子，則選項A不正確。二叉樹中序遍歷的順序是左子樹-根-右子樹，前序遍歷的順序是根-左子樹-右子樹。若中序遍歷的最后結點是葉結點，則它的父結點是它的前驅遍歷結點，該葉結點是父節點的右孩子;因此在前序遍歷時，該葉節點必然仍然是最后遍歷的。快速排序需要輔助空間，最好和平均情況下的空間復雜度為O(logn)。在哈希表中存入第一個同義關鍵字后，后面至少連續有k-1個單元為空，故按照線性探測法可以依次存入剩余的k-1個關鍵字，至少需要1+2+ ...+ k-1= k(k-1)/2 次。

【網易校招筆試題】相關文章：

網易筆經11-11