Click on Subject/Paper under Semester to enter.

Probability and Environmental Sciences

Professional English complex function - and Sustainability -
Professional English - - II - HS3252 MA3303 GE3451
I - HS3152
Statistics and Electromagnetic Transmission and
Matrices and Calculus Numerical Methods - Theory - EE3301 Distribution - EE3401

4th Semester
3rd Semester

- MA3151 MA3251
1st Semester

2nd Semester

Digital Logic Circuits - Linear Integrated

Engineering Physics - Engineering Graphics EE3302 Circuits - EE3402
PH3151 - GE3251
Measurements and
Electron Devices and Instrumentation -
Engineering Chemistry Physics for Electrical Circuits - EC3301 EE3403
- CY3151 Engg - PH3202
Microprocessor and
Electrical Machines I - Microcontroller -
Basic Civil and
EE3303 EE3404
Problem Solving and Mechanical Engg -
Python Programming - BE3255
C Programming and Electrical Machines II
GE3151
Electric Circuit Data Structures - - EE3405
Analysis - EE3251 CS3353

Power System Analysis

High Voltage
- EE3501
Engineering - EE3701
Protection and
Switchgear - EE3601
Power Electronics - Human Values and
5th Semester

EE3591 Ethics - GE3791

8th Semester
7th Semester
6th Semester

Power System
Operation and Control
Control Systems - - EE3602 Open Elective 2
EE3503 Project Work /
Open Elective-1
Open Elective 3 Intership
Elective 1 Elective-4
Open Elective 4
Elective 2 Elective-5
Elective 7
Elective 3 Elective-6
Management Elective
 All EEE Engg Subjects - [ B.E., M.E., ] (Click on Subjects to enter)
Circuit Theory Digital Logic Circuits Electromagnetic Theory
Environmental Science and Linear Integrated Circuits Discrete Time Systems and
Engineering and Applications Signal Processing
Electronic Devices and Electrical Machines I Electrical Machines II
Circuits
Power Plant Engineering Special Electrical Machines Transmission and Distribution
Power System Analysis Control Systems Power Electronics
Power System Operation Measurements and Design of Electrical Machines
and Control Instrumentation
Communication Engineering Solid State Drives Embedded Systems
Power Quality High Voltage Engineering Protection and Switchgear
Flexible AC Transmission Microprocessors and Electric Energy Generation,
Systems Microcontrollers Utilization and Conservation
Professional Ethics in Physics for Electronics Basic Civil and Mechanical
Engineering Engineering Engineering
Transforms and Partial Environmental Science and Problem Solving and Python
Differential Equations Engineering Programming
Engineering Physics Engineering Chemistry Numerical Methods
Engineering Graphics Technical English Object Oriented Programming
Principles of Management Total Quality Management
 www.BrainKart.com
4931_Grace College of Engineering, Thoothukudi

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

BE- Electrical and Electronics Engineering

&
BE- Electronics and Communication Engineering

Anna University Regulation: 2021

CS3353 - C Programming and Data Structures

II Year/III Semester

Question Bank

Unit- IV NON-LINEAR DATA STRUCTURES

Prepared By,

Ms. S. Abarna, AP/CSE

CS3353_CPDS

https://play.google.com/store/apps/details?id=info.therithal.brainkart.annauniversitynotes&hl=en_IN
 www.BrainKart.com
4931_Grace College of Engineering, Thoothukudi

CS3353- C Programming and Data Structures

UNIT IV NON-LINEAR DATA STRUCTURES

Trees – Binary Trees – Tree Traversals – Expression Trees – Binary Search Tree – Hashing -
Hash Functions – Separate Chaining – Open Addressing – Linear Probing– Quadratic Probing –
Double Hashing – Rehashing.
UNIT-IV/ PART-A
1 Define Tree. Give an example.
A Tree is a collection of one or more nodes with a distinct node called the root, while
remaining nodes are partitioned as T1 ,T2, ..,Tk , K≥ 0 each of which are sub trees, the
edges of T1,T2,…,Tk are connected the root.

Example : directory structure hierarchy

2 Give some applications of Trees.
 Implementing the file system of several operating systems.
 Evaluation of arithmetic expression.
 Set representation.
 Gaming/Decision making problems.
3 Define node, degree, siblings, depth/height, level.(Nov/Dec 19)
 Node: A node is an item of information with branches to other items.
 Degree: The number of subtrees of a node is called is degree.
 Siblings: The children of the same parent is said to be siblings.
 Level: The level of a node is defined recursively by assuming the level of the root to
be one and if a node is at level l, then its children at level l+1.
 Depth/Height: The depth/height of a tree is defined to be the level of a node which is
maximum.
4 Write the routine for node declaration in trees.
typedef struct TreeNode , *PtrToNode;
struct TreeNode
{ ElementType Element;
PtrToNode FirstChild;
PtrToNode NextSibling;
};

22

CS3353_CPDS

https://play.google.com/store/apps/details?id=info.therithal.brainkart.annauniversitynotes&hl=en_IN
 www.BrainKart.com
4931_Grace College of Engineering, Thoothukudi

CS3353- C Programming and Data Structures

5 Define a path in a tree.
A path in a tree is a sequence of distinct nodes in which successive nodes are connected
by edges in the tree.

The path from A-H is A-C-G-H

6 Define terminal and nonterminal nodes in a tree
 A node which has no children is called a terminal node. It is also referred as a leaf
node. These nodes have a degree as zero.
 All intermediate nodes that traverse the given tree from its root node to the terminal
nodes are referred as terminal nodes.
7 Define a Binary Tree ADT with an example.
A Binary Tree is a tree, which has nodes either empty or not more than two child nodes,
each of which may be a leaf node.

8 Define a full binary tree.

A full binary tree, is a tree in which all the leaves are on the same level and every non-
leaf node has exactly two children.
9 Define a complete binary tree.
A complete binary tree is a tree in which every non-leaf node has exactly two children
not necessarily to be on the same level.
10 State the properties of a Binary Tree.
 Maximum No. of nodes on level n of a binary tree is 2^(n-1),where n>=1.
 Maximum No. of nodes in a Binary tree of height is 2^(n-1),where n>=1.
 For any non-empty tree, nl=nd+1 where nl is the number of leaf nodes and nd is the
no. of nodes of degree 2.
11 What are the different ways of representing a Binary Tree?
 Linear Representation using Arrays.
 Linked Representation using Pointers.
12 Define Traversal.
Traversal is an operation which can be performed on a binary tree is visiting all the nodes
exactly once.
 In order: traversing the LST, visiting the root and finally traversing the RST.
 Preorder: visiting root, traversing LST and finally traversing RST.
 Post- order: traversing LST, then RST and finally visiting root.

23

CS3353_CPDS

https://play.google.com/store/apps/details?id=info.therithal.brainkart.annauniversitynotes&hl=en_IN
 www.BrainKart.com
4931_Grace College of Engineering, Thoothukudi

CS3353- C Programming and Data Structures

13 Define a Binary Search Tree. (Dec 19)
A Binary Search Tree is a special binary tree, which is either empty or if it is empty it
should satisfy the conditions given below:
 Every node has a value and no two nodes should have the same value (Values
should be distinct).
 The value in any left subtree is less than the value of its parent node.
 The value in any right subtree is greater than the value of its parent node.

14 Define Threaded Binary tree.

A Threaded Binary Tree is a binary tree in which every node that does not have a right
child has a THREAD (in actual sense, a link) to its INORDER successor. By doing this
threading we avoid the recursive method of traversing a Tree, which makes use of stacks
and consumes a lot of memory and time.
15 Define Forest.
A forest is a collection on N(N>0) disjoint tree or group of trees. If the root is removed
from the tree that tree becomes a forest.
Uses:
 Forest data structure finds great use in data science.
 Social networking websites.
 Operating system storage
 Big Data
16 Perform inorder, preorder and postorder traversal for the given tree.

24

CS3353_CPDS

https://play.google.com/store/apps/details?id=info.therithal.brainkart.annauniversitynotes&hl=en_IN
 www.BrainKart.com
4931_Grace College of Engineering, Thoothukudi

CS3353- C Programming and Data Structures

17 Draw the expression tree for the given postfix expression using stack.
AB*C+

18 Define balanced search tree. (Dec 13)

Balanced search tree have the structure of binary tree and obey binary search tree
properties with that it always maintains the height as O(log n) by means of a special kind
of rotations.
E.g. AVL, Splay, B-tree.
19 Define AVL tree. (Dec 13)
An empty tree is height balanced. If T is a non-empty binary tree with TL and TR as its left
and right subtrees, then T is height balanced if
1. TL and TR are height balanced.
2. | hL - hR | ≤ 1.
Where hl and hr are the height of TL and TR respectively.
20 What are the drawbacks of AVL trees?
The drawbacks of AVL trees are
 Frequent rotations
 The need to maintain balances for the tree’s nodes
 Overall complexity, especially of the deletion operation.
21 What are the two alternatives that are used to construct a heap?
The two alternatives to construct a heap are
 Bottom-up heap construction
 Top-down heap construction

25

CS3353_CPDS

https://play.google.com/store/apps/details?id=info.therithal.brainkart.annauniversitynotes&hl=en_IN
 www.BrainKart.com
4931_Grace College of Engineering, Thoothukudi

CS3353- C Programming and Data Structures

22 What is the main use of heap?
Heaps are especially suitable for implementing priority queues. Priority queue is a set of
items with orderable characteristic called an item’s priority, with the following
operations
 Finding an item with the highest priority
 Deleting an item with highest priority
 Adding a new item to the set.
23 Give three properties of heaps?
The properties of heap are
 There exists exactly one essentially complete binary tree with ‘n’ nodes. Its height
is equal to log2n
 The root of the heap is always the largest element
 A node of a heap considered with all its descendants is also a heap
24 Give the main property of a heap that is implemented as an array.
A heap can be implemented as an array by recording its elements in the top-down, left- to-
right fashion. It is convenient to store the heap’s elements in positions 1 through n of such
an array. In such a representation
 The parental node keys will be in the first n/2 positions of the array, while the leaf
keys will occupy the last n/2 positions
 The children of a key in the array’s parental position ‘i’ (1  i  n/2) will be in
positions 2i and 2i+1and correspondingly, the parent of the key in position ‘i’
(2  i  n) will be in position i/2.
25 Define binary heaps.
A binary heap is a heap data structure created using a binary tree. It can be seen as a
binary tree with two additional constraints:
 The shape property: the tree is an almost complete binary tree; that is, all levels of
the tree, except possibly the last one (deepest) are fully filled, and, if the last level
of the tree is not complete, the nodes of that level are filled from left to right.
 The heap property: each node is greater than or equal to each of its children
according to some comparison predicate which is fixed for the entire DS.
26 What is a heap? Or Illustrate Heap Data Structure. (Dec 20)
A heap is a partially ordered data structure, and can be defined as a binary tree assigned
to its nodes, one key per node, provided the following two conditions are met
 The tree’s shape requirement-The binary tree is essentially complete, that is all the
leaves are full except possibly the last level, where only some rightmost leaves will
be missing.
 The parental dominance requirement-The key at each node is greater that or equal
to the keys of its children.
27 Define Min-heap and Max-heap.
 Min-heap: A min-heap is a mirror image of the heap structure. It is a complete binary
tree in which every element is less than or equal to its children. So the root of the min-
heap contains the smallest element.
 Max-heap: A heap in which the parent has a larger key that the child’s key values
then it is called Max-heap
26

CS3353_CPDS

https://play.google.com/store/apps/details?id=info.therithal.brainkart.annauniversitynotes&hl=en_IN
 www.BrainKart.com
4931_Grace College of Engineering, Thoothukudi

CS3353- C Programming and Data Structures

28 Define B-tree? (Dec 15, May 16)
A B-tree of order m in an m-way search tree that is either empty or is of height ≥1 and
 The root node has at least 2 children
 All nodes other than the root node and failure nodes have at least m/2 children.
 All failure nodes are at same level.
29 Explain AVL rotation. Mention the two types of rotations (Dec 13)
Some modifications done on AVL tree in order to rebalance it is called Rotation of AVL
tree. Two types of rotation are
1. single rotation
 Left-Left Rotation
 Right-Right Rotation
2. Double rotation.
 Left-Right Rotation
 Right-Left Rotation
30 Define Priority Queue?
Priority queue is a specialized data structure in which the elements are organized
according to the priorities of some key value.
31 Define splay tree.
A splay tree is a binary search tree in which restructuring is done using a scheme called
splay. A splay is heuristic method which moves a given vertex v to the roof of the splay
tree using a sequence of rotations.
32 Show the result of inorder traversal of the binary search tree given in figure. (Nov 18)

Inorder Traversal – 1 2 3 4 5 6 7 9
33 For the tree in Figure .
(a) List the siblings for node E
(b) Compute the height. (Nov 18)

List the siblings for node E = D

Compute the height = 3

27

CS3353_CPDS

https://play.google.com/store/apps/details?id=info.therithal.brainkart.annauniversitynotes&hl=en_IN
 www.BrainKart.com
4931_Grace College of Engineering, Thoothukudi

CS3353- C Programming and Data Structures

34 The depth of complete binary tree is 8 compute the number of nodes in leaf. (May 19)
Nodes at depth d in a perfect binary tree = 2d
Nodes at depth d in a perfect binary tree = 28 = 256 leaf nodes
35 How to resolve dangling threads in binary tree? Illustrate.(Dec 20)
The linked representation of any binary tree has more null links than actual pointers. If
there are 2n total links, there are n+1 null links. A clever way to make use of these null
links has been devised by A.J. Perlis and C. Thornton. Their idea is to replace the null
links by pointers called Threads to other nodes in the tree. If the RCHILD (p) is normally
equal to zero, we will replace it by a pointer to the node which would be printed after P
when traversing the tree in inorder. A null LCHILD link at node P is replaced by a
pointer to the node which immediately precedes node P in inorder.
UNIT-IV / PART-B
1 a) What are the types of representation of binary tree?
b) Show that for the perfect binary tree of height h containing 2h+1-1nodes
2 What is traversal? Give an algorithm for traversal in the binary tree. Or Explain the tree
traversal techniques with an example. (Dec 19)
3 Draw a Binary search tree for the following input list 60,25,75,15,50,66,33, 44. Trace the
algorithm to delete the nodes 25, 75, 44 from the tree.
4 Write a routine to implement the basic binary search tree operations. Or How to insert
and delete an element into a binary search tree and write down the code for the insertion
routine with an example. (Dec 19)
5 Explain in detail about Threaded binary trees.
6 Write the algorithm to construction an expression tree and construction an expression
tree for the input ab+cde+**.
7 Show the result of inserting 10,12,1,14,6,5,8,15,3,9,7,4,11,13, and, 2, one at a time, in to an
initially empty binary heap.
8 Write and test a program that performs the operation Insert, DeleteMin, Build Heap,
Findmin, DecreaseKey, Delete, and IncreaseKey in a binary Heap.
9 Show the result of inserting 2, 4,1,5,9,3,6,7 in to an initially empty AVL Tree.
10 Write a procedure to implement AVL single and double rotations.
11 Write a routine to perform insertion and deletion in B-Tree.
12 Explain in detail about splay trees and its rotations with example.
13 Construct the heap for the following array structure and write a procedure to perform
percolate up and percolate down in a binary heap.
5 19 8 37 75 55 14 22 43 4
14 Distinguish between B Tree and B+ Tree.
Create a B tree of order 5 by inserting the following elements: 3, 14, 7, 1, 8, 5, 11, 17, 13, 6,
23, 12, 20, 26, 4, 16, 18, 24, 25 and 19. (Nov 18)
15 Write the following routines to implement the basic binary search tree operations. (Nov 18)
i) Perform search operation in binary search tree.
ii) Find_min and Find_max

28

CS3353_CPDS

https://play.google.com/store/apps/details?id=info.therithal.brainkart.annauniversitynotes&hl=en_IN
 www.BrainKart.com
4931_Grace College of Engineering, Thoothukudi

CS3353- C Programming and Data Structures

16 i) Write a routine for post order traversal. Is it possible to find minimum and
maximum value in the binary search tree using traversals? Discuss
ii) Display the given tree using Inorder, Preorder, Postorder traversals.
iii) Delete 11 and 10 from the above binary search tree. And display the tree after each
deletion (May 19)

17 i) Write a routine for AVL tree insertion. Insert the following elements in the empty
tree and how do you balance the tree after each element insertion? Elements :
2,5,4,6,7,9,8,3,1,10.
ii) Discuss about B+ tree. And discuss the applications of heap. (May 19)
i) Write C functions to perform deletion in Binary search tree (Include all the cases)
ii) Construct a binary search tree for the values 45, 56, 39, 12, 34, 32, 10, 78, 67, 89, 91.
Give the pre order and post order traversal of the resultant binary search tree.(Dec 20)
18 Construct B tree to insert the following key elements with order 5. 2, 14, 12, 4, 22, 8, 16,
26, 20, 10, 38, 18, 36, 48, 6, 24, 28, 40, 42, 32. (Dec 20)
19 i) Compare B trees with B+ trees.
ii) Create a B+ tree of order 5 for the following data arriving in sequence :
90, 27, 7, 9, 18, 21, 3, 4, 16, 11, 21, 72 (Dec 20)

29

CS3353_CPDS

https://play.google.com/store/apps/details?id=info.therithal.brainkart.annauniversitynotes&hl=en_IN
 Click on Subject/Paper under Semester to enter.
Random Process and Electromagnetic
Professional English Linear Algebra -
Professional English - - II - HS3252 Fields - EC3452
MA3355
I - HS3152
C Programming and Networks and
Statistics and
Data Structures - Security - EC3401
Matrices and Calculus Numerical Methods -
CS3353
- MA3151 MA3251
1st Semester

3rd Semester

Linear Integrated

4th Semester
2nd Semester

Signals and Systems - Circuits - EC3451

Engineering Physics - Engineering Graphics
- GE3251 EC3354
PH3151 Digital Signal
Processing - EC3492
Physics for Electronic Devices and
Engineering Chemistry Electronics Engg - Circuits - EC3353
- CY3151 PH3254 Communication
Systems - EC3491
Control Systems -
Basic Electrical & EC3351
Problem Solving and Instru Engg - BE3254 Environmental
Python Programming - Sciences and
GE3151 Digital Systems Design Sustainability -
Circuit Analysis - - EC3352 GE3451
EC3251

Wireless
Communication -
EC3501 Embedded Systems
and IOT Design -
ET3491
VLSI and Chip Design
5th Semester

- EC3552 Human Values and

7th Semester

8th Semester
6th Semester

Artificial Intelligence Ethics - GE3791

and Machine Learning
Transmission Lines and - CS3491
RF Systems - EC3551 Open Elective 2 Project Work /
Intership
Open Elective-1 Open Elective 3
Elective 1
Elective-4
Open Elective 4
Elective 2
Elective-5
Elective 3
Elective-6
 All ECE Engg Subjects - [ B.E., M.E., ] (Click on Subjects to enter)
Circuit Analysis Digital Electronics Communication Theory
Basic Electrical and Electrical Engineering and Principles of Digital
Instrumentation Engineering Instrumentation Signal Processing
Electronic Devices Linear Integrated Circuits Signals and Systems
Electronic Circuits I Electronic Circuits II Digital Communication
Transmission Lines and Wave Control System Engineering Microprocessors and
Guides Microcontrollers
Computer Architecture Computer Networks Operating Systems
RF and Microwave Engineering Medical Electronics VLSI Design
Optical Communication and Embedded and Real Time Cryptography and
Networks Systems Network Security
Probability and Random Transforms and Partial Physics for Electronics
Processes Differential Equations Engineering
Engineering Physics Engineering Chemistry Engineering Graphics
Problem Solving and Python Object Oriented Programming Environmental Science
Programming and Data Structures and Engineering
Principles of Management Technical English Total Quality
Management
Professional Ethics in Engineering Mathematics I Engineering Mathematics
Engineering II
 Click on Subject/Paper under Semester to enter.
Probability and Environmental Sciences
Professional English complex function - and Sustainability -
Professional English - - II - HS3252 MA3303 GE3451
I - HS3152
Statistics and Electromagnetic Transmission and
Matrices and Calculus Numerical Methods - Theory - EE3301 Distribution - EE3401

4th Semester
3rd Semester

- MA3151 MA3251
1st Semester

2nd Semester

Digital Logic Circuits - Linear Integrated

Engineering Physics - Engineering Graphics EE3302 Circuits - EE3402
PH3151 - GE3251
Measurements and
Electron Devices and Instrumentation -
Engineering Chemistry Physics for Electrical Circuits - EC3301 EE3403
- CY3151 Engg - PH3202
Microprocessor and
Electrical Machines I - Microcontroller -
Basic Civil and
EE3303 EE3404
Problem Solving and Mechanical Engg -
Python Programming - BE3255
C Programming and Electrical Machines II
GE3151
Electric Circuit Data Structures - - EE3405
Analysis - EE3251 CS3353

Power System Analysis

High Voltage
- EE3501
Engineering - EE3701
Protection and
Switchgear - EE3601
Power Electronics - Human Values and
5th Semester

EE3591 Ethics - GE3791

8th Semester
7th Semester
6th Semester

Power System
Operation and Control
Control Systems - - EE3602 Open Elective 2
EE3503 Project Work /
Open Elective-1
Open Elective 3 Intership
Elective 1 Elective-4
Open Elective 4
Elective 2 Elective-5
Elective 7
Elective 3 Elective-6
Management Elective
 All EEE Engg Subjects - [ B.E., M.E., ] (Click on Subjects to enter)
Circuit Theory Digital Logic Circuits Electromagnetic Theory
Environmental Science and Linear Integrated Circuits Discrete Time Systems and
Engineering and Applications Signal Processing
Electronic Devices and Electrical Machines I Electrical Machines II
Circuits
Power Plant Engineering Special Electrical Machines Transmission and Distribution
Power System Analysis Control Systems Power Electronics
Power System Operation Measurements and Design of Electrical Machines
and Control Instrumentation
Communication Engineering Solid State Drives Embedded Systems
Power Quality High Voltage Engineering Protection and Switchgear
Flexible AC Transmission Microprocessors and Electric Energy Generation,
Systems Microcontrollers Utilization and Conservation
Professional Ethics in Physics for Electronics Basic Civil and Mechanical
Engineering Engineering Engineering
Transforms and Partial Environmental Science and Problem Solving and Python
Differential Equations Engineering Programming
Engineering Physics Engineering Chemistry Numerical Methods
Engineering Graphics Technical English Object Oriented Programming
Principles of Management Total Quality Management