Question Paper of CS-62 C Programming And Data Structure Dec- 2004

Q.l(a) Represent a polynomial using a circularly inked list. Write an algorithm to subtract two polynomials using the representation above. What is the time complexity of your algorithm to subtract two polynomials using the representation above. What is the time complexity of your algorithm ?

(b) A file stores a series of numbers. Write an algorithm using binary search tree that counts the occurrence of different numbers in the file. For example, file containing data 1, 50, 20, 1, 25 would produce output as
Number Occurrence
1 2
20 1
25 1
50 1

© Write an algorithm to sort a sequence of number of numbers in increasing order using bubble sort. What is the time complexity of this algorithm ?

(d) What are the various applications of stacks and queues ? Give at least two applications of each.

Question Paper of CS - 62 C Programming And Data Structure June- 2004

Q.l(a) What is the Time and Space complexity of an algorithm? For the binary search algorithm, derive the best, average and worst case time complexities for its execution.

(b) What are Row major and Column major representations of arrays? For a character array defined as AJ2O] [20], if A|0] |0| is located at memory address 100, where is element A[10J [1] located in Column major representation and in Row major representation.

© Write an algorithm that takes a pointer to the root of a binary tree T and another variable which indicates whether preorder, postorder or inorder traversal of the tree is required. Depending on this variable, the function should print the tree in either preorder, poster or inorder.

Question Paper of CS- 62 C Programming And Data Structure Dec - 2003

Q.l(a) Write an algorithm to add two polynomials. Use the array implementation. If the polynomials have M and N terms respectively, what is the time complexity of your algorithm?

(b) Write an algorithm to convert an Infix Expression which includes the operators (,), +, -, * and / to Postfix Expression.

© Write a function that takes a pointer to the root of a binary tree T and computes the number of full nodes in T. What is the running time of your function?

Question Paper of CS-62 C Programming And Data Structure June-2003

Q.l(a) Write a function to multiply two polynomials, using a linked list implementation. You must make sure that the output polynomial is sorted by exponent and has almost one term corresponding to any power. Assume appropriate representation for input polynomials.

(b) Given two Sorted Lists, L, and L2, write an algorithm to compute Lj u L2. Lj and L2 are to be implemented as Arrays.

© Write a function that takes only a pointer to the root of a binary tree T and computes the number of nodes in T.

Q.2(a) Draw the Internal memory representation of the following Binary Tree using Sequential Representation. Assume that nodes appear in the following physical sequence:
A, B, C, D, E, F, G, H
Image No. 1

(b) Consider the tree in the following figure:

© List atleast 4 differences between Arrays and Pointers in *C Ianguage.

Q.3(a) Write the Postfix form of the following expression:
(i) (C x D) + (a - b)
(ii) C x D + a - b

(b) Write an algorithm for the addition of two matrices. The second matrix will be a sparse matrix. The first matrix is not a sparse matrix.

© What is an AVL Tree? How does it differ from a Binary Tree?

Q.4(a) Write an algorithm to solve the Single-Source Shortest-Path problem.

(b) Does either Prim’s or Kruskal’s algorithm work if there are negative edge weights? Justify your answer.

Q.5(a) Consider the following figure:

Find the Minimum Cost Spanning Tree for the above graph using Prim’s Algorithm.

(b) Write Prim’s Algorithm.

Q.6(a) Write a recursive algorithm to implement Quick Sort.

(b) The input sequence to a Quick Sort’ algorithm which sorts in increasing order is
75, 73, 65, 82, 55, 90
Show the Sorting Process step-wise.

Question Paper of CS-62 C Programming And Data Structure Dec-2002

Q.l(a) Ackermann’s function A (m, n) is defined as follows:

n + 1 ,ifm = 0
A (m,n)= A (m-1, 1) ,ifn = 0
A (m-1, A (m,n-1)) , otherwise.

Write a recursive algorithm for computing this function.

(b) Let *P* be a pointer to a doubly linked list. Show how this list may be used as a queue by writing algorithms to add and delete elements. Specify the value for ‘P’ when the queue is empty.

© Write a non-recursive procedure for traversing a Binary Tree in “Postorder".

Q.2(a) Draw the internal memory representation of the following Binary Tree using sequential representation:

(b) Devise a scheme using a stack to convert an infix expression to a postfix expression.

Q.3(a) Write the postfix form of the following expressions:
(i) a + b x (C -j- d)

(b) Write an algorithm for multiplication of two matrices.

Q.4(a) Devise an algorithm to count the number of connected components in a directed graph.

(b) Write Prim’s Algorithm.

Q.5(a) Consider the following graph;

(b) Write Kruskal’s Algorithm.

Question Paper of CS-62 C Programming And Data Structure June-2002

Q.l(a) If A = (3j, a2,……, an) and B = (bp b2,…., bm) are ordered lists and are represented by Arrays, then write an algorithm for the concatenation of the above ordered lists.

(b) Write an algorithm to transform an infix expression to a postfix expression.

© Write an algorithm to count the number of leaves in a tree.

Q.2(a) Draw the internal memory representation of the following Binary Tree using Sequential Representation.

(b) Write an algorithm to evaluate a prefix arithmetic expression.

Q.3(a) Write the postfix form of the following expressions :

(i)(c*d)x(a + b)
(ii) a + b x c -5- d

(b) Write an algorithm for the addition of two sparse matrices (use proper representation for sparse matrices).

Q.4(a) What is the relationship between the sum of the degrees of the vertices of a graph and the number of edges in the graph?

(b) Write Kruskal’s algorithm.

Q.5(a) Consider the following graph :

Find the minimum cost spanning tree for the above graph using Prim’s algorithm.

(b) Prove that if the edge weights on an undirected graph are distinct, there is only one minimum-cost spanning tree.

Q.6(a) Write an algorithm to implement Quick Sort.

(b) The input sequence to a Bubble Sort algorithm which sorts in increasing order is : 6, 5, 39, 32, 11, 41
Show the sorting process stepwise.

Question Paper of CS-62 C Programming And Data Structure Dec-2001

Q.I (a) A general polynomial A(x) can be written as
ax’ + a .x"-1 +…..+ a,x + a.
where an*0 and we say that the degree of A is ‘n Each ax1 is a term of the polynomial. If a. - 0, then it is a zero term, otherwise, it is a nonzero term. Now, write an algorithm which evaluates a polynomial at a value ‘x0′

(b) Let (P’ be a pointer to a circularly linked list Show how this list may be used as a queue by writing algorithms to add and delete elements. Specify the value for *P’ when the queue is empty.

© Write a non-recursive procedure for traversing a Binary Tree in “Preorder".

Question Paper of CS-62 C Programming And Data Structure June - 2001

Q.l(a) Write a program EXPR in C language which evaluates a Reverse Polish expression from the command line, where each operator or operand is a separate argument. For example,

EXPR 2 3 4 + *
evaluates 2 x (3 + 4).
For example:

(b) Give the node structure for implementing a linked list containing two information fields viz. info 1, info 2. Let p be the pointer to the first node of the linked list. Traverse the linked list to go to the node containing the information info 1 = u and>Hen print the info 1 and info 2 fields.

© Define binary search tree. Write a function in *C* to create a binary search tree.

Question Paper of CS-62 C Programming And Data Structure Jan 2001

Q.l(i) What are the advantages and disadvantages of C-pointer? What types of operations can be implemented on pointers? Explain through examples.

(ii) Let List 1 = (x,, x2,…, xn) and List 2 = (y,, y2,…, yo) be two linked lists. Write an algorithm to merge the two lists to obtain the linked list,

List 3 = (x1, y1, x2, y2…. xmiya…..,xn) if m < n,

and List 3 = (x1,y1,y2,.xnxn+1,…..x2 if m > n.

graph

Obtain :
(a) In-degree and out-degree of each vertex
(b) Its adjacency matrix
© Its adjacency list representation

(iv) Write a C-program to implement quicksort recursively. Show the status of the file at each recursive call of quicksort The input file has 8 records with keys (15, 5, 25, 2, 40, 7, 50, 12).

(v)(a) Show the stack evaluation of postfix notation :

(b) List all data structures for representing tree.

Question Paper of CS-06 Data Base Management System June-2004

Q.1. (a). What are the advantages of DBMS over a traditional file system?

(b) What is ISAM? How are records stored in ISAM? Show this with diagrams.

© Define BCNF. How does it differ from 3NF? Explain them through an example.

(d) What is a knowledge-base system? Differentiate between a knowledge base system and a database system.