| UPOR | процедура генерирует упорядоченный по возрастанию массив чисел |
| NOTUPOR | процедура генерирует неупорядоченный (случайный) массив чисел |
| PR_CHOOSE | процедура осуществляет сортировку методом прямого выбора |
| PR_INS | процедура осуществляет сортировку методом прямой вставки |
| PR_OBM | процедура осуществляет сортировку методом прямого обмена |
| MAKE | процедура осуществляет исследование прямых методов сортировки |
| EXAMPLE | процедура выполняет контрольный пример (сортировку методом прямого включения) |
Текст программы
{$M 65000,65000,65000}
{Выделение памяти осуществляется для того, чтобы было возможно осуществлять исследование массива, содержащего 10000 элементов
***********************************************************
Данная программа является курсовой работой по дисциплине
'Структуры и алгоритмы обработки данных'
на тему 'Прямые методы сортировки'
В работе исследуются методы:
- прямого выбора;
- прямого обмена;
- прямой вставки.
Для исследования используются массивы из 10,100,100,10000 элементов.
**********************************************************}
{ использование модулей для осуществления вывода на экран }
uses crt,crtext,dcrt;***************************************************}
{** процедура, генерирующая упорядоченный по возрастанию массив чисел**}
{*********************************************************}
procedure upor(a:array of integer;var a1:array of integer);
var
{i - счетчик в циклах}
i:integer;
begin
{первый элемент принимает значение 1}
a[0]:=1;
for i:=1 to high(a) do
begin
{каждый последующий элемент принимает значение,
равное значению предыдущего элемента + случайное число}
a[i]:=a[i-1]+random(2);
end;
for i:=0 to high(a) do
a1[i]:=a[i];
end;
{*********************************************************}
{** процедура, генерирующая не упорядоченный (случайный) массив чисел**}
{*********************************************************}
procedure notupor(a:array of integer;var a1:array of integer);
var
{i - счетчик в циклах}
i:integer;
begin
for i:=0 to high(a) do
begin {элемент массива принимает случайное значение из диапазона 0 <= a[i] < 9999}
a[i]:=random(9999);
end;
for i:=0 to high(a) do
a1[i]:=a[i];
end;
{*********************************************************}
{***** процедура, осуществляющая сортировку методом прямого выбора***}
{*********************************************************}
procedure pr_choose(a:array of integer;var a1:array of integer;var k,k1:longint);
var
{i,j - счетчики в циклах}
i,j:integer;
{x - переменная для осуществления обмена между a[i] и a[j]}
x:integer;
begin
{k1 - переменная для подсчета количества сравнений
k - переменная для подсчета количества перемещений}
k:=0;k1:=0;
{high(a) - функция, возвращающая номер последнего элемента массива}
for i := 0 to high(a) - 1 do
begin
for j := i + 1 to high(a) do
begin
k1:=k1+1;
if a[i] < a[j] then
begin
k:=k+1;
{перестановка i-го с j-м элементом с помощью переменной x}
x:=a[i];
a[i]:=a[j];
a[j]:=x;
end;
end;
end;
for i:=0 to high(a) do
a1[i]:=a[i];
end;
{**********************************************************
***** процедура, осуществляющая сортировку методом прямого *
*************** обмена(метод пузырька) *********************
**********************************************************}
procedure pr_obm(a:array of integer;var a1:array of integer;var k,k1:longint);
var
{i,j - счетчики в циклах}
i,j:integer;
{x - переменная для осуществления обмена между a[j-1] и a[j]}
x:integer;
begin
{k1 - переменная для подсчета количества сравнений
k - переменная для подсчета количества перемещений}
k:=0;k1:=0;
for i := 1 to high(a) do
begin
for j := high(a) downto i do
begin
k1:=k1+1;
if a[j - 1] < a[j] then
begin
k:=k+1;
{обмена содержимым элементов массива a[j-1] и a[j]
с помощью переменной x}
x := a[j - 1];
a[j - 1] := a[j];
a[j] := x;
end;
end;
end;
for i:=1 to high(a) do
a1[i]:=a[i];
end;
{*********************************************************}
{*** процедура, осуществляющая сортировку методом прямого включения **}
{*********************************************************}
procedure pr_ins(a:array of integer;var a1:array of integer;var k,k1:longint);
var
{i,j - счетчики в циклах}
i,j:integer;
{x - переменная для осуществления обмена между a[i] и a[j]}
x:integer;
begin
{k1 - переменная для подсчета количества сравнений
k - переменная для подсчета количества перемещений}
k:=0;k1:=0;
for i := 1 to high(a) do
begin
x := a[i];
for j := i - 1 downto 0 do
begin
k1:=k1+1;
if x > a[j] then
begin
k:=k+1;
{обмена содержимым элементов массива a[j+1] и a[j]
с помощью переменной x}
a[j + 1] := a[j];
a[j]:=x;
end;
end;
end;
for i:=0 to high(a) do
a1[i]:=a[i];
end;
{**********************************************************
процедура, осуществляющая исследование методов сортировок для
*********** заданного массива чисел ***********************
**********************************************************}
procedure make(x1,n:integer;a,a1:array of integer;k:byte);
var
{количество перестановок}
kol_pr_ins, kol_pr_obm,kol_pr_choose:longint;
{количество сравнений}
kol_sr_ins, kol_sr_obm,kol_sr_choose:longint;
s:string;
begin
case k of
1:s:='упорядоченных по возрастанию';
2:s:='неупорядоченных (случайных)';
3:s:='упорядоченных по убыванию';
end;
{--------метод прямого включения---------}
pr_ins(a,a1,kol_pr_ins,kol_sr_ins);
{--------метод прямого обмена (метод пузырька)--------}
pr_obm(a,a1,kol_pr_obm,kol_sr_obm);
{---------метод прямого выбора----------}
pr_choose(a,a1,kol_pr_choose,kol_sr_choose);
{** вывод результата исследования **}
{вывод шапки таблицы}
gotoxy(3,x1);textcolor(cyan);textbackground(1);
writeln('Для ',high(a)+1,' ',s,' элементов:');
gotoxy(3,x1+1);textcolor(lightgreen);textbackground(1);
writeln('Методы: прямого включения прямого обмена прямого выбора');
{вывод полученных при исследовании данных}
gotoxy(3,x1+2);textcolor(white);write('перест.');
gotoxy(17,wherey);write(kol_pr_ins);
gotoxy(37,wherey);write(kol_pr_obm);
gotoxy(58,wherey);writeln(kol_pr_choose);
gotoxy(3,x1+3);write('сравн.');
gotoxy(17,wherey);write(kol_sr_ins);
gotoxy(37,wherey);write(kol_sr_obm);
gotoxy(58,wherey);writeln(kol_sr_choose);
str(high(a)+1,s);box(1,19,80,24,1,15,double,s+' элементов');
gotoxy(4,20);write('Сортировка ',s,' элементов по убыванию');
gotoxy(4,21);write('Сортируются ',s,' упорядоченных(по возрастанию) элементов');
gotoxy(4,22);write('Сортируются ',s,' неупорядоченных(случайных) элементов');
textbackground(lightgray);
textcolor(red);gotoxy(3,25);write('Esc - главное меню');
end;
{*********************************************
Пример сортировки методом прямого включения
Дан массив записей, содержащий:
-имя студента;
-кол-во баллов (рейтинг).
Необходимо отсортировать данный массив по
убыванию количества баллов у студента.
*********************************************}
procedure example;
type
{rec - запись, содержащая:
name - имя студента;
num - кол-во баллов (рейтинг).}
rec=record
name:string;
num:byte;
end;
var
{mas - массив записей rec}
mas:array[1..20] of rec;
{счетчики в циклах}
i,j:integer;
x:rec;
{переменные для подсчета количества сравнений и перемещений
во время сортировки}
k_sr,k_p:integer;
key:char;
begin
{переменные для подсчета количества сравнений и перемещений
во время сортировки}
k_sr:=0;k_p:=0;
randomize;
{Данный массив, содержащий имена студентов}
mas[1].name:='Иван';mas[2].name:='Петр';mas[3].name:='Сидор';
mas[4].name:='Василий';mas[5].name:='Денис';mas[6].name:='Геннадий';
mas[7].name:='Борис';mas[8].name:='Марат';mas[9].name:='Казбек';
mas[10].name:='Алексей';mas[11].name:='Владимир';mas[12].name:='Сидор';
mas[13].name:='Виталий';mas[14].name:='Александр';mas[15].name:='Михаил';
mas[16].name:='Евгений';mas[17].name:='Артур';mas[18].name:='Руслан';
mas[19].name:='Мурат';mas[20].name:='Аркадий';
{задание количества баллов у студента случайным образом}
for i:=1 to 20 do
mas[i].num:=random(19)+1;
{вывод пояснений}
getshadow;
textbackground(lightgray);
textcolor(red);gotoxy(15,1);write('Пример сортировки по убыванию методом прямого включения');
textbackground(lightgray);
textcolor(red); gotoxy(3,25); write('Esc - главное меню');
textcolor(red); gotoxy(65,25); write('F1 - задание');
box(58,0,80,25,1,15,double,'Статистика');
textcolor(lightmagenta);
gotoxy(59,3); write(' Сортировка методом ');
gotoxy(61,4); write('прямого включения.');
textcolor(white); gotoxy(59,5); write('---------------------');
box(31,0,57,25,1,15,double,'После сортировки');
textcolor(lightmagenta); gotoxy(32,3); write(' N Имя балл');
box(1,0,30,25,1,15,double,'До сортировки');
textcolor(lightmagenta); gotoxy(3,3); write('N Имя балл');
{вывод на экран исходного массива}
for i:=1 to 20 do
begin
textcolor(lightcyan); gotoxy(3,i+3); write(i);
textcolor(yellow); gotoxy(7,i+3); write(mas[i].name);
textcolor(lightred); gotoxy(25,i+3); writeln(mas[i].num);
end;
{сортировка по убыванию количества баллов}
for i := 2 to 20 do
begin
x := mas[i];
for j := i - 1 downto 1 do
begin
{k_sr - счетчик количества сравнений}
k_sr:= k_sr+1;
if x.num > mas[j].num then
begin
{k_p - счетчик количества перемещений}
k_p:=k_p+1;
{обмена содержимым элементов массива mas[j+1] и mas[j]
с помощью переменной x}
mas[j + 1] := mas[j];
mas[j]:=x;
end;
end;
end;
{вывод на экран отсортированного массива}
for i:=1 to 20 do
begin
textcolor(lightcyan); gotoxy(33,i+3); write(i);
textcolor(yellow); gotoxy(37,i+3); write(mas[i].name);
textcolor(lightred); gotoxy(52,i+3); writeln(mas[i].num);
end;
{вывод на экран количества сравнений и перестановок
в массиве, осуществленных во время сортировки}
textcolor(lightgreen); gotoxy(61,6); write('Сравнений:');
textcolor(lightgray); gotoxy(75,6); write(k_sr);
textcolor(lightgreen); gotoxy(61,8); write('Перестановок:');
textcolor(lightgray); gotoxy(75,8); write(k_p);
repeat
key:=' '; if keypressed then key:=readkey;
case key of
{#59 - код клавиши F1}
#59:begin
{вывод окна с заданием для контрольного примера}
{putshadow+box - вывод окна с тенью}
putshadow(15,7,65,15);box(15,7,65,15,lightgray,0,double,'Задание');
textcolor(red);
gotoxy(21,9); write('Дан список, содержащий фамилии студентов');
gotoxy(21,10); write('и их рейтинговые баллы. Необходимо от-');
gotoxy(21,11); write('сортировать данный список по убыванию ');
gotoxy(21,12); write('рейтинговых баллов.');
textcolor(yellow);gotoxy(50,15);write('Enter - отмена');
end;
{#13 - код клавиши Enter}
#13:getshadow;
end;
{#27 - код клавиши Esc}
until key=#27;
end;
{**********************************************************
************************ Основная программа **************
**********************************************************}
const
{массив строк - пунктов главного меню}
menu:array[1..7] of string=(' Пример сортировки ',' Исследование (10 эл-тов)',
' Исследование (100 эл-тов) ',
' Исследование (1000 эл-тов) ',
' Исследование (10000 эл-тов) ',
' О программе '
,' Выход ');
var
{массивы чисел, используемые для исследования}
a,a1:array[0..9] of integer; {10 - чисел}
b,b1:array[0..99] of integer; {100 - чисел}
c,c1:array[0..999] of integer; {1000 - чисел}
d,d1:array[0..9999] of integer; {10000 - чисел}
f:byte; {показатель того , какой массив
поступает в процедуру для упо-
рядочивания по убыванию:
1 - неупорядоченный (слу-
чайный);
2 - упорядоченный по воз-
растанию;
3 - упорядоченный по убы-
ванию}.
k:char;
item:byte;
begin
clrscr;cursoroff; {гашение курсора}
repeat
textbackground(0);clrscr;
{fill - процедура, заполняющая заданную область экрана заданными символами заданного цвета}
fill(lightgray,1,1,2,80,25,' ');
{menuv - процедура, выводящая на экран вертикальное меню}
menuv(25,10,menu,lightgray,black,red,lightgreen,yellow,'Сортировка',item,double);
{item - переменная, содержащая номер выбранного пункта меню}
case item of
1:example;
2:begin
{getshadow - процедура, убирающая тень от меню}
getshadow;
{** исследуются 10 упорядоченных по возрастанию элементов **}
{box - процедура, выводящая на экран окно}
box(1,0,80,18,1,15,double,'10 элементов');
{вызов процедуры upor, генерирующей упорядоченный по возрастанию
массив чисел}
upor(a,a);
{вызов процедуры make, осуществляющей исследование методов сортировки}
make(3,10,a,a1,1);
{** исследуются 10 неупорядоченных (случайных) элементов **}
{вызов процедуры notupor, генерирующей неупорядоченный(случайный) массив чисел}
notupor(a,a);
{вызов процедуры make, осуществляющей исследование методов сортировки}
make(8,10,a,a1,2);
{** исследуются 10 упорядоченных по убыванию элементов **}
{вызов процедуры make, осуществляющей исследование методов сортировки}
make(13,10,a1,a1,3);
{ожидание нажатия клавиши Esc}
repeat
k:=readkey;
until k=#27;
end;
3:begin
{getshadow - процедура, убирающая тень от меню}
getshadow;
{box - процедура, выводящая на экран окно}
box(1,0,80,18,1,15,double,'100 элементов');
{исследуются 100 упорядоченных по возрастанию элементов}
upor(b,b);
make(3,100,b,b1,1);
{исследуются 100 неупорядоченных (случайных) элементов}
notupor(b,b);
make(8,100,b,b1,2);
{исследуются 100 упорядоченных по убыванию элементов}
make(13,100,b1,b1,3);
repeat k:=readkey; until k=#27;
end;
4:begin
{getshadow - процедура, убирающая тень от меню}
getshadow;
box(1,0,80,18,1,15,double,'1000 элементов');
{исследуется 1000 упорядоченных по возрастанию элементов}
upor(c,c);
make(3,1000,c,c1,1);
{исследуется 1000 неупорядоченных (случайных) элементов}
notupor(c,c);
make(8,1000,c,c1,2);
{исследуется 1000 упорядоченных по убыванию элементов}
make(13,1000,c1,c,3);
repeat
k:=readkey;
until k=#27;
end;
5:begin
getshadow;
box(1,0,80,18,1,15,double,'10000 элементов');
{исследуются 10000 упорядоченных по возрастанию элементов}
upor(d,d);
make(3,10000,d,d1,1);
{исследуются 10000 неупорядоченных (случайных) элементов}
notupor(d,d);
make(8,10000,d,d1,2);
{исследуются 10000 упорядоченных по убыванию элементов}
make(13,10000,d1,d,3);
repeat
k:=readkey;
until k=#27;
end;
6:begin
{getshadow - процедура, убирающая тень от меню}
getshadow;
{ввод окна с темой курсовой работы}
box(10,5,70,15,lightgray,0,double,'О программе');
putshadow(10,5,70,15);
textcolor(brown);
gotoxy(12,7);write('Данная программа является курсовой работой по дисциплине');
gotoxy(21,8);write('"Алгоритмы и структуры обработки данных"');
gotoxy(30,9);write('Тема курсовой работы: ');
gotoxy(18,10);write(' "Исследование прямых методов сортировки"');
gotoxy(17,11);write('Курсовую работу выполнили студенты группы 95-ОА-21');
textcolor(red);gotoxy(3,25);write('Esc - главное меню');
repeat
k:=readkey;
until k=#27;
end;
end;
until item=7;
end.
{*********************конец программы********************}
Заключение
В учебном пособии были рассмотрены наиболее распространенные оперативные структуры данных и алгоритмы их обработки, которые традиционно применяются при создании программных систем и комплексов. В силу ограниченности объемом курса не было уделено внимания таким структурам, как В - деревья и графы, в разделе поиска опущен раздел хеширования. Однако, на базе уже рассмотренного материала эти разделы могут быть легко изучены самостоятельно.
Современное состояние и тенденции развития вычислительной техники как основного инструмента информатики таковы, что наряду с увеличением функциональности вычислительная техника приобретает свойства, позволяющие работать на ней пользователю, не разбирающемуся в программировании. Бурно развиваются в последнее время локальные, корпоративные и глобальные вычислительные сети. Создаются мощные накопители данных. Другими словами, основные процессы информационных технологий (обработка, обмен и накопление данных) поднялись на следующую ступень, что, естественно, требует новых подходов к организации данных в ЭВМ и созданию соответствующих систем программирования. Определяющими факторами к этому являются современные требования к пользовательскому интерфейсу и мультимедийные системы. Появились структкры графических данных и более крупные, интегральные информационные единицы - объекты. Следствием явилось бурное развитие объектно-ориентированных систем программирования: Visual BASIC, Visual PASCAL, Visual C ++ и т.д., используемых для создания программ, в основе которых лежит обработка объектных структур данных. Обмен объектными структурами в сетях вызван развитием сетевых операционных систем: Intranetware, Solaris, Windows NT и т.д. Обработка данных на многопроцессорных вычислительных системах потребовала создания новых структур данных, основанных на абстрактных представлениях и новых языков программирования: Modula 2, ADA, OCCAM.
Таким образом, развитие информационных технологий, их проникновение во все области жизнедеятельности человека требуют компьютерного отображения информации в виде соответствующих структкр данных и, естественно, каждый новый поступаельный шаг информатики будет сопровождаться соответсвующим шагом в области структур данных.
Литература
1. Бертисс А.Т. Структуры данных./Пер.с англ.- М.:Статистика,1974.
2. Вирт Н. Алгоритмы и структуры данных.- М.: Мир,1989.
3. Д. Райли. Абстракция и структуры данных. Вводный курс. М.: Мир, 1993.
4. Костин А.Е.,Шаньгин В.Ф. Организация и обработка структур данных в вычислительных системах.- М.: Высшая школа,1987.
5. Ленгсам и др. Структуры данных для персональных ЭВМ. - М.: Мир, 1989.
6. Трамбле Ж., Соренсон П. Введение в структуры данных. - М.: Машиностроение, 1982.
приложение.
Тесты с ответами
Лабораторная работа 1. Полустатические структуры данных (стеки).
6. В чём особенности очереди ?
- открыта с обеих сторон (верный);
- открыта с одной стороны на вставку и удаление;
- доступен любой элемент.
7. В чём сосбенности стека ?
- открыт с обеих сторон на вставку и удаление;
- доступен любой элемент;
- открыт с одной стороны на вставку и удаление (верный).
8. Какую дисциплину обслуживания принято называть FIFO ?
- стек;
- очередь (верный);
- дек.
9. Какая операция читает верхний элемент стека без удаления ?
- pop;
- push;
- stackpop (верный).
10. Каково правило выборки элемента из стека ?
- первый элемент;
- последний элемент (верный);
- любой элемент.
Лабораторная работа 2.Списковые структуры данных (односвязные очереди).
6. Как освободить память от удаленного из списка элемента ?
- p=getnode;
- ptr(p)=nil;
- freenode(p) (верный);
- p=lst.
7. Как создать новый элемент списка с информационным полем D ?
- p=getnode;
- p=getnode; info(p)=D (верный);
- p=getnode; ptr(D)=lst.
8. Как создать пустой элемент с указателем p ?
- p=getnode (верный);
- info(p);
- freenode(p);
- ptr(p)=lst.
9. Сколько указателей используется в односвязных списках ?
- 1 (верный);
- 2;
- сколько угодно.
10. В чём отличительная особенность динамических объектов ?
- порождаются непосредственно перед выполнением программы;
- возникают уже в процессе выполнения программы (верный);
- задаются в процессе выполнения программы.
Лабораторная работа 3.Списковые структуры данных.
6. При удалении элемента из кольцевого списка…
- список разрывается;
- в списке образуется дыра;
- список становится короче на один элемент (верный).
7. Для чего используется указатель в кольцевых списках ?
- для ссылки на следующий элемент;
- для запоминания номера сегмента расположения элемента;
- для ссылки на предыдущий элемент (верный);
- для расположения элемента в списке памяти.
8. Чем отличается кольцевой список от линейного ?
- в кольцевом списке последний элемент является одновременно и первым;
- в кольцевом списке указатель последнего элемента пустой;
- в кольцевых списках последнего элемента нет (верный);
- в кольцевом списке указатель последнего элемента не пустой.
9. Сколько указателей используется в односвязном кольцевом списке ?
- 1(верный);
- 2;
- сколько угодно.
10. В каких направлениях можно перемещаться в кольцевом двунаправленном списке ?
- в обоих (верный);
- влево;
- вправо.
Лабораторная работа 4. Модель массового обслуживания.
6. Чем отличается заявка первого приоритета от заявки второго приоритета ?
- тем, что заявка второго приоритета обслуживается с вероятностью P=1, а заявка первого приоритета обслуживается с вероятностью P(B);
- тем, что заявка второго приоритета становится в начало очереди, а первого приоритета становится в конец очереди (верный);
- ничем, если есть очередь.
7. Может ли заявка первого приоритета вытеснить из очереди заявку второго приоритета ?
- да, если P(B)=1;
- да;
- нет (верный).
8. Может ли на обслуживании находится заявка первого приоритета, если в очереди находится заявка второго приоритета ?
- да, если P(B)=1;
- да (верный);
- нет.
9. С помощью какой структуры данных наиболее рационально реализовать очередь ?
- стек;
- список (верный);
- дек.
10. Когда заявка покидает систему. Найдите ошибку.
- если заявка обслужилась подложенное ей число тактов;
- если заявка находится в очереди больше Т тактов;
- если заявок второго приоритета стало больше, чем заявок первого приоритета (верный).
Лабораторная работа 5. Бинарные деревья (основные процедуры).
6. Для включения новой вершины в дерево нужно найти узел, к которому её можно присоединить. Узел будет найден, если очередной ссылкой, определяющей ветвь дерева, в которой надо продолжать поиск, окажется ссылка:
- p=right(p);
- p=nil (верный);
- p=left(p).
7. Для написания процедуры над двумя деревьями необходимо описать элемент типа запись, который содержит поля:
- Element=Запись
Left,Right : Указатели
Rec : Запись;
- Element=Запись
Left : Указатель
Key : Ключ
Rec : Запись;
- Element=Запись (верный)
Left, Right : Указатели
Кеу : Ключ
Rec : Запись.
8. В памяти ЭВМ бинарное дерево удобно представлять в виде:
- связанных линейных списков;
- массивов;
- связанных нелинейных списков (верный).
9. Элемент t, на котрый нет ссылок:
- корнем (верный);
- промежуточным;
- терминальным (лист).
10. Дерево называется полным бинарным, если степень исходов вершин равна:
- 2 или 0 (верный);
- 2;
- М или 0;
- M.
Лабораторная работа 6. Сортировка методом прямого включения.
6. Даны три условия окончания просеивания при сортировке прямым включением. Найдите среди них лишнее.
- найден элемент a(i) с ключом, меньшим чем ключ у x;
- найден элемент a(i) с ключом, большим чем ключ у x (верный);
- достигнут левый конец готовой последовательности.
7. Какой из критериев эффективности сортировки определяется формулой M=0,01*n*n+10*n ?
- число сравнений (верный);
- время, затраченное на написание программы;
- количество перемещений;
- время, затраченное на сортировку.
8. Как называется сортировка, происходящая в оперативной памяти ?
- сортировка таблицы адресов;
- полная сортировка;
- сортировка прямым включением;
- внутренняя сортировка (верный);
- внешняя сортировка.
9. Как можно сократить затраты машинного времени при сортировке большого объёма данных ?
- производить сортировку в таблице адресов ключей (верный);
- производить сортировку на более мощном компьютере;
- разбить данные на более мелкие порции и сортировать их.
10. Существуют следующие методы сортировки. Найдите ошибку.
- строгие;
- улудшенные;
- динамические (верный).
Лабораторная работа 7. Сортировка методом прямого выбора.
6. Метод сортировки называется устойчивым, если в процессе сортировки…
- относительное расположенние элементов безразлично;
- относительное расположение элементов с равными ключами не меняется (верный);
- относительное расположение элементов с равными ключами изменяется;
- относительное расположение элементов не определено.
7. Улучшенные методы имеют значительное преимущество:
- при большом количестве сортируемых элементов (верный);
- когда массив обратно упорядочен;
- при малых количествах сортируемых элементов;
- во всех случаях.
8. Что из перечисленных ниже понятий является одним из типов сортировки ?
- внутренняя сортировка (верный);
- сортировка по убыванию;
- сортировка данных;
- сортировка по возрастанию.
9. Сколько сравнений требует улучшенный алгоритм сортировки ?
- n*log(n) (верный);
- en;
- n*n/4.
10. К какому методу относится сортировка, требующая n*n сравнений ключей ?
- прямому (верный);
- бинарному;
- простейшему;
- обратному.
Лабораторная работа 8. Сортировка с помощью прямого обмена.
6. Сколько сравнений и пeрестановок элементов требуется в пузырьковой сортировке ?
- n*lon(n);
- (n*n)/4 (верный);
- (n*n-n)/2.
7. Сколько дополнительных переменных нужно в пузырьковой сортировке помимо массива, содержащего элементы ?
- 0 (не нужно);
- всего 1 элемент (верный);
- n переменных (ровно столько, сколько элементов в массиве).
8. Как рассортировать массив быстрее, пользуясь пузырьковым методом ?
- одинаково (верный);
- по возрачстанию элементов;
- по убыванию элементов.
9. В чём заключается идея метода QuickSort ?
- выбор 1,2,…n – го элемента для сравнения с остальными;
- разделение ключей по отношению к выбранному (верный);
- обмен местами между соседними элементами.
10. Массив сортируется “пузырьковым” методом. За сколько проходов по массиву самый “лёгкий” элемент в массиве окажется вверху ?
- за 1 проход (верный);
- за n-1 проходов;
- за n проходов, где n – число элементов массива.
Лабораторная работа 9. Сортировка с помощью дерева.
6. При обходе дерева
слева направо получаем последовательность…
- отсортированную по убыванию;
- неотсортированную (верный);
- отсортированную по возрастанию.
7. Какое из трёх деревьев не является строго сбалансированным ?
- A;
- B(верный);
- C.
8. При обходе дерева слева направо его элемент заносится в массив…
- при втором заходе в элемент (верный);
- при первом заходе в элемент;
- при третьем заходе в элемент.
9. Элемент массива с ключом k=20 необходимо вставить в изображённое дерево так, чтобы дерево осталось отсортированным. Куда его нужно вставить ?
- левым сыном элемента 30 (верный);
- левым сыном элемента 41;
- левым сыном элемента 8.
10. При обходе какого дерева слева направо получается отсортированный по возрастанию массив ?
- A;
- B;
- C (верный).
Лабораторная работа 10. Исследование методов линейного и бинарного поиска.
6. Где эффективен линейный поиск ?
- в списке;
- в массиве;
- в массиве и в списке (верный).
7. Какой поиск эффективнее ?
- линейный;
- бинарный (верный);
- без разницы.
8. В чём суть бинарного поиска ?
- нахожденние элемента массива x путём деления массива пополам каждый раз, пока элемент не найден (верный);
- нахождение элемента x путём обхода массива;
- нахождение элемента массива х путём деления массива.
9. Как расположены элементы в массиве бинарного поиска ?
- по возрастанию (верный);
- хаотично;
- по убыванию.
10. В чём суть линейного поиска ?
- производится последовательный просмотр от начала до конца и обратно через 2 элемента;
- производится последовательный просмотр элементов от середины таблицы;
- производится последовательный просмотр каждого элемента (верный).
Лабораторная работа 11. Исследование методов поиска с перемещением в начало и транспозицией.
6. Где наиболее эффективен метод транспозиций ?
- в массивах и в списках (верный);
- только в массивах;
- только в списках.
7. В чём суть метода перестановки ?
- найденный элемент помещается в голову списка (верный);
- найденный элемент помещается в конец списка;
- найденный элемент меняется местами с последующим.
8. В чём суть метода транспозиции ?
- перестановка местами соседних элементов;
- нахождение одинаковых элементов;
- перестановка найденного элемента на одну позицию в сторону начала списка (верный).
9. Что такое уникальный ключ ?
- если разность значений двух данных равна ключу;
- если сумма значений двух данных равна ключу;
- если в таблице есть только одно данное с таким ключом (верный).
10. В чём состоит назначение поиска ?
- среди массива данных найти те данные, которые соответствуют заданному аргументу (верный);
- определить, что данных в массиве нет;
- с помощью данных найти аргумент.
Лабораторная работа 12. Поиск по дереву с включением.
6. В каком дереве при бинарном поике нужно перебрать в среднем N/2 элементов ?
- A;
- B (верный);
- C.
7. Сколько нужно перебрать элементов в сбалансированном дереве ?
E) N/2;
F) Ln(N);
G) Log2(N);
H) eN.
- A;
- B;
- C (верный);
- D.
8. Выберете вариант дерева, полученного после вставки узла -1.
- A (верный);
- B;
- C.
9. К какому элементу присоединить элемент 40 для вставки его в данное дерево ?
- к 30-му (верный);
- к 15-му;
- к –15-му;
- к 5-му.
10. Какой вид примет дерево после встаки элемента с ключом 58 ?
- A (верный);
- B;
- C.
Лабораторная работа 13. Поиск по дереву с исключением.
6. Выберете вариант дерева, полученного после удаления узла –3.
- A;
- B (верный);
- C.
7. Какой вариант дерева получится после удаления элемента –1, а затем –8 ?
- A;
- B (верный);
- C.
8. Выберете вариант дерева, полученного после удаления узла с индексом 0.
- A (верный);
- B;
- C.
9. Какие из следующих пар чисел могут стать корнями дерева после удаления элемента 10 в соответсвии с двумя способами удаления узла, имеющего двух сыновей ?
- 0 или 15;
- 0 или 20;
- 5 или 30;
- 5 или 15 (верный).
10. Какой вид примет дерево после удаления элемента с ключом 58 ?
- A (верный);
- B;
- C.
Лойко Валерий Иванович
Лаптев Сергей Владимирович
Структуры и алгоритмы
Обработки данных
(электронное издание)
Учебное пособие для вузов
Авторская правка
350044, Краснодар, Калинина, 13
Дата: 2019-12-10, просмотров: 263.
