Quiz
ICS2210
This quiz has question types that open in the usual player.
Questions in this quiz (20)
1RBT are always balanced
- ATrue
- BFalse
2Which of the following are typically stored in a RBT node?
- AA pointer to the left child, right child and the colour of the node.
- BWhether the node is a Nil node, a pointer to the parent, left child, right child and the colour of the node.
- CA pointer to the parent, left child, right child and the colour of the node.
- DThe height of the tree, a pointer to the left child, right child and the colour of the node.
3Which of these is true about RBT paths?
- ARBT longest path is 2log(n+1)
- BRBT shortest path is 2log(n+1)
- CThe number of black nodes can vary between paths
- DThe number of black nodes is the same in different paths
- EThe number of red nodes can vary between paths
- FThe number of red nodes is the same in different paths
- GThe shortest path is equal to the number of red nodes
- HThe shortest path is equal to the number of black nodes
4When does an RBT insertion NOT require any fix up?
- AParent is black
- BParent is red
- CAll of the above
- DNone of the above
5Which is the correct procedure to fix the violation in the image?
- APerform a right rotation between the parent and grandparent and then colour swap the parent and grandparent.
- BPerform a left rotation between the parent and grandparent and then colour swap the parent and grandparent
- CPerform a left-right rotation between the child and grandparent and then colour swap the child and grandparent
- DPerform a right-left rotation between the child and grandparent and then colour swap the child and grandparent
6Which is the correct procedure to fix the violation in the image?
- APerform a right rotation between the parent and grandparent and then colour swap the parent and grandparent
- BPerform a left rotation between the parent and grandparent and then colour swap the parent and grandparent
- CPerform a left-right rotation between the child and grandparent and then colour swap the child and grandparent
- DPerform a right-left rotation between the child and grandparent and then colour swap the child and grandparent
7Which is the correct procedure to fix the violation in the image?
- APerform a right rotation between the parent and grandparent and then colour swap the parent and grandparent
- BPerform a left rotation between the parent and grandparent and then colour swap the parent and grandparent
- CPerform a left-right rotation between the child and grandparent and then colour swap the child and grandparent
- DPerform a right-left rotation between the child and grandparent and then colour swap the child and grandparent
8Which is the correct procedure to fix the violation in the image?
- APerform a right rotation between the parent and grandparent and then colour swap the parent and grandparent
- BPerform a left rotation between the parent and grandparent and then colour swap the parent and grandparent
- CPerform a left-right rotation between the child and grandparent and then colour swap the child and grandparent
- DPerform a right-left rotation between the child and grandparent and then colour swap the child and grandparent
9If the parent and uncle are red no rotations are required when inserting.
- ATrue
- BFalse
10Which of the following is true?
- AInsertion and deletion can both be implemented using an iterative top-down approach
- BOnly insertion can be implemented using an iterative top-down approach
- COnly deletion can be implemented using an iterative top-down approach
- DNeither insertion nor deletion can be implemented using an iterative top-down approach
11Deleting a red leaf node does not require an fix-ups.
- ATrue
- BFalse
12What is the difference between a substring and a subsequence?
- ASubstrings are in-order but subsequences are not
- BSubstrings are contiguous but subsequences are not
- CSubsequences are in-order but substrings are not
- DSubsequences are contiguous but substrings are not
13Which of these are examples of substrings of the word "hello"?
- Ahelo
- Bell
- Clo
- Dhll
- Eeo
- Fll
- Ghell
14Which of these are examples of subsequences of the word "hello"?
- Ahlo
- Bole
- Celo
- Dheo
- Eeoll
- Fhoe
15c[i,j] {
if i=0 or j=0:
return [blank_start]0[blank_end]
if x[i] == y[j]:
return [blank_start]c(i-1, j-1)+1[blank_end]
else:
return [blank_start]max(c(i-1, j), c(i, j-1))[blank_end]- Amax(c(i-1, j), c(i, j-1))
- Bc(i-1, j-1)+1
- C0
16Which of these is true about the LCS problem?
- AThe LCS problem satisfies the optimal substructure property.
- BThe LCS problem can be solved incrementally.
- CAll of the above.
- DNone of the above.
17Which of these is correct about the recursion tree of the LCS algorithm?
- AThe height is n+m with 2^(n+m) nodes
- BThe height is 2^(n+m) with n+m nodes
- CThe height is n+m with log(n+m) nodes
- DThe height is log(n+m) with n+m nodes
18The LCS can be optimised.
- ATrue
- BFalse
19Which of these is an advantage of skip lists over self-balancing trees?
- ASkip lists are faster
- BSkip lists take less space
- CSkip lists are easier to implement
- DSkip lists have no advantage over self-balancing trees
20When searching in a skip list we start from the bottom and move up.
- ATrue
- BFalse
Information
- Description
- Information Technology Quiz on ICS2210, created by 🐈 💕 on 01/06/2024.
- Author
- 🐈 💕
- Language
- English
- Views
- 13
- Tags
- Rating
- No ratings yet Rate this quiz