You can download Data Structures Part – 6 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.
Stack and Queue
Q. 36 Explain Stack and Queue with suitable examples.
OR
Q.36 Explain LIFO and FIFO Systems with suitable examples.
Ans. : LIFO System :
(i) LIFO system is last-in-first-out system. In this type of system, the element which is inserted at last, will be deleted first.
(ii) Stack is an example of LIFO system. It is a linear system in which insertion and deletion takes place only at one end i.e. top of the list.
(iii) The insertion operation is referred to as push and deletion operation as pop.
e.g. consider a stack of dishes. If we want to add a new dish to this stack then it is added at the top of stack also deletion takes place from the top.
FIFO System :
(i) A FIFO system is first-in-first-out system. In this type of system, the element which is
inserted first in the list will also be deleted first.
(ii) Queue is an example of FIFO system, A queue is a linear list, in which insertion takes
place only at one end of the list known as ‘rear’ of the list and deletion takes place at the other end, called as ‘front’ of the list.
e.g. A queue for tickets in a cinema hall.
Tree
Q. 37 What is a tree ? What do you mean by root, leaf, siblings and child about tree.
Ans : Tree :
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 :
a) There is specially designated node called the root.
b) The remaining nodes are partitioned into n² 0 finite disjoint sets
T1, T2…… Tn where each of these set is tree.
T1, T2, …., In are called ‘subtrees’ of the root.
For e.g. figure shows tree which has 11 nodes, each item of data being a single letter.
Root :
A node which has no parent. Generally first node is called as ‘root node’. In figure, a the node A is the root of the tree.
Leaf :
The node which has no child or children. Such nodes have degree zero. In figure a D, I, F, J, K are the leaf nodes. Also called as terminal node.
Child :
The nodes which are reachable from a node, say u, through a single edge are called the children of u. e.g In figure a, the children of node C are F, G, and H.
Sibling :
Children of the same parent are said to be siblings. e.g. The nodes D and E are both children of node B. So D and E are siblings.
Q. 38 Explain the following terms :
Ans. : 1. Level of tree:
Each node in a tree is assigned a level number. Generally, the level number of root ‘R’ of the tree is zero and every other node is assigned to level number which is one more than the level number of its parent.
It is distance from the root
- Depth / Height :
Depth of the tree as maximum level of any node in a tree. If root is level 0 than depth or height of tree is equal to 1+ largest level number.
e.g. Depth of above tree is 3.
- Degree :
The number of subtrees of a node is called degree of a node.
The degree of a tree is the maximum degree of the node in tree.
e.g. the degree of each node in figure is as
The tree has degree 3.
Q. 39 What is a binary tree ?
Ans. : Binary tree is a finite set of elements called nodes such that is
(1) It may be empty or
(2) It is partitioned into three disjoint subsets :
(a) there is a single distinguished element called the root of tree.
(b) other two subsets are themselves binary tree called left subtree and right subtree of the original tree.
A left and right subtree can be empty.
In binary tree, there is no node with degree greater than two.
e.g.
Q. 40 What is a binary tree ? With a suitable example, explain the terminology describing family relationship between the elements of a binary tree.
Ans :
Binary tree : Please refer Q. No. 39.
Basic terminology : Consider the example :
The binary tree contains 8 nodes (A to H). Root A is at the top of tree.
(1) Left successor : B is left successor of node A.
(2) Right successor : C is right successor of node A.
(3) Left subtree : Left subtree consists of nodes B, D and E.
(4) Right subtree : Right subtree consists of nodes C, F, G and H.
(5) Terminal node : The node with no successors are is called terminal node D. E, H and G are terminal nodes.
(6) Binary tree T1 and T2 are similar if they have same structure.
Any node N ina binary tree T has either 0, 1 or 2 successors.
Q. 41 What is a binary tree ? With a suitable example show the relationship between to, numbers of nodes and depth of a tree.
Ans. : Binary tree : Please refer Q. No. 39.
(i) Relationship between total number of nodes and depth of a tree :
Depth of a tree means maximum level of any node in a tree. Maximum number of node or binary tree with depth n are 2n – 1.
For example :
(ii) Consider the following tree with depth 3.
So with depth 3, the total number of nodes in a given tree is
2n – 1 = 23 -1
= 8-1
= 7
The tree with depth n having 2n – 1 number of total nodes.
Q. 42 Define the following :
Ans :
1. Complete Binary Tree : If all leaf nodes of a binary tree have same level number and every non-leaf node has non-empty left and right subtrees then the tree is called as complete binary tree. All nodes at the last level appears as far left as possible.
2. Extended binary tree or 2-tree:
A binary tree T is said to be a 2-tree or an extended binary tree if each node N has either 0 or 2 children. The nodes with 2 children are called internal node and the nodes with 0 children are called external nodes.
3. Binary Search Tree :
It is a binary tree in which each node N of tree has the property that the value at N is greater than every node value in the left subtree of N and is less than or equal to every node value in the right subtree of N.
Click on DOWNLOAD and Data Structures Part – 6 pdf will start downloading.
-
Can I download Data Structures Part – 6 PDF Free ?
Yes, you can download all TPS Computer Science 12th Pdf for free. Only you need to click on download button and wait for 30 seconds. Your download will start automatically.
-
Unable to download the pdf ?
Please click on the download button and wait for 30 seconds for the downloading link to be generated. After that check your downloads you will get your pdf.
-
Why I am seeing count down timer after clicking on download button ?
Please wait for it to complete and then you will able to download it. You are seeing count down timer for downloading link to be generated.