Главная Вход в систему Регистрация
Задать вопрос Консультации Пользователи Форум
О системе Помощь
Задать вопрос экспертам
Консультация № 184645
02.12.2011, 09:35
100.00 руб.
0 2 1
Компьютеры Программирование
Здравствуйте! У меня возникли сложности с таким вопросом:
1. На базе каких структур данных удобно реализовать линейный двунаправленный список?
На базе динамического массива.
На базе двух стеков.
На базе дека.
2. Элементы множества хранятся в массиве в возрастающем порядке. Пусть множество содержит 12 элементов. Сколько операций сравнения достаточно выполнить, чтобы найти произвольный элемент в множестве или убедиться в его отсутствии?
Достаточно трех операций.
Достаточно четырех операций.
Достаточно пяти операций.
Достаточно шести операций.
3. Пусть требуется реализовать упорядоченный набор элементов, причем элемент может повторяться в наборе несколько раз. Элементы можно добавлять к набору и удалять из набора. Какая структура данных лучше всего подходит для этого?
Линейный двунаправленный список.
Множество, реализованное на базе упорядоченного бинарного дерева.
Нагруженное множество, реализованное на базе упорядоченного бинарного дерева.
Динамический массив.
4. Пусть у каждой нетерминальной вершины бинарного дерева есть ровно два сына. Пусть в дереве 123 вершины. Какова максимальная высота такого дерева? (Высотой дерева называется число вершин в пути максимальной длины от корня к некоторой терминальной вершине, включая первую и последнюю вершины пути.)
максимальная высота равна 8
максимальная высота равна 60
максимальная высота равна 61
максимальная высота равна 62
максимальная высота равна 63
5. Пусть в красно-черном дереве число черных вершин (не включая внешние, или нулевые, вершины) равно 21. Какое максимальное количество красных вершин может быть в дереве?
Максимальное количество красных вершин равно 9.
Максимальное количество красных вершин равно 10.
Максимальное количество красных вершин равно 11.
Максимальное количество красных вершин равно 41.
Максимальное количество красных вершин равно 42.
6. В хеш-реализации множества хеш-функция принимает 4 различные значения с равной вероятностью, т.е. множество представляется в виде объединения четырех непересекающихся подмножеств. Пусть множество содержит 4 элемента. Какова вероятность того, что все подмножества будут непустыми?
Вероятность равна 0.09375
Вероятность равна 0.25
Вероятность равна 0.75
Вероятность равна 0.90625
7. В хеш-реализации множества хеш-функция принимает 5 различных значений с равной вероятностью, т.е. множество представляется в виде объединения пяти непересекающихся подмножеств. Пусть множество содержит 3 элемента. Какова вероятность того, что все они попадут в разные подмножества?
Вероятность равна 0.42
Вероятность равна 0.48
Вероятность равна 0.52
Вероятность равна 0.625
Вероятность равна 0.8

Обсуждение

Неизвестный
02.12.2011, 10:57
общий
02.12.2011, 11:10
2. a -максимальное количество сравнивавший, b -количество элементов
a=int(log[$8322$]b)+1
log[$8322$]12[$8776$]3.5849
int(log[$8322$]12)+1=4
ответ: 4
давно
Лысков Игорь Витальевич
Посетитель
7438
7205
06.12.2011, 23:54
общий
это ответ
Здравствуйте, Заречнева Вера Михайловна!
1. На базе дека. Дек уже есть, по сути, список с двумя концами
2. Достаточно четырех операций. Т.к. log212 при округлении по избытку дает 4
3. Лучше подходит "линейный двунаправленный список"
4. Максимальная высота (123-1)/2 = 61
5. Максимальное число красных вершин 21*2 = 42. Когда у каждой черной вершины есть два потомка - красные вершины.
Черные листья, по условию, не считаем.
6. Всего есть 4 раскладки: 1-1-1-1, 1-1-2-0, 1-3-0-0, 4-0-0-0. Нас интересует одна 1-1-1-1. Значит вероятность = 1/4 = 0.25
7. Первый элемент попадет в "отличное" множество с вероятностью 5/5 = 1 (для него все "отличные")
Второй - с вероятностью 4/5, третий - 3/5. Значит общая вероятность равна 1 * 4/5 * 3/5 = 12/25 = 0.48
Об авторе:
"Если вы заметили, что вы на стороне большинства, —
это верный признак того, что пора меняться." Марк Твен
Форма ответа