Stack
Process of
inserting an element in stack is called ____________
a) Create
b) Push
c) Evaluation
d) Pop
Answer: b
2. Process of
removing an element from stack is called __________
a) Create
b) Push
c) Evaluation
d) Pod
Answer: d
In a stack, if a
user tries to remove an element from empty stack it is called _________
a) Underflow
b) Empty
collection
c) Overflow
d) Garbage
Collection
Answer: a
Pushing an
element into stack already having five elements and stack size of 5 , then
stack becomes
a) Overflow
b) Crash
c) Underflow
d) User flow
Answer: a
Entries in a
stack are “ordered”. What is the meaning of this statement?
a) A collection
of stacks is sortable
b) Stack entries
may be compared with the ‘<‘ operation
c) The entries
are stored in a linked list
d) There is a
Sequential entry that is one by one
Answer : d
Which of the
following applications may use a stack?
a) A parentheses
balancing program
b) Tracking of local
variables at run time
c) Compiler
Syntax Analyzer
d) All of the
mentioned
Answer: d
Explanation: All
are applications of stack.
Consider the
usual algorithm for determining whether a sequence of parentheses is balanced.
The maximum
number of parentheses that appear on the stack AT ANY ONE TIME when the
algorithm analyzes: (()(())(())) are:
a) 1
b) 2
c) 3
d) 4 or more
Answer: c
Explanation:
Applying the postfix expression evaluation.
Consider the
usual algorithm for determining whether a sequence of parentheses is balanced.
Suppose that you
run the algorithm on a sequence that contains 2 left parentheses and 3 right
parentheses (in some order).
The maximum
number of parentheses that appear on the stack AT ANY ONE TIME during the
computation?
a) 1
b) 2
c) 3
d) 4 or more
Answer: b
Explanation:
Applying the postfix expression evaluation.
9. What is the
value of the postfix expression 6 3 2 4 + – *:
a) Something
between -5 and -15
b) Something
between 5 and -5
c) Something
between 5 and 15
d) Something between
15 and 100
Answer: d
Explanation: On
solving the postfix expression the answer comes out to 18.
Here is an infix
expression: 4 + 3*(6*3-12). Suppose that we are using the usual stack algorithm
to convert the expression from infix to postfix notation.
The maximum
number of symbols that will appear on the stack AT ONE TIME during the
conversion of this expression?
a) 1
b) 2
c) 3
d) 4
Answer: d
Explanation:
None.
The postfix form
of the expression (A+ B)*(C*D- E)*F / G is?
a) AB+ CD*E – FG
/**
b) AB + CD* E –
F **G /
c) AB + CD* E –
*F *G /
d) AB + CDE * –
* F *G /
Answer: a
Explanation:
Applying the postfix expression evaluation.
2. The data
structure required to check whether an expression contains balanced parenthesis
is?
a) Stack
b) Queue
c) Array
d) Tree
Answer: a
Explanation:
None.
3. What data
structure would you mostly likely see in a non recursive implementation of a
recursive algorithm?
a) Linked List
b) Stack
c) Queue
d) Tree
Answer: b
Explanation:
None.
4. The process
of accessing data stored in a serial access memory is similar to manipulating
data on a ________
a) Heap
b) Binary Tree
c) Array
d) Stack
Answer: d
Explanation:
None.
5. The postfix
form of A*B+C/D is?
a) *AB/CD+
b) AB*CD/+
c) A*BC+/D
d) ABCD+/*
Answer: b
Explanation:
Applying the postfix expression evaluation.
6. Which data
structure is needed to convert infix notation to postfix notation?
a) Branch
b) Tree
c) Queue
d) Stack
Answer: d
Explanation:
None.
7. The prefix
form of A-B/ (C * D ^ E) is?
a) -/*^ACBDE
b) -ABCD*^DE
c) -A/B*C^DE
d) -A/BC*^DE
Answer: c
Explanation:
Applying the prefix expression evaluation.
8. What is the
result of the following operation
Top (Push (S,
X))
a) X
b) Null
c) S
d) None of the
mentioned
Answer: a
Explanation:
None.
9. The prefix
form of an infix expression p + q – r * t is?
a) + pq – *rt
b) – +pqr * t
c) – +pq * rt
d) – + * pqrt
Answer: c
Explanation:
Applying the prefix expression evaluation.
Which data
structure is used for implementing recursion?
a) Queue
b) Stack
c) Array
d) List
Answer: b
Explanation:
Stacks are used for implementation of Recursion.
The result of
evaluating the postfix expression 5, 4, 6, +, *, 4, 9, 3, /, +, * is?
a) 600
b) 350
c) 650
d) 588
Answer: b
Explanation:
None.
Convert the
following infix expressions into its equivalent postfix expressions
(A + B ⋀D)/(E – F)+G
a) (A B D ⋀ + E F – / G +)
b) (A B D +⋀ E F – / G +)
c) (A B D ⋀ + E F/- G +)
d) None of the
mentioned
Answer: a
Explanation:
Applying the postfix expression evaluation.
Convert the
following Infix expression to Postfix form using a stack
x + y * z + (p *
q + r) * s, Follow usual precedence rule and assume that the expression is
legal.
a) xyz*+pq*r+s*+
b) xyz*+pq*r+s+*
c) xyz+*pq*r+s*+
d) None of the
mentioned
Answer: a
Explanation:
Applying the postfix expression evaluation.
Which of the
following statement(s) about stack data structure is/are NOT correct?
a) Linked List
are used for implementing Stacks
b) Top of the
Stack always contain the new node
c) Stack is the
FIFO data structure
d) Null link is
present in the last node at the bottom of the stack
Answer: c
Explanation:
Stack follows LIFO.
5. Consider the
following operation performed on a stack of size 5.
Push(1);
Pop();
Push(2);
Push(3);
Pop();
Push(4);
Pop();
Pop();
Push(5);
After the completion
of all operation, the number of elements present in stack are
a) 1
b) 2
c) 3
d) 4
Answer: a
Explanation:
None.
Which of the
following is not an inherent application of stack?
a) Reversing a
string
b) Evaluation of
postfix expression
c) Implementation
of recursion
d) Job
scheduling
Answer: d
Explanation: Job
Scheduling is not performed using stacks.
The type of
expression in which operator succeeds its operands is?
a) Infix
Expression
b) Prefix
Expression
c) Postfix
Expression
d) None of the
mentioned
Answer: c
Queue
A linear list of
elements in which deletion can be done from one end (front) and insertion can
take place only at the other end (rear) is known as a ?
a) Queue
b) Stack
c) Tree
d) Linked list
Answer: a
Explanation:
None.
The data
structure required for Breadth First Traversal on a graph is?
a) Stack
b) Array
c) Queue
d) Tree
Answer: c
Explanation:
None.
A queue is a ?
a) FIFO (First In First Out) list
b) LIFO (Last In First Out) list
c) Ordered array
d) Linear tree
Answer: a
Explanation:
None.
In Breadth First
Search of Graph, which of the following data structure is used?
a) Stack
b) Queue
c) Linked list
d) None of the mentioned
Answer: b
Explanation:
None.
If the elements
“A”, “B”, “C” and “D” are placed in a queue and are deleted one at a time, in
what order will they be removed?
a) ABCD
b) DCBA
c) DCAB
d) ABDC
Answer: a
Explanation:
Queue follows FIFO approach.
A data structure
in which elements can be inserted or deleted at/from both the ends but not in
the middle is?
a) Queue
b) Circular queue
c) Dequeue
d) Priority queue
Answer: c
Explanation:
None.
A normal queue,
if implemented using an array of size MAX_SIZE, gets full when
a) Rear = MAX_SIZE – 1
b) Front = (rear + 1)mod MAX_SIZE
c) Front = rear + 1
d) Rear = front
Answer: a
Explanation:
Condition for size of queue.
LInk List
A linear
collection of data elements where the linear node is given by means of pointer
is called?
a) Linked list
b) Node list
c) Primitive
list
d) None of the
mentioned
Answer: a
Consider an
implementation of unsorted singly linked list. Suppose it has its
representation with a head pointer only.
Given the
representation, which of the following operation can be implemented in O(1)
time?
i) Insertion at the front of the linked
list
ii) Insertion at the end of the linked list
iii) Deletion of
the front node of the linked list
iv) Deletion of the last node of the linked
list
a) I and II
b) I and III
c) I, II and III
d) I, II and IV
Answer: b
In linked list
each node contain minimum of two fields. One field is data field to store the
data second field is?
a) Pointer to
character
b) Pointer to
integer
c) Pointer to
node
d) Node
Answer: c
What would be
the asymptotic time complexity to add a node at the end of singly linked list,
if the pointer is initially pointing to the head of the list?
a) O(1)
b) O(n)
c) θ(n)
d) θ(1)
Answer: c
What would be
the asymptotic time complexity to add an element in the linked list?
a) O(1)
b) O(n)
c) O(n2)
d) None of the
mentioned
Answer: b
What would be
the asymptotic time complexity to find an element in the linked list?
a) O(1)
b) O(n)
c) O(n2)
d) None of the
mentioned
Answer: b
What would be
the asymptotic time complexity to insert an element at the second position in
the linked list?
a) O(1)
b) O(n)
c) O(n2)
d) None of the
mentioned
Answer: a
Explanation:
None.
8. The
concatenation of two list can performed in O(1) time. Which of the following
variation of linked list can be used?
a) Singly linked
list
b) Doubly linked
list
c) Circular
doubly linked list
d) Array
implementation of list
Answer: c
Consider the
following definition in c programming language
struct node
{
int data;
struct node * next;
}
typedef struct
node NODE;
NODE *ptr;
Which of the
following c code is used to create new node?
a) ptr =
(NODE*)malloc(sizeof(NODE));
b) ptr =
(NODE*)malloc(NODE);
c) ptr =
(NODE*)malloc(sizeof(NODE*));
d) ptr =
(NODE)malloc(sizeof(NODE));
Answer: a
Explanation: As
it represents the right way to create a node.
This set of Data
Structure Multiple Choice Questions & Answers (MCQs) focuses on “Singly
Linked List”.
1. Which of the
following is not a disadvantage to the usage of array?
a) Fixed size
b) You know the
size of the array prior to allocation
c) Insertion
based on position
d) Accessing
elements at specified positions
Answer: d
Explanation:
Array elements can be accessed in two steps. First, multiply the size of the
data type with the specified position, second, add this value to the base
address. Both of these operations can be done in constant time, hence accessing
elements at a given index/position is faster.
What is the time
complexity of inserting at the end in dynamic arrays?
a) O(1)
b) O(n)
c) O(logn)
d) Either O(1)
or O(n)
Answer: d
Explanation:
Depending on whether the array is full or not, the complexity in dynamic array
varies. If you try to insert into an array which is not full, then the element
is simply stored at the end, this takes O(1) time. If you try to insert into an
array which is full, first you will have to allocate an array with double the
size of the current array and then copy all the elements into it and finally
insert the new element, this takes O(n) time.
What is the time
complexity to count the number of elements in the linked list?
a) O(1)
b) O(n)
c) O(logn)
d) None of the
mentioned
Answer: b
Explanation: To
count the number of elements, you have to traverse through the entire list,
hence complexity is O(n).
What is the
functionality of the following code?
public void
function(Node node)
{
if(size == 0)
head = node;
else
{
Node temp,cur;
for(cur = head; (temp =
cur.getNext())!=null; cur = temp);
cur.setNext(node);
}
size++;
}
a) Inserting a
node at the beginning of the list
b) Deleting a
node at the beginning of the list
c) Inserting a
node at the end of the list
d) Deleting a
node at the end of the list
Answer: c
Explanation: The
for loop traverses through the list and then inserts a new node as
cur.setNext(node);
6. What is the
space complexity for deleting a linked list?
a) O(1)
b) O(n)
c) Either O(1)
or O(n)
d) O(logn)
Answer: a
Explanation: You
need a temp variable to keep track of current node, hence the space complexity
is O(1).
This set of Data
Structure Interview Questions and Answers for freshers focuses on “Singly
Linked Lists Operations – 2”.
1. What kind of
linked list is best to answer question like “What is the item at position n?”
a) Singly linked
list
b) Doubly linked
list
c) Circular
linked list
d) Array
implementation of linked list
Answer: d
Linked lists are
not suitable to for the implementation of?
a) Insertion
sort
b) Radix sort
c) Polynomial
manipulation
d) Binary search
Answer: d
Explanation: It
cannot be implemented using linked lists.
Linked list is
considered as an example of ___________ type of memory allocation.
a) Dynamic
b) Static
c) Compile time
d) None of the
mentioned
In Linked List
implementation, a node carries information regarding
a) Data
b) Link
c) Data and Link
d) None of the
mentioned
Answer: b
Explanation:
None.
Linked list data
structure offers considerable saving in
a) Computational
Time
b) Space
Utilization
c) Space
Utilization and Computational Time
d) None of the
mentioned
Which of the
following points is/are true about Linked List data structure when it is
compared with array
a) Arrays have
better cache locality that can make them better in terms of performance
b) It is easy to
insert and delete elements in Linked List
c) Random access
is not allowed in a typical implementation of Linked Lists
d) All of the
mentioned
Answer: d
Explanation:
None.
What does the
following function do for a given Linked List with first node as head?
void fun1(struct
node* head)
{
if(head == NULL)
return;
fun1(head->next);
printf("%d ", head->data);
}
a) Prints all
nodes of linked lists
b) Prints all
nodes of linked list in reverse order
c) Prints
alternate nodes of Linked List
d) Prints
alternate nodes in reverse order
Answer: b
Explanation:
fun1() prints the given Linked List in reverse manner.
For Linked List
1->2->3->4->5, fun1() prints 5->4->3->2->1.
Which of the
following sorting algorithms can be used to sort a random linked list with
minimum time complexity?
a) Insertion
Sort
b) Quick Sort
c) Heap Sort
d) Merge Sort
Answer: d
Explanation:
Both Merge sort and Insertion sort can be used for linked lists. The slow
random-access performance of a linked list makes other algorithms (such as
quicksort) perform poorly, and others (such as heapsort) completely impossible.
Since worst case time complexity of Merge Sort is O(nLogn) and Insertion sort
is O(n2), merge sort is preferred.
Double Link List
This set of Data Structure Multiple Choice Questions
& Answers (MCQs) focuses on “Doubly Linked List”.
1. Which of the following is false about a doubly linked
list?
a) We can navigate in both the directions
b) It requires more space than a singly linked list
c) The insertion and deletion of a node take a bit longer
d) None of the mentioned
Answer: d
Explanation: A doubly linked list has two pointers ‘left’
and ‘right’ which enable it to traverse in either direction. Compared to singly
liked list which has only a ‘next’ pointer, doubly linked list requires extra
space to store this extra pointer. Every insertion and deletion requires
manipulation of two pointers, hence it takes a bit longer time.
Given the Node class implementation, select one of the
following that correctly inserts a node at the tail of the list.
public class Node
{
protected
int data;
protected
Node prev;
protected
Node next;
public
Node(int data)
{
this.data
= data;
prev
= null;
next
= null;
}
public
Node(int data, Node prev, Node next)
{
this.data
= data;
this.prev
= prev;
this.next
= next;
}
public
int getData()
{
return
data;
}
public
void setData(int data)
{
this.data
= data;
}
public
Node getPrev()
{
return
prev;
}
public
void setPrev(Node prev)
{
this.prev
= prev;
}
public
Node getNext
{
return
next;
}
public
void setNext(Node next)
{
this.next
= next;
}
}
public class DLL
{
protected
Node head;
protected
Node tail;
int
length;
public DLL()
{
head
= new Node(Integer.MIN_VALUE,null,null);
tail
= new Node(Integer.MIN_VALUE,null,null);
head.setNext(tail);
length
= 0;
}
}
a)public void insertRear(int data)
{
Node
node = new Node(data,tail.getPrev(),tail);
node.getPrev().setNext(node);
tail.setPrev(node);
length++;
}
b)public void insertRear(int data)
{
Node
node = new Node(data,tail.getPrev(),tail);
node.getPrev().getPrev().setNext(node);
tail.setPrev(node);
length++;
}
c)public void insertRear(int data)
{
Node
node = new Node(data,tail.getPrev(),tail);
node.getPrev().setNext(tail);
tail.setPrev(node);
length++;
}
d)public void insertRear(int data)
{
Node
node = new Node(data,head,tail);
node.getPrev().setNext(node);
tail.setPrev(node);
length++;
}
Answer: a
Explanation: First create a new node whose ‘prev’ points
to the node pointed to by the ‘prev’ of tail. The ‘next’ of the new node should
point to tail. Set the ‘prev’ of tail to point to new node and the ‘prev’ of
new node to point to the new node.
What is a memory efficient double linked list?
a) Each node has only one pointer to traverse the list
back and forth
b) The list has breakpoints for faster traversal
c) An auxiliary singly linked list acts as a helper list
to traverse through the doubly linked list
d) None of the mentioned
Answer: a
Explanation: Memory efficient doubly linked list has been
proposed recently which has only one pointer to traverse the list back and
forth. The implementation is based on pointer difference.
Explanation: If the position to be deleted is not the
head, advance to the given position and manipulate the previous and next
pointers of next and previous nodes respectively.
5. How do you calculate the pointer difference in a
memory efficient double linked list?
a) head xor tail
b) pointer to previous node xor pointer to next node
c) pointer to previous node – pointer to next node
d) pointer to next node – pointer to previous node
Answer: b
Explanation: The pointer difference is calculated using
option b.
What is the time complexity of inserting a node in a
doubly linked list?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(1)
Answer: c
Explanation: In the worst case, the position to be
inserted maybe at the end of the list, hence you have to traverse through the
entire list to get to the correct position, hence O(n).
How do you insert a node at the beginning of the list?
a)
public class insertFront(int data)
{
Node
node = new Node(data, head, head.getNext());
node.getNext().setPrev(node);
head.setNext(node);
size++;
}
b)
public class insertFront(int data)
{
Node
node = new Node(data, head, head);
node.getNext().setPrev(node);
head.setNext(node);
size++;
}
c)
public class insertFront(int data)
{
Node
node = new Node(data, head, head.getNext());
node.getNext().setPrev(head);
head.setNext(node);
size++;
}
d)
public class insertFront(int data)
{
Node
node = new Node(data, head, head.getNext());
node.getNext().setPrev(node);
head.setNext(node.getNext());
size++;
}
Answer: a
Explanation: The new node’s previous pointer will point
to head and next pointer will point to the current next of head.
Consider the following doubly linked list:
head-1-2-3-4-5-tail
What will be the list after performing the given sequence
of operations?
Node
temp = new Node(6,head,head.getNext());
Node
temp1 = new Node(0,tail.getPrev(),tail);
head.setNext(temp);
temp.getNext().setPrev(temp);
tail.setPrev(temp1);
temp1.getPrev().setNext(temp1);
a) head-0-1-2-3-4-5-6-tail
b) head-1-2-3-4-5-6-tail
c) head-6-1-2-3-4-5-0-tail
d) head-0-1-2-3-4-5-tail
Answer: c
Explanation: The given sequence of operations perform
addition of nodes at the head and tail of the list.
What is the functionality of the following piece of code?
public int function()
{
Node
temp = tail.getPrev();
tail.setPrev(temp.getPrev());
temp.getPrev().setNext(tail);
size--;
return
temp.getItem();
}
a) Return the element at the tail of the list but do not
remove it
b) Return the element at the tail of the list and remove
it from the list
c) Return the last but one element from the list but do
not remove it
d) Return the last but one element at the tail of the
list and remove it from the list
Answer: b
Explanation: The previous and next pointers of the tail
and the last but one element are manipulated, this suggests that the last node
is being removed from the list.
Consider the following doubly linked list:
head-1-2-3-4-5-tail
What will be the list after performing the given sequence
of operations?
Node
temp = new Node(6,head,head.getNext());
head.setNext(temp);
temp.getNext().setPrev(temp);
Node
temp1 = tail.getPrev();
tail.setPrev(temp1.getPrev());
temp1.getPrev().setNext(tail);
a) head-6-1-2-3-4-5-tail
b) head-6-1-2-3-4-tail
c) head-1-2-3-4-5-6-tail
d) head-1-2-3-4-5-tail
Answer: b
Explanation: A new node is added to the head of the list
and a node is deleted from the tail end of the list.
Circular LINK LIST
This set of Data Structure Multiple Choice Questions
& Answers (MCQs) focuses on “Circular Linked List”.
1. What differentiates a circular linked list from a
normal linked list?
a) You cannot have the ‘next’ pointer point to null in a
circular linked list
b) It is faster to traverse the circular linked list
c) You may or may not have the ‘next’ pointer point to
null in a circular linked list
d) All of the mentioned
Answer: c
Explanation: The ‘next’ pointer points to null only when
the list is empty, otherwise it points to the head of the list.
How do you count the number of elements in the circular
linked list?
a)
public int length(Node head)
{
int
length = 0;
if( head
== null)
return
0;
Node
temp = head.getNext();
while(temp
!= head)
{
temp
= temp.getNext();
length++;
}
return
length;
}
b)
public int length(Node head)
{
int
length = 0;
if( head
== null)
return
0;
Node temp
= head.getNext();
while(temp
!= null)
{
temp
= temp.getNext();
length++;
}
return
length;
}
c)
public int length(Node head)
{
int
length = 0;
if( head
== null)
return
0;
Node
temp = head.getNext();
while(temp
!= head && temp != null)
{
temp = head.getNext();
length++;
}
return
length;
}
d) None of the mentioned
What is the functionality of the following piece of code?
Select the most appropriate
public void function(int data)
{
int flag
= 0;
if( head
!= null)
{
Node
temp = head.getNext();
while((temp
!= head) && (!(temp.getItem() == data)))
{
temp
= temp.getNext();
flag
= 1;
break;
}
}
if(flag)
System.out.println("success");
else
System.out.println("fail");
}
a) Print success if a particular element is not found
b) Print fail if a particular element is not found
c) Print success if a particular element is equal to 1
d) Print fail if the list is empty
Answer: b
Explanation: The function prints fail if the given
element is not found. Note that this option is inclusive of option d, the list
being empty is one of the cases covered.
What is the time complexity of searching for an element
in a circular linked list?
a) O(n)
b) O(nlogn)
c) O(1)
d) None of the mentioned
Answer: a
Explanation: In the worst case, you have to traverse
through the entire list of n elements.
Which of the following application makes use of a
circular linked list?
a) Undo operation in a text editor
b) Recursive function calls
c) Allocating CPU to resources
d) All of the mentioned
Answer: c
Explanation: Generally, round robin fashion is employed
to allocate CPU time to resources which makes use of the circular linked list
data structure.
What is the functionality of the following code? Choose
the most appropriate answer.
public int function()
{
if(head
== null)
return
Integer.MIN_VALUE;
int var;
Node
temp = head;
while(temp.getNext()
!= head)
temp
= temp.getNext();
if(temp
== head)
{
var
= head.getItem();
head
= null;
return
var;
}
temp.setNext(head.getNext());
var = head.getItem();
head =
head.getNext();
return
var;
}
a) Return data from the end of the list
b) Returns the data and deletes the node at the end of
the list
c) Returns the data from the beginning of the list
d) Returns the data and deletes the node from the
beginning of the list
Answer: d
Explanation: First traverse through the list to find the
end node, then manipulate the ‘next’ pointer such that it points to the current
head’s next node, return the data stored in head and make this next node as the
head.
What is the functionality of the following code? Choose
the most appropriate answer.
public int function()
{
if(head
== null)
return
Integer.MIN_VALUE;
int var;
Node
temp = head;
Node
cur;
while(temp.getNext()
!= head)
{
cur
= temp;
temp
= temp.getNext();
}
if(temp
== head)
{
var
= head.getItem();
head
= null;
return
var;
}
var =
temp.getItem();
cur.setNext(head);
return
var;
}
a) Return data from the end of the list
b) Returns the data and deletes the node at the end of
the list
c) Returns the data from the beginning of the list
d) Returns the data and deletes the node from the
beginning of the list
Answer: b
Explanation: First traverse through the list to find the
end node, also have a trailing pointer to find the penultimate node,
make this trailing pointer’s ‘next’ point to the head and
return the data stored in the ‘temp’ node.
Which of the following is false about a circular linked
list?
a) Every node has a successor
b) Time complexity of inserting a new node at the head of
the list is O(1)
c) Time complexity for deleting the last node is O(n)
d) None of the mentioned
Answer: b
Explanation: Time complexity of inserting a new node at
the head of the list is O(n) because you have to traverse through the list to
find the tail node.
Consider a small circular linked list. How to detect the
presence of cycles in this list effectively?
a) Keep one node as head and traverse another temp node
till the end to check if its ‘next points to head
b) Have fast and slow pointers with the fast pointer
advancing two nodes at a time and slow pointer advancing by one node at a time
c) Cannot determine, you have to pre-define if the list
contains cycles
d) None of the mentioned
Answer: b
Balanced Parenthesis Multiple Choice Questions
What is the time complexity of balancing parentheses
algorithm?
a) O (N)
b) O (N log N)
c) O (M log N)
d) O (N2)
Answer: a
Explanation: The time complexity of balancing parentheses
algorithm is mathematically found to be O (N).
Which application of stack is used to ensure that the
pair of parentheses is properly nested?
a) Balancing symbols
b) Reversing a stack
c) Conversion of an infix to postfix expression
d) Conversion of an infix to prefix expression
Answer: a
Explanation: Balancing symbols application ensures that
the pair of parentheses are properly nested while reversing stack reverses a
stack.
In balancing parentheses algorithm, the string is read
from?
a) right to left
b) left to right
c) center to right
d) center to left
Answer: b
Explanation: Any string is read by the compiler from left
to right and not from right to left.
Which is the most appropriate data structure for applying
balancing of symbols algorithm?
a) stack
b) queue
c) tree
d) graph
Answer: a
Explanation: Stack is the most appropriate data structure
for balancing symbols algorithm because stack follows LIFO principle (Last In
First Out).
Which of the following does the balancing symbols
algorithm include?
a) balancing double quotes
b) balancing single quotes
c) balancing operators and brackets
d) balancing parentheses, brackets and braces
Answer: d
Explanation: The balancing symbols algorithm using stack
only includes balancing parentheses, brackets and braces and not any other
symbols.
Which of the following statement is incorrect with
respect to balancing symbols algorithm?
a) {[()]}
b) ([ )]
c) {( )}
d) { [ ] }
Answer: b
Explanation: ([ )] is incorrect because’)’ occurs before
the corresponding ‘]’ is encountered.
What should be done when an opening parentheses is read
in a balancing symbols algorithm?
a) push it on to the stack
b) throw an error
c) ignore the parentheses
d) pop the stack
Answer: a
Explanation: When an opening bracket/braces/parentheses
is encountered, it is pushed on to the stack. When the corresponding end bracket/braces/parentheses
is not found, throw an error.
When the corresponding end bracket/braces/parentheses is
not found, what happens?
a) The stack is popped
b) Ignore the parentheses
c) An error is reported
d) It is treated as an exception
If the corresponding end bracket/braces/parentheses is
encountered, which of the following is done?
a) push it on to the stack
b) pop the stack
c) throw an error
d) treated as an exception
Answer: b
Explanation: When the corresponding end
bracket/braces/parentheses is encountered, the stack is popped. When an opening
bracket/braces/parentheses is encountered, it is pushed on to the stack.
An error is reported when the stack is not empty at the
end.
a) True
b) False
Answer: a
Explanation: When the stack contains elements at the end,
it means that the given string of parentheses is not balanced.
Which among the following is not a palindrome?
a) Madam
b) Dad
c) Malayalam
d) Maadam
Answer: d
Explanation: By definition, a palindrome is a string
which is the same forward and backward, here, option d doesn’t adhere to this
definition.
4. Which data structure can be used to test a palindrome?
a) Tree
b) Heap
c) Stack
d) Priority queue
Answer: c
What is the number of moves required in the Tower of
Hanoi problem for k disks?
a) 2k – 1
b) 2k + 1
c) 2k + 1
d) 2k – 1
Answer: d
Infix to Prefix Conversion:-
What data structure is used when converting an infix
notation to prefix notation?
a) Stack
b) Queue
c) B-Trees
d) Linked-list
Answer: a
Explanation: First you reverse the given equation and
carry out the algorithm of infix to postfix expression. Here, the data
structure used is stacks.
What would be the Prefix notation for the given equation?
A+(B*C)
a) +A*CB
b) *B+AC
c) +A*BC
d) *A+CB
Answer: c
Explanation: Reverse the equation or scan the equation
from right to left. Apply the infix-postfix algorithm. The equation inside the
bracket evaluates to CB* and outside the bracket evaluates to A+ therefore
getting CB*A+. Reversing this and we get +A*BC.
What would be the Prefix notation for the given equation?
(A*B)+(C*D)
a) +*AB*CD
b) *+AB*CD
c) **AB+CD
d) +*BA*CD
Answer: a
Explanation: Reverse the equation or scan the equation
from right to left. Apply the infix-postfix algorithm. The equation inside the
brackets evaluate to DC* and BA* respectively giving us DC*BA*+ in the end.
Reversing this we get the +*AB*CD.
What would be the Prefix notation for the given equation?
A+B*C^D
a) +A*B^CD
b) +A^B*CD
c) *A+B^CD
d) ^A*B+CD
Answer: a
Explanation: Reverse the equation or scan the equation
from right to left. Apply the infix-prefix algorithm. The preference order in
ascending order are as follows +*^. Operators are pushed into the stack and
popped if its preference is greater than the one which is getting pushed. In
the end all operators are popped. The equation evaluates to DC^B*A+. Reversing
this we get our following answer.
Out of the following operators (^, *, +, &, $), the
one having highest priority is _________
a) +
b) $
c) ^
d) &
Answer: c
Explanation: According to the algorithm (infix-prefix),
it follows that the exponentiation will have the highest priority.
6. Out of the following operators (|, *, +, &, $),
the one having lowest priority is ________
a) +
b) $
c) |
d) &
Answer: b
Explanation: According to the algorithm (infix-prefix),
it follows that the logical OR will have the lowest priority.
What would be the Prefix notation for the given equation?
A^B^C^D
a) ^^^ABCD
b) ^A^B^CD
c) ABCD^^^
d) AB^C^D
Answer: a
Explanation: Reverse the equation or scan the equation
from right to left. Apply the infix-prefix algorithm. Here we have to remember
that the exponentiation has order of associativity from right to left.
Therefore the stack goes on pushing ^. Therefore resulting in ^^^ABCD.
What would be the Prefix notation for the given equation?
a+b-c/d&e|f
a) |&-+ab/cdef
b) &|-+ab/cdef
c) |&-ab+/cdef
d) |&-+/abcdef
Answer: a
Infix to Postfix Conversion
When an operand is read, which of the following is done?
a) It is placed on to the output
b) It is placed in operator stack
c) It is ignored
d) Operator stack is emptied
Answer: a
Explanation: While converting an infix expression to a
postfix expression, when an operand is read, it is placed on to the output.
When an operator is read, it is placed in the operator stack.
What should be done when a left parenthesis ‘(‘ is
encountered?
a) It is ignored
b) It is placed in the output
c) It is placed in the operator stack
d) The contents of the operator stack is emptied
Answer: c
Explanation: When a left parenthesis is encountered, it
is placed on to the operator stack. When the corresponding right parenthesis is
encountered, the stack is popped until the left parenthesis and remove both the
parenthesis.
3. Which of the following is an infix expression?
a) (a+b)*(c+d)
b) ab+c*
c) +ab
d) abc+*
Answer: a
Explanation: (a+b)*(c+d) is an infix expression. +ab is a
prefix expression and ab+c* is a postfix expression.
4. What is the time complexity of an infix to postfix
conversion algorithm?
a) O(N log N)
b) O(N)
c) O(N2)
d) O(M log N)
Answer: b
Explanation: The time complexity of an infix to postfix
expression conversion algorithm is mathematically found to be O(N).
What is the postfix expression for the corresponding
infix expression?
a+b*c+(d*e)
a) abc*+de*
b) abc+*de*
c) a+bc*de+*
d) abc*+(de)*
Answer: a
Explanation: Using the infix to postfix expression
conversion algorithm, the corresponding postfix expression is found to be
abc*+de*.
Parentheses are simply ignored in the conversion of infix
to postfix expression.
a) True
b) False
Answer: b
Explanation: When a parenthesis is encountered, it is
placed on the operator stack. When the corresponding parenthesis is
encountered, the stack is popped until the other parenthesis is reached and
they are discarded.
It is easier for a computer to process a postfix
expression than an infix expression.
a) True
b) False
Answer: a
Explanation: Computers can easily process a postfix
expression because a postfix expression keeps track of precedence of operators.
What is the postfix expression for the infix expression?
a-b-c
a) -ab-c
b) abc–
c) –abc
d) -ab-c
Answer: d
Explanation: The corresponding postfix expression for the
given infix expression is found to be –ab-c and not abc- – .
What is the postfix expression for the following infix
expression?
a/b^c-d
a) abc^/d-
b) ab/cd^-
c) ab/^cd-
d) abcd^/-
Answer: a
Explanation: Using the infix to postfix conversion
algorithm, the corresponding postfix expression for the infix expression is
found to be abc^/d-.
Which of the following statement is incorrect with
respect to infix to postfix conversion algorithm?
a) operand is always placed in the output
b) operator is placed in the stack when the stack
operator has lower precedence
c) parenthesis are included in the output
d) higher and equal priority operators follow the same
condition
Answer: c
Explanation: Parentheses are not included in the output.
They are placed in the operator stack and then discarded.
In infix to postfix conversion algorithm, the operators
are associated from?
a) right to left
b) left to right
c) centre to left
d) centre to right
Answer: b
Prefix to Infix Conversion:-
What would be the solution to the given prefix notation?
- + 5 / 10 5 5
a) 2
b) 5
c) 10
d) 7
Answer: a
Explanation: The infix notation of the given prefix
notation is 5+10/5-5 which gives us 2 as our answer.
What would be the solution to the given prefix notation?
/ / / / 16 4 2 1
a) 1
b) 4
c) 2
d) 8
Answer: a
What would be the solution to the given prefix notation?
+ 9 * 3 / 8 4
a) 14
b) 15
c) 18
d) 12
Answer: b
Explanation: The infix notation for the given prefix
notation is (9+(3*(8/4))) which solves to 15. So 15 is correct answer.
What would be the solution to the given prefix notation?
- + 1 2 * 3 / 6 2
a) 6
b) -6
c) 3
d) -3
Answer: b
Self Organizing List :-
The self organizing list improves the efficiency of
_______
a) binary search
b) jump search
c) sublist search
d) linear search
Answer: d
Explanation: Linear search in a linked list has time
complexity O(n). To improve the efficiency of the linear search the self
organizing list is used. A self-organizing list improves the efficiency of
linear search by moving more frequently accessed elements towards the head of
the list.
Which of the following is true about the Move-To-Front
Method for rearranging nodes?
a) node with highest access count is moved to head of the
list
b) requires extra storage
c) may over-reward infrequently accessed nodes
d) requires a counter for each node
Answer: c
Explanation: In Move-To-front Method the element which is
searched is moved to the head of the list. And if a node is searched even once,
it is moved to the head of the list and given maximum priority even if it is
not going to be accessed frequently in the future. Such a situation is referred
to as over-rewarding.
What technique is used in Transpose method?
a) searched node is swapped with its predecessor
b) node with highest access count is moved to head of the
list
c) searched node is swapped with the head of list
d) searched nodes are rearranged based on their proximity
to the head node
Answer: a
Explanation: In Transpose method, if any node is
searched, it is swapped with the node in front unless it is the head of the
list. So, in Transpose method searched node is swapped with its predecessor.
The worst case running time of a linear search on the
self organizing list is ____
a) O(1)
b) O(logn)
c) O(n)
d) O(n2)
Answer: c
Explanation: Worst case occurs when the element is
located at the very end of list. So n comparisons must be made to the locate
element. So the worst case running time of linear search on self organizing
list is O(n).
Which of the following data structure is preferred to
have lesser search time when the list size is small?
a) search tree
b) sorted list
c) self organizing list
d) linked list
Answer: c
Explanation: Self-organizing list is easy and simple to
implement than search tree and it requires no additional space. So using self
organizing list is preferred when list size is small.
In _____________ method, whenever a node is accessed, it
might move to the head of the list if its number of accesses becomes greater
than the records preceding it.
a) least recently used
b) count
c) traspose
d) exchange
Answer: b
Explanation: In the count method, the number of times a
node was accessed is counted and is stored in a counter variable associated
with each node. Then the nodes are arranged in descending order based on their
access counts. And the node with highest access count is head of the list.
Symbol tables during compilation of program is
efficiently implemented using __________
a) a singly linked list
b) a doubly linked list
c) a self organizing list
d) an array
Answer: c
Explanation: Self organizing list allows fast sequential
search and it is simple to implement and requires no extra storage. Self-organizing
list is used to implement the symbol table.
Which of the following method performs poorly when
elements are accessed in sequential order?
a) count method
b) move to front method
c) transpose meth
d) ordering method
Answer: b
Explanation: Move-to-front method performs poorly when
the elements are accessed in sequential order, especially if that sequential
order is then repeated multiple times.
9. The self organizing list improves _____
a) average access time
b) insertion
c) deletion
d) binary search
Answer: a
Explanation: The self-organizing list rearranges the
nodes based on the access probabilities of the nodes. So the required elements
can be located efficiently. Therefore, self-organizing list is mainly used to
improve the average access time.
Which of the following is not the rearranging method used
to implement self-organizing lists?
a) count method
b) move to front method
c) ordering method
d) least frequently used
Answer: d
Explanation: Least frequently used is a buffer
replacement policy, while other three are methods to reorder the nodes in the
self-organizing lists based on their access probability.
Preorder Traversal
For the tree below, write the pre-order traversal.
a) 2, 7, 2, 6, 5, 11, 5, 9, 4
b) 2, 7, 5, 2, 6, 9, 5, 11, 4
c) 2, 5, 11, 6, 7, 4, 9, 5, 2
d) 2, 7, 5, 6, 11, 2, 5, 4, 9
Answer: a
Explanation: Pre order traversal follows
NLR(Node-Left-Right).
For the tree below, write the post-order traversal.
a) 2, 7, 2, 6, 5, 11, 5, 9, 4
b) 2, 7, 5, 2, 6, 9, 5, 11, 4
c) 2, 5, 11, 6, 7, 4, 9, 5, 2
d) 2, 7, 5, 6, 11, 2, 5, 4, 9
Answer: c
Explanation: Post order traversal follows
LRN(Left-Right-Node).
Select the code snippet which performs pre-order
traversal.
a)
public void preorder(Tree root)
{
System.out.println(root.data);
preorder(root.left);
preorder(root.right);
}
b)
public void preorder(Tree root)
{
preorder(root.left);
System.out.println(root.data);
preorder(root.right);
}
c)
public void preorder(Tree root)
{
System.out.println(root.data);
preorder(root.right);
preorder(root.left);
}
d) None of the mentioned
Answer: a
Explanation: Pre-order traversal follows
NLR(Node-Left-Right).
Select the code snippet which performs post-order
traversal.
a)
public void postorder(Tree root)
{
System.out.println(root.data);
postorder(root.left);
postorder(root.right);
}
b)
public void postorder(Tree root)
{
postorder(root.left);
postorder(root.right);
System.out.println(root.data);
}
c)
public void postorder(Tree root)
{
System.out.println(root.data);
postorder(root.right);
postorder(root.left);
}
d) None of the mentioned
Answer: a
Explanation: Post order traversal follows
NLR(Left-Right-Node).
What is the time complexity of pre-order traversal in the
iterative fashion?
a) O(1)
b) O(n)
c) O(logn)
d) O(nlogn)
Answer: b
Explanation: Since you have to go through all the nodes,
the complexity becomes O(n).
What is the space complexity of the post-order traversal
in the recursive fashion? (d is the tree depth and n is the number of nodes)
a) O(1)
b) O(nlogd)
c) O(logd)
d) O(d)
Answer: d
Explanation: In the worst case we have d stack frames in
the recursive call, hence the complexity is O(d).
To obtain a prefix expression, which of the tree
traversals is used?
a) Level-order traversal
b) Pre-order traversal
c) Post-order traversal
d) In-order traversal
Answer: b
Explanation: As the name itself suggests, pre-order
traversal can be used.
Postorder Traversal
In postorder traversal of binary tree right subtree is
traversed before visiting root.
a) True
b) False
Answer: a
What is the possible number of binary trees that can be
created with 3 nodes, giving the sequence N, M, L when traversed in post-order.
a) 15
b) 3
c) 5
d) 8
Answer: c
The post-order traversal of a binary tree is O P Q R S T.
Then possible pre-order traversal will be ________
a) T Q R S O P
b) T O Q R P S
c) T Q O P S R
d) T Q O S P R
Answer: c
A binary search tree contains values 7, 8, 13, 26, 35,
40, 70, 75. Which one of the following is a valid post-order sequence of the
tree provided the pre-order sequence as 35, 13, 7, 8, 26, 70, 40 and 75?
a) 7, 8, 26, 13, 75, 40, 70, 35
b) 26, 13, 7, 8, 70, 75, 40, 35
c) 7, 8, 13, 26, 35, 40, 70, 75
d) 8, 7, 26, 13, 40, 75, 70, 35
Answer: d
Which of the following pair’s traversals on a binary tree
can build the tree uniquely?
a) post-order and pre-order
b) post-order and in-order
c) post-order and level order
d) level order and preorder
Answer: b
A full binary tree can be generated using ______
a) post-order and pre-order traversal
b) pre-order traversal
c) post-order traversal
d) in-order traversal
Answer: a
The maximum number of nodes in a tree for which
post-order and pre-order traversals may be equal is ______
a) 3
b) 1
c) 2
d) any number
Answer: b
The steps for finding post-order traversal are traverse
the right subtree, traverse the left subtree or visit the current node.
a) True
b) False
The pre-order and in-order are traversals of a binary
tree are T M L N P O Q and L M N T O P Q. Which of following is post-order
traversal of the tree?
a) L N M O Q P T
b) N M O P O L T
c) L M N O P Q T
d) O P L M N Q T
Answer: a
For a binary tree the first node visited in in-order and
post-order traversal is same.
a) True
b) False
Answer: b
Inorder Traversal
For the tree below, write the in-order traversal.
a) 2, 7, 2, 6, 5, 11, 5, 9, 4
b) 2, 7, 5, 2, 6, 9, 5, 11, 4
c) 2, 5, 11, 6, 7, 4, 9, 5, 2
d) 2, 7, 5, 6, 11, 2, 5, 4, 9
Answer: d
For the tree
below, write the level-order traversal.
a) 2, 7, 2, 6, 5, 11, 5, 9, 4
b) 2, 7, 5, 2, 6, 9, 5, 11, 4
c) 2, 5, 11, 6, 7, 4, 9, 5, 2
d) 2, 7, 5, 6, 11, 2, 5, 4, 9
Answer: b
Select the code snippet which performs in-order
traversal.
a)
public void inorder(Tree root)
{
System.out.println(root.data);
inorder(root.left);
inorder(root.right);
}
b)
public void inorder(Tree root)
{
inorder(root.left);
System.out.println(root.data);
inorder(root.right);
}
c)
public void inorder(Tree root)
{
System.out.println(root.data);
inorder(root.right);
inorder(root.left);
}
d) None of the mentioned
Answer: b
What is the space complexity of the in-order traversal in
the recursive fashion? (d is the tree depth and n is the number of nodes)
a) O(1)
b) O(nlogd)
c) O(logd)
d) O(d)
Answer: d
Explanation: In the worst case we have d stack frames in
the recursive call, hence the complexity is O(d).
What is the time complexity of level order traversal?
a) O(1)
b) O(n)
c) O(logn)
d) O(nlogn)
Answer: b
Which of the following graph traversals closely imitates
level order traversal of a binary tree?
a) Depth First Search
b) Breadth First Search
c) Depth & Breadth First Search
d) None of the mentioned
Answer: b
In a binary search tree, which of the following
traversals would print the numbers in the ascending order?
a) Level-order traversal
b) Pre-order traversal
c) Post-order traversal
d) In-order traversal
Answer: d
Binary Search Tree
Which of the following is false about a binary search
tree?
a) The left child is always lesser than its parent
b) The right child is always greater than its parent
c) The left and right sub-trees should also be binary
search trees
d) None of the mentioned
Answer: d
Explanation: All the options hold good for a binary
search tree and can be considered as a definition for a BST.
2. How to search for a key in a binary search tree?
a)
public Tree search(Tree root, int key)
{
if( root
== null || root.key == key )
{
return
root;
}
if(
root.key < key )
{
return
search(root.right,key);
}
else
return
search(root.left,key);
}
b)
public Tree search(Tree root, int key)
{
if( root
== null || root.key == key )
{
return
root;
}
if(
root.key < key )
{
return
search(root.left,key);
}
else
return
search(root.right,key);
}
c)
public Tree search(Tree root, int key)
{
if( root
== null)
{
return
root;
}
if(
root.key < key )
{
return
search(root.right,key);
}
else
return
search(root.left,key);
}
d) None of the mentioned
Answer: a
Explanation: As we know that the left child is lesser
than the parent, if the root’s key is greater than the given key, we look only
into the left sub-tree, similarly for right sub-tree.
What is the speciality about the inorder traversal of a
binary search tree?
a) It traverses in a non increasing order
b) It traverses in an increasing order
c) It traverses in a random fashion
d) None of the mentioned
Answer: b
Explanation: As a binary search tree consists of elements
lesser than the node to the left and the ones greater than the node to the
right, an inorder traversal will give the elements in an increasing order.
What does the following piece of code do?
public void func(Tree root)
{
func(root.left());
func(root.right());
System.out.println(root.data());
}
a) Preorder traversal
b) Inorder traversal
c) Postorder traversal
d) Level order traversal
Answer: c
Explanation: In a postorder traversal, first the left
child is visited, then the right child and finally the parent.
What does the following piece of code do?
public void func(Tree root)
{
System.out.println(root.data());
func(root.left());
func(root.right());
}
a) Preorder traversal
b) Inorder traversal
c) Postorder traversal
d) Level order traversal
Answer: a
Explanation: In a preorder traversal, first the parent is
visited, then the left child and finally the right child.
How will you find the minimum element in a binary search
tree?
a)
public void min(Tree root)
{
while(root.left()
!= null)
{
root
= root.left();
}
System.out.println(root.data());
}
b)
advertisement
public void min(Tree root)
{
while(root
!= null)
{
root
= root.left();
}
System.out.println(root.data());
}
c)
public void min(Tree root)
{
while(root.right()
!= null)
{
root
= root.right();
}
System.out.println(root.data());
}
d)
public void min(Tree root)
{
while(root
!= null)
{
root
= root.right();
}
System.out.println(root.data());
}
Answer: a
Explanation: Since all the elements lesser than a given
node will be towards the left, iterating to the leftmost leaf of the root will
give the minimum element in a binary search tree.
Given that 2 elements are present in the tree, write a
function to find the LCA(Least Common Ancestor) of the 2 elements.
a)
public void lca(Tree root,int n1, int n2)
{
while
(root != NULL)
{
if
(root.data() > n1 && root.data() > n2)
root =
root.right();
else if
(root.data() < n1 && root.data() < n2)
root =
root.left();
else break;
}
System.out.println(root.data());
}
b)
public void lca(Tree root,int n1, int n2)
{
while (root !=
NULL)
{
if
(root.data() > n1 && root.data() < n2)
root =
root.left();
else if
(root.data() < n1 && root.data() > n2)
root =
root.right();
else
break;
}
System.out.println(root.data());
}
c)
public void lca(Tree root,int n1, int n2)
{
while (root !=
NULL)
{
if
(root.data() > n1 && root.data() > n2)
root =
root.left();
else if
(root.data() < n1 && root.data() < n2)
root =
root.right();
else
break;
}
System.out.println(root.data());
}
d) None of the mentioned
Answer: c
What are the conditions for an optimal binary search tree
and what is its advantage?
a) The tree should not be modified and you should know
how often the keys are accessed, it improves the lookup cost
b) You should know the frequency of access of the keys,
improves the lookup time
c) The tree can be modified and you should know the
number of elements in the tree before hand, it improves the deletion time
d) None of the mentioned
Answer: a
Balanced Binary Tree
What will be the height of a balanced full binary tree
with 8 leaves?
a) 8
b) 5
c) 6
d) 4
Answer: d
The balance factor of a node in a binary tree is defined
as _____
a) addition of heights of left and right subtrees
b) height of right subtree minus height of left subtree
c) height of left subtree minus height of right subtree
d) height of right subtree minus one
Answer: c
Figure below is a balanced binary tree. If a node
inserted as child of the node R, how many nodes will become unbalanced?
balanced-binary-tree-questions-answers-q3
a) 2
b) 1
c) 3
d) 0
Answer: b
A binary tree is balanced if the difference between left
and right subtree of every node is not more than ____
a) 1
b) 3
c) 2
d) 0
Answer: a
Which of the following tree data structures is not a
balanced binary tree?
a) AVL tree
b) Red-black tree
c) Splay tree
d) B-tree
Answer: d
Balanced binary tree with n items allows the lookup of an
item in ____ worst-case time.
a) O(log n)
b) O(nlog 2)
c) O(n)
d) O(1)
Answer: a
Which of the following data structures can be efficiently
implemented using height balanced binary search tree?
a) sets
b) priority queue
c) heap
d) both sets and priority queue
Answer: d
Two balanced binary trees are given with m and n elements
respectively. They can be merged into a balanced binary search tree in ____
time.
a) O(m+n)
b) O(mn)
c) O(m)
Answer: a
Which of the following is an advantage of balanced binary
search tree, like AVL tree, compared to binary heap?
a) insertion takes less time
b) deletion takes less time
c) searching takes less time
d) construction of the tree takes less time than binary
heap
Answer: a
Self Balancing Binary Search Tree
Which of the following is not the self balancing binary
search tree?
a) AVL Tree
b) 2-3-4 Tree
c) Red – Black Tree
d) Splay Tree
Answer: b
The binary tree sort implemented using a self – balancing
binary search tree takes ______ time is worst case.
a) O(n log n)
b) O(n)
c) O(n2)
d) O(log n)
Answer: a
Explanation: The worst case running time of the binary
tree sort is O(n2). But, the worst case running time can be improved to the O(n
log n) using a self – balancing binary search tree.
An AVL tree is a self – balancing binary search tree, in
which the heights of the two child sub trees of any node differ by _________
a) At least one
b) At most one
c) Two
d) At most two
Answer: b
Associative arrays can be implemented using __________
a) B-tree
b) A doubly linked list
c) A single linked list
d) A self balancing binary search tree
Answer: d
Self – balancing binary search trees have a much better
average-case time complexity than hash tables.
a) True
b) False
Answer: b
Which of the following is a self – balancing binary
search tree?
a) 2-3 tree
b) Threaded binary tree
c) AA tree
d) Treap
Answer: c
A self – balancing binary search tree can be used to
implement ________
a) Priority queue
b) Hash table
c) Heap sort
d) Priority queue and Heap sort
Answer: a
In which of the following self – balancing binary search
tree the recently accessed element can be accessed quickly?
a) AVL tree
b) AA tree
c) Splay tree
d) Red – Black tree
Answer: c
The minimum height of self balancing binary search tree
with n nodes is _____
a) log2(n)
b) n
c) 2n + 1
d) 2n – 1
Answer: a
Binary tree sort implemented using a self balancing
binary search tree takes O(n log n) time in the worst case but still it is
slower than merge sort.
a) True
b) False
Answer: a
AVL Tree
What is an AVL tree?
a) a tree which is balanced and is a height balanced tree
b) a tree which is unbalanced and is a height balanced
tree
c) a tree with three children
d) a tree with atmost 3 children
Answer: a
Why we need to a binary tree which is height balanced?
a) to avoid formation of skew trees
b) to save memory
c) to attain faster memory access
d) to simplify storing
What is the maximum height of an AVL tree with p nodes?
a) p
b) log(p)
c) log(p)/2
d) p⁄2
Answer: b
To restore the AVL property after inserting a element, we
start at the insertion point and move towards root of that tree. is this
statement true?
a) true
b) false
Answer: a
Given an empty AVL tree, how would you construct AVL tree
when a set of numbers are given without performing any rotations?
a) just build the tree with the given input
b) find the median of the set of elements given, make it
as root and construct the tree
c) use trial and error
d) use dynamic programming to build the tree
Answer: b
What maximum difference in heights between the leafs of a
AVL tree is possible?
a) log(n) where n is the number of nodes
b) n where n is the number of nodes
c) 0 or 1
d) atmost 1
Answer: a
Consider the pseudo code:
int
avl(binarysearchtree root):
if(not root)
return 0
left_tree_height = avl(left_of_root)
if(left_tree_height== -1)
return
left_tree_height
right_tree_height= avl(right_of_root)
if(right_tree_height==-1)
return
right_tree_height
Does the above code can check if a binary search tree is
an AVL tree?
a) yes
b) no
Answer: a
Consider the below left-left rotation pseudo code where
the node contains value pointers to left, right child nodes and a height value
and Height() function returns height value stored at a particular node.
avltree
leftrotation(avltreenode z):
avltreenode w
=x-left
x-left=w-right
w-right=x
x-height=max(Height(x-left),Height(x-right))+1
w-height=max(missing)+1
return w
What is missing?
a) Height(w-left), x-height
b) Height(w-right), x-height
c) Height(w-left), x
d) Height(w-left)
Answer: a
Red Black Tree
What is the special property of red-black trees and what
root should always be?
a) a color which is either red or black and root should
always be black color only
b) height of the tree
c) pointer to next node
d) a color which is either green or black
Answer: a
Why do we impose restrictions like
. root property is black
. every leaf is black
. children of red node are black
. all leaves have same black
a) to get logarithm time complexity
b) to get linear time complexity
c) to get exponential time complexity
d) to get constant time complexity
Answer: a
What are the operations that could be performed in
O(logn) time complexity by red-black tree?
a) insertion, deletion, finding predecessor, successor
b) only insertion
c) only finding predecessor, successor
d) for sorting
Answer: a
Explanation: We impose restrictions (refer question 2) to
achieve logarithm time complexities.
5. Which of the following is an application of Red-black
trees and why?
a) used to store strings efficiently
b) used to store integers efficiently
c) can be used in process schedulers, maps, sets
d) for efficient sorting
Answer: c
When it would be optimal to prefer Red-black trees over
AVL trees?
a) when there are more insertions or deletions
b) when more search is needed
c) when tree must be balanced
d) when log(nodes) time complexity is needed
Answer: a
Why Red-black trees are preferred over hash tables though
hash tables have constant time complexity?
a) no they are not preferred
b) because of resizing issues of hash table and better
ordering in redblack trees
c) because they can be implemented using trees
d) because they are balanced
Answer: b
How can you save memory when storing color information in
Red-Black tree?
a) using least significant bit of one of the pointers in
the node for color information
b) using another array with colors of each node
c) storing color information in the node structure
d) using negative and positive numbering
Answer: a
When to choose Red-Black tree, AVL tree and B-trees?
a) many inserts, many searches and when managing more
items respectively
b) many searches, when managing more items respectively
and many inserts respectively
c) sorting, sorting and retrieval respectively
d) retrieval, sorting and retrieval respectively
Answer: a
B-Tree
Which of the following is the most widely used external
memory data structure?
a) AVL tree
b) B-tree
c) Red-black tree
d) Both AVL tree and Red-black tree
Answer: b
B-tree of order n is a order-n multiway tree in which
each non-root node contains __________
a) at most (n – 1)/2 keys
b) exact (n – 1)/2 keys
c) at least 2n keys
d) at least (n – 1)/2 keys
Answer: d
A B-tree of order 4 and of height 3 will have a maximum
of _______ keys.
a) 255
b) 63
c) 127
d) 188
Answer: a
Five node splitting operations occurred when an entry is
inserted into a B-tree. Then how many nodes are written?
a) 14
b) 7
c) 11
d) 5
Answer: c
B-tree and AVL tree have the same worst case time
complexity for insertion and deletion.
a) True
b) False
Answer: a
2-3-4 trees are B-trees of order 4. They are an isometric
of _____ trees.
a) AVL
b) AA
c) 2-3
d) Red-Black
Answer: d
What is the best case height of a B-tree of order n and
which has k keys?
a) logn (k+1) – 1
b) nk
c) logk (n+1) – 1
d) klogn
Answer: a
Compression techniques can be used on the keys to reduce
both space and time requirements in a B-tree.
a) True
b) False
Answer: a
Which of the following is true?
a) larger the order of B-tree, less frequently the split
occurs
b) larger the order of B-tree, more frequently the split
occurs
c) smaller the order of B-tree, more frequently the split
occurs
d) smaller the order of B-tree, less frequently the split
occurs
Answer: a
B+ Tree
In a B+ tree, both the internal nodes and the leaves have
keys.
a) True
b) False
Answer: b
Which of the following is true?
a) B + tree allows only the rapid random access
b) B + tree allows only the rapid sequential access
c) B + tree allows rapid random access as well as rapid
sequential access
d) B + tree allows rapid random access and slower
sequential access
Answer: c
A B+ tree can contain a maximum of 7 pointers in a node.
What is the minimum number of keys in leaves?
a) 6
b) 3
c) 4
d) 7
Answer: b
Which of the following is false?
a) A B+ -tree grows downwards
b) A B+ -tree is balanced
c) In a B+ -tree, the sibling pointers allow sequential searching
d) B+ -tree is shallower than B-tree
Answer: a
Statement 1: When a node is split during insertion, the
middle key is promoted to the parent as well as retained in right half-node.
Statement 2: When a key is deleted from the leaf, it is
also deleted from the non-leaf nodes of the tree.
a) Statement 1 is true but statement 2 is false
b) Statement 2 is true but statement 1 is false
c) Both the statements are true
d) Both the statements are false
Answer: a
Efficiency of finding the next record in B+ tree is ____
a) O(n)
b) O(log n)
c) O(nlog n)
d) O(1)
Answer: d
What is the maximum number of keys that a B+ -tree of
order 3 and of height 3 have?
a) 3
b) 80
c) 27
d) 26
Answer: d
Which of the following is false?
a) Compared to B-tree, B+ -tree has larger fanout
b) Deletion in B-tree is more complicated than in B+
-tree
c) B+ -tree has greater depth than corresponding B-tree
d) Both B-tree and B+ -tree have same search and
insertion efficiencies
Answer: c
Which one of the following data structures are preferred
in database-system implementation?
a) AVL tree
b) B-tree
c) B+ -tree
d) Splay tree
Answer: c
Heap
In a max-heap, element with the greatest key is always in
the which node?
a) Leaf node
b) First node of left sub tree
c) root node
d) First node of right sub tree
Answer: c
Heap exhibits the property of a binary tree?
a) True
b) False
Answer: a
What is the complexity of adding an element to the heap.
a) O(log n)
b) O(h)
c) O(log n) & O(h)
d) None of the mentioned
Answer: c
The worst case complexity of deleting any arbitrary node
value element from heap is
a) O(logn)
b) O(n)
c) O(nlogn)
d) O(n2)
Answer: a
Heap can be used as ________________
a) Priority queue
b) Stack
c) A decreasing order array
d) None of the mentioned
Answer: a
An array consist of n elements. We want to create a heap
using the elements. The time complexity of building a heap will be in order of
a) O(n*n*logn)
b) O(n*logn)
c) O(n*n)
d) O(n *logn
*logn)
Answer: b
Binary Heap
What is the space complexity of searching in a heap?
a) O(logn)
b) O(n)
c) O(1)
d) O(nlogn)
Answer: b
What is the best case complexity in builading a heap?
a) O(nlogn)
b) O(n2)
c) O(n*longn *logn)
d) O(n)
Answer: d
Given the code ,choose the correct option that is
consistent with the code
build(A,i)
left->
2*i
right->2*i
+1
temp-
> i
if(left<=
heap_length[A] ans A[left] >A[temp])
temp
-> left
if
(right = heap_length[A] and A[right] > A[temp])
temp->right
if
temp!= i
swap(A[i],A[temp])
build(A,temp)
Here A is the heap
a) It is the build function of max heap
b) It is the build function of min heap
c) It is general build function of any heap
d) None of the mentioned
Answer: a
What is the location of parent node for any arbitary node
i?
a) (i/2) position
b) (i+1)/ position
c) floor(i/2) position
d) ceil(i/2) position
Answer: c
State the complexity of algorithm gien below
int
function(vector<int> arr)
int
len=arr.length();
if(len==0)
return;
temp=arr[len-1];
arr.pop_back();
return
temp;
a) o(n)
b) O(logn)
c) O(1)
d) O(n logn)
Answer: c
Given an array of element 5,7,9,1,3,10,8,4. Tick all the
correct sequences of elements after inserting all the elements in a min-heap.
a) 1,3,4,7,8,9,10
b) 1,4,3,8,9,5,7,10
c) 1,3,4,5,8,7,9,10
d) None of the mentioned
Answer: a
Hash Tables
What is a hash table?
a) A structure that maps values to keys
b) A structure that maps keys to values
c) A structure used for storage
d) A structure used to implement stack and queue
Answer: b
Explanation: A hash table is used to implement
associative arrays which has a key-value pair, so the has table maps keys to
values.
If several elements are competing for the same bucket in
the hash table, what is it called?
a) Diffusion
b) Replication
c) Collision
d) None of the mentioned
Answer: c
Explanation: None.
What is direct addressing?
a) Distinct array position for every possible key
b) Fewer array positions than keys
c) Fewer keys than array positions
d) None of the mentioned
Answer: a
Explanation: Direct addressing is possible only when we
can afford to allocate an array that has one position for every possible key.
What is the search complexity in direct addressing?
a) O(n)
b) O(logn)
c) O(nlogn)
d) O(1)
Answer: d
Explanation: Since every key has a unique array position,
searching takes a constant time.
What is a hash function?
a) A function has allocated memory to keys
b) A function that computes the location of the key in
the array
c) A function that creates an array
d) None of the mentioned
Answer: b
What can be the techniques to avoid collision?
a) Make the hash function appear random
b) Use the chaining method
c) Use uniform hashing
d) All of the mentioned
Answer: d
What is the load factor?
a) Average array size
b) Average key size
c) Average chain length
d) None of the mentioned
Answer: c
What is simple uniform hashing?
a) Every element has equal probability of hashing into
any of the slots
b) A weighted probabilistic method is used to hash
elements into the slots
c) All of the mentioned
d) None of the mentioned
Answer: a
In simple uniform hashing, what is the search complexity?
a) O(n)
b) O(logn)
c) O(nlogn)
d) O(1)
Answer: d
In simple chaining, what data structure is appropriate?
a) Singly linked list
b) Doubly linked list
c) Circular linked list
d) Binary trees
Answer: b
Hash Tables with Linear
Probing
Which of the following problems occur due to linear
probing?
a) Primary collision
b) Secondary collision
c) Separate chaining
d) Extendible hashing
Answer: a
How many probes are required on average for insertion and
successful search?
a) 4 and 10
b) 2 and 6
c) 2.5 and 1.5
d) 3.5 and 1.5
Answer: c
What is the load factor for an open addressing technique?
a) 1
b) 0.5
c) 1.5
d) 0
Answer: b
Which of the following is not a collision resolution
strategy for open addressing?
a) Linear probing
b) Quadratic probing
c) Double hashing
d) Rehashing
Answer: d
In linear probing, the cost of an unsuccessful search can
be used to compute the average cost of a successful search.
a) True
b) False
Answer: a
Which of the following is the correct function definition
for linear probing?
a) F(i)= 1
b) F(i)=i
c) F(i)=i2
d) F(i)=i+1
Answer: b
___________ is not
a theoretical problem but actually occurs in real implementations of probing.
a) Hashing
b) Clustering
c) Rehashing
d) Collision
Answer: b
What is the hash function used in linear probing?
a) H(x)= key mod table size
b) H(x)= (key+ F(i2)) mod table size
c) H(x)= (key+ F(i)) mod table size
d) H(x)= X mod 17
Answer: c
Explanation: The hash function used in linear probing is
defined to be H(x)= (key+ F(i)) mod table size where i=0,1,2,3,…,n.
Hashing can be used in online spelling checkers.
a) True
b) False
Answer: a
Explanation: Initially, collision occurs while hashing 49
for the first time.
Hence, after setting f(i)=1, the hashed location is found
to be 0.
What is the formula to find the expected number of probes
for an unsuccessful search in linear probing?
a) ½(1+1/(1-⅄))
b) ½(1+1/(1-⅄)2)
c) ½(1+1/(1+⅄))
d) ½(1+1/(1+⅄)(1-⅄))
Answer: a
Hash Tables with Quadratic Probing
Which of the following schemes does quadratic probing
come under?
a) rehashing
b) extended hashing
c) separate chaining
d) open addressing
Answer: d
Quadratic probing overcomes primary collision.
a) True
b) False
Answer: a
What kind of deletion is implemented by hashing using
open addressing?
a) active deletion
b) standard deletion
c) lazy deletion
d) no deletion
Answer: c
In quadratic
probing, if the table size is prime, a new element cannot be inserted if the
table is half full.
a) True
b) False
Answer: b
Which of the following is the correct function definition
for quadratic probing?
a) F(i)=i2
b) F(i)=i
c) F(i)=i+1
d) F(i)=i2+1
Answer: a
How many
constraints are to be met to successfully implement quadratic probing?
a) 1
b) 2
c) 3
d) 4
Answer: b
Which among the
following is the best technique to handle collision?
a) Quadratic probing
b) Linear probing
c) Double hashing
d) Separate chaining
Answer: a
Which of the following techniques offer better cache
performance?
a) Quadratic probing
b) Linear probing
c) Double hashing
d) Rehashing
What is the formula used in quadratic probing?
a) Hash key = key mod table size
b) Hash key=(hash(x)+F(i)) mod table size
c) Hash key=(hash(x)+F(i2)) mod table size
d) H(x) = x mod 17
Answer: c
Hashing Functions
Which scheme uses a randomization approach?
a) hashing by division
b) hashing by multiplication
c) universal hashing
d) open addressing
Answer: c
Which hash function satisfies the condition of simple
uniform hashing?
a) h(k) = lowerbound(km)
b) h(k)= upperbound(mk)
c) h(k)= lowerbound(k)
d) h(k)= upperbound(k)
Answer: a
A good hash approach is to derive the hash value that is
expected to be dependent of any patterns that might exist in the data.
a) True
b) False
Answer: b
Explanation: A hash value is expected to be unrelated or
independent of any patterns in the distribution of keys.
Interpret the given character string as an integer
expressed in suitable radix notation.
Character string = pt
a) 14963
b) 14392
c) 12784
d) 14452
Answer: d
What is the hash function used in the division method?
a) h(k) = k/m
b) h(k) = k mod m
c) h(k) = m/k
d) h(k) = m mod k
Answer: b
Explanation: In division method for creating hash
functions, k keys are mapped into one of m slots by taking the reminder of k
divided by m.
6. What can be the value of m in the division method?
a) Any prime number
b) Any even number
c) 2p – 1
d) 2p
Answer: a
Which scheme provides good performance?
a) open addressing
b) universal hashing
c) hashing by division
d) hashing by multiplication
Answer: b
Using division method, in a given hash table of size 157,
the key of value 172 be placed at position ____
a) 19
b) 72
c) 15
d) 17
Answer: c
Explanation: The key 172 can be placed at position 15 by
using the formula
H(k) = k mod m
H(k) = 172 mod 157
H(k) = 15.
How many steps are involved in creating a hash function
using a multiplication method?
a) 1
b) 4
c) 3
d) 2
Answer: d
What is the hash function used in multiplication method?
a) h(k) = floor( m(kA mod 1))
b) h(k) = ceil( m(kA mod 1))
c) h(k) = floor(kA mod m)
d) h(k) = ceil( kA mod m)
Answer: a
What is the advantage of the multiplication method?
a) only 2 steps are involved
b) using constant
c) value of m not critical
d) simple multiplication
Answer: c
What is the table size when the value of p is 7 in
multiplication method of creating hash functions?
a) 14
b) 128
c) 49
d) 127
Answer: b
Explanation: In multiplication method of creating hash
functions the table size can be taken in integral powers of 2.
m = 2p
m= 27
m = 128.
What is the value of h(k) for the key 123456?
Given: p=14, s=2654435769, w=32
a) 123
b) 456
c) 70
d) 67
Answer: d
Explanation: A = s/2w
A = 2654435769/ 232
k.A = 123456 * (2654435769/ 232)
= (76300 * 232) + 17612864
Hence r1= 76300; r0=17612864
Since w=14 the 14 most significant bits of r0 yield the value
of h(k) as 67.
What is the average retrieval time when n keys hash to
the same slot?
a) Theta(n)
b) Theta(n2)
c) Theta(nlog n)
d) Big-Oh(n2)
Answer: a
Collisions can be reduced by choosing a hash function
randomly in a way that is independent of the keys that are actually to be
stored.
a) True
b) False
Answer: a
Double Hashing
Double hashing is one of the best methods available for
open addressing.
a) True
b) False
Answer: a
What is the hash function used in Double Hashing?
a) (h1(k) – i*h2(k))mod m
b) h1(k) + h2(k)
c) (h1(k) + i*h2(k))mod m
d) (h1(k) + h2(k))mod m
Answer: c
Explanation: Double hashing uses a hash function of the
form (h1(k) + i*h2(k))mod m where h1 and h2 are auxiliary hash functions and m
is the size of the hash table.
3. On what value does the probe sequence depend on?
a) c1
b) k
c) c2
d) m
Answer: b
Explanation: The probe sequence depends in upon the key k
since the initial probe position, the offset or both may vary.
The value of h2(k) can be composite relatively to the
hash table size m.
a) True
b) False
Answer: b
What are the
values of h1(k) and h2(k) in the hash function?
a)
h1(k) = m mod k
h2(k) = 1+ (m’ mod k)
b)
h1(k) = 1 + (m mod k)
h2(k) = m’ mod k
c)
h1(k) = 1+ (k mod m)
h2(k) = k mod m
d)
h1(k) = k mod m
h2(k) = 1+ (k mod m’)
Answer: d
What is the running time of double hashing?
a) Theta(m)
b) Theta(m2)
c) Theta(m log k)
d) Theta(m3)
View Answer
Answer: a
Explanation: The running time of double hashing is
Theta(m) since each possible (h1(k), h2(k)) pair yields a distinct probe
sequence. Hence the performance of double hashing is better.
7. Which technique has the greatest number of probe
sequences?
a) Linear probing
b) Quadratic probing
c) Double hashing
d) Closed hashing
Answer: c
At what position the number 72 gets inserted in the
following table?
Index Key
0 22
1 34
2
3
4
5 56
6
7 18
8 41
9
10
a) 3
b) 10
c) 4
d) 6
Answer: d
Explanation: The number 72 must be inserted at index 6.
H(k)=k mod m
H(72)= 72 mod 11
H(72)= 6.
Where does the number 14 get inserted in the following
table?
Index Key
0
1 79
2
3
4 69
5 98
6
7 72
8
9
10
11 50
12
a) 2
b) 9
c) 4
d) 8
What is the value of m’ if the value of m is 19?
a) 11
b) 18
c) 17
d) 15
Answer: C
Graph
Which of the following statements for a simple graph is
correct?
a) Every path is a trail
b) Every trail is a path
c) Every trail is a path as well as every path is a trail
d) None of the mentioned
Answer: a
In the given graph identify the cut vertices.
a) B and E
b) C and D
c) A and E
d) C and B
Answer: d
For the given graph(G), which of the following statements
is true?
a) G is a complete graph
b) G is not a connected graph
c) The vertex connectivity of the graph is 2
d) The edge connectivity of the graph is 1
Answer: c
Explanation : After removing vertices B and C, the graph
becomes disconnected.
What is the number of edges present in a complete graph
having n vertices?
a) (n*(n+1))/2
b) (n*(n-1))/2
c) n
d) Information given is insufficient
Answer: b
The given Graph is regular.
a) True
b) False
Answer: a
Explanation: In a regular graph, degrees of all the
vertices are equal. In the given graph the degree of every vertex is 3.
In a simple graph, the number of edges is equal to twice
the sum of the degrees of the vertices.
a) True
b) False
Answer: b
A connected planar graph having 6 vertices, 7 edges
contains _____________ regions.
a) 15
b) 3
c) 1
d) 11
Answer: b
If a simple graph G, contains n vertices and m edges, the
number of edges in the Graph G'(Complement of G) is ___________
a) (n*n-n-2*m)/2
b) (n*n+n+2*m)/2
c) (n*n-n-2*m)/2
d) (n*n-n+2*m)/2
Answer: a
Which of the following properties does a simple graph not
hold?
a) Must be connected
b) Must be unweighted
c) Must have no loops or multiple edges
d) All of the mentioned
Answer: a
What is the maximum number of edges in a bipartite graph
having 10 vertices?
a) 24
b) 21
c) 25
d) 16
Answer: c
Total number of edges would be n*(10-n), differentiating
with respect to n, would yield the answer.
Which of the following is true?
a) A graph may contain no edges and many vertices
b) A graph may contain many edges and no vertices
c) A graph may contain no edges and no vertices
d) None of the mentioned
Answer: b
For a given graph G having v vertices and e edges which
is connected and has no cycles, which of the following statements is true?
a) v=e
b) v = e+1
c) v + 1 = e
d) None of the mentioned
Answer: b
For which of the following combinations of the degrees of
vertices would the connected graph be eulerian?
a) 1,2,3
b) 2,3,4
c) 2,4,5
d) 1,3,5
Answer: a
A graph with all vertices having equal degree is known as
a __________
a) Multi Graph
b) Regular Graph
c) Simple Graph
d) Complete Graph
Answer: b
Which of the following ways can be used to represent a
graph?
a) Adjacency List and Adjacency Matrix
b) Incidence Matrix
c) Adjacency List, Adjacency Matrix as well as Incidence
Matrix
d) None of the mentioned
Answer: c
Directed Acyclic Graph
Every Directed Acyclic Graph has at least one sink
vertex.
a) True
b) False
Answer: a
Which of the following is a topological sorting of the
given graph?
data-structure-questions-answers-directed-acyclic-graph-q2
a) A B C D E F
b) A B F E D C
c) A B E C F D
d) All of the Mentioned
Answer: d
With V(greater than 1) vertices, how many edges at most
can a Directed Acyclic Graph possess?
a) (V*(V-1))/2
b) (V*(V+1))/2
c) (V+1)C2
d) (V-1)C2
Answer: a
The topological sorting of any DAG can be done in
________ time.
a) cubic
b) quadratic
c) linear
d) logarithmic
Answer: c
If there are more than 1 topological sorting of a DAG is
possible, which of the following is true.
a) Many Hamiltonian paths are possible
b) No Hamiltonian path is possible
c) Exactly 1 Hamiltonian path is possible
d) Given information is insufficient to comment anything
Answer: b
What sequence would the BFS traversal of the given graph
yield?
a) A F D B C E
b) C B A F D
c) A B D C F
d) F D C B A
Answer: c
What would be the output of the following C++ program if
the given input is
0 0 0 1 1
0 0 0 0 1
0 0 0 1 0
1 0 1 0 0
1 1 0 0 0
#include <bits/stdc++.h>
using namespace std;
bool visited[5];
int G[5][5];
void fun(int i)
{
cout<<i<<"
";
visited[i]=true;
for(int
j=0;j<5;j++)
if(!visited[j]&&G[i][j]==1)
fun(j);
}
int main()
{
for(int
i=0;i<5;i++)
for(int
j=0;j<5;j++)
cin>>G[i][j];
for(int
i=0;i<5;i++)
visited[i]=0;
fun(0);
return
0;
}
a) 0 2 3 1 4
b) 0 3 2 4 1
c) 0 2 3 4 1
d) 0 3 2 1 4
Answer: b
Which of the given statement is true?
a) All the Cyclic Directed Graphs have topological
sortings
b) All the Acyclic Directed Graphs have topological
sortings
c) All Directed Graphs have topological sortings
d) None of the given statements is true
Answer: a
For any two different vertices u and v of an Acyclic
Directed Graph if v is reachable from u, u is also reachable from v?
a) True
b) False
Answer: b
What is the value of the sum of the minimum in-degree and
maximum out-degree of an Directed Acyclic Graph?
a) Depends on a Graph
b) Will always be zero
c) Will always be greater than zero
d) May be zero or greater than zero
Answer: b
Undirected Graph
The number of possible undirected graphs which may have
self loops but no multiple edges and have n vertices is ________
a) 2((n*(n-1))/2)
b) 2((n*(n+1))/2)
c) 2((n-1)*(n-1))/2)
d) 2((n*n)/2)
Answer: d
Given a plane graph, G having 2 connected component,
having 6 vertices, 7 edges and 4 regions. What will be the number of connected
components?
a) 1
b) 2
c) 3
d) 4
Answer: b
Number of vertices with odd degrees in a graph having a
eulerian walk is ________
a) 0
b) Can’t be predicted
c) 2
d) either 0 or 2
Answer: d
How many of the following statements are correct?
i) All cyclic graphs are complete graphs.
ii) All complete graphs are cyclic graphs.
iii) All paths are bipartite.
iv) All cyclic graphs are bipartite.
v) There are cyclic graphs which are complete.
a) 1
b) 2
c) 3
d) 4
Answer: b
All paths and cyclic graphs are bipartite graphs.
a) True
b) False
Answer: b
What is the number of vertices of degree 2 in a path
graph having n vertices,here n>2.
a) n-2
b) n
c) 2
d) 0
Answer: a
All trees with n vertices consists of n-1 edges.
a) True
b) False
Answer: a
Which of the following graphs are isomorphic to each
other?
a) fig 1 and fig 2
b) fig 2 and fig 3
c) fig 1 and fig 3
d) fig 1, fig 2 and fig 3
Answer: d
In the given graph which edge should be removed to make
it a Bipartite Graph?
a) A-C
b) B-E
c) C-D
d) D-E
Answer: a
What would the time complexity to check if an undirected
graph with V vertices and E edges is Bipartite or not given its adjacency
matrix?
a) O(E*E)
b) O(V*V)
c) O(E)
d) O(V)
Answer: b
Adjacency List
Space complexity for an adjacency list of an undirected
graph having large values of V (vertices) and E (edges) is ___________
a) O(E)
b) O(V*V)
c) O(E+V)
d) O(V)
Answer: c
For some sparse graph an adjacency list is more space
efficient against an adjacency matrix.
a) True
b) False
Time complexity to find if there is an edge between 2
particular vertices is _________
a) O(V)
b) O(E)
c) O(1)
d) O(V+E)
Answer: a
For the given conditions, which of the following is in
the correct order of increasing space requirement?
i) Undirected, no weight
ii) Directed, no weight
iii) Directed, weighted
iv) Undirected, weighted
a) ii iii i iv
b) i iii ii iv
c) iv iii i ii
d) i ii iii iv
Answer: a
Space complexity for an adjacency list of an undirected
graph having large values of V (vertices) and E (edges) is __________
a) O(V)
b) O(E*E)
c) O(E)
d) O(E+V)
Answer: c
Explanation: In an adjacency list for every vertex there
is a linked list which have the values of the edges to which it is connected.
Complete the given snippet of code for the adjacency list
representation of a weighted directed graph.
class
neighbor
{
int
vertex, weight;
____
next;
}
class
vertex
{
string
name;
_____
adjlist;
}
vertex
adjlists[101];
a) vertex, vertex
b) neighbor, vertex
c) neighbor, neighbor
d) vertex, neighbor
Answer: c
In which case adjacency list is preferred in front of an
adjacency matrix?
a) Dense graph
b) Sparse graph
c) Adjacency list is always preferred
d) None of the mentioned
Answer: b
To create an adjacency list C++’s map container can be
used.
a) True
b) False
Answer: a
What would be the time complexity of the following
function which adds an edge between two vertices i and j, with some weight
‘weigh’ to the graph having V vertices?
vector<int> adjacent[15] ;
vector<int> weight[15];
void addEdge(int i,int j,int weigh)
{
adjacent[a].push_back(i);
adjacent[b].push_back(j);
weight[a].push_back(weigh);
weight[b].push_back(weigh);
}
a) O(1)
b) O(V)
c) O(V*V)
d) O(log V)
Answer: a
What would be the time complexity of the BFS traversal of
a graph with n vertices and n1.25 edges?
a) O(n)
b) O(n1.25)
c) O(n2.25)
d) O(n*n)
Answer: b
Adjacency Matrix
The number of elements in the adjacency matrix of a graph
having 7 vertices is __________
a) 7
b) 14
c) 36
d) 49
Answer: d
What would be the number of zeros in the adjacency matrix
of the given graph?
a) 10
b) 6
c) 16
d) 0
Answer: b
Adjacency matrix of all graphs are symmetric.
a) False
b) True
Answer: a
The time complexity to calculate the number of edges in a
graph whose information in stored in form of an adjacency matrix is
____________
a) O(V)
b) O(E2)
c) O(E)
d) O(V2)
Answer: d
For the adjacency matrix of a directed graph the row sum
is the _________ degree and the column sum is the ________ degree.
a) in, out
b) out, in
c) in, total
d) total, out
Answer: b
What is the maximum number of possible non zero values in
an adjacency matrix of a simple graph with n vertices?
a) (n*(n-1))/2
b) (n*(n+1))/2
c) n*(n-1)
d) n*(n+1)
Answer: c
On which of the following statements does the time
complexity of checking if an edge exists between two particular vertices is
not, depends?
a) Depends on the number of edges
b) Depends on the number of vertices
c) Is independent of both the number of edges and
vertices
d) It depends on both the number of edges and vertices
Answer: c
In the given connected graph G, what is the value of
rad(G) and diam(G)?
a) 2, 3
b) 3, 2
c) 2, 2
d) 3, 3
Answer: a
Which of these adjacency matrices represents a simple
graph?
a) [ [1, 0, 0], [0, 1, 0], [0, 1, 1] ]
b) [ [1, 1, 1], [1, 1, 1], [1, 1, 1] ]
c) [ [0, 0, 1], [0, 0, 0], [0, 0, 1] ]
d) [ [0, 0, 1], [1, 0, 1], [1, 0, 0] ]
Answer: d
Given an adjacency matrix A = [ [0, 1, 1], [1, 0, 1], [1,
1, 0] ], how many ways are there in which a vertex can walk to itself using 2
edges.
a) 2
b) 4
c) 6
d) 8
Answer: c
If A[x+3][y+5] represents an adjacency matrix, which of
these could be the value of x and y.
a) x=5, y=3
b) x=3, y=5
c) x=3, y=3
d) x=5, y=5
Answer: a
0 মন্তব্যসমূহ