[email protected] +91 9175287066
This website is always under updation with new contents
Unit - I Introduction to Data Structures
Unit I
Unit II
Unit III
Unit IV
Unit V
1. How are the binary and decimal integers stored in memory?
Ans:
Computer memory is divided into three sections: main memory, cache memory in the central processing unit (CPU), and persistent storage.
Main memory, also called random access memory (RAM), is where instructions (programs) and data are stored. Main memory is volatile; that is, instructions and data contained in main memory are lost once the computer is powered down.
Cache memory in the CPU is used to store frequently used instructions and data that has been used by the CPU.
Persistent storage is an external storage device such as a hard disk that stores instructions and data. Persistent storage is nonvolatile; that is, instructions and data remain stored even when the computer is powered down.
Storage of binary number in memory
Memory is a bunch of electronic switches called transistors that can be placed in one of two states: on or off. The state of a switch is meaningless unless we assign a value to each state, which we do using the binary numbering system.
The binary numbering system consists of two digits called binary digits (bits): zero and one. A switch in the off state represents zero, and a switch in the on state represents one. This means that one transistor can represent one of two digits.
A numbering system is a way to count things and perform arithmetic. For example, humans use the decimal numbering system, and computers use the binary numbering system. Both these numbering systems do exactly the same thing: they enable us to count things and perform arithmetic. We can add, subtract, multiply, and divide using the binary numbering system and we’ll arrive at the same answer as if we used the decimal numbering system.
However, there is a noticeable difference between the decimal and binary numbering systems: the decimal numbering system consists of 10 digits (0 through 9) and the binary numbering system consists of 2 digits (0 and 1).
Storage of decimal integers in memory:
2. What do you mean by data types? Or what are the different data types used to store the data and information? Explain in each of them with suitable example.
Ans:
Data type:
Each variable in algorithm has a data type. Data type determines the code for storing data.
The data can be categorized in following four categories:
a) Character
b) Real
c) Integer
d) Logical
Integers
The integer abstract data type group consists of four abstract data types used to reserve memory to store whole numbers: byte , short , int , and long.
Depending on the nature of the data, sometimes an integer must be stored using a positive or negative sign, such as a +10 or –5. Other times an integer is assumed to be positive so there isn’t any need to use a positive sign. An integer that is stored with a sign is called a signed number; an integer that isn’t stored with a sign is called an unsigned number.
What’s all this hoopla about signed numbers? The sign takes up 1 bit of memory that could otherwise be used to represent a value. For example, a byte has 8 bits, all of which can be used to store an unsigned number from 0 to 255. You can store a signed number in the range of –128 to +127.
C and C++ support unsigned integers. Java does not. An unsigned integer is a value that is implied to be positive. The positive sign is not stored in memory. All integers in Java are represented with a sign. Zero is stored as a positive number.
Floating-Point
Abstract data types in the floating-point group are used to store real numbers in memory. A real number contains a decimal value. There are two kinds of floating point data types: float and double The float abstract data type is a single precision number, and a double is a double precision number. Precision of a number is the number of places after the decimal point that contains an accurate value.
The term floating-point refers to the way decimals are referenced in memory. There are two parts of a floating-point number: the real number, which is stored as a whole number, and the position of the decimal point within the whole number. This is why it is said that the decimal point “floats” within the number. For example, the floating-point value 43.23 is stored as 4323 (no decimal point). Reference is made in the number indicating that the decimal point is placed after the second digit.
Characters
A character abstract data type is represented as an integer value that corresponds to a character set. A character set assigns an integer value to each character, punctuation, and symbol used in a language.
For example, the letter A is stored in memory as the value 65, which corresponds to the letter A in a character set. The computer knows to treat the value 65 as the letter A rather than the number 65 because memory was reserved using the char abstract data type. The keyword char tells the computer that the integer stored in that memory location is treated as a character and not a number.
There are two character sets used in programming, the American Standard Code for Information Interchange (ASCII) and Unicode. ASCII is the granddaddy of character sets and uses a byte to represent a maximum of 256 characters. However, a serious problem was evident after years of using ASCII. Many languages such as Russian, Arabic, Japanese, and Chinese have more than 256 characters in their language. A new character set called Unicode was developed to resolve this problem. Unicode uses 2 bytes to represent each character. Choose a char whenever you need to store a single character in memory.
Boolean Abstract Data Type
A boolean abstract data type reserves memory to store a boolean value, which is a true or false represented as a zero or one. Choose a boolean whenever you need to store one of two possibilities in memory.
3. Explain the abstract data type specification. Or Explain Abstract Data Type (ADT).
Ans:
An abstract data type is a keyword of a programming language that specifies the amount of memory needed to store data and the kind of data that will be stored in that memory location. However, an abstract data type does not tell the computer how many bytes to reserve for the data. The number of bytes reserved for an abstract data type varies, depending on the programming language used to write the program and the type of computer used to compile the program.
Abstract data types in Java have a fixed size in order for programs to run in all Java runtime environments. In C and C++, the size of an abstract data type is based on the register size of the computer used to compile the program. The int and float data types are the size of the register. A short data type is half the size of an int , and a long data type is double the size of an int .
The abstract data type also tells the computer the kind of data that will be stored at the memory location. This is important because computers manipulate data of some abstract data types differently than data of other abstract data types.
Each memory address represents 1 byte of memory. Some abstract data types, such as an int, reserve 2 bytes of memory. Technically, data stored in this memory location has two memory address: one address for the first byte of memory and another address for the second byte of memory. However, the computer references only the address of the first byte of memory when accessing that memory location.
The double abstract data type is used to store real numbers that are very large or very small and require double the amount of memory that is reserved with a float abstract data type
4. Write an ADT for varying length string for substring. Or Explain Abstract Data Type (ADT) for varying length and fixed length record. Or Write an ADT specification for the varying length data string.
Ans:
ADT of varying length character string:
There are four basic operation normally included in systems that support varying character string.
These operations are:
a) Length of string:
Length returns the number of characters in a string (word or set of word) including space
b) Concatenation of two strings:
Concatenation means the addition (combine) of two strings.
The length of concatenated string is the sum of length of both input strings
c) Get a sub string from a string:
Sub strings are the part of strings. For this we need to specify starting position of the part of strings to be extracted and number of characters.
d) To get first position of substring from a string
The ADT is as follows:
Abstract typedef string
String s;
Post condition legth=len(s);
Method to concatenate two strings:
Abstract strings concat (s1,s2)
Strings s1,s2;
Post condition cancat=s1+s2;
Method to extract part of strings:
Abstract string substr(s1,j,k)
Strings s1;
Int j,k;
Pre condition 0<=j<=len(s1)
0<=k<=len(s1)=j;
Post condition substr=sub(s1,j,k);
Explain the representation of one dimensional array in memory. Or explain the array representation of list of memory with suitable example.
Ans:
An array is a way to reference a series of memory locations using the same name. Each memory location is represented by an array element. An array element is similar to one variable except it is identified by an index value instead of a name. An index value is a number used to identify an array element.
We can also say that, Array is a
 An ordered collection of homogenous data structure
 Linear collection of data having same type
 E.g. An array of integers to store age
 An array of strings to store the name of students
One dimensional array:
 Only one subscript/index
 Declaring array
 Data_type var_name[index]
 E.g. int A[100]
 A[L…..U] : L lower, U upper bound
 Range: upper-lower+1
Representation of linear array in memory
Let LA is a linear array. As we know that the memory of computer is simply a sequence of address location as pictured in following figure.
LOC(LA[k])=address of elements LA[k] of the array LA
As LA is linear array hence, the elements of LA are stored in successive memory location cell. Hence it is not necessary for computer to keep track of the address of every elements of LA. Computer only keep track, address of the first elements denoted by Base(LA) and is called as the base address of LA.
Using the address Base(LA), the computer calculate the address of any elements of LA by the following formula:
LOC(LOC[k])=base(LA)+w(K-lower bond)
Where
W is the number of word per memory cell for the array LA.

For example
Consider the array auto, which record the number of automobile sold each year from 1932 through 1984.
Supposed auto appear in memory by using following rule:
Base(auto)=200
W=4 word per memory cells for auto. Then
LOC(auto[1932])=200
LOC(auto[1933])=204
LOC(auto[1934])=208 ans so on.
Then the address of array elements for the year k=1965 can be obtained by
LOC(auto[1965])=base(auto)+w(1965-lower bond)
=200+4(1965-1932)=332
Explain the representation of two dimensional arrays in memory. Find the addressing function by using column major order.
Ans:
Two dimensional array:
A two dimensional M*N array A is a collection of M*N data elements such that each elements is specified by pair of indices (such as j and k) called subscripts with the property that 1<=j<=M and 1<=k<=N.
 Declaration
int arr_name[row][column]
E.g. 3x3 matrix
 2 4 5
 1 6 7
 8 9 0
A[1][1] = 2
A[2][1]= 1
Write an algorithm which inserts given. ITEM of information into Kth position of a linear array LA.
Ans:
Inserting into a linear array:
Let LA be a linear array- which is a collection of data elements in the memory of computers.
Inserting refer to the operation of adding another elements to the collection “LA”.
INSERT(LA,N,K,ITEM)
Here LA is the linear array with N elements and K<=N. this algorithum insert an elements ITEM into Kth position In LA.
1)	Set J=N
2)	Repeat step 3 and 4 while J>=K
3)	[Move jth elements down ward]
	Set LA[J+1]=LA[J]
4)	Decrease counter
	J=j-1;
	{end of loop 2}
5)	[insert elements] set LA[k]=item
6)	[Reset n] set n=n+1
7)	Exit
Write an algorithm for inserting a node at the end of link list.
Inserting of a node in single link list at the end:

The algorithm INSERT_SL_END is to insert a node into a single linked list at the end of the list. INSERT_SL_END (HEADER,X)
HEADER is the pointer to the header node and X be the data f the node which is to be inserted.
a)	New=GETNODE(NODE)
b)	If(new=NULL)
	1)	Print”memory is insufficient; insertion is not possible”;
	2)	exit
c)	Else
	1)	Ptr=HEADER
	2)	While (ptr.link!=null) do
		Ptr=ptr.link
	3)	End of while
	4)	Ptr.link=new
	5)	New.link=null;
d)	End if
e)	Stop
Write am algorithm to insert a KEY element after the given ITEM element in single linked list.
Ans:
Inserting of a node in single link list at the any:

The algorithm INSERT_SL_END is to insert a node into a single linked list at the end of the list.
INSERT_SL_Any (HEADER,X, key)
HEADER is the pointer to the header node and X is the data f the node which is to be inserted. Key is the data of the key node after which the new node to be inserted.
1)	New=GETNODE(NODE)
2)	If(new=NULL)
	1) Print”memory is insufficient; insertion is not possible”;
	2) exit
	Else
	1) Ptr=HEADER
	2) While (ptr.link!=null && ptr.data!=key) do
		Ptr=ptr.link
3)	End of while
4)	If(ptr.Link==NULL) then
	1.	Print “key is not present in the list”
	2.	Exit
5)	Else
	1.	New.link=ptr.link;
	2.	new.data=X
	3.	ptr.link=new
6)	end if

7)	End if
8)	Stop
Write an algorithm to delete the last node from the linked list.
Ans:
Deleting of a node in single link list at the end:

The algorithm DELETE_SL_END is to insert a node into a single linked list at the end of the list.
DELETE_SL_END (HEADER,X)
HEADER is the pointer to the header node and X be the data of the node which is to be deleted.
1.	ptr=header
2.	if(ptr.link=null) then
	a.	print”the list is empty no deletion is possible”
	b.	exit
3.	else
	1.	while (ptr.link!=null) do
		ptr1=ptr
		ptr=ptr.link
	2.	end while
	3.	ptr1.link=null
	4.	returnnode(ptr)
4.	end if
5.	stop
Write an algorithm to delete the given. ITEM of information from the linked list.
Ans:
Deleting of a node in single link list at the any position:

The algorithm DELETE_SL_ANY is to insert a node into a single linked list at the end of the list.
DELETE_SL_ANY (HEADER,X,KEY)
HEADER is the pointer to the header node and X be the data of the node which is to be deleted. Key is the element of the node which is to be deleted.
1.	Ptr1=header
2.	Ptr=ptr1.link
3.	if(ptr.link=null) then
		print”the list is empty no deletion is possible”
		exit
4.	else
	1.	while (ptr.link!=null && ptr.DATA!=key) do
		ptr1=ptr
		ptr=ptr.link
	2.	end while
3.	if(ptr.link==Null)
		print”no key itenm is present”
4.	else
		ptr1.link=ptr.link
		returnnode(node)
		Exit

5.	end if
6.	stop
Suppose NAME1 is a linked list in memory, write an algorithm which copies NAME1 into a linked list NAME2.
Ans
Explain the Double linked list. What are the advantages and disadvantages of ONE WAY LINK LIST linked list? Or discuss the advantages, if any, of a ONE way linked list over a ARRAY.
Ans:
 Doubly linked lists
 Each node points to not only successor but the predecessor
 There are two NULL: at the first and last nodes in the list
 Advantage: given a node, it is easy to visit its predecessor. Convenient to traverse lists backwards

Array versus Linked Lists:
 Linked lists are more complex to code and manage than arrays, but they have some distinct advantages.
 Dynamic: a linked list can easily grow and shrink in size.
 We don’t need to know how many nodes will be in the list. They are created in memory as needed.
 In contrast, the size of a C++ array is fixed at compilation time.
 Easy and fast insertions and deletions
 To insert or delete an element in an array, we need to copy to temporary variables to make room for new elements or close the gap caused by deleted elements.
 With a linked list, no need to move other nodes. Only need to reset some pointers.
Advantages of doubly linked list over singly linked list:

For accessing computer programs go to TECHNOLOGY