2nd PUC Computer Science Question Bank Chapter 4 Data Structures

You can Download Chapter 4 Data Structures Questions and Answers, Notes, 2nd PUC Computer Science Question Bank with Answers Karnataka State Board Solutions help you to revise complete Syllabus and score more marks in your examinations.

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:
data structure is a systematic way of organising, storing and accessing data.

Question 2.
Differentiate between one-dimensional and two-dimensional array.
Answer:
One-dimensional array is structured in one dimension and each element is accessed by an index value whereas two-dimensional array is structured in two dimensions and each element is accessed by a pair of index values.

Question 3.
Give any two examples for primitive data structures.
Answer:
The two examples for primitive data structures are int and float data.

Question 4.
Mention any two examples for non-primitive data structures.
Answer:
The two examples for non-primitive data structures are array and lists.

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

Question 6.
What are non-primitive data structures?
Answer:
The non-primitive data structures derived from primitive data types are more complex.

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

Question 8.
What is the other name of the queue?
Answer:
The FIFO list is the other name of the queue.

Question 9.
Define an array.
Answer:
Array is a collection of similar elements that share a common name. It is a structured data type and allocates memory contiguously.

Question 10.
What are the lists?
Answer:
Lists are a way to store many different values under a single variable. Every item in this list is numbered with an index.

Question 11.
What is meant by linear data structures?
Answer:
The linear(sequential) data structures is the one which displays the relationship of adjacency between the elements.

Question 12.
What are non-linear data structures?
Answer:
data structure that is possible to derive any relationship other than the adjacency relationship is called non-linear data structures.

Question 13.
What is a stack?
Answer:
stack is an ordered collection of items in which items may be inserted and deleted at one end.

Question 14.
What is a queue?
Answer:
A queue is a non-primitive data structure where an item is inserted at one end and removed from the other end.

Question 15.
Name the data structure whose relationship between data elements is by means of links.
Answer:
The data structure whose relationship between data elements is by means of links is linked lists.

Question 16.
What is a linked list?
Answer:
Linked list is a data structure in which each element is dynamically allocated and in which elements point to each other to define a linear relationship.

Question 17.
Mention any one application of stack.
Answer:
The one application of stack is recursive function/expression evaluation.

Question 18.
What do you mean by traversal in data structure?
Answer:
The process of accessing each data item only once in group of elements for some operation.

Question 19.
Define searching in a one-dimensional array.
Answer:
Searching is the process of finding the location of data element in the array.

Question 20.
What is meant by sorting in an array?
Answer:
The sorting is the process of arranging the array elements in ascending or in descending order.

Question 21.
Mention the types of searching in the array.
Answer:
The linear search and binary search techniques are the types of searching in the array.

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:
The TREE is a general data structure that describes the relationship between data items or ‘nodes’. The parent node of a binary tree has only two child nodes.

Question 24.
What do you mean by the depth of a tree?
Answer:
It is the number of ancestors of a node excluding itself i.e., the length of the path to its root.

Question 25.
How do you find the degree of a tree?
Answer:
The degree of the tree is the total number of its children i-e the total number nodes that originate from it. The leaf of the tree does not have any child so its degree is zero.

Question 26.
What are the operations that can be performed on stacks?
Answer:
The stack(), push(item), pop(), peek(), is Empty() and size() are the operations that can be performed on stacks.

Question 27.
What are the operations that can be performed on queues?
Answer:
The queue(), enqueue(item), dequeue(), isEmpty() and size() are the operations that can be performed on queues.

Question 28.
Define the term PUSH and POP operations in stack.
Answer:
The process of adding a new item to the top of the stack is called PUSH and the process of removing the top item from the top of stack is called POP operation.

Question 29.
What is the FIFO list?
Answer:
The data structure queue is called FIFO(First In First Out) which means first inserted data item is removed first.

Question 30.
What is the LIFO list?
Answer:
The data structure stack is called LIFO(Last In First Out) which means the last inserted data item is removed first.

Question 31.
Mention the different types of queues.
Answer:
The different types of queues are simple queue, circular queue, priority queue and dequeue.

Question 32.
Give examples for linear data structures.
Answer:
The examples for linear data structures are stack, queues and linked lists.

Question 33.
Give examples for non-linear data structures.
Answer:
The examples for non-linear data structures are trees and graphs.

Question 34.
What is meant by traversal operations on data structure?
Answer:
It is the process of accessing each and every data element only once for some task.

Question 35.
What is meant by insertion operations on data structure?
Answer:
It is the process of adding a data element into the existing set of data elements.

Question 36.
What is meant by deletion operations on data structure?
Answer:
It is the process of removing existing data element from the existing set of data elements.

Question 37.
What is meant by merging operations on data structure?
Answer:
It is the process of combining more than one set of similar data elements into one set of elements.

Question 38.
How is each and every element in the array referred?
Answer:
The array elements are referred by subscript or index of an array.

Question 39.
Give the syntax of a one-dimensional array declaration.
Answer:
Datatype arrayname [size] ;

Question 40.
What is the first element index number in an array?
Answer:
The first element index number in an array is 0.

Question 41.
What is the last element index number in an array?
Answer:
The last element index number of array is n-1 where n is the number of elements in an array.

Question 42.
Give the formula to calculate the length of the one-dimensional array.
Answer:
The formula is
Size of the array = UB – LB + 1
Where UB is Upper bound, LB is lower bound

Question 43.
What do you mean by base address in-memory representation of an array?
Answer:
The base address in-memory representation of an array is the memory address of the first element of an array.

Question 44.
Give the formula to calculate the memory address of an array element.
Answer:
The formula to calculate the memory address of an array element is
Base_Address + W ( Position – LB )
Where W is the number of words per memory cell, position is the location of array element for which memory address is calculated, LB is Lower bound of an array.

Question 45.
Mention any one advantage of the linear search method.
Answer:
The linear search method doesn’t require the list should be in order.

Question 46.
Mention any one dis-advantage of the linear search method.
Answer:
The disadvantage of the linear search method is time-consuming (slow in searching).

Question 47.
Mention any one advantages of the binary search method.
Answer:
The binary search method is very fast.

Question 48.
Mention any one disadvantage of the binary search method.
Answer:
The binary search method requires the list of elements should be in order.

Question 49.
What is the formula to calculate mid element index number in the binary search method?
Answer:
The formula to calculate mid element index number in the binary search method is
Mid-element-index = (low + high) / 2
Where low is beginning index number and high is the last index number of an array.

Question 50.
What are the different types of representation of stacks in memory?
Answer:
The two types of representation of stacks in memory are static representation and dynamic representation.

Question 51.
Give the various elements that are required for stack PUSH operation.
Answer:
The various elements required for PUSH operation are PUS( STACK, TOP, SIZE, ITEM).

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

Question 1.
How are data structure classified?
Answer:
The data structure is classified as primitive data structures and non-primitive data structures.

Question 2.
Justify the need for using arrays.
Answer:
Array is a contiguous memory locations represented by a single name and useful in storing data elements in adjacent memory locations. It can be used to implement data structures like linked lists, stacks, queues, trees, graphs, etc.,

Question 3.
How are arrays classified?
Answer:
Array is classified as one dimensional, two dimensional and multidimensional arrays.

Question 4.
Mention the various operations performed on arrays.
Answer:
The various operations performed on arrays are traversing, searching, sorting, insertion, deletion, and merging.

Question 5.
How do you find the length of the array?
Answer:
Length of the array = UB – LB + 1
where
UB is the largest index or upper bound index number
LB is the smallest index or lower bound index number.

Question 6.
Mention the types of linked lists.
Answer:
The types of linked lists are Singly linked list, Doubly linked list and a circular linked list.

Question 7.
What is a stack? Mention the types of operations performed on the stacks.
Answer:
A stack is an ordered collection of items in which data item may be inserted and deleted at one end.
The stack(), push(item), pop(), peek(), isEmpty() and size() are the operations that can be performed on stacks.

Question 8.
What is a queue? Mention the various operations performed on the queue.
Answer:
A queue is a non-primitive data structure where an item is inserted at one end and removed from the other end.
The queue(), enqueue(item), dequeue(), isEmpty() and size() are the operations that can be performed on queues.

Question 9.
Give the syntax for a 2-dimensional array declaration.
Answer:
The two dimensional array declaration syntax
Datatype arrayname [rowsize] [columnsize] ;

Question 10.
What do you mean by row-major ordering and column-major ordering in two-dimensional array?
Answer:
In row-major ordering, every row of the 2-dimensional array is stored one after the other in the memory. In column-major ordering, every column of the two-dimensional array is stored one after the other in the memory.

Question 11.
Give the formula to calculate the memory address of an element using row-major ordering and column-major ordering methods.
Answer:
Row major order method formula
LOC(rowidx, colidx) = BaseAddress + W ( colsize * rowidx + colidx)
Column major order method formula
LOC(rowidx, colidx) = BaseAddress + W (rowidx + rowsize * colidx)

Question 12.
What is an expression? Write the different methods of representing an expression.
Answer:
The expression is a combination of operators and operators. The different methods are infix, prefix and postfix expressions.

Question 13.
Convert the infix expression A + B to prefix and postfix expression.
Answer:
Prefix expression –    +AB
Postfix expression –    AB +

Question 14.
Write the rules for evaluating postfix expressions.
Answer:
Rule 1:
read the expression from left to right.

Rule 2:
each operator follows the previous two operands.

Rule 3:
PUSH when operands are read, and operands will be in the top two-element when operator found.

Rule 4:
evaluate the expression and push the result on the stack.

Question 15.
What is the significance of variables FRONT and REAR in a queue?
Answer:
The variable FRONT is used to identify the position of the first element in the queue, and variable REAR is used to identify the position of the last element of the queue.

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

Question 1.
Mention the various operations performed on data structures.
Answer:
The various operations performed on primitive data structures are create, destroy, select and update and traversal, insertion-deletion, searching, sorting and merging on non-primitive data structures.

Question 2.
Explain the memory representation of a one-dimensional array.
Answer:
The data elements of array is stored in contiguous memory locations. Let P be the location of the data element. The address of the first element of linear array A is given by Base(A)
To calculate the address of any element of A formula
LOC ( A[P] ) = Base(A) + W ( P – LB )
Where
W is the size of data type (number of words per memory cell)
P – location of the data element
A – Base address of first element of array
LB – Lower bound index number

Question 3.
Explain the memory representation of a stack using a one-dimensional array.
Answer:
The items into the stack are stored in a sequential order from the first location of the memory block. A pointer TOP contains the location of the top element of the stack. A variable MAXSTK contains the maximum number of elements that can be stored in stack.
The stack is full when TOP = MAXSTK
The stack is empty when TOP = 0.

Question 4.
Explain the memory representation of the queue using a one-dimensional array.
Answer:
Let Q be a linear array of size N
The pointer FRONT contains location of front element of the queue (element to be deleted)
The pointer REAR contains location of rear element of the queue (recently added element)
The queue is empty when FRONT = 0
The queue is full when FRONT = N
To add element, REAR = REAR + 1
To delete element, FRONT = FRONT + 1

Question 5.
Explain the memory representation of single linked list.
Answer:
A linked list maintains the memory location of each item in the list by using a series of ‘pointers’ within the data structure.
Every node of a singly-linked list contains the following information:

• Data element (user’s data);
• A link to the next element (auxiliary data).

A number of pointers are required, these are:

1. The start pointer’ points to the first node in the list.
2. The last node in the list has a ‘null pointer’ (which is an empty pointer)
3. Each node has a pointer providing the location of the next node in the list.

Question 6.
Define the following with respect to binary tree

1. root
2. subtree
3. depth
4. degree

Answer:
1. root:
A topmost node in a tree

2. subtree:
A tree T is a tree consisting of node in T and all of its descendants in T.

3. depth:
It is the number of ancestors of a node excluding itself i.e., the length of the path to its root.

4. degree:
The degree of the tree is the total number of it’s children i.e., the total number nodes that is zero.

Question 7.
Write an algorithm for traversal in a linear array.
Answer:
Algorithm for traversal of linear array
Traversal (A, N) – A is an array of N elements
Step 1: for i = 0 to N-l repeat step 2
Step 2: print A[i]
[End of for loop]
Step 3: Exit.

Question 8.
Give the memory representation of the two-dimensional array.
Answer:
Let A be two-dimensional array
Let M is rows and N is columns
The A array may be stored in the memory in one of the following methods;
1. Row-major representation:
In this type of method, the first row occupies the first set of memory locations reserved for the array and second-row occupies the next set and so on.

2. Column-major representation:
In this type of method, the first column occupies the first set of memory locations reserved for the array and the second column occupies the next set and so on.

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

Question 1.
Write an algorithm to insert an element in an array.
Answer:
A is an array
N is number of elements (size)
Element is a data element
Pos is the location of the element to be inserted.

Insertion (A, N, Element, Pos)
Step 1: for i = N-1 downto Pos repeat step 2
Step 2: A[i+1] = A[i]
End for
Step 3: A [Pos] = Element
Step 4: N = N + 1

Question 2.
Write an algorithm to delete an element in an array.
Answer:
A is an array
N is number of elements (size)
Element is a deleted data element
Pos is the location of the element to be deleted.
Deletion (A, N, Pos)
Step 1: Element = A [Pos]
Step 2: for i = Pos to N-1 repeat step 3
Step 3: A[ i ] = A[i+1]
End for
Step 4: N = N -1

Question 3.
Write an algorithm to search an element in an array using binary search. Algorithm: Binary_search(A,ele,N)
Answer:
Step 1: low = 0
Step 2: high = n-1
Step 3: while (low <= high) repeat step 4 through step 6
Step 4: mid = (low + high) / 2
Step 5: Is ( ele = = a[mid]) then
Loc = mid
goto step 7
Otherwise
Step 6: is ( ele < a[mid])? then
high = mid – 1
otherwise
low = mid + 1
[end while – step 3]
Step 7: Is ( Loc >= 0 ) ? then
Print “search element found at location “, loc
Otherwise
Print “search element not found”.

Question 4.
Write an algorithm to sort an array using insertion sort Algorithm: lnsertion_sort (A,N)
Answer:
Step 1: for i = 1 to n-1 Repeat step 2
Step 2: for j = i downto 1 Repeat step 3
Step 3: is ( a[j] < a[j-1])? then
temp = a[j]
A[j] = a[j-1]
A[j-1] = temp [ end of j loop]
[ end of i loop]

Question 5.
Write an algorithm for push and pop operation in stack using array.
Answer:
Algorithm for PUSH operation
PUSH(STACK, TOP, SIZE, ITEM)
Step 1: if TOP >= N-1 then
PRINT “stack is overflow”
Exit
End of if
Step 2: Top = TOP + 1
Step 3: STACK[TOP] = ITEM
Step 4: Return

Algorithm for POP operation
PUSH(STACK, TOP, ITEM)
Step 1: if TOP = 0 then
PRINT “stack is empty”
Exit
End of if
Step 2: ITEM = STACK[POP]
Step 3: TOP = TOP -1
Step 4: Return

Question 6.
Write an algorithm to insert a data element at the rear end of the queue.
Answer:
Step 1: if REAR >= N -1 then
Print “Queue is overflow”
Exit
End of if
Step 2: REAR = REAR+ 1
Step 3: QUEUE [REAR] = element
Step 4: if FRONT =-1 then
FRONT = 0.

Question 7.
Write an algorithm to delete a data element from the front end of the queue.
Answer:
Step 1: if FRONT = -1 then
Print “Queue is Underflow”
Exit
End of if
Step 2: ITEM = QUEUE [FRONT]
Step 3: if FRONT = REAR then
FRONT = 0
REAR = 0
Else
FRONT = FRONT + 1
Step 4: return

Question 8.
Write an algorithm to insert a data element at the beginning of a linked list.
Answer:
Step 1: if AVAIL = NULL then
Print ” Availability stack is empty”
Else
NEW_NODE = AVAIL
AVAIL = AVAIL → LINK
Step 2: if FIRST = NULL then
NEW_NODE → INFO = ELEMENT
NEW_NODE → LINK = NULL
FIRST = NEW_NODE
Else
NEW_NODE → INFO = ELEMENT
NEW_NODE → LINK = FIRST
FIRST = NEW_NODE
Step 3: return

Question 9.
Write an algorithm to delete a data element at the end of a linked list.
Answer:
Step 1: if FIRST = NULL then
Print “Linked list is empty”
Exit
End of if
Step 2: if FIRST → LINK= NULL then
Return FIRST → data
FIRST = NULL
Else
P2 = FIRST
While P2 → LINK not equal to NULL
P1 = P2
P2 =P2 → UNK
End while
STEP 4: Return p2 → data
STEP 5: P1 → LINK = NULL
STEP 6: EXIT.

Question 10.
Apply binary search for the following sequence of number. 10,20,30,35,40,45,50,55,60 search for item 35.
Answer:
Low = 0, High = 8 search_ele = 35
Mid_ele_idx = (low + high)/2
= (0+8)/2
= 4
Is 40 = 35? No
The list now is 10 20 30 35
Low =0, high= 3
Mid_ele_idx = (low + high) /2
= (0+3)/2
= 1
Is 20 = 35? No
The list now is 30 35
Low = 2, high = 3
Mid_ele_idx = (low + high)/2
= (2+3)/2
= 2
Is 30 = 35 No
The list now is 35
Low = 3, high = 3
Mid_ele_idx = (low + high) fl
= (3+3)/2
= 3
Is 35 = 35 yes
location = 3
Output:
The search element 35 is found at location 3.