1.
Derive the formula to find physical address of an element of three dimensional array
stored in row major order.
2. What do you mean by complexity? Explain time complexity and space complexity
and write down time-space trade off.
3. What is sparse matrix? Explain. Write the applications of sparse matrix?
4. Consider the linear array, A(5:50), whose base address is 300 and the number of
words per memory cell is 4. Find the address of A[15].
5. Consider the linear arrays AAA[5:50],BBB[-5:10] and CCC[1:8]
a. Find the number of elements in each array?
b. Suppose base (AAA) =300 and w=4 words per memory cell for AAA. Find the
address of AAA[15],AAA[35] and AAA[55].
6. Describe various form of data structure. Define data structure and also describe the
difference between primitive and non-primitive data structure. Write most commonly
used function in data structure. What are the factors that affect the choice of data
structure?
7. Define Linked List? What are the applications of Linked List?
8. Explain the method to represent the polynomial equation using Iinked list. Write and
explain method to add two polynomial equations using linked list.
9. Write a C function to count the number of nodes in singly linked list?
10. What are advantages and disadvantages of doubly linked list over singly linked list?
11. Explain Garbage Collection and Compaction.
12. What do you mean by Stack? Explain with suitable example with all its operation.
How stack can be represented in memory?
13. State the Tower of Hanoi problem. Write recursive algorithm to solve the problem.
14. Write an algorithm to convert INFIX expression to postfix expression. Carefully state
any assumption you make regarding the input.
15. Write the algorithm to evaluate a postfix expression using a stack.
16. Write an algorithm to convert a valid arithmetic infix expression into its equivalent
postfix expression.
17. Convert the following arithmetic expression into postfix and show stack status after
every step in tabular forms: A+(B*C-(D/E-F)*G)*H
18. Write an algorithm for evaluating an expression in postfix form. Consider the
following infix expression ((a+b)+c^ (d+e)+f)^(g+h) Convert the expression to
equivalent prefix expression and postfix expression.
19. Convert the following arithmetic expression into postfix and show stack status after
every step at each step:
a. (A+B)*D+E / (F+A*D)+
b. A*(B+C) / D- G
c. 3* LOG (X+1) –A/2
20. Explain queue data structure. Write an algorithm and c function to implement Queue
using Array and Linked list. Write algorithm for performing insertion and deletion in
it.
21. Show, how a priority queue can be implemented using linked list.
22. How would you implement a circular queue of integers in C using array? Write
routines to implement the appropriate operations for it.
23. Discuss the array representation of the binary tree
24. Draw binary tree of following algebraic equation:
[a + (b - c)] * [(d - e) / (f + g - h)]
25. A recursive function f is shown below. What is the value of f(5)?int f (int x)
{
if (x<2)
return 1;
else
return f(x-1)+f(x-2);
}
26. Comparison between Array and Linked List.
27. Write an algorithm to insert and delete a node from doubly linked list. Illustrate with
an example.
28. What is the need of different type of data structure?
29. What is the advantage of linked list over array? Explain in brief.
30. Discuss some application of asymptotic analysis of algorithm.
31. Differentiate between time complexity and space complexity of an algorithm.
32. A two dimensional array GU [6][8] is stored ion row major order with base address
351. What is the address of GU[3][4].
33. What are the parameters to judge the efficiency of an algorithm?
34. Write the merits and demerits of static and dynamic memory allocation?
35. What do you understand by the term algorithm? Describe the characteristics of an
algorithm.
36. Write the traversing algorithm for linear array.
37. What is doubly link list? Write a c program to insert a new node at the end of a
doubly linked list.
38. Write a procedure to that concatenates two circular linked list into one circular link
list.
39. Write an algorithm and C function to reverse a single link list
40. Write a program in C to implement a queue using linked list. Your program should at
least contain ADD, CREATE, DELETE, FULL and EMPTY function.
41. Give an equivalent postfix expression for the following infix expression (A+B) –
(C+D*E)/F*G.
42. Which data structure used for implementing recursion? Why.
43. Distinguish between ordinary queue and circular queue.
44. Define polish notation with example.
45. Explain a circular queue. What is the condition of if the circular queue is full?
46. Explain queue with suitable example. Also give procedure to insert and delete an
element from queue.
47. Write a program in C to find the Greatest Common Divisor of two positive number
using recursion functions.
48. Write a function for conversion of an infix expression to postfix expression.
49. What is recursion? Write a program to solve Tower of Hanoi problem.
50. Define stack. Write a c program to implement stack using array.
51. What do you understand by tail recursion? Give example. Discus its significance.
52. Show the detailed content of the stack for given postfix expression to evaluate
623+ -382/+*2^3+
a) Draw the expression tree of the following infix expression. Convert it into prefix and
post fix expression.
((a + b) + c* (d + e) + f) * (g + h)
53. If the inorder traversal of a binary tree is B,I,D,A,C,QE,H,F and its postorder traversal
is I,D,B,QC,H,F,E,A, determine the binary tree.
54. Explain different method of binary tree representation.
55. Discuss the application of binary tree for algebraic expression.
56. Illustrate the use of stack to convert the following infix expression to postfix: A* (B + C ^D) – E
^F*(G/H).
57. Draw a binary tree for the following algebraic expression
[a + (b – c)]* [(d –e)/(f + g – h)]
58. Solve the following:
I. ((A-(B+C) *D)/(E+F)) (FIND POSTFIX USING STACK)
II. 752+*415-/-(EVALUATE THE GIVEN POSTFIX EXPRESSION).
59. How do you find the complexity of an algorithm? What is the relation between the time
complexity and space complexity of an algorithm? Justify answer with an example.
60. What is meant by doubly linked list? Write the function to perform the following operation
in a doubly linked list.
I. Creation of list of nodes.
II. Insertion after a specific node.
III. Display from the beginning to end.
61. Give a 2 D array A[-100:100, -5:50]. Find the address of element A[99,49] considering the
base address 10 and each element required 4 bytes for storage. Follow row major order and
column major order..
62. Explain Tail recursion with a suitable example. Construct a recursion tree of the Tower of
Hanoi n=5.
63. Construct the Binary tree from the following two traversal results. In-order: Q, B, K,
C,F,A,G,P,E,D,H,R Pre-order: G,B,Q,A,C,K,F,P,D,E,R, H Find the post-order traversal sequence
of the tree.
64. Draw the expression tree for the given algebraic expression.
A + (B * C - ( D / (E ^ F) ) * G ) * H
Find the pre-order traversal sequence of the tree.
65. Define priority queue. Give one application of priority queue.
66. Define a sparse matrix. Suggest a space efficient representation for sparse matrices.
67. Differentiate between underflow and overflow condition in a linked list.
68. Convert the given expression into its corresponding postfix expression:
A+(B*C-(D/E↑F)*G)*H
69. Consider an array A[1…10][1...15] whose base address is 100 and W= 4. Find out
the address of A[8][6] using row major and column major order.
70. Define sparse matrix with example. Write a C program to represent sparse matrix in
3-tuple form.
71. Evaluate the following expressions:
623+-382/+*2^3+
72. Define Recursion. Write a recursive and tail-recursive function to calculate the
factorial of a given number.
73. Write an algorithm for conversion of infix to postfix expression using tack. Convert
the following infix expression into postfix expression sing stack.
A*(B+C)/D–E*(F+G/H)
74.