# VTU Previous Question Papers BE-CS 3rd Semester

# Data Structures with C **May/June 2010**

**Important Note : 1. On completing your answers, compulsorily draw diagonal cross lines on the remaining blank pages.**

**2. Any revealing of identification, appeal to evaluator and /or equations written eg, 42+8 = 50, will be treated as malpractice.**

**Note: Answer any FIVE full questions, selecting at least TWO questions from each part**

**PART-A**

1. (a)What is a pointer? What are the uses of pointers in G?

(b)Explain what is meant by lvalue and rvalue, with examples.

(c)Write a C program to read ten integers and store them in an array using pointers. Print their sum and average.

2.(a)What is a string? How is a string declared and initialized?

(b)Write appropriate structure definition and variable declarations to store following information about 100 students:

Name, USN, Gender, Date of birth and marks in three subjects Si, S2 & S3. Date of birth should be a structure containing fields day, month and year

(c)Write a function that given a binary file, copies the odd items (item 1,3,5, 11) to a second binary file and the even items(item, 2,4,6,8,….n+1) to a third binary file.

3.(a) Define stack. Briefly explain the primitive operations on the stack.

(b).Show using the tabular columns, how the expression (A+B)*C is converted into a postfix expression according to the infix to postfix conversion algorithm.

(c) Write the algorithm to evaluate a valid postfix expression and hence evaluate the postfix expression :

6 2 3 + – 3 8 2 / + ×

All the operands are single digit positive integers and operators are binary in nature.

4 (a). Determine what the following recursive C function computes:

int func(int n) { if (n = = 0) retum(O); retum(n + func(n – 1));} /* end of func */

Write an iterative function to accomplish the same.

(b)Explain the working of a simple queue.

(c)Write a recursive function fact(n) to find the factorial of an integer. Diagrammatically explain, how the stacking and unstacking takes place during execution for fact(4)

**PART-B**

5(a). What is a linear linked list? Write the algorithm to add an element to the front of the list.

(b)What are the advantages and disadvantages of representing a group of items as an array versus linear linked list?

(c)Write the following C routines for the dynamic implementation of a linked list: NODEPTR is of type pointer to a node.

i) void insertafter(NODEPTR p, int x) which inserts a node with information x after a node pointed to by p.

ii) void place(NODEPTR *plist, int x) which inserts a node with information x at a proper position within the linear linked list pointed to by *plist. The list is assumed to contain information in the increasing order.

6 (a). What is a circular list? Explain with a diagram.

b. Compare linear linked list and doubly linked list, with diagrams.

c. Give the C implementation of stack as circular list.

7(a) With reference to the b-tree in Fig.Q7(a), give the three traversals

Fig.Q 7(a)

b.( i) Define strictly binary tree. Is the tree in Fig.Q7(a), a strictly b-tree.

(ii) Define almost-complete b-tree. Is the tree in Fig.Q7(a), an almost complete b-tree.

c.With reference to the dynamic node representation of b-tree, write the following C routines:

(i) NODEPTR maketree(int x) which creates a node with information x.

(ii) Void setleft(NODEPTR, int x) which sets a node with contents x as the left son of the node pointed to by p.

8 (a) With an example, show how a list can be represented as binary tree.

b. Define the following terms with reference to general trees: Father, son, brother, forest and ordered tree.

c. Give the node structure of an expression tree. Explain how the expression is evaluated.

plz read it