IT GUIDE NOTES ON Data Structure & Algorithm

 

Data Structure & Algorithm

 

Variables

Before going to the definition of variables, let us relate them to old mathematical equations. All of us have solved many mathematical equations since childhood. As an example, consider the below equation:

We don’t have to worry about the use of this equation. The important thing that we need to understand is that the equation has names (x and y), which hold values (data). That means the names (x and y) are placeholders for representing data. Similarly, in computer science programming we need something for holding data, and variables is the way to do that.

Data Types

In the above-mentioned equation, the variables x and y can take any values such as integral numbers (10, 20), real numbers (0.23, 5.5), or just 0 and 1. To solve the equation, we need to relate them to the kind of values they can take, and data type is the name used in computer science programming for this purpose. A data type in a programming language is a set of data with predefined values. Examples of data types are: integer, floating point, unit number, character, string, etc. Computer memory is all filled with zeros and ones. If we have a problem and we want to code it, it’s very difficult to provide the solution in terms of zeros and ones. To help users, programming

languages and compilers provide us with data types. For example, integer takes 2 bytes (actual value depends on compiler), float takes 4 bytes, etc. This says that in memory we are combining 2 bytes (16 bits) and calling it an integer. Similarly, combining 4 bytes (32 bits) and calling it a float. A data type reduces the coding effort. At the top level, there are two types of data types:

• System-defined data types (also called Primitive data types)

• User-defined data types

System-defined data types (Primitive data types)

Data types that are defined by system are called primitive data types. The primitive data types provided by many programming languages are: int, float, char, double, bool, etc. The number of bits allocated for each primitive data type depends on the programming languages, the compiler and the operating system. For the same primitive data type, different languages may use different sizes. Depending on the size of the data types, the total available values (domain) will also change.

For example, “int” may take 2 bytes or 4 bytes. If it takes 2 bytes (16 bits), then the total possible values are minus 32,768 to plus 32,767 (-215 to 215-1). If it takes 4 bytes (32 bits), then the possible values are between -2,147,483,648 and +2,147,483,647 (-231 to 231-1). The same is the case with other data types.

User defined data types

If the system-defined data types are not enough, then most programming languages allow the users to define their own data types, called user – defined data types. Good examples of user defined data types are: structures in C/C + + and classes in Java. For example, in the snippet below, we are combining many system-defined data types and calling the user defined data type by the name “newType”. This gives more flexibility and comfort in dealing with computer memory.

Data Structures

Based on the discussion above, once we have data in variables, we need some mechanism for manipulating that data to solve problems. Data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently. A data structure is a special format for organizing and storing data. General data structure types include  arrays, files, linked lists, stacks, queues, trees, graphs and so on.

Depending on the organization of the elements, data structures are classified into two types:

1) Linear data structures: Elements are accessed in a sequential order but it is not compulsory to store all elements sequentially. Examples: Linked Lists, Stacks and Queues.

2) Non – linear data structures: Elements of this data structure are stored/accessed in a non-linear order. Examples: Trees and graphs.

Abstract Data Types (ADTs)

Before defining abstract data types, let us consider the different view of system-defined data types. We all know that, by default, all primitive data types (int, float, etc.) support basic operations such as addition and subtraction. The system provides the implementations for the primitive data types. For user-defined data types we also need to define operations. The implementation for these operations can be done when we want to actually use them. That means, in general, user defined data types are defined along with their operations.

To simplify the process of solving problems, we combine the data structures with their operations and we call this Abstract Data Types (ADTs). An ADT consists of two parts:

1. Declaration of data

2. Declaration of operations

Commonly used ADTs include: Linked Lists, Stacks, Queues, Priority Queues, Binary Trees, Dictionaries, Disjoint Sets (Union and Find), Hash Tables, Graphs, and many others. For example, stack uses LIFO (Last-In-First-Out) mechanism while storing the data in data structures.

The last element inserted into the stack is the first element that gets deleted. Common operations of it are: creating the stack, pushing an element onto the stack, popping an element from stack,

finding the current top of the stack, finding number of elements in the stack, etc. While defining the ADTs do not worry about the implementation details. They come into the picture only when we want to use them. Different kinds of ADTs are suited to different kinds of applications, and some are highly specialized to specific tasks. By the end of this book, we will go through many of them and you will be in a position to relate the data structures to the kind of problems they solve.

What is an Algorithm?

Let us consider the problem of preparing an omelette. To prepare an omelette, we follow the steps given below:

1) Get the frying pan.

2) Get the oil.

a. Do we have oil?

i. If yes, put it in the pan.

ii. If no, do we want to buy oil?

1. If yes, then go out and buy.

2. If no, we can terminate.

3) Turn on the stove, etc...

What we are doing is, for a given problem (preparing an omelette), we are providing a step-bystep procedure for solving it. The formal definition of an algorithm can be stated as:

An algorithm is the step-by-step unambiguous instructions to solve a given problem.

In the traditional study of algorithms, there are two main criteria for judging the merits of algorithms: correctness (does the algorithm give solution to the problem in a finite number of steps?) and efficiency (how much resources (in terms of memory and time) do es it take to execute the).

Read More

C Array

In C, array is a composite data type. Because we can create an array with the help of primitive data type like int, chat, double etc.

Syntax for creation of one Dimensional array in C

int a[5];

Here a is the array name, type is int. total allocation is 5(5*4=20bytes) here index starts from 0(zero)

Initialization of an array :

int a[]={1,2,3,4,5,6}

if you want access element from above mentioned array, then you can access it with help of index. for example the index of value 3 is 2.

if you want to access all the element from an array, then you can use loop

example : for loop

for(i=0;i<6;i++)

{

   printf("%d\n", a[i]);

}

to calculate size of an array, use the formula :

l=sizeof(a)/sizeof(a[0])

Question & Answer

Choose correct or the best alternative in the following:

Q.1 What is the output of the following program?

main ( )

{ int x = 2, y = 5;

if (x < y) return (x = x+y); else printf (“z1”);

printf(“z2”);

}

(A) z2 (B) z1z2

(C) Compilation error (D) None of these

Ans: D

There is no compilation error but there will no output because function is returning a

value and if statement is true in this case.

Q.2 Choose the correct one

(A) Address operator can not be applied to register variables

(B) Address operator can be applied to register variables

(C) Use of register declaration will increase the execution time

(D) None of the above

Ans: D

A register access is much faster than a memory access, keeping the frequently

accessed variables in the register will lead to faster execution of programs.

Q.3 What is the following program doing?

main ()

{ int d = 1;

do

printf(“%d\n”, d++);

while (d < = 9);}

(A) Adding 9 integers (B) Adding integers from 1 to 9

(C) Displaying integers from 1 to 9 (D) None of these

Ans: C

d starting from 1 is incrementing one by one till d=9 so the printf statement is printing

numbers from 1 to 9.

Q.4 What is the output of the following program?

main ( )

{ extern int x;

x = 20;

printf(“\n%d”, x);

}

(A) 0 (B) 20

(C) error (D) garbage value

Ans: C

Output of the given program will be “Linker error-undefined symbol x”. External

variables are declared outside a function.

Q.5 If x is one dimensional array, then pick up the correct answer

(A) *(x + i) is same as &x[i] (B) *&x[i] is same as x + i

(C) *(x + i) is same as x[i] +1 (D) *(x + i) is same as *x[i]

Ans: A

num[i] is same as *(num+i)

Q.6 Consider the following declaration

int a, *b = &a, **c = &b;

The following program fragment

a = 4;

**c = 5;

(A) does not change the value of a (B) assigns address of c to a

(C) assigns the value of b to a (D) assigns 5 to a

Ans: D

The given statements assigns 5 to a

Q.7 Choose the correct answer

(A) enum variable can not be assigned new values

(B) enum variable can be compared

(C) enumeration feature increase the power of C

(D) None of the above

Ans: C

The enumerated data types give an opportunity to invent our own data typeand define

what value the variable of this data type can take.

Q.8 The content of file will be lost if it is opened in

(A) w mode (B) w+ mode

(C) a mode (D) a+ mode

Ans: A

When the mode is writing, the contents are deleted and the file is opened as a new file.

Q.9 Consider the following code segment:

int a[10], *p1, *p2;

p1 = &a[4];

p2 = &a[6];

Which of the following statements is incorrect w.r.t. pointers?

(A) p1 + 2 (B) p2 – 2

(C) p2 + p1 (D) p2 – p1

Ans: C

Addition of two pointers is not allowed.

Q.10 The second expression (j – k) in the following expression will be evaluated

(i + 5) && (j – k)

(A) if expression (i + 5) is true.

(B) if expression (i + 5) is false.

(C) irrespective of whether (i + 5) is true or false.

(D) will not be evaluated in any case.

Ans: A

In a compound logical expression combined with &&, the second expression is

evaluated only if first is evaluated in true.

In the for statement: for (exp1; exp2; exp3) { … }

where exp1, exp2 and exp3 are expressions. What is optional?

(A) None of the expressions is optional.

(B) Only exp1 is optional.

(C) Only exp1 and exp3 are optional.

(D) All the expressions are optional.

Ans: D

All the expressions are optional. For (;;) is a valid statement in C.

Q.12 The output of the following code segment will be

char x = ‘B’;

switch (x) {

case ‘A’: printf(“a”);

case ‘B’: printf(“b”);

case ‘C’: printf(“c”);

}

(A) B (B) b

(C) BC (D) bc

Ans: D

Since there is no break statement, all the statement after case’B’ are executed.

Q.13 What will be the output of the following code segment?

main( ) {

char s[10];

strcpy(s, “abc”);

printf(“%d %d”, strlen(s), sizeof(s));

}

(A) 3 10 (B) 3 3

(C) 10 3 (D) 10 10

Ans: A

strlen(s) give the length of the string, that is 3 and sizeof(s) give the size of array s

that is 10.

Q.14 Which of the following is the odd one out?

(A) j = j + 1; (B) j =+ 1;

(C) j++; (D) j += 1;

Ans: B

j=+1 is odd one out as rest all means incrementing the value of variable by 1.

Q.15 Which of the following is true for the statement:

NurseryLand.Nursery.Students = 10;

(A) The structure Students is nested within the structure Nursery.

(B) The structure NurseryLand is nested within the structure Nursery.

(C) The structure Nursery is nested within the structure NurseryLand.

(D) The structure Nursery is nested within the structure Students.

Ans: C

The structure Nursery is nested within the structure NurseryLand.

Q.16 What will be the output of the following code segment, if any?

myfunc ( struct test t) {

strcpy(t.s, “world”);

}

main( ) {

struct test { char s[10]; } t;

strcpy(t.s, “Hello”);

printf(“%s”, t.s);

myfunc(t);

printf(“%s”, t.s);

}

(A) Hello Hello (B) world world

(C) Hello world (D) the program will not compile

Ans: D

The program will not compile because undefined symbol s for myfunc( ) function.

Structure should be defined before the main and the function where it is called.

Q.17 If a function is declared as void fn(int *p), then which of the following statements is

valid to call function fn?

(A) fn(x) where x is defined as int x;

(B) fn(x) where x is defined as int *x;

(C) fn(&x) where x is defined as int *x;

(D) fn(*x) where x is defined as int *x;

Ans: B

Function void fn(int *p) needs pointer to int as argument. When x is defined as int

*x, then x is pointer to integer and not *x.

Q.18 What is the following function computing? Assume a and b are positive integers.

int fn( int a, int b) {

if (b == 0)

return b;

else

return (a * fn(a, b - 1));

}

(A) Output will be 0 always (B) Output will always be b

(C) Computing ab (D) Computing a + b

Ans: A

The output is always be 0 because b is decremented in recursive function fn each time

by 1 till the terminating condition b==0 where it will return 0.

Q.19 What is the output of the following C program?

# include <stdio.h>

main ( )

{

int a, b=0;

static int c [10]={1,2,3,4,5,6,7,8,9,0};

for (a=0; a<10;+ + a)

if ((c[a]%2)= = 0) b+ = c [a];

printf (“%d”, b);

}

(A) 20 (B) 25

(C) 45 (D) 90

Ans: A

printf statement will print b which is sum of the those values from array c which get

divided by 2, that is 2+4+6+8=20.

Q.20 If a, b and c are integer variables with the values a=8, b=3 and c=-5. Then what is the

value of the arithmetic expression:

2 * b + 3 * (a-c)

(A) 45 (B) 6

(C) -16 (D) -1

Ans: A

the value of the arithmetic expression is 45 as 2*3+3*(8—5)=6+3*13=6+39=45

Thank you, Keep Learning

Read More

Digital Library Book list

Algorithm 

Introduction to Algorithms 3rd.Edition - (CLRS)

Aptitude 

100 aptitude trick(102pgs)s

Artificial Intelligence 

Artificial Intelligence A Modern Approach Third Edition -  Stuart Russel

Assembly Language

Assembly Language for X86 Processors KIP R. Irvine

C Language

C Programming for absolute beginners 

Head First C

Pointers & Memory

C Solved Program List (Part I)

C questions and answer

C++

Effective_Modern_C++ - Scott Meyers

Modern C++ Programming Cookbook - Marius Bancila

The C ++Programming Language - Bjarne Stroustrup

OBJECT_ORIENTED_PROGRAMMING Question & Answer

Competitive Programming

Competitive Programming hand book

Competitive_programming

Company Placement Materials

Aptitude shortcut prime material

DevOps

DevOps with Kubernetes -  Hideto Saito

Digital Electronics 

Moris Mano Degital Design 3rd Edition

Drupal

Drupal 8 Module Development by Daniel Sipos

Excel

Mircrosoft_Excel_2019_Bible . M Alexander, Richard Kusleika,John

Flutter

Beginning App Development with Flutter by Rap Payne 

HTML & CSS & Javascript

HTML & CSS Design and Build Website

JavaScript Data Structures and Algorithms

HTML5 & javascript  By :- Jeanine Meyer

THE HTML AND CSS WORKSHOP

Hacking

CEH : Certified Ethical Hackers, All in one Exam Guide

Hacking: The Art of Exploitation, 2nd Edition

Web security for developers - malcolm mcdonald

Hacking The Xbox

KALI LINUX WIRELESS PENETRATION TESTING BEGINNERS GUIDE THIRD EDITION - Cameron Buchanan, Vivek Ramachandran

ICSE 

ICSE Class X Computer Application Notes

Internet Of Things 

INTERNET  OF THINGS PROJECTS WITH ESP32

Java

Introduction to Programming in Java

Java The Complete Reference Ninth Edition

Java The Complete Reference Eleventh_Edition

Jira 

Jira 8 Administration Cookbook Third Edition

Microsoft Power BI

MICROSOFT POWER  BI COOKBOOK

MongoDB

MongoDB in Action, 2nd Edition

Networking

Data_Communications and Networking 4th Ed Behrouz A Forouzan

PHP

Gunnard Engebreth PHP 8 Revealed Use Attributes the JIT Compiler

Python

Data Analysis from scratch with Python

Head First Python

Foundations of Agile Python Development (2008)

Python For Beginners Ride The Wave Of Artificial Intelligence

 Python Data Science - The Bible - Mark Solomon Brown

Full_Book_Python_Data_Structures_And_Algorithm

Cracking Codes with Python An Introduction to Building and Breaking

ADVANCED DEEP LEARNING WITH PYTHON

PostgreSQL

Thomas S.M. - PostgreSQL High Availability Cookbook - 2017

PostgreSQL

React

Pro React 16

react hooks in Action - John Larsen

SQL

SQL Learning (2nd Edition)

SQL : Introduction, Entity- relationship model, Relational Model

Unix/Linux

The-Linux-Command-Line-A-Complete-Introduction

Read More