Quiz
Data Structures 1 - Review 2
Crie uma conta grátis para terminar este quiz
Salve seu progresso e veja sua nota final.
Já tem uma conta? Inicie sessão
Perguntas do quiz (27)
1Binary search trees are efficient because they guarantee Θ(logn) access time.
- AVerdadeiro
- BFalso
2Every subtree of an AVL tree is also a Binary Search tree.
- AVerdadeiro
- BFalso
3Suppose that X is a B-tree leaf containing 41 entries (keys) and having at least one sibling. Which statement is true?
- AAny sibling of X is also a leaf.
- BAny sibling of X contains at least 41 entries.
- CThe parent of X has exactly 42 entries.
- DX has at least 41 siblings.
4Suppose that a B-tree has MAXIMUM branching of 11 and that a node already contains the keys/values 1 through 10. If a new value, 11, is added to this node, the node will split into two nodes. What values will be in these two nodes?
- AThe first node will have 1 through 5 and the second node will have 6 through 11.
- BThe first node will have 1 through 10 and the second node will have only 11.
- CThe first node will have 1 through 5 and the second node will have 7 through 11.
- DThe first node will have 1 through 6 and the second node will have 7 through 11.
- EThe first node will have only 1 and the second node will have the rest of the numbers.
5Which statement is true for a B-tree?
- AAll keys/entries of a node are greater than or equal to the keys/entries in the node's children.
- BAll leaves are at the exact same depth.
- CAll nodes contain the exact same number of keys/entrees.
- DAll non-leaf nodes have the exact same number of children.
6In an AVL tree, a DOUBLE left rotation is done on a node when:
- AThe balance value of the node is 2 and the right child's balance value is -1
- BThe balance value of the node is 1 and the right child's balance value is -2
- CThe balance value of the node is 1 and the right child's balance value is 2
- DThe balance value of the node is 2 and the right child's balance value is 0 or 1
- EThe balance value of the node is -2 and the left child's balance value is 0 or -1
- FThe balance value of the node is -2 and the left child's balance value is 1
7The depth of a node in a tree is equal to the number of its ancestors.
- AVerdadeiro
- BFalso
8In a B-tree of order 8, the ROOT node must always have at least 4 subtrees.
- AVerdadeiro
- BFalso
9In a height balanced binary search tree (AVL), when do you make an adjustment in the tree?
- AWhen the height difference between two sides of a node is greater than or equal to one
- BWhen the height difference between two sides of a node is greater than or equal to two
- CWhen the balance value of a node is equal to -1
- DWhen the height difference between two sides of a node is greater than or equal to zero
10Suppose that a non-leaf node in a B-tree has 41 entries (keys). How many children will this node have?
- A41
- B82
- C42
- D2
- E40
11All the leaves of a B-tree are at the same level.
- AVerdadeiro
- BFalso
12If both the left and right subtrees of a binary tree T meet the definition of an AVL tree, then T must be also meet the definition of an AVL tree.
- AVerdadeiro
- BFalso
13AVL trees are efficient because they provide Θ(n) access/search time and insert time.
- AVerdadeiro
- BFalso
14In an AVL tree, a DOUBLE right rotation is done on a node when:
- AThe balance value of the node is -2 and the left child's balance value is 0 or -1
- BThe balance value of the node is 1 and the right child's balance value is -2
- CThe balance value of the node is 2 and the right child's balance value is 0 or 1
- DThe balance value of the node is -2 and the left child's balance value is 1
- EThe balance value of the node is 1 and the right child's balance value is 2
- FThe balance value of the node is 2 and the right child's balance value is -1
15In an AVL tree, a SINGLE right rotation is done on a node when:
- AThe balance value of the node is 2 and the right child's balance value is 0 or 1
- Bhe balance value of the node is 1 and the right child's balance value is 2
- CThe balance value of the node is -2 and the left child's balance value is 0 or -1
- DThe balance value of the node is 2 and the right child's balance value is -1
- EThe balance value of the node is -2 and the left child's balance value is 1
- FThe balance value of the node is 1 and the right child's balance value is -2
16Every subtree of an AVL tree is another AVL tree.
- AVerdadeiro
- BFalso
17The O( ) complexity for insert into an AVL (balanced) binary search tree is (select the best answer):
- AO(1) - constant time
- BO(N log N) - linearithmetic time
- CO(N) - linear time
- DO(log N) - logrithmic time
18Data elements added to a Binary Search tree will always be added as a leaf node.
- AVerdadeiro
- BFalso
19The balance value of an AVL node is calculated by finding the MAX height of the two children and adding 1.
- AVerdadeiro
- BFalso
20If the depth of x is greater than the depth of y in a tree, then x is a descendant of y.
- AVerdadeiro
- BFalso
21In an AVL tree, a SINGLE left rotation is done on a node when:
- AThe balance value of the node is -2 and the left child's balance value is 1
- BThe balance value of the node is 2 and the right child's balance value is -1
- CThe balance value of the node is 1 and the right child's balance value is -2
- DThe balance value of the node is -2 and the left child's balance value is 0 or -1
- EThe balance value of the node is 1 and the right child's balance value is 2
- FThe balance value of the node is 2 and the right child's balance value is 0 or 1
22For both binary search trees and AVL trees (when using ascending order), the data values of all children of a node must be less than the data value of the node.
- AVerdadeiro
- BFalso
23Every subtree of a "binary search tree" is also a "binary search tree".
- AVerdadeiro
- BFalso
24A breadth first traversal of a tree or a graph is commonly implemented with a(n):
- Abinary search tree
- Bstack
- Cqueue
- Dheap
25In an AVL tree, when the height of both children of a node are the same, this indicates that the balance factor of this node is:
- A0
- B2
- C-1
- D1
26Every subtree of an Binary Search tree is also an AVL tree.
- AVerdadeiro
- BFalso
27The O( ) worst case complexity for insert into a binary search tree is (select the best answer):
- AO(log N) - logrithmic time
- BO(N log N) - linearithmetic time
- CO(1) - constant time
- DO(N) - linear time
Informações
- Descrição
- Quiz sobre Data Structures 1 - Review 2, criado por jshin13 em 10-03-2015.
- Autor
- jshin13
- Idioma
- English
- Visualizações
- 14
- Histórico
- Criado em 10 mar 2015 · atualizado em 19 fev 2016
- Avaliação
- Ainda sem avaliações Avalie este quiz