NEW
Font size
WorksheetsSMARTICUS
Total questions: 20
Worksheet time: 10mins
If the post order traversal gives a b - c d * + then the label of the nodes 1, 2, 3 ... will be
+, -, *, a, b, c, d
a, -, b, +, c, *, d
a, b, c, d, -, *, +
-, a, b, +, *, c, d
What is the time complexity for adding an element to a heap?
O(1)
O(log n)
O(n)
O(n log n)
Which data structure is used to implement depth-first search in a graph?
Array
Linked List
Stack
Queue
Which of the following operations on a heap data structure has the worst-case time complexity of O(log n)?
Insertion
Deletion
Search
Heapify
Which of the following is the correct formula to calculate the index of a node's parent in a binary heap?
i/2
2i
2i+1
i-1
The postfix form of the expression (A B)*(C*D− E)*F / G is
AB CD* E − F **G /
AB CD*E − FG /**
AB CDE − F *G /
AB CD* E − F G /
What is a cycle in a graph?
A set of vertices that are all connected to each other.
A path in the graph that starts and ends at the same vertex.
A group of edges that connect two different vertices.
A subgraph that is disconnected from the main graph.
A binary tree is generated by inserting in order the following integers:
50, 15, 62, 5, 20,58, 91, 3,8,37, 60, 24
The number of nodes in the left and right of the root respectively is
(4,7)
(7,4)
(6,3)
(3,6)
What is the time complexity of sorting an array using bubble sort?
O(1)
O(n)
O(n log n)
O(n^2)
Which of the following data structures is commonly used in conjunction with a suffix array to perform efficient pattern matching?
Trie
Hash table
Bloom filter
Skip list
Which of the following algorithms is commonly used to construct a suffix array?
Bubble sort
Merge sort
Quick sort
Radix sort
A binary tree in which every non-leaf node has non-empty left and right subtrees is called a strictly binary tree. Such a tree with 10 leaves
cannot have more than 19 nodes
has exactly 19 nodes
has exactly 17 nodes
cannot have more than 17 nodes
What is the main advantage of using a Treap over other data structures such as AVL trees or red-black trees?
Treaps have a simpler implementation.
Treaps have a lower expected height, resulting in faster operations.
Treaps have better worst-case time complexity.
Treaps are easier to balance.
Which of the following is an advantage of using abstract data types?
They are easy to implement.
They provide a clear separation of concerns between the implementation and the interface
They are only used in low-level programming languages.
They are always more efficient than using concrete data types.
A priority queue is used to implement a stack S that stores characters PUSH(C)is implemented as INSERT(Q,C,K)where K is an appropriate integer key chosen by the implementation. POP is implemented as DELETEMIN(Q). For a sequence of operations, the key chosen are in
Non-increasing order
Non-decreasing order
Strictly increasing order
Strictly decreasing order
The initial configuration of a queue is a, b, c, d, ('a' is in the front end). To get the configuration d, c, b, a, one needs a minimum o
2 deletions and 3 additions
3 deletion and 2 additions
3 deletions and 3 additions
3 deletions and 4 additions
The depth of a complete binary tree with 'n nodes is (log is to be base two)
log (n+1)-1
log(n)
log (n-1) + 1
log(n) + 1
What is the time complexity of inserting an element into a binomial queue of size n?
O(log n)
O(n)
O(log^2 n)
O(1)
Which of the following sorting algorithms has the worst-case time complexity of O(n^2)?
Merge Sort
Quick Sort
Insertion Sort
Radix Sort
Consider the following nested representation of binary trees indicates y and z are the left right subtrees, respectively, of node x. Note that y and z may be NULL or further nested. Which of the following represents a valid binary tree?
(1 2(4 5 6 7))
1((2 3 NULL)4 5 6)7)
(1(234)(567)
(1(2 3 NULL)(4 5))
