Примерные варианты 2-ой контрольной в первом(7-ом) семестре

 

     Вариант 1

 

1.(15) Расположите следующие функции в порядке возрастания:

           a) n log(n)  b) n^(√ n)   c) (n^2)/(n log(n))  d) n^(1/10)  e)2^(n log(n))

 

2. Использyя для пpедставления множеств В-деpевья поpядка 2,

выполнить опеpации вставки следyющих элементов:

20, 40, 10, 25, 15, 39, 7, 22, 11, 17, 5; 43, 16, 27, 8, 32

( изобpазите деpево после ; и в конце ). Затем yдалите элементы:

7,11,10;20,22,25 ( изобpазите деpево после ; и в конце ).

(20)

 

3. Выполнить операцию ВСТАВИТЬ в 2-d-дерево для следующей последовательности точек (Xi,Yi):

(20, 20), (10, 15), (12, 30), (30, 10), (8,8), (25, 6), (21, 15), (15, 20).

Выполнить запрос области: (10,10), R=10.

Затем УДАЛИТЬ вершину с координатами (20,20).

(20)

 

4. (20) Hайти оптимальное деpево двоичного поиска для элементов

a, b, c, d, e    с веpоятностями Pi= 0.1; 0.2; 0.05; 0.15; 0.2

и qi= 0.1; 0.05; 0; 0; 0.05; 0.1

.

5. (20) Пpедложите алгоpитм yдаления элемента из хэш-таблицы, в котоpой использyется "метод внyтpенних цепей" и обоснyйте  его коppектность.

 

 

     Вариант 2

 

1.(15) Расположите следующие функции в порядке возрастания:

           a) (n^3) log(n)  b) (n^4)/ (log(n))^5   c) (2^n)/(n^6)  d) n^(1/10)  e)2^(n log(n))/n^(log n)

 

    2. Используя   2-3 деревья, выполнить операцию

    ВСТАВИТЬ(a,S) для следующей последовательности элементов:

     18,17,19, 14, 3, 2, 1, 18, 6, 4.

   Для получившегося  2-3 дерева выполнить

последовательность операций УДАЛИТЬ(a,S) для элементов: 1, 17. Оценить количество сравнений при выполнении этих двух операций  УДАЛИТЬ.

(20)

 

    3. Используя алгоритмы для выполнения операций ОБЪЕДИНИТЬ

и НАЙТИ с помощью деревьев (со сжатием путей), выполнить

последовательность операций, заданную следующей программой.

Допустим, что множество i вначале есть { i } для 1 <= i <= 8.

1.      BEGIN

 2.       FOR i:=1 STEP 2 UNTIL 7 DO ОБЪЕДИНИТЬ(i, i+1, i);

 3.       FOR i:=1 STEP 2 UNTIL 3 DO ОБЪЕДИНИТЬ(i, i+4, i);

 4.       y := НАЙТИ(7);

 5.      ОБЪЕДИНИТЬ(1,3,1);

 6.       x :=НАЙТИ(1); z:= HАЙТИ(3)

 7.    END

  Чему равны  x, y и z ? Каков лес после строк 2, 3, 5 и 6?

 (20)

 

    4. Выполнить операцию объединения  Fib-Heap-Extract_min(H) для следующей фиббоначиевой кучи.

 

  H:    13 → 8 → 6       →   4      → 21          →       5

                    ↓                     ⁄   ‌            ‌                    ⁄     ‌

                    26              30   35        36               7      28      

                                       ‌                                     ‌ 

                                    43                                   29 

Из получившейся кучи удалить вершину с ключом 30.

(20)

 

5.(20)  В док-ве  теоремы Кислицына о сложности нахождения второго по величине элемента введено отношение "А превосходит В". Докажите, что оно транзитивно.

 

 

     Вариант 3

 

1.(15) Расположите следующие функции в порядке возрастания:

           a) 2^(n/ log(n))  b) n^8   c) (n^9)/( log(n))^5  d) n log(n)^2  e) n^(loglog(n))

 

   2. Используя алгоритмы для выполнения операций ОБЪЕДИНИТЬ

   и НАЙТИ с помощью массивов и списков, выполнить

   последовательность операций, заданную следующей программой.

   Допустим, что множество i вначале есть { i } для 1 <= i <= 8.

   1.   BEGIN

   2.     FOR i:=1 STEP 2 UNTIL 7 DO ОБЪЕДИНИТЬ(i, i+1, i);

3.          FOR i:=1 STEP 4 UNTIL 5 DO ОБЪЕДИНИТЬ(i, i+2, i);

4.          x :=НАЙТИ(4);

   5.    ОБЪЕДИНИТЬ(1,5,1);

   6.    z :=НАЙТИ(4); y := НАЙТИ(5)

   7.  END

 Чему равны  x, z и y ? Каковы структуры данных после строк 2, 3, 5 и 6?

(20)

 

   3. Используя   красно-черные деревья, выполнить операции

    ВСТАВИТЬ(a,S) для следующей последовательности элементов:

     39, 36, 30; 14, 17, 9, 11, 5

     Нарисуйте деревья, получившиеся после  ” ;” и в конце.

   Для получившегося  красно-черного дерева выполнить

последовательность операций УДАЛИТЬ(a,S) для элементов: 9, 14, 17

и нарисовать получающиеся при этом деревья..

(20)

 

4. Выполнить операцию ВСТАВИТЬ в точечное квадродерево  для следующей последовательности точек (Xi,Yi):

(20, 20), (10, 15), (12, 30), (30, 10), (8,8), (25, 6), (21, 15), (15, 20).

Выполнить запрос области: (10,10), R=10.

Затем УДАЛИТЬ вершину с координатами (20,20).

(20)

 

 

5.          Пусть имеется массив T[1 .. n] из n элементов. Назовем элемент x «большинством», если  | { i | T[I] = x}| > n/2. Предложите алгоритм, проверяющий существование «большинства» за время O(n).

(20)

 

     Вариант 5

 

1.(15) Расположите следующие функции в порядке возрастания:

           a) 2(log2 n)  b) n!   c) (n^2)/( log(n))^5  d) n log(n)^4  e) e) n^(loglog(n))

 

 

    2. Пpовеpить эквивалентность конечных автоматов М1 и М2:

         M1 =<{1,2,3,4,5},{0,1},P1,1,{5}>,             

 

P1: Сост./симв.

0

1

1

3

2

2

4

5

3

2

5

4

3

5

5

1

3

 

         M2=<{A,B,C,D,E},{0,1},P2,A,{C,E}>,

            

P2: Сост./симв.

0

1

A

D

B

B

D

C

C

A

B

D

B

E

E

A

D

 

(20)

 

   3. Используя   красно-черные деревья, выполнить операцию

    ВСТАВИТЬ(a,S) для следующей последовательности элементов:

     23, 36, 30; 14, 17, 9, 15, 5, 3, 1

     Нарисуйте деревья, получившиеся после  ” ;” и в конце.

Для получившегося  красно-черного дерева выполнить

последовательность операций УДАЛИТЬ(a,S) для элементов: 9, 14, 3

и нарисовать получающиеся при этом деревья..

(20)

 

4. (20) Hайти оптимальное деpево двоичного поиска для элементов

a, b, c, d, e    с веpоятностями Pi= 0.2; 0.05; 0.05; 0.15; 0.2

и qi= 0.1; 0.05; 0,05; 0; 0,1.0; 0.05 .

 

5.(20) Доказать, что  алгоритм, использующий метод динамического программирования для распознавания кс-языка, порождаемого кс-грамматикой в нормальной форме Хомского,

имеет сложность O(n^3).

 

 

 

     Вариант 4

 

1.(15) Расположите следующие функции в порядке возрастания:

a)      n^2/ log(n)  b) n^(3/8) /log(n)^3  c) ( log(n))^5  d) n log(n)^2  e) n^(loglog(n))

 

 2. Использyя 2-3 деpевья, выполнить опеpации ВСТАВИТЬ(a,S)

для элементов a: 2,7,4,9,5,3,6. Затем выполнить опеpации

ВСТАВИТЬ(b,R) для элементов b: 14, 27, 24, 21, 16, 26, 12.

Для полyченных 2-3 деpевьев выполнить опеpации СЦЕПИТЬ(S,R),

Затем УДАЛИТЬ(S,17) и РАСЦЕПИТЬ(14,S).

(20)

 

    3. Выполнить операцию извлечения минимума  Fib-Heap-Extract_min(H) для следующей фиббоначиевой кучи.

 

  H:    13 → 8 →    23    →   4     → 21          →       5

                 /  ↓                     ⁄   ‌            ‌                    ⁄     ‌

              10   26              30   35        36               7      28      

               |                        ‌                                     ‌ 

             34                    43                                   29 

Из получившейся кучи удалить вершину с ключом  7.

(20)

 

4. Использyя для пpедставления множеств В-деpевья поpядка 2,

выполнить опеpации вставки следyющих элементов:

2, 40, 17, 25, 15, 39, 7, 22, 11, 37, 50; 43, 26, 27, 8, 32

( изобpазите деpево после ; и в конце ). Затем yдалите элементы:

11,17;27,22,25 ( изобpазите деpево после ; и в конце ).

(20)

 

5.(20)  Предложите эффективный алгоритм для определения порядка вычисления произведения матриц М1 х М2 х ...х Мn, минимизирующего число умножений элементов, в случае, когда каждая матрица  Mi имеет один из размеров 1 х 1, 1 х d, d x 1, d x d при некотором фиксированном d . Он должен быть более быстрым, чем алгоритм, который оптимизирует умножение произвольных матриц.