2nd PUC Computer Science Question Bank Chapter 4 Data Structures

Students can Download 2nd PUC Computer Science Chapter 4 Data Structures Questions and Answers, Notes Pdf, 2nd PUC Computer Science Question Bank with Answers helps you to revise the complete Karnataka State Board Syllabus and to clear all their doubts, score well in final exams.

Karnataka 2nd PUC Computer Science Question Bank Chapter 4 Data Structures

2nd PUC Computer Science Data Structures One Mark Questions and Answers

Question 1.
What are data structures?
Answer:
A data structure is a specialized format for organizing and storing data.

Question 2.
Differentiate between one dimensional and two dimensional array.
Answer:
An array with only one row or column is called one dimensional array. A two dimensional array is an array in which each element is identified by a pair of indices.

Question 3.
Give any two examples for primitive data structures.
Answer:
The integers, real float, logical data, character data, pointer.

Question 4.
Mention any two examples for non- primitive data structure.
Answer:
Arrays, lists and files.

Question 5.
What are primitive data structures?
Answer:
The data structures that are directly operated upon by machine – level instructions are known as primitive data sturcture.

Question 6.
What are non – primitive data structures.
Answer:
There are the data structure that are derived from the primitive data structure.

Question 7.
Name the data structure which is called LIFO list.
Answer:
Stock.

Question 8.
What is the other name of queue?
Answer:
FIFO (First In First Out).

Question 9.
Define any array.
Answer:
An array is a collection of homogeneous elements with unique name and the elements are arranged one after another in the adjacent memory location.

Question 10.
What are lists?
Answer:
It is a non – primitive data structure having defnite ordered collection of values.

Question 11.
What is meant by linear data structure?
Answer:
Linear data structure are a kind of data structure that have homogenous elements.

Question 12.
What are non – linear data structure?
Answer:
A non – linear data structure is a data structure in which a data item is connected to several other data items.

Question 13.
What is a stack?
Answer:
A stock is an ordered collection of items where the addition of new items and the removal of existing items always take place at the same end.

Question 14.
What is a queue?
Answer:
A queue is an ordered collection of items where the addition of new items and the removal of existing items always takes place at different ends.

Question 15.
Name the data structure whose relation between data elements is by means of links.
Answer:
Linked Lists.

Question 16.
What is linked list.
Answer:
A linked list is a linear collection of data elements called nodes and the linear order is given by means of pointers.

Question 17.
Mention any one application of stack.
Answer:
A simplest application of stack is to reverse a word. You push given word to stack letter-by-letter and then pop lettters from the stack.

Question 18.
What do you mean by traversal in data structures?
Answer:
The process of accessing each data items exactly once to perfor some operation is called traversing.

Question 19.
Define searching in one dimensional array.
Answer:
The process of finding the location of a data item in the given collection of data items is called searching.

Question 20.
What is meant by sorting in an array?
Answer:
The process of arrangement of data items in the ascending or decending order is called sorting.

Question 21.
Mention the types of searching in the array.
Answer:
Linear search & binary search.

Question 22.
What are non – linear data structures?
Answer:
The TREES and GRAPH are non – linear data structures.

Question 23.
What is a binary tree?
Answer:
A binary tree is a tree in which each node has at most two descendants.

Question 24.
What do you mean by depth of tree?
Answer:
The depth of the node in tree is the length of the path to its root (i.e. its root path)

Question 25.
How do you find the degree of to tree?
Answer:
Number of nodes to be traversed from root to reach a leaf of a tree.

Question 26.
What are the operations that can be performed on the stack?
Answer:
Is empty (), size (), PUSH (), pop.

Question 27.
What are the operations that can be performed on the queue?
Answer:
Enqueue, dequeue, is Empty (), size ().

Question 28.
Define the term PUSH & POP operations on the stock.
Answer:
PUSH is adding new element to the top of the stock, pop is removing the top of the stock.

Question 29.
What is FIFO list?
Answer:
The element inserted first will be deleted first. (First In First Out) (FIFO).

Question 30.
What is LIFO List?
Answer:
The most recently added element is the one that is in the position to be removed of first. (Last In First Out) (LIFO).

Question 31.
Mention the different types of queues.
Answer:

1. Simple Queue
2. Circular Queue
3. Priority Queue
4. Dequeue (Double ended queue)

2nd PUC Computer Science Data Structures Two Marks Questions and Answers

Question 1.
How are the data structure classified?
Answer:
The data structure are divided into.

1. Primitive data structure ex: int, float.
2. Non – primitive data structure. ex: Array, list. The Non – primitive data structure again divided into,
   • Linear data structure, ex: stock, queue.
   • Non – linear data structure, ex: Tree, graph.

Question 2.
Justify the need for using arrays.
Answer:
When we require to process a group of data items that are of the same type, we can use array. In array, elements are stored in continous memory location. Hence it is necessary to use arrays to perform the operations of sorting arid searching as it saves time, since elements are at a particular place in memory.

Question 3.
How are arrays classified?
Answer:

1. One – dimensional array
2. Two – dimensional array
3. Multi – dimensional array.

Question 4.
Mention the various operations performed on arrays.
Answer:
Traversing, searching, sorting, Insertion, Deletion, Merging.

Question 5.
How do you find the length of the array?
Answer:
Arrays can store a list of finite number (n) of data items of same data type in consecutive locations. The number n is called size or length of the array.
The lenght of the array is calculated by L = UB – LB + 1.
Here, UB is the largest index & LB is the smallest index of an array.

Question 6.
Mention the types of linked lists.
Answer:

1. Singly linked list (SLL)
2. Doubly linked list (DLL)
3. Circular linked list (CLL)

Question 7.
What is stack? Mention the types of operation performed on the stacks.
Answer:
The type of operation performed:

1. Stock: Creates a new stock that is empty.
2. push: add a new item to the top of the stock.
3. pop: removes the top item from the stock.
4. peek: retems the top item from the stock.
5. is empty: lists whether the stock is empty
6. size: reterns the number of items on the stock.

Question 8.
What is queue? Mention the various operations pre-owned on the queue.
Answer:
A queue is an ordered collection of items where the addition of new items and the removal of existing items always takes places at different ends.
Different operations performed on the queue are:

1. Queue (): It creates a new queue that is empty.
2. Enqueue (item ): It adds a new item to the rear of the queue.
3. Dequeue (): It removes the front item from the queue.
4. Is empty (): It tests to see whether the queue is empty.
5. Size (): It returns the number of items in the queue.

2nd PUC Computer Science Data Structures Three Marks Questions and Answers

Question 1.
Mention the various operations performed non linear data structures.
Answer:
The basic operations non – linear data structure are as follows:

1. Traversal: The process of accessing each data item exactly once to perform some operation is called traversal.
2. Insertion: The process of adding a new data item into the given collection of data items is called insertion.
3. Deletion: The process of removing an existing data item from the given collection of data items is called as deletion.
4. Searching: The process of finding the location of a data item from the given collection of data items is called as searching.
5. Sorting: The process of arrangement of data items in ascending or decending order is called sorting.
6. Merging: The process of combining the data items of two structure of form a single structure is called merging.

Question 2.
Explain the memory representation of a one – dimensional array.
Answer:
Elements of linear array are stored in the consecutive memory locations. Let p be the location of the element. Address of first element of linear array A is given by Base (A) called the Base address of A using this we can calculate the address of any element in the array A by the formula.
LOC( A[P] ) = Base (A) + W (P-LB)
Here, w is the number of words per memory cell. ex: Suppose if a sorting S is used to store a string ABCDE in it with starting address at 1000, one can find the address of fourth element as follows:

Now the address of the elements S(3) can be calculated as follows: Address (S[3]) = Base (S) +w (P – LB)
Here, w = 1 for character,
= 1000 + 1(3 – 0)
= 1003

Question 3.
Explain the memory representation of a stack using one – dimensional array.
Answer:
Stack can be represented using a one dimentional array. A block of memory is allocated which is required to accomodate the items to the full capacity of the stack. The items into the stack are stored in the sequential order from the first location of the memory block.

The pointer TOP contains the location of the top elements of the stack. A variable MAXSTX contains the maximum number of elements that cab be stored in the stack.

The condition TOP = MAXSTX contains the maximum number of elements that can be stored in the stack. The condition TOP = MAXSTX indicates that the stack is full and TOP = NULL indicates that the stack is empty. Representing a stack using a array is easy & convenient. However, it is useful for fixed sized stacks, sometimes in a program, the size of the stack may be required to increase during execution, i.e., dynamic creation of a stack is not possible using arrays. This requires linked lists.

Question 4.
Explain the memory representation of a queue using one – dimensional array.
Answer:
Queue is represented in the memory linear array. Let QUEUE be linear queue. Two pointer variable called FRONT and REAR are maintained. The pointer variable FRONT contains the location of the element to be removed and the pointer variable REAR contains location of the last element inserted. The condition FRONT = NULL indicates that the queue is empty and the condition REAR =N indicates that the queue is full.

Question 5.
Explain the memory representation of single linked list.
Answer:
A signle linked list contains two fields in each node – the data field and link field. The data field contains the data of that node while the link field contains address of the next node, since there is only one link field in each node, the linked list is called as singly linked list.

Question 6.
Define the following with respect to binary tree.
Answer:

1. root: The top most node in the tree is called root node.
2. subtree: A subtree of a tree T is a tree consisting of a node in T and all of its descendants in T.
3. depth: The depth of a node is the lenght of the path to its root (i.e, its root path).
4. degree: Number of descendants of a node.

Question 7.
Write an algorithm for traversal in a linear array.
Answer:
Let A be a linear array with LB & UB as lower bounds and upper bound. This algorithm traverses the array A by applying the operation PROCESS to each elements of A.
1. for LOC = LB – UB
PROCESS A [LOC]
End of for
2. Exit

Question 8.
Give the memory representation of two – dimensional array.
Answer:
There are two methods for representing two – dimensional array.
1. ROW – major order:
Let A be the array of order m x n. In row major order, all the first – row elements are stored in sequential memory locations and then all the second row elements are stored & so on. Base [A] is the address of the first element. The memory address of any element A[I] [J] can be obtained by the formula.
LOC (A[I] [J] = Base (A) + w [n(I – 1) + (J – 1)]
where w is the number of words per memory location.

2. Column – Major order:
Let A be the array of order mxn. In column-major order, all the first column elements are stored in sequential memory locations and then all the second column elements are stored & so on. Base [A] is the address of the first elements. The memory address of any elements A [I] [J] cab be obtained by the formula,
LOC (A[I][J]) = Base [A]+w[I – 1) + m (J – 1)]
Where w is the number of words per memory location.

2nd PUC Computer Science Data Structures Five Marks Questions and Answers

Question 1.
Write an algorithm to insert an element in an array.
Answer:
A is array with N elements. ITEM is the elements to be inserted in the position p.
Step 1 : for I = N – 1 down to P
A [I + 1] = A [I]
End of for
Step 2 : A[P] = ITEM
Step 3 : N = N + 1
Step 4 : Exit

Question 2.
Write an algorithm to delete an element in an array.
Answer:
A is the array with N elements. ITEM is the element to be deleted in the position p & it is stored into the variable Item.
Step 1 : Item = A [p]
Step 2 : for I = p to N – 1
A[I] = A[I + 1]
End of for
Step 3 : N = N – 1
Step 4 : Exit

Question 3.
Write an algorithm to search an element in an array using binary search.
Answer:
A is the sorted array with LB as lower bound & UB as the upper bound respectively. Let B, E, M denote beginning, end & middle locations of the segments of A.
Step 1 : Set B = LB, E = UB
Step 2 : while (B < = E)
M = int (B + E)/2
if (ELE = A [M])
LOC = M
GOTO 3
else
if (ELE < A[M]) B = M – 1 else E = M + 1 Step 3 : if (LOC >= 0)
PRINT LOC
else
PRINT “search is unsuccessful”
Step 4 : Exit

Question 4.
Write an algorithm to sort an array using insertion sort.
Answer:
Let A be an array with N unsorted elements. The following algorithm sorts the elements in order.
Step 1 : for P = 1 to N – 1
Step 2 : temp = A[P]
PTR = P – 1
Step 3 : while temp < A [PTR]
A [PTR + 1] = A [ PTR]
PTR = PTR + 1
End of while
Step 4 : A [PTR + 1] = temp
End of for
Step 5 : End.

Question 5.
Write an algorithm for push & pop operation in stack using array.
Answer:
PUSH (STACK, TOP, SIZE, ITEM)
Stock is the array that contains N elements & TOP is the pointer to the top element of the array. ITEM the element to be inserted. This procedure inserts ITEM into the STACK.
Step 1 : If Top = N then [Check overflow]
PRINT “stack is full”
Exit
End of If
Step 2 : Top = Top + 1 [Increment the top]
Step 3 : STACK [TOP] = ITEM [Insert the ITEM]
Step 4 : Return

POP [STACK, Top, ITEM)
STACK is the array that store N items, TOP is the pointers to the top element of the array. This procedure delete top element from the STACK.
Step 1 : IF Top = 0 then [check underflow]
PRINT “stack is empty”
Exit
End of If
Step 2 : STACK [Top] = ITEM [copy the top element]
Step 3 : Top =’Top – 1 [Decrement the top]
Step 4 : Return

Question 6.
Write an algorithm to insert a data element at the rear end of the queue.
Answer:
Let QUEUE is the linear array consisting of N elements. FRONT is the pointer that contains the location of the element to be deleted and REAR contains the location of the inserted element. ITEM is the element to be inserted.
Step 1 : If REAR = N Then [ check for over flow]
PRINT “overflow”
Exit
Step 2 : If FRONT = NULL Then [check whether QUEUE is empty]
FRONT = 0
REAR =0
Else
REAR = REAR + 1 [Increment REAR pointer]
Step 3 : QUEUE = [REAR] = ITEM [Copy ITEM to REAR position]
Step 4 : Return

Question 7.
Write an algorithm to delete a data element from the front end of the queue.
Answer:
Let QUEUE is the linear array consisting of N elements FRONT is the pointer that contains the location of the element to be deleted & REAR contains the location of the inserted element. The algorithm deletes the elements at FRONT position.
Step 1 : If FRONT = NULL Then [ check for underflow]
PRINT “underflow”
Exit
Step 2 : ITEM = QUEUE [FRONT]
Step 3 : It FRONT = NULL Then [ It QUEUE has only one element]
FRONT = 0
REAR = 0 .
else
FRONT = FRONT = 1 [ FRONT = FRONT + 1]
Step 4 : Return

Question 8.
Write an algorithm to insert a data element at the beginning of the linked list.
Answer:

1. p ← new Node
2. data (p) ← num
3. link (p) ← START
4. START ← P
5. Return

Question 9.
Write an algorithm to delete a data element at the rnd of a linked list.
Answer:
The used two pointers p₁& p₂. pointer p₁ is used to traverse the linked list & pointers p₂ keep the location of the previous node of p₁.

1. START
2. p₂ ← START
3. While (linked (p₂) : NULL
   P₁ ← P₂
   P₂ ← link (P₂)
4. PRINT data (P₂)
5. link (P₁) ← NULL
6. STOP

Question 10.
Apply binary search for the following sequence of numbers. 10, 20, 30, 35, 40, 45, 50, 55, 60 search for item = 35
Answer:

0	1	2	3	4	5	6	7	8
10	20	30	35	40	45	50	55	60

Given n = 9, item = 35.
Let LOC = -1, Beg = 0, End = 8 (n – 1)
1. Mid = \(\frac{0+8}{2}\) = 4
a [ Mid] = a [4] = 40
35 ≠ a [Mid]
35 ≠ 40
= 35 < 40 = End = Mid – 1 = 4 – 1 = 3 2. Mid = \(\frac{0+3}{2}\) = 1 a[1] = 20 35 ≠ 20 35 > 20
= Big = Mid + 1 = 1 + 1 = 2

3. Mid = \(\frac{2+3}{2}\) = 2
a [2] = 30
35 ≠ 30
35 > 20
= Big = Mid + 1 = 2 + 1 = 3

4. Mid = \(\frac{3+3}{2}=\) = 3
a [3] = 35
= LOC = Mid
= LOC = 3
35 bound in location 3.