UNIT1 :
Basic Concept and Introduction to Data structure
1. The word ____________comes from the name of a
Persian mathematician Abu Ja’far Mohammed ibn-i Musa al Khowarizmi.
a) Flowchart
b) Flow
c) Algorithm
d) Syntax
Answer: c
2. In computer science, algorithm refers to a
special method usable by a computer for the solution to a problem.
a) True
b) False
c. Maybe
d. None of the above
Answer: a
3. Which of the following is incorrect? Algorithms
can be represented:
a) as pseudo codes
b) as syntax
c) as programs
d) as flowcharts
Answer: b.
4. When an algorithm is written in the form of a
programming language, it becomes a _________
a) Flowchart
b) Program
c) Pseudo code
d) Syntax
Answer: b
5. Any algorithm is a program.
a) True
b) False
c. Maybe
d. None of the above
Answer: b
6. In computer science, algorithm refers to a
pictorial representation of a flowchart.
a) True
b) False
c. Maybe
d. None of the above
Answer: b
7. The process of drawing a flowchart for an algorithm
is called __________
a) Performance
b) Evaluation
c) Algorithmic Representation
d) Flowcharting
Answer: d
8. Which of the following header files must necessarily
be included to use dynamic memory allocation functions?
a) stdlib.h
b) stdio.h
c) memory.h
d) dos.h
Answer: a
9. In the function malloc(), each byte of allocated
space is initialized to zero.
a) True
b) False
c) Maybe
d) None of the above
Answer: b
10. Which of the following functions allocates
multiple blocks of memory, each block of the same size?
a) malloc()
b) realloc()
c) calloc()
d) free()
Answer: c
11. A condition where in memory is reserved
dynamically but not accessible to any of the programs is called _____________
a) Memory leak
b) Dangling pointer
c) Frozen memory
d) Pointer leak
Answer: a
12. The incorrect statement with respect to dangling
pointers is ___________
a) Pointer pointing to non-existent memory location
is called dangling pointer
b) When a dynamically allocated pointer references
the original memory after it has been freed, a dangling pointer arises
c) If memory leak occurs, it is mandatory that a
dangling pointer arises
d) Dangling pointer may result in segmentation
faults and potential security risks
Answer: c
13. In the function realloc(), if the new size of
the memory block is larger than the old size, then the added memory ___________
a) is initialized to junk values
b) is initialized to zero
c) results in an error
d) is not initialized
Answer: d
14. The free() function frees the memory state
pointed to by a pointer and returns ___________
a) the same pointer
b) the memory address
c) no value
d) an integer value
Answer: c
15. The number of arguments taken as input which
allocating memory dynamically using malloc() is ___________
a) 0
b) 1
c) 2
d) 3
Answer: b
16. Suppose we have a one dimensional array, named
‘x’, which contains 10 integers. Which of the following is the correct way to
allocate memory dynamically to the array ‘x’ using malloc()?
a) x=(int*)malloc(10);
b) x=(int*)malloc(10,sizeof(int));
c) x=malloc(int 10,sizeof(int));
d) x=(int*)malloc(10*sizeof(int));
Answer: d
17. If malloc() and calloc() are not type casted,
the default return type is ___________
a) void*
b) void**
c) int*
d) char*
Answer: a
18. When the pointer is NULL, then the function
realloc is equivalent to the function ___________
a) malloc
b) calloc
c) free
d) alloc
Answer: a
19. Garbage collector frees the programmer from
worrying about ___________
a) Dangling pointers
b) Creating new objects
c) Memory leak
d) Segmentation errors
Answer: c
20. If the space in memory allocated by malloc is
not sufficient, then an allocation fails and returns ___________
a) NULL pointer
b) Zero
c) Garbage value
d) The number of bytes available
Answer: a
21.Among 4 header files, which should be included
to use the memory allocation functions like malloc(), calloc(), realloc() and free()?
A. #include<string.h>
B. #include<stdlib.h>
C. #include<memory.h>
D. Both b and c
Ans : B
22.Which of the following is/are true
A. calloc() allocates the memory and also initializes
the allocates memory to zero, while memory allocated using malloc() has random
data.
B. malloc() and memset() can be used to get the
same effect as calloc()
C. Both malloc() and calloc() return 'void *' pointer
D. All of the above
Ans : D
23.Which of the following statement is correct
prototype of the malloc() function in c ?
A. int* malloc(int);
B. Char* malloc(char);
C. unsigned int* malloc(unsigned int);
D. void* malloc(size_t);
Ans : D
24. Specify the 2 library functions to dynamically
allocate memory?
A. malloc() and memalloc()
B. alloc() and memalloc()
C. malloc() and calloc()
D. memalloc() and faralloc()
Ans : C
25.malloc() returns a float pointer if memory is
allocated for storing float's and a double pointer if memory is allocated for storing
double's.
A. TRUE
B. FALSE
C. May Be
D. Can't Say
Ans : B
26.malloc() allocates memory from the heap and not
from the stack.
A. TRUE
B. FALSE
C. May Be
D. Can't Say
Ans : A
27.What is wild pointer?
A. Pointer which is wild in nature
B. Pointer which has no value.
C. Pointer which is not initialized
D. None
Ans : C
28.Address stored in the pointer variable is of
type __________.
A. Integer
B. Float
C. Array
D. Character
Ans : A
29.In order to fetch the address of the variable we
write preceding _________ sign before variable name.
A. Percent(%)
B. Comma(,)
C. Ampersand(&)
D. Asteric(*)
Ans : C
30.Space complexity of an algorithm is the maximum
amount of _______ required by it during execution.
a.Time
b.Operations
c.Memory space
d.None of the above
ANS C
31.Frequently, the memory space required by an
algorithm is a multiple of the size of input. State if the statement is True or
False or Maybe.
a. True
b. False
c. Maybe
d. None of the above
ANS a
32An algorithm performs lesser number of operations
when the size of input is small, but performs more operations when the size of
input gets larger. State if the statement is True or False or Maybe.
a. True
b. False
c. Maybe
d. None of the above
ANS a
33.In the analysis of algorithms, what plays an
important role?
a. Text Analysis
b. Growth factor
c. Time
d. None of the above
ANS b
34 To verify whether a function grows faster or
slower than the other function, we have some asymptotic or mathematical notations,
which is_________.
a. Big Omega Ω (f)
b. Big Theta θ (f)
c. Big Oh O (f)
d. All of the above
ANS d
35. An algorithm that indicates the amount of
temporary storage required for running the algorithm, i.e., the amount of
memory needed by the algorithm to run to completion is termed as_____.
a. Big Theta θ (f)
b. Space complexity
c. Big Oh O (f)
d. None of the above
ANS b
36. The amount of time the computer needs to run to
completion is known as_____.
a. Space complexity
b. Time complexity
c. Recursive function
d. None of the above
ANS b
37. ___________algorithm is one which utilizes
minimum processor time and requires minimum memory space during its execution.
a. Best
b. Efficient
c. Both (a) and (b)
d. None of the above
ANS c
38.What is (void*)0?
A.Representation of NULL pointer
B.Representation of void pointer
C.Error
D.None of above
Answer: A
39.If a variable is a pointer to a structure, then
which of the following operator is used to access data members of the structure
through the pointer variable?
A. .
B. &
C. *
D. ->
Answer: D
40. A pointer is
A. A keyword used to create variables
B. A variable that stores address of an instruction
C. A variable that stores address of other variable
D. All of the above
Answer: C
41.The operator used to get value at address stored
in a pointer variable is
A. *
B. &
C. &&
D. ||
Answer: A
42. Choose the correct option about abstract data
type(ADT).
a. An abstract data type is a model of a certain
kind of data structure.
b. In abstract data type we know what a specific
data type can do, but how it actually does it is hidden.
c. ADT is user defined type.
d. All of the above.
ANSWER: All of the above.
43. Which of these best describes an array?
a) A data structure that shows a hierarchical
behaviour
b) Container of objects of similar types
c) Arrays are immutable once initialised
d) Array is not a data structure
Answer: b
44. How do you initialize an array in C?
a) intarr[3] = (1,2,3);
b) intarr(3) = {1,2,3};
c) intarr[3] = {1,2,3};
d) intarr(3) = (1,2,3);
Answer: c
45. How do you instantiate an array in Java?
a) intarr[] = new int(3);
b) intarr[];
c) intarr[] = new int[3];
d) intarr() = new int(3);
Answer: c
46. Which of the following is a correct way to
declare a multidimensional array in Java?
a) int[] arr;
b) intarr[[]];
c) int[][]arr;
d) int[[]] arr;
Answer: c
47. A mathematical-model with a collection of
operations defined on that model is called
A. Data Structure
B. Abstract Data Type
C. Primitive Data Type
D. Algorithm
Answer: b
48. Representation of data structure in memory is
known as:
A. Recursive
B. Abstract data type
C. Storage structure
D. File structure
Answer: b
49. Which of the following abstract data types can
be used to represent a many to many relation?
A. Tree
B. Plex
C. Graph
D. Both (b) and (c)
Answer: d
50. When does the ArrayIndexOutOfBounds Exception
occur?
a) Compile-time
b) Run-time
c) Not an error
d) Not an exception at all
Answer: b
UNIT 2 :
Linear Data structure
1. What is an external sorting algorithm?
a) Algorithm that uses tape or disk during the sort
b) Algorithm that uses main memory during the sort
c) Algorithm that involves swapping
d) Algorithm that are considered ‘in place’
Answer: a
2. What is an internal sorting algorithm?
a) Algorithm that uses tape or disk during the sort
b) Algorithm that uses main memory during the sort
c) Algorithm that involves swapping
d) Algorithm that are considered ‘in place’
Answer: b
3. What is the worst case complexity of bubble
sort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Answer: d
4. What is the average case complexity of bubble
sort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Answer: d
5. Which of the following is not an advantage of
optimised bubble sort over other sorting techniques in case of sorted elements?
a) It is faster
b) Consumes less memory
c) Detects whether the input is already sorted
d) Consumes less time
Answer: c
6. The given array is arr = {1, 2, 4, 3}. Bubble sort
is used to sort the array elements. How many iterations will be done to sort
the array?
a) 4
b) 2
c) 1
d) 0
Answer: a
7. What is the best case efficiency of bubble sort
in the improvised version?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Answer: c
8. The given array is arr = {1,2,4,3}. Bubble sort
is used to sort the array elements. How many iterations will be done to sort
the array with improvised version?
a) 4
b) 2
c) 1
d) 0
Answer: b
9. Merge sort uses which of the following technique
to implement sorting?
a) backtracking
b) greedy algorithm
c) divide and conquer
d) dynamic programming
Answer: c
10. What is the average case time complexity of
merge sort?
a) O(n log n)
b) O(n2)
c) O(n2 log n)
d) O(n log n2)
Answer: a
11. What is the auxiliary space complexity of merge
sort?
a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)
Answer: c
12. Merge sort can be implemented using O(1)
auxiliary space.
a) true
b) false
Answer: a
13. What is the worst case time complexity of merge
sort?
a) O(n log n)
b) O(n2)
c) O(n2 log n)
d) O(n log n2)
Answer: a
14. Which of the following method is used for
sorting in merge sort?
a) merging
b) partitioning
c) selection
d) exchanging
Answer: a
15. What will be the best case time complexity of
merge sort?
a) O(n log n)
b) O(n2)
c) O(n2 log n)
d) O(n log n2)
Answer: a
16. Which of the following is not a variant of
merge sort?
a) in-place merge sort
b) bottom up merge sort
c) top down merge sort
d) linear merge sort
Answer: d
17. Choose the incorrect statement about merge sort
from the following?
a) it is a comparison based sort
b) it is an adaptive algorithm
c) it is not an in place algorithm
d) it is stable algorithm
Answer: b
18. Which of the following is not in place sorting
algorithm?
a) merge sort
b) quick sort
c) heap sort
d) insertion sort
Answer: a
19. Which of the following is not a stable sorting
algorithm?
a) Quick sort
b) Cocktail sort
c) Bubble sort
d) Merge sort
Answer: a
20. Which of the following stable sorting algorithm
takes the least time when applied to an almost sorted array?
a) Quick sort
b) Insertion sort
c) Selection sort
d) Merge sort
Answer: d
21. Merge sort is preferred for arrays over linked
lists.
a) true
b) false
Answer: b
22. Which of the following sorting algorithm makes
use of merge sort?
a) tim sort
b) intro sort
c) bogo sort
d) quick sort
Answer: a
23. Which of the following sorting algorithm does
not use recursion?
a) quick sort
b) merge sort
c) heap sort
d) bottom up merge sort
Answer: d
24.What is the advantage of bubble sort over other
sorting techniques?
a) It is faster
b) Consumes less memory
c) Detects whether the input is already sorted
d) All of the mentioned
Answer: c
25.The given array is arr = {1,2,4,3}. Bubble sort
is used to sort the array elements. How many iterations will be done to sort the
array?
a) 4
b) 2
c) 1
d) 0
Answer: a
26.What is the best case complexity of QuickSort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Answer: a
27.What is the average case complexity of selection
sort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Answer: d
28.What is the disadvantage of selection sort?
a) It requires auxiliary memory
b) It is not scalable
c) It can be used for small keys
d) None of the mentioned
Answer: b
29.What is the worst case complexity of bubble
sort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Answer: d
30.What is the worst case complexity of selection
sort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Answer: d
31.Where is linear searching used?
a) When the list has only a few elements
b) When performing a single search in an unordered
list
c) Used all the time
d) When the list has only a few elements and When
performing a single search in an unordered list
Answer: d
32. What is the best case for linear search?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(1)
Answer: d
33. What is the worst case for linear search?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(1)
Answer: c
34. What is the best case and worst case complexity
of ordered linear search?
a) O(nlogn), O(logn)
b) O(logn), O(nlogn)
c) O(n), O(1)
d) O(1), O(n)
Answer: d
35. Which of the following is a disadvantage of
linear search?
a) Requires more space
b) Greater time complexities compared to other
searching algorithms
c) Not easy to understand
d) Not easy to implement
Answer: b
.
36. Is there any difference in the speed of execution
between linear serach(recursive) vs linear search(lterative)?
a) Both execute at same speed
b) Linear search(recursive) is faster
c) Linear search(Iterative) is faster
d) Cant be said
Answer: c
37. Is the space consumed by the linear search(recursive)
and linear search(iterative) same?
a) No, recursive algorithm consumes more space
b) No, recursive algorithm consumes less space
c) Yes
d) Nothing can be said
Answer: a
38. What is the worst case runtime of linear search(recursive)
algorithm?
a) O(n)
b) O(logn)
c) O(n2)
d) O(nx)
Answer: a
39. Linear search(recursive) algorithm used in
_____________
a) When the size of the dataset is low
b) When the size of the dataset is large
c) When the dataset is unordered
d) Never used
Answer: a
40. The array is as follows: 1,2,3,6,8,10. At what
time the element 6 is found? (By using linear search(recursive) algorithm)
a) 4th call
b) 3rd call
c) 6th call
d) 5th call
Answer: a
41. The array is as follows: 1,2,3,6,8,10. Given
that the number 17 is to be searched. At which call it tells that there’s no
such element? (By using linear search(recursive) algorithm)
a) 7th call
b) 9th call
c) 17th call
d) The function calls itself infinite number of
times
Answer: a
42. What is the best case runtime of linear search(recursive)
algorithm on an ordered set of elements?
a) O(1)
b) O(n)
c) O(logn)
d) O(nx)
Answer: a
43. Can linear search recursive algorithm and
binary search recursive algorithm be performed on an unordered list?
a) Binary search can’t be used
b) Linear search can’t be used
c) Both cannot be used
d) Both can be used
Answer: a
44. What is the recurrence relation for the linear
search recursive algorithm?
a) T(n-2)+c
b) 2T(n-1)+c
c) T(n-1)+c
d) T(n+1)+c
Answer: c
45. What is the advantage of recursive approach
than an iterative approach?
a) Consumes less memory
b) Less code and easy to implement
c) Consumes more memory
d) More code has to be written
Answer: b
46. Given an input arr = {2,5,7,99,899}; key = 899;
What is the level of recursion?
a) 5
b) 2
c) 3
d) 4
Answer: c
47. Given an array arr = {45,77,89,90,94,99,100}
and key = 99; what are the mid values(corresponding array elements) in the
first and second levels of
recursion?
a) 90 and 99
b) 90 and 94
c) 89 and 99
d) 89 and 94
Answer: a
48. What is the worst case complexity of binary
search using recursion?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Answer: b
49. What is the average case time complexity of
binary search using recursion?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Answer: b
50. Which of the following is not an application of
binary search?
a) To find the lower/upper bound in an ordered
sequence
b) Union of intervals
c) Debugging
d) To search in unordered list
Answer: d
51. Binary Search can be categorized into which of
the following?
a) Brute Force technique
b) Divide and conquer
c) Greedy algorithm
d) Dynamic programming
Answer: b
52. Given an array arr = {5,6,77,88,99} and key =
88; How many iterations are done until the element is found?
a) 1
b) 3
c) 4
d) 2
Answer: d
53. Given an array arr = {45,77,89,90,94,99,100}
and key = 100; What are the mid values(corresponding array elements) generated
in the first and second iterations?
a) 90 and 99
b) 90 and 100
c) 89 and 94
d) 94 and 99
Answer: a
54. What is the time complexity of binary search
with iteration?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Answer: b
55. In which of the cases uniform binary search
fails compared to binary search?
a) A table lookup is generally faster than an addition
and a shift
b) Many searches will be performed on the same
array
c) Many searches will be performed on several
arrays of the same length
d) Complexity of code
Answer: d
56. Given delta[4] is a global array and number of
elements in the sorted array is 10, what are the values in the delta array?
a) 4, 3, 1, 0
b) 5, 3, 1, 0
c) 4, 2, 1, 1
d) 5, 2, 1, 1
Answer: b
57. What is the time complexity of uniform binary
search?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Answer: b
58. Given, arr = {1,3,5,6,7,9,14,15,17,19} key = 17
and delta = {5,3,1,0} How many key comparisons are made?(exclude the comparison
used to decide the left or right sub array)
a) 4
b) 3
c) 5
d) 6
Answer: b
59. Which of the following step is taken after
finding an element having value greater than the element being searched?
a) linear search takes place in the forward direction
b) linear search takes place in the backward
direction
c) binary search takes place in the forward direction
d) binary search takes place in a backward direction
Answer: b
60. Which of the following searching algorithm is fastest?
a) jump search
b) binary search
c) linear search
d) all are equally fast
Answer: b
Unit 3 : Linked List
1. 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) Unordered list
2. 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
3. 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
4. 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)
5. What would be the asymptotic time complexity to insert
an element at the front of the linked list (head is known)?
a) O(1)
b) O(n)
c) O(n2)
d) O(n3)
6. 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) O(n4)
7. 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) O(n3)
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
9. 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
10. Linked lists are not suitable to for the implementation
of?
a) Insertion sort
b) Radix sort
c) Polynomial manipulation
d) Binary search
11. Linked list is considered as an example of ___________
type of memory allocation.
a) Dynamic
b) Static
c) Compile time
d) Heap
12. In Linked List implementation, a node carries information
regarding ___________
a) Data
b) Link
c) Data and Link
d) Node
13. Linked list data structure offers considerable
saving in _____________
a) Computational Time
b) Space Utilization
c) Space Utilization and Computational Time
d) Speed Utilization
14. Which of the following points is/are not 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) Access of elements in linked list takes less
time than compared to arrays
15. 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
16. In the worst case, the number of comparisons needed
to search a singly linked list of length n for a given element is
a) log 2 n
b) n ⁄2
c) log 2 n – 1
d) n
17. Given pointer to a node X in a singly linked
list. Only one pointer is given, pointer to head node is not given, can we
delete the node X from given linked list?
a) Possible if X is not last node
b) Possible if size of linked list is even
c) Possible if size of linked list is odd
d) Possible if X is not first node
18. You are given pointers to first and last nodes
of a singly linked list, which of the following operation are dependent on the
length of the linked list?
a) Delete the first element
b) Insert a new element as a first element
c) Delete the last element of the list
d) Add a new element at the end of the list
19. In the worst case, the number of comparisons needed
to search a singly linked list of length n for a given element is
a) log2 n
b) n ⁄2
c) log2 n – 1
d) n
20. Which of the following is not a disadvantage to
the usage of array?
a) Fixed size
b) There are chances of wastage of memory space if elements
inserted in an array are lesser than the allocated size
c) Insertion based on position
d) Accessing elements at specified positions
21. 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)
22. 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) O(n2)
23. 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)
24. 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) Implementing a doubly linked list is easier than
singly linked list
25. 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) A doubly linked list that uses bitwise AND
operator for storing addresses
26. 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
27. What is the worst case time complexity of
inserting a node in a doubly linked list?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(1)
28. 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)Head node is known in circular linked list
29. 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) O(n2)
30. 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) Implement Hash Tables
31. 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) We can traverse the whole circular linked list
by starting from any point
32. 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) Circular linked list itself represents a cycle.
So no new cycles cannot be generated
33. Which of the following real world scenarios
would you associate with a stack data structure?
a) piling up of chairs one above the other
b) people standing in a line to be serviced at a
counter
c) offer services based on the priority of the
customer
d) tatkal Ticket Booking in IRCTC
34. What does ‘stack underflow’ refer to?
a) accessing item from an undefined stack
b) adding items to a full stack
c) removing items from an empty stack
d) index out of bounds exception
35. What is the time complexity of pop() operation
when the stack is implemented using an array?
a) O(1)
b) O(n)
c) O(logn)
d) O(nlogn)
36. Which of the following array position will be occupied
by a new element being pushed for a stack of size N elements(capacity of stack
> N).
a) S[N-1]
b) S[N]
c) S[1]
d) S[0]
37. What happens when you pop from an empty stack while
implementing using the Stack ADT in Java?
a) Undefined error
b) Compiler displays a warning
c) EmptyStackException is thrown
d) NoStackException is thrown
38. Array implementation of Stack is not dynamic,
which of the following statements supports this argument?
a)space allocation for array is fixed and cannot be
changed during run-time
b) user unable to give the input for stack
operations
c) a runtime exception halts execution
d) improper program compilation
39. Which of the following array element will
return the top-of-the-stack-element for a stack of size N elements(capacity of
stack > N).
a) S[N-1]
b)S[N]
c) S[N-2]
d)S[N+1]
40. What is the best case time complexity of
deleting a node in Singly Linked list?
a) O (n)
b) O (n2)
c) O (nlogn)
d) O (1)
41. Which of the following statements are not
correct with respect to Singly Linked List(SLL) and Doubly Linked List(DLL)?
a) Complexity of Insertion and Deletion at known position
is O(n) in SLL and O(1) in DLL
b) SLL uses lesser memory per node than DLL
c) DLL has more searching power than SLL
d) Number of node fields in SLL is more than DLL
42. In linked list implementation of queue, if only
front pointer is maintained, which of the following operation take worst case
linear time?
a) Insertion
b) Deletion
c) To empty a queue
d) Both Insertion and To empty a queue
43. In linked list implementation of a queue, where
does a new element be inserted?
a) At the head of link list
b) At the centre position in the link list
c) At the tail of the link list
d) At any position in the linked list
44. In linked list implementation of a queue, front
and rear pointers are tracked. Which of these pointers will change during an
insertion into a NONEMPTY queue?
a) Only front pointer
b) Only rear pointer
c) Both front and rear pointer
d) No pointer will be changed
45. In linked list implementation of a queue, front
and rear pointers are tracked. Which of these pointers will change during an
insertion into EMPTY queue?
a) Only front pointer
b) Only rear pointer Both front and rear pointer
c) No pointer will be changed
46. In linked list implementation of a queue, from
where is the item deleted?
a) At the head of link list
b)At the centre position in the link list
c) At the tail of the link list
d)Node before the tail
47. In linked list implementation of a queue, the important
condition for a queue to be empty is?
a) FRONT is null
b) REAR is null
c) LINK is empty
d) FRONT==REAR-1
48. The essential condition which is checked before
insertion in a linked queue is?
a) Underflow
b) Overflow
c) Front value
d) Rear value
49. The essential condition which is checked before
deletion in a linked queue is?
a) Underflow
b) Overflow
c) Front value
d) Rear value
50. Which of the following is true about linked
list implementation of queue?
a) In push operation, if new nodes are inserted at
the beginning of linked list, then in pop operation, nodes must be removed from
end
b) In push operation, if new nodes are inserted at
the beginning, then in pop operation, nodes must be removed from the beginning
c) In push operation, if new nodes are inserted at
the end, then in pop operation, nodes must be removed from end
d) In push operation, if new nodes are inserted at
the end, then in pop operation, nodes must be removed from beginning
UNIT 4 : Stack
1. 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) Pop
Answer: d
3. 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
4. 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
5. 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
6. The data structure required to check whether an
expression contains balanced parenthesis is?
a) Stack
b) Queue
c) Array
d) Tree
Answer: a
7. Which data structure is needed to convert infix
notation to postfix notation?
a) Branch
b) Tree
c) Queue
d) Stack
Answer: d
8. Which data structure is used for implementing
recursion?
a) Queue
b) Stack
c) Array
d) List
Answer: b
9. 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
10. The type of expression in which operator
succeeds its operands is?
a) Infix Expression
b) Prefix Expression
c) Postfix Expression
d) Both Prefix and Postfix Expressions
Answer: c
11. If the elements “A”, “B”, “C” and “D” are placed
in a stack and are deleted one at a time, what is the order of removal?
a) ABCD
b) DCBA
c) DCAB
d) ABDC
Answer: b
12. What is the result of the following operation
Top (Push (S, X))
a) X
b) Null
c) S
d) None
ANSWER: a
13. Which data structure is used for implementing
recursion?
a) Queue
b) Stack
c) Array
d) List
ANSWER: b
14. Consider the linked list implementation of a
stack. Which of the following node is considered as Top of the stack?
a) First node
b) Last node
c) Any node
d) Middle node
ANSWER: a
15. Consider the following operation performed on a
stack of size 5. 1) Push(1);2) Pop();3) Push(2);4) Push(3);5) Pop();6)
Push(4);7) Pop();8) Pop();9) Push(5); After the completion of all operation,
the no of element present on stack are
a) 1
b) 2
c) 3
d) 4
ANSWER: a
16. 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
17. Which of the following operation take worst
case linear time in the array implementation of stack?
a) Push
b) Pop
c) IsEmpty
d) None
ANSWER: d
18. The type of expression in which operator
Preceeds its operands is?
a) Infix Expression
b) pre fix Expression
c) postfix Expression
d) None
ANSWER: b
19. Which of the following application generally
use a stack?
a) Parenthesis balancing program
b) Syntax analyzer in compiler
c) Keeping track of local variables at run time
d) All of the above
ANSWER: d
20. What is the minimum number of stacks of size n
required to implement a queue of size n?
a) One
b) Two
c) Three
d) Four
ANSWER: b
21. What will be the initial value with which top
is initialized.
a) 1
b) -1
c) 0
d) Garbage
ANSWER: d
22.Which of the following is true about linked list
implementation of stack?
a) In push operation, if new nodes are inserted at
the beginning of linked list, then in pop
b) operation, nodes must be removed from end. In
push operation, if new nodes are inserted at the end, then in pop operation,
nodes must be removed from the beginning.
c) Both of the above
d) None of the above
ANSWER :d
23.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
24.Other names for the insertion and deletion
operations in Stacks?
a) PUSH – insertion, POP –Deletion.
b) PUSH – Deletion, POP – Insertion.
c) Both A and B are valid.
d) Only A is true.
Answer: d
25.In stacks, the possibility to do insertion and
deletion is ____
a) At one end only
b) at both ends
c) Both A & B.
d) None
Answer: a
26. Pick from the following which represents an
element in a stack.
a) SIZE
b) ITEM
c) TOP
d) BOTTOM
Answer: b
27. At which position in the stacks , the operations
are being done.
a) TOP
b) SIZE
c) POP
d) PUSH
Answer: a
28. It is impossible to do ___ operation on empty
stack.
a) PUSH
b) POP
c) STATUS
d) None
Answer: b
29. From the following which are static and dynamic
representations of stacks?
a) Arrays – Static, Linked lists – Dynamic.
b) Linked lists – Static, Arrays – Dynamic.
c) Queues –Dynamic ,Arrays – Static
d) None of the mentioned.
Answer: a
30. Pick out the odd one which is not related to
stacks.
a) LIFO list
b) FIFO list
c) Push down lists.
d) Piles
Answer: b
31. Can we delete a node at front of a stack
by using POP operation?
a) YES
b) NO
Answer: a
40.Is there possibility to add a node at front of
the stacks without PUSH operation.
a) YES
b) NO
Answer: b
32.The concept “Pile of Plates” is applicable in
which one of the following.
a) Stack
b) Queue
c) Linked list
d) Tree
Answer: a
33) In liked representation of stack ……. holds the
elements of the stack.
a) INFO fields
b) TOP fields
c) LINK fields
d) NULL fields
Answer: a
34) In the linked representation of the stack ………
behaves as the top pointer variable of stack.
a) Stop pointer
b) Begin pointer
c) Start pointer
d) Avail pointer
Answer: c
35) In linked representation of stack the null pointer
of the last node in the list signals ……….
a) Beginning of the stack
b) Bottom of the stack
c) Middle of the stack
d) In between some value
Answer: b
36) What happens when you push a new node onto a
stack?
a) The new node is placed at the front of the
linked list
b) The new node is placed at the back of the linked
list
c) The new node is placed at the middle of the
linked list
d) No Changes happens
Answer: a
37) The retrieval of items in a stack is ……….. operation.
a) Push
b) Pop
c) retrieval
d) access
Answer: b
38) Which is the pointer associated with the stack?
a) FIRST
b) FRONT
c) TOP
d) REAR
Answer: c
39) The elements are removal from a stack in ……….
order.
a) Reverse
b) Hierarchical
c) Alternative
d) Sequential
Answer: a
40) Which of the following is an application of
stack?
a) finding factorial
b) tower of Hanoi
c) infix to postfix
d) all of the above
Answer: d
41. What is the value of the postfix expression 6 3
2 4 + – *?
a) 1
b) 40
c) 74
d) -18
Answer: d
42. 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
43. 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: c
44. The postfix form of A*B+C/D is?
a) *AB/CD+
b) AB*CD/+
c) A*BC+/D
d) ABCD+/*
Answer: b
45. 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
46.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
47.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
48. The result of evaluating the postfix expression
5, 4, 6, +, *, 4, 9, 3, /, +, * is?
a) 600
b) 350
c) 650
d) 588
Answer: b
49. Which data structure can be used to test a
palindrome?
a) Tree
b) Heap
c) Stack
d) Priority queue
Answer: c
50. At the end of last operation, total number of
element present in stack are
a) 3
b) 2
c) 1
d) 0
Answer: a
Unit 5: Queue
1. 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
2. The data structure required for Breadth First
Traversal on a graph is?
a) Stack
b) Array
c) Queue
d) Tree
Answer: c
3. A queue follows __________
a) FIFO (First In First Out) principle
b) LIFO (Last In First Out) principle
c) Ordered array
d) Linear tree
Answer: a
4. Circular Queue is also known as ________
a) Ring Buffer
b) Square Buffer
c) Rectangle Buffer
d) Curve Buffer
Answer: a
5. 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
6. 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
7. 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
8. Queues serve major role in ______________
a) Simulation of recursion
b) Simulation of arbitrary linked list
c) Simulation of limited resource allocation
d) Simulation of heap sort
Answer: c
9. Which of the following is not the type of queue?
a) Ordinary queue
b) Single ended queue
c) Circular queue
d) Priority queue
Answer: b
10. In linked list implementation of a queue, where
does a new element be inserted?
a) At the head of link list
b) At the tail of the link list
c) At the centre position in the link list
d) None
ANSWER: b
11. In the array implementation of circular queue,
which of the following operation take worst case linear time?
a) Insertion
b) Deletion
c) To empty a queue
d) None
ANSWER: d
12. In linked list implementation of queue, if only
front pointer is maintained, which of the following operation take worst case linear
time?
a) Insertion
b) Deletion
c) To empty a queue
d) Both a) and c)
ANSWER: d
13. If the MAX_SIZE is the size of the array used
in the implementation of circular queue. How is rear manipulated while inserting
an element in the queue?
a) rear=(rear%1)+MAX_SIZE
b) rear=rear%(MAX_SIZE+1)
c) rear=(rear+1)%MAX_SIZE
d) rear=rear+(1%MAX_SIZE)
ANSWER: c
14. If the MAX_SIZE is the size of the array used
in the implementation of circular queue, array index start with 0, front point to
the first element in the queue, and rear point to the last element in the
queue. Which of the following condition specify that circular queue is FULL?
a) Front=rear= - 1
b) Front=(rear+1)%MAX_SIZE
c) Rear=front+1
d) Rear=(front+1)%MAX_SIZE
ANSWER: b
15. A circular queue is implemented using an array
of size 10. The array index starts with 0, front is 6, and rear is 9. The
insertion of next element takes place at the array index.
a) 0
b) 7
c) 9
d) 10
ANSWER: a
16. What is the worst case time complexity of a
sequence of n queue operations on an initially empty queue?
a) θ (n)
b) θ (n + k)
c) θ (nk)
d) θ (n2)
ANSWER: a
17. If the MAX_SIZE is the size of the array used
in the implementation of circular queue, array index start with 0, front point to
the first element in the queue, and rear point to the last element in the
queue. Which of the following condition specify that circular queue is EMPTY?
a) Front=rear=0
b) Front= rear=-1
c) Front=rear+1
d) Front=(rear+1)%MAX_SIZE
ANSWER: b
18. 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
19. In linked list implementation of a queue, front
and rear pointers are tracked. Which of these pointers will change during an insertion
into a NONEMPTY queue?
a) Only front pointer
b) Only rear pointer
c) Both front and rear pointer
d) None of the front and rear pointer
ANSWER: b
20. 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
21. In linked list implementation of a queue, front
and rear pointers are tracked. Which of these pointers will change during an insertion
into EMPTY queue?
a) Only front pointer
b) Only rear pointer
c) Both front and rear pointer
d) None
ANSWER: c
22. An array of size MAX_SIZE is used to implement
a circular queue. Front, Rear, and count are tracked. Suppose front is 0 and
rear is MAX_SIZE -1. How many elements are present in the queue?
a) Zero
b) One
c) MAX_SIZE-1
d) MAX_SIZE
ANSWER: d
23. Suppose a circular queue of capacity (n-1) elements
is implemented with an array of n elements. Assume that the insertion and
deletion operations are carried out using REAR and FRONT as array index
variables, respectively. Initially REAR=FRONT=0. The conditions to detect queue
full and queue is empty are?
a) Full: (REAR+1)mod n == FRONTEmpty: REAR==FRONT
b) Full: (REAR+1)mod n == FRONTEmpty: (FRONT+1) mod
n == REAR
c) Full: REAR==FRONTEmpty: (REAR+1) mod n==FRONT
d) Full: (FRONT+1)mod n==REAREmpty: REAR==FRONT
ANSWER: a
24.Which one of the following is an application of
Queue Data Structure? When a resource is shared among multiple consumers.
a) When data is transferred asynchronously (data
not necessarily received at same rate as sent) between two processes
b) Load Balancing
c) All of the above
Ans : c
25.In linked list implementation of queue, if only
front pointer is maintained, which of the following operation take worst case linear
time?
a) Insertion
b) Deletion
c) To empty a queue
d) Both Insertion and To empty a queue
Ans : D
26.How many stacks are needed to implement a queue.
Consider the situation where no other data structure like arrays, linked list
is available to you.
a)1
b) 2
c) 3
d) 4
Ans : B
27.In a Queue, if a user tries to remove an element
from empty Queue it is called _________.
a) Underflow
b) Empty collection
c) Overflow
d) Garbage Collection
Ans : A
28. In case of insertion into a linked queue, a
node borrowed from the __________ list is inserted in the queue.
a) REAR
b) None of the mentioned
c) AVAIL
d) FRONT
Ans : A
29.If the MAX_SIZE is the size of the array used in
the implementation of circular queue. How is rear manipulated while inserting
an element in the queue?
a) rear=(rear%1)+MAX_SIZE
b) rear=rear%(MAX_SIZE+1)
c) rear=(rear+1)%MAX_SIZE
d) rear=rear+(1%MAX_SIZE)
ANSWER: b
30. Queues serve major role in Simulation of
recursion
a) Simulation of arbitrary linked list
b) Simulation of limited resource allocation
c) All of the mentioned
Ans : C
31. Which of the following is not the type of queue?
a) Ordinary queue
b) Single ended queue
c) Circular queue
d) Priority queue
Ans : B
32.What kind of a datastructure does a queue is?
a) Linear
b) B non-linear
c) both A&B
d) none
Answer: A
33.Which one of the following terms we use to
mention the number of elements that a queue can hold?
a) LENGTH
b) SIZE
c) CAPACITY
d) DATA
Answer : A
34. Similarly in DEQUEUEs, insertion is performed at
___ end whereas the deletion is performed at __ end.
a) FRONT, REAR
b) REAR, FRONT.
c) Both A & B
d) None of the above
Answer: C
35.Consider P,Q,R and S are the four elements in a
queue. If we delete an element at a time then on which order they will get
deleted?
a) PQRS
b) SRQP
c) PSQR
d) SRQP
Answer: A
36.A circular queue is implemented using an array
of size 10. The array index starts with 0, front is 6, and rear is 9. The
insertion of next element takes place at the array index of__.
a) 0
b) 7
c) 9
d) 10
Answer : A
37.In linked list implementation of a queue, front
and rear pointers are tracked. Which of these pointers will change during an insertion
into a NONEMPTY queue?
a) Only front pointer
b) Only rear pointer
c) Both front and rear pointer
d) None of the front and rear pointer
Answer : B
38.The implementation of Radix sort can be done
with the help of ____.
a) Linked list
b) Stack
c) Queue
d) Possible with all the above.
Answer: C
39.Which one of the following is an application(s)
of Queue Data Structure?
a) When a resource is shared among multiple
consumers
b) When data is transferred asynchronously between
the two processes.
c) Load balancing
d) all the above
Answer: D
40. How many stacks are needed to implement a
queue?
a) 1
b) 2
c) 3
d) 4
Answer: B
41. In Queue, ENQUEUE means____ whereas DEQUEUE
refers____.
a) an insertion operation, a deletion operation.
b) End of the queue, defining a queue.
c) Both A and B.
d) None of the above are true.
Answer: A
42. ___________of the queue added a new nodes
a) Front
b) middle
c) back
d) Both A and B
Answer: c
43. Major role of queue server in ______________
a) Simulation of heapsort
b) Simulation of arbitrary linked list
c) Simulation of limited resource allocation
d) Simulation of recursion
Answer: c
44. Which elements not in middle but can be inserted
or deleted at/from both the ends?
a) Circular queue
b) Priority queue
c) Queue
d) DE queue
e) All of these
Answer: d
45. Circular Queue is also called ________
a) Square Buffer
b) Ring Buffer
c) Rectangle Buffer
d) Curve Buffer
e) None of these
Answer: b
46. For Breadth-First Traversal on a graph is the
data structure required?
a) Stack
b) queue
c) array
d) Tree
e) Both a&b
Answer: b
47. Which deletion can be insertion take place only
at the other end(rear) and done from one end (front)?
a) linked list
b) Stack
c) Tree
d) queue
e)both a&c
Answer: d
48. In what order will they be removed If the
elements “A”, “B”, “C” and “D” are placed in a queue and are deleted one at a time
a) ABCD
b) DCAB
c) DCBA
d) ABDC
e) All of the above
Answer: a
49. if implemented using an array of size MAX_SIZE,
gets full when
a) Front = (rear + 1)mod MAX_SIZE
b) Front = rear + 1
c) Rear = MAX_SIZE – 1
d) Rear = front
e) None of above
Answer: c
50. Which is not the type of queue?
a) Single ended queue
b) Ordinary queue
c) Circular queue
d) Priority queue
e) Both c&d
Answer: a
0 Comments