lOMoARcPSD|38907382

Ds - Ggvvg

Computer science (Chhatrapati Shivaji Maharaj University)

Scan to open on Studocu

Studocu is not sponsored or endorsed by any college or university

Downloaded by Dipali Aalone (dipalikasunde3@[Link])
 lOMoARcPSD|38907382

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

Downloaded by Dipali Aalone (dipalikasunde3@[Link])

 lOMoARcPSD|38907382

[Link] 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
Downloaded by Dipali Aalone (dipalikasunde3@[Link])
 lOMoARcPSD|38907382

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

[Link] 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
Downloaded by Dipali Aalone (dipalikasunde3@[Link])
 lOMoARcPSD|38907382

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

[Link] 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

[Link] merge sort on an array of size n which is already sorted is

A. O(n)
B. O(nlogn)

Downloaded by Dipali Aalone (dipalikasunde3@[Link])

 lOMoARcPSD|38907382

C O(n2)
D None

[Link] 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
[Link] 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

Downloaded by Dipali Aalone (dipalikasunde3@[Link])

 lOMoARcPSD|38907382

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
Downloaded by Dipali Aalone (dipalikasunde3@[Link])
 lOMoARcPSD|38907382

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

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

A. AB+ CD*E - FG /**
B. AB + CD* E - F **G /
[Link] + 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

Downloaded by Dipali Aalone (dipalikasunde3@[Link])
 lOMoARcPSD|38907382

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

[Link] is also called as

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

[Link] 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

[Link] 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

[Link] 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

[Link] 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
Downloaded by Dipali Aalone (dipalikasunde3@[Link])
 lOMoARcPSD|38907382

B) True, True, False

C) True, True, True
D) False, True, True

[Link] 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

[Link] number of comparisons done by sequential search is ………………

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

[Link] .............. , 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

[Link] 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
Downloaded by Dipali Aalone (dipalikasunde3@[Link])
 lOMoARcPSD|38907382

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

[Link] 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

[Link] 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

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

[Link] of the following is not the type of queue?

A) Ordinary queue
B) Single ended queue
C) Circular queue
Downloaded by Dipali Aalone (dipalikasunde3@[Link])
 lOMoARcPSD|38907382

D) Priority queue

[Link] 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

[Link] 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

[Link] 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

[Link] 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

[Link] is/are the application(s) of stack

A) Function calls
B) Large number Arithmetic
C) Evaluation of arithmetic expressions
D) All of the above
Downloaded by Dipali Aalone (dipalikasunde3@[Link])
 lOMoARcPSD|38907382

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

[Link] 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.
[Link].
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.
Downloaded by Dipali Aalone (dipalikasunde3@[Link])
 lOMoARcPSD|38907382

12. Sort the following given numbers using Radix Sort Technique. 6,5,3,1,8,7,2,4
[Link] 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.

[Link] between DFS and BFS
[Link] tree traversal techniques with example.
1. Inorder [Link] 3. Postorder
[Link] 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
[Link] and explain the Asymptotic Notations for analysis of Algorithms.
[Link] the following operations on the circular linked list :
[Link].
[Link].
[Link]

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
Downloaded by Dipali Aalone (dipalikasunde3@[Link])
 lOMoARcPSD|38907382

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

[Link] 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.

[Link] B Tree and Construct B Tree of order 4 for given numbers

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

[Link] 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

[Link] 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.

Downloaded by Dipali Aalone (dipalikasunde3@[Link])

 lOMoARcPSD|38907382

[Link] the algorithms for insertion and deletion operations on circular queue

[Link] a C Program or Pseudo Code for implementation of Stack using singly linked list

[Link] 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.

[Link] different types of time complexity like constant, linear, etc.

[Link] is algorithm? Describe in detail time and space complexity

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

[Link] 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

[Link] 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)
Downloaded by Dipali Aalone (dipalikasunde3@[Link])
 lOMoARcPSD|38907382

i. Insert at Start
ii. Delete at Start
iii. Display

[Link] 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

Downloaded by Dipali Aalone (dipalikasunde3@[Link])