Стаття зі структури даних (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) 2m-1 (B)2m (C)2m+1 (D)4m
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)
{
якщо (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->наступний; вільний(q);
(B) q=p->наступний; q->data=p->data; p->next=Q->наступний; вільний(q);
(C) q=p->наступний; p->next=Q->наступний; вільний(q);
(D) q=p->далі; p->data=Q->data; вільний(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,2l
(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 node *rchild; }bitree;
bitree *bstsearch(bitree *t, int k)
{
якщо (t==0 ) return(0); інакше (t!=0)
якщо (t->key==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 00:10:55