Лабораторная работа 1. Полустатические структуры данных (стеки).
1. В чём особенности очереди ?
- открыта с обеих сторон ;
- открыта с одной стороны на вставку и удаление;
- доступен любой элемент.
2. В чём сосбенности стека ?
- открыт с обеих сторон на вставку и удаление;
- доступен любой элемент;
- открыт с одной стороны на вставку и удаление .
3. Какую дисциплину обслуживания принято называть FIFO?
- стек;
- очередь ;
- дек.
4. Какая операция читает верхний элемент стека без удаления?
- pop;
- push;
- stackpop .
5. Какого правило выборки элемента из стека ?
- первый элемент;
- последний элемент ;
- любой элемент.
Лабораторная работа 2.Списковые структуры данных (односвязные очереди).
1. Как освободить память от удаленного из списка элемента ?
- p=getnode;
- ptr(p)=nil;
- freenode(p) ;
- p=lst.
2. Как создать новый элемент списка с информационным полем D ?
- p=getnode;
- p=getnode; info(p)=D ;
- p=getnode; ptr(D)=lst.
3. Как создать пустой элемент с указателем p ?
- p=getnode ;
- info(p);
- freenode(p);
- ptr(p)=lst.
4. Сколько указателей используется в односвязных списках ?
- 1 ;
- 2;
- сколько угодно.
5. В чём отличительная особенность динамических объектов?
- порождаются непосредственно перед выполнением программы;
- возникают уже в процессе выполнения программы ;
- задаются в процессе выполнения программы.
Лабораторная работа 3.Списковые структуры данных.
1. При удалении элемента из кольцевого списка…
- список разрывается;
- в списке образуется дыра;
- список становится короче на один элемент .
2. Для чего используется указатель в кольцевых списках ?
- для ссылки на следующий элемент;
- для запоминания номера сегмента расположения элемента;
- для ссылки на предыдущий элемент ;
- для расположения элемента в списке памяти.
3. Чем отличается кольцевой список от линейного ?
- в кольцевом списке последний элемент является одновременно и первым;
- в кольцевом списке указатель последнего элемента пустой;
- в кольцевых списках последнего элемента нет ;
- в кольцевом списке указатель последнего элемента не пустой.
4. Сколько указателей используется в односвязном кольцевом списке ?
- 1;
- 2;
- сколько угодно.
5. В каких направлениях можно перемещаться в кольцевом двунаправленном списке ?
- в обоих ;
- влево;
- вправо.
Лабораторная работа 4. Модель массового обслуживания.
1. Чем отличается заявка первого приоритета от заявки второго приоритета ?
- тем, что заявка второго приоритета обслуживается с вероятностью P=1, а заявка первого приоритета обслуживается с вероятностью P(B);
- тем, что заявка второго приоритета становится в начало очереди, а первого приоритета становится в конец очереди ;
- ничем, если есть очередь.
2. Может ли заявка первого приоритета вытеснить из очереди заявку второго приоритета ?
- да, если P(B)=1;
- да;
- нет .
3. Может ли на обслуживании находится заявка первого приоритета, если в очереди находится заявка второго приоритета ?
- да, если P(B)=1;
- да ;
- нет.
4. С помощью какой структуры данных наиболее рационально реализовать очередь ?
- стек;
- список ;
- дек.
5. Когда заявка покидает систему. Найдите ошибку.
- если заявка обслужилась подложенное ей число тактов;
- если заявка находится в очереди больше Т тактов;
- если заявок второго приоритета стало больше, чем заявок первого приоритета .
Лабораторная работа 5. Бинарные деревья (основные процедуры).
1. Для включения новой вершины в дерево нужно найти узел, к которому её можно присоединить. Узел будет найден, если очередной ссылкой, определяющей ветвь дерева, в которой надо продолжать поиск, окажется ссылка:
- p=right(p);
- p=nil ;
- p=left(p).
2. Для написания процедуры над двумя деревьями необходимо описать элемент типа запись, который содержит поля:
- Element=Запись
Left,Right : Указатели
Rec : Запись;
- Element=Запись
Left : Указатель
Key : Ключ
Rec : Запись;
- Element=Запись
Left, Right : Указатели
Кеу : Ключ
Rec : Запись.
3. В памяти ЭВМ бинарное дерево удобно представлять в виде:
- связанных линейных списков;
- массивов;
- связанных нелинейных списков .
4. Элемент t, на котрый нет ссылок:
- корнем ;
- промежуточным;
- терминальным (лист).
5. Дерево называется полным бинарным, если степень исходов вершин равна:
- 2 или 0 ;
- 2;
- М или 0;
- M.
Лабораторная работа 6. Сортировка методом прямого включения.
1. Даны три условия окончания просеивания при сортировке прямым включением. Найдите среди них лишнее.
- найден элемент a(i) с ключом, меньшим чем ключ у x;
- найден элемент a(i) с ключом, большим чем ключ у x ;
- достигнут левый конец готовой последовательности.
2. Какой из критериев эффективности сортировки определяется формулой M=0,01*n*n+10*n ?
- число сравнений ;
- время, затраченное на написание программы;
- количество перемещений;
- время, затраченное на сортировку.
3. Как называется сортировка, происходящая в оперативной памяти ?
- сортировка таблицы адресов;
- полная сортировка;
- сортировка прямым включением;
- внутренняя сортировка ;
- внешняя сортировка.
4. Как можно сократить затраты машинного времени при сортировке большого объёма данных ?
- производить сортировку в таблице адресов ключей ;
- производить сортировку на более мощном компьютере;
- разбить данные на более мелкие порции и сортировать их.
5. Существуют следующие методы сортировки. Найдите ошибку.
- строгие;
- улудшенные;
- динамические .
Лабораторная работа 7. Сортировка методом прямого выбора.
1. Метод сортировки называется устойчивым, если в процессе сортировки…
- относительное расположенние элементов безразлично;
- относительное расположение элементов с равными ключами не меняется ;
- относительное расположение элементов с равными ключами изменяется;
- относительное расположение элементов не определено.
2. Улучшенные методы имеют значительное преимущество:
- при большом количестве сортируемых элементов ;
- когда массив обратно упорядочен;
- при малых количествах сортируемых элементов;
- во всех случаях.
3. Что из перечисленных ниже понятий является одним из типов сортировки ?
- внутренняя сортировка ;
- сортировка по убыванию;
- сортировка данных;
- сортировка по возрастанию.
4. Сколько сравнений требует улучшенный алгоритм сортировки ?
- n*log(n) ;
- en;
- n*n/4.
5. К какому методу относится сортировка, требующая n*n сравнений ключей ?
- прямому ;
- бинарному;
- простейшему;
- обратному.
Лабораторная работа 8. Сортировка с помощью прямого обмена.
1. Сколько сравнений и пeрестановок элементов требуется в пузырьковой сортировке ?
- n*lon(n);
- (n*n)/4 ;
- (n*n-n)/2.
2. Сколько дополнительных переменных нужно в пузырьковой сортировке помимо массива, содержащего элементы ?
- 0 (не нужно);
- всего 1 элемент ;
- n переменных (ровно столько, сколько элементов в массиве).
3. Как рассортировать массив быстрее, пользуясь пузырьковым методом ?
- одинаково ;
- по возрачстанию элементов;
- по убыванию элементов.
4. В чём заключается идея метода QuickSort ?
- выбор 1,2,…n – го элемента для сравнения с остальными;
- разделение ключей по отношению к выбранному ;
- обмен местами между соседними элементами.
5. Массив сортируется “пузырьковым” методом. За сколько проходов по массиву самый “лёгкий” элемент в массиве окажется вверху ?
- за 1 проход ;
- за n-1 проходов;
- за n проходов, где n – число элементов массива.
Лабораторная работа 9. Сортировка с помощью дерева.
1. При обходе дерева
слева направо получаем последовательность…
- отсортированную по убыванию;
- неотсортированную ;
- отсортированную по возрастанию.
2. Какое из трёх деревьев не является строго сбалансированным ?
- A;
- B;
- C.
3. При обходе дерева слева направо его элемент заносится в массив…
- при втором заходе в элемент ;
- при первом заходе в элемент;
- при третьем заходе в элемент.
4. Элемент массива с ключом k=20 необходимо вставить в изображённое дерево так, чтобы дерево осталось отсортированным. Куда его нужно вставить ?
- левым сыном элемента 30 ;
- левым сыном элемента 41;
- левым сыном элемента 8.
-
5. При обходе какого дерева слева направо получается отсортированный по возрастанию массив ?
- A;
- B;
- C .
Лабораторная работа 10. Исследование методов линейного и бинарного поиска.
1. Где эффективен линейный поиск ?
- в списке;
- в массиве;
- в массиве и в списке .
2. Какой поиск эффективнее ?
- линейный;
- бинарный ;
- без разницы.
3. В чём суть бинарного поиска ?
- нахожденние элемента массива x путём деления массива пополам каждый раз, пока элемент не найден ;
- нахождение элемента x путём обхода массива;
- нахождение элемента массива х путём деления массива.
4. Как расположены элементы в массиве бинарного поиска ?
- по возрастанию ;
- хаотично;
- по убыванию.
5. В чём суть линейного поиска ?
- производится последовательный просмотр от начала до конца и обратно через 2 элемента;
- производится последовательный просмотр элементов от середины таблицы;
- производится последовательный просмотр каждого элемента .
Лабораторная работа 11. Исследование методов поиска с перемещением в начало и транспозицией.
1. Где наиболее эффективен метод транспозиций ?
- в массивах и в списках ;
- только в массивах;
- только в списках.
2. В чём суть метода перестановки ?
- найденный элемент помещается в голову списка ;
- найденный элемент помещается в конец списка;
- найденный элемент меняется местами с последующим.
3. В чём суть метода транспозиции ?
- перестановка местами соседних элементов;
- нахождение одинаковых элементов;
- перестановка найденного элемента на одну позицию в сторону начала списка .
4. Что такое уникальный ключ ?
- если разность значений двух данных равна ключу;
- если сумма значений двух данных равна ключу;
- если в таблице есть только одно данное с таким ключом .
5. В чём состоит назначение поиска ?
- среди массива данных найти те данные, которые соответствуют заданному аргументу ;
- определить, что данных в массиве нет;
- с помощью данных найти аргумент.
Лабораторная работа 12. Поиск по дереву с включением.
1. В каком дереве при бинарном поике нужно перебрать в среднем N/2 элементов ?
- A;
- B;
- C.
2. Сколько нужно перебрать элементов в сбалансированном дереве ?
A) N/2;
B) Ln(N);
C) Log2(N);
D) eN.
- A;
- B;
- C ;
- D.
3. Выберете вариант дерева, полученного после вставки узла -1.
- A ;
- B;
- C.
-
4. К какому элементу присоединить элемент 40 для вставки его в данное дерево ?
- к 30-му ;
- к 15-му;
- к –15-му;
- к 5-му.
5. Какой вид примет дерево после встаки элемента с ключом 58 ?
- A ;
- B;
- C.
Лабораторная работа 13. Поиск по дереву с исключением.
1. Выберете вариант дерева, полученного после удаления узла –3.
- A;
- B ;
- C.
2. Какой вариант дерева получится после удаления элемента –1, а затем –8?
- A;
- B ;
- C.
3. Выберете вариант дерева, полученного после удаления узла с индексом 0.
- A ;
- B;
- C.
4. Какие из следующих пар чисел могут стать корнями дерева после удаления элемента 10 в соответсвии с двумя способами удаления узла, имеющего двух сыновей ?
- 0 или 15;
- 0 или 20;
- 5 или 30;
- 5 или 15 .
5. Какой вид примет дерево после удаления элемента с ключом 58 ?
- A ;
- B;
- C.
Методическое руководство к курсовой
работе
Введение
Курсовая работа выполняется студентами специальности 22.04 в четвертом семестре.
Целью курсовой работы является закрепление основ и углубление знаний в области структур и алгоритмов обработки данных в ЭВМ.
Тематика заданий на курсовую работу, приведенных в данных методических указаниях, может быть дополнена, расширена, увязана с решением актуальных научно-исследовательских задач, выполняемых на кафедре.
Требования к курсовой работе
1.1 Тема курсовой работы выдается каждому студенту индивидуально. В коллективных работах, в которых принимают участие два и более студентов, четко определяются объем и характер работы каждого студента. В задании формулируется задача, метод её решения.
1.2 Курсовая работа состоит из пояснительной записки, к которой прилагается дискета с отлаженными программами (пояснительная записка может быть выполнена в виде текстового файла в формате Microsoft Word).
1.3 В пояснительную записку должны входить:
- титульный лист (приложение Б);
- задание на курсовое проектирование (приложение А);
- реферат (ПЗ, количество таблиц, рисунков, схем, программ приложений, краткая характеристика и результаты работы);
- содержание:
а) постановка задачи исследования;
б) краткая теория по теме курсовой работы;
в) программная реализация исследуемых алгоритмов;
г) программа, с помощью которой проводилось исследование;
д) результаты проведенного исследования:
е) выводы;
- список использованной литературы;
- подпись, дата.
1.4 Пояснительная записка должна быть оформлена на листах формата А4, имеющих поля. Все листы следует сброшюровать и пронумеровать.
1.5 Исследование алгоритмов операций над структурами данных и методов сортировок и поиска проводить при следующих фиксированных количествах элементов в структурах: 10, 100, 1000, 10000.
1.6 Дополнительные условия выполнения курсовой работы выдаются руководителем работы.
Примерный перечень курсовых работ
1) Исследование стеков.
2) Исследование очередей.
3) Исследование кольцевых структур.
4) Исследование полустатических структур.
5) Исследование линейных одно- и двусвязных списков.
6) Исследование деревьев бинарного поиска.
7) Исследование методов сортировки включением.
8) Исследование методов сортировки выбором.
9) Исследование методов сортировки обменом.
10) Исследование методов сортировки с помощью деревьев.
11) Исследование улучшенных методов сортировки.
12) Исследование линейного, индексного и бинарного поисков.
13) Исследование методов оптимизации поиска.
14) Исследование задач поиска по дереву.
Пример выполнения курсовой работы
Постановка задачи
Осуществить исследование прямых методов сортировки:
- метод прямого выбора;
- метод прямой вставки;
- метод прямого обмена.
Исследование осуществить, используя массивы упорядоченных и неупорядоченных чисел по 10,100,1000 и 10000 элементов.
Краткая теория
При обработке данных важно знать и информационное поле данных, и размещение их в машине.
Различают внутреннюю и внешнюю сортировки:
- внутренняя сортировка - сортировка в оперативной памяти;
- внешняя сортировка - сортировка во внешней памяти.
Сортировка - это расположение данных в памяти в регулярном виде по их ключам. Регулярность рассматривают как возрастание (убывание) значения ключа от начала к концу в массиве.
Если сортируемые записи занимают большой объем памяти, то их перемещение требует больших затрат. Для того, чтобы их уменьшить, сортировку производят в таблице адресов ключей, делают перестановку указателей, т.е. сам массив не перемещается. Это метод сортировки таблицы адресов.
При сортировке могут встретиться одинаковые ключи. В этом случае при сортировке желательно расположить после сортировки одинаковые ключи в том же порядке, что и в исходном файле. Это устойчивая сортировка.
Эффективность сортировки можно рассматривать с нескольких критериев:
- время, затрачиваемое на сортировку;
- объем оперативной памяти, требуемой для сортировки;
- время, затраченное программистом на написание программы.
Выделяем первый критерий. Можно подсчитать количество сравнений при выполнении сортировки или количество перемещений.
Пусть Н = 0,01n2 + 10n - число сравнений. Если n < 1000, то второе слагаемое больше, если n > 1000, то больше первое слагаемое.
Т. е. при малых n порядок сравнения будет равен n2, при больших n порядок сравнения - n.
Порядок сравнения при сортировке лежит в пределах
от 0 (n log n) до 0 (n2); 0 (n) - идеальный случай.
Различают следующие методы сортировки:
- строгие (прямые) методы;
- улучшенные методы.
Строгие методы:
1) метод прямого включения;
2) метод прямого выбора;
3) метод прямого обмена.
Количество перемещений в этих трех методах примерно одинаково.
3.2.1 Сортировка методом прямого включения
Неформальный алгоритм
for i = 2 to n
x = a(i)
находим место среди а(1)…а(i) для включения х
next i
Программа на Паскале:
| for i := 2 to n do begin x := a[i]; a[0] = x; for j := i - 1 downto 1 do if x < a[j] then a[j + 1] := a[j] else a[j + 1] := x; end; |
Эффективность алгоритма:
Количество сравнений в худшем случае будет равно
(n - 1)(n - 1).
3.2.2 Сортировка методом прямого выбора
Рассматриваем весь ряд массива и выбираем элемент, меньший или больший элемента а(i), определяем его место в массиве - k, и затем меняем местами элемент а(i) и элемент а(k).
Программа на Паскале:
| for i := 1 to n - 1 do begin x := a[i]; k := i; for j := i + 1 to n do if x > a[j] then begin k := j; x := a[k]; end; a[k] := a[i]; a[i] := x; end; |
Эффективность алгоритма:
Число сравнений М = 
.
Число перемещений Cmin = 3(n - 1), Cmax = 3(n - 1) 
(порядок n2).
В худшем случае сортировка прямым выбором дает порядок n2, как и для числа сравнений, так и для числа перемещений.
Дата: 2019-12-10, просмотров: 444.
