Data Structures Notes CS-1 Class 12th

 Q.1) Define the following :

a) Traversing :- Traversing means accessing each record (elements) only once so that it can be processed.

b) Searching :- Searching means finding the location of record (element) with given key value or finding all records that satisfies condition.

c) Inserting :- Inserting means adding new record (element) to the structure.

d) Deleting :- Deleting means removing the record (element) from the structure.

e) Sorting :- Sorting means annoying records (elements) in some logical order.

 For example : (i) Arranging names in aplhabitical order.

(ii) Arranging numbers in ascending order.

f) Merging :- Merging means combining the records in two different files into a single file.

How to Gain Free traffic from Guest Posting.

Q.2) What is an algorithm ?

Ans: (i) A algorithm, is a finite step-by-step list of well defined instructions for solving a particular problem.

(ii) It lists for variable and input data.

(iii) It is used as specification for performing calculations and data processing.

Q.3) Define Sequential logic.

Ans: (i) Algorithm consists of modules. Each module js a set of steps.

(ii) In Sequential flow (or sequential logic) the modules are executed one after the other.

Module A 

Module B

Module C

Q.3) Define Conditional flow (or selection logic).

Ans: In conditional flow (or selection logic) one or the other modules is seleted depending on condition.

There are three types :-

(i) Single Alternative :-

This has the form -

If condition, then : 

[Module A]

[End of If structure]

(ii) Double Alternative :-

This has the form -

If condition, then :

[Module A]

ELSE :

[Module B]

[End of IF structure]

(iii) Multiple Alternative :-

This has the form -

If condition (1), then :

[Module A1]

ELSE if condition (2), then :

[Module A2]

..........

ELSE if condition (m), then :

[Module Am]

ELSE :

[Module B]

[End of IF structure]

The logic of this structure allows only one module to be executed.

Q.4) Define Repetitive flow (or Iteration logic).

Ans: Here certain module is executed repeatedly unity condition satisfies. The repeat for loop has the form :

Repeat for K=R to S by T

[Module]

[End of if loop]

The Story of a Faceless Creature

Q.5) Define the following terms :

(i) Data 

Ans: Data are simply values or set of values.

(ii) Group items

Ans: Data items which are divided into subitems are called as group items.

Eg: Data may be divided into three subitems- day, month, and year. So data becomes group item.

(iii) Elementary items

Ans: Data which are not divided into subitems are called as elementary items.

Eg: Pincode number cannot be divided into subitems. So it is elementary item.

(iv) Entity

Ans: An entity is something that has certain attributes or properties which may be assigned values. The values themselves may be numeric of non-numeric.

(v) Field

Ans: Field is a single elementary unit of information representing an attribute of an entity.

(vi) Record

Ans: Record is a collection of field values of given entity.

(vii) File

Ans: A file is a collection of records of the entities in a given entity set.

Q.6) What are linear arrays ?

Ans: A data structure is said to be linear if it's elements form a sequence.

A Linear array is the data structure which consists of finite, ordered set of homogeneous data Elements such that :

a) The elements of the array are refferced respectively by an index set (subscript) consisting of 'n' consecutive numbers.

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

c) The number 'n' of the element is called as length or size of an array.

LENGTH = UB - LV + 1

where, 

UB : the largest index called Upper bound.

LB : the smallest index called Lower bound.

Q.7) What is traversing an array ? Give the algorithm for traversing a linear array.

Ans: Traversing an array means accessing with each element of array only once, so that it can be processed.

• Algorithm :- Traversing a linear array.

Step :1:  [Initiatilize counter]

Set K:= LB

Step :2:  Repeat step 3 and 4 while k ≤ UB :

Step :3:  [Visit element]

Apply PROCESS to LA [K]

Step :4:  [Increment counter]

set K:= K+1

[End of step 2 loop]

Step :5:  Exit

Q.8) Explain Bubble sort algorithm with suitable example.

Ans: • Algorithm :- Bubble sort (DATA, N)

Here DATA is a linear array with N elements. This algorithm sorts elements of DATA in ascending order.

Step :1:  Repeat step 2 and 3 for K:= 1 to n-1 :

Step:2:  Set ptr:= 1

Step :3:  Repeat while Ptr ≤ N-K :

a) If DATA [Ptr] > DATA [Ptr+1], then interchange DATA[Ptr] and DATA[Ptr+1]

[End of IF structure]

b) [Increment pointer]

Set ptr:= ptr + 1

[End of inner loop]

[End of outer loop]

Step :4:  Exit

Q.9) What are the advantages of Binary Search algorithm ?

Ans: (i) Binary Search algorithm is efficient as the search scope gets reduced to half the size of the array, with each interaction. 

(ii) The number if comparison required are approximately equal to log n which are less that linear search.

(iii) Binary search is used to search an element from a sorted array.

Q.10) What are the disadvantages of Binary Search Algorithm ?

Ans: (i) The given list must be sorted.

(ii) The access of the list must be random means the middle elements can be accessed.

(iii) At each iteration, middle entry calculation us required.

Q.11) What is an pointer array ?

Ans: An array is called pointer array, if each element of that array is a pointer.

Q.12) What is an pointer variable ?

Ans: The variable is called as pointer variable, if it's pointers to another variable i.e. it contains the memory address of the other variables.

Q.13) What is a Record ?

Ans: (i) A record is a collection of relative data items, each of which is called as field or attribute.

(ii) Collection of Records is know as files.

(iii) In a record, natural ordering of elements is not possible.

(iv) A record may contain non-homogeneous data.

(v) The elements in record can be described by level numbers.

Q.14) What are linked lists ? Show a linked list with suitable example having six nodes with a properly labelled diagram.

Ans: (i) A linked list is a linear collection of data Elements, called nodes, where the linear order is maintained with the help of pointers.

(ii) Linked list is also called as one-way list.

(iii) Each node in the linked list is divided into two parts.

a) First part is called as INFO part, which contains information about the element or actual element.

b) Second part is called as LINK part, which is next pointer field, i.e. it contains the address of next node in the list.

Linked list with 6 nodes.

Q.15) Explain Stack (or LIPO) with a suitable example.

Ans: • Stack (or LIPO) :-

(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) A stack is a data structure in which items may be added or removed only at one end.

(iii) The insertion operation is reffered to as PUSH and the deletion operation is called as POP.

(iv) A stack is also called as last-in-first out (LIFO) list.

(v) Example: Consider a stack of dishes, if we want to add a new dish to this stack of dishes then, it is added at the top of the stack then it added at the top of stack also deletion takes place from the top.

Q.16) Explain Queue (or FIFO) with a suitable example.

Ans: • Queue (or FIFO) :-

(i) A FIFO system is first-in-first out system. In this type of a system, the element which is inserted first in the list will also be deleted first.

(ii) A Queue is a linear list in which items may be added only at one end and item may be removed only at one end.

(iii) The Queue is also called as first-in-first out (FIFO) list.

(iv) Example: A Queue for the ticket in cinema hall.

Q.17) Define the followings :-

a) Root :-

Ans: A node which has no parent. Generally first node is called as "Root Node".

b) Leaf :-

Ans: The node which has no children or child  Such nodes have degree zero. It is called as terminal node.

c) Child :-

Ans: The nodes which are reachable from a node, through a single edge are called the children.

d) Siblings :-

Ans: Children if the same parent are said to be siblings.

Q.18) What is a Binary Tree ? Draw a digram of Binary Tree.

Ans: Binary tree is a finite set of elements called nodes such that :-

(i) It may be empty.

(ii) It is partitioned into three disjoint subsets :

a) There is a single distinguishing element called the root of the tree.

b) Other two subsets are themselves binary tree called as 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.

Binary Tree 

Q.19) With suitable example, explain the terminology describing family relationship between the elements of a binary tree.

Ans: Basic terminologies :- {refer the above diagram}

The Binary tree contains 9 nodes (A to I)

Root A is at the top of the tree.

(i) Left successor :- B is the left successor of node A.

(ii) Right successor :- C is the right successor of node A.

(iii) Left subtree :- Left subtree consists of node B,E, and D.

(iv) Right subtree :- Right subtree consists of node C,F,H,G and I.

(v) Terminal node :- The node with no succesors is called as terminal node. D,E,H,G,I are terminal nodes.

Q.20) Define tree.

Ans: Tree is a non-linear hierarchical data structure which consists of finite set of one or more nodes.

(i) There is specially designed node called The Root.

(ii) The remaining nodes are partitioned into finite disjoint set T1,T2,T3,........,Tn, where each of these sets is tree.

Note:- If you want notes on any other topics/chapters or any other content please feel free to tell in the comment section.