Shivaji University , Kolhapur

Question Bank For Mar 2022 (Summer ) Examination

Subject Code:73278 Subject Name: Data structures

Question Bank
1. A binary tree in which all its levels except the last, have maximum numbers of nodes, and all
the nodes in the last level have only one child it will be its left child. Name the tree.
A Threaded tree
B Complete binary tree
C M-way search tree
D Full binary tree

2. The number of edges in a complete graph of n vertices is

A. n(n+1)/2
B. n(n-1)/2
C. n2 /2
D. n

3 ………. sorting is good to use when alphabetizing a large list of names.

A. Merge
B. Heap
C. Radix
D. Bubble

4. To represent hierarchical relationship between elements, which data structure is suitable?

A. Dequeue

B. Priority

C. Tree

D. Graph

5 The elements of a linked list are stored

A. In a structure

B. In an array

C. Anywhere the computer has space for them

D. In contiguous memory locations

6.Which of this best describes an array??
A A data structure that shows a hierarchical behavior
B. Container of objects of similar types
C. Arrays are immutable once initialized
D. Array is not a data structure

7. In a stack, if a user tries to remove an element from an empty stack it is called _________
A. Underflow
B. Empty collection
C. Overflow
D. Garbage Collection

8 The time complexity of quick sort is …………..

A) O(n)
B) O(n2)
C) O(n log n)
D) O(log n)

9. The property of binary tree is

A) The first subset is called left subtree

B) The second subtree is called right subtree
C) The root cannot contain NULL
D) The right subtree can be empty

10. In general, the binary search method needs no more than ........... comparisons.
A) [log2n]-1
B) [logn]+1
C) [log2n]
D) [log2n]+1

11. A graph is a collection of nodes, called ………. And line segments called arcs or that
connect pair of nodes.

A) vertices, edges
B) edges, vertices
C) vertices, path
D)Graph node, edge

12. Describes the running time of an algorithm

A. Asymptotic Notation

B. Time complexity
C. Performance Analysis

D. None of these

13. Which of the following is not the internal sort?

A) Insertion Sort
B) Bubble Sort
C) Merge Sort
D) Heap Sort

14.In a queue, the initial values of front pointer f rare pointer r should be …….. and respectively.
A) 0 and 1
B) 0 and -1
C) -1 and 0
D) 1 and 0

15. Which of the following statement is true?

i) Using singly linked lists and circular list, it is not possible to traverse the list backwards.
ii) To find the predecessor, it is required to traverse the list from the first node in case of
singly linked list.
A) i-only
B) ii-only
C) Both i and ii
D) None of both

16. Each node in a linked list has two pairs of ………….. and ……………….

A) Link field and information field

B) Link field and avail field
C) Avail field and information field
D) Address field and link field

17. Finding the location of the element with a given value is:
A) Traversal
B) Search
C) Sort
D) None of above

18. Linked lists are best suited

A) for relatively permanent collections of data

B) for the size of the structure and the data in the structure are constantly changing
C) for both of above situation
D) for none of above situation
 19. Which if the following is/are the levels of implementation of data structure
A) Abstract level
B) Application level
C)Implementation level
D)All of the above

20. ...........is not the component of data structure.

A. Operations
B. Storage Structures
C. Algorithms
D. None of above

21. Which data structure allows deleting data elements from and inserting at rear?
A) Stacks
B) Queues
C) Dequeues
D) Binary search tree

22. In ............. , search start at the beginning of the list and check every element in the list.
A) Linear search
B) Binary search
C) Hash Search
Binary Tree search

23.Which of the following is non-linear data structure?

A. Array

B. Linked lists

C. Stacks

D. None of these

24. Which of the following is not a stable sorting algorithm?

A Insertion sort
B Selection sort
C Bubble sort
D Merge sort

25.Running merge sort on an array of size n which is already sorted is

A. O(n)
B. O(nlogn)
C O(n2)
D None

26.If the given input array is sorted or nearly sorted, which of the following algorithm gives the best
performance?
A. Insertion sort
B. Selection sort
C. Quick sort
D. Merge sort

27. Minimum number of fields in each node of a doubly linked list is ____
A. 2
B. 3
C. 4
D. None of the above

28. To perform level-order traversal on a binary tree, which of the following data structure will be
required?
A Hash table
B Queue
C Binary search tree
D Stack

29. Which of the following is a linear data structure?

A. Array
B.AVL Trees
C. Binary Trees
D. Graphs

30. Consider the following stack implemented using stack.

# define SIZE 11
struct STACK
{
int arr[SIZE];
int top=-1;
}
What would be the maximum value of the top that does not cause
the overflow of the stack?
A. 8
B. 9
C. 11
D. 10
31. The time complexity of quicksort is …….

A. O(n)
B. O(logn)
C. O(n2)
D. O (n logn)

32. ………. sorting is good to use when alphabetizing a large list of names.
A. Merge
B. Heap
C. Radix
D. Bubble

33 Identify the data structure which allows deletions at both ends of the list but insertion at only
one end.
A. Input restricted dequeue
B. Output restricted queue
C. Priority queues
D. All of the above

34. Which of the following statement is false?

A. Arrays are dense lists and static data structure.
B. Data elements in linked list need not be stored in adjacent space in
memory
C. Pointers store the next data element of a list.
D. Linked lists are collection of the nodes that contain information part
and next pointer.

35. What data structure would you mostly likely see in a non-recursive implementation of a
recursive algorithm?
A. Stack
B. Linked list
C. Queue
D. Trees

36. An adjacency matrix representation of a graph cannot contain information of :

A. nodes
B. edges
C. direction of edges
D. parallel edges

37’ Which of the following data structures is indexed structure?

A. Array
B. Structure
C. Stack
D. Queue

38. A B-tree of minimum degree t can maximum _____ pointers in a node.

A. t–1
B. 2t–1
C. 2t
D. t

39. An adjacency matrix representation of a graph cannot contain information of:

A. nodes
B. edges
C. direction of edges
D. parallel edges

40.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 /

41. Which data structure is used in breadth first search of a graph to hold nodes?

A. Stack
B. queue
C. Tree
D. Array

42. Which of the following is not an in-place sorting algorithm?

A. Selection sort
B. Heap sort
C. Quick sort
D. Merge sort

43.A binary search tree whose left subtree and right subtree differ in hight by at most 1 unit is
called ……
A) AVL tree
B) Red-black tree
C) Lemma tree
D) None of the above

44................. level is where the model becomes compatible executable code

 A) Abstract level
B) Application level
C) Implementation level
D) All of the above

45.Stack is also called as

A) Last in first out
B) First in last out
C) Last in last out
D) First in first out

46.Which of the following is true about the characteristics of abstract data types?
i) It exports a type.
A) True, False
B) False, True
C) True, True
D) False, False

47.To represent hierarchical relationship between elements, Which data structure is suitable?
A) Dequeue
B) Priority
C) Tree
D) Graph

48.A directed graph is ................. if there is a path from each vertex to every other vertex in the
digraph.
A) Weakly connected
B) Strongly Connected
C) Tightly Connected
D) Linearly Connected

49.In the ................. traversal we process all of a vertex’s descendants before we move to an
adjacent
vertex.
A) Depth First
B) Breadth First
C) With First
D) Depth Limited

50.State True of False.

i) Network is a graph that has weights or costs associated with it.
ii) An undirected graph which contains no cycles is called a forest.
iii) A graph is said to be complete if there is no edge between every pair of vertices.
A) True, False, True
 B) True, True, False
C) True, True, True
D) False, True, True

51.Match the following.

a) Completeness i) How long does it take to find a solution

b) Time Complexity ii) How much memory need to perform the search.

c) Space Complexity iii) Is the strategy guaranteed to find the solution when there in one.

A) a-iii, b-ii, c-i

B) a-i, b-ii, c-iii
C) a-iii, b-i, c-ii
D) a-i, b-iii, c-ii

52.The number of comparisons done by sequential search is ………………

A) (N/2)+1
B) (N+1)/2
C) (N-1)/2
D) (N+2)/2

53.In .............. , search start at the beginning of the list and check every element in the list.

D) Linear search
E) Binary search
F) Hash Search
G) Binary Tree search

54.State True or False.

i) Binary search is used for searching in a sorted array.
ii) The time complexity of binary search is O(logn).

A) True, False
B) False, True
C) False, False
D) True, True

55. State True or False.

i) An undirected graph which contains no cycles is called forest.
ii) A graph is said to be complete if there is an edge between every pair of vertices.
A) True, True
B) False, True
C) False, False
D) True, False
56. A graph is said to be .............. if the vertices can be split into two sets V1 and V2 such there are
no edges between two vertices of V1 or two vertices of V2.
A) Partite
B) Bipartite
C) Rooted
D) Bisects

57.In a circular queue the value of r will be ..

A) r=r+1

B) r=(r+1)% [QUEUE_SIZE – 1]

C) r=(r+1)% QUEUE_SIZE

D) r=(r-1)% QUEUE_SIZE

58.Which of the following statement is true?

i)Using singly linked lists and circular list, it is not possible to traverse the list backwards.
ii)To find the predecessor, it is required to traverse the list from the first node in case of singly
linked list.

A. i-only
B. ii-only
C. Both i and ii
D. None of both

59.A .......... is a graph that has weights of costs associated with its edges.
A) Network
B) Weighted graph
C) Both A and B
D) None A and B

60.In general, the binary search method needs no more than .......... comparisons.
A. [log2n]-1
B. [logn]+1
C. [log2n]
D. [log2n]+1

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

A) Ordinary queue
B) Single ended queue
C) Circular queue
 D) Priority queue

62.The property of binary tree is

A. The first subset is called left subtree
B. The second subtree is called right subtree
C. The root cannot contain NULL
D. The right subtree can be empty

63.State true or false.

i) The degree of root node is always zero.
ii) Nodes that are not root and not leaf are called as internal nodes.
A) True, True
B) True, False
C) False, True
D) False, False

64.Any node is the path from the root to the node is called

A) Successor node
B) Ancestor node
C) Internal node
D) None of the above

65.State true of false.

i) A node is a parent if it has successor nodes.

ii) A node is child node if out degree is one.
A) True, True
B) True, False
C) False, True
D) False, False

66.................. is not an operation performed on linear list

a) Insertion b) Deletion c) Retrieval d) Traversal
A) only a,b and c
B) only a and b
C) All of the above
D) None of the above

67.Which is/are the application(s) of stack

A) Function calls
B) Large number Arithmetic
C) Evaluation of arithmetic expressions
D) All of the above
68.A .............. is an acyclic digraph, which has only one node with indegree 0, and other nodes
have in-
degree 1.
A) Directed tree
B) Undirected tree
C) Dis-joint tree
D) Direction oriented tree

69.................... Is a directed tree in which outdegree of each node is less than or equal to two.
A) Unary tree
B) Binary tree
C) Trinary tree
D) Both B and C

70.What will be the value of top, if there is a size of stack STACK_SIZE is 5

A) 5
B) 6
C) 4
D) None

Solve the following questions 7 marks each

1. Explain Circular queue with example in detail.

2. Write the note on applications of stack and queue.
3. With the help of suitable example explain Insertion sort.
4 List and explain various types of Linked List with appropriate examples.
5 Explain the following operations on the singly linked list
a. Insertion.
b.Searching.
c. traversing
6. Draw the BST for the given input: 10, 1, 5, 15, 10, 20, 2, 16, 7, 20, 2, 1
Write the inorder traversal of the BST.
7. Write algorithm for finding minimum and maximum values from Binary Search Tree
8. What is complete binary tree? Calculate size of an array to store complete Binary tree of
depth4?
9 What is B-tree? Explain with suitable example, insertion of a node in B-Tree?
10. Give the Definition of Data structure? Explain with suitable examples following terms
i. Array
ii. Functions
ii. Control Structures
11. Explain working of the Bubble Sort Algorithm. Comment on Complexity of Sorting
Algorithm.
 12. Sort the following given numbers using Radix Sort Technique. 6,5,3,1,8,7,2,4
13.Explain Graph terminology. Give various types of Graphs.
14. Define the following terms with example:

a. Strictly Binary Tree

b. AVL tree
c. Heap tree
15 Explain graph traversal techniques with Example-DFS
16. Describe data structures used for storing a graph.
17. Explain graph traversal techniques with Example-BFS
18. What is AVL tree? Explain inset node operation of AVL tree.

19. Explain Push and Pop operations on stack with example in detail.
20. Explain working of the Merge Sort Algorithm. Comment on Complexity of Merge Sort.
21 Define queue. Explain its operations with example
1. Insertion 2. Deletion
22. Define Stack. Explain stack operations with example
23 Explain Binary search with example
24. Explain the following operations on the doubly linked list
1. Insertion.
2. Searching.
3. Traversing

25. Explain Heap sort with example.

26.Difference between DFS and BFS
27.Explain tree traversal techniques with example.
1. Inorder 2.Preorder 3. Postorder
28.What is data structure? Explain the classification of data structures in details.
29. Explain working of the Selection Sort Algorithm. Comment on Complexity of Merge Sort
30 Convert the following infix expression to postfix using stack
(a + b) * (c / d – e) show the contents of stack at every step of conversion.
31. Explain Priority queue in details? Write a note on applications of Priority queues
32.List and explain the Asymptotic Notations for analysis of Algorithms.
33.Explain the following operations on the circular linked list :
a.Insertion.
b.Searching.
c.Traversing

34. Explain following tree terminologies with suitable example

a. Terminal Nodes
b. Degree of a Node
c. Degree of a Tree
35 What is use of Binary Search Tree? Construct BST for following set of key values.
55,45,30,65,54,32,35,50,61
36. Explain Graph basic concepts and its storage representation
37. Write an algorithm for DFS Traversal. Examine the DFS traversal for the given graph from
source node H

3Insert the given numbers into an empty AVL tree:

64, 1, 44, 26, 13, 110, 98, 85
Perform necessary rotations and Build the tree.

39. Define the following terms with example

1. Path
2. Directed Graph
3. Strongly Connected Graph
4. Weighted Graph

40.Construct a heap from following list of numbers:

44, 30, 50, 22, 60, 55, 77, 55
After constructing a heap perform delete root operation and reconstruct
the heap.

41.Define B Tree and Construct B Tree of order 4 for given numbers

1, 6, 8, 2, 9, 12, 15, 7, 18, 3, 4, 20

42.Build a C code to sort the given list using Insertion sort method.
Sort the given list of numbers using same sort:
7, 8, 26, 44, 13, 23, 98, 57

43.Write algorithms for Insert and search operations on binary search tree.
Construct the BST for given list of letters:
S, T, P, Q, M, N, O, R, K, V, A, B. Perform Delete M operation and reconstruct the BST.
45.Write the algorithms for insertion and deletion operations on circular queue

46.Write a C Program or Pseudo Code for implementation of Stack using singly linked list

47.What is Hashing. Elaborate different types of Hash Functions

48. Write a sample code for following operations on doubly linked list

i. Insert a node at start of the list.

ii. Delete the node from end of list.

49.Compare different types of time complexity like constant, linear, etc.

50.What is algorithm? Describe in detail time and space complexity

51. Compare different types of time complexity like constant, linear, etc

52.Perform following set of operations on Stack. Consider stack of size 5.

PUSH (10), PUSH(20), PUSH(30), PUSH(40),POP, PUSH(50), PUSH(60), PUSH (70), POP,
POP, POP, PUSH (80), POP, POP, PUSH(90), POP, POP, POP, PUSH(100)

Indicate status of top variable in every operation

53.With help of suitable example, explain working of enqueue and dequeue operation on a Linear
queue.

54 With help of suitable example and diagrams describe working of circular queue and priority
queue

Initial Linked List

Linked List after insertion of 9

55. What is Hashing? Define collision. List and explain different types of collision resolution
techniques

56. What is use of Binary Search Tree? Construct BST for following set of key values.

55,45,30,65,54,32,35,50,61

57. List and explain various types of Linked List with appropriate examples.

58. Write a C Program to implement following operations on Singly Linked List (make all required
declarations)
 i. Insert at Start
ii. Delete at Start
iii. Display

59.List and Explain various applications of Linked List.

60. Sort the following sequence of numbers using Insertion Sort algorithm (Show all the steps of
every pass).

55, 25, 50, 30, 5, 11