игра брюс 2048
Главная / Алгоритмы и дискретные структуры / Алгоритмы и структуры данных поиска / Тест 5

Алгоритмы и структуры данных поиска - тест 5

Упражнение 1:
Номер 1 
Пусть известна последовательность из n ключей, представленная массивом A. Что называется k-ой порядковой статистикой?

Ответ:

 (1) k-ый элемент в массиве A 

 (2) элемент в массиве A, встречающийся k раз 

 (3) k-ый в порядке возрастания ключ в массиве A 

 (4) частота встречаемости k-го элемента в массиве A 

Номер 2 
Какое математическое ожидание времени работы у алгоритма поиска k-ой порядковой статистики (Random-варианта)?

Ответ:

 (1) O(log N) 

 (2) O(N) 

 (3) O(N * log N) 

 (4) O(N2) 

Номер 3 
Модификация какого алгоритма ипользуется для рандомизированного способа поиска порядковой статистики?

Ответ:

 (1) Merge-sort 

 (2) сортировка вставкой 

 (3) Quick-sort 

Номер 4 
За счет чего происходит оптимизация по времени работы для рандомизированного способа поиска порядковой статистики по сравнению со стандартным алгоритмом быстрого поиска?

Ответ:

 (1) массив рекурсивно делится на более чем две части 

 (2) разделитель для рекурсивного деления ищется по медиане 

 (3) массив рекурсивно делится на две равные части, после чего поиск производится только для той части, которая содержит искомый элемент 

 (4) после рекурсивного разделения массива на две части следующий вызов производится только для той части, которая содержит искомый элемент 

Упражнение 2:
Номер 1 
В представленном ниже псевдокоде алгоритма поиска порядковой статистики что находится на пропущенном месте?

	Random-select(A, k)
	задать λ
	...
	если k <= |A1|:
		вернуть Random-select(A1, k)
	иначе:
		вернуть Random-select(A2, k - |A1|)

Ответ:

 (1) пустая строка, ничего не пропущено 

 (2) разделить (A, λ) -> (A1, A2) 

 (3) разделить (A, k) -> (A1, A2) 

 (4) разделить (A, |A| - k) -> (A1, A2) 

Номер 2 
В представленном ниже псевдокоде алгоритма поиска порядковой статистики что находится на пропущенном месте?

	Random-select(A, k)
	задать λ
	разделить (A, λ) -> (A1, A2)
	...
		вернуть Random-select(A1, k)
	иначе:
		вернуть Random-select(A2, k - |A1|)

Ответ:

 (1) если k > |A1|: 

 (2) если k <= |A1|: 

 (3) если k > |A2|: 

 (4) если k == λ 

Номер 3 
В представленном ниже псевдокоде алгоритма поиска порядковой статистики что находится на пропущенном месте?
	
	Random-select(A, k)
	задать λ
	разделить (A, λ) -> (A1, A2)
	если k <= |A1|:
		...
	иначе:
		вернуть Random-select(A2, k - |A1|)

Ответ:

 (1) вернуть Random-select(A1, k - |A1|) 

 (2) вернуть Random-select(A1, k) 

 (3) возврат 

 (4) вернуть Random-select(A1, k - |A2|) 

Упражнение 3:
Номер 1 
Какие существуют особенности для алгоритма, который ищет k-ую порядковую статистику за линейное время в худшем случае?

Ответ:

 (1) используется рандомизированный выбор разделителя 

 (2) используется приближенная медиана в качестве разделителя 

 (3) используется точная медиана в качестве разделителя 

 (4) поиск разделителя производится с помощью рекурсивного вызова 

Номер 2 
Для приведенного псевдокода поиска k-ой порядковой статистики, выберите строки, которых не хватает для корректной работы алгоритма:
		
		Select (A, k)
		...
		partition(A, λ) -> (A1, A2)
		if k <= |A1| then:
			return Select(A1, k)
		else:
			return Select(A2, k - |A1|)

Ответ:

 (1) group by 5 elements 

 (2) group by k elements 

 (3) sort groups 

 (4) λ = median of medians 

 (5) λ = random of medians 

Номер 3 
Отметьте слагаемые, которые входят в формулу матожидания времени работы рекурсивного алгоритма для поиска k-ой порядковой статистики

Ответ:

 (1) T((3/10) * N) 

 (2) O(N) 

 (3) T(N/5) 

 (4) T((7/10) * N) 

 (5) O(log N) 

Упражнение 4:
Номер 1 
Что такое куча, каково ее назначение?

Ответ:

 (1) хранит упорядоченный по неубыванию или невозрастанию набор ключей и связанных с ними значений 

 (2) структура данных, которая хранит в себе ключи-приоритеты и связные с ними значения 

 (3) так называют любое, неупорядоченное ни по каким параметрам множество значений 

 (4) любая структура данных, представленная в виде дерева, хранящая в себе ключи и связанные с ними значения 

Номер 2 
Как можно удалить элемент из кучи?

Ответ:

 (1) по переданному значению 

 (2) по переданному ключу или итератору 

 (3) по ключу или значению 

Номер 3 
В каком месте min-кучи достигается минимум приоритетов е элементов?

Ответ:

 (1) в листьях 

 (2) в корне 

 (3) может быть в любом месте кучи 

 (4) в правом крайнем листе 

 (5) в левом крайнем листе 

Номер 4 
Какое условие должно быть выполнено, чтобы дерево T с вершинами v удовлетворяло свойствам min-кучи? pri(v) - приоритет вершины v

Ответ:

 (1) pri(vi) >= pri(vi+1) для всех вершин v. i - порядковый индекс элемента 

 (2) pri(vi) <= pri(vi+1) для всех вершин v. i - порядковый индекс элемента 

 (3) pri(parent(v)) >= pri(v) для всех вершин v, кроме корня 

 (4) pri(parent(v)) <= pri(v) для всех вершин v, кроме корня 

Упражнение 5:
Номер 1 
Какие операции есть в структуре данных куча?

Ответ:

 (1) Insert(k) 

 (2) Remove(k) 

 (3) Get-min() 

 (4) Extract(k) 

 (5) Extract-min() 

 (6) Decrease-key(k) 

Номер 2 
Для кучи, реализованной поверх массива, у каких операций время работы будет O(1)?

Ответ:

 (1) Get-min() 

 (2) Extract-min() 

 (3) Insert(k) 

 (4) Remove(k) 

 (5) Decrease-key(k) 

Номер 3 
Для кучи, реализованной поверх массива, у каких операций время работы будет O(N)?

Ответ:

 (1) Get-min() 

 (2) Extract-min() 

 (3) Insert(k) 

 (4) Remove(k) 

 (5) Decrease-key(k) 

Упражнение 6:
Номер 1 
Что делает операция Decrease-key для кучи?

Ответ:

 (1) извлекает минимальное значение и возвращает его 

 (2) возвращает миниальное значение без извлечения 

 (3) удаляет значение по итератору 

 (4) по итератору и новому значению ключа обновляет этот ключ в структуре данных 

Номер 2 
Что делает операция Extract-min для кучи?

Ответ:

 (1) извлекает минимальное значение и возвращает его 

 (2) возвращает миниальное значение без извлечения 

 (3) удаляет значение по итератору 

 (4) по итератору и новому значению ключа обновляет этот ключ в структуре данных 

Номер 3 
Что делает операция Get-min для кучи?

Ответ:

 (1) извлекает минимальное значение и возвращает его 

 (2) возвращает миниальное значение без извлечения, то есть без изменения структуры данных 

 (3) удаляет значение по итератору 

 (4) по итератору и новому значению ключа обновляет этот ключ в структуре данных 

Упражнение 7:
Номер 1 
Какое дерево можно назвать полным бинарным?

Ответ:

 (1) каждая вершина является листом или имеет одного или двух сыновей 

 (2) каждая вершина является листом или имеет ровно два сына, все листья находятся на одной глубине 

 (3) каждая вершина является листом или имеет ровно два сына, листья могут находиться на соседних уровнях 

Номер 2 
Какое дерево можно назвать почти полным бинарным?

Ответ:

 (1) каждая вершина либо лист, либо имеет двух или одного сына: левого или правого 

 (2) каждая вершина либо лист, либо имеет ровно два сына, все листья находятся на одной глубине 

 (3) если взять полное бинарное дерево и убрать на последнем уровне часть сыновей, начиная справа, то получится почти полное бинарное дерево 

Номер 3 
Для вершины с индексом i какие индексы будут у сыновей вершины?

Ответ:

 (1) i/2, (i-1)/2 

 (2) 2*i + 1, 2*i + 2 

 (3) i, 2*i 

Номер 4 
Для левого и правого сыновей с индексом i, какие индексы будут у их родителя?

Ответ:

 (1) i/2, (i-1)/2 

 (2) (i+1)/2, (i-1)/2 

 (3) 2*i + 1, 2*i + 2 

 (4) i, 2*i 

Упражнение 8:
Номер 1 
Как можно построить кучу из N элементов за время O(N)?

Ответ:

 (1) создать пустую кучу, применить операцию Insert для каждого элемента 

 (2) это невозможно, потому что все операции в куче работают за O(log N) 

 (3) применить операцию MakeHeap для второй половины элементов, затем восстановить свойства кучи только для этой половины элементов 

Номер 2 
За какое время выполняется операция MakeHeap, то есть построение кучи из набора размером N?

Ответ:

 (1) O(N * log N) 

 (2) O(N) 

 (3) O(N2) 

 (4) O(N2 * log N) 

Номер 3 
Какое условие должно выполняться для процедуры просеивания вверх (Sift-up), чтобы текущий элемент продолжал просеивание? Для мин-кучи

Ответ:

 (1) key(i) > key(parent(i)) 

 (2) key(i) < key(parent(i)) 

 (3) key(i) < key(i-1) 

 (4) key(i) < key(i+1) 

Номер 4 
Какая сложность у процедур просеивания для куч (sift-up, sift-down)?

Ответ:

 (1) O(N) 

 (2) O(log N) 

 (3) O(1) 

 (4) O(N * log N) 

Упражнение 9:
Номер 1 
Какие операции включает в себя процедура вставки (Insert(k)) для кучи?

Ответ:

 (1) приписывание ключа в конец кучи 

 (2) Sift-up() 

 (3) Sift-down() 

 (4) приписывание ключа в начало (корень) кучи 

Номер 2 
Какие операции включает в себя процедура извлечения минимума (Extract-min()) для кучи?

Ответ:

 (1) Sift-up() 

 (2) Sift-down() 

 (3) приписывание ключа в конец кучи 

 (4) перемещение конечного элемента кучи в начало(корень) кучи 

Номер 3 
Для каких операций у k-ичной кучи время работы будет O(k * logk N)?

Ответ:

 (1) Insert(k) 

 (2) Extract-min() 

 (3) Decrease-key(k) 

 (4) Increase-key(k) 

Номер 4 
Для каких операций у k-ичной кучи время работы будет O(logk N)?

Ответ:

 (1) Insert(k) 

 (2) Extract-min() 

 (3) Decrease-key(k) 

 (4) Increase-key(k) 

Номер 5 
С помощью какой структуры данных можно реализовать сливаемые очереди с приоритетом?

Ответ:

 (1) биномиальная очередь 

 (2) min-куча 

 (3) max-куча 

 (4) левацкая куча 

Упражнение 10:
Номер 1 
Как можно реализовать биномиальную кучу размерности 
		T3?

Ответ:

 (1) построить троичную бинарную кучу из бинарных куч размерности T1 

 (2) объединить корни куч размерностей T1 и T2 

 (3) построить кучу из трех элементов 

Номер 2 
Сколько узлов имеет биномиальное дерево Ti?

Ответ:

 (1) i 

 (2) 2i 

 (3) 2i+1 

 (4) i2 

Номер 3 
Если структуру бинарное дерево размера 5(1012) слить со структурой размера 7(1112) получится структура размера:

Ответ:

 (1) 4(1002) 

 (2) 12(11002) 

 (3) 8(10002) 

 (4) 7(1112) 

Номер 4 
Структура бинарного дерева размера 5(1012) включает в себя:

Ответ:

 (1) бинарные деревья T2 и T3 

 (2) бинарные деревья T0 и T2 

 (3) бинарные деревья T0,...,T4 

Упражнение 11:
Номер 1 
Как склеить 2 бинарных дерева T1(с корнем α) и T2(с корнем β), если α <= β?

Ответ:

 (1) соеденить α с β, α - родитель 

 (2) это невозможно 

 (3) соеденить β с α, β - родитель 

Номер 2 
За какое время выполняется слияние двух деревьев?

Ответ:

 (1) O(N) 

 (2) O(log N) 

 (3) O(1) 

 (4) O(N * log N) 

Номер 3 
Как находить минимум в сливаемом бинарном дереве за O(1)?

Ответ:

 (1) искать минимум в корнях поддеревьев 

 (2) запоминать минимум при каждом слиянии деревьев 

 (3) минимум будет находиться в корне полученного дерева 

Упражнение 12:
Номер 1 
За какое время работает операция Insert в бинарном дереве?

Ответ:

 (1) O(1) 

 (2) O(N) 

 (3) O(log N) 

 (4) O(N * log N) 

Номер 2 
За какое время работает операция Extract-min в бинарном дереве?

Ответ:

 (1) O(1) 

 (2) O(N) 

 (3) O(log N) 

 (4) O(N * log N) 

Номер 3 
За какое время работает операция Decrease-key в бинарном дереве?

Ответ:

 (1) O(1) 

 (2) O(N) 

 (3) O(log N) 

 (4) O(N * log N) 

Упражнение 13:
Номер 1 
Чему равен ранг вершины v = Null левацкого дерева?

Ответ:

 (1) 1 

 (2) 0 

 (3) Null 

 (4) может принимать любое значение 

Номер 2 
Если у левацкого дерева вершина v не равна Null, то чему равен ранг этой вершины?

Ответ:

 (1) 1 + min(left(v), right(v)) 

 (2) min(left(v), right(v)) 

 (3) 1 + max(left(v), right(v)) 

Номер 3 
Сколько вершин содержится в поддереве любой вершины v?

Ответ:

 (1) 2r(v) 

 (2) не менее 2r(v) - 1 

 (3) 2 * r(v) 

Номер 4 
Ранг любой вершины кучи с N элементами равен:

Ответ:

 (1) O(N) 

 (2) O(log N) 

 (3) O(N * log N) 

Упражнение 14:
Номер 1 
При выполнении какого свойства куча будет называться левацкой?

Ответ:

 (1) rank(left(v)) >= rank(right(v)) для любой вершины v 

 (2) rank(left(v)) <= rank(right(v)) для любой вершины v 

 (3) rank(v) <= rank(parent(v)) для любой вершины v 

 (4) rank(v) >= rank(parent(v)) для любой вершины v 

 (5) rank(left(v)) = rank(right(v)) для любой вершины v 

Номер 2 
Можно ли любую кучу превратить в левацкую, если да, то как?

Ответ:

 (1) нельзя 

 (2) если обменять левого и правого сына в тех вершинах v, для которых свойство левацкости (rank(left(v)) >= rank(right(v))) нарушается 

 (3) если выполнить процедуру просеивания (вверх или вниз) для тех вершин, у которых свойство левацкости нарушается 

 (4) если удалить те вершины, у которых свойство левацкости нарушается 

Номер 3 
Как изменяются ранги вершин при движении по правому пути левацкой кучи?

Ответ:

 (1) ранги не изменяются 

 (2) уменьшаются ровно на 1 при каждом шаге 

 (3) увеличиваются ровно на 1 при каждом шаге 

 (4) уменьшаются на 1 при каждом шаге или не меняются 

Упражнение 15:
Номер 1 
Отметьте какие утверждения относятся к левацким кучам

Ответ:

 (1) ранг правого сына всегда на 1 меньше чем ранг родителя 

 (2) ранг растет линейно по числу элементов 

 (3) Операция Insert сводится к созданию кучи из одного элемента, а затем к слиянию 

 (4) левацкая куча хранит в каждой вершине помимо ее приоритета также ранг 

 (5) если у кучи есть правый сын, но нет левого, то она может быть левацкой 

Номер 2 
Отметьте, какие утверждения относятся к операции слияния (Meld) двух левацких куч

Ответ:

 (1) при слиянии двух левацких куч получается куча со свойствами левацкости без совершения дополнительных действий 

 (2) операция слияния выполняется рекурсивно 

 (3) если одна из двух сливаемых куч пустая, то результат их слияния равен другой куче 

 (4) время выполнения операции слияния двух левацких куч O(log N) 

 (5) если для приоритетов корней (u и v) двух куч выполняется u < v, то u ставится корнем результата слияния 

Номер 3 
Отметьте какие действия нужно дополнительно совершить на каждом шаге рекурсии для процедуры слияния двух левацких куч, чтобы полученная куча тоже была левацкой

Ответ:

 (1) перед возвратом из рекурсии нужно заново вычислить ранг вершины, являющейся корнем кучи 

 (2) перед возвратом из рекурсии проверить для вершины, являющейся корнем кучи, свойство левацкости и если оно нарушено, то исправить 

 (3) при слиянии двух куч получается левацкая куча без совершения дополнительных операций 

Номер 4 
Какие операции поддерживают левацкие кучи?

Ответ:

 (1) Get-min 

 (2) Extract-min 

 (3) Decrease-key 

 (4) Insert 

 (5) Meld 

Упражнение 16:
Номер 1 
В каком случае вершина v(отличная от корня) называется тяжелой для косой кучи?

Ответ:

 (1) weight(v) >= 1/2weight(parent(v)) 

 (2) weight(v) > 1/2weight(parent(v)) 

 (3) weight(v) > weight(parent(v)) 

 (4) weight(v) <= 1/2weight(parent(v)) 

Номер 2 
Чему равен вес для вершины v w(v) для косой кучи?

Ответ:

 (1) рангу вершины v 

 (2) количеству вершин в поддереве с корнем v (считая и саму вершину) 

 (3) количеству вершин в правом поддереве 

 (4) приоритету вершины, умноженному на ее ранг 

Номер 3 
Какая вершина у косой кучи называется плохой?

Ответ:

 (1) если она является легким правым сыном 

 (2) если она является тяжелым правым сыном 

 (3) если у нее легкий правый сын 

 (4) если ее вес равен 0 

Упражнение 17:
Номер 1 
Что называется потенциалом косой кучи?

Ответ:

 (1) количество хороших вершин в ней 

 (2) количество плохих вершин в ней 

 (3) общее количество вершин в ней 

 (4) количество тяжелых вершин в ней 

Номер 2 
Для косой кучи выполняется следующее свойство. В дереве из N вершин на любом пути, идущем вниз, содержится:

Ответ:

 (1) не более log N тяжелых вершин 

 (2) не более log N легких вершин 

 (3) не более log N плохих вершин 

Номер 3 
Для косой кучи выполняется следующее свойство. У вершины не может быть:

Ответ:

 (1) одновременно легкого и тяжелого сыновей 

 (2) два тяжелых сына 

 (3) два плохих сына 

Номер 4 
Чему равно учетное время выполнения операции Meld для косой кучи?

Ответ:

 (1) O(N * log N) 

 (2) O(log N) 

 (3) O(N) 



Главная / Алгоритмы и дискретные структуры / Алгоритмы и структуры данных поиска / Тест 5