Roll No.:…………….........
National Institute of Technology, Delhi
Name of the Examination: B.Tech.
End Semester Lab Examination (Spring, 2020)
Branch : EE Semester : 2nd
Title of the Course : Data Structure Course Code : CSB102
Time: 2 Hours Maximum Marks: 50
Note : Attempt All Questions
_______________________________________________________________________________
Q 1- Which one of the below mentioned is linear data structure −
A - Queue
B - Stack
C - Arrays
D - All of the above
Q 2 - Quick sort running time depends on the selection of
A - size of array
B - pivot element
C - sequence of values
D - none of the above!
3. Which of the following points is/are true about Linked List data structure when it is compared
with array
(A) Arrays have better cache locality that can make them better in terms of performance.
(B) It is easy to insert and delete elements in Linked List
(C) Random access is not allowed in a typical implementation of Linked Lists
(D) The size of array has to be pre-decided, linked lists can change their size any time.
(E) All of the above
4 ............. form of access is used to add and remove nodes from a queue.
A. LIFO, Last In First Out
B. FIFO, First In First Out
C. Both a and b
D. None of these
5. In linked representation of stack ........ holds the elements of the stack.
A. INFO fields
B. TOP fields
C. LINK fields
D. NULL fields
6 ........... form of access is used to add remove nodes from a stack.
A. LIFO
B. FIFO
C. Both A and B
D. None of these
7. 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
8. New nodes are added to the ……… of the queue.
A. Front
B. Back
C. Middle
D. Both A and B
9. 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
10. 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
11. A queue is a ………
A. FIFO
B. LIFO
C. FILO
D. LOFI
12. Which of the following name does not relate to stacks?
A. FIFO lists
B. LIFO lists
C. Piles
D. Push down lists
13. The retrieval of items in a stack is ............... operation.
A. push
B. pop
C. retrieval
D. access
14. The term push and pop is related to
A. Array
B. Lists
C. Stacks
D. Trees
15. Which is the pointer associated with the stack?
A. FIRST
B. FRONT
C. TOP
D. REAR
16. The elements are removal from a stack in .............. order.
A. Reverse
B. Hierarchical
C. Alternative
D. Sequential
17. The insertion operation in the stack is called ………
A. insert
B. push
C. pop
D. top
18. …………..is the term used to insert an element into stack.
A. Push
B. Pull
C. Pop
D. Pump
19. Stack follows the strategy of ……..
A. LIFO
B. FIFO
C. LRU
D. RANDOM
20. ………is the term used to delete an element from the stack.
A. Push
B. Pull
C. Pop
D. Pump
21. Deletion operation is done using ……… in a queue.
A. front
B. rear
C. top
D. list
22. A pointer variable which contains the location at the top element of the stack is called
…..
A. Top
B. Last
C. Final
D. End
23. 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
24. Following is C like pseudo code of a function that takes a number as an argument, and
uses a stack S to do processing.
void fun(int n)
{
Stack S; // Say it creates an empty stack S
while (n > 0)
{
// This line pushes the value of n%2 to stack S
push(&S, n%2);
n = n/2;
}
// Run while Stack S is not empty
while (!isEmpty(&S))
printf("%d ", pop(&S)); // pop an element from S and print it
}
What does the above function do in general?
(A) Prints binary representation of n in reverse order
(B) Prints binary representation of n
(C) Prints the value of Logn
(D) Prints the value of Logn in reverse order
25. Which one of the following is an application of Stack Data Structure?
A Managing function calls B The
stock span problem
C Arithmetic expression evaluation D All of
the above
26. To evaluate an expression without any embedded function calls:
A One stack is enough
B Two stacks are needed
C As many stacks as the height of the expression tree are needed D
A Turing machine is needed in the general case
27. Assume that the operators +, -, × are left associative and ^ is right associative. The order of
precedence (from highest to lowest) is ^, x , +, -. The postfix expression corresponding to the infix
expression a + b × c - d ^ e ^ f is
A abc × + def ^ ^ -
B abc × + de ^ f ^ - C
ab + c × d - e ^ f ^ D
- + a × bc ^ ^ def
28. A program P reads in 500 integers in the range [0..100] exepresenting the scores of 500
students. It then prints the frequency of each score above 50. What would be the best way for P
to store the frequencies? (GATE CS 2005)
A. An array of 50 numbers
B. An array of 100 numbers
C. An array of 500 numbers
D. A dynamically allocated array of 550 numbers
29.The minimum number of comparisons required to determine if an integer appears more
than n/2 times in a sorted array of n integers is
A Θ(n)
B Θ(logn) C
Θ(log*n) D
Θ(1)
30. Which of the following correctly declares an array?
A int geeks[20]; B int
geeks;
C geeks{20};
D array geeks[20];
31. Consider a two dimensional array A[20][10]. Assume 4 words per memory cell, the base address of
array A is 100, elements are stored in row-major order and first element is A[0][0]. What is the address
of A[11][5] ?
A 560
B 460
C 570
D 575
32. Which one of the following is an application of Queue Data Structure?
A When a resource is shared among multiple consumers.
B When data is transferred asynchronously (data not necessarily received at same rate as sent) between
two processes
C Load Balancing D
All of the above
33. 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
34. How many queues are needed to implement a stack. Consider the situation where no other data
structure like arrays, linked list is available to you.
A 1
B 2
C 3
D 4
35. APriority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level- order
traversal of the heap is given below: 10, 8, 5, 3, 2 Two new elements ”1‘ and ”7‘ are inserted in the
heap in that order. The level-order traversal of the heap after the insertion of the elements is:
A 10, 8, 7, 5, 3, 2, 1
B 10, 8, 7, 2, 3, 1, 5
C 10, 8, 7, 1, 2, 3, 5
D 10, 8, 7, 3, 2, 1, 5
36. What is common in three different types of traversals (Inorder, Preorder and
Postorder)?
A Root is visited before right subtree
B Left subtree is always visited before right subtree C
Root is visited after left subtree
D All of the above
E None of the above
37. The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g,
respectively. The postorder traversal of the binary tree is:
Adebfgca
B edbgfca
Cedbfgca
Ddefgbca
38. Which of the following pairs of traversals is not sufficient to build a binary tree from the
given traversals?
A Preorder and Inorder
B Preorder and Postorder
C Inorder and Postorder
D None of the Above
39. Which traversal of tree resembles the breadth first search of the graph?
40. Which of the tree traversal uses a queue data structure?
41.Which of the following cannot generate the full binary tree?
A Inorder and Preorder
B Inorder and Postorder
C Preorder and Postorder
D None of the above
42. The goal of hashing is to produce a search that takes?
a) O(1) times
b) O(n2) times
c) O( log n) times
d) O(n log n) times
43. Which of the following is not a type of queue?
a) Priority queue
b) Circular queue
c) Ordinary queue
d) Single ended queue
44. Which algorithm is used by card sorter?
a) Quick
b) Heap
c) Insertion
d) Radix
45. The number of leaf nodes in a complete binary tree of depth d is?
a) 2d
b) 2d-1 +1
c) 2d+1+1
d) 2d +1
46. What does the following function do for a given Linked List with first node as head?
void fun1(struct node* head)
{
if(head == NULL)
return;
fun1(head->next);
printf("%d ", head->data);
}
47. Which of the sorting algorithms can be used to sort a random linked list with minimum time
complexity?
48. What differentiates a circular linked list from a normal linked list?
49. The full binary tree with 2n+1 node contain
a) n leaf nodes
b) n non-leaf nodes
c) n-1 leaf nodes
d) n-1 non-leaf nodes
50. The quick sort algorithm exploit which design technique?
a) Overflow
b) Backtracking
c) Dynamic programming
d) Divide and conquer
