Font size
Worksheetsdata structures lab model exam
Total questions: 60
Worksheet time: 3600secs
What is an AVL tree?
a tree which is balanced and is a height balanced tree
a tree which is unbalanced and is a height balanced tree
a tree with three children
a tree with atmost 3 children
Why we need to a binary tree which is height balanced?
to avoid formation of skew trees
to save memory
to attain faster memory access
to simplify storing
What is the maximum height of an AVL tree with p nodes?
p
log(p)
log(p)/2
p/2
Given an empty AVL tree, how would you construct AVL tree when a set of numbers are given without performing any rotations?
just build the tree with the given input
find the median of the set of elements given, make it as root and construct the tree
use trial and error
use dynamic programming to build the tree
Why to prefer red-black trees over AVL trees?
Because red-black is more rigidly balanced
AVL tree store balance factor in every node which costs space
AVL tree fails at scale
Red black is more efficient
When performing trinode restructuring in an AVL tree, which node should be labeled "Z"?
the first node at which the height-balance property is violated
the first node that would be visited in an inorder traversal
the child of the node where the height-balance property is violated
the traller grandchild of the node at which the height-balance property is violated
The goal of trinode restructuring is to ___.
balance the subtree
move "a" to be the root
move "c" to be the root
move "y" to be the root
What is the worst-case height of an AVL tree?
O(log n)
O(n)
O(n logn)
O(1)
A height balanced binary search tree is called__________
height tree
AVL tree
binary tree
binary search tree
The balancing factor for AVL tree =
hL-hR
hR-hL
hL-hL
hR-hR
The allowed values for height of an avl tree
0,1
2,0,-2
0,1,2
-1,0,1
For RL imbalance which rotation is need to balance the tree
Single LL rotation
Single RR rotation
LL and RR rotation
None
Possible Operations on AVL tree
insertion
deletion
traversal
all the above
Which of the following is a double rotation
LL rotation
RR rotation
RL rotation
None
What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.
2
3
4
5
In an AVL tree the difference between heights of left and right sub trees cannot be more than
1
2
3
0
AVL tree got its name after its
Adelson-Velsky and Landis
Adam Velsky Lenin
Adelson Vel Landis
None
The sequence of insertion 10,12,14 will lead to imbalance by using which rotation can be used to balance the tree
RR rotation
LL rotation
LR rotation
RL rotation
The sequence of insertion 25,12,9 will lead to imbalance by using which rotation can be used to balance the tree
RR rotation
LL rotation
RL rotation
LR rotation
After an insertion or deletion operation in an AVL tree the first node with an invalid balancing factor is called............
nodes
invalid node
node
critical node
What does a searching algorithm do?
Search through a set of data
Save a set of data
Help to organise data
What would be needed if searching algorithms didn't exist?
The data would need to be saved
Each item of data would need to be looked at one by one, until the searched for data was found
A new set of data to look at would be needed
Which of these is a type of searching algorithm?
Linear search
Word search
Search engine
What does a linear search do?
Looks at the first item of data, then each one in turn, until it finds the data item requested
Organises the data into alphabetical order
Splits the data until the requested data is found
What is an advantage of a linear search?
It is very quick
It only works with ordered lists
It is a simple algorithm
Which of the following is NOT an advantage of a serial search?
It can be used on any set of data regardless of type
It is the quickest search to use
It is a simple algorithm, so it is easy to write a computer program to carry it out
What does a binary search do?
a)Looks at the first item of data, then each one in turn, until it finds the data item requested
b)Converts all the data into binary
c)Takes the data and splits it in half repeatedly until it finds the data item requested
Which search algorithm would be best to use with ordered data?
A binary search
Either binary search or a linear search
A linear search
What is an advantage of a binary search
It's very quick
It only works with ordered lists
It is a simple algorithm
What is the biggest disadvantage of a binary search?
It is slow
It can only be used if the data is sorted into an order
It takes the data and keeps dividing it in half until it finds the item it is looking for
What does a sorting algorithm do?
Finds an item of data in a set of data
Saves a set of data
Puts a list of items into order
Which of the following is not a sorting algorithm?
Bubble Sort
Long Sort
Insertion Sort
What does a bubble sort do?
Sorts a list by comparing two items that are side by side, to see which is out of order
Separates a list of data into different collections of data, before sorting and gathering back into a list
Finds an item of data in a list
How many passes will a bubble sort go through?
Only one pass
Two passes
Several passe - until the data is fully ordered
Why does a bubble sort do a final pass even when the data is in the correct order?
To save the data
It does not recognise that the data is in order until the final pass requires no changes
It needs to do this to put the data back in to a list
Which of the following is an advantage of a bubble sort?
It is a very small and simple computer program
It takes a very long time to run
It is very quick
Which of the following is NOT an advantage of a bubble sort?
It is a very small and simple computer program
There is only one task to perform
It is very quick
What does an insertion sort do?
Separates a list of data into different collections of data which are sorted and gathered back into a list
Goes through a list of data a number of times and compares two items that are side by side to each other to see which is out of order
Goes through a list, comparing two items that are side by side, and continues to move one value until it is in the correct place.
Which of the following is an advantage of a insertion sort when compared with a bubble sort?
It is quicker than a bubble sort algorithm
It is simpler than a bubble sort algorithm
There is no advantage.
How many passes will an insertion sort go through?
Only one pass
Two passes
Several passes - until the data is fully ordered
Breadth First Search is equivalent to which of the traversal in the Binary Trees?
Pre-order Traversal
Post-order Traversal
Level-order Traversal
In-order Traversal
Time Complexity of Breadth First Search is? (V – number of vertices, E – number of edges)
O(V + E)
O(V)
O(E)
O(V*E)
The Data structure used in standard implementation of Breadth First Search is?
Stack
b) Queue
c) Linked List
d) Tree
The Breadth First Search traversal of a graph will result into?
Linked List
Tree
Graph with back edges
Arrays
A person wants to visit some places. He starts from a vertex and then wants to visit every place connected to this vertex and so on. What algorithm he should use?
Depth First Search
Breadth First Search
Trim’s algorithm
Kruskal’s algorithm
Which of the following is not an application of Breadth First Search?
Finding shortest path between two nodes
Finding bipartiteness of a graph
GPS navigation system
Path Finding
When the Breadth First Search of a graph is unique?
When the graph is a Binary Tree
When the graph is a Linked List
When the graph is a n-ary Tree
When the graph is a Ternary Tree
Regarding implementation of Breadth First Search using queues, what is the maximum distance between two nodes present in the queue? (considering each edge length 1)
Can be anything
0
At most 1
Insufficient Information
In BFS, how many times a node is visited?
Once
Twice
Equivalent to number of indegree of the node
Thrice
Depth First Search is equivalent to which of the traversal in the Binary Trees?
Pre-order Traversal
Post-order Traversal
Level-order Traversal
In-order Traversal
Time Complexity of DFS is? (V – number of vertices, E – number of edges)
O(V + E)
O(V)
O(E)
O(V*E)
The Data structure used in standard implementation of Breadth First Search is?
Stack
Queue
Linked List
Tree
The Depth First Search traversal of a graph will result into?
Linked List
Tree
Graph with back edges
Array
A person wants to visit some places. He starts from a vertex and then wants to visit every vertex till it finishes from one vertex, backtracks and then explore other vertex from same vertex. What algorithm he should use?
Depth First Search
Breadth First Search
Trim’s algorithm
Kruskal’s Algorithm
Which of the following is not an application of Depth First Search?
For generating topological sort of a graph
For generating Strongly Connected Components of a directed graph
Detecting cycles in the graph
Peer to Peer Networks
When the Depth First Search of a graph is unique?
When the graph is a Binary Tree
When the graph is a Linked List
When the graph is a n-ary Tree
When the graph is a n-ary Tree
Regarding implementation of Depth First Search using stacks, what is the maximum distance between two nodes present in the stack? (considering each edge length 1)
Can be anything
0
At most 1
Insufficient Information
In Depth First Search, how many times a node is visited?
Once
Twice
Equivalent to number of indegree of the node
Thrice
Traversal of a graph is different from tree because
There can be a loop in graph so we must maintain a visited flag for every vertex
DFS of a graph uses stack, but inorrder traversal of a tree is recursive
BFS of a graph uses queue, but a time efficient BFS of a tree is recursive.
All of the above
Which of the following algorithms can be used to most efficiently determine the presence of a cycle in a given graph ?
Depth First Search
Breadth First Search
Prim’s Minimum Spanning Tree Algorithm
Kruskal’ Minimum Spanning Tree Algorithm
