<< Пред.           стр. 18 (из 19)           След. >>

Список литературы по разделу

  В учебном пособии были рассмотрены наиболее распространенные оперативные структуры данных и алгоритмы их обработки, которые традиционно применяются при создании программных систем и комплексов. В силу ограниченности объемом курса не было уделено внимания таким структурам, как В - деревья и графы, в разделе поиска опущен раздел хеширования. Однако, на базе уже рассмотренного материала эти разделы могут быть легко изучены самостоятельно.
  Современное состояние и тенденции развития вычислительной техники как основного инструмента информатики таковы, что наряду с увеличением функциональности вычислительная техника приобретает свойства, позволяющие работать на ней пользователю, не разбирающемуся в программировании. Бурно развиваются в последнее время локальные, корпоративные и глобальные вычислительные сети. Создаются мощные накопители данных. Другими словами, основные процессы информационных технологий (обработка, обмен и накопление данных) поднялись на следующую ступень, что, естественно, требует новых подходов к организации данных в ЭВМ и созданию соответствующих систем программирования. Определяющими факторами к этому являются современные требования к пользовательскому интерфейсу и мультимедийные системы. Появились структкры графических данных и более крупные, интегральные информационные единицы - объекты. Следствием явилось бурное развитие объектно-ориентированных систем программирования: 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. В чём состоит назначение поиска ?
 - среди массива данных найти те данные, которые соответствуют заданному аргументу (верный);
 - определить, что данных в массиве нет;
 - с помощью данных найти аргумент.

<< Пред.           стр. 18 (из 19)           След. >>

Список литературы по разделу