1. 	(a) 	What do you mean by Sparse Matrix. Write a program to compute the transpose a sparse matrix.[6 marks] 

	(b) 	List the advantages and disadvantages of doubly link list over singly link list. What is a priority Queue? Write an algorithm for inserting an element into circular queue.[8 marks] 

	(c) 	Write an algorithm for insertion sort. Apply insertion sort algorithm for the following list of elements.

		17,36,95,25,54,72,68 		[7 marks] 

	(d) 	Define Postorder and Preorder traversal of tree. Given the following Postorder and Preorder traversals,construct the corresponding Binary tree.

		Post order: J H D E B I F G C A
		Pre order: D J H B E A F I C G		[8 Marks] 



2. 	(a) 	What is recursion? Write a recursive function to find factorial of a number.[4 Marks] 

	(b) 	Convert the following infix expression into postfix. Write an algorithm for the same.
		
		(i) ((A-(B+C)*D)/(E+F))
		(ii)(A^(B*C)-D)+(E/F)*(G+H) 



3. 	(a) 	What is B-tree? What are the properties of a B-tree of Order M. [5 marks] 

	(b) 	Write a program in C for implementing Breadth First Search (BFS). 


4. 	(a) 	What is a File? Write a 'C' program to copy the contents of one file to another file.

	(b) 	Define Binary Search Tree (BST. Write an algorithm to insert a node in a BST. [5 marks] 


5. 	Write short notes on the folowing: [10 marks]

	(a) Stack
	(b) Circular Link List
	(c) Complete Binary Tree
	(d) Storage Pool
	(e) Pointers



6. 	(a) 	Define an AVL tree. Construct a height balanced tree for the following list of elements: 4, 6, 12, 8, 4, 2, 15, 7, 3 [8 marks] 

	(b) 	Write an algorithm to emplement linked list using pointers and perform the following tasks: [10 marks] 

		1.	Delete a node in the list, given a pointer to that node. 
		2.	Write a function to reverse the linked list.
	
	(c) 	Write an algorithm that reads m*n matrix "A" and p*q matrix "B", checks whether these matrices are multipliable in either order or not. (e.g wheter A*B or B*A is defined). Further, if A*B or B*A is defined then calculate the product. Note : Show proper error handling also. [7 marks] 

	(d) 	Calculate the time complexity of the following code by using Big 'O' notation : [5 marks] 
		
		1.	scanf("%d",&n);
		2.	scanf("%d",&m);
		3.	for(i=0;i<=m+n;i+=2)
		4.	printf("%d\n",i-1);
		5.	for(j=m*n/100;j<=m*n;++j)
		6.	printf("%d\n",j);


7. 	(a) 	Write an algorithm that accepts 12 words of different string-size. Arrange the words in descending order based on the sum of ASCII values of the characters in the string. e.g : if string is "ABFD", its ASCII mapping is 65,66,70,68 respectively and sum is 65+66+70+68=269

		Hint : ASCII value of 'A' starts with 65, and 'a' starts with 97 		[6 marks] 


	(b) 	Write an algorithm to implement bubble sort technique. Also, show the steps of bubble sort on the following given number : "5, 12, 38, 7, 3, 18, 68, 115" [4 marks]. 


8. 	(a) 	Construct the binary tree using the following preorder and inorder sequences : 
		
		Pre order : A B C E I F J D G H K L
		Post order : E I C F J B G D K H L A

		Also, write the postorder sequence of it. [5 marks] 


	(b) 	Write algorithms to perform the following operations in circular queue : [5 marks] 
		
		1.	Create a circular queue
		2.	Check whether a queue is empty


9.	Insert an element in a queue

10. 	(a) 	Consider the following graph:
 
		Make the adjacecy matrix for the given graph. Also, write an algorithm to compute the transpose of the matrix. [5 marks] 

	(b) 	What is sparse matrix ? Which method is used to represent its non-zero elements ? Also, write the algorithm corrseponding to this method, explaining its steps. [5 marks] 



11. 	Explain the followingwith an example of each : [10 marks]

	1.	Direct file organisation
	2.	Depth first search
	3.	B-tree
	4.	Column major order



12. 	(a) 	Ackermann's function A(m,n) is defined as follows: [10 marks]

A(m,n)={n+1 ,if m=0
{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.[10 marks] 

	(c) 	Write a non recursive procedure for traversing a Binary tree in "Postorder". [10 marks] 



13. 	(a) 	Draw the internal memory representation of the following Binary Tree using sequential representation.[5 marks]

 	(b) 	Devise a scheme using a stack to convert an infix expression to postfix expression.[5 marks]

 
14. 	(a) 	Write the postfix form of the following expressions [5 marks]
		(i) a+b*(c/d)
		(ii)(a+b*c)/d 

	(b) 	Write a programme for multiplication of two matrices.[5 marks] 


15. 	(a) 	Devise an algorithm to count the number of connected componenets in the directed graph. [5 marks] 

	(b) 	Write Prim's Algorithm. [5 marks] 


16. 	(a) 	Consider the following graph:
 
		Find the minimum cost spanning tree for the above graph using Kruskal's Algorithm.[5 marks] 
	
	(b) 	Write Kruskal's Algorithm.[5 marks] 
		

17. 	(a) 	Write an Algorithm to implement Heap Sort.[6 marks] 

	(b) 	The input sequence to a Heap sort Algorithm which sorts in increasing order is:
		
		5,3,9,2,14,8
	show the sorting process stepwise. 


18. 	(a) 	Write an Algorithm to add two polynomials. Use the array implementation.If the polynomails 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 Post fix Expression..[10 marks] 

	(c) 	Write a function that takes a pointer to the root of a Binary Tree T an dcomputes the number of full nodes in T. What is the running time of your function? [10 marks] 


19. 	(a) 	Draw the internal memory representation of the following Binary Tree using sequential representation.[5 marks]
 
	(b) 	What is the minimum number of external nodes for a Binary Tree with hieght 'h'? Justify your answer.[5 marks] 


20. 	(a) 	Write the postfix form of the following expressions [5 marks]
		
		(i) a+b-c*d
		(ii)(a-b)*(c+d) 

	(b) 	Write an Algorithm for the multiplication of two sparse matrices (Use proper representation for the sparse matrices ).[5 marks] 



21. 	(a) 	Draw the transitive closure of the directed graph shown in the following figure: [5 marks]
 
	(b) 	Write Dijkstra's Algorithm. [5 marks] 


22. 	(a) 	Consider the following graph:
 
 	Find the minimum cost spanning tree for the above graph using Prim's Algorithm.[5 marks] 
	
	(b) 	Is the minimumn cost spanning tree found by using Prim's Algorithm unique? Justify your answer.[5 marks] 


23. 	(a) 	Write an Algorithm to implement Bubble Sort technique of sorting.[5 marks] 

	(b) 	The input sequence to a Bubble sort Algorithm which sorts in increasing order is:
		
		35,5,38,7,41,39,37.

	show the sortin process stepwise. 



24. 	(a) 	Show how the array, [10 marks]

A=[ 3 4 9 2]
  [ 0 1 6 8]
  [ 7 8 4 5]
  [ 9 9 2 3]

would appear in memory when stored in
  (i) Row Major order
  (ii) Column Major order
  (iii)Logical representation 


	(b) 	What is Binary search Tree (BST)? Write Algorithms for inserting and deleting nodes in BST. Explain them with the help of an example each.[10 marks] 


	(c) 	Assume A is a N*N square matrix. Write the Algorithm for the following operations in the matrix A. [10 marks]
	
		(i) Find the product of the diagonal elements of A.
		(ii) Find the sum of the elements above the diagonal elements. 


25. 	(a) 	Construct a Height Balanced Tree for the following list of elements:

	2,6,13,8,4,3,18,7,1,8,11 
	
	(b) 	Write an Algorithm to convert an infix expression to a post fix expression. Also, Explain the logic with the help of an example.(Use stack implementation)[5 marks] 


26. 	(a) 	Write and explain the Hash function method, "Division-Remainder Hashing".Also explain where this can be used. 

	(b) 	For the digraph shown below find[5 marks]

		(i) the indegree and outdegree of each vertex.
		(ii) its adjacency matrix representation.
		(iii)its adjacency list representation.
		(iv) its strongly connected component.
 

27. 	(a) 	Write an algorithm to construct a doubly linked list and search for a data. 

	(b) 	Write an algorithm for addition and deletion of an element into a queue. [5 marks] 


28. 	(a) 	Define the following and given an example for each:[5 marks]
		(i) UNION in C language
		(ii) Circular Linked list
		(iii)Post order traversal of a binary tree
		(iv) Insertion sort
		(v) K- Wauy merging. 


	(b) 	Is the minimumn cost spanning tree found by using Prim's Algorithm unique? Justify your answer.[5 marks] 


29. 	(a) 	Write an Algorithm to implement Bubble Sort technique of sorting.[5 marks] 

	(b) 	The input sequence to a Bubble sort Algorithm which sorts in increasing order is:

		35,5,38,7,41,39,37.

	show the sorting process stepwise. 



30. 	(a) 	Using Quick sort method, sort the following sequence in descending order: 07, 62, 54, 03, 94, 01, 100. [10 marks] 

	(b) 	Define stack ? Implement PUSH and POP operations using pointers in 'C'. [10 marks] 

	(c) 	Write a program in 'C' to implement the following Binary Tree Traversals. 

		1.	Inorder Traversal
		2.	Preorder Traversal
		3.	Postorder Traversal
	
			use recursion. [10 marks] 


31. 	(a) 	Discuss the following file organization methods w.r.t. the structure, operations like insertion of records, deletion of records, updation of records and retrieval: 
		
		1.	Sequential Files
		2.	Indexed Files

			Give the applications of above two file organization techniques. [5 marks] 


	(b) 	Write a program in 'C' to count: 
		1.	Number of words in a given string
		2.	Numbe of vowels in a given string		[5 marks] 


32. 	(a) 	Write a program in 'C' to insert an element into singly linked list at: 
		1.	Begining of list
		2.	Middle of list
		3.	End of list			[6 marks] 


	(b) 	Explain the following parameter passing mechanisms to functions: 

		1.	Call-by-value
		2.	Call-by-reference		[4 marks] 



33. 	(a) 	Compare the performance of the following sorting techniques: 
		1.	Bubble Sort
		2.	Merge Sort			[4 marks] 


	(b) 	Write a program in 'C' to implement staic and dynamic allocation for a STUDENT structure with following fields: 

		•	char name[10],
		•	int marks,
		•	long int mobile_no.		[4 marks] 


(c) 	Compare structure and union. [2 marks] 


34. 	(a) 	Write a short notes on the following: 
		
		1.	AVL-Tree
		2.	Breadth First Search(BFS)
		3.	Circular Queue
		4.	Doubly Linked List
		5.	Binary Search Trees
			
			[5*2=10 marks] 


		
35. 	(a) 	What is sparse matrix ? Discuss methods of representation of sparse matrix in memory. Explain row-major and column-major order with example. [9 marks] 

	(b) 	What is binary search tree ? Write an algorithm to find an element in a binary search tree. [5 marks] 

	(c) 	Define a circular queue. What is the condition that a circular queue is full (if queue is implemented using array) ? Write an algorithm for inserting a node at given location in a circular queue. [8 marks] 

	(d) 	Differentiate between internal and external sorting. Which sorting algorithm is preferred for external sorting ? Write an algorithm for K-way merge sort. [8 marks] 



36. 	(a) 	Write a program in C for binary search tree. [5 marks] 

	(b) 	Apply Binary search for elements in array P to find the element 40, 11, 22, 30, 33, 40, 44, 55, 60, 66, 77, 80, 88, 99. [3 marks] 

	(c) 	What are the various disadvantages of sequential file organization ? [2 marks] 


37. 	(a) 	Convert the following postfix expression into infix using stack: A B C * D E F ^ / G * - H * + [3 marks] 

	(b) 	What is AVL tree ? Construct an AVL search tree by inserting the following elements in order of their occurrence. (Show each of the rotations). 64, 1, 44, 26, 13, 110, 98, 85. [7 marks] 


38.	Write short notes on the following:

	(i) Directed Graph
	(ii) Compaction
	(iii) Complete Binary tree
	(iv) Hash function
	(v) Height balanced tree
		
		[5*2=10 marks] 


39. 	(a) 	Write a program in C for bubble sort. [5 marks] 

	(b) 	Explain indexed-sequential file organization. Under what conditions is it advantageous to have file organized as indexed-sequential rather than direct file ? [5 marks] 

Leave a Reply

Subscribe to Posts | Subscribe to Comments

Follow by Email

All Notes on BCA

All Notes  on BCA
BCA all subjects notes

Total Pageviews

Google+ Followers

Translate

Powered by Blogger.

- Copyright © All Notes on BCA - Metrominimalist - Powered by Blogger - Designed by Johanes Djogan -