Data Structures Part – 7 | Class 12th Free PDF Download

You can download Data Structures Part – 7 tps computer science class 12th pdf for free by click on download button given below.

Probable Marks in board exam: 17
Above probable marks means : In board exam questions asked form this chapter are nearly for 17 marks out of 50 Marks.

Scope of the Syllabus

• Introduction to data structures.
• Data structure operations.
• Algorithmic notations.
• Control structures.
• Arrays-Representation in memory, Traversing, Deleting, Sorting, Binary search in an array, Pointer arrays, Records in memory using array.
• Linked list – Representation in memory
• Trees, Binary trees – Representing binary tree in memory.

Q. 43 How binary trees are represented in memory ?

  Asked in Board Exam   (Mar.2015) (March 2003, 2009)     Important  

With suitable example and labelled diagram, show the representation of binary tree in memory.

Ans : A binary tree T can be represented in memory by two types of representation :
(i) Linked representation
(ii) Sequential representation.

(i) Linked representation :

  Asked in Board Exam  (Oct. 2008,15)     Important  

Linked representation uses three parallel arrays INFO and, LEFT and RIGHT and a pointer variable ROOT such that for an index K, INFO [K] contains actual element, LEFT [K] contains address of the Jeft child and RIGHT [K] contains address of right child.

e.g. Consider a binary tree as below :

The ROOT stores address of first node of tree T.

AVAL stores address of first null node. To insert another node to tree T, it is inserted memory location pointed by AVAIL.

Note : In above example, to insert an element K, then it will be inserted at INFO [10]. After insertion LEFT [10] and RIGHT [10] will contain zero (null pointer) and AVAIL will contain 8 i.e. next element is to be inserted at 8.

(ii) Sequential representation :
For sequential representation, only one linear array is used. This array is generally known as TREE such that :

(a) The root R of the tree is stored in TREE [1].

(b) If a node N of tree stored in TREE [K], then, its left successor is stored in TREE [2*K] and right successor is stored in TREE [(2*K) +1]
e.g. Consider a binary tree as follows :

This tree can be represented in memory as,

In general, the sequential representation of a tree with depth d will require an array with approximately 2^d+1 elements

---

Q. 44 Each store in a chain sends in a weekly record of its sales according to the following structure 01 Store, 02 Hardware, 02 Clothing, 03 Men, 03 Women, 03 Children 04 Boys, 04 Girls, 02 Drugs, 03 Prescription, 03 Nonprescription, 02 Stationary.

1. Draw the appropriate tree diagram.
2. How many elementary items are there ?
3. How many group items.are there ?

Ans : 1. The tree diagram is as follows :

Elementary items are those all nodes which have no children under given group. The above tree has 8 elementary items as :

Hardware, Men, Women, Boys, Girls, Prescription, Nonprescription, Stationary.

Group items are those all nodes having children excluding root.

The above tree has 3 group items as –
Clothing
Children
Drugs.

---

Q 45. Explain the following data structures with suitable diagram.

(a) Linear array (b) Linked list (c) Tree

  Asked in Board Exam   (March 2003,08,11,12,15; Oct. 2006)     Important  

Ans. : (a) Linear array :

A linear array is the data structure which consists of finite ordered set of homogeneous data elements such that :

(i) The elements of the array are referenced respectively by an index set consisting or consecutive numbers.

(ii) The elements of the array are stored respectively in successive memory locations.

(ii) The number n of the elements is called length of size or array.

For e.g. let DATA be 5 elements linear array as follows :

(b) Linked list

(i) A linked list is a linear collection of data elements called nodes where the linear order’s maintained with the help of pointers.

(ii) Each node in the linked list is divided into two parts. First part is called as INFO part which contains the information about the element or actual element and second part is called as LINK part which is next pointer field i.e, it contains the address of next node in the list.

(iii)

(c) Tree:

  Asked in Board Exam   (Oct. 2006)     Important  

Tree is a non-linear hierarchical data structure which consists of finite set of one or more nodes (i.e. collected data items such that :

(i) There is specially designated node called the root.
(ii) The remaining nodes are partitioned into n Z 0 finite disjoint sets T1, T2, …., In where each of these set is tree.

T1, T2, ……. , In are called ‘subtree’ of the root.

Click on DOWNLOAD and Data Structures Part – 7 pdf will start downloading.

Important Links

Data Structures Part – 1

Data Structures Part – 2

Data Structures Part – 3

Data Structures Part – 4

Data Structures Part – 5

Data Structures Part – 6

Data Structures Part – 7

Data Structures Part – MCQ