Поисковые деревья. Определения -15
1.Для корневого дерева, заданного в каноническом виде ,
(где - отец вершины i и, если , то вершина i является корнем дерева, вершины нумеруются от 1 и ключ вершины совпадает с ее номером), определить, какие из следующих утверждений являются верными:
а)существует бинарное дерево, изоморфное данному дереву
+б) существует сбалансированное дерево, изоморфное данному дереву
в) существует идеально сбалансированное дерево, изоморфное данному дереву
+г) существует полное бинарное дерево, изоморфное данному дереву
+д) существует бинарное дерево, изоморфное данному дереву
е)нет верных утверждений
2. Для корневого дерева, заданного в каноническом виде ,
(где - отец вершины i и, если , то вершина i является корнем дерева, вершины нумеруются от 1 и ключ вершины совпадает с ее номером), определить, какие из следующих утверждений являются верными:
+а)существует бинарное дерево, изоморфное данному дереву
б) существует сбалансированное дерево, изоморфное данному дереву
в) существует идеально сбалансированное дерево, изоморфное данному дереву
г) существует полное бинарное дерево, изоморфное данному дереву
+д) существует бинарное дерево, изоморфное данному дереву
е)нет верных утверждений
3. Для корневого дерева, заданного в каноническом виде,
(где - отец вершины i и, если , то вершина i является корнем дерева, вершины нумеруются от 1 и ключ вершины совпадает с ее номером), определить, какие из следующих утверждений являются верными:
+а)существует бинарное дерево, изоморфное данному дереву
+б) существует сбалансированное дерево, изоморфное данному дереву
+в) существует идеально сбалансированное дерево, изоморфное данному дереву
+г) существует полное бинарное дерево, изоморфное данному дереву
+д) существует бинарное дерево, изоморфное данному дереву
е)нет верных утверждений
4. Для корневого дерева, заданного в каноническом виде,
(где - отец вершины i и, если , то вершина i является корнем дерева, вершины нумеруются от 1 и ключ вершины совпадает с ее номером), определить, какие из следующих утверждений являются верными:
+а)существует бинарное дерево, изоморфное данному дереву
+б) существует сбалансированное дерево, изоморфное данному дереву
+в) существует идеально сбалансированное дерево, изоморфное данному дереву
г) существует полное бинарное дерево, изоморфное данному дереву
+д) существует бинарное дерево, изоморфное данному дереву
е)нет верных утверждений
5. Для корневого дерева, заданного в каноническом виде ,
(где - отец вершины i и, если , то вершина i является корнем дерева, вершины нумеруются от 1 и ключ вершины совпадает с ее номером), определить, какие из следующих утверждений являются верными:
+а)существует бинарное дерево, изоморфное данному дереву
б) существует сбалансированное дерево, изоморфное данному дереву
в) существует идеально сбалансированное дерево, изоморфное данному дереву
г) существует полное бинарное дерево, изоморфное данному дереву
+д) существует бинарное дерево, изоморфное данному дереву
е)нет верных утверждений
6. Для корневого дерева, заданного в каноническом виде,
(где - отец вершины i и, если , то вершина i является корнем дерева, вершины нумеруются от 1 и ключ вершины совпадает с ее номером), определить, какие из следующих утверждений являются верными:
+а)существует бинарное дерево, изоморфное данному дереву
+б) существует сбалансированное дерево, изоморфное данному дереву
в) существует идеально сбалансированное дерево, изоморфное данному дереву
+г) существует полное бинарное дерево, изоморфное данному дереву
+д) существует бинарное дерево, изоморфное данному дереву
е)нет верных утверждений
7. Для корневого дерева, заданного в каноническом виде,
(где - отец вершины i и, если , то вершина i является корнем дерева, вершины нумеруются от 1 и ключ вершины совпадает с ее номером), определить, какие из следующих утверждений являются верными:
+а)существует бинарное дерево, изоморфное данному дереву
+б) существует сбалансированное дерево, изоморфное данному дереву
+в) существует идеально сбалансированное дерево, изоморфное данному дереву
+г) существует полное бинарное дерево, изоморфное данному дереву
+д) существует бинарное дерево, изоморфное данному дереву
е)нет верных утверждений
Хеш-таблицы -10
1.Для хранения ключей, поступающих последовательно из массива Х, используется закрытое хеширование с функцией , задающей линейную последовательность проб. Определить правильный порядок хранения ключей в хеш-таблице H.
а)
j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
2 |
3 |
12 |
31 |
22 |
4 |
5 |
15 |
44 |
100 |
б)
j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
22 |
12 |
2 |
3 |
31 |
5 |
15 |
4 |
44 |
100 |
+в)
j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
100 |
31 |
2 |
3 |
12 |
22 |
44 |
4 |
5 |
15 |
г)
j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
100 |
31 |
22 |
12 |
4 |
15 |
5 |
44 |
3 |
2 |
д)Нет правильного варианта ответа.
2.Для хранения ключей, поступающих последовательно из массива Х, используется закрытое хеширование с функцией , задающей линейную последовательность проб. Определить правильный порядок хранения ключей в хеш-таблице H.
а)
j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
100 |
0 |
1 |
99 |
1 |
33 |
4 |
13 |
8 |
19 |
б)
j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
0 |
1 |
1 |
8 |
13 |
4 |
33 |
100 |
99 |
19 |
в)
j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
0 |
1 |
1 |
33 |
13 |
100 |
99 |
4 |
8 |
19 |
|
|
|
|
|
|
|
|
|
|
|
+г)
j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
100 |
99 |
1 |
33 |
4 |
13 |
0 |
1 |
8 |
19 |
д)Нет правильного варианта ответа.
3.Для хранения ключей, поступающих последовательно из массива Х, используется закрытое хеширование с функцией , задающей линейную последовательность проб. Определить правильный порядок хранения ключей в хеш-таблице H.
+а)
j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
15 |
1 |
11 |
2 |
12 |
3 |
13 |
4 |
14 |
5 |
б)
j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
15 |
1 |
2 |
3 |
4 |
5 |
11 |
12 |
13 |
14 |
в)
j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
1 |
11 |
12 |
13 |
14 |
15 |
5 |
4 |
3 |
2 |
г)
j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
14 |
1 |
11 |
3 |
13 |
5 |
15 |
2 |
12 |
4 |
д)Нет правильного варианта ответа.
4.Для хранения ключей, поступающих последовательно из массива Х, используется закрытое хеширование с функцией , задающей линейную последовательность проб. Определить правильный порядок хранения ключей в хеш-таблице H.
а)
j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
99 |
1 |
11 |
111 |
40 |
20 |
0 |
10 |
999 |
9 |
+б)
j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
99 |
999 |
0 |
10 |
40 |
20 |
1 |
11 |
111 |
9 |
в)
j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
0 |
1 |
10 |
11 |
20 |
40 |
99 |
999 |
111 |
9 |
г)
j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
99 |
999 |
0 |
10 |
40 |
20 |
1 |
111 |
11 |
9 |
д)Нет правильного варианта ответа.
5. Для хранения ключей, поступающих последовательно из массива Х, используется закрытое хеширование с функцией , задающей линейную последовательность проб. Определить правильный порядок хранения ключей в хеш-таблице H.
а)
j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
0 |
1 |
2 |
8 |
9 |
13 |
14 |
17 |
22 |
109 |
б)
j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
0 |
1 |
2 |
13 |
14 |
9 |
22 |
17 |
8 |
109 |
в)
j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
109 |
1 |
2 |
13 |
14 |
22 |
0 |
17 |
8 |
9 |
+г)
j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
109 |
1 |
22 |
13 |
14 |
2 |
0 |
17 |
8 |
9 |
д)Нет правильного варианта ответа.
6. Для хранения ключей, поступающих последовательно из массива Х, используется закрытое хеширование с функцией , задающей линейную последовательность проб. Определить правильный порядок хранения ключей в хеш-таблице H.
+а)
j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
0 |
1 |
2 |
3 |
14 |
22 |
108 |
17 |
7 |
88 |
б)
j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
0 |
1 |
2 |
3 |
14 |
22 |
108 |
17 |
88 |
7 |
в)
j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
1 |
2 |
3 |
0 |
14 |
22 |
17 |
7 |
88 |
108 |
г)
j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
0 |
1 |
2 |
3 |
14 |
88 |
108 |
7 |
17 |
22 |
д)Нет правильного варианта ответа.
Рекуррентное соотношение -15.
1.Решить рекуррентное соотношение и указать для полученного многочлена коэффициент при старшей степени (задающей порядок роста функции, являющейся решением рекуррентного соотношения) и свободный член. Например, для правильным ответом являются коэффициенты 6 и -4.
а)1
б)2
+в)-2
г)4
д)-10
+е)12
ж)-18
з) Нет нужного варианта ответа.
2.Решить рекуррентное соотношение и указать для полученного многочлена коэффициент при старшей степени (задающей порядок роста функции, являющейся решением рекуррентного соотношения) и свободный член. Например, для правильным ответом являются коэффициенты 6 и -4.
а)-5
+б)-10
в)17
г)20
+д)27
е)37
ж)-40
з) Нет нужного варианта ответа.
3.Решить рекуррентное соотношение и указать для полученного многочлена коэффициент при старшей степени (задающей порядок роста функции, являющейся решением рекуррентного соотношения) и свободный член. Например, для правильным ответом являются коэффициенты 6 и -4.
а)1
+б)-2
в)-3
г)-11
д)12
е)-13
+ж)20
з) Нет нужного варианта ответа.
4.Решить рекуррентное соотношение и указать для полученного многочлена коэффициент при старшей степени (задающей порядок роста функции, являющейся решением рекуррентного соотношения) и свободный член. Например, для правильным ответом являются коэффициенты 6 и -4.
а)-1
б)10
+в)-16
г)23
+д)29
е)-32
ж)44
з) Нет нужного варианта ответа.
5.Решить рекуррентное соотношение и указать для полученного многочлена коэффициент при старшей степени (задающей порядок роста функции, являющейся решением рекуррентного соотношения) и свободный член. Например, для правильным ответом являются коэффициенты 6 и -4.
а)2
б)3
+в)-7
г)-20
д)102
+е)107
ж)-203
з) Нет нужного варианта ответа.
6.Решить рекуррентное соотношение и указать для полученного многочлена коэффициент при старшей степени (задающей порядок роста функции, являющейся решением рекуррентного соотношения) и свободный член. Например, для правильным ответом являются коэффициенты 6 и -4.
а)-3
+б)-6
в)9
г)10
+д)20
е)-30
ж)-40
з) Нет нужного варианта ответа.
7.Решить рекуррентное соотношение и указать для полученного многочлена коэффициент при старшей степени (задающей порядок роста функции, являющейся решением рекуррентного соотношения) и свободный член. Например, для правильным ответом являются коэффициенты 6 и -4.
а)2
+б)-4
в)6
г)-8
д)15
е)17
+ж)19
з) Нет нужного варианта ответа.
8.Решить рекуррентное соотношение и указать для полученного многочлена коэффициент при старшей степени (задающей порядок роста функции, являющейся решением рекуррентного соотношения) и свободный член. Например, для правильным ответом являются коэффициенты 6 и -4.
+а)-2
б)6
в)-8
+г)18
д)-32
е)64
ж)-100
з) Нет нужного варианта ответа.
9.Решить рекуррентное соотношение и указать для полученного многочлена коэффициент при старшей степени (задающей порядок роста функции, являющейся решением рекуррентного соотношения) и свободный член. Например, для правильным ответом являются коэффициенты 6 и -4.
+а)-1
б)3
в)-5
г)10
д)-52
е)101
+ж)201
з) Нет нужного варианта ответа.
10.Решить рекуррентное соотношение и указать для полученного многочлена коэффициент при старшей степени (задающей порядок роста функции, являющейся решением рекуррентного соотношения) и свободный член. Например, для правильным ответом являются коэффициенты 6 и -4.
+а)-1
б)-2
в)3
г)12
+д)18
е)21
ж)-36
з) Нет нужного варианта ответа.
11.Решить рекуррентное соотношение и указать для полученного многочлена коэффициент при старшей степени (задающей порядок роста функции, являющейся решением рекуррентного соотношения) и свободный член. Например, для правильным ответом являются коэффициенты 6 и -4.
а)1
б)-3
в)-4
+г)-10
д)16
е)19
ж)210
+з) Нет нужного варианта ответа.