Quiz
Data Structures 1 - Review 2
Create a free account to finish this quiz
Save your progress and see your final score.
Already have an account? Sign in
Questions in this quiz (27)
1Binary search trees are efficient because they guarantee Θ(logn) access time.
- ATrue
- BFalse
2Every subtree of an AVL tree is also a Binary Search tree.
- ATrue
- BFalse
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.
- ATrue
- BFalse
8In a B-tree of order 8, the ROOT node must always have at least 4 subtrees.
- ATrue
- BFalse
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.
- ATrue
- BFalse
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.
- ATrue
- BFalse
13AVL trees are efficient because they provide Θ(n) access/search time and insert time.
- ATrue
- BFalse
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.
- ATrue
- BFalse
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.
- ATrue
- BFalse
19The balance value of an AVL node is calculated by finding the MAX height of the two children and adding 1.
- ATrue
- BFalse
20If the depth of x is greater than the depth of y in a tree, then x is a descendant of y.
- ATrue
- BFalse
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.
- ATrue
- BFalse
23Every subtree of a "binary search tree" is also a "binary search tree".
- ATrue
- BFalse
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.
- ATrue
- BFalse
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
Information
- Description
- Quiz on Data Structures 1 - Review 2, created by jshin13 on 10/03/2015.
- Author
- jshin13
- Language
- English
- Views
- 14
- History
- Created on 10 Mar 2015 · updated on 19 Feb 2016
- Rating
- No ratings yet Rate this quiz