Data structure - mcq questions
Data Structures (Pondicherry University)
Scan to open on Studocu
Studocu is not sponsored or endorsed by any college or university
OBJECTIVE TYPE QUESTIONS
Subject : Data Structures and Algorithm Group:B.Tech
Q1. A binary tree of depth “d” is an almost complete binary tree if
Each leaf in the tree is either at level “d” or at level “d–1”
For any node “n” in the tree with a right descendent at level “d” all the left descendents of
“n” that are leaves, are also at level “d”
Both (A) &
Q2. A linear collection of data elements where the linear node is given by means of pointer
is called
linked list (B) node list
Q3. Representation of data structure in memory is known as:
(A) recursive (B) abstract data type
Q4. If the address of A[1][1] and A[2][1] are 1000 and 1010 respectively and each element
occupies 2 bytes then the array has been stored in order.
(A) row major (B) column major (C)
Q5. An adjacency matrix representation of a graph cannot contain information of : (A) nodes
(B) edges
direction of edges (D) parallel edges
Q6. Quick sort is also known as
merge sort (B) heap sort
(C) bubble sort (D) none of these
Q7. An ADT is defined to be a mathematical model of a user-defined type along with the
collection of all operations on that model.
(A) Cardinality (B) Assignment
(C) Primitive (D) Structured
Q8. An algorithm is made up of two independent time complexities f (n) and g (n).
Then the complexities of the algorithm is in the order of
(A) f(n) x g(n) (B) Max ( f(n),g(n))
(C) Min (f(n),g(n)) (D) f(n) + g(n)
Q9. The goal of hashing is to produce a search that takes
(A) O(1) time (B) O(n2 ) time
(C) O(log n ) time (D) O(n log n ) time
Q10. The best average behaviour is shown by
(A) Quick Sort (B) Merge Sort
(C) Insertion Sort (D) Heap Sort
Q11. What is the postfix form of the following prefix *+ab–cd
(A) ab+cd–* (B) abc+*–
(C) ab+*cd– (D) ab+*cd–
Q.12 A queue is a,
(A) FIFO (First In First Out) list. (B) LIFO (Last In First Out) list.
(C) Ordered array. (D) Linear tree.
Q13. Which data structure is needed to convert infix notation to postfix notation?
(A) Branch (B) Queue
(C) Tree (D) Stack
Q14. Which of the following operations is performed more efficiently by doubly linked list
than by singly linked list?
(A) Deleting a node whose location in given
(B) Searching of an unsorted list for a given item
(C) Inverting a node after the node with given location
Q15. The extra key inserted at the end of the array is called a,
(A) End key. (B) Stop key.
(C) Sentinel. (D) Transposition.
Q16. Consider that n elements are to be sorted. What is the worst case time complexity of
Bubble sort?
(A) O(1) (B) O(log2n)
(C) O(n) (D) O(n2)
Q17. A characteristic of the data that binary search uses but the linear search ignores is the .
(A) Order of the elements of the list. (B) Length of the list.
(C) Maximum value in list.
(D) Type of elements of the list.
Q18. 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 above.
Q19. The largest element of an array index is called its
(A) lower bound. (B) range.
(C) upper bound. (D) All of these.
Q20.What is the result of the following operation Top (Push (S, X))
(A) X (B) null
S (D) None of these.
Which of the following algorithm solves the all pair shortest path problem ?
Dijkstra's algorithm
Floyd's algorithm
Prim's algorithm
Warshall's algorithm
Explanation: The Floyd–Warshall algorithm (also known as Floyd's algorithm, Roy–
Warshall algorithm, Roy–Floyd algorithm, or the WFI algorithm) is a graph analysis
algorithm for finding shortest paths in a weighted graph (with positive or negative edge
weights) and also for finding transitive closure of a relation R. –
As part of maintenance work, you are entrusted with the work of rearranging the library
books in a shelf in proper order, at the end of each day. The ideal choice will be ?
Bubble sort
Insertion sort
Selection sort
8) The way a card game player arranges his cards as he picks them up one by one, is an
example of ?
bubble sort
selection sort
insertion sort
merge sort
Explanation: He scans throught the rest of the cards and pick the one with least value and
places it next to the point till which he has already sorted the cards
The average successful search time for sequential search on 'n' items is ?
n/2
(n - 1)/2
(n + 2)/2
log(n) + 1 Show/Hide Answer
If the sequence of operations - push(1), push(2), pop, push(1), push(2), pop, pop, pop,
push(2), pop are performed on a stack, the sequence of popped out values are ?
2, 2, 1, 1, 2
2, 2, 1, 2, 2
2, 1, 2, 2, 1
2, 1, 2, 2, 2
Show/Hide Answer
Explanation: The elements are popped from the top of the stack.
See more at: choice.html#sthash.r4P5Qd6T.dpuf
Sparse matrices have ?
many zero entries
many non- zero entries
higher dimension
none of above Show/Hide Answer
See more at: choice.html#sthash.KRCZRhXN.dpuf
What is Data Structure ?
Way to organize data
Accessing of data elements in specified manner
Organization of mathematical and logical concepts
All of Above Show/Hide Answer
Explanation:A Data Structure may be organized in different ways : The logical or
mathematical model of a particular organization of data is called Data Structure.
Which operation is not possible on Data Structure ?
Traversing
Insertion
Reading
Deletion Show/Hide Answer
Explanation:Possible operations on the Data Structure are Traversing, Insertion, Searching
and Deletion.
The memory address of the first element is called ?
Floor Address
Foundation Address
First Address
Base Address Show/Hide Answer
Explanation:The memory address of the first element is often called base address in Data
Structure.
The value of first linked list address is ?
0
-1
None of Above Show/Hide Answer
Explanation: No explanation for this question.
Two dimensional arrays are also called ?
Matrix Array
Table Array
Both a and b
None of the Above Show/Hide Answer
Explanation:Two dimensional arrays are called as matrix array and table arrays because
they contains rows and columns.
The situation in linked list START=NULL is called ?
Overflow
Underflow
Both of above
None of Above Show/Hide Answer
Explanation:It is the situation when we are trying to delete an item from the empty linked
list.
Length of the linear array can be found by using the formula ?
UB - LB + 1
LB + UB
LB - UB
LB - UB + 1
Show/Hide Answer
Explanation:The length of linear array can be found by using UB - LB + 1 Where UB is upper
Bound, LB is Lower Bound of the array.
The restriction while using the binary search is ?
List should be small in number
List should be large in number
List should be sorted
No restriction Show/Hide Answer
Explanation: Binary search can be applied to a list only if the list is either in ascending or
descending order.
The terms PUSH and POP are related to ?
Arrays
Stacks
Linked List
None Show/Hide Answer
Explanation:PUSH is used for inserting an element into the stack and POP is used for
deleting an elements from the stack.
The operation of processing element is called ?
Traversing
Inserting
Deleting
Searching
Show/Hide Answer
Explanation:Traversing means visiting or processing each element exactly once.
Which of the following is not the type of queue?
Ordinary queue
Single ended queue
Circular queue
Priority queue
The property of binary tree is
The first subset is called left subtree
The second subtree is called right subtree
The root cannot contain NULL
The right subtree can be empty
State true or false.
The degree of root node is always zero.
Nodes that are not root and not leaf are called as internal nodes.
True, True
True, False
False, True
False, False
Any node is the path from the root to the node is called
Successor node
Ancestor node
Internal node
None of the above
State true of false.
A node is a parent if it has successor nodes.
A node is child node if out degree is one.
True, True
True, False
False, True
False, False
6 is not an operation performed on linear list
Insertion b) Deletion c) Retrieval d) Traversal
only a,b and c
only a and b
All of the above
None of the above
Which is/are the application(s) of stack
Function calls
Large number Arithmetic
Evaluation of arithmetic expressions
All of the above
A is an acyclic digraph, which has only one node with indegree 0, and other nodes
have indegree 1.
Directed tree
Undirected tree
Dis-joint tree
Direction oriented tree
9 Is a directed tree in which outdegree of each node is less than or equal to two.
Unary tree
Binary tree
Dinary tree
Both B and C
State true or false.
An empty tree is also a binary tree.
In strictly binary tree, the outdegree of every node is either o or 2.
True, False
False, True
True, True
False, False
A directed graph is if there is a path from each vertex to every other vertex in the
digraph.
Weakly connected
Strongly Connected
Tightly Connected
Linearly Connected
In the traversal we process all of a vertex’s descendents before we move to an
adjacent vertex.
Depth First
Breadth First
With First
Depth Limited
State True of False.
Network is a graph that has weights or costs associated with it.
An undirected graph which contains no cycles is called a forest.
A graph is said to be complete if there is no edge between every pair of vertices.
True, False, True
True, True, False
True, True, True
False, True, True
Match the following.
Completeness i) How long does it take to find a solution
Time Complexity ii) How much memory need to perform the search.
Space Complexity iii) Is the strategy guaranteed to find the solution when there in one.
a-iii, b-ii, c-i
a-i, b-ii, c-iii
a-iii, b-i, c-ii
a-i, b-iii, c-ii
The number of comparisons done by sequential search is ………………
(N/2)+1
(N+1)/2
(N-1)/2
(N+2)/2
In , search start at the beginning of the list and check every element in the list.
Linear search
Binary search
Hash Search
Binary Tree search
State True or False.
Binary search is used for searching in a sorted array.
The time complexity of binary search is O(logn).
True, False
False, True
False, False
True, True
Which of the following is not the internal sort?
Insertion Sort
Bubble Sort
Merge Sort
Heap Sort
State True or False.
An undirected graph which contains no cycles is called forest.
A graph is said to be complete if there is an edge between every pair of vertices.
True, True
False, True
False, False
True, False
A graph is said to be if the vertices can be split into two sets V1 and V2 such
there are no edges between two vertices of V1 or two vertices of V2.
Partite
Bipartite
Rooted
Bisects
In a queue, the initial values of front pointer f rare pointer r should be …….. and ………..
respectively.
0 and 1
0 and -1
-1 and 0
1 and 0
In a circular queue the value of r will be ..
r=r+1
r=(r+1)% [QUEUE_SIZE – 1]
r=(r+1)% QUEUE_SIZE
r=(r-1)% QUEUE_SIZE
Which of the following statement is true?
Using singly linked lists and circular list, it is not possible to traverse the list backwards.
To find the predecessor, it is required to traverse the list from the first node in case of singly
linked list.
i-only
ii-only
Both i and ii
None of both
The advantage of is that they solve the problem if sequential storage
representation. But disadvantage in that is they are sequential lists.
Lists
Linked Lists
Trees
Queues
What will be the value of top, if there is a size of stack STACK_SIZE is 5
None
is not the operation that can be performed on queue.
Insertion
Deletion
Retrieval
Traversal
There is an extra element at the head of the list called a ……….
Antinel
Sentinel
List header
List head
A graph is a collection of nodes, called ………. And line segments called arcs or that
connect pair of nodes.
vertices, edges
edges, vertices
vertices, paths
graph node, edges
A is
Network
Weighted graph
Both A and B
None A and B
In general, the binary search method needs no more than comparisons.
[log2n]-1
[logn]+1
[log2n]
[log2n]+1