Доклад за структурата на данните (1)
1. Въпроси с множествен избор (2 точки на въпрос, общо 20 точки)
1. Общите характеристики на стековете и опашките са ( ).
О. Да се позволява вмъкване и изтриване на елементи само в крайната точка
Б. Всички първи влязоха, последни излязоха
В. Всичко е първи влязъл, първи излязъл
Г. Няма обща основа
2. Опашката, съхранявана по свързан начин, се вмъква при изпълнение на операцията за вмъкване ( ).
А. Само указателят на главата е модифициран Б. Указателите на глава и опашка трябва да бъдат модифицирани
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. Дърветата са най-подходящи за представяне на ( ).
А. Подредени елементи от данни Б. Неподредени елементи от данни
C. Данни с разклонени йерархични връзки между елементите D. Данни без връзка между елементите
6. Максималният брой възли в k-тия слой на двоичното дърво е ( ).
A.2k-1 B.2K+1 C.2K-1 D. 2k-1
7. Ако има подредена таблица от 18 елемента, съхранена в едномерен масив A[19], първият елемент се поставя в A[1], и след това се извършва двоично търсене, тогава индексът на сравнителната последователност за намиране на A[3] е ( )
А. 1,2,3 Б. 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-бар, в съответната таблица на съседствата има съответно _______ и ________ ребра възли.
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) Линейните таблици се реализират с верижно съхранение за улесняване на операциите по вмъкване и изтриване
(г) Линейните таблици се реализират с последователно съхранение за улесняване на операциите по вмъкване и изтриване
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->next; свободен(q);
(B) q=p->следващ; q->data=p->data; p->next=Q->next; свободен(q);
(C) q=p->следващ; p->next=Q->next; свободен(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. Да предположим, че има n върха e ребра в ненасочения граф G, тогава броят на заглавните възли и таблиците в съответната таблица е ( ).
(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) Merge сортиране (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. Ако има n върха e в посоката граф G с насочени ребра, и сумата от всички върхове, въвеждащи степени, е 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 възел *lchild; struct node *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 ч.
|
