HackerRank A Basic Data Structures and Algorithms Quiz #1

Source

HackerRank A Basic Data Structures and Algorithms Quiz #1
problem statement(コンテストページ)

問題概要

以下の10問のクイズに答える問題

  1. クイックソートの最悪時間計算量は?
  2. マージソートの最悪時間計算量は?
  3. マージソートの平均時間計算量は?
  4. $n$ 要素からなるヒープを作るのに必要な時間計算量は?
  5. ヒープは2分探索木の一種である,真か偽か?
  6. ダイクストラのノードをたどる順番は以下のどれと似ているか? BFS,DFS,トポロジカルソート,どれでもない
  7. スタックは2つのキューで作れる,キューは2つのスタックで作れる,はそれぞれ真か偽か?(push/popなどの平均時間計算量は中にある要素数に依存してはいけない)
  8. UnionFindは以下のどれに応用され使われるか? DFS,BFS,最小全域木の計算,全節点対の最短路の計算
  9. 二分探索木で,あるkeyを探すのに必要な最悪計算量は?
  10. 'make'/'ant build'が基本的なコンポーネントであるグラフ理論のアルゴリズムは次のうちどれか? 最大流,最小パス,最小全域木,二部マッチング,トポロジカルソート

解法

正直良くわからないのや納得出来ないのもあるが以下の通り.

  1. $O(n^2)$
  2. $O(n \log n)$
  3. $O(n \log n)$
  4. $O(n)$
  5. BFS
  6. キューを2つのスタックで作ることのみできる
  7. 最小全域木の計算
  8. $O(n)$
  9. トポロジカルソート

スパゲッティ (?) なソースコード

1:c
2:b
3:b
4:a
5:b
6:a
7:a
8:c
9:a
10:e

Current time: 2017年07月24日15時46分04秒
Last modified: 2014年05月11日15時10分17秒 (by laycrs)
Tags: Competitive_Programming HackerRank
トップページに戻る

Logged in as: unknown user (not login)

ログイン: