Bubble Short

Q. Bubble sorts the following numbers in an array:
32, 51, 27, 85, 66, 23, 13, 57.
Ans:
Pass 1: 32 51 27 85 66 23 13 57
32 51 27 85 66 23 13 57
32 27 51 85 66 23 13 57
32 27 51 85 66 23 13 57
32 27 51 66 85 23 13 57
32 27 51 66 23 85 13 57
32 27 51 66 23 13 85 57
32 27 51 66 23 13 57 85
Pass 2: 32 27 51 66 23 13 57 85
27 32 51 66 23 13 57 85
27 32 51 66 23 13 57 85
27 32 51 66 23 13 57 85
27 32 51 23 66 13 57 85
27 32 51 23 13 66 57 85
27 32 51 23 13 57 66 85

Pass 3: 27 32 51 23 13 57 66 85
27 32 51 23 13 57 66 85
27 32 51 23 13 57 66 85
27 32 23 51 13 57 66 85
27 32 23 13 51 57 66 85
27 32 23 13 51 57 66 85


Pass 4: 27 32 23 13 51 57 66 85
27 32 23 13 51 57 66 85
27 23 32 13 51 57 66 85
27 23 13 32 51 57 66 85
27 23 13 32 51 57 66 85

Pass 5: 27 23 13 32 51 57 66 85
23 27 13 32 51 57 66 85
23 13 27 32 51 57 66 85
23 13 27 32 51 57 66 85

Pass 6: 23 13 27 32 51 57 66 85
13 23 27 32 51 57 66 85
13 23 27 32 51 57 66 85

Pass 7: 13 23 27 32 51 57 66 85
13 23 27 32 51 57 66 85


So the sorted list is - 13 23 27 32 51 57 66 85.
The computer computes the address LOC (A [J, K]) of A [J, K] using the formula –
(Column major order) LOC (A [J, K]) = Base (A) + w [M (K – 1) + (J – 1)]
(Row major order) LOC (A [J, K]) = Base (A) + w [N (J – 1) + (K – 1)]
Where, M = number of row
N = number of column
w = number of words per memory location for the array (int, char etc).
Example: - Base (SCORE) = 200
w = 4
J = 12
K = 3
M = 25
N = 4
Row – major order.
LOC (SCORE [12, 3]) = 200 + 4[4(12 – 1) + (3 – 1)]
= 200 + 4[(4 × 11) + 2]
= 200 + 4[44 + 2]
= 200 + (4×46)
= 200 + 184
= 384
Q. What do you mean by record?
Ans: Record: A record is a collection of related data items, each of which is called a field or attribute, and a file is a collection of similar records. Each data item itself may be a group item composed of sub-items.
Although a record may be a collection of data items, it differs from a linear array in the following ways –
• A record may be a collection of nonhomogeneous data.
• The data items in a record are indexed by attribute names, so there may not be a natural ordering of its elements.
Example: - A hospital keeps records of new born baby may be organized as follows:
1. New born.
(a) Name
(b) Sex
(c) Birthday
i. Month
ii. Day
iii. Year
(d) Father
i. Name
ii. Age
(e) Mother
i. Name
ii. Age
Q. Describe the representation of linear arrays in memory.

Ans: Representation of linear arrays in memory: Let, LA be a linear array in the memory of the computer. The memory of the computer is simply a sequence of addressed locations as pictured below and the notation –
LOC (LA [K]) = address of the element LA [K] of the array LA.
The elements of LA are stored in successive memory cells. Using address Base (LA), the computer calculates the address of any element of LA by the following formula:
LOC (LA [K]) = Base (LA) + w (K – lower bound).
Where w is the number of words per memory cell for the array LA.
Q. What is linear array? How length of array can calculate? Write array notation.
Ans: Linear array: A linear array is a list of a finite number n of homogeneous data elements such that:
a. The elements of the array are referenced respectively by an index set consisting of n consecutive numbers.
b. The elements of the array are stored respectively in successive memory locations.
Length of array: The length or the number of data elements of the array can be obtained from the index set by formula –
Length = UB – LB + 1.
Where, UB is the largest index, called the upper bound, and
LB is the smallest index, called the lower bound, of the array.
Array notation: The elements of an array A may be denoted by the subscript notation –
A1, A2, A3, … … …, An.
Or, by the parentheses notation –
A (1), A (2), A (3), … … … , A (N).
Or, by the bracket notation –
A [1], A [2], A [3], … … … , A [N].
Usually the subscript notation or the bracket notation is used.
Q. What are two dimensional arrays? Describe the representation of two dimensional arrays.
Ans: Two dimensional arrays: Two dimensional arrays are called matrices in mathematics and tables in business applications. Two dimensional arrays are sometimes called matrix arrays.
Let, A is a two dimensional m×n array where j is the first subscript and k is the second subscript. This two dimensional array is denoted by –
AJ.K or, A [J, K]
Length of two dimensional arrays: The length of two dimensional arrays can be obtained from the formula –
Length = upper bound – lower bound + 1.
Representation of two dimensional arrays in memory: Let A be a two – dimensional m×n array where m is rows and n is columns. The array will be represented in memory by a block of m.n sequential memory locations in following ways –
1. column by column, is called column – major order.
2. row by row, is called row – major order.
The following figure shows these two ways when A is a two – dimensional 3×4 array.

DATA STRUCTURE FOR STUDENTS

1. When there is no more memory space left to insert a new data item in a list, the situation is known as –
a. AVAIL
b. NULL
c. FULL
d. OVERFLOW
2. In case of LINKED LIST data structure, the essential field of a node is –
a. Data
b. Item
c. Address
d. Link
3. Array is a non – linear data structure used to store polynomials. The above statement is –
a. TRUE
b. FALSE
c. NONE
4. Let A be an M×N matrix and B be a Q×R matrix. Then when multiply two matrices if and only if –
a. M = N
b. M = P
c. N = Q
d. R = N
5. When we insert a new data item in a QUEUE data structure, the operation is referred as –
a. Insert
b. Push
c. Enqueue
d. Dequeue
6. Let A be a linear array and its upper bound = 1984 and lower bound = 1930. Then the length of the array is –
a. 51
b. 52
c. 54
d. 55
7. In case of declaration of an ARRAY data structure, the information that must be provided are –
a. The name of the ARRAY
b. The data type of the ARRAY
c. The index set
d. The storage type
8. In BUBBLE SORT algorithm, the number of the comparison required in Kth numbered step is –
a. K
b. K – 1
c. N – 1
d. N – K
Where N is the number of elements.
9. Binary search cannot be applied to LINKED LIST, because –
a. Linked list is not stored
b. No way to determine the middle element
c. Each node contains a pointer field
d. Nodes are not stored in sequential number
10. A row in a two – dimensional array is –
a. Vertical list of elements
b. Linear list of elements
c. Horizontal list of elements
d. Subset of the array
11. Two – dimensional ARRAY can be represented in the memory by using –
a. Row – major representation
b. Column – major representation
c. Row divided by Column
d. Non – linear representation
12. The major differences between RECORDS and ARRAY is –
a. Records require more memory space than Array
b. Records contain less data items than Array
c. Array contains homogenous data item whereas Records contains non – homogenous
d. Array is stored sequentially but Records are stored randomly.
13. In STACK we use a special pointer to access the data elements. This is called –
a. FRONT
b. REAR
c. TOP
d. AVAIL
14. Let Lower bound if an ARRAY is defined as 300 and the ARRAY has 62 elements. Then the Upper bound of the array will be –
a. 362
b. 363
c. 361
d. 364
15. In LINKED LIST, a NODE allocates memory space by using a special function. The function is –
a. Calloc ()
b. Malloc ()
c. Alloc ()
d. Cmalloc ()
16. Together with the linked list in memory, a special is maintained which consists of unused memory cells. This list is called –
a. List of available space
b. Free storage list
c. Free pool
d. Garbage collection
17. If any data s attempted to delete from an empty list, then it is known as –
a. Free pool
b. Underflow
c. Overflow
d. Deletion

DATA STRUCTURE

helpfull to all

Q. 1: Describe different types of string operations.
Ans: String operation:
Sub string: Accessing a substring from a given string requires three pieces of information:
i. The name of the string or the string itself.
ii. The position of the first character of the substr5ing in the given string and
iii. The length of the substring or the position of the last character of the substring.
We call this operation SUBSTRING. Specially, we write
SUBSTRING (String, initial, length)
To denote the substring of a string S beginning in a position K and having a length L.
Example:
SUBSTRING (‘TO BE OR NOT TO BE’, 4, 7) = ‘BE OR N’
Indexing: Indexing also called pattern matching, re4fers to finding the position where a string pattern P first appears in a given text T. We call this operation INDEX and write
INDEX (text, pattern)
If the pattern P does not appear in the text T, then INDEX is assigned the value 0. The argument “text” and “pattern” can be either string constants or string variables.
Example:
T = ‘HIS FATHER IS THE PROFESSIOR’
Then, INDEX (T, ‘THE’), INDEX (T, ‘THEN’)
Have the values 7, 0 respectively.
Concatenation: Let S1 and S2 be strings. Recall that the concatenation of S1 and S2, which we denote by S1//S2, is the string consisting of the characters of S1 followed by the characters of S2.
Example:
Suppose, S1 = ‘MARK’,
And, S2 = ‘TWAIN’
Then, S1//S2 = ‘MARKTWAIN’
But, S1//’ ‘//S2 = ‘MARK TWAIN’
Length: The number of characters in a string is called its length. We will write –
LENGTH (string)
for the length of a given string.
Example:
Thus LENGTH (‘COMPUTER’) = 8
LENGTH (‘ ’) = 0
LENGTH (‘’) = 0
Q. 2: Describe different types of word processing.
Ans: Word processing: The operations usually associated with word processing are the following:
a. Insertion: Inserting a string in the middle of the text. Suppose in given text T, we want to insert a string S, so that S begins in position K. We denote this operation by
INSERT (text, position, string)
For example, INSERT (‘ABCDEFG’, 3, ‘XYZ’) = ‘ABXYZCDEFG’
b. Deletion: Deleting a string from the text. Suppose in a given text T we want to delete the substring which begins in position K and has length L. We denote this operation by
DELETE (text, position, length)
For example, DELETE (‘ABCDEFG’, 4, 2) = ‘ABCFG’
c. Replacement: Replacing one string in the text by another. Suppose in a given text T we want to replace the first occurrence of a pattern P1 by a pattern P2. We will denote this operation by
REPLACE (text, pattern1, pattern2)
For example, REPLACE (‘XABYABZ’, ‘AB’, ‘C’) = ‘XCYABZ’

1at blog

Q. 1: What is data structure? Describe the different types of data structure.

Ans: Data Structure: Data may be organized in many different ways; the logical or mathematical model of a particular organization of data is called a data structure.

Different types of data structure:

• Arrays: The simplest type of data structure is a linear array. A linear array is a list of a finite number n of homogeneous data elements such that:
  

• The elements of the array are referenced respectively by an index set consisting of n consecutive numbers.


• The elements of the array are stored respectively in successive memory locations.
  

Linear arrays are called one dimensional array. A two dimensional array is a collection of similar data elements where each elements is referenced by two subscripts and multidimensional arrays are defined analogously.

• Records:A record is a collection of related data items, each of which is called a field or attribute and a file is a collection of similar records.
  

Example: A hospital record on each new born baby:

• New born
  


• Name


• Sex


• Birthday
  


• Month


• Day


• Year
  


• Father
  

• Name


• Age
  


• Mother
  

• Name


• Age
  


• Link lists:A linked list or one way list is a linear collection of data elements, called nodes, where the linear order is given by means of pointers. Each node is divided into two parts: the first part contains the information of the element, and the second part called the link field or next pointer field contains the address of the next node in the list.

• Stacks: A stack is a list of elements in which an element may be inserted or deleted only at one end, called the top of the stack. This means that elements are removed from a stack in the reverse order of that in which they were inserted into the stack. Stacks are called last in first – out (LIFO) system. Special terminology is used for two basic operations associated with stacks:
  


• “Push” is the term used to insert an element into a stack.


• “Pop” is the term used to delete an element from a stack.
  


• Queues: A queue is a linear list of elements in which deletion can take place only at one end, called the front and insertions can take place only at the other end, called the rear. The terms “front” and “rear” are used in describing a linear list only when it is implemented as a queue. Queues are called first in first out (FIFO) lists.


• Trees: Tree is a non linear data structure. Tree is used to represent data containing a hierarchical relationship between elements, e.g. records, family trees and table of contents. Binary tree is a special kind of tree, which can be sassily maintained in the computer.

Graphs: Data sometimes contain a relationship between pairs of elements which is not necessarily hierarchical in nature. The data structure which reflects this type of relationship is called a graph.

Q. 2: Define different types of data structure operations.

Ans: Data structure operations: The following four operations play a major role in data structure operation:

• Traversing: Accessing each record exactly once, so that certain items in the record may be processed.


• Searching:Finding the location of the record with a given key value, or finding the locations of all records which satisfy one or more conditions.


• Inserting:Adding a new record to the structure.


• Deleting: Removing a record from the structure.

The following two operations, which are used in special situations:

• Sorting: Arranging the records in some logical order.


• Merging: Combining the records in two different sorted files into a single sorted file.

Q.3: What is time space trade off?

Ans: Time space trade off: The time space trade off refers to a choice between algorithmic solutions of a data processing problem that allows one to decrease the running time of an algorithm solution by increasing the space to store the data and vice versa.

Q.4: What is algorithm complexity?

Ans: Algorithm complexity: The complexity of an algorithm M is the function f(n) which gives the running time and / or storage space requirement of the algorithm in terms of the size n of the input data.

DATA STRUCTURE FOR STUDENTS

please wait a while