IMPORTANT QUESTION DATA STRUCTURE IN C++

 PAPER 2nd

QUESTION:1
WHAT IS DATA STRUCTURE? EXPLAIN DIFFERENT TYPES OF DATA STRUCTURE

A data structure is a group of data elements grouped together under one name. These data elements, known as members, can have different types and different lengths. Data structures can be declared in C++ using the following syntax:
struct type_name {
member_type1 member_name1;

Types Data Structures are:-

1. Arrays
An array is a structure of fixed-size, which can hold items of the same data type. Arrays are indexed, meaning that random access is possible. An array is usually presented as a native data structure in many programming languages. However, one shall not confuse array with the list like data structures in languages like python. Let us see arrays are presented in C++;
// simple declaration
int array[] = {1, 2, 3, 4, 5 };
// in pointer form (refers to an object stored in heap)
int * array = new int[5];

2. Linked Lists

A linked list is a sequential structure that consists of a sequence of items in linear order which are linked to each other. You are only required to know one end of the chain to traverse through this data structure. In a scenario where the size changes frequency, using an array might not be advantageous unless data is accessed randomly (expansions can cause higher copy times and use more memory unless you implement a shrink operation). So a linked list can be considered as a data structure that supports frequent size variations and sequential access.

3. Stacks

A stack is a LIFO (Last In First Out — the element placed at last can be accessed at first) structure. Although this data structure has a different behaviour, this can be considered as a derivation of the linked list with only a head or access to the top element.

4. Queues

A queue is a FIFO (First In First Out — the element placed at first can be accessed at first) structure. This can be considered as the reverse scenario of the stack. In simpler terms, it is a linked list where we add from one end read from the other end. This emulates the real-world line-up at a driveway. 

QUESTION:2
WHAT IS LINKED LIST? PERFORM BASIC OPERATION ON LINKED LIST?

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers

Basic Operation On linked List are:-

Traversal: To traverse all the nodes one after another.

Insertion: To add a node at the given position.

Deletion: To delete a node.

Searching: To search an element(s) by value.

Updating: To update a node.

Sorting: To arrange nodes in a linked list in a specific order.

Merging: To merge two linked lists into one.

-:Related searches:-

QUESTION:3
EXPLAIN BINARY TREE AND BINARY TREE TRAVERSAL

A binary tree is a hierarchical data structure whose behaviour is similar to a tree, as it contains root and leaves (a node that has no child). The root of a binary tree is the topmost node. Each node can have at most two children, which are referred to as the left child and the right child

BINARY TREE TRAVERSAL

Tree traversal is the process of visiting each node in the tree exactly once. Visiting each node in a graph should be done in a systematic manner. If search result in a visit to all the vertices, it is called a traversal. There are basically three traversal techniques for a binary tree that are,

Preorder traversal

Inorder traversal

Postorder traversal

QUESTION-4

WRITE DOWN THE ALGORITHM TO PERFORM BINARY SEARCH

Working –

1. Search the sorted array by repeatedly dividing the search interval in half
2. Begin with an interval covering the whole array.
3. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half.
4. Otherwise narrow it to the upper half.
5. Repeatedly check until the value is found or the interval is empty.

Algorithm to perform Binary Search –

Take input array, left, right & x

START LOOP – while(left greater than or equal to right)

mid = left + (right-left)/2

if(arr[mid]==x) then

return m

else if(arr[mid] less than x) then

left = m + 1

else

right= mid – 1

END LOOP

return -1

C++ Program to Implement Binary Search –

#include < iostream >

  using namespace std;

int binarySearch(int arr[], int left, int right, int x) {

  while (left <= right) {

    int mid = left + (right - left) / 2;

    if (arr[mid] == x) {

      return mid;

    } else if (arr[mid] < x) {

      left = mid + 1;

    } else {

      right = mid - 1;

    }

  }

  return -1;

}

int main() {

  int myarr[10];

  int num;

  int output;

  cout << "Please enter 10 elements ASCENDING order" << endl;

  for (int i = 0; i < 10; i++) {

    cin >> myarr[i];

  }

  cout << "Please enter an element to search" << endl;

  cin >> num;

  output = binarySearch(myarr, 0, 9, num);

  if (output == -1) {

    cout << "No Match Found" << endl;

  } else {

    cout << "Match found at position: " << output << endl;

  }

  return 0;

}

QUESTION:5

EXPLAIN HASH FUNCTIONS AND COLLISION RESOLUTION TECHNIQUE

HASH FUNCTION:-

A hash function is any function that can be used to map data of arbitrary size to fixed-size values. The values returned by a hash function are called hash values, hash codes, digests, or simply hashes. The values are usually used to index a fixed-size table called a hash table.

COLLISION RESOLUTION TECHNIQUE

There are two types of collision resolution techniques.

Separate chaining (open hashing)

Open addressing (closed hashing)

SEPARATE CHAINING

In this technique, a linked list is created from the slot in which collision has occurred, after which the new key is inserted into the linked list. This linked list of slots looks like a chain, so it is called separate chaining. It is used more when we do not know how many keys to insert or delete.

OPEN ADDRESSING

Open addressing is collision-resolution method that is used to control the collision in the hashing table. There is no key stored outside of the hash table. Therefore, the size of the hash table is always greater than or equal to the number of keys. It is also called closed hashing.

The following techniques are used in open addressing:

Linear probing

Quadratic probing

Double hashing