metoda_2013
.pdf
|
процессорах (например, в процессоре Pentium)? |
|||
|
Ответ обоснуйте. |
|
|
448 |
4. |
Подсистема |
памяти. |
Методы |
повышения |
|
быстродействия памяти. Виды ЗУ. Иерархическая |
|||
|
организация памяти. Какие вычислительные системы, |
|||
|
на каком уровне иерархической организации требуют |
|||
|
организации пакетного доступа к памяти. Ответ |
|||
|
поясните. |
|
|
452 |
5.Организация кэш-памяти. Зарисуйте структуру памяти (ОЗУ и кэш) для секторированного наборно-
ассоциативного кэша, состоящего из трех банков. |
|
Поясните её. |
456 |
6.Операционный и командный конвейер. Необходимые условия организации конвейеров этих типов. Режимы работы конвейеров. Объясните, почему при
организации конвейера команд не целесообразно |
|
использовать Принстонскую архитектуру ЭВМ? |
458 |
7. Многопроцессорные вычислительные комплексы |
|
(МПВК). Типы структур. Проблемы организации. |
|
Способы распределения ресурсов в МПВК. Сравните |
|
типы структур МПВК по следующим критериям: а) |
|
быстродействию; в) аппаратным затратам на систему |
|
коммутации; г) надежности. |
463 |
8.Машины, управляемые потоком данных. Недостатки принципа управления потоком данных. Граф потока данных. Типы вершин графа потока данных. Можно ли использовать принцип управления потоком данных в конвейерных вычислительных системах? Ответ
|
обоснуйте. |
466 |
XII. ПРАКТИЧЕСКАЯ ЧАСТЬ |
469 |
|
1. |
Разработка баз данных. |
469 |
2. |
UML диаграммы. |
486 |
3. |
Написание технического задания |
496 |
4. |
Написание постановки задачи. |
499 |
5. |
ГОСТ о стадиях разработки. |
500 |
6. |
ГОСТ о техническом задании. |
502 |
7. |
ГОСТ о видах программ и программных документов. |
506 |
8. |
Принципы Юзабилити |
509 |
|
10 |
|
СТРУКТУРЫ И ОРГАНИЗАЦИЯ ДАННЫХ В ЭВМ.
I.СТРУКТУРЫ И ОРГАНИЗАЦИЯ ДАННЫХ В ЭВМ.
1.Линейные списки. Стеки и очереди
Линейный список – это упорядоченная структура, каждый элемент которой связан со следующим элементом. Списки могут быть реализованы статически (на массивах) и динамически (на указателях).
Статические списки более просты в реализации, но у них есть недостатки:
1)они не обладают достаточной гибкостью при необходимости изменения их структуры,
2)память под них должна быть выделена на этапе компиляции и не будет освобождена до выхода из области действия списка. Динамические списки характеризуются высокой гибкостью. Это достигается благодаря возможности выделять и освобождать память под элементы в любой момент времени работы программы и возможности установить связь между любыми 2-я элементами с помощью указателей. Для организации связей между элементами динамической структуры данных требуется, чтобы каждый элемент содержал кроме информационных значений как минимум 1 указатель. Поэтому, наиболее часто в качестве элементов списков используют записи, которые могут объединять в единое целое разнородные элементы. В простейшем случае элемент динамической структуры должен состоять из 2 полей: информационного и указательного. Схематично:
Наибольшее распространение получили два вида линейных односвязных списков: стеки и очереди.
Кольцевой список – список, в котором последний элемент соединен с первым.
Достоинства.
1)Удобство создания структур данных для циклического обслуживания.
2) Из любого элемента можно попасть в любой.
3)Экономия памяти.
11
СТРУКТУРЫ И ОРГАНИЗАЦИЯ ДАННЫХ В ЭВМ.
Очередь - упорядоченный набор элементов, которые могут удаляться с одного его конца (называемого началом очереди) и помещаться в другой конец этого набора (называемого концом очереди). При работе с очередью первый помещенный в неё элемент удалится первым (т.е. реализуется принцип FIFO). Примеры - очередь в банке, на автобусной остановке, в ЭВМ – очередь на получение ресурсов, последовательность операций. При использовании массива начало очереди обычно находится в первом элементе, а конец задается индексом и меняется при изменении очереди. При создании динамической очереди требуются указатели: на начало очереди и на конец очереди. Кроме того, для освобождения памяти удаляемых элементов требуется дополнительный временный указатель:
struct node { int data;
struct node *next;
};
struct node *dequeue(struct node *head) { assert(head != NULL);
struct node *tmp = head->next; free(head);
return tmp;
}
struct node* enqueue(struct node *head, int data) { if (head == NULL) {
head = (struct node *)malloc(sizeof(struct node)); assert(head != NULL);
head->data = data; head->next = NULL;
return head;
}
struct node *tmp = head; while (tmp->next != NULL) {
tmp = tmp->next;
}
tmp->next = (struct node *)malloc(sizeof(struct node)); assert(tmp->next != NULL);
tmp = tmp->next;
12
СТРУКТУРЫ И ОРГАНИЗАЦИЯ ДАННЫХ В ЭВМ.
tmp->data = data; tmp->next = NULL;
return head;
}
void destroy(struct node *head) { struct node *current = head; while (current != NULL) {
head = current;
current = current->next; free(head);
}
}
Стек - частный случай линейного односвязного списка, для которого разрешено добавлять и удалять элементы только с одного конца списка, который называется вершиной (головой) стека. Т.о. элемент, помещенный в стек первым удалится из него последним (принцип FILO). В статическом представлении стек задается одномерным массивом, величина которого определяется с запасом. Необходимо обрабатывать ошибку переполнения и попытку удаления из пустого стека.
Для работы с динамическим стеком, в отличие от очереди, необходимо иметь один основной указатель на вершину стека и один дополнительный временный указатель, который используется для выделения и освобождения.
struct node { int data;
struct node *next;
};
struct node* push(struct node *stack, int data) {
struct node* tmp = (struct node*)malloc(sizeof(struct node));
13
СТРУКТУРЫ И ОРГАНИЗАЦИЯ ДАННЫХ В ЭВМ.
assert(tmp != NULL);
tmp->data = data; tmp->next = stack; return tmp;
}
struct node* pop(struct node *stack, int *element) { assert(stack != NULL);
assert(element != NULL);
struct node *tmp = stack; *element = stack->data; stack = stack->next; free(tmp);
return stack;
}
int empty(struct node *stack) { return (stack == NULL ? 1 : 0);
}
Двусвязные списки – списки, элементы которых имеют по 2 указателя – на правого и левого «соседа» по очереди. Удаление из таких списков происходит очень быстро и легко.
Интересным свойством такого списка является то, что для доступа к его элементам вовсе не обязательно хранить указатель на первый элемент. Достаточно иметь указатель на любой элемент списка. Первый элемент всегда можно найти по цепочке указателей на предыдущие элементы, а последний - по цепочке указателей на следующие.
Но наличие указателя на заголовок списка в ряде случаев ускоряет работу со списком.
Мультисписки
Иногда возникают ситуации, когда имеется несколько разных списков, которые включают в свой состав одинаковые элементы. В таком случае при использовании традиционных списков происходит многократное дублирование динамических
14
СТРУКТУРЫ И ОРГАНИЗАЦИЯ ДАННЫХ В ЭВМ.
переменных и нерациональное использование памяти. Списки фактически используются не для хранения элементов данных, а для организации их в различные структуры. Использование мультисписков позволяет упростить эту задачу.
Мультисписок состоит из элементов, содержащих такое число указателей, которое позволяет организовать их одновременно в виде нескольких различных списков. За счет отсутствия дублирования данных память используется более рационально.
Экономия памяти – далеко не единственная причина, по которой применяют мультисписки. Многие реальные структуры данных не сводятся к типовым структурам, а представляют собой некоторую комбинацию из них. Причем комбинируются в мультисписках самые различные списки – линейные и циклические, односвязанные и двунаправленные.
15
СТРУКТУРЫ И ОРГАНИЗАЦИЯ ДАННЫХ В ЭВМ.
2.Деревья и способы их организации в памяти. Рекурсивные алгоритмы обхода бинарных деревьев.
Дерево — одна из наиболее широко распространённых структур данных в информатике, эмулирующая древовидную структуру в виде набора связанных узлов. Является связанным графом, не содержащим циклы. Большинство источников также добавляют условие на то, что рёбра графа не должны быть ориентированными. В дополнение к этим трём ограничениям, в некоторых источниках указываются, что рёбра графа не должны быть взвешенными.
Представление деревьев
Существует множество различных способов представления деревьев. Наиболее общий способ представления изображает узлы как записи, расположенные в динамически выделяемой памяти с указателями на своих потомков, предков (или и тех и других), или как элементы массива, связанные между собой отношениями, определёнными их позициями в массиве (например, двоичная куча).
Методы обхода
Пошаговый перебор элементов дерева по связям между предками-узлами и потомками-узлами называется обходом дерева, а сам процесс называется обходом по дереву. Зачастую, операция может быть выполнена переходом указателя по отдельным узлам. Обход, при котором каждый узел-предок просматривается прежде его потомков называется предупорядоченным обходом или обходом в прямом порядке (pre-order walk), а когда просматриваются сначала потомки, а потом предки, то обход называется поступорядоченным обходом или обходом в обратном порядке (post-order walk). Существует также симметричный обход, при котором посещается сначала левое поддерево, затем узел, затем — правое поддерево, и обход в ширину, при котором узлы посещаются уровень за уровнем (N-й уровень дерева — множество узлов с высотой N). Каждый уровень обходится слева направо.
16
СТРУКТУРЫ И ОРГАНИЗАЦИЯ ДАННЫХ В ЭВМ.
Применение
1)управление иерархией данных;
2)упрощение поиска информации (см. обход дерева);
3)управление сортированными списками данных;
4)синтактический разбор арифметических выражений (англ. parsing), оптимизация программ;
5)в качестве технологии компоновки цифровых картинок для получения различных визуальных эффектов;
форма принятия многоэтапного решения
struct treeNode { int element; treeNode *left; treeNode *right;
};
treeNode* insert(int element, struct treeNode *root) { if (root == NULL) {
root = (struct treeNode *)malloc(sizeof(struct treeNode)); assert(root != NULL);
root->element = element; root->left = NULL; root->right = NULL;
}else if (element < root->element) { root->left = insert(element, root->left);
}else if (element > root->element) {
root->right = insert(element, root->right);
}
return root;
}
void destroy_up(struct treeNode *root) { if (root != NULL) {
17
СТРУКТУРЫ И ОРГАНИЗАЦИЯ ДАННЫХ В ЭВМ.
destroy(root->left); destroy(root->right); free(root);
}
}
void down(struct treeNode *root)
{
if (root != NULL) {
printf("%d\n", root->element); down(root->left); down(root->right);
}
}
void leftToRight(struct treeNode *root) { if (root != NULL) {
leftToRight(root->left); printf("%d\n", root->element); leftToRight(root->right);
}
}
3.Представления графов с помощью матрицы смежности и списковых структур
Граф=структура, состоящая из вершин и связей между ними (ребер). Если ребра имеют направление, то их называют дугами, а граф - ориентированным.
Представление графа
1) Матрица смежности = матрица, в которой aij равно 1, если вершина ai связана с вершиной aj, иначе 0.Для неориентированных графов эта матрица симметрична.
Достоинства: наглядность, легкий доступ к сыновьям и предшественникам, возможность использования аппарата матричной алгебры.
Недостатки: неэкономичность (особенно для разреженных графов),неудобство корректировки (добавления и удаления вершин).
2) Списковое представление.
18
СТРУКТУРЫ И ОРГАНИЗАЦИЯ ДАННЫХ В ЭВМ.
Часто использование матрицы смежности неудобно, т. к. число узлов требуется знать заранее. Для решения этой проблемы используют динамическое представление графа (аналогично представлению бинарных деревьев).
Граф представляется в виде двух списков: Первый описывает вершины графа и содежрит ссылку на ту часть второго списка, где описываются ребра для этой веришны:
Достоинства: экономичность, возможность корректировки Недостатки: сложность поиска, невозможность сразу найти предшественников текущей вершины. Эти недостатки можно преодолеть введением дополнительных списков, но это еще больше усложняет структуру.
Возможны и смешанные варианты представления графа. Например, для графов, допускающих существование нескольких дуг между двумя вершинами, элементами матрицы смежности могут быть указатели на соответствующие списки дуг.
4. Бинаpные деpевья поиска и их коppектиpовка
Бинарное дерево = дерево, у каждой вершины которого не более 2 сыновей.
Бинарное дерево поиска = бинарное дерево, в котором у каждой вершины ключевое значение больше ключевых значение левого поддерева и меньше ключевых значений правого поддерева.
Рассмотрим бинарное дерево
Вставка. Для того чтобы определить место вставки нового ключа, вершины просматриваются начиная с корня – Если ключ для вставки меньше значения ключа текущей вершины, то переходим по левой ветке, а если больше – то по правой.
Например, вставка ключа 48:
19