Data Structures and Applications Question Paper - Dec 18 - Computer Science (Semester 3) - Visvesvaraya Technological University (VTU)

0views

written 6.9 years ago by

teamques10 ★ 70k

Data Structures and Applications - Dec 18

Computer Science (Semester 3)

Total marks: 80
Total time: 3 Hours INSTRUCTIONS
(1) Question 1 is compulsory.
(2) Attempt any three from the remaining questions.
(3) Draw neat diagrams wherever necessary.

1.a. Write a C program with an appropriate structure definition and variable declaration to read and display information about an employee, using nested structures. Consider the following fields like Ename, Eid, DOJ(Date, Month, Year) and Salary (Basic, DA, HRA).

(6 marks) 00

1.b. Consider 2 polynomials A(x) =2x^1000 + 1 and B(x)=x⁴ + 10x³ + 3x² +1, show how these polynomials are stored in the 1-D array also give its C representation.

(4 marks) 00

1.c. Write a C function to add 2 polynomials A and B store the result in polynomial C

(6 marks) 00

2.a. Consider the pattern ababab, construct the table and the corresponding labeled directed graph used in the second pattern matching algorithm

(6 marks) 00

1.b. Write transpose algorithm to transpose the given sparse matrix, express the given sparse matrix as triplets and find its transpose

Pic

(10 marks) 00

Module -2

3.a. Implement push and pop function for stack with stack full (using dynamic arrays) amd stack empty conditions

(6 marks) 00

3.b Define recursion, write a function for tower of hanoii.

(6 marks) 00

3.c. Write a note on Dequeses and Priority queues.

(6 marks) 00

4.a. write a C function to insert and delete an item into a circular queue. Explain how it is advantageous over linear queue

(6 marks) 00

4.b. Convert the following infix expression to postfix form , (i) a+(b+c) + (b/d)a+zu ii) A-B/C(C*DSE)

(4 marks) 00

4.c. Write a C function to evaluate the postfix expression and trace the given postfix expression using stack 623 + -382/*253 +

(6 marks) 00

Module -3

5.a. Write C function to perform the following

(i) To insert a node at front end of the single linked list.

(ii) To delete a node at rear end of S.L.L.

(iii) To create an ordered S.L.L

(iv) To concatenate 2 S.L.L.

(12 marks) 00

5.b. What are the advantages of double linked list over single linked list? Explain with an example

(4 marks) 00

6.a. Write a C function to perform the following operations on double linked list:

(i) Inserting a node at the beginning.

(ii) Deleting a node at the rear end

(iii) Inserting an item at a specified position.

(9 marks) 00

6.b. Write a C function to add 2 polynomials represented as circular list with header modes.

(7 marks) 00

Module-4

7.a. Define tree, for the tree given below define the following terminologies:

(i) Degree

(ii) Non Terminals and terminals nodes.

(iii) Siblings

(iv) Ancestors

(v) Level

(vi) Height or depth

Pic

(5 marks) 00

7.b. Explain Binary tree using Array representation and linked representation, which representation is more suitable and why?

(6 marks) 00

7.c. write a note on threaded binary trees and write the rules to construct the threads

(5 marks) 00

8.a. Define binary search tree, write a function for recursive or iterative search BST.

(6 marks) 00

8.b. For the given data draw a binary search tree 1, 3, 8, 5, 7, 9, 10, 12, 15, 14, 13, 11,6

(4 marks) 00

8.c For a tree given below traverse the tree using inorder, preorder, postorder, traversals, write the C routines for any traversal.

Pic

(6 marks) 00

Module -5

9.a. Define Graph, for the given graph G show adjacency matrix and adjacency list representation of the graph.

Pic Pic

(8 marks) 00

9.b. What are the methods used for traversing a graph, explain any one with example and write the function for the same.

(8 marks) 00

10.a. Sort the following list of numbers using Radi x sort: 45, 37, 05, 09, 06, 11, 18, 27

(4 marks) 00

10.b. What are the types of file organisation? Explain any two

(8 marks) 00

10.c. Explain binary files, how are they different from text files

(4 marks) 00

ADD COMMENT EDIT