DataStructure LMN PDF

|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
An array is collection of items stored at continuous memory locations. The idea is to declare
multiple items of same type together.
Array declaration:
In C, we can declare an array by specifying it’s and size or by initializing it or by both.
// Array declaration by specifying size

int arr[10];
// Array declaration by initializing elements

int arr[] = {10, 20, 30, 40};
// Array declaration by specifying size and

// initializing elements
int arr[6] = {10, 20, 30, 40}
Formulas:
Length of Array = UB - LB + 1
Given the address of first element, address of any other element is calculated using the
formula:-
Loc (arr [k]) = base (arr) + w * k

w = number of bytes per storage location
of for one element
k = index of array whose address we want
to calculate
Shivam M. Trivedi Page 1

Elements of two-dimensional arrays (mXn) are stored in two ways:-
 Column major order: Elements are stored column by column, i.e. all elements of first
column are stored, and then all elements of second column stored and so on.
Loc(arr[i][j]) = base(arr) + w (m *j + i)
 Row major order: Elements are stored row by row, i.e. all elements of first row are
stored, and then all elements of second row stored and so on.
Loc(arr[i][j]) = base(arr) + w (n*i + j)
Stack is a linear data structure which follows a particular order in which the operations are
performed. The order may be LIFO (Last in First Out) or FILO (First in Last Out).
Basic operations
1. Push: Adds an item in the stack. If the stack is full, then it is said to be an Overflow
condition. (Top=Top+1).
2. Pop: Removes an item from the stack. The items are popped in the reversed order in
which they are pushed. If the stack is empty, then it is said to be an Underflow
condition.
(Top=Top-1).
3. Peek: Get the topmost item.
Infix, prefix, and Postfix notations
1. Infix notation: “X + Y” Operators are written in-between their operands. This is the
usual way we write expressions. An expression such as
A * (B + C) / D
2. Postfix notation (also known as “Reverse Polish notation”): “X Y +” Operators are

written after their operands. The infix expression given above is equivalent to
A B C + * D/

3. Prefix notation (also known as “Polish notation”): “+ X Y” Operators are written before
their operands. The expressions given above are equivalent to
/ * A + B C D
Tower of Hanoi
Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The
objective of the puzzle is to move the entire stack to another rod, obeying the following
simple rules:
1. Only one disk can be moved at a time.

2. Each move consists of taking the upper disk from one of the stacks and placing it on top
of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
3. No disk may be placed on top of a smaller disk.
For n disks, total 2n – 1 move are required

Time complexity: O (2n) [exponential time]
Queue is a linear structure which follows a particular order in which the operations are
performed. The order is First in First out (FIFO). A good example of queue is any queue of
consumers for a resource where the consumer that came first is served first.
 Stack: Remove the item the most recently added

 Queue: Remove the item the least recently added
Operations on Queue
1. Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an
Overflow condition.
2. Dequeue: Removes an item from the queue. The items are popped in the same order in
which they are pushed. If the queue is empty, then it is said to be an Underflow
condition.
3. Front: Get the front item from queue.
4. Rear: Get the last item from queue.

Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at
contiguous location; the elements are linked using pointers.
Advantages over arrays
1. Dynamic size
2. Ease of insertion/deletion
Drawbacks
1. Random access is not allowed. We have to access elements sequentially starting

from the first node. So we cannot do binary search with linked lists.
2. Extra memory space for a pointer is required with each element of the list.
Representation in C: A linked list is represented by a pointer to the first node of the
linked list. The first node is called head. If the linked list is empty, then value of head
is NULL.
Each node in a list consists of at least two parts
1. Data
2. Pointer to the next node In C, we can represent a node using structures. Below is an
example of a linked list node with an integer data.
// A linked list node

struct node
{
int data;
struct node *next;
};
 Long Questions
1. Differentiate List and Array.
2. Define Algorithm. Explain Key features of and algorithm.
3. Write a short note of Doubly Linked List.
4. Write a short note on Circular Linked List.

5. Differentiate Stack and Queue.
6. Explain collision resolution techniques.
7. Define tree. Explain applications of tree.
8. Explain different tree traversal methods with example.
9. What is Hashing? Explain any two hashing techniques.
10. Differentiate circular linked list and singly linked list.
11. Define following terms necessary example/figure: Indegree, Leaf node, Direct edge,
and Path.
12. Application of stack and queue.
13. Short note: DMA
14. What is Data structure? Explain its type. [linear, non-linear, primitive, non-
primitive]
 Algorithm
1. Write and algorithm to compare two strings without using library function
‘strcmp’.
2. Write and explain POP and PUSH operation algorithm of stack.
3. Write an algorithm to insert an element in Queue.
4. Write an algorithm to insert new node at the starting of singly linked list.
5. Write an algorithm of Bubble sort, Merge Sort, Quick Sort, Insertion Sort, and
Selection sort.
6. Write an algorithm for inserting and deleting a node from circular queue.
7. Write an algorithm for connate two strings.
8. Write an algorithm for compare two strings.
9. Write an algorithm to insert a node in singly linked list.
10. Write an algorithm to delete a node from beginning in doubly linked list.
11. Write an algorithm to find length of given string without using library function.
12. Write an algorithm for Binary search.
13. Write an algorithm to search a node in singly linked list.
14. Write an algorithm to count the number of nodes in singly linked list.
15. Write an algorithm for post order tree traversal method.
16. Write an algorithm for in-order tree traversal method.
 Short Questions
1. Define Time and Space complexity.
2. List out applications of data structure and explain any one.
3. Explain puts() and putchar() with an example.

4. Define pointer and write an advantages of pointer.
5. Write applications of linked list.
6. Define Hashing.
7. Define Forest, BST, Leaf node and Indegree.
8. Define row-major and column-major array.
9. Define string and list out different string operations.
10. Define big-oh notation.
11. Define singly linked list and structure.
12. Differentiate: Simple queue v Circular queue.
13. Define collision. List out collision resolution techniques.


DataStructure LMN PDF

Uploaded by

Copyright:

Available Formats

DataStructure LMN PDF

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

DataStructure LMN PDF

Uploaded by

Copyright:

Available Formats

|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

In C, we can declare an array by specifying it’s and size or by initializing it or by both.

// Array declaration by specifying size

// Array declaration by initializing elements

// Array declaration by specifying size and

Loc (arr [k]) = base (arr) + w * k

Shivam M. Trivedi Page 1

Loc(arr[i][j]) = base(arr) + w (n*i + j)

Infix, prefix, and Postfix notations

2. Postfix notation (also known as “Reverse Polish notation”): “X Y +” Operators are

Shivam M. Trivedi Page 2

1. Only one disk can be moved at a time.

For n disks, total 2n – 1 move are required

 Stack: Remove the item the most recently added

Shivam M. Trivedi Page 3

Advantages over arrays

1. Random access is not allowed. We have to access elements sequentially starting

Each node in a list consists of at least two parts

// A linked list node

Shivam M. Trivedi Page 4

Shivam M. Trivedi Page 5

Shivam M. Trivedi Page 6

You might also like