## Time: 3 Hours                                                                                                     Max. Marks: 100

NOTE: There are 11 Questions in all.

·      Question 1 is compulsory and carries 16 marks.

·      Answer any THREE Questions each from Part I and Part II. Each of these questions carries 14 marks.

·      Any required data not explicitly given, may be suitably assumed and stated.

Q.1       Give short answers:                                                                                                    (2x8)

a.       How does an array differ from an ordinary variable?

b.      What values are automatically assigned to those array elements which are not explicitly initialised?

c.   A stack is to be implemented using an array. The associated declarations are:

int stack [100];

int top = 0;

Give the statement to perform push operation.

d.   Assume that a queue is available for pushing and popping elements. Given an input sequence a, b, c, (c be the first element), give the output sequence of elements if the rightmost element given above is the first to be popped from the queue.

e.   A two dimensional  array TABLE [6] [8] is stored in row major order with base address 351. What is the address of TABLE [3] [4]?

f.    Which sorting algorithm is best if the list is already sorted? Why?

g.   What is the time complexity of Merge sort and Heap sort algorithms?

h.       What is the maximum possible number of nodes in a binary tree at level 6?

# PART I

Answer any THREE Questions. Each question carries 14 marks.

Q.2     a.   List various problem solving techniques.                                                              (5)

b.      What do you understand by structured programming? Explain.                            (5)

c.   Explain the concept of primitive data structures.                                                  (4)

Q.3     a.   Determine the frequency counts for all statements in the following program segment.

for (i=1; i ≤ n; i ++)

for (j = 1; j ≤ i;  j++)

for (k =1; k ≤ j; k++)

y ++;                                                                                                            (3)

b.   Write an algorithm to count number of nodes in the circular linked list.                 (3)

c.   Write an algorithm to insert a node in between any two nodes in a linked list.                      (4)

d.   Write down any four application of a stack.                                                        (4)

Q.4     a.   Give the algorithm to construct a binary tree where the yields of preorder and postorder traversal are given.                                                                                                                         (6)

b.   Construct the binary tree for the following sequence of nodes in preorder and inorder respectively.

Preorder :  G, B, Q, A, C, K, F, P, D, E, R, H

Inorder:   Q, B, K, C, F, A, G, P,  E,  D, H, R                                                   (4)

c.   Convert the following infix expression into a postfix expression (Show steps)                                                                                                                          (4)

Q.5     a.   Write an algorithm to delete a particular node from binary search tree. Trace your algorithm to delete a node (10) from the given tree.

(7)

b.   Draw a picture of the directed graph specified below:

G = ( V, E)

V(G) = {1, 2, 3, 4, 5, 6}

E(G) = {(1,2), (2, 3), (3, 4), (5,1), (5, 6), (2, 6), (1, 6), (4, 6), (2, 4)}

Obtain the following for the above graph:

(ii)                React ability matrix.                                                                                (7)

Q.6     a.   Write an algorithm for binary search. What are the conditions under which sequential search  of a list is preferred over binary search?               (7)

b.   Write an algorithm for selection sort. Describe the behaviours of selection sort when the input is already sorted.                                                                                                              (7)

# PART II

Answer any THREE Questions. Each question carries 14 marks.

Q.7           Define any Four the following terms:

(i)                  Abstract data type.

(ii)                Column major ordering for arrays.

(iv)              Game trees.

(v)                Hash function.                                                                                      (14)

Q.8     a.   Describe various memory allocation strategies.                                                    (8)

b.   How memory  is freed using Boundary tag method in the context of Dynamic memory management?                                                                      (6)

Q.9     a.   Define a method for keeping two stacks within a single linear array S in such a way that neither stack overflows until entire array is used and an entire stack is never shifted to a different location within the array. Write routines for pushing and poping elements in two stacks.                             (8)

b.  Suppose a queue is housed in an array in circular fashion. It is desired to add new items to the queue. Write down a procedure ENQ to achieve this also checking whether the queue is full. Write another procedure DQ to delete an element after checking queue empty status.                                       (6)

Q.10           a. What is a height balanced tree? Explain how the height is balanced after addition/deletion of nodes in it?                                                            (7)

b.   Show the linked representation of the following two polynomials.

Build a procedure for adding two polynomials stored in linked lists. Verify

steps of your procedure for the above two polynomials.                                     (7)

Q.11                Write short notes on the following:

(i)                  Threaded binary trees.

(ii)                Graph traversal.

(iii)               Conversion of forest into tree.

(iv)              Doubly linked list.                                                                 ()

## Time: 3 Hours                                                                                                     Max. Marks: 100

NOTE: There are 11 Questions in all.

·      Question 1 is compulsory and carries 16 marks. Answer to Q. 1. must be written in the space provided for it in the answer book supplied and nowhere else.

·      Answer any THREE Questions each from Part I and Part II. Each of these questions carries 14 marks.

·      Any required data not explicitly given, may be suitably assumed and stated.

Q.1       Choose the correct or best alternative in the following:                                           (2x8)

c.       A queue is a,

(A)  FIFO (First In First Out) list.        (B)  LIFO (Last In First Out) list.

(C)  Ordered array.                             (D)  Linear tree.

c.       Which data structure is needed to convert infix notation to postfix notation?

(A)  Branch                                         (B)  Queue

(C)  Tree                                             (D)  Stack

c.   Which of the following operations is performed more efficiently by doubly linked list than by singly linked list?

(A)     Deleting a node whose location in given

(B)     Searching of an unsorted list for a given item

(C)     Inverting a node after the node with given location

(D)    Traversing a list to process each node

d.   The extra key inserted at the end of the array is called a,

(A)  End key.                                      (B)  Stop key.

(C)    Sentinel.                                       (D)  Transposition.

e.   The prefix form of A-B/ (C * D ^ E) is,

(A)     -/*^ACBDE                                (B)  -ABCD*^DE

(C)  -A/B*C^DE                                (D)  -A/BC*^DE

f.    Consider that n elements are to be sorted. What is the worst case time complexity of Bubble sort?

(A)     O(I)                                             (B)  O(log2n)

(C)  O(n)                                             (D)  O(n2)

g.   A characteristic of the data that binary search uses but the linear search ignores is the ___________.

(A)    Order of the elements of the list.

(B)    Length of the list.

(C)    Maximum value in list.

(D)    Type of elements of the list.

h.   In Breadth First Search of Graph, which of the following data structure is used?

(A)  Stack.                                          (B)  Queue.

(C)  Linked List.                                  (D) None of the above.

# PART I

Answer any THREE Questions. Each question carries 14 marks.

Q.2     a.   Differentiate between system defined data types and Abstract data types with suitable examples.                                                                (8)

d.      Explain the following:

(i)                  Complexity of an Algorithm.

(ii)                The space-time trade off algorithm.                                    (6)

Q.3     a.   Define a sparse matrix. Explain different types of sparse matrices? Show how a triangular array is stored in memory. Evaluate the method to calculate address of any element ajk of a matrix stored in memory. (10)

b.   A linear array A is given with lower bound as 1. If address of A[25] is  375 and A[30] is 390, then find address of A[16].                                (4)

Q.4     a.   Let a binary tree ‘T’ be in memory. Write a procedure to delete all terminal nodes of the tree.                                                                    (8)

b.   Consider the following eight numbers 50, 33, 44, 22, 77, 35, 60 and 40. Display the construction of the binary by inserting the above numbers in the given order.                                                    (6)

Q.5     a.   Can a Queue be represented by circular linked list with only one pointer pointing to the tail of the queue? Substantiate your answer using an example.                                                                        (5)

b.   Establish the usage of linked lists for polynomial manipulation.                             (5)

c.   Convert the following infix expressions  to postfix notation

(i)                  A+((B+C)*(D+E)+F/G)

(ii)                                                                                          (4)

Q.6     a.   Explain Hash Tables, Hash function and Hashing Techniques?                             (8)

b.   Explain the concepts of first fit and best-fit algorithms for memory allocation with suitable examples.                                                                       (6)

# PART II

Answer any THREE Questions. Each question carries 14 marks.

Q.7           Define a linked-list? How are these stored in the memory? Suppose the linked list in the memory consisting of numerical values. Write a procedure for each of the following:

(i)   To find the maximum MAX of the values in the list.

(ii)  To find the average MEAN of the values in the list.

(iii) To find the product PROD of the values in the list.                                      (14)

Q.8     a.   Using array to implement the queue structure, write an algorithm/program to

(i) insert  an element in the queue.

(ii) delete an element from the queue.    (9)

b.   Define a stack. Describe ways to implement stack.                                             (5)

Q.9     a.   Sort the following list using Heap Sort technique, displaying each step.

20, 12, 25 6, 10, 15, 13                                                                                    (7)

b.  Give the binary search algorithm.                                                                        (7)

Q.10           a. The following lists represent preorder and postorder sequences of nodes of a binary tree.

Preorder: G, B, Q, A, C, K, F, P,D, E, R, H

Inorder :  Q, B, K, C, F, A, G,  P, E, D, H, R

Draw the tree T and give the yield of the postorder traversal of the tree.              (8)

### b.   Give the adjacency matrix and adjacency list of the following graphs.

(6)

Q.11           a.                                                       Consider the algebraic expression

E = (5x+z) (3a-b)2

(i)                  Draw the expression tree corresponding to E

# DEC./2003

## Time: 3 Hours                                                                                                     Max. Marks: 100

NOTE: There are 11 Questions in all.

·      Question 1 is compulsory and carries 16 marks. Answer to Q. 1. must be written in the space provided for it in the answer book supplied and nowhere else.

·      Answer any THREE Questions each from Part I and Part II. Each of these questions carries 14 marks.

·      Any required data not explicitly given, may be suitably assumed and stated.

Q.1       Choose the correct or best alternative in the following:                                           (2x8)

e.       The largest element of an array index is called its

(A)  lower bound.                                (B)  range.

(C)  upper bound.                                (D)  All of these.

d.      What is the result of the following operation

Top (Push (S, X))

(A)  X                                                 (B)  null

(C)  S                                                  (D)  None of these.

c.   How many nodes in a tree have no ancestors.

(E)     0                                                  (B)  1

(C)  2                                                  (D)  n

d.   In order to get the contents of a Binary search tree in ascending order, one has to traverse it in

(A)  pre-order.                                    (B)  in-order.

(D)    post order.                                   (D)  not possible.

e.   Which of the following sorting algorithm is stable

(A)  insertion sort.                                (B)  bubble sort.

(C)  quick sort.                                    (D)  heap sort.

f.    The prefix form of an infix expression  is

(A)  .                                  (B)  .

(C)  .                                  (D)  .

g.   Which data structure is used for implementing recursion?

(A)  queue.                                          (B)  stack.

(C)  arrays.                                          (D)  list.

h.   In binary search, average number of comparison required for searching an element in a list if n numbers is

(A)  .                                        (B)  .

(C)  n.                                                 (D)  n – 1.

# PART I

Answer any THREE Questions. Each question carries 14 marks.

Q.2     a.   Define an array. How does an array differ from an ordinary variable?  How are arrays represented in the memory?                                             (5)

f.        Consider an array A[20, 10].  Assume 4 words per memory cell and the base address of array A is 100.  Find the address of A[11, 5] assuming row major storage.                                                 (5)

c.   What are the characteristics of a good algorithm?                                                (4)

Q.3     a.   Write an algorithm to convert an infix expression into postfix expression.             (8)

b.   Suggest a way of implementing two stacks in one array such that as long as space is there in an array, you should be able to add an element in either stack.  Using proposed method, write algorithms for push and pop operations for both the stacks.                                                                          (6)

Q.4     a.   List various problem-solving techniques.                                                             (5)

b.   Write an algorithm to insert a node p at the end of a linked list.                            (5)

c.   Write down any four applications of queues.                                                       (4)

Q.5     a.   Write an algorithm to compute the value of postfix expression using stack.           (7)

b.   Draw a binary tree from its inorder and preorder traversal sequences given as follows:

Inorder   :    d b g e h a c n f

Preorder :    a b d e g h c f n                                                                               (7)

Q.6     a.   Write an algorithm that counts number of nodes in a linked list.                            (5)

b.   Write an algorithm to add an element at the end of circular linked list.                  (5)

c.   Delete a given node from a doubly linked list.                                                      (4)

# PART II

Answer any THREE Questions. Each question carries 14 marks.

Q.7     a.   Write an algorithm to sort a given list using Quick sort method.  Describe the behaviour of Quick sort when input is already sorted.                         (7)

b.   Describe various memory allocation strategies.                                                    (7)

Q.8     a.   Sort the following list using Heap Sort

66, 33, 40, 20, 50, 88, 60, 11, 77, 30, 45, 65.                                                  (7)

b.   Write a recursive function to count the number of nodes in a binary tree.              (7)

Q.9     a.   Define the following :

(i)                  AVL tree.

(iii)               Heap.

(iv)              Binary Search Tree.                                                                               (8)

b.   Write an algorithm for searching a key from a sorted list using binary search technique.                    (6)

Q.10           a.                                                        Define graph, adjacency matrix, adjacency list, hash function, sparse matrix, reachability matrix.                                                                                  (6)

### b.   Explain various graph traversal schemes and write their merits and demerits.                       (8)

Q.11                                                                     Write short notes on the following:

(i)                  Decision and game trees.

(ii)                Polynomial representation and manipulation using linked lists.

(iii)               Analysis of algorithm.

(iv)              Circular queues.                                                                   (3 ½ x 4 = 14)

## Time: 3 Hours                                                                                                     Max. Marks: 100

NOTE: There are 11 Questions in all.

·      Question 1 is compulsory and carries 16 marks. Answer to Q. 1. must be written in the space provided for it in the answer book supplied and nowhere else.

·      Answer any THREE Questions each from Part I and Part II. Each of these questions carries 14 marks.

·      Any required data not explicitly given, may be suitably assumed and stated.

Q.1       Choose the correct or best alternative in the following:                                           (2x8)

g.       In order to get the information stored in a Binary Search Tree in the descending order, one should traverse it in which of the following order?

(A)  left, root, right                               (B)  root, left, right

(C)  right, root, left                               (D)  right, left, root

e.       The equivalent prefix expression for the following infix expression  (A+B)-(C+D*E)/F*G is

(A)  -+AB*/+C*DEFG                       (B)  /-+AB*+C*DEFG

(C)  -/+AB*+CDE*FG                       (D)  -+AB*/+CDE*FG

c.   The number of nodes in a complete binary tree of depth d is

(A)                                        (B)

(C)                                        (D)

d.   Ackerman’s function is defined on the non-negative integers as follows

a (m,n)      = n+1 if m=0

= a (m-1, 1) if m0, n=0

= a (m-1, a(m, n-1)) if  m0, n0

The value of a (1, 3) is

(A)  4.                                                 (B)  5.

(E)     6.                                                 (D)  7.

e.   The result of evaluating the postfix expression 5, 4, 6, +, *, 4, 9, 3, /, +, * is

(B)     600.                                             (B)  350.

(C)  650.                                             (D)  588.

f.    The worst case of quick sort has order

(B)     O(n2)                                           (B)  O(n)

(C)  O(n log2 n)                                   (D)  O(log2 n)

g.   For an undirected graph G with n vertices and e edges, the sum of the degrees of each vertex is

(A)  ne                                                (B)  2n

(C)  2e                                                (D) en

h.   The time required to delete a node x from a doubly linked list having n nodes is

(A)  O (n)                                            (B)  O (log n)

(C)  O (1)                                           (D) O (n log n)

# PART I

Answer any THREE Questions. Each question carries 14 marks.

Q.2     a.   What is the smallest value of n such that an algorithm whose running time is 100n2 runs faster than an algorithm whose running time is 2n on the same machine.                                                     (4)

h.       Explain any three methods of representing polynomials using arrays. Write which method is most efficient for representing the following polynomials.

(i)                  8x100+10x+6

(ii)                8x3-7x2+5x+15

Write an algorithm to add two polynomials using any one of your representations.               (10)

Q.3     a.   Let X = (X1, X2, X3,….Xn) and Y= (Y1, Y2, Y3,….Xm) be two linked lists. Write an algorithm to merge the lists together to obtain the linked list Z such that Z =  (X1, Y1, X2, Y2,….Xm, Ym,Xm+1….Xn) if m<=n or      Z  = (X1, Y1,X2,Y2….Xn,Yn,Yn+1….Ym) if m>n.                      (7)

b.   Devise a representation for a list where insertions and deletions can be made at either end. Such a structure is called a Deque (Double ended queue). Write functions for inserting and deleting at either end.         (7)

Q.4     a.   Using stacks, write an algorithm to determine whether the infix expression has balanced parenthesis or not.                                                             (7)

b.   Implement a stack using linked list. Show both the  PUSH and POP operations.                 (7)

Q.5     a.   Write binary search algorithm and trace it to search element 91 in following list:

 13 30 62 73 81 88 91

What are the limitations of Binary Search?                                                           (7)

b.  What are the two phases in heap sort algorithm? Sort the following data

using heap sort and show all the intermediate steps.

88, 12, 91, 23, 10, 36, 45, 55, 15, 39, 81                                                          (7)

Q.6     a.   What is a Binary Search Tree (BST)? Make a BST for the following sequence of numbers.

45, 32, 90, 21, 78, 65, 87, 132, 90, 96, 41, 74, 92                                           (7)

b.   Traverse the Binary Search Tree created above in Preorder, Inorder and Postorder.                       (7)

# PART II

Answer any THREE Questions. Each question carries 14 marks.

Q.7     a.   What is a sparse matrix? How is it stored in the memory of a computer? Write a function to find the transpose of a sparse matrix using this representation.                                                         (8)

b.   What do you understand by row-major order and column-major order of arrays? Derive a formula for calculating the address of an array element in terms of the row number, column number and the base address of the array.                                                                                                       (6)

Q.8     a.   Write an algorithm for converting an infix expression into a postfix expression using stack. Illustrate the steps for the following expression. (((a+b)*c) / (d+e))                                                                 (7)

b.   Write an algorithm for finding solution to the Towers of Hanoi problem. Explain the working of your algorithm (with 4 disks) with diagrams. (7)

Q.9     a.   Suppose we have divided n elements in to m sorted lists. Explain how to produce a single sorted list of all n elements in time O (n log m )?              (7)

b.  Define hashing. Describe any two commonly used hash functions. Describe one method of collision resolution.                                            (7)

Q.10           a. A Binary tree has 9 nodes. The inorder and preorder traversals of the tree yields the following sequence of nodes:

 Inorder : E A C K F H D B G Preorder: F A E K C D H G B

Draw the tree. Explain your algorithm.  (7)

### input data:

69, 19, 43, 16, 25, 40, 132, 100, 145, 7, 15, 18                                               (7)

Q.11     a.    What is the difference between Prims algorithm and Kruskals algorithm for finding the minimum-spanning tree of a graph? Execute both Prim’s and Kruskal’s algorithms on the following graph.       (8)