Мишенин_Теория экономических ИС_Практикум
.pdfЗадание 3.2. Напишите программу последовательного поис ка в последовательном отсортированном массиве реквизитов единственного значения q. Используйте любой доступный вам язык программирования.
Задание 3.3. Напишите программу последовательного поис ка в последовательном неотсортированном массиве реквизитов всех значений q. Используйте любой доступный вам язык про граммирования.
Задание 3.4. Напишите программу последовательного поис ка в последовательном отсортированном массиве реквизитов всех значений q. Используйте любой доступный вам язык програм мирования.
Задание 3.5. Напишите программу бинарного поиска в после довательном отсортированном массиве реквизитов единственно го значения q. Используйте любой доступный вам язык програм мирования.
Задание 3.6. Напишите программу бинарного поиска в после довательном отсортированном массиве реквизитов всех значений q. Используйте любой доступный вам язык программирования.
Задание 3.7. Определите для последовательного поиска:
•максимальное и среднее число сравнений при поиске в не упорядоченном массиве из М элементов единственного значе ния q\
•среднее число сравнений при поиске в упорядоченном мас сиве из М элементов единственного значения q, когда искомого значения в массиве нет.
Задание 3.8. Определим оболочку поискового запроса как множество всех реквизитов, участвующих в формулировке зап роса. Сколько различных оболочек может быть у файла из Л^ реквизитов?
Задание 3.9. Реализует ли приведенная ниже программа алго ритм сортировки простым выбором?
140
PROGRAM |
SimpleSelect; |
|
|
|
|
|
|
|||||||
const |
N = |
400; |
|
|
|
|
|
|
|
|
||||
var |
J^I^K |
|
: I n t e g e r ; |
|
|
|
|
|
|
|||||
|
Max/Ind: |
|
I n t e g e r ; |
|
of |
I n t e g e r ; |
|
|
||||||
|
A |
|
|
: |
Array |
[0..N] |
|
|
||||||
BEGIN |
|
t o |
N do |
|
|
|
|
|
|
|
||||
For |
I:=0 |
|
|
|
Write |
(A[I]:4) |
end; |
|||||||
|
begin |
A[I] |
:= |
Random (N); |
||||||||||
For J:=N |
downto 1 do |
|
|
|
|
|
|
|||||||
|
begin |
|
:= |
A [ J ] ; |
Ind |
:= |
J; |
|
|
|
||||
|
|
Max |
|
|
|
|||||||||
|
|
For |
I : = J |
downto |
0 |
do |
|
|
|
|
||||
|
|
|
If |
|
A[I]>Max |
Max := A [ I ] ; |
Ind |
:= I |
end; |
|||||
|
|
If |
|
|
then |
begin |
||||||||
|
|
|
I n d o J |
|
|
|
|
|
|
|
|
|||
|
|
|
then |
begin |
|
|
A[Ind] |
:= |
A [ J ] ; |
|||||
|
|
|
|
|
|
К |
:= |
A [ I n d ] ; |
||||||
|
|
|
|
|
|
A[J] |
:= |
К |
|
|
|
|
|
|
|
end; |
|
|
|
|
end |
|
|
|
|
|
|
||
For |
t o |
N do Write |
|
(A[I]:4) |
|
|
|
|||||||
I:=0 |
|
|
|
|
||||||||||
END. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Задание 3.10. Реализуйте сортировку для приведенного ниже файла по реквизиту «Фамилия» средствами табличного процес сора Excel. «Год» обозначает год поступления на работу. Экс портируйте отсортированные данные в таблицу Access.
1 |
Фамилия |
Год |
lAghion |
|
! 1994 |
Полковский |
1991 |
|
Amistrong |
1974 |
|
Arrow |
|
1981 |
Borkin |
|
1978 |
Архангельская |
1978 |
|
Borkin |
|
1970 |
Howitt |
|
1992 |
Sundgren |
1992 |
|
Sundgren |
1978 |
|
Wagner |
1969 |
|
Wagner |
1964 |
|
Беляев |
|
1977 |
Буренкова |
1980 |
|
Келехсаев |
1987 1 |
|
141
Задание 3.11. Напишите программу слияния двух упорядочен ных файлов с неодинаковым количеством элементов. Используйте любой доступный вам язык программирования.
Задание 3.12. Напишите программу индексирования основно го файла по одному реквизиту. Используйте любой доступный вам язык программирования.
Задание 3.13. Индексируйте приведенный ниже файл по рек визиту В. Необходимые дополнительные параметры выберите са мостоятельно.
1 А |
В |
1 Физический адрес |
|
020 |
10 |
5ТТо |
|
030 |
15 |
5120 |
|
130 |
19 |
5220 |
|
070 |
25 |
5160 |
|
080 |
29 |
5170 |
|
150 |
34 |
5240 |
|
050 |
36 |
5140 |
|
090 |
45 |
5180 |
|
160 |
55 |
5250 |
|
100 |
59 |
5190 |
|
ПО |
65 |
5200 |
|
140 |
72 |
5230 |
|
060 |
75 |
5150 |
|
010 |
80 |
5100 |
|
040 |
89 |
5130 |
1 |
120 |
98 |
5210 |
Задание 3.14. Реализуйте описанные выше операции индекси рования средствами СУБД Access не менее чем в трех вариантах, изменяя размер файла, размер участка индексирования и метод индексирования.
Задание 3.15. Рассчитайте среднее значение величины Y • Л для последовательного поиска, если количество релевантных за писей точно известно заранее.
Задание 3.16. Создайте средствами СУБД Access индексную структуру для поиска терминов по предметным областям, и пред метных областей - по терминам.
142
Задание 3.17. Рассмотрите файл из двух реквизитов А п В с первой записью (11,8) и последующими значениями А и В, полу чаемыми по формулам
A(i+l) = (7 • А(0 + 19) mod 13;
B{i+l) = (5 • В(/) + 11) mod 17,
состоящий из 25 записей. Создайте индексные файлы по реквизи там А и В и двум реквизитам совместно. Необходимые дополни тельные параметры выберите самостоятельно.
Задание 3.18. Дан основной массив. Каждая запись имеет по два ключевых признака из множества признаков А ={а, Ь, с, d, e,f, g, Л}. Признак имеет длину 4 байта, адрес записи - 8 байт. Опреде лить объем памяти под инвертированный массив.
Задание 3.19, Представьте схему инвертированного массива для следующего массива записей.
Адрес |
Ключевые признаки |
100 |
EBD |
140 |
СЕА |
200 |
DE |
300 |
СЕ |
3.2. Цепная организация данных
Методические указания
Списком называется множество записей, занимающих произ вольные участки памяти, последовательность обработки которых задается с помощью адресов связи. Адресом связи некоторой за писи называется реквизит, в котором хранится начальный адрес или номер записи, обрабатываемой после этой записи. Последо вательность обработки записей в списке определяется возраста нием значений ключа в записях.
В списке вьщеляется собственная информация (записи с со держательными сведениями) и ассоциативная информация, т.е. все адреса связи.
143
Описание записей списка на языке программирования (напри мер, Паскаль) может быть проведено двумя способами.
1. Определение адресов связи как начальных адресов записей:
type ref='^node; node=record
key: integer; {ключевой реквизит записи} other: string[30]; {остальные реквизиты} next: ref {адрес связи}
end;
2. Определение адресов связи как номеров записей:
const М=12; type node=record
key: integer; {ключевой реквизит записи} other: string[30]; {остальные реквизиты} next: integer {адрес связи}
end;
var t:array[1..М] of node;
Второй вариант является более практичным, особенно если требуется хранить список на внешнем запоминающем устройстве.
При списковой организации данных необходим специальный реквизит, называемый указателем списка, который содержит на чальный адрес или номер первой в порядке обработки записи списка. Кроме того, адрес связи последней записи списка должен содержать специальное значение, называемое концом списка и отмечающее, что последующих записей у данной записи нет. Обычно конец списка обозначается нулем.
Графически адрес связи изображается в виде прямоугольни ка со стрелкой, стрелка указывает на запись, адрес хранения ко торой содержится в адресе связи.
При формировании упорядоченного списка записей возмож ны два варианта:
•вновь поступающие записи вставлять так, чтобы не нару шать упорядоченность по ключу;
•создать сначала неупорядоченный список, а затем отсорти ровать его.
Учитывая, что для сортировки можно использовать метод сли яния, второй вариант следует признать более целесообразным.
144
в итоге время формирования упорядоченного списка пропор ционально Т-- М • logM.
Для поиска данных в упорядоченном списке можно приме нять те же методы, что и в последовательном массиве, однако эффективность этих методов иная, поскольку адреса связи созда ют возможность быстрого доступа только к следующей записи списка.
Для поиска данных в однонаправленном списке используется единственный метод - последовательный поиск. Ключевой рек визит первой записи (ее адрес извлекается из указателя списка) сравнивается с искомым значением q, затем такое же сравнение выполняется для ключа второй записи, которая извлекается по адресу связи первой записи, и т.д. Время поиска, естественно, пропорционально Т^М.
Цепным каталогом называется сплошной участок памяти (или несколько таких участков), в котором одновременно размеща ются список обрабатываемых записей и список свободных пози ций памяти (УСП). Адрес связи, отмечающий первую обрабаты ваемую запись, называется указателем списка (УС). Адрес связи, отмечающий первую свободную позицию памяти, называется ука зателем свободной памяти. Адрес связи последней записи (или последней позиции свободной памяти) в списке называется кон цом списка, и здесь отмечается нулевым значением.
Рассмотрим пример цепного каталога, в котором адреса свя зи представлены номерами соответствующих записей. Описание каталога на языке Паскаль имеет вид:
const |
М=9; |
|
type |
|
|
node=record |
|
|
key: |
i n t e g e r ; |
{ключевой реквизит записи} |
n e x t : i n t e g e r |
{адрес связи} |
|
end; |
|
|
var t : a r r a y [ 1 . . М ] of node;
Первоначальное состояние каталога показано на рис. 3.2 а. Включение и исключение записей в цепном каталоге предпо лагает поиск местоположения включаемой (исключаемой) запи си и замену значений адресов связи для установления новой пос ледовательности записей основного списка и списка свободной
памяти.
Приведем алгоритм вставки записи с ключом FB цепной каталог.
145
1. Найти в каталоге запись с ключом непосредственно мень ше, чем F (предшествующая запись).
2.Поместить запись с ключом F в первую позицию свобод ной памяти.
3.Заменить УСП на адрес связи новой записи, этот адрес - на адрес связи предшествующей записи, а последний - на первона чальное значение УСП.
На рис. 3.2 а вставляется запись с ключом F=61. Алгоритм удаления записи с ключом Ж из каталога.
1. Найти в каталоге запись с ключом непосредственно мень ше, чем W (предшествующая запись).
2. Заменить УСП на адрес связи предшествующей записи, этот адрес - на адрес связи исключаемой записи, а последний - на пер воначальное значение УСП.
На рис. Ъ.2 б удаляется запись с ключом W=30.
|
KEY |
NEXT US = 6 |
|
KEY |
NEXT US = 6 |
||
1 |
50 |
5 |
USP = 3 |
1 |
50 |
5 |
USP = 7 |
|
|
||||||
2 |
20 |
8 |
|
2 |
20 |
8 |
|
3 |
|
7 |
|
3 |
61 |
9 |
|
4 |
40 |
1 |
|
4 |
40 |
1 |
|
5 |
60 |
9 |
|
5 |
60 |
3 |
|
6 |
10 |
2 |
|
6 |
10 |
2 |
|
7 |
30 |
0 |
|
7 |
30 |
0 |
|
8 |
4 |
1 |
8 |
4 |
1 |
||
9 |
70 |
0 |
9 |
70 |
0 |
||
До вставки записи |
После вставки записи |
||||||
|
KEY |
NEXT |
us = 6 |
|
KEY |
NEXT |
US = 6 |
1 |
50 |
5 |
USP = 3 |
1 |
50 |
5 |
USP = 8 |
|
|
||||||
2 |
20 |
8 |
|
2 |
20 |
4 |
|
3 |
|
7 |
|
3 |
|
7 |
|
4 |
40 |
1 |
|
4 |
40 |
1 |
|
5 |
60 |
9 |
|
5 |
60 |
9 |
|
6 |
10 |
2 |
|
6 |
10 |
2 |
|
7 |
30 |
0 |
|
7 |
30 |
0 |
|
8 |
4 |
1 |
8 |
3 |
1 |
||
9 |
70 |
0 |
9 |
70 |
0 |
||
До удаления записи |
После удаления записи |
||||||
Рис. 3.2. Корректировка данных в цепном каталоге
146
Оценка времени корректировки складывается из времени реализации поиска и времени на замену значений адресов свя зи. В последнем случае число пересылок адресов связи всегда одинаково ц не зависит от числа записей в цепном каталоге, поэтому затраты времени на поиск при корректировке явля ются доминирующими и время корректировки пропорциональ но Т-М.
Задания
Задание 3.20. Установите адреса связи и указатели для обра ботки записей по возрастанию значений ключа.
|
УС |
0 |
|
УСП |
0 |
Адрес записи |
Значение ключа |
Адрес связи |
10375
11215
1297
13115
1535
16400
Задание 3.21. Установите адреса связи и указатели для обра ботки записей по возрастанию значений ключа.
|
УС |
0 |
|
УСП |
0 |
Адрес записи |
Значение ключа |
Адрес связи |
1028
1145
1264
1315
1431
16 98
147
Задание 3.22. Установите адреса связи и указатели для обра ботки записей по возрастанию значений ключа.
|
УС |
0 |
|
УСП |
0 |
Адрес записи |
Значение ключа |
Адрес связи |
10 |
|
|
1116
1237
1385
1419
1533
1691
Задание 3.23. Установите адреса связи и указатели для удале ния записи с ключом 45 из цепного каталога.
|
УС |
11 |
|
УСП |
10 |
Адрес записи |
Значение ключа |
Адрес связи |
10 |
|
0 |
11 |
16 |
14 |
12 |
37 |
13 |
13 |
85 |
16 |
14 |
19 |
15 |
15 |
33 |
12 |
! 16 |
91 |
0 |
Задание 3.24. Установите адреса связи и указатели для обра ботки записей по возрастанию значений ключа.
|
УС |
0 |
|
УСП |
0 |
Адрес записи |
Значение ключа |
Адрес связи |
1015
1120
1210
1318
1425
1536
148
Задание 3.25. Установите адреса связи и указатели для удале ния записи с ключом 45 из цепного каталога.
|
У С |
13 |
1 |
Адрес записи |
У С П |
15 |
|
Значение ключа |
Адрес связи |
|
|
10 |
28 |
14 |
|
11 |
45 |
12 |
|
12 |
64 |
16 |
|
13 |
15 |
10 |
|
14 |
31 |
И |
|
15 |
98 |
0 |
1 |
16 |
0 |
Задание 3.26. Установите адреса связи и указатели для встав ки записи с ключом 16 в цепной каталог.
|
У С |
12 |
|
Адрес записи |
УС П |
16 |
|
Значение ключа |
Адрес связи |
|
|
10 |
15 |
13 |
|
11 |
20 |
14 |
|
12 |
10 |
10 |
|
13 |
18 |
И |
|
14 |
25 |
15 |
|
15 |
36 |
0 |
1 |
16 |
|
0 |
Задание 3.27. Установите адреса связи и указатели для удале ния записи с ключом 35 из цепного каталога.
|
У С |
15 |
Адрес записи |
УС П |
14 |
Значение ключа |
Адрес связи |
|
10 |
375 |
16 |
11 |
215 |
10 |
12 |
97 |
13 |
13 |
115 |
11 |
14 |
35 |
0 |
15 |
12 |
|
16 |
400 |
0 |
149