Unit 2 MCQ

CS8391 DATA STRUCTURES
CS8391 Data Structures

Anna University :: Regulations 2017
Multiple Choice Questions (MCQ)
UNIT II LINEAR DATA STRUCTURES – STACKS, QUEUES
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
1 www.studymaterialz.in
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. 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
Answer: d
7. 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
Answer: c
8. 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
Answer: b
9. What is the value of the postfix expression 6 3 2 4 + – *?
a) 1
b) 40
c) 74
d) -18
Answer: d
10. 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
Answer: d
11. 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
12. The data structure required to check whether an expression contains balanced parenthesis is?
a) Stack
b) Queue
c) Array
d) Tree
Answer: a
13. 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
14. 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
15. The postfix form of A*B+C/D is?
a) *AB/CD+
b) AB*CD/+
c) A*BC+/D
d) ABCD+/*
Answer: b
16. Which data structure is needed to convert infix notation to postfix notation?
a) Branch
b) Tree
c) Queue
d) Stack
Answer: d
17. The prefix form of A-B/ (C * D ^ E) is?
a) -/*ÂCBDE
b) -ABCD*^DE
c) -A/B*C^DE
d) -A/BC*^DE
Answer: c
18. What is the result of the following operation?
Top (Push (S, X))
a) X
b) X+S
c) S
Answer: a
19. 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
20. Which data structure is used for implementing recursion?
a) Queue
b) Stack
c) Array
d) List
Answer: b
21. 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
22. 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
23. Which of the following is an infix expression?
a) (a+b)*(c+d)
b) ab+c*
c) +ab
d) abc+*
Answer: a
24. 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
25. a) abc*+de*+
b) abc+*de*+
c) a+bc*de+*
d) abc*+(de)*+
Answer: a
26. a) -ab-c
b) ab – c –
c) – -abc
d) -ab-c
Answer: b
27. a) abc^/d-
b) ab/cd^-
c) ab/^cd-
d) abcd^/-
Answer: a
28. 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
29. 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
30. a) ab*+cd/
b) ab+*cd/
c) abc*+/d
d) abc+*d/
Answer: d
31. a) ab*cdef/^*g-h+
b) abcdef^/*g*h*+
c) abcd*êd/g*-h*+
d) abc*de^fg/*-*h+
Answer: b
32. a) abc^de-fg+*^*+i-
b) abcde^-fg*+*^h*+i-
c) abcdê-fgh*+^*+i-
d) ab^-dc*+ef^gh*+i-
Answer: c
33. From the given Expression tree, identify the correct postfix expression from the list of options.
a) ab*cd*+
b) ab*cd-+
c) abcd-*+
Answer: b
34. 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
35. The data structure required for Breadth First Traversal on a graph is?
a) Stack
b) Array
c) Queue
d) Tree
Answer: c
36. 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
37. Circular Queue is also known as ________
a) Ring Buffer
b) Square Buffer
c) Rectangle Buffer
d) Curve Buffer
Answer: a
38. 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
39. 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
40. 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
41. 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
42. 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
43. With what data structure can a priority queue be implemented?
a) Array
b) List
c) Heap
d) Tree
Answer: d
44. 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
Answer: c
45. 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)
Answer: c
46. a) Delete the second element in the list
b) Return but not delete the second element in the list
c) Delete the first element in the list
d) Return but not delete the first element in the list
Answer: c
47. 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
Answer: c
48. 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
Answer: d
49. 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)
Answer: c
50. 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
Answer: a
51. a) Insert at the front end of the dequeue
b) Insert at the rear end of the dequeue
c) Fetch the element at the rear end of the dequeue
d) Fetch the element at the front end of the dequeue
Answer: b
52. 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
Answer: d
53. a) 10 30 10 15
b) 20 30 40 15
c) 20 30 40 10
d) 10 30 40 15
Answer: d
54. 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
Answer: b
55. 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–
Answer: b
56. 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
Answer: a
57. What is the time complexity of enqueue operation?
a) O(logn)
b) O(nlogn)
c) O(n)
d) O(1)
Answer: d
58. a) Dequeue
b) Enqueue
c) Return the front element
d) Return the last element
Answer: c
59. 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
Answer: a
60. What is the space complexity of a linear queue having n elements?
a) O(n)
b) O(nlogn)
c) O(logn)
d) O(1)
Answer: a
61. a) 3 3
b) 3 6
c) 6 6
d) 10 6
Answer: a

Unit 2 MCQ

Uploaded by

Copyright:

Available Formats

Unit 2 MCQ

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Unit 2 MCQ

Uploaded by

Copyright:

Available Formats

CS8391 DATA STRUCTURES

CS8391 Data Structures

2. Process of removing an element from stack is called __________

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

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

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

a) AB+ CD*E – FG /**

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

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

18. What is the result of the following operation?

Top (Push (S, X))

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

20. Which data structure is used for implementing recursion?

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

d) Operator stack is emptied

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

b) It is placed in the output

c) It is placed in the operator stack

d) The contents of the operator stack is emptied

23. Which of the following is an infix expression?

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

a) operand is always placed in the output

c) parenthesis are included in the output

d) higher and equal priority operators follow the same condition

36. A queue follows __________

a) FIFO (First In First Out) principle

b) LIFO (Last In First Out) principle

37. Circular Queue is also known as ________

b) Front = (rear + 1)mod MAX_SIZE

41. Queues serve major role in ______________

b) Simulation of arbitrary linked list

c) Simulation of limited resource allocation

d) Simulation of heap sort

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

b) Single ended queue

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

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

b) Interrupt handling in operating system

c) Undo operation in text editors

d) Bayesian spam filter

46. a) Delete the second element in the list

b) Return but not delete the second element in the list

c) Delete the first element in the list

d) Return but not delete the first element in the list

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

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

b) Processes with different priority can be efficiently handled

c) Applications with differing requirements

d) Easy to delete elements in any case

50. What is a dequeue?