Статья по структуре данных (1)
1. Вопросы с выбором ответа (2 балла за вопрос, всего 20 баллов)
1. Общие характеристики стеков и очередей — ( ).
A. Разрешать вставку и удаление элементов только в конечной точке
B. Все первые, кто ушёл
C. Всё — первый пришёл — первый вышел
D. Нет общего языка
2. Очередь, хранящаяся связанным образом, вставляется при выполнении операции вставки ( ).
A. Модифицирован только указатель головы B. Указатели на голове и хвосте должны быть модифицированы
C. Модифицировать только указатель хвоста D. Указатели головы и хвоста могут потребовать модификации
3. Какая из следующих структур данных является нелинейной? ( )
A. Очередь B. Стек C. Линейная таблица D. Двоичное дерево
4. Если существует двумерный массив A[m][n], при условии, что A[0][0] хранится в 644 (10), а A[2][2] — в 676 (10), то каждый элемент занимает пространство, где хранится A[3][3][3](10)? Сноска (10) указывает, что он выражается в десятичной форме.
A.688 B.678 C.692 D.696
5. Деревья лучше всего использовать для представления ( ).
A. Упорядоченные элементы данных B. Неупорядоченные элементы данных
C. Данные с ветвляющимися иерархическими отношениями между элементами D. Данные без связи между элементами
6. Максимальное количество узлов на k-м слое бинарного дерева равно ( ).
A.2k-1 B.2K+1 C.2K-1 D. 2k-1
7. Если существует упорядочённая таблица из 18 элементов, хранящаяся в одномерном массиве A[19], первый элемент помещается в A[1], и теперь выполняется двоичный поиск, то индекс последовательности сравнения для поиска A[3] равен ( )
A. 1,2,3 B. 9,5,2,3
C. 9,5,3 D. 9,4,2,3
8. Быстро отсортируйте файлы из n записей, и вспомогательное пространство будет примерно таким же
A. O(1) B. O(n) C. O(1og2n) D. O(n2)
9. Для линейных таблиц (7, 34, 55, 25, 64, 46, 20, 10) для хеш-хранилища, если H(K)=K %9 выбран в качестве хеш-функции, существуют элементы ( ) с хеш-адресом равным 1.
A.1 B.2 C.3 D.4
10. Неориентированный граф с 6 узлами, и граф должен иметь не менее ( ) рёбер для обеспечения связного графа.
A.5 B.6 C.7 D.8
2. Заполнить пробелы (1 очко за каждую стрельбу, всего 26 очков)
1. Качество алгоритма обычно оценивается по четырём аспектам: _________, _________, _________ и _________.
2. Временная сложность алгоритма равна (n3+n2log2n+14n)/n2, а его порядок величины выражается как ________.
3. Если предположить, что обобщённая таблица дерева представлена как A(C,D(E,F,G),H(I,J)), то количество узлов, содержащихся в дереве, равно __________, глубина дерева — ___________, а степень дерева — _________.
4. Значение суффикса формулы 9 2 3 +- 10 2 / - равно __________. Формула суффикса, соответствующая средней формуле (3+4X)-2Y/3, равна _______________________________.
5. Если двоичное дерево хранится с связанным списком, у каждого узла есть два указателя на левого ребёнка и правого ребёнка в дополнение к полю данных. В этой структуре хранения бинарное дерево с n узлами содержит всего ________ полей указателей, из которых ________ указателей хранят адреса, а ________________ указатели — пустые.
6. Для ориентированного графа и неориентированного графа с n вершинами и рёбрами E-bar в соответствующей таблице смежности имеются соответственно _______ и ________ узлы рёбер.
7. Сеть AOV — это граф ___________________.
8. В неориентированном полном графе с n вершинами существует ________ рёбер, а в ориентированном полном графе с n вершинами — ________ рёбер.
9. При условии, что линейная таблица равна (12,23,74,55,63,40), если элементы одного и того же остатка становятся подтаблицей согласно условию Key % 4, получаемые четыре подтаблицы — это ____________________________, ___________________, _______________________ и __________________________.
10. В процессе вставки элементов в B_ дерево, если корневой узел дерева окончательно разделён, высота нового дерева ___________ выше исходного дерева.
11. В процессе сортировки кучи временная сложность просеивания любого узла ветви равна ________, а сложность всего процесса сортировки кучи — ________.
12. В быстрой сортировке, куче и слиянии сортировка _________ стабильна.
Статья по структуре данных (2)
1. Вопросы с выбором ответа (24 балла)
1. Следующее описание линейных таблиц неверно ().
(A) Линейные таблицы хранятся последовательно и должны занимать смежный участок пространства
(B) Линейные таблицы являются цепочками и не занимают непрерывное пространство для хранения
(C) Линейные таблицы реализованы с помощью цепного хранения для облегчения операций вставки и удаления
(d) Линейные таблицы реализованы с последовательным хранением для облегчения операций вставки и удаления
2. Предположим, что общее количество листовых узлов в дереве Хаффмана равно m, и если в качестве структуры хранения используется бинарный связанный список, то в дереве Хаффмана существует всего ( ) пустых полей указателей.
(A) 2м-1 (B)2м (C)2м+1 (D)4м
3. Если указатели на голову и хвост последовательной очереди петли Q[0:M-1] равны F и R соответственно, указатель головы F всегда указывает на предыдущее положение головного элемента, а указатель хвоста R всегда указывает на текущее положение хвостового элемента, то количество элементов в очереди петли равно ( ).
(A) R-F (B) F-R (C) (R-F+M)%M (D) (F-R+M)%M
4. Если последовательность обхода среднего порядка бинарного дерева равна ABCD, а предыдущая последовательность обхождения последовательности — CABD, то последовательность, полученная при обходе бинарного дерева в следующем порядке, равна ().
(A) BADC (B)BCDA (C) CDAB (D) CBDA
5. Пусть в полностью неориентированном графе есть n вершин, тогда в полностью неориентированном графе есть ( ) рёбра.
(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1
6. Предположим, что в бинарном дереве 2000 узлов, тогда минимальная высота бинарного дерева равна ( ).
(A) 9 (B) 10 (C) 11 (D) 12
7. Предположим, что в ориентированном графе есть n вершин, тогда в таблице смежности, соответствующих ориентированному графу, есть ( ) заголовочные узлы.
(A) n-1 (B) n (C) n+1 (D) 2n-1
8. Установите набор начальных последовательностей ключевых слов (5, 2, 6, 3, 8), и результат быстрой сортировки по первому ключевому слову 5 будет ( ).
(A) 2,3,5,8,6 (B) 3,2,5,8,6
(C) 3,2,5,6,8 (D) 2,3,6,5,8
2. Заполните пробелы (24 балла)
1. Для эффективного применения технологии поиска HASH необходимо решить две задачи — это ____________________ и __________________________.
2. Функция следующего сегмента программы реализует данные x в стек и требует заполнения правильного оператора в подчёркивании.
typedefstruct {int s[100]; int top; } sqstack;
void push(sqstack&stack,int x)
{
if (stack.top==m-1) printf("переполнение");
иначе {____________________; _________________; }
}
3. Последовательность, полученная при прохождении двоичного дерева сортировки в среднем порядке, является ___________ последовательностью (заполненной в упорядочённом или неупорядочённом).
4. Самая худшая по времени при быстрой сортировке — ___________, а средняя сложность — __________.
5. Если количество узлов со степенью 0 в бинарном дереве равно N0, а номер узла со степенью 1 — N1, то количество узлов с степенью 2 в бинарном дереве равно _________; Если в качестве структуры хранения бинарного дерева используется бинарный связанный список, в бинарном дереве остаётся _______ пустых указательных полей.
6. Пусть количество вершин и рёбер в определённом неориентированном графе равно n и e соответственно, а сумма степеней всех вершин — d, тогда e = _______.
7. Если начальная последовательность ключевых слов записи — (55, 63, 44, 38, 75, 80, 31, 56), то начальная куча, установленная методом скрининга, — это ___________________________.
8. Известно, что структура хранения в таблице смежности ориентированного графа выглядит следующим образом: Из вершины 1 выходная последовательность обхода DFS выглядит следующим образом:
, выходная последовательность обхода BFS равна
Статья по структуре данных (3)
1. Вопросы с выбором ответа (1 балл за вопрос, всего 20 баллов)
1. Если двоичная форма структуры данных выражена как A=(D,R),D={01,02,03,04,05,06,07,08,09}, R={r},r={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03,07>,<03,08>,<03,09>}, то структура данных A равна ( ).
(A) Линейная структура (B) Древесная структура (C) Физическая структура (D) Графическая структура
2. Временной комплекс следующей программы равен ()
for(i=1,s=0; i<=n; i++) {t=1;for(j=1;j<=i; j++) t=t*j; s=s+t; }
(A) O(n) (B) O(n2) (C) O(n3) (D) O(n4)
3. Установите переменную указателя p так, чтобы она указывала на узел A в одном связанном списке; если вы удалите узел A из одного связанного списка, необходимо изменить последовательность операций указателя на ().
(A) q=p->следующий; p->data=Q->data; p->next=q->next; free(q);
(B) q=p->следующий; q->data=p->data; p->next=q->next; free(q);
(C) q=p->следующий; p->next=q->next; free(q);
(D) q=p->следующий; p->data=Q->data; free(q);
4. Если для сортировки требуется n ключевых слов записи, ( ) в сортировке кучи требуются вспомогательные единицы записи.
(A) 1 (B) n (C) nlog2n (D) n2
5. Если начальные ключевые слова для записи ключевых слов — (20, 15, 14, 18, 21, 36, 40, 10), то результат после быстрой сортировки, зафиксированной с 20 в качестве бенчмарка, будет ( ).
(A) 10,15,14,18,20,36,40,21
(B) 10, 15, 14, 18, 20, 40, 36, 21
(C) 10, 15, 14, 20, 18, 40, 36, 2 л
(D) 15,10,14,18,20,36,40,21
6. Предположим, что в бинарном дереве сортировки есть n узлов, тогда средняя длина поиска в бинарном дереве сортировки равна ( ).
(A) O(1) (B) O(log2n) (C) (D) O(n2)
7. Пусть в неориентированном графе G есть n рёбер вершин e, то количество заголовочных узлов и узлов таблицы в соответствующей таблице смежности равно ( ).
(A) n,e (B) e,n (C) 2n,e (D) n,2e
8. Предположим, что в графе сильных связностей есть n вершин, тогда в графе сильных связностей есть как минимум ( ) рёбра.
(A) n(n-1) (B) n+1 (C) n (D) n(n+1)
9. Существует 5000 ключевых слов записей, которые нужно отсортировать, если вам нужно использовать самый быстрый способ для выбора самых маленьких 10 ключевых слов записей, вы можете использовать следующий метод ( ) для достижения этой цели.
(A) Быстрая сортировка (B) Сортировка кучи (C) Объединение сортировки (D) Вставить сортировку
10. Следующие четыре вида ( ) обладают наибольшей пространственной сложностью.
(A) Сортировка по вставке (B) Сортировка пузырьков (C) Сортировка по куче (D) Сортировка по слиянию
2. Заполните пробелы (1 очко за каждую стрельбу, всего 20 очков)
1. Физическая структура данных в основном включает две ситуации: _____________ и ______________.
2. Если в полном бинарном дереве 500 узлов, глубина бинарного дерева равна __________; Если использовать бинарный связанный список в качестве структуры хранения для полностью бинарного дерева, ___________ пустых полей указателей.
3. Если входная последовательность равна 1, 2, 3, то ___________ различных выходных последовательностей можно получить после действия стека.
4. Если матрица смежности A[n][n] используется в качестве структуры хранения графа G, то сумма всех элементов строки i в матрице смежности равна ________ вершины i, а сумма всех элементов столбца i равна ________ вершины i.
5. Если в дереве Хаффмана есть n узлов, то в дереве Хаффмана есть ________ узлов со степенью 1.
6. Если в направлении графа G есть n вершин e с направленными рёбрами, и сумма всех вершин, вводящих степени, равна d, то связь между e и d равна _________.
7. __________ прохождение узлов в дереве бинарной сортировки позволяет получить дополнительную последовательность ключевых слов (заполненных, средних или апостериорных).
8. Если в таблице поиска 100 элементов, если вы используете метод дихотомического поиска для поиска элемента данных X, нужно сравнивать его до ________ раз, чтобы определить, есть ли элемент данных X в таблице поиска.
9. Будь то стек с последовательной структурой хранения или стек с цепочной структурой хранилища, временная сложность операций внутри стека и наружу ____________.
10. Полное двоичное дерево с n узлами, если пронумеровать сверху вниз и слева направо, начиная с 1, родительский узел i-го узла нумеруется ____________, а номер правого дочернего узла — ___________.
11. Если начальный набор записанных ключевых слов равен (72, 73, 71, 23, 94, 16, 5), то результат быстрой сортировки по ключевому слову записи 72 — ___________________________.
12. Если в направленном графе G E={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>} существует множество направленных рёбер, то топологическая последовательность графа равна ____________________.
13. Следующий алгоритм реализует ключевое слово с значением x в последовательном хэш-списке, пожалуйста, заполните правильное утверждение в подчёркивании.
struct record{int key; в других; };
inthashsqsearch(struct record hashtable[ ],int k)
{
inti,j; j=i=k % p;
в то время как (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; если (i==j) return(-1); }
если (_______________________ ) return(j); в противном случае возврат(-1);
}
14. Следующий алгоритм реализует ключевое значение k в бинарном дереве сортировки, пожалуйста, заполните правильное утверждение в подчёркивании.
typedefstruct node{int key; struct node *lchild; struct узел *rchild; }bitree;
bitree *bstsearch(bitree *t, int k)
{
если (t==0 ) return(0); в противном случае пока (t!=0)
если (t->ключ==k)_____________; иначе если (t->ключ>k) t=t->lchild; else_____________;
}
Тестовая работа по структуре данных (1) См. ответ
1. Вопросы с выбором ответа (2 балла за вопрос, всего 20 баллов)
1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A
2. Заполнить пробелы (1 очко за каждую стрельбу, всего 26 очков)
1. Правильность, читаемость, прочность и высокая эффективность
2.O(n)
3.9 3 3
4.-1 3 4 X * + 2 Y * 3 / -
5.2n n-1 n+1
6.e 2e
7. Направленные и нецепные
8.n(n-1)/2 n(n-1)
9.（12，40） （ ） （74） （23,55，63）
10. Добавить 1
11.O(log2n) O(nlog2n)
12. Консолидация
Ответы на другие вопросы теста можно увидеть:
Туристы, если вы хотите увидеть скрытое содержание этого поста, пожалуйста Ответ
|
Опубликовано 25.11.2014 12:46:30
|
|
|
Опубликовано 30.12.2014 0:10:55