Please refer to Data structures Class 12 Computer Science Notes and important questions below. The Class 12 Computer Science Chapter wise notes have been prepared based on the latest syllabus issued for the current academic year by CBSE. Students should revise these notes and go through important Class 12 Computer Science examination questions given below to obtain better marks in exams
Data structures Class 12 Computer Science Notes and Questions
The below Class 12 Data structures notes have been designed by expert Computer Science teachers. These will help you a lot to understand all the important topics given in your NCERT Class 12 Computer Science textbook. Refer to Chapter 2 Data structures Notes below which have been designed as per the latest syllabus issued by CBSE and will be very useful for upcoming examinations to help clear your concepts and get better marks in examinations.
Learning Outcomes: Learn basic data structures: lists, stacks, and queues.
- The logical or mathematical model of a particular organization of data is called data structure. It is a way of storing, accessing, manipulating data.
- Types of data structure:
- Operation on data structure:
- Traversing: Accessing each record exactly once.
- Insertion: Adding a new element to the structure.
- Deletion: Removing element from the structure.
- Searching: Search the element in a structure.
- Sorting: Arrange the elements in ascending and descending order.
- Merging: Joining two data structures of same type.
- List:An array or list is the collection of elements in ordered way.
- There are two types of arrays:
- One dimensional list (1-D Lists)
- Multi-dimensional list (Nested Lists)
Traversing 1-D array (List):
- Inserting Element in a list: There are two ways to insert an element in a list:
- If the array is not sorted
- If the array is sorted
- If the array is not sorted: In this case, enter the element at any position using insert( ) function or add the element in the last of the array using append( ) function.
Example:
L=[15,8,25,45,13,19]
L.insert(3, 88) # insert element at the index 3 print(L)
Output:
[15, 8, 25, 88, 45, 13, 19]
• If the array is sorted: In this case, import bisect module and use the functions bisect( ) and insort( ). bisect( ) : identifies the correct index for the element and returns the index. insort( ): Inserts the element in the list in its correct order.
• Deletion of an element from a List: To delete an element from a list we can use remove( ) or pop( ) method.
Example:
L=[10,15,35,12,38,74,12]
print(“List Before deletion of element: “, L)
val=int(input(“Enter the element that you want to delete: “))
L.remove(val)
print(“After deletion the element”, val,”the list is: “, L)
OUTPUT:
List Before deletion of element: [10, 15, 35, 12, 38, 74, 12]
Enter the element that you want to delete: 12
After deletion the element 12 the list is: [10, 15, 35, 38, 74, 12]
- Searching in a List: There are two types of searching techniques we can use to search an element in a list. These are:
- Linear Search
- Binary Search
(i) Linear Search: It is a simple searching technique.
Program:
L=eval(input(“Enter the elements: “))
n=len(L)
item=eval(input(“Enter the element that you want to search : “))
for i in range(n):
if L[i]==item:
print(“Element found at the position :”, i+1)
break
else:
print(“Element not Found”)
Output:
Enter the elements: 56,78,98,23,11,77,44,23,65
Enter the element that you want to search : 23
Element found at the position : 4
(ii) Binary Search: (Theory already discussed in the chapter recursion).
Program:
def BinarySearch(LIST,n,item):
LB=0
UB=n-1
while LB<=UB:
mid=int((LB+UB)/2)
if item<LIST[mid]:
UB=mid-1
elif item>LIST[mid]:
LB=mid+1
else:
return mid
else:
return -1
L=eval(input(“Enter the elements in sorted order: “))
size=len(L)
element=int(input(“Enter the element that you want to search :”))
found=BinarySearch(L,size,element)
if found>=0:
print(element, “Found at the position : “,found+1)
else:
print(“Element not present in the list”)
OUTPUT:
Enter the elements in sorted order: [1,2,3,4]
Enter the element that you want to search :3
3 Found at the position : 3
| Linear Search | Binary Search |
| Access of elements sequentially. | Access of elements randomly. |
| Elements may or may not be in sorted order. | Elements must be in sorted order i.e. ascending or descending order |
| Takes more time to search an element. | Takes less time to search an element. |
| easy | tricky |
| Efficient for small array. | Efficient for larger array |
• Sorting: To arrange the elements in ascending or descending order. There are many sorting techniques.
Program:
L=eval(input(“Enter the elements:”))
n=len(L)
for p in range(0,n-1):
for i in range(0,n-1):
if L[i]>L[i+1]:
L[i], L[i+1] = L[i+1],L[i]
print(“The sorted list is : “, L)
OUTPUT:
Enter the elements:[60, 24, 8, 90, 45, 87, 12, 77]
The sorted list is : [8, 12, 24, 45, 60, 77, 87, 90]
♦ Stack:It is a linear data structure.
♦ Stack is a list of elements in which an element may be inserted or deleted only at one end, called the TOP of the stack.
♦ It follows the principle Last In First Out (LIFO).
♦ There are two basic operations associated with stack:
♦ Push : Insert the element in stack
♦ Pop : Delete the element from stack
- Menu based programme for stack:
S=[]
from os import system
#menu display
def menu():
ch=0
while(ch<1 or ch>4):
#print (“\n”*100)
anyvar=system(‘cls’)
print (“\n\n\n\n\n”)
print (“\t\t\t1: PUSH”)
print (“\t\t\t2: POP”)
print (“\t\t\t3: DISPLAY”)
print (“\t\t\t4: EXIT”)
ch=int(input(“\n\t\t\tEnter a choise (1-4):”))
return ch
def push():
#code to push an item
item=int(input(“\t\t\tEnter an item to push: “))
S.append(item)
print (“\t\t\tITEM ” , item ,” PUSHESD IN THE STACK”)
def pop():
#code to pop from stack
if (S==[]):
print (“\t\t\tNO ITEM TO POP”)
else:
item=S.pop()
print (“\t\t\tITEM ” , item ,” POPPED FROM THE STACK”)
def display():
#code to display stack
if (S==[]):
print (“\t\t\tEMPTY STACK”)
else:
print (“\t\t\t”,)
for i in S:
print( i ,’ ‘,end=””)
#code to call all functions
import sys
ch=0
while(ch!=4):
ch=menu()
if(ch==1):
push()
elif(ch==2):
pop()
elif(ch==3):
display()
elif(ch==4):
print (“\t\t\tABORTING PROGRAM…..”)
sys.exit()
anyvar=input(“\n\t\t\tPress any key to continue…\n”)
• QUEUE: Queue is a linear data structure. Queue is a list of elements in which insertion takes place at one end, called the REAR and
deletion takes place only at the other end, called the FRONT.
♦ It follows the principle First In First Out (FIFO).
♦ There are two basic operations associated with stack:
♦ Enqueue : Insert the element in queue
♦ Dequeue : Delete the element from queue
♦ Menu based programme for queue:
Q=[]
from os import system
#menu display
def menu():
ch=0
while(ch<1 or ch>4):
#print (“\n”*100)
anyvar=system(‘cls’)
print (“\n\n\n\n\n”)
print (“\t\t\t1: INSERT”)
print (“\t\t\t2: DELETE”)
print (“\t\t\t3: DISPLAY”)
print (“\t\t\t4: EXIT”)
ch=int(input(“\n\t\t\tEnter a choise (1-4):”))
return ch
def insert():
#code to insert an item
item=int(input(“\t\t\tEnter an item to insert: “))
Q.append(item)
print (“\t\t\tITEM ” , item ,” INSERTED IN THE QUEUE”)
def delete():
#code to delete from queue
if (Q==[]):
print (“\t\t\tNO ITEM TO DELETE”)
else:
item=Q.pop(0)
print (“\t\t\tITEM ” , item ,” DELETED FROM THE QUEUE”)
def display():
#code to display stack
if (Q==[]):
print (“\t\t\tEMPTY QUEUE”)
else:
print (“\t\t\t”,)
for i in Q:
print (i ,’ ‘, end=” “)
#code to call all functions
import sys
ch=0
while(ch!=4):
ch=menu()
if(ch==1):
insert()
elif(ch==2):
delete()
elif(ch==3):
display()
elif(ch==4):
print (“\t\t\tABORTING PROGRAM…..”)
sys.exit()
anyvar=input(“\n\t\t\tPress any key to continue…\n”)
