02 апреля 2009

Занятие 2 апреля: разминка

Вопрос 1.

Что делает метод hasCycle(), при условии что длина списка равна N?

01: class Node {
02:
Node next;
03:
Object value;
04:
}
05:
06:
class List {
07:
Node first;
08:
09:
boolean hasCycle() {
10:
if (first == null) return false;
11:
12:
int stepCount = 1;
13:
Node t1 = first;
14:
Node t2 = first;
15:
16:
while (true) {
17: t1
= t2;
18: stepCount
*= 2;
19:
for (int i = 0; i < stepCount; i++) {
20: t2
= t2.next;
21:
if (t2 == null) return false;
22:
if (t2 == t1) return true;
23:
}
24:
}
25:
}
26:
}


  1. Проверяет наличие цикла за время O(log(N))
  2. Проверяет наличие цикла за время O(N)
  3. Проверяет наличие цикла за время O(N*log(N))
  4. Проверяет наличие цикла за время O(N^2)
  5. Иногда тупо зависает в бесконечном цикле
Вопрос 2

Какая структура данных больше подходит для реализации обхода в ширину?

  1. FIFO
  2. LIFO
  3. GIGO