Фонд оценочных средств дисциплины Алгоритмы и структуры данных, АиСД (стр. 4 )

25. Изобразите структуру линейного односвязного списка.

26. Изобразите структуру линейного двусвязного списка.

27. Перечислите достоинства и недостатки линейных двусвязных списков.

28. Изобразите возможные структуры двусвязных кольцевых списков.

29. Объясните назначение выделенного заглавного звена в списках.

30. На каких структурах данных могут строится списки?

31. Предложите алгоритм удаления из связного списка каждого чётного звена.

32. Предложите методы использования двусвязного кольцевого списка для работы с деком.

Раздел 15, 16.  Очереди и стеки. Исчерпывающий поиск

1. Что представляет собой очередь?

2. Какие известны виды очередей?

3. На основе каких структур данных могут организовываться очереди?

4. Какой характер имеет операция считывания для очередей?

5. Какими свойствами обладают очереди?

6. Каким недостатком обладает простая очередь? Каков способ борьбы с этим недостатком?

7. Чем отличается приоритетная очередь от простой?

8. К каким структурам данных относятся очереди?

9. Какой метод доступа к элементам используется в очередях? Опишите особенности этого метода.

10. Какие операции над элементами характерны для очередей?

11. Перечислите основные отличия очереди от массива.

12. Для решения каких задач применяются очереди?

13. В чем преимущества циклической очереди? Чем она отличается от простой очереди?

14. К каким позициям очереди возможен доступ при записи и чтении информации?

15. Предложите процедуры работы с очередью на основе односвязного линейного списка. Обеспечьте надёжность работы такой очереди.

16. Что представляет собой дек?

17. Предложите методы работы с деком при помощи двусвязного кольцевого списка.

18. Что представляет собой стек?

19. На основе каких структур данных могут организовываться стеки?

20. Чем отличается стек на основе массива от стека на основе связного списка?

21. Чем отличается стек на основе связного списка от собственно связного списка?

22. К каким структурам данных относятся очереди и стеки?

23. Перечислите основные отличия стека от очереди.

24. Какой метод доступа используется при доступе к элементам стека? В чем его особенности?

25. Перечислите основные операции, применяемые при работе со стеками. К каким позициям в стеке они могут применяться?

26. Какой характер имеет операция считывания для стеков?

27. Перечислите задачи, для решения которых применяются стеки.

28. Изобразите структуру звена динамического стека.

29. Как определить наличие или отсутствие элементов в стеке?

30. Как определить количество элементов в стеке?

Коды контролируемых компетенций: ОПК-1, 5, ПК-11, 12

Критерии оценки знаний

Оценка «зачтено» выставляется студенту, если он правильно ответил на 75% и более вопросов.

Оценка «не зачтено» выставляется студенту, если он правильно ответил менее чем на 75% вопросов.

Составитель ___________________

___________________________ 2015 г.        

Приложение 2

Федеральное агентство связи

Федеральное государственное образовательное бюджетное учреждение высшего

образования

«Поволжский государственный университет телекоммуникаций и информатики»

г. Самара

Кафедра Информационных систем и технологий

Комплект заданий для промежуточной аттестации (зачёт)

по дисциплине

Алгоритмы и структуры данных

1. Какие основные операции над элементами характерны для списков?

2. Какие позиции списка с выделенным ведущим звеном доступны для занесения новых элементов (при условии, что используются наиболее простые и унифицированные процедуры работы со списком)?

3. Из каких позиций списка можно удалять звенья (предположим, что выделенного ведущего звена нет)?

4. Какая следующая структура данных имеет наименьший объем служебной информации?

5. Какое минимальное количество полей может содержать каждое звено линейного односвязного списка, при условии, что в нём содержится полезная информация?

6. Какое минимальное количество полей может содержать каждое звено линейного двусвязного списка, при условии, что в нём содержится полезная информация?

7. Какое минимальное количество полей может содержать каждое звено кольцевого односвязного списка, при условии, что в нём содержится полезная информация?

8. Какое минимальное количество полей может содержать каждое звено кольцевого двусвязного списка, при условии, что в нём содержится полезная информация?

9. Из каких позиций списка с выделенным ведущим звеном можно удалять звенья?

10. В список с выделенным ведущим звеном подряд заносились целые числа, упорядоченные по возрастанию. Просмотр списка даёт следующий результат: 1, 2, 3, 4, 5, 6, 7. В какую позицию заносились данные?

11. В список с выделенным ведущим звеном подряд заносились целые числа, упорядоченные по возрастанию. Просмотр списка даёт следующий результат: 7, 6, 5, 4, 3, 2, 1. В какую позицию заносились данные?

12. В список с выделенным ведущим звеном подряд заносились целые числа, упорядоченные по убыванию. Просмотр списка даёт следующий результат: 1, 2, 3, 4, 5, 6, 7. В какую позицию заносились данные?

13. В список с выделенным ведущим звеном подряд заносились целые числа, упорядоченные по убыванию. Просмотр списка даёт следующий результат: 7, 6, 5, 4, 3, 2, 1. В какую позицию заносились данные?

14. В список с выделенным ведущим звеном подряд заносились символы, упорядоченные по возрастанию. Просмотр списка даёт следующий результат: a, b, c, d, e, f. В какую позицию заносились данные?

15. В список с выделенным ведущим звеном подряд заносились символы, упорядоченные по возрастанию. Просмотр списка даёт следующий результат: f, e, d, c, b, a. В какую позицию заносились данные?

16. В список с выделенным ведущим звеном подряд заносились символы, упорядоченные по убыванию. Просмотр списка даёт следующий результат: a, b, c, d, e, f. В какую позицию заносились данные?

17. В список с выделенным ведущим звеном подряд заносились символы, упорядоченные по убыванию. Просмотр списка даёт следующий результат: f, e, d, c, b, a. В какую позицию заносились данные?

18. В список без выделенного ведущего звена подряд заносились целые числа, упорядоченные по возрастанию. Просмотр списка даёт следующий результат: 1, 2, 3, 4, 5, 6, 7. В какую позицию заносились данные?

19. В список без выделенного ведущего звена подряд заносились целые числа, упорядоченные по возрастанию. Просмотр списка даёт следующий результат: 7, 6, 5, 4, 3, 2, 1. В какую позицию заносились данные?

20. В список без выделенного ведущего звена подряд заносились целые числа, упорядоченные по убыванию. Просмотр списка даёт следующий результат: 1, 2, 3, 4, 5, 6, 7. В какую позицию заносились данные?

21. В список без выделенного ведущего звена подряд заносились целые числа, упорядоченные по убыванию. Просмотр списка даёт следующий результат: 7, 6, 5, 4, 3, 2, 1. В какую позицию заносились данные?

22. В список без выделенного ведущего звена подряд заносились символы, упорядоченные по возрастанию. Просмотр списка даёт следующий результат: a, b, c, d, e, f. В какую позицию заносились данные?

23. В список без выделенного ведущего звена подряд заносились символы, упорядоченные по возрастанию. Просмотр списка даёт следующий результат: f, e, d, c, b, a. В какую позицию заносились данные?

24. В список без выделенного ведущего звена подряд заносились символы, упорядоченные по убыванию. Просмотр списка даёт следующий результат: a, b, c, d, e, f. В какую позицию заносились данные?

25. В список без выделенного ведущего звена подряд заносились символы, упорядоченные по убыванию. Просмотр списка даёт следующий результат: f, e, d, c, b, a. В какую позицию заносились данные?

26. Просмотр списка даёт следующий результат: 7, 6, 5, 4, 3, 2, 1. Известно, что данные заносились в начало списка. Как они были упорядочены перед вводом в список?

27. Просмотр списка даёт следующий результат: 7, 6, 5, 4, 3, 2, 1. Известно, что данные заносились в конец списка. Как они были упорядочены перед вводом в список?

28. Просмотр списка даёт следующий результат: 1, 2, 3, 4, 5, 6, 7. Известно, что данные заносились в начало списка. Как они были упорядочены перед вводом в список?

29. Просмотр списка даёт следующий результат: 1, 2, 3, 4, 5, 6, 7. Известно, что данные заносились в конец списка. Как они были упорядочены перед вводом в список?

30. Какая из следующих операций не применяется для связных списков: Просмотр, Добавление звена, Удаление звена, Поиск, Подсчёт числа уровней?

31. Какую операцию над списком выполняет процедура, содержащая операторы: { del->next->prev=del->prev; del->prev->next=del->next; ;delete del; }?

32. Имеется неупорядоченный массив целых чисел из N элементов. Сколько операций сравнения потребуется для установления факта отсутствия искомых данных в этом массиве?

33. Имеется неупорядоченный массив целых чисел из N элементов. Сколько операций сравнения потребуется для нахождения искомого ключа, если он находится в конце массива?

34. Имеется неупорядоченный массив целых чисел из N элементов. Сколько операций сравнения потребуется для нахождения искомого ключа, если он находится в начале массива?

35. Имеется неупорядоченный массив целых чисел из N элементов. Сколько операций сравнения в среднем требуется для нахождения искомого ключа, если поиск выполняется несколько раз и каждый раз ищется случайный ключ?

36. Имеется упорядоченный массив целых чисел из N (нечётное число) элементов. Сколько операций сравнения потребуется при двоичном поиске для нахождения искомого ключа, если он находится в точно в середине массива?

37. Имеется упорядоченный массив целых чисел из N элементов. Сколько операций сравнения потребуется при двоичном поиске для установления факта отсутствия искомых данных в этом массиве?

38. Имеется неупорядоченный массив целых чисел из N элементов. Для нахождения ключа используется последовательный поиск. Гарантируется ли в этом случае истинность результата поиска?

39. Имеется упорядоченный массив целых чисел из N элементов. Для нахождения ключа используется последовательный поиск. Гарантируется ли в этом случае истинность результата поиска?

40. Имеется неупорядоченный массив целых чисел из N элементов. Для нахождения ключа используется двоичный поиск. Гарантируется ли в этом случае истинность результата поиска?