Учебное пособие Чебоксары 2008 удк 004. 657 П 36

Контрольные вопросы

1. 
   Какие задачи решаются при помощи поиска в структурах данных?
   
2. 
   В чем заключается смысл алгоритма линейного поиска?
   
3. 
   В чем заключается смысл алгоритма поиска делением пополам (двоичного поиска)?
   
4. 
   Какие особенности поиска в таблице данных?
   
5. 
   Как осуществляется поиск текстовой информации? Как реализуется алгоритм прямого поиска строки?
   
6. 
   Как реализуется алгоритм Кнута, Мориса и Пратта?
   
7. 
   Как реализуется алгоритм Боуера и Мура? Чем обусловлена наибольшая эффективность этого алгоритма?
   

^

Лабораторная работа 4.

Сортировка значений в таблице

Цель работы: изучить методы сортировки массивов.

Необходимые исходные сведения

Сортировка представляет собой процесс упорядочения множества подобных информационных объектов в порядке возрастания или убывания их значений. Например, список i из n элементов будет отсортирован в порядке возрастания значений элементов, если i <= i <= ... <= I.

В общем случае при сортировке данных только часть информации используется в качестве ключа сортировки, который используется в сравнениях. Когда выполняется обмен, передается вся структура данных. Например, в списке почтовых отправлений в качестве ключа сортировки может использоваться почтовый индекс, а в операциях обмена к почтовому индексу добавляется полное имя и адрес.

^ Классы алгоритмов сортировки

Имеется три способа сортировки массивов:

- сортировка обменом;

- сортировка выбором;

- сортировка вставкой.

Представьте, что лежит колода карт. Для сортировки карт обменом необходимо разложить карты на столе лицевой стороной вверх и затем менять местами те карты, которые расположены в неправильном порядке, делая это до тех пор, пока колода карт не станет упорядоченной.

Для сортировки выбором необходимо разложить карты на столе, выбрать самую младшую карту и взять ее в свою руку. Затем из оставшихся на столе карт вновь выбрать наименьшую по значению карту и поместить ее позади той карты, которая уже имеется в руке. Этот процесс надо продолжать до тех пор, пока все карты не окажутся в руках. Поскольку каждый раз выбирается наименьшая по значению карта из оставшихся на столе, по завершении такого процесса карты в руке будут отсортированы.

Для сортировки вставкой необходимо держать карты в своей руке, поочередно снимая карту с колоды. Каждая взятая вами карта помещается в новую колоду на столе, причем она ставится на соответствующее место. Колода будет отсортирована, когда у вас в руке не окажется ни одной карты.

^ Сортировка Шелла

Сортировка Шелла получила свое название по имени ее создателя Д.Л. Шелла. Однако это название можно считать удачным, так как выполняемые при сортировке действия напоминают укладывание морских ракушек друг на друга ("ракушка" – одно из значений слова shell).

Общий метод, который использует сортировку вставкой, применяет принцип уменьшения расстояния между сравниваемыми элементами. Далее показана схема выполнения сортировки Шелла для массива "оасве". Сначала сортируются все элементы, которые смещены друг от друга на три позиции. Затем сортируются все элементы, которые смещены на две позиции. И, наконец, упорядочиваются все соседние элементы.

• 
  проход 1: f d a c b e
  
• 
  проход 2: c b a f d e
  
• 
  проход 3: a b c e d f
  
• 
  полученный результат: a b c d e f
  

procedure shell(var a:massiv;p:word);

const

t=5;

var

i,j,k,s,m:integer;

h:array[1..t] of integer;

x:data;

begin

writeln('Сортировка Шелла:');

h[1]:=9; h[2]:=5; h[3]:=3; h[4]:=2; h[5]:=1;

for m:=1 to t do

begin

k:=h[m];

s:=-k;

for i:=k+1 to p do

begin

x:=a[i];

j:=i-k;

if s=0 then

begin

s:=-k;

s:=s+1;

a[s]:=x;

end;

while (x
begin

a[j+k]:=a[j];

j:=j-k;

end;

a[j+k]:=x;

end;

end;

end;

При поверхностном взгляде на алгоритм нельзя сказать, что он дает хороший результат и даже то, что в результате получится отсортированный массив. Однако он дает и то и другое. Эффективность этого алгоритма объясняется тем, что при каждом проходе используется относительно небольшое число элементов или элементы массива уже находятся в относительном порядке, а упорядоченность увеличивается при каждом новом просмотре данных. Расстояния между сравниваемыми элементами могут изменяться по-разному. Обязательным является лишь то, что последний шаг должен равняться единице. Например, хорошие результаты дает последовательность шагов 9, 5, 3, 2, 1, которая использована в показанном выше примере. Следует избегать последовательностей степени двойки, которые, как показывают сложные математические выкладки, снижают эффективность алгоритма сортировки. Однако при использовании таких последовательностей шагов между сравниваемыми элементами эта сортировка будет по-прежнему работать правильно.

Внутренний цикл имеет два условия проверки. Условие х<а[j] необходимо для упорядочения элементов. Условия j>0 и j<=count необходимы для того, чтобы предотвратить выход за пределы массива. Эта дополнительная проверка в некоторой степени ухудшает сортировку Шелла.

Слегка измененные версии сортировки Шелла используют специальные управляющие элементы, которые не являются в действительности частью той информации, которая должна сортироваться. Управляющие элементы имеют граничные для массива данных значения, т.е. наименьшее и наибольшее значения. В этом случае не обязательно выполнять проверку на граничные значения.

Однако применение таких управляющих элементов требует специальных знаний о той информации, которая сортируется, и это снижает универсальность процедуры сортировки. Анализ сортировки Шелла требует решения некоторых сложных математических задач. Время выполнения сортировки Шелла пропорционально 1,2n.

Эта зависимость значительно лучше квадратичной зависимости, которой подчиняются рассмотренные ранее алгоритмы сортировки.

^ Варианты заданий

Вариант	Задание
1	Разработать алгоритм и программу внутренней сортировки значений в таблице (пузырьковая сортировка)
2	Разработать алгоритм и программу внутренней сортировки значений в таблице (сортировка простыми вставками)
3	Разработать алгоритм и программу внутренней сортировки значений в таблице (простая сортировка выбором)
4	Разработать алгоритм и программу внутренней сортировки значений в таблице (метод Шелла)
5	Разработать алгоритм и программу внутренней сортировки значений в таблице (бинарные вставки)
6	Разработать алгоритм и программу внутренней сортировки значений в таблице (быстрая сортировка)
7	Разработать алгоритм и программу внутренней сортировки значений в таблице (сортировка выбором)
8	Разработать алгоритм и программу внешней сортировки значений в таблице (простое слияние)
9	Разработать алгоритм и программу внешней сортировки значений в таблице (естественное слияние)
10	Разработать алгоритм и программу внешней сортировки значений в таблице (улучшенные методы сортировки)

^ Пример выполнения

Задание: составить алгоритм и программу сортировки массива методом Шелла.


Блок-схема алгоритма



Текст программы:

uses crt;

type

data=integer;

massiv=array[1..15] of integer;

var

a,b:massiv;

n,i:word;

procedure create_massive(var a:massiv;p:word);

var

i:word;

begin

writeln('Массив создан:');

for i:=1 to p do

begin

a[i]:=2*(9+random(100));

write(a[i]:5);

end;

end;

procedure vivod_massive(var a:massiv;p:word);

var

i:word;

begin

for i:=1 to p do write(a[i]:5);

end;


procedure shell(var a:massiv;p:word);

const

t=5;

var

i,j,k,s,m:integer;

h:array[1..t] of integer;

x:data;

begin

writeln('Сортировка Шелла:');

h[1]:=9; h[2]:=5; h[3]:=3; h[4]:=2; h[5]:=1;

for m:=1 to t do

begin

k:=h[m];

s:=-k;

for i:=k+1 to p do

begin

x:=a[i];

j:=i-k;

if s=0 then

begin

s:=-k;

s:=s+1;

a[s]:=x;

end;

while (x
begin

a[j+k]:=a[j];

j:=j-k;

end;

a[j+k]:=x;

end;

end;

end;

begin

clrscr;

write('Введите число элементов массива 2..15: ');

readln(n);

create_massive(b,n);

writeln;

shell(b,n);

vivod_massive(b,n);

readkey;

end.

Результаты расчетов

Контрольные вопросы

1. 
   Для чего применяется сортировка данных?
   
2. 
   Какие существуют алгоритмы внешней сортировки?
   
3. 
   Какие существуют алгоритмы внутренней сортировки?
   
4. 
   В чем заключается смысл алгоритма сортировки Хоара?
   
5. 
   В чем заключается смысл алгоритма сортировки слиянием?
   
6. 
   В чем заключается смысл алгоритма сортировки выбором?
   
7. 
   Какие существуют алгоритмы усовершенствованной сортировки?
   
8. 
   В чем заключается смысл алгоритма сортировки вставками?
   
9. 
   В чем заключается смысл алгоритма сортировки Шелла?
   
10. 
    В чем заключается смысл алгоритма обменной сортировки?
    
11. 
    В чем заключается смысл алгоритма сортировки методом «пузырька»?
    

Рекомендации по выполнению

курсовой работы

1. Тематика курсовых работ

Курсовая работа студента – заключительный этап изучения определенной дисциплины. Цель работы – систематизация и закрепление теоретических знаний, полученных за время обучения, а также приобретение и закрепление навыков самостоятельной работы. Работа, как правило, основывается на обобщении выполненных студентом лабораторных работ или представляет собой индивидуальное задание по изучаемой дисциплине и подготавливается к защите в завершающий период теоретического обучения.

Тематика курсовых работ по дисциплине определяется преподавателем кафедры. При этом выбор основывается как на государственном стандарте, так и на направлениях научно-исследовательской и учебно-методической работы, актуальных направлениях работы других организаций, деятельность которых связана с разработкой математического, информационного и программного обеспечения ЭВМ. Студенту предоставляется право выбора одной из предложенных тем или предложения своей темы с обоснованием целесообразности ее разработки.

Курсовая работа должна быть подготовлена к защите в срок, устанавливаемый преподавателем. К защите курсовой работы представляется:

• 
  пояснительная записка;
  
• 
  электронная реализация в виде программы и данных.
  

Пояснительная записка содержит основной текст (собственно работа), графические материалы (иллюстрации) и, при необходимости, приложения – разработанную программу с исходным текстом на бумажном и/или дисковом носителе, исходные данные и результаты расчетов, алгоритмы, модели, структуры.

Пояснительная записка включает следующие компоненты:

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

^ 2. Последовательность выполнения работы

Курсовые работы могут выполняться как на выпускающей кафедре, так и в других организациях. Используются фонды университетской и городских библиотек, компьютерная техника вычислительного центра и кафедры.

Руководитель работы выдает задание студенту, оказывает помощь в разработке календарного плана выполнения работы, проводит регулярные консультации, контролирует ход выполнения работы. Ответственность за выбор того или иного решения, правильность расчетов, оформление работы несет студент. Руководитель предостерегает его от ошибочных решений и характеризует достоинства и недостатки различных вариантов решений, при этом право окончательного выбора предоставляется студенту. Если в процессе работы руководитель убеждается в невозможности ее качественного и своевременного выполнения студентом, он может поставить вопрос о прекращении работы.

Последовательность выполнения включает следующие этапы:

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

Периодический контроль за работой студента осуществляется руководителем в процессе проведения консультаций.

Пояснительная записка должен содержать следующие разделы:

• 
  задание;
  
• 
  раскрытие теоретического вопроса;
  
• 
  описание выбранного алгоритма обработки данных (в соответствии с ва­риантом задания);
  
• 
  блок схемы работы программы (в соответствии с вариантом за­дания);
  
• 
  текст программы (оформляется после выполнения программы на ЭВМ);
  
• 
  результаты выполнения программы;
  
• 
  анализ эффективности используемых алгоритмов и выводы по проделанной работе.
  

^ 3. Оформление работы

Текст работы оформляется в виде пояснительной записки в соответствии с требованиями ГОСТ 2.105.95 “Общие требования к текстовым документам” в объеме 8-40 страниц формата А4. Изложение должно быть последовательным, логичным, конкретным.

Работа оформляется с использованием текстового редактора Word и распечатывается на принтере. Текст пояснительной записки к курсовой работе делится на разделы, подразделы и пункты. Размещение текста – с одной стороны листа. Размер шрифта – 14, поля слева – 30 мм, сверху и справа – по 15 мм, снизу – 20 мм. Нумерация страниц – внизу по середине. Первая страница – титульный лист, вторая – задание, далее – оглавление и текст (номера первых двух страниц не указываются). Оглавление создается автоматически средствами текстового редактора. Для вставки формул используется редактор формул Microsoft Equation. Формулы нумеруются в пределах каждого раздела, номер указывается справа от формулы – у правой границы текста, в круглых скобках по образцу (3.6) – шестая формула в третьем разделе.

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

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

^ 4. Подготовка курсовой работы к защите

Оформленная курсовая работа представляется студентом преподавателю для просмотра в соответствии с учебным планом за 2-3 дня до защиты.

График защиты курсовых работ составляется преподавателем и доводится до сведения студентов. При необходимости демонстрации программных продуктов защита назначается в компьютерных классах, где есть необходимое программное обеспечение.

Во время защиты курсовой работы студент должен кратко сформулировать цель работы, изложить содержание, акцентируя внимание на наиболее важных и интересных с его точки зрения решениях, в первую очередь, принятых студентом самостоятельно. При выступлении может быть использована демонстрация созданного программного обеспечения.

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

При неудовлетворительной оценке работы преподаватель устанавливает, может ли студент представить к повторной защите ту же работу с необходимой доработкой или должен разработать новую тему.

Студент, не сдавший в установленный срок курсовую работу, не допускается к сессии.

Защищенные курсовые работы хранятся в университете в течение трех лет.

^ 5. Типовые задания для курсовых работ

Задание 1.

1. 
   Теоретический вопрос: цифровая сортировка.
   
2. 
   Разработать блок-схему алгоритма и программу в соответствии с заданием: написать программу, которая наглядно иллюстрирует работу обменной поразрядной сортировки для типов данных: целого, символьного, строкового.
   
3. 
   Разработать блок-схему алгоритма и программу в соответствии с заданием: написать процедуру, реализующую вставку элемента в В-дерево.
   

4. Выполнить тестирование программы для нормальных, граничных и исключительных условий. Результаты тестирования свести в таблицу.

Задание 2.

1. 
   Теоретический вопрос: доказуемо трудно разрешаемые задачи и алгоритмы.
   
2. 
   Разработать блок-схему алгоритма и программу в соответствии с заданием: найти расстановку пяти ферзей, при которой каждое поле шахматной доски будет находится под ударом хотя одного из них.
   
3. 
   Разработать блок-схему алгоритма и составить программу обработки текстовых данных, хранящихся в произвольном файле на магнитном диске. Вид обработки данных: сортировка букв по возрастанию. Текстовые данные, подлежащие обработке, заносятся в файл редактором текста. В программе предусмотреть ввод с терминала имен входного и выходного (в случае необходимости) файлов, вывод на печать входного и выходного файлов. Предусмотреть запись выходного файла на диск. Длина строки файла не должна превышать 80 символов.
   

4. Выполнить тестирование программы для нормальных, граничных и исключительных условий. Результаты тестирования свести в таблицу.

Задание 3.

1. 
   Теоретический вопрос: сцепляемые очереди.
   
2. 
   Разработать блок-схему алгоритма и программу в соответствии с заданием: написать процедуру, реализующую удаление элемента из В-дерева.
   
3. 
   Разработать блок-схему алгоритма и составить программу обработки текстовых данных, хранящихся в произвольном файле на магнитном диске. Вид обработки данных: найти все слова, имеющие заданное окончание. Текстовые данные, подлежащие обработке, заносятся в файл редактором текста. В программе предусмотреть ввод с терминала имен входного и выходного (в случае необходимости) файлов, вывод на печать входного и выходного файлов. Предусмотреть запись выходного файла на диск. Длина строки файла не должна превышать 80 символов.
   

4. Выполнить тестирование программы для нормальных, граничных и исключительных условий. Результаты тестирования свести в таблицу.

Задание 4.

1. 
   Теоретический вопрос: алгоритмы преобразования ключей (расстановка).
   
2. 
   Разработать блок-схему алгоритма и программу в соответствии с заданием: написать процедуру, реализующую вставку элемента из В-дерево.
   
3. 
   Разработать блок-схему алгоритма и составить программу обработки текстовых данных, хранящихся в произвольном файле на магнитном диске. Вид обработки данных: подсчитать количество слов, которые содержат определённое количество согласных. Текстовые данные, подлежащие обработке, заносятся в файл редактором текста. В программе предусмотреть ввод с терминала имен входного и выходного (в случае необходимости) файлов, вывод на печать входного и выходного файлов. Предусмотреть запись выходного файла на диск. Длина строки файла не должна превышать 80 символов.
   

4. Выполнить тестирование программы для нормальных, граничных и исключительных условий. Результаты тестирования свести в таблицу.

Задание 5.

1. 
   Теоретический вопрос: неориентированные графы.
   
2. 
   Разработать блок-схему алгоритма и программу в соответствии с заданием: Подсчитать количество слов в Trie-дереве, начинающихся с заданной последовательности символов.
   
3. 
   Разработать блок-схему алгоритма и составить программу обработки текстовых данных, хранящихся в произвольном файле на магнитном диске. Вид обработки данных: подсчитать число вхождений каждого слова в текст. Текстовые данные, подлежащие обработке, заносятся в файл редактором текста. В программе предусмотреть ввод с терминала имен входного и выходного (в случае необходимости) файлов, вывод на печать входного и выходного файлов. Предусмотреть запись выходного файла на диск. Длина строки файла не должна превышать 80 символов.
   

4. Выполнить тестирование программы для нормальных, граничных и исключительных условий. Результаты тестирования свести в таблицу.

Задание 6.

1. 
   Теоретический вопрос: методы анализа алгоритмов.
   
2. 
   Разработать блок-схему алгоритма и программу в соответствии с заданием: в Trie-дереве определить количество слов, содержащих букву А.
   
3. 
   Разработать блок-схему алгоритма и составить программу обработки текстовых данных, хранящихся в произвольном файле на магнитном диске. Вид обработки данных: подсчитать число слов с чётной длиной. Текстовые данные, подлежащие обработке, заносятся в файл редактором текста. В программе предусмотреть ввод с терминала имен входного и выходного (в случае необходимости) файлов, вывод на печать входного и выходного файлов. Предусмотреть запись выходного файла на диск. Длина строки файла не должна превышать 80 символов.
   

4. Выполнить тестирование программы для нормальных, граничных и исключительных условий. Результаты тестирования свести в таблицу.

Задание 7.

1. 
   Теоретический вопрос: методы разработки алгоритмов.
   
2. 
   Разработать блок-схему алгоритма и программу в соответствии с заданием: написать программу поиска всех возможных вариантов путей выхода из лабиринта без пересечений.
   
3. 
   Разработать блок-схему алгоритма и составить программу обработки текстовых данных, хранящихся в произвольном файле на магнитном диске. Вид обработки данных: подсчитать количество согласных букв. Текстовые данные, подлежащие обработке, заносятся в файл редактором текста. В программе предусмотреть ввод с терминала имен входного и выходного (в случае необходимости) файлов, вывод на печать входного и выходного файлов. Предусмотреть запись выходного файла на диск. Длина строки файла не должна превышать 80 символов.
   

4. Выполнить тестирование программы для нормальных, граничных и исключительных условий. Результаты тестирования свести в таблицу.

Задание 8.

1. 
   Теоретический вопрос: структуры данных и алгоритмы для внешней памяти.
   
2. 
   Разработать блок-схему алгоритма и программу в соответствии с заданием: построить последовательность максимальной длины из n костей домино.
   
3. 
   Разработать блок-схему алгоритма и составить программу обработки текстовых данных, хранящихся в произвольном файле на магнитном диске. Вид обработки данных: напечатать заданное слово в обратном порядке. Текстовые данные, подлежащие обработке, заносятся в файл редактором текста. В программе предусмотреть ввод с терминала имен входного и выходного (в случае необходимости) файлов, вывод на печать входного и выходного файлов. Предусмотреть запись выходного файла на диск. Длина строки файла не должна превышать 80 символов.
   

4. Выполнить тестирование программы для нормальных, граничных и исключительных условий. Результаты тестирования свести в таблицу.

Задание 9.

1. Теоретический вопрос: проблемы управления памятью при работе с данными.

2. 
   Разработать блок-схему алгоритма и программу в соответствии с заданием: дано n предметов, у каждого есть вес и цена. Предложить набор предметов максимальной стоимости, помещающийся в рюкзак 50 кг.
   
3. 
   Разработать блок-схему алгоритма и составить программу обработки текстовых данных, хранящихся в произвольном файле на магнитном диске. Вид обработки данных: отсортировать слова методом вставки в список с вычисление адреса. Текстовые данные, подлежащие обработке, заносятся в файл редактором текста. В программе предусмотреть ввод с терминала имен входного и выходного (в случае необходимости) файлов, вывод на печать входного и выходного файлов. Предусмотреть запись выходного файла на диск. Длина строки файла не должна превышать 80 символов.
   

4. Выполнить тестирование программы для нормальных, граничных и исключительных условий. Результаты тестирования свести в таблицу.

Задание 10.

1. 
   Теоретический вопрос: неэлементарные алгоритмы и их использование.
   
2. 
   Разработать блок-схему алгоритма и программу в соответствии с заданием: найти максимальную длину кольца, построенного из слов, содержащих одинаковое количество гласных и согласных букв.
   
3. 
   Разработать блок-схему алгоритма и составить программу обработки текстовых данных, хранящихся в произвольном файле на магнитном диске. Вид обработки данных: удалить все пробелы. Текстовые данные, подлежащие обработке, заносятся в файл редактором текста. В программе предусмотреть ввод с терминала имен входного и выходного (в случае необходимости) файлов, вывод на печать входного и выходного файлов. Предусмотреть запись выходного файла на диск. Длина строки файла не должна превышать 80 символов.
   

4. Выполнить тестирование программы для нормальных, граничных и исключительных условий. Результаты тестирования свести в таблицу.

Задание 11.

1. 
   Теоретический вопрос: оценка эффективности хеш-функций. Хеш-таблицы.
   
2. 
   Разработать блок-схему алгоритма и программу в соответствии с заданием: на шахматной доске определить поля, в которые может попасть конь за n ходов из указанной позиции.
   

3. Разработать блок-схему алгоритма и программу в соответствии с заданием: написать процедуру, реализующую удаление элемента из В-дерева.

4. Выполнить тестирование программы для нормальных, граничных и исключительных условий. Результаты тестирования свести в таблицу.

Задание 12.

1. 
   Теоретический вопрос: очереди с приоритетами и частично упорядоченные деревья.
   
2. 
   Разработать блок-схему алгоритма и программу в соответствии с заданием: Имеются n городов. Некоторые из них соединены дорогами известной длины. Найти кратчайшие маршруты из заданного города в остальные.
   
3. 
   Разработать блок-схему алгоритма и программу в соответствии с заданием: Исследовать сортировки простым и естественным слиянием, построить графики зависимости количества сравнений и количества перестановок от количества элементов массива для этих двух сортировок.
   

4. Выполнить тестирование программы для нормальных, граничных и исключительных условий. Результаты тестирования свести в таблицу.

Задание 13.

1. 
   Теоретический вопрос: структуры сложных множеств.
   
2. 
   Разработать блок-схему алгоритма и программу в соответствии с заданием: Имеются n городов. Некоторые из них соединены дорогами известной длины. Найти кратчайший маршрут, начинающийся в заданном городе и проходящий через все остальные.
   
3. 
   Разработать блок-схему алгоритма и программу в соответствии с заданием: проиллюстрировать работу сортировки Бэтчера.
   

4. Выполнить тестирование программы для нормальных, граничных и исключительных условий. Результаты тестирования свести в таблицу.

Задание 14.

1. 
   Теоретический вопрос: нагруженные деревья.
   
2. 
   Разработать блок-схему алгоритма и программу в соответствии с заданием: Имеются n различных предметов, известны вес каждого предмета и его стоимость. Определить, какие предметы надо положить в рюкзак, чтобы общий вес не превышал заданной границы, а общая стоимость бала максимальной.
   
3. 
   Разработать блок-схему алгоритма и программу в соответствии с заданием: написать программу, иллюстрирующую сортировку массива распределяющим подсчётом.
   

4. Выполнить тестирование программы для нормальных, граничных и исключительных условий. Результаты тестирования свести в таблицу.


Задание 15.

1. 
   Теоретический вопрос: ориентированные ациклические графы.
   
2. 
   Разработать блок-схему алгоритма и программу в соответствии с заданием: найти расстановку пяти ферзей, при которой каждое поле шахматной доски будет находиться под ударом, хотя одного из них.
   
3. 
   Разработать блок-схему алгоритма и программу в соответствии с заданием: в Trie-дереве подсчитать количество слов, которые содержат определённое количество согласных.
   

4. Выполнить тестирование программы для нормальных, граничных и исключительных условий. Результаты тестирования свести в таблицу.

Примерные тестовые вопросы

Вопрос 1. Какие из указанных ниже структур данных относятся к встроенным:

1) списки;

2) целый тип;

3) дерево;

4) стек.

Вопрос 2. Какая из ниже перечисленных структур данных отличается наличием вершины:

1) дерево;

2) множество;

3) стек;

4) массив.

Вопрос 3. Описание

Var

    i, j : integer;

    x : real;

    s: string;

объявляет переменные. Переменная s будет является переменной типа:

1. 
   целый;
   
2. 
   действительный;
   
3. 
   строка;
   
4. 
   массив.
   

Вопрос 4. Упорядоченная совокупность элементов некоторого типа, адресуемых при помощи одного или нескольких индексов, называется:

1) массив;

2) дерево;

3) стек;

4) список.

Вопрос 5. Структура данных, объединяющая элементы данных разных типов, называется:

1) массив;

2) дерево;

3) стек;

4) запись.

Вопрос 6. Какие существуют типы указателей:

1) переменные;

2) типизированные;

3) динамические;

4) статические.

Вопрос 7. Структура данных, состоящая из элементов, содержащих такое число указателей, которое позволяет организовать их одновременно в виде нескольких различных списков;

1) мегасписок;

2) n-список;

3) мультисписок;

4) дублирующий список.

Вопрос 8. Структуру данных стек можно организовать с помощью:

1) массивов;

2) деревьев;

3) записей;

4) графов.

Вопрос 9. Частным случаем графа является:

1. 
   стек;
   
2. 
   очередь;
   
3. 
   дерево;
   
4. 
   матрица.
   

Вопрос 10. В бинарном дереве из каждой вершины выходит:

1. 
   произвольное количество дуг;
   
2. 
   не более двух дуг;
   
3. 
   не более трех дуг;
   
4. 
   четное количество дуг.
   

Вопрос 11. Какой метод поиска применяется только к отсортированным массивам:

1. 
   линейный поиск;
   
2. 
   КМП-поиск;
   
3. 
   двоичный поиск;
   
4. 
   алгоритм Боуера и Мура.
   

Вопрос 12. Пузырьковая сортировка относится к:

1. 
   сортировке выбором;
   
2. 
   обменной сортировке;
   
3. 
   сортировке вставкой;
   
4. 
   усовершенствованной сортировке.
   

Вопрос 13. К усовершенствованным алгоритмам сортировки относится:

1. 
   сортировка Шелла;
   
2. 
   пузырьковая сортировка;
   
3. 
   сортировка выбором;
   
4. 
   сортировка вставкой.
   

Вопрос 14. Хеширование данных используется для:

1. 
   поиска элементов в таблице;
   
2. 
   заполнения таблицы значениями;
   
3. 
   предварительного упорядочивания элементов в таблице;
   
4. 
   обмена элементов в таблице.
   

Вопрос 15. К методам ускорения доступа к данным относится:

1. 
   метод разрешения коллизий;
   
2. 
   метод вставки;
   
3. 
   рехеширование;
   
4. 
   метод выбора.
   

Вопрос 16. Способ организации вычислительного процесса, при котором подпрограмма (процедура или функция) в ходе выполнения составляющих её операторов обращается сама к себе:

1) итерация;

2) рекурсия;

3) цикл;

3) условие.

Вопрос 17. Какая из ниже перечисленных структур данных отличается наличием «хвоста» и «головы»:

1) дерево;

2) множество;

3) стек;

4) очередь.

Вопрос 18. Структура данных, в которой отсутствует возможность индексирования отдельных элементов, называется:

1) массив;

2) запись;

3) стек;

4) множество.

Вопрос 19. Структуры данных, в процессе обработки которых изменяются не только значения переменных, но и сама их организация, называются:

1) статические структуры;

2) матрицы;

3) динамические структуры;

4) файлы.

Вопрос 20. Описание данных, представленное следующим образом

type

       element = record

                   data:string;

                   next: pointer;

       end;

var

       head: pointer;

       current, last : ^element;

представляет собой:

1. 
   очередь;
   
2. 
   линейный список;
   
3. 
   массив;
   
4. 
   стек.
   

Вопрос 21. Структуру данных очередь можно организовать с помощью:

1) указателей;

2) деревьев;

3) записей;

4) графов.

Вопрос 22. Структуру данных дерево можно организовать с помощью:

1) деревьев;

2) записей;

3) курсоров;

4) графов.

Вопрос 23. Алгоритм поиска, при котором осуществляется сдвиг слова не на один символ на каждом шаге, а на некоторое переменное количество символов, называется:

1) алгоритм Боуера и Мура;

2) алгоритм прямого поиска;

3) алгоритм бинарного поиска;

4) алгоритм Кнута, Мориса и Пратта.

Вопрос 24. Какой метод поиска, основывается на необычном соображении – сравнение символов начинается с конца слова, а не с начала:

1. 
   линейный поиск;
   
2. 
   КМП-поиск;
   
3. 
   двоичный поиск;
   
4. 
   алгоритм Боуера и Мура.
   

Вопрос 25. Сортировка Хоара относится к:

1. 
   сортировке выбором;
   
2. 
   обменной сортировке;
   
3. 
   сортировке вставкой;
   
4. 
   усовершенствованной сортировке.
   

Вопрос 26. К усовершенствованным алгоритмам сортировки относится:

1. 
   пузырьковая сортировка;
   
2. 
   быстрая сортировка;
   
3. 
   сортировка выбором;
   
4. 
   сортировка вставкой.
   

Вопрос 27. К методам разрешения коллизий относится:

1. 
   поиск элементов в таблице;
   
2. 
   метод цепочек;
   
3. 
   метод умножения;
   
4. 
   метод свертки.
   

Вопрос 28. К методам ускорения доступа к данным относится:

1. 
   метод вставки;
   
2. 
   метод хеширования;
   
3. 
   рехеширование;
   
4. 
   метод выбора.
   

Вопрос 29. Какая из ниже перечисленных структур данных отличается наличием корня:

1) дерево;

2) множество;

3) стек;

4) массив.

Вопрос 30. Структура данных, объединяющая элементы данных одного типа, называется:

1) массив;

2) дерево;

3) стек;

4) запись.

Вопрос 31. Структуру данных список можно организовать с помощью:

1) стеков;

2) деревьев;

3) массивов;

4) графов.

Вопрос 32. Какой метод поиска применяется к последовательностям данных:

1. 
   линейный поиск;
   
2. 
   КМП-поиск;
   
3. 
   двоичный поиск;
   
4. 
   алгоритм Боуера и Мура.
   

Вопрос 33. Дерево, у которого ветви каждого узла упорядочены:

1) бинарное дерево;

2) сильноветвящееся дерево;

3) дерево поиска;

4) связанное дерево.

Вопрос 34. Арность дерева – это:

1) количество узлов;

2) число ветвей, выходящих из узла;

3) число ветвей;

4) количество поддеревьев.

Вопрос 35. Упорядоченные n-арные деревья, где n>2, называется:

1) бинарным деревом;

2) сильноветвящимся деревом;

3) деревом поиска;

4) связанным деревом.

Вопрос 36. Сортировка Шелла относится к:

1. 
   сортировке выбором;
   
2. 
   обменной сортировке;
   
3. 
   сортировке вставкой;
   

4) внешней сортировке.

Вопрос 37. К алгоритмам внешней сортировки относится:

1. 
   сортировка Шелла;
   
2. 
   пузырьковая сортировка;
   
3. 
   простое слияние;
   
4. 
   сортировка вставкой.
   

Вопрос 38. Сортировка, применяемая к данным, которые хранятся во внешней памяти компьютера:

1. 
   сортировка выбором;
   
2. 
   обменная сортировка;
   
3. 
   сортировка вставкой;
   

4) внешняя сортировка.

Вопрос 39. Сортировка, применяемая к данным, которые хранятся в оперативной памяти компьютера:

1. 
   сортировка выбором;
   
2. 
   внутренняя сортировка;
   
3. 
   сортировка вставкой;
   

4) внешняя сортировка.

Вопрос 40. Сортировка простым выбором относится к:

1) внешней сортировке;

2) пузырьковой сортировке;

3) внутренней сортировке;

4) сортировке Шелла.

Вопрос 41. Метод разрешения коллизий относится к:

1. 
   методу вставки;
   
2. 
   рехешированию;
   
3. 
   ускорению доступа к данным;
   
4. 
   методу выбора.
   

Вопрос 42. Квадратичное опробование относится к методу:

1) свёртки;

2) разрешения коллизий;

3) деления;

4) цепочек.


Список рекомендуемой литературы

1. 
   Ахо А. Структуры и алгоритмы / А.Ахо, Д.Хопкрофт - М.: Вильямс, 2001.
   
2. 
   Бентли Дж. Жемчужины программирования, 2-е изд. / Дж.Бентли – СПб.: Питер, 2002.
   
3. 
   Вирт Н. Алгоритмы и структуры данных / Н.Вирт - М.: Мир, 1989.
   
4. 
   Вирт Н. Алгоритмы + структуры данных = программы / Н.Вирт - М.: Мир, 1985.
   
5. 
   Вирт Н. Алгоритмы и структуры данных / Н.Вирт – СПб.: Невский диалект, 2001.
   
6. 
   Дмитриева М.В. Турбо Паскаль и Турбо Си: построение и обработка структур данных: учебное пособие / М.В.Дмитриева, А.А.Кубенский – СПб.: Изд-во С.-Петербургского университета, 1995.
   
7. 
   Кнут Д. Искусство программирования. т.3. Сортировка и поиск: пер. с англ. / Д.Кнут – М.: Вильямс, 2000.
   
8. 
   Кортмен Т. Алгоритмы: построение и анализ / Т.Кортмен, Ч.Лейзеррсон, Р.Ривест - М: МЦНМО, 2000.
   
9. 
   Лэнгсам Й. Структуры данных для персональных ЭВМ / Й.Лэнгсам, М.Огенстайн - М.: Мир, 1989.
   
10. 
    Лэнгсам Й. Структуры данных для персональных ЭВМ / Й.Лэнгсам, М.Огенстайн, А.Тененбау - М.: Мир, 1989.
    
11. 
    Матьяш В.А. Структуры и алгоритмы обработки данных / В.А.Матьяш, В.А.Путилов, В.В.Фильчаков, С.В.Щекин - Апатиты: КФ ПетрГУ, 2000.
    
12. 
    Павлов Л.А. Структуры и алгоритмы обработки данных в ЭВМ. Алгоритмы на графах: консп. лекций / Л.А.Павлов - Чуваш.ун-т: Чебоксары, 2001.
    
13. 
    Павлов Л.А. Структуры и алгоритмы обработки данных в ЭВМ. Методы быстрого поиска: консп. лекций / Л.А.Павлов - Чуваш.ун-т: Чебоксары, 1995.
    
14. 
    Павлов Л.А. Структуры и алгоритмы обработки данных в ЭВМ. Методы сортировки: консп. лекций / Л.А.Павлов - Чуваш.ун-т: Чебоксары, 1995.
    
15. 
    Павлов Л.А. Структуры и алгоритмы обработки данных в ЭВМ: метод. указания к курсовому проектированию / Л.А.Павлов - Чуваш.ун-т: Чебоксары, 1999.
    
16. 
    Сибуя М. Алгоритмы обработки данных / М.Сибуя, Т.Ямамото - М.: Мир, 1986.
    
17. 
    Ускова О.Ф. Программирование алгоритмов обработки данных / О.Ф.Ускова, Н.В.Огаркова, И.Е.Воронина, М.В.Мельников - СПб.: БХВ-Петербург, 2003.
    

Учебно-практическое издание


Пичугин Владимир Николаевич

Фёдоров Роман Вадимович


СТРУКТУРЫ И АЛГОРИТМЫ

КОМПЬЮТЕРНОЙ ОБРАБОТКИ ДАННЫХ


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


Редактор Н. А. Романова


Подписано в печать . Формат 60×84/16. Бумага газетная. Печать оперативная. Гарнитура Times. Усл. печ. л. 8,60. Уч.-изд. л. 8,29. Тираж 500 экз. Заказ №


Издательство Чувашского университета

Типография университета

428015 Чебоксары, Московский просп., 15