B.E 3rd Sem Data Structure Assignment-1

Government Engineering College, Patan

B.E 3^rd SEM CSE Department

DATA STRUCTURE (2130702)

Assignment:-1

Stack:

1)      Define Data Structure and classify it.

2)      What do you mean by Data Structure? Give the difference between Primitive and Non-primitive data structures.

3)  Define array and give its representation.

4)  Discuss applications of an array.

5)  Discuss sparse matrix and its representation.

6)  What is Stack? Write down algorithms for performing PUSH and POP operations on a stack.

7)  Write user-defined functions in C to perform four stack operations.

8)  Define the concept of recursion with suitable example.

9)  Discuss a stack application "Tower of Hanoi" with algorithm.

10) Write a 'C’ program for followings using recursion:

·         Factorial

11)  Explain Postfix Notation in detail with suitable example.

12)  Convert following infix expression into postfix format showing stack status after every step in tabular form.

A. A+ (B*C-(D/E^F)*G)*H

B. (A*B+ (C/D))-F

C. A*B/C/D-E*F*G*(H-2)

E. A + B*(C+ D/E*F* (G + H) * I)-K

F. (A + B*C/D-E + F/G/ (H + I))

            G. (A + B) * C + D / (B + A * C) + D

H. A*(B+C/D*E)/ (F+G*H/ (I+J))

I. A+B*C-D/E*H

J. ((A+B)*C-(D-E)) $(F+G)

K. P * (Q - R/S * T) / (A + B * C/D + E)) + F

13)  Convert following infix expressions to polish (prefix) notation.

a. A+B*C-D/E*H

 b. A*(B+C/D*E)/(F+G*H/(I+J))

14)  Convert following Infix expression into Postfix expression. Show each step.

A + B ^ C^ D - E * F / G

15)  Evaluate the following expression showing status of stack in tabular Form:

            a. 546+*493/+*

b. 7 5 2 + * 4 1 1 + / -

c. 3 5 * 6 2 / +

d. 12, 7, 3, -, /, 2, 1, 5, +, *, +

16)  Evaluate the following postfix expression using stack

        AB+CD/*GH*+ ((where A=2, B=4, C=6, D=3, G=8, H=7))

Queue:

17) State the difference between LIFO and FIFO.

18) Discuss representation of Queue and operations on Queue.

19) Write an algorithm to insert an element into and delete an element from singly queue.

20) What is the drawback of the simple queue? How can we overcome it? (State the advantages of circular queue over normal queue.)

21) Write an algorithm to insert an element into and delete an element from circular queue.

22) Define following terms:

a. Priority Queue

 b. Dequeue

23) What is the difference between simple queue, circular queue, double ended queue (dequeue) and priority queue?

24) Discuss applications of queue with example.

Linked List:

25) Explain: Linear linked list. .

26) State the advantage of circular linked list over singly linked list.

27) Write algorithm to insert and delete element at the beginning, ending, Middle & Sorted of singly linked list.

28) Explain circular linked list, doubly linked list.

29) Explain the applications of linked list.

30) State advantages and disadvantages.         

31) Write down advantages of linked list over array and explain it in detail.