дипломы,диссертации,курсовые,контрольные,рефераты,отчеты на заказ

Структура и алгоритмы обработки данных в ЭВМ
Кафедра АСУ
Горитов А.Н.
Томск-2000

Введение в предмет.
дипломы,курсовые,рефераты,контрольные,диссертации,отчеты на заказ

№ 1
Атрибут объекта - это:
• уникальный набор свойств.

№ 2
Наборы атрибутов различных объектов:
• могут пересекаться, но не могут совпадать.

№ 3
Экземпляр объекта описывается:
• конкретным набором значений атрибутов.

Основные типы и структуры данных ЭВМ.

№ 4
Минимальная адресуемая единица памяти:
• байт.

№ 5
Минимальным полем фиксированной длины является:
• полуслово.

№ 6
Важнейший архитектурный признак ЭВМ:
• слово.

№ 7
Структуры, обладающие свойством “непредсказуемости размера структуры в процессе ее обработки”:
• полустатические структуры;
• динамические структуры.

№ 8
Структуры, обладающие свойством “отсутствие физической смежности элементов структуры в памяти ЭВМ”:
• полустатические структуры;
• динамические структуры.

№ 9
К динамическим структурам относятся:
• связанные списки.

№ 10
К статическим структурам относятся:
• массивы, записи, множества.

№ 11
К полустатическим структурам относятся:
• стеки, очереди, деки.

№ 12
Статические структуры отличаются от полустатических:
• постоянством структуры в течении всего времени ее существования;
• отсутствием информации об отношениях между элементами в самих элементах структуры.

№ 13
Тип Character предназначен для:
• хранения одного символа - буквы, знака или кода.

№ 14
Тип Boolean предназначен для:
• запоминания логического значения.

№ 15
Индексы массива:
• могут вычисляться.

№ 16
Представление строки в Turbo Pascale:
• длина строкового типа в байтах равна его максимальной строке плюс единица;
• первый байт содержит текущую длину строки, следующие - символы строки.

№ 17
Вариантная часть в записи:
• должна быть последней.

№ 18,19
Множество это:
• неупорядоченная совокупность элементов;
• произвольный набор однотипных объектов, понимаемых как единое целое.

№ 20
Базовым типом множества может быть:
• перечислимый и интервальный.

№ 21
Множеством - степенью называется:
• множества всех подмножеств.

№ 22
var p:set of 0..9; i, j: integer;
Если i=3 и j=5, то какое значение получит переменная p при выполнении следующего оператора присваивания - p := [2*i..j]:
• [ ].

№ 23
Чему равен результат [ 1, 3, 5 ] * [ 2, 4 ]:
• [ ].

№ 24
Вычислить значения отношений:
1) [ 2 ] <> [ 2, 2, 2 ];
2) [ 'a', 'b' ] = [ 'b', 'a' ];
3) [ 4, 5, 6 ] = [ 4..6 ];
4) [ 'c, 'b' ] = [ 'c'..'b' ];
5) [ 2, 3, 5, 7 ] <= [ 1..9 ]
6) [ 3, 6..8 ] <= [ 2..7, 9 ]
• (false true true false true false)

№ 25
1) [ ] <= [ '0'..'9']
2) 'q' in [ 'a'..'z' ]
3) trunc (3.9) in [ 1, 3, 5 ];
4) odd (4) in [ ];
5) [ 2 ] < [ 1..3 ];
6) 66 = [ 66 ].
• (true true true false ошибка ошибка)

№ 26
Основной метод, используемый при файловой сортировки:
• метод слияния.

№ 27
В последовательном файле доступ к элементам:
• доступен только один элемент, другие - только путем последовательного продвижения по файлу.

№ 28
В качестве базового типа файла может быть:
• простой или структурированный, но не файл .

№ 29
Под слиянием упорядоченных файлов понимают:
• объединение этих файлов в одну упорядоченную последовательность при помощи циклического выбора элементов, доступных в данный момент

№ 31
Фазой называется:
• операция, которая однократно обрабатывает всё множество данных.

№ 32
Наименьший подпроцесс, который, повторяясь, образует процесс сортировки - это:
• проход.

№ 33
Название метода?
Метод сортировки файлов, который состоит в следующем:
1) последовательность А разбивается на две половины В и С;
2) последовательности В и С сливаются при помощи объединения отдельных элементов в упорядоченные пары;
3) полученной последовательности присваивается имя А, после чего повторяются шаги 1) , 2), при этом упорядоченные пары сливаются в упорядоченные четверки;
4) предыдущие шаги повторяются при этом четверки сливаются в восьмерки и т. д.
• простым слиянием.

№ 34
Метод сортировки, при котором каждый раз сливаются две самые длинные возможные последовательности называется:
• метод естественного слияния.


№ 35
const n = 100;
var aa : array [ 1..n ] of tt;
t: integer;
где tt - любой тип.
Это определение:
• стека.

№ 36
const n = 100;
var aa : array [ 1..n ] of tt;
f, r : integer;
где tt - любой тип.
Это определение:
• очереди.

№ 37
Чему будет равен указатель на стек, если стек стал пустым, после извлечения из него всех элементов?
• нулю.

№ 38
Дек - это:
• сочетание очереди и стека.

№ 39
Неверная операцию для очереди:
• включение нового элемента перед элементом с номером k.

№ 40
Стек - это линейный последовательный список, в котором:
• включение элементов выполняется с одного конца, т.е. доступен только последний элемент.

№ 41
В вершине стека находится:
• последний по времени поступления элемент.

№ 42
Стек считается пустым если:
• вершина стека смещена вниз на длину одной ячейки относительно низа стека.

№ 43
В односвязном списке каждый элемент состоит из:
• содержательного поля и поля указателя.

№ 44
Неверное свойство связных списков:
• невозможно включить элемент в связный список в любое место списка.

№ 45
Свойство, присущее кольцевому связному списку:
• просмотр списка можно начинать с любого элемента.

№ 46
Данные типа Pointer:
• указывают на некоторые данные или группу данных.

№ 47
Область памяти, ранее занимаемая элементом динамической структуры после ее освобождения:
• может повторно использоваться для этой же динамической структуры.

№ 48
Элементы, выделяемые динамически:
• не имеют имени.

№ 49
type A = array [ 1..100 ] of integer;
PA = ^a;
Здесь значение переменной PA является:
• ссылка на динамический объект, значением которого является массив из 100 целых чисел.

№ 50
Пусть Р - указатель, определенный ранее. Тогда Р^ означает:
• сама переменная.

№ 51
Указатель определен как
VAR J : ^integer;
• переменная J может использоваться только для ссылки на элементы типа integer.

№ 52
После введения в употребление ссылочной переменной она: ссылается на программные объекты; имеет своим значение пустую ссылку Nil?
• не имеет ни того, ни другого.

№ 53
Пусть объявлена переменная - var p : T;
При выполнении операции new(p):
• выделяется память для переменной типа Т, а переменная указатель р получает значение ссылки на динамически размещенную переменную.

№ 54
После выполнения блока программы
var j : ^integer;
new (j);
j^ : 7;
j := Nil;
• указатель j никуда не указывает, но область остается занятой.

№ 55
Процедура dispose(p):
• освобождает область памяти, на которую указывает указатель p.

№ 56
Ошибка при выполнении процедуры dispose(p) не выдается в случае:
• если р имеет любое значение, кроме Nil.

№ 57
Что описывает ниже приведенный фрагмент программы
type a = ^b;
b = record
name : integer;
c : a;
end;
var ff : a;
• стек.

№ 58
Что выполняет ниже приведенная процедура:
type a = ^b;
b = record
name : integer;
c : a;
end;
var ff : a;
Procedure d( k : integer);
var w : a;
begin
new (w);
w^.name := k;
w^.c := ff;
end;
• размещает новый элемент в стеке.

№ 59
type a = ^b;
b = record
name : integer;
c : a;
end;
var ff : a;
Procedure m(var u : integer);
var L : a;
begin
L := ff;
u := L^.name;
a := L^.c;
dispose( L );
end;
• извлекает элемент из стека.

№ 60
Описание
a = ^b;
b = record
name : integer;
c : a;
end;
d = record
aa = a;
bb = a;
end;
var E : d
Это:
• описание очереди.

№ 61
a = ^b;
b = record
name : integer;
c : a;
end;
d = record
aa = a;
bb = a;
end;
var E : d
Function S (m : d): Boolean;
begin
if m.aa = Nil then
S := true else S:= false
end;
Эта функция:
• проверка наличия элементов в очереди.

№ 62
a = ^b;
b = record
name : integer;
c : a;
end;
d = record
aa = a;
bb = a;
end;
var E : d
Procedure asd( var m : d; st : integer);
var p : a;
begin
new(p);
p^.name := st;
p^.c := Nil;
if s(m) then
begin
m.aa := p;
m.tt := p end
else begin
m.bb^.c := p;
m.tt := p
end;
end;
Это процедура выполняет:
• размещение нового элемента в очереди.

№ 63
a = ^b;
b = record
name : integer;
c : a;
end;
d = record
aa = a;
bb = a;
end;
var E : d
Function k ( m: d ): integer;
begin
k := m.aa^.name;
end;
Это функция выполняет:
• извлечение значения объекта, стоящего в начале очереди.

№ 64
a = ^b;
b = record
name : integer;
c : a;
end;
d = record
aa = a;
bb = a;
end;
var E : d
Procedure n ( var m : d );
var w : a;
begin
w := m.aa;
m.aa := m.aa^.next;
dispose(w);
end;
Эта процедура выполняет:
• удаление старшего элемента из очереди.


№ 65
Элемент в дереве, на который не ссылается ни какой другой элемент:
• корень.

№ 66
Элемент в дереве, на который могут ссылаться другие элементы, и он в свою очередь может ссылаться на несколько элементов следующего уровня иерархии:
• узел.

№ 67
Иерархическая структура, каждый элемент промежуточного уровня которого порожден только одним элементом более высокого уровня:
• дерево.

№ 68
Элементы дерева, которые не ссылаются на другие элементы:
• лист.

№ 69
Связь между элементами предыдущего уровня и последующего уровня в дереве:
• предок - потомок.

№ 70
“Вырожденным деревом” называют:
• список.

№ 71
Любое дерево нельзя описать:
• списками.

№ 72
Высотой дерева называется:
• максимальный уровень дерева.

№ 73
Степень дерева называется:
• максимальная степень всех узлов дерева.

№ 74
Длиной пути к вершине x называется:
• число ветвей или ребер, которые нужно пройти от корня к вершине x.

№ 75
Длина пути дерева - это:
• сумма длин путей всех его узлов.

№ 76
Бинарное дерево - это:
• дерево второй степени.

№ 77
Дано двоичное дерево.
Двоичное дерево
В какой последовательности выполняется обход вершин в случае: обхода сверху вниз;
обхода слева направо;
обхода снизу вверх.
В ответе последовательность вершин для каждого обхода соответственно.
• (PMQLK, QMLPK, QLMKP)

№ 78
Обход сверху вниз. Вид записи:
• префиксная.

№ 79
Обход слева направо.
• инфиксная.

№ 80
Обход дерева снизу вверх:
• постфиксная.

№ 81
Последовательный поиск в массиве:
• работает как для упорядоченных так и для неупорядоченных массивов.

№ 82
Двоичный поиск в массиве:
• работает для упорядоченных массивов.

№ 83
Из N элементов организуется двоичное дерево. Его высота:
• log2N.

№ 84
Практическое использование сильно ветвящихся деревьев:
• формирование и использование крупномасштабных деревьев поиска.

№ 85
Страница в сильно ветвящемся дереве это:
• поддерево.

№ 86
Б-дерево - это:
• совокупность страниц, сформированных особым образом.

№ 87
Неверное свойство Б-деревьев:
• листья могут располагаться на различных уровнях.

№ 88
Б-дерево растет:
• от листьев к корню.

№ 90
Дано дерево:
Дерево
Сколько в дереве листьев?
• (7)

№ 91
- Сколько в дереве внутренних узлов?
• (5)

№ 92
- Длина путь до вершины M?
• (4)

№ 93
- Какова длина дерева?
• (31)

№ 94
- Разложить на вложенные скобки:
• [(A(B(C),E(K(F,M),L)),D(G(H,I,N))))]

№ 95
Даны два дерева:
Два разных дерева
• они разные.

№ 96
Идеально-сбалансированное дерево это:
• все узлы расположены поровну слева и справа от каждого узла.

№ 99
Основное преимущество матрицы смежности:
• за один шаг можно ответить на вопрос существует ли ребро из x в y.

№ 100
Сколько ячеек памяти необходимо для представления графа с помощью списков инциденции (n - количество вершин, m - количество ребер):
• 2 x n x m.

№ 101
Рассмотрим следующий метод. Начинаем поиск с некоторой фиксированной вершины v0. Затем выбираем произвольную вершину u, смежную с v0 и повторяем наш просмотр от u. В общем случае предположим, что мы находимся в некоторой вершине v. Если существует новая (еще не просмотренная) вершина u, u-v, то мы рассматриваем эту вершину. (она перестает быть новой) начиная с нее, продолжаем поиск. Если же не существует новой вершины, смежной с v, мы говорим, что вершина v использована, возвращаемся в вершину, из которой попали в v и продолжаем поиск (если v=v0, то поиск закончен). Этот метод называется:
• поиск в ширину в графе.

№ 102
Произвольный путь, проходящий через каждое ребро графа ровно один раз, называется:
• Эйлеровым путем.

№ 103
Условие существования гамильтонова пути:
• граф должен быть связан и должен содержать не более чем две вершины нечетной степени.

№ 104
Путь, проходящий ровно один раз через каждую вершину:
• гамильтонов путь.

№ 105
В процессе вычисления расстояния от одной вершины a до другой вершины b в графе мы находим:
• расстояние от a до всех вершин графа.

№ 106
Алгоритм Дейкстры справедлив для графов, у которых:
• веса всех дуг неотрицательны.

№ 107
Критический путь в графе называется:
• максимальный по длине путь из a в b.

№ 108
Какой метод используется при отыскании фундаментального множества циклов:
• метод поиска в глубину.

№ 109
Гамильтонов путь?
• обход графа с проходом по всем узлам графа по одному разу.

№ 110
Алгоритмы с возвратом используются:
• при построении гамильтонова пути графа.

№ 111
С помощью какого из алгоритмов можно найти минимальный путь от исходной вершины X до произвольной вершины Y связанного графа:
• поиск в ширину.

№ 112
Вычислительная сложность алгоритма построения стягивающего дерева, использующего метод поиска в ширину:
• O(n+m).

№ 113
Вычислительная сложность общего алгоритма поиска кратчайшего пути от фиксированной вершины:
• O(n*m).

№ 114
Вычислительная сложность алгоритма Дейкстры нахождения кратчайшего пути:
• O (m log n).


на главную база по специальностям база по дисциплинам статьи