15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных

^ 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» Вариант 1
1. Дана последовательность чисел: 2, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 8. Нумерация частей начинается с нуля. Элемент с каким номером будет найден способом бинарного поиска по ключу key=5?


2. Дан программный код. Какое значение 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных возвращает функция Search?

int Search(int *x, int k, int key){

int i;

for (i = k-1; i >=0 ; i--)

if ( x[i] == key )

break;

return i > 0 ? i : -1;

}


3. Размер хеш-таблицы HashTableSize =7. Обусловьте хеш-коды для первых 5 обычных чисел, сформированные функцией Hash.

int Hash 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных(int Key, int HashTableSize) {

return Key % HashTableSize;

}


4. Разработка данного способа хеширования заключается в том, что элементы огромного количества, которым соответствует одно и то же хеш-значение, связываются в цепочку-список. О каком способе 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных хеширования речь идет?



5. Укажите, на какую позицию произойдет 2-ое смещение начала подстроки при поиске в тексте по методу Кнута, Морриса и Пратта. Строчка: АВСКВАВСМКВ, подстрока: ВСМ. Нумерация в 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных строке начинается с нуля.


^ 6. Дано случайное дерево поиска. Укажите примеры входных последовательностей, которые могли бы сформировать данное дерево.


7. Дана частотность возникновения знаков в тексте. Сделайте кодирование знаков способом Хаффмана. Укажите 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных код знака ‘е’. Считать, что очередной бит кода начинает формироваться с единицы.

a

b

c

d

e

0,4

0,15

0,22

0,05

0,18


^ 8. Обусловьте коэффициент сжатия текста «abcaabbaac», к которому использовано сжатие по способу Хаффмана. Размер входной последовательности на 1 б больше ее длины.
Вариант 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных 2
1. Дана последовательность чисел: 2, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 7, 7, 8, 8, 8, 8. Нумерация частей начинается с нуля. Элемент с каким номером будет найден способом бинарного поиска по ключу key=8?


^ 2. Дан программный код. Какое значение возвращает функция Search?

int Search(int *x 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных, int k, int key){

x = (int *)realloc(x,(k+1)*sizeof(int));

x[k] = key;

int i = 0;

while ( x[i] != key )

i++;

return i < k ? i : -1;

}


3. Хеш-таблица формируется способом середин квадратов. Обусловьте хеш-коды для первых 5 двузначных обычных чисел, сформированные функцией Hash 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных.

int Hash(int Key) {

return ((Key*Key)/10)%10 ;

}


4. При данном способе хешировании в хеш-таблице хранятся конкретно сами элементы, а не заглавия списков частей. Потому в каждой записи (секторе) может храниться только один элемент. О каком 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных способе хеширования речь идет?


^ 5. Составьте таблицу смещений при поиске подстроки в строке по методу Бойера и Мура. Строчка: АВВОМРАВАВМАВ, подстрока: ВАВ. Нумерация в строке начинается 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных с нуля.


^ 6. На схеме показано вращение АВЛ-дерева. Обусловьте вид вращения.






7. Дана частотность возникновения знаков в тексте. Сделайте кодирование знаков способом Хаффмана. Укажите среднюю длину кодового слова, которая равна 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных сумме произведений вероятности на длину кода каждого знака соответственно. Считать, что очередной бит кода начинает формироваться с единицы.

a

b

c

d

e

0,4

0,15

0,22

0,05

0,18


^ 8. Сделайте кодирование текста «abcaabbaac», к которому использовано сжатие по способу Хаффмана. Считать, что 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных очередной бит кода начинает формироваться с единицы.



Вариант 3
^ 1. Дана последовательность n вещественных чисел. Нужно отыскать число по ключу key с точностью e методом бинарного поиска. Оцените время выполнения метода.


^ 2. Дан 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных программный код. Какое значение возвращает функция Search?

int Search(int *x, int k, int key){

bool found = false;

int high = k - 1, low = 0;

int middle = (high + low) / 2;

while ( !found && high >= low ){

if (key == x 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных[middle])

found = true;

else if (key < x[middle])

high = middle - 1;

else

low = middle + 1;

middle = (high + low) / 2;

}

return found ? middle : -1 ;

}


3. Хеш-таблица формируется способом поразрядного сложения двузначных представлений цифр числа с следующим переводом результата в десятичное число. Обусловьте хеш-коды для первых 5 двузначных составных чисел 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных, сформированные функцией хеширования.


^ 4. Если осуществляется попытка поместить элемент х в сектор с номером , который уже занят другим элементом, то в согласовании с данной методикой выбирается последовательность других номеров частей , куда можно поместить элемент 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных х. Каждое из этих местоположений поочередно проверяется, пока не будет найдено свободное. О какой методике хеширования речь идет?


5. Укажите, на какую позицию произойдет 5-ое смещение 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных начала подстроки при поиске в тексте по методу Бойера и Мура. Строчка: АВСССКВАВСМВВВК, подстрока: ВСМ. Нумерация в строке начинается с нуля.


^ 6. Дано упорядоченное бинарное 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных дерево. Укажите позицию вставки элемента с ключом 3 в это дерево, чтоб соблюдалась балансировка дерева.






7. Дана частотность возникновения знаков в тексте. Сделайте кодирование знаков способом Хаффмана. Укажите 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных длину кода знака ‘b’. Считать, что очередной бит кода начинает формироваться с единицы.

a

b

c

d

e

0,4

0,15

0,22

0,05

0,18


^ 8. Дано кодовое дерево. Каким из представленных строк оно соответствует?




^ 15.3. Тест по теме «Алгоритмы сортировки массивов. Методы на графах» Вариант 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных 1
1. Укажите последовательности, которые являются бинарными пирамидами.


^ 2. В верхушку пирамиды помещен элемент. На какой позиции он остановится в итоге спуска вниз? Нумерация частей начинается с нуля.







3. Дан массив частей: 4, 7, 3, 8, 5, 6, 3, 7, 2, 6, 8. Укажите порядок частей 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных этого массива после выполнения первого прохода сортировки Хоара по невозрастанию. Опорный элемент размещен на средней позиции.


^ 4. Дан массив частей: 4, 7, 9, 0, 3, 2, 6, 8, 7. Укажите порядок частей этого массива после выполнения 1-го прохода сортировки Шелла по 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных неубыванию с шагом h=4.


^ 5. В методе наружной сортировки употребляется три вспомогательных файла и раздельно реализуются рассредотачивание и слияние. Обусловьте свойства таковой сортировки.


^ 6. Во входном файле дан массив чисел:

5 6 9 3 2 3 4 5 4 7 8 6 0

Сделайте 1-ое 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных рассредотачивание входных данных по двум вспомогательным файлам f1 и f2, используя сортировку по неубыванию естественным слиянием.


7. Укажите порядок вершин при обходе графа в ширину, начиная с 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных верхушки 1.




^ 8. Дано описание метода поиска кратчайшего пути на графе. «Алгоритм находит кратчайший путь из данной верхушки до других вершин. Построим огромное количество S вершин, для которых кратчайшие пути от 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных исходной верхушки уже известны. На каждом шаге к огромному количеству S добавляется та из оставшихся вершин, расстояние до которой от исходной верхушки меньше, чем для других оставшихся вершин.» Укажите заглавие метода.



Вариант 2
^ 1. Укажите последовательности, которые не являются бинарными пирамидами.


^ 2. В верхушку пирамиды помещен элемент. На какой позиции он остановится в итоге спуска вниз? Нумерация частей начинается с нуля.






3. Дан 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных массив частей: 4, 7, 3, 8, 5, 6, 3, 7, 2, 6, 8. Укажите порядок частей этого массива после выполнения второго прохода сортировки Хоара по неубыванию. Опорный элемент размещен на средней позиции.


4. Дан массив частей: 4, 7, 3, 0, 3, 2, 6, 8, 7, 2, 6, 4. Укажите порядок частей этого массива после выполнения 1-го 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных прохода сортировки Шелла по невозрастанию с шагом h=6.


^ 5. В методе наружной сортировки употребляется два вспомогательных файла и совмещены рассредотачивание и слияние. Обусловьте свойства таковой сортировки.


^ 6. После рассредотачивания по двум файлам были получены 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных данные (серии разбиты апострофом).

f1: 3 7 2 8 5 9 1 3 f2: 6 9 3 5 7 7

Сделайте слияние этих результатов в один файл согласно методу обычной сортировки по неубыванию.


^ 7. Укажите порядок вершин при обходе графа в глубину, начиная с верхушки 1.






8. Дано описание 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных метода поиска кратчайшего пути на графе. «Алгоритм находит кратчайшее расстояние меж 2-мя хоть какими верхушками графа на основании факта о том, что всякий неэлементарный кратчайший путь состоит из других кратчайших путей.» Укажите 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных заглавие метода.



Вариант 3
^ 1. Укажите последовательности, которые являются бинарными пирамидами.


2. В верхушку пирамиды помещен элемент. На какой позиции он остановится в итоге спуска вниз 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных? Нумерация частей начинается с нуля.




3. Дан массив частей: 7, 9, 0, 3, 2, 4, 7, 6, 5, 2, 0. Укажите порядок частей этого массива после выполнения второго прохода сортировки Хоара по невозрастанию. Опорный элемент размещен на средней позиции.


^ 4. Дан массив частей: 5, 0, 6, 4, 9, 7, 9, 2, 1, 0. Укажите порядок частей этого 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных массива после выполнения 1-го прохода сортировки Шелла по неубыванию с шагом h=5.

^ 5. В методе наружной сортировки употребляется два вспомогательных файла и раздельно реализуются рассредотачивание и слияние. Обусловьте свойства таковой сортировки.


^ 6. Во входном файле дан массив чисел:

5 6 9 3 2 3 4 5 4 7 8 6 0

Сделайте 1-ое рассредотачивание входных данных по двум вспомогательным файлам f1 и f2, используя сортировку по невозрастанию естественным слиянием.


7. Укажите 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных порядок вершин при обходе графа в ширину, начиная с верхушки 5.




8. Дано описание метода поиска кратчайшего пути на графе. «Алгоритм находит среднее решение задачки о кратчайшем пути на графе способом проб и ошибок 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных (попробуем сходить в эту сторону: не получится – вернемся и попробуем в другую).» Укажите заглавие метода.



Учебное издание

ВАНЫКИНА Галина Владиславовна

СУНДУКОВА Татьяна Олеговна

Методы

КОМПЬЮТЕРНОЙ ОБРАБОТКИ 15.2. Тест по теме «Алгоритмы поиска, хеширования и сжатия данных» - Обработки данных ДАННЫХ


Учебное пособие




15-uluchshenie-demograficheskoj-situacii-doklad-o-rezultatah-i-osnovnih-napravleniyah-deyatelnosti.html
15-v-sfere-zhkh-pravila-nediskriminacionnogo-dostupa-k-uslugam-monopolij-24-nediskriminacionnij-dostup-k-neftyanoj-trube-24.html
15-vidacha-voditelskogo-udostovereniya-na-pravo-upravleniya-mehanicheskim-transportnim-sredstvom-sootvetstvuyushej-kategorii-s-talonom-k-nemu-dalee-voditelsk.html