Quiznetik

Data Structures (DS) | Set 1

1. 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

Correct : B. Container of objects of similar types

2. How do you initialize an array in C?

A. int arr[3] = (1,2,3);

B. int arr(3) = {1,2,3};

C. int arr[3] = {1,2,3};

D. int arr(3) = (1,2,3);

Correct : C. int arr[3] = {1,2,3};

3. How do you instantiate an array in Java?

A. int arr[] = new int(3);

B. int arr[];

C. int arr[] = new int[3];

D. int arr() = new int(3);

Correct : C. int arr[] = new int[3];

4. Which of the following is a correct way to declare a multidimensional array in Java?

A. int[] arr;

B. int arr[[]];

C. int[][]arr;

D. int[[]] arr;

Correct : C. int[][]arr;

5. When does the ArrayIndexOutOfBoundsException occur?

A. Compile-time

B. Run-time

C. Not an error

D. Not an exception at all

Correct : B. Run-time

6. Which of the following concepts make extensive use of arrays?

A. Binary trees

B. Scheduling of processes

C. Caching

D. Spatial locality

Correct : D. Spatial locality

7. What are the advantages of arrays?

A. Objects of mixed data types can be stored

B. Elements in an array cannot be sorted

C. Index of first element of an array is 1

D. Easier to store elements of same data type

Correct : D. Easier to store elements of same data type

8. What are the disadvantages of arrays?

A. Data structure like queue or stack cannot be implemented

B. There are chances of wastage of memory space if elements inserted in an array are lesser than the allocated size

C. Index value of an array can be negative

D. Elements are sequentially accessed

Correct : B. There are chances of wastage of memory space if elements inserted in an array are lesser than the allocated size

9. Assuming int is of 4bytes, what is the size of int arr[15];?

A. 15

B. 19

C. 11

D. 60

Correct : D. 60

10. In general, the index of the first element in an array is

A. 0

B. -1

C. 2

D. 1

Correct : A. 0

11. Elements in an array are accessed

A. randomly

B. sequentially

C. exponentially

D. logarithmically

Correct : A. randomly

12. 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

Correct : D. Accessing elements at specified positions

13. 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)

Correct : D. Either O(1) or O(n)

14. 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)

Correct : B. O(n)

15. 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)

Correct : A. O(1)

16. Which of these is not an application of linked list?

A. To implement file systems

B. For separate chaining in hash-tables

C. To implement non-binary trees

D. Random Access of elements

Correct : D. Random Access of elements

17. 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

Correct : D. Implementing a doubly linked list is easier than singly linked list

18. 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)

Correct : C. O(n)

19. 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

Correct : C. You may or may not have the ‘next’ pointer point to null in a circular linked list

20. 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)

Correct : A. O(n)

21. 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

Correct : C. Allocating CPU to resources

22. 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

Correct : B. Time complexity of inserting a new node at the head of the list is O(1)

23. 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

Correct : 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

24. 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

Correct : A. Linked list

25. 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

Correct : C. Pointer to node

26. 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)

Correct : C. θ(n)

27. 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)

Correct : A. O(1)

28. 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)

Correct : B. O(n)

29. 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)

Correct : A. O(1)

30. 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

Correct : C. Circular doubly linked list

31. 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));

Correct : A. ptr = (NODE*)malloc(sizeof(NODE));

32. Process of inserting an element in stack is called

A. Create

B. Push

C. Evaluation

D. Pop

Correct : B. Push

33. Process of removing an element from stack is called

A. Create

B. Push

C. Evaluation

D. Pop

Correct : D. Pop

34. 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

Correct : A. Underflow

35. 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

Correct : A. Overflow

36. 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

Correct : D. There is a Sequential entry that is one by one

37. Which of the following is not the application of stack?

A. A parentheses balancing program

B. Tracking of local variables at run time

C. Compiler Syntax Analyzer

D. Data Transfer between two asynchronous process

Correct : D. Data Transfer between two asynchronous process

38. 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. none

D. none

Correct : B. 2

39. What is the value of the postfix expression 6 3 2 4 + – *?

A. 1

B. 40

C. 74

D. -18

Correct : D. -18

40. The postfix form of the expression (A+ B)(CD- 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 /

Correct : C. AB + CD* E – *F *G /

41. The data structure required to check whether an expression contains balanced parenthesis is?

A. Stack

B. Queue

C. Array

D. Tree

Correct : A. Stack

42. 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

Correct : B. Stack

43. 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

Correct : D. Stack

44. The postfix form of A*B+C/D is?

A. *AB/CD+

B. AB*CD/+

C. A*BC+/D

D. ABCD+/*

Correct : B. AB*CD/+

45. Which data structure is needed to convert infix notation to postfix notation?

A. Branch

B. Tree

C. Queue

D. Stack

Correct : D. Stack

46. The prefix form of A-B/ (C * D ^ E) is?

A. -/*^ACBDE

B. -ABCD*^DE

C. -A/B*C^DE

D. -A/BC*^DE

Correct : C. -A/B*C^DE

47. What is the result of the following operation? Top (Push (S, X))

A. X

B. X+S

C. S

D. none

Correct : A. X

48. The prefix form of an infix expression (p + q) – (r * t) is?

A. + pq – *rt

B. – +pqr * t

C. – +pq * rt

D. – + * pqrt

Correct : C. – +pq * rt

49. Which data structure is used for implementing recursion?

A. Queue

B. Stack

C. Array

D. List

Correct : B. Stack

50. 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

Correct : A. It is placed on to the output

51. 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

Correct : C. It is placed in the operator stack

52. Which of the following is an infix expression?

A. (a+b)*(c+d)

B. ab+c*

C. +ab

D. abc+*

Correct : A. (a+b)*(c+d)

53. 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)

Correct : B. O(N)

54. 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

Correct : C. parenthesis are included in the output

55. 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

Correct : B. left to right

56. 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

Correct : A. Queue

57. The data structure required for Breadth First Traversal on a graph is?

A. Stack

B. Array

C. Queue

D. Tree

Correct : C. Queue

58. A queue follows

A. FIFO (First In First Out) principle

B. LIFO (Last In First Out) principle

C. Ordered array

D. Linear tree

Correct : A. FIFO (First In First Out) principle

59. Circular Queue is also known as

A. Ring Buffer

B. Square Buffer

C. Rectangle Buffer

D. Curve Buffer

Correct : A. Ring Buffer

60. 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

Correct : A. ABCD

61. 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

Correct : C. Dequeue

62. 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

Correct : A. Rear = MAX_SIZE – 1

63. 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

Correct : C. Simulation of limited resource allocation

64. Which of the following is not the type of queue?

A. Ordinary queue

B. Single ended queue

C. Circular queue

D. Priority queue

Correct : B. Single ended queue

65. With what data structure can a priority queue be implemented?

A. Array

B. List

C. Heap

D. Tree

Correct : D. Tree

66. Which of the following is not an application of priority queue?

A. Huffman codes

B. Interrupt handling in operating system

C. Undo operation in text editors

D. Bayesian spam filter

Correct : C. Undo operation in text editors

67. What is the time complexity to insert a node based on key in a priority queue?

A. O(nlogn)

B. O(logn)

C. O(n)

D. O(n2)

Correct : C. O(n)

68. What is not a disadvantage of priority scheduling in operating systems?

A. A low priority process might have to wait indefinitely for the CPU

B. If the system crashes, the low priority systems may be lost permanently

C. Interrupt handling

D. Indefinite blocking

Correct : C. Interrupt handling

69. Which of the following is not an advantage of priority queue?

A. Easy to implement

B. Processes with different priority can be efficiently handled

C. Applications with differing requirements

D. Easy to delete elements in any case

Correct : D. Easy to delete elements in any case

70. What is the time complexity to insert a node based on position in a priority queue?

A. O(nlogn)

B. O(logn)

C. O(n)

D. O(n2)

Correct : C. O(n)

71. What is a dequeue?

A. A queue with insert/delete defined for both front and rear ends of the queue

B. A queue implemented with a doubly linked list

C. A queue implemented with both singly and doubly linked lists

D. A queue with insert/delete defined for front side of the queue

Correct : A. A queue with insert/delete defined for both front and rear ends of the queue

72. What are the applications of dequeue?

A. A-Steal job scheduling algorithm

B. Can be used as both stack and queue

C. To find the maximum of all sub arrays of size k

D. To avoid collision in hash tables

Correct : D. To avoid collision in hash tables

73. Which of the following properties is associated with a queue?

A. First In Last Out

B. First In First Out

C. Last In First Out

D. Last In Last Out

Correct : B. First In First Out

74. In a circular queue, how do you increment the rear end of the queue?

A. rear++

B. (rear+1) % CAPACITY

C. (rear % CAPACITY)+1

D. rear–

Correct : B. (rear+1) % CAPACITY

75. What is the term for inserting into a full queue known as?

A. overflow

B. underflow

C. null pointer exception

D. program won’t be compiled

Correct : A. overflow

76. What is the time complexity of enqueue operation?

A. O(logn)

B. O(nlogn)

C. O(n)

D. O(1)

Correct : D. O(1)

77. What is the need for a circular queue?

A. effective usage of memory

B. easier computations

C. to delete elements based on priority

D. implement LIFO principle in queues

Correct : A. effective usage of memory

78. What is the space complexity of a linear queue having n elements?

A. O(n)

B. O(nlogn)

C. O(logn)

D. O(1)

Correct : A. O(n)

79. What is the maximum number of children that a binary tree node can have?

A. 0

B. 1

C. 2

D. 3

Correct : C. 2

80. The following given tree is an example for?

A. Binary tree

B. Binary search tree

C. Fibonacci tree

D. none

Correct : A. Binary tree

81. How many common operations are performed in a binary tree?

A. 1

B. 2

C. 3

D. 4

Correct : C. 3

82. What is the traversal strategy used in the binary tree?

A. depth-first traversal

B. breadth-first traversal

C. random traversal

D. Priority traversal

Correct : B. breadth-first traversal

83. How many types of insertion are performed in a binary tree?

A. 1

B. 2

C. 3

D. 4

Correct : B. 2

84. What operation does the following diagram depict?

A. inserting a leaf node

B. inserting an internal node

C. deleting a node with 0 or 1 child

D. none

Correct : C. deleting a node with 0 or 1 child

85. How many bits would a succinct binary tree occupy?

A. n+O(n)

B. 2n+O(n)

C. n/2

D. n

Correct : B. 2n+O(n)

86. The average depth of a binary tree is given as?

A. O(N)

B. O(√N)

C. O(N2)

D. O(log N)

Correct : D. O(log N)

87. How many orders of traversal are applicable to a binary tree (In General)? 3

A. 1

B. 4

C. 2

D. 3

Correct : D. 3

88. If binary trees are represented in arrays, what formula can be used to locate a left child, if the node has an index i?

A. 2i+1

B. 2i+2

C. 2i

D. 4i

Correct : A. 2i+1

89. Using what formula can a parent node be located in an array?

A. (i+1)/2

B. (i-1)/2

C. i/2

D. 2i/2

Correct : B. (i-1)/2

90. Which of the following properties are obeyed by all three tree – traversals?

A. Left subtrees are visited before right subtrees

B. Right subtrees are visited before left subtrees

C. Root node is visited before left subtree

D. Root node is visited before right subtree

Correct : A. Left subtrees are visited before right subtrees

91. 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. none

Correct : A. 2, 7, 2, 6, 5, 11, 5, 9, 4

92. 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. none

Correct : C. 2, 5, 11, 6, 7, 4, 9, 5, 2

93. 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)

Correct : B. O(n)

94. 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)

Correct : D. O(d)

95. 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

Correct : B. Pre-order traversal

96. Consider the following data. The pre order traversal of a binary tree is A, B, E, C, D. The in order traversal of the same binary tree is B, E, A, D, C. The level order sequence for the binary tree is

A. A, C, D, B, E

B. A, B, C, D, E

C. A, B, C, E, D

D. D, B, E, A, C

Correct : B. A, B, C, D, E

97. 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

Correct : C. 5

98. 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

Correct : C. T Q O P S R

99. 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

Correct : D. 8, 7, 26, 13, 40, 75, 70, 35

100. 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

Correct : B. post-order and in-order

Quiznetik

Data Structures (DS) | Set 1

1. Which of these best describes an array?

2. How do you initialize an array in C?

3. How do you instantiate an array in Java?

4. Which of the following is a correct way to declare a multidimensional array in Java?

5. When does the ArrayIndexOutOfBoundsException occur?

6. Which of the following concepts make extensive use of arrays?

7. What are the advantages of arrays?

8. What are the disadvantages of arrays?

9. Assuming int is of 4bytes, what is the size of int arr[15];?

10. In general, the index of the first element in an array is

11. Elements in an array are accessed

12. Which of the following is not a disadvantage to the usage of array?

13. What is the time complexity of inserting at the end in dynamic arrays?

14. What is the time complexity to count the number of elements in the linked list?

15. What is the space complexity for deleting a linked list?

16. Which of these is not an application of linked list?

17. Which of the following is false about a doubly linked list?

18. What is the worst case time complexity of inserting a node in a doubly linked list?

19. What differentiates a circular linked list from a normal linked list?

20. What is the time complexity of searching for an element in a circular linked list?

21. Which of the following application makes use of a circular linked list?

22. Which of the following is false about a circular linked list?

23. Consider a small circular linked list. How to detect the presence of cycles in this list effectively?

24. A linear collection of data elements where the linear node is given by means of pointer is called?

25. In linked list each node contain minimum of two fields. One field is data field to store the data second field is?

26. 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?

27. What would be the asymptotic time complexity to insert an element at the front of the linked list (head is known)?

28. What would be the asymptotic time complexity to find an element in the linked list?

29. What would be the asymptotic time complexity to insert an element at the second position in the linked list?

30. The concatenation of two list can performed in O(1) time. Which of the following variation of linked list can be used?

31. Which of the following c code is used to create new node?

32. Process of inserting an element in stack is called

33. Process of removing an element from stack is called

34. In a stack, if a user tries to remove an element from empty stack it is called

35. Pushing an element into stack already having five elements and stack size of 5, then stack becomes

36. Entries in a stack are “ordered”. What is the meaning of this statement?

37. Which of the following is not the application of stack?

39. What is the value of the postfix expression 6 3 2 4 + – *?

40. The postfix form of the expression (A+ B)*(C*D- E)*F / G is?

41. The data structure required to check whether an expression contains balanced parenthesis is?

42. What data structure would you mostly likely see in a non recursive implementation of a recursive algorithm?

43. The process of accessing data stored in a serial access memory is similar to manipulating data on a

44. The postfix form of A*B+C/D is?

45. Which data structure is needed to convert infix notation to postfix notation?

46. The prefix form of A-B/ (C * D ^ E) is?

47. What is the result of the following operation? Top (Push (S, X))

48. The prefix form of an infix expression (p + q) – (r * t) is?

49. Which data structure is used for implementing recursion?

50. When an operand is read, which of the following is done?

51. What should be done when a left parenthesis ‘(‘ is encountered?

52. Which of the following is an infix expression?

53. What is the time complexity of an infix to postfix conversion algorithm?

54. Which of the following statement is incorrect with respect to infix to postfix conversion algorithm?

55. In infix to postfix conversion algorithm, the operators are associated from?

56. 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 ?

57. The data structure required for Breadth First Traversal on a graph is?

58. A queue follows

59. Circular Queue is also known as

60. 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?

61. A data structure in which elements can be inserted or deleted at/from both the ends but not in the middle is?

62. A normal queue, if implemented using an array of size MAX_SIZE, gets full when

63. Queues serve major role in

64. Which of the following is not the type of queue?

65. With what data structure can a priority queue be implemented?

66. Which of the following is not an application of priority queue?

67. What is the time complexity to insert a node based on key in a priority queue?

68. What is not a disadvantage of priority scheduling in operating systems?

69. Which of the following is not an advantage of priority queue?

70. What is the time complexity to insert a node based on position in a priority queue?

71. What is a dequeue?

72. What are the applications of dequeue?

73. Which of the following properties is associated with a queue?

74. In a circular queue, how do you increment the rear end of the queue?

75. What is the term for inserting into a full queue known as?

76. What is the time complexity of enqueue operation?

77. What is the need for a circular queue?

78. What is the space complexity of a linear queue having n elements?

79. What is the maximum number of children that a binary tree node can have?

40. The postfix form of the expression (A+ B)(CD- E)*F / G is?