Quiz
database final
This quiz has question types that open in the usual player.
Questions in this quiz (75)
1Given an array where numbers are in range from 1 to n6, which sorting algorithm can be used to sort these numbers in linear time?
- Ainsertion sort
- Bquick sort
- Cradix sort
- Dnot possible
2Which is the best sorting algorithm to use for the elements in array that is more than 1 million?
- Amerge sort
- Bbubble sort
- Cquick sort
- Dinsertion sort
3Consider a situation where swap operation is very costly, which of the following sorting algorithms should be preferred so that the number of swap operations are minimized?
- AHeap sort
- BSelection sort
- Cinsertion sort
- Dmerge sort
4Suppose we have an O(n) time algorithm that finds median of an unsorted array. Now consider a quicksort implementation where we first find median uing the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified quicksort?
- AO(n^2 log n)
- BO(n^2)
- CO(n log n log n)
- DO(n log n)
5What is the time complexity for insertitem in an AVL tree
- AO(1)
- BO(n)
- CO(log n)
- DO(n log n)
6Assume that a mergesort algorithm in the worst case takes 30 seconds for an input size of 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes?
- A256
- B512
- C1048
- D2048
7Splay trees are always balanced
- ATrue
- BFalse
8Worse case performance of a splay tree is O(n)
- ATrue
- BFalse
9Which of the following sorting algorithms in its typical implementation gives best performance when applied to an array which is sorted or almost sorted (max 1 or 2 elements misplaced)
- Aquick sort
- Bheap sort
- Cmerge sort
- Dinsertion sort
10Which kind of tree makes sure the height is balanced
- Abinary tree
- Bheap tree
- CAVL tree
- Dskip list
11In a splay tree if we have a node X and it is left children of parent P which is a left children of grandparent G, then what type of splaying operation needs to be done in order to get the X node to the root?
- AZig-zag
- BZag
- CZig-zig
- DZig
12Which of the following is not a stable sorting algorithm in its typical implementation
- AInsertion sort
- Bmerge sort
- Cquick sort
- Dbubble sort
13In a binary search tree, what is the time complexity of the following method?
- AO(n)
- BO(n log n)
- CO(h)
- DO(h + s)
14Which of the following is true about merge sort?
- Amerge sort works better than quick sort if data is accessed from slow sequential memory
- Bmerge sort is stable by nature
- Cmerge sort outperforms heap sort in most of the practical situations
- Dall of the above
15Which of the following is an advantage of adjacency list representation over adjacency matrix representation of a graph?
- AIn adjacency list representation, space is saved for sparse graphs
- BDFS and BFS can be done in O(V + E) time for adjacency list representation. These operations take O(V^2) time in adjacency matrix representation. Here is V and E number of vertices and edges respectively
- Cadding a vertex in adjacency list representation is easier than adjacency matrix representation
- Dall of the above
16The most efficient algorithm for finding the number of connected components in an undirected graph of n vertices and m edges has time complexity of:
- AO(n)
- BO(m)
- CO(mn)
- DO(m+n)
17Given an undirected graph of G with V vertices and E edges, the sum of the degree of all vertices is
- AE
- B2E
- CV
- D2V
18Consider a directed graph of n vertices and m edges such that all edges have same edge weights. Find the complexity of the best known algorithm to compute the minimum spanning tree of the graph
- AO(m+n)
- BO(m log n)
- CO(mn)
- DO(N log m)
19Give the visited node order for each type of graph search starting with s, given the following adjacency lists:
- ABFS: s c d b c a
DFS: s d b c e a - BBFS: s d b c e a
DFS: s d b c e a - CBFS: s a c d e b
DFS: s a c e b d - DBFS: s a e c d b
DFS: s a c b e d
- ABFS: s c d b c a
20Among the following sequences:
(I) a b e g h f
(II) a b f e h g
(III) a b f h g e
(IV) a f g h b e
Which are depth first traversals of the above graph?
- AI, II and IV only
- BI and IV only
- CII, III and IV only
- DI, III and IV only
21Match the problems with their best suited algorithms:
1. greedy method
2. divide and conquer
3. dynamic programming
[blank_start]3[blank_end] - matrix chain product
[blank_start]1[blank_end] - task scheduling
[blank_start]1[blank_end] - fractional knapsack
[blank_start]2[blank_end] - mergesort
[blank_start]3[blank_end] - 0-1 knapsack problem- A3
- B1
- C1
- D2
- E3
22Dijkstras algorithm solution
Vertex - cost - path
A | 0 |
B | [blank_start]1[blank_end] | [blank_start]AB[blank_end]
C | [blank_start]2[blank_end] | [blank_start]ABC[blank_end]
D | [blank_start]7[blank_end] | [blank_start]ABCED[blank_end]
E | [blank_start]5[blank_end] | [blank_start]ABCE[blank_end]
F | [blank_start]7[blank_end] | [blank_start]ABCEF[blank_end]
G| [blank_start]3[blank_end] | [blank_start]ABG[blank_end]
- A1
- BAB
- C2
- DABC
- E7
- FABCED
- G5
- HABCE
- I7
- JABCEF
- K3
- LABG
23review for kruskals algorithm
https://www.hackerearth.com/blog/algorithms/kruskals-minimum-spanning-tree-algorithm-example/- ATrue
- BFalse
24What is the worst case time complexity for search, insert and delete operations in a general Binary Search Tree?
- AO(n)
- BO(Log n)
- CO(Log n) for search and insert, and O(n) for delete
- DO(Log n) for search, and O(n) for insert and delete
25What are the worst case time complexities of searching in binary tree, BST and AVL tree respectively?
- AO(n)
- BO(Log n)
- CO(n) for binary tree, and O(Log n) for others
- DO(n) for binary tree and BST, and O(Log n) for AVL
26What are splay trees?
- Aself adjusting binary search trees
- Bself adjusting binary trees
- Ca tree with strings
- Da tree with probability distributions
27Why to prefer splay trees?
- Aeasier to program
- Bspace efficiency
- Ceasier to program and faster access to recently accessed items
- Dquick searching
28What is a splay operation?
- Amoving parent node to down of child
- Bmoving a node to root
- Cmoving root to leaf
- Dremoving leaf node
29What is the disadvantage of using splay trees?
- Aheight of a splay tree can be linear when accessing elements in non decreasing order.
- Bsplay operations are difficult
- Cno significant disadvantage
- Dsplay tree performs unnecessary splay when a node is only being read
30What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.
Assuming height as 3, minimum number of nodes required:
N(h) = N(h-1) + N(h-2) + 1
N(3) = N(2) + N(1) + 1 = 4 + 2 + 1 = 7.- A2
- B3
- C4
- D5
31What is the worst case possible height of AVL tree?
- A2*log n
- B1.44*log n
- CDepends upon implementation
- Dθ(n)
32Which of the following is TRUE?
- AThe cost of searching an AVL tree is θ(log n) but that of a binary search tree is O(n)
- BThe cost of searching an AVL tree is θ(log n) but that of a complete binary tree is θ(n log n)
- CThe cost of searching a binary search tree is O(log n ) but that of an AVL tree is θ(n)
- DThe cost of searching an AVL tree is θ(n log n) but that of a binary search tree is O(n)
33What is a skip list?
- Aa linkedlist with size value in nodes
- Ba linkedlist that allows faster search within an ordered sequence
- Ca linkedlist that allows slower search within an ordered sequence
- Da tree which is in the form of linked list
34Consider the 2-level skip list
- Atravel 20-30-35-38
- Btravel 20-30-40-38
- Ctravel 20-38
- Dtravel 20-40-38
35Skip lists are similar to which of the following datastructure?
- Astack
- Bheap
- Cbinary search tree
- Dbalanced binary search tree
36What is the time complexity improvement of skip lists from linked lists in insertion and deletion?
- AO(n) to O(logn) where n is number of elements
- BO(n) to O(1) where n is number of elements
- Cno change
- DO(n) to O(n2) where n is number of elements
37skip list insert
We will start from highest level in the list and compare key of next node of the current node with the key to be inserted. Basic idea is If –
- Key of next node is less than key to be inserted then we keep on moving forward on the same level
- Key of next node is greater than the key to be inserted then we store the pointer to current node i at update[i] and move one level down and continue our search.
At the level 0, we will definitely find a position to insert given key- ATrue
- BFalse
38skip list delete
Deletion of an element k is preceded by locating element in the Skip list using above mentioned search algorithm. Once the element is located, rearrangement of pointers is done to remove element form list just like we do in singly linked list. We start from lowest level and do rearrangement until element next to update[i] is not k.
After deletion of element there could be levels with no elements, so we will remove these levels as well by decrementing the level of Skip list- ATrue
- BFalse
39Insert, into an empty binary search tree, entries with keys 30, 40, 24, 58, 48, 26, 11, 13 (in this order).
Draw the tree after each insertion.
final tree:
- Ay
- Bn
40a multi-way search tree is an ordered tree such that
Each internal node has at least two children and stores d-1 key-element items
The leaves store no items and serve as placeholders- ATrue
- BFalse
41(2,4) Trees
At most 4 children
All external nodes have same depth
insert a new item (k, o) at the parent v of the leaf reached by searching for k
Split, transfer, and fusion each take O(1)
Search, insertion and deletion each take O(log n)- ATrue
- BFalse
42What is the special property of red-black trees and what root should always be?
- Aa color which is either red or black and root should always be black color only
- Bheight of the tree
- Cpointer to next node
- Da color which is either green or black
43Why do we impose restrictions like
. root property is black
. every leaf is black
. children of red node are black
. all leaves have same black- Ato get logarithm time complexity
- Bto get linear time complexity
- Cto get exponential time complexity
- Dto get constant time complexity
44What are the operations that could be performed in O(logn) time complexity by red-black tree?
- Ainsertion, deletion, finding predecessor, successor
- Bonly insertion
- Conly finding predecessor, successor
- Dfor sorting
45When it would be optimal to prefer Red-black trees over AVL trees?
- Awhen there are more insertions or deletions
- Bwhen more search is needed
- Cwhen tree must be balanced
- Dwhen log(nodes) time complexity is needed
46When to choose Red-Black tree, AVL tree and Binary-trees?
- Amany inserts, many searches and when managing more items respectively
- Bmany searches, when managing more items respectively and many inserts respectively
- Csorting, sorting and retrieval respectively
- Dretrieval, sorting and retrieval respectively
47The height of a node is the largest number of edges in a path from that node to a leaf node.
The depth of a node is the number of edges in the path from the root node to that node.- ATrue
- BFalse
48The height of a binary tree is the largest number of edges in a path from the root node to a leaf node. Essentially, it is the height of the root node.
- ATrue
- BFalse
49Like QuickSort, Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves.
- ATrue
- BFalse
50Which sorting algorithm will take least time when all elements of input array are identical? Consider typical implementations of sorting algorithms.
- AInsertion Sort
- BHeap Sort
- CMerge Sort
- DSelection Sort
51Which of the following sorting algorithms has the lowest worst-case complexity?
- AMerge Sort
- BBubble Sort
- CQuick Sort
- DSelection Sort
52Suppose we are sorting an array of eight integers using quicksort, and we have just finished the first partitioning with the array looking like this:
2 5 1 7 9 12 11 10
Which statement is correct?- AThe pivot could be either the 7 or the 9
- BThe pivot could be the 7, but it is not the 9
- CThe pivot is not the 7, but it could be the 9
- DNeither the 7 nor the 9 is the pivot.
53Which is the correct order of the following algorithms with respect to their time Complexity in the best case ?
- AMerge sort > Quick sort >Insertion sort > selection sort
- Binsertion sort < Quick sort < Merge sort < selection sort
- CMerge sort > selection sort > quick sort > insertion sort
- DMerge sort > Quick sort > selection sort > insertion sort
54Which of the following is not true about comparison based sorting algorithms?
- AThe minimum possible time complexity of a comparison based sorting algorithm is O(n Log n) for a random input array
- BAny comparison based sorting algorithm can be made stable by using position as a criteria when two elements are compared
- CCounting Sort is not a comparison based sorting algorithm
- DHeap Sort is not a comparison based sorting algorithm
55Which of the following sorting algorithms has the lowest worst-case complexity?
- AMerge Sort
- BBubble Sort
- CQuick Sort
- DSelection Sort
56Which one of the following in-place sorting algorithms needs the minimum number of swaps?
- AInsertion Sort
- BQuick Sort
- CHeap Sort
- DSelection Sort
57Divide and Conquer example
- Ay
- Bn
58The greedy method is a general algorithm design paradigm, built on the following elements:
configurations: different choices, collections, or values to find
objective function: a score assigned to configurations, which we want to either maximize or minimize- ATrue
- BFalse
59Fractional Knapsack problem:
greedy approach is to calculate the ratio value/weight for each item and sort the item on basis of this ratio. Then take the item with the highest ratio and add them until we can’t add the next item as a whole and at the end add the next item as much as we can- ATrue
- BFalse
60Task Scheduling Algorithm:
generate all subsets of given set of jobs and check individual subset for feasibility of jobs in that subset. Keep track of maximum profit among all feasible subsets. The time complexity of this solution is exponential.- ATrue
- BFalse
61Dynamic Programming
Decision is made as you progress through rather than make the decision at the start (greedy method)
mainly an optimization over plain recursion- ATrue
- BFalse
62A Graph is a non-linear data structure consisting of nodes and edges. The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph
- ATrue
- BFalse
63Depth First Search is equivalent to which of the traversal in the Binary Trees?
- APre-order Traversal
- BPost-order Traversal
- CLevel-order Traversal
- DIn-order Traversal
64Time Complexity of DFS is? (V – number of vertices, E – number of edges)
- AO(V + E)
- BO(V)
- CO(E)
- DNone of the mentioned
65The Depth First Search traversal of a graph will result into?
- ALinked List
- BTree
- CGraph with back edges
- DNone of the mentioned
66In Depth First Search, how many times a node is visited?
- AOnce
- BTwice
- CEquivalent to number of indegree of the node
- DNone of the mentioned
67In the following graphs, assume that if there is ever a choice amongst multiple nodes, both the BFS and DFS algorithms will choose the left-most node first. Starting from the green node at the top, which algorithm will visit the least number of nodes before visiting the yellow goal node?
- ABFS
- BDFS
- CNeither BFS nor DFS will ever encounter the goal node in this graph
- DBFS and DFS encounter same number of nodes before encounter the goal node
68In the following graphs, assume that if there is ever a choice amongst multiple nodes, both the BFS and DFS algorithms will choose the left-most node first. Starting from the green node at the top, which algorithm will visit the least number of nodes before visiting the yellow goal node?
- ABFS
- BDFS
- CNeither BFS nor DFS will ever encounter the goal node in this graph
- DBFS and DFS encounter same number of nodes before encounter the goal node
69Consider the following graph. If there is ever a decision between multiple neighbor nodes inthe BFS or DFS algorithms, assume we always choose the letter closest to the beginning of the alphabetfirst.
In what order will the nodes be visited using a Breadth First Search?
In what order will the nodes be visited using Depth First Search?
Consider A is the start node
- ABFS: A B D C E G H F
DFS: A B C E H F G D - BBFS: A D C G H E F B
DFS: A B C F E G H D - CBFS: A B C E H F G D
DFS: A B D C E G H F
- ABFS: A B D C E G H F
70Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal’s algorithm?
- A(b,e), (e,f), (a,c), (b,c), (f,g), (c,d)
- B(b,e), (e,f), (a,c), (f,g), (b,c), (c,d)
- C(b,e), (a,c), (e,f), (b,c), (f,g), (c,d)
- D(b,e), (e,f), (b,c), (a,c), (f,g), (c,d)
71What are NP and P problems?
P is set of problems that can be solved by a deterministic Turing machine in Polynomial time.
NP is set of decision problems that can be solved by a Non-deterministic Turing Machine in Polynomial time- ATrue
- BFalse
72The problem 3-SAT and 2-SAT are
- Aboth in P
- Bboth NP complete
- CNP-complete and in P respectively
- Dundecidable and NP-complete respectively
73Complexity
binary search tree - O([blank_start]h[blank_end])
AVL tree- O([blank_start]log n[blank_end])
splay tree- O([blank_start]log n[blank_end])
(2,4) tree - O([blank_start]log n[blank_end])
red-black tree - O([blank_start]logn[blank_end])
skip list - O([blank_start]log n[blank_end])
merge sort - O([blank_start]n log n[blank_end])- Ah
- Blog n
- Clog n
- Dlog n
- Elog n
- Flog n
- Gn log n
74space used in algorithm-
binary search tree - O([blank_start]n[blank_end])
AVL tree - O([blank_start]n[blank_end])
Splay tree - O([blank_start]n[blank_end])
red-black tree - O([blank_start]n[blank_end])
skip list - O([blank_start]n[blank_end])
merge sort - O([blank_start]n[blank_end])- An
- Bn
- Cn
- Dn
- En
- Fn
75Tree height-
AVL tree - O([blank_start]n[blank_end])
(2,4) tree- O([blank_start]log n[blank_end])
red-black tree- O([blank_start]log n[blank_end])- An
- Blog n
- Clog n
Information
- Description
- Computer Science Quiz on database final, created by Duncan Levings on 17/04/2019.
- Author
- Duncan Levings
- Language
- English
- Views
- 4
- Tags
- Rating
- No ratings yet Rate this quiz