# Data Structures with C June/July 08

Third Semester B.E. Degree Examination, June / July 08 Data Structures with C

Note : Answer any FIVE full questions.

1. (a) Explain the meaning of the following:

(i) int*P    (ii) int(*P)   (iii) intP(char*a[ ]).

(b).Write an appropriate declaration for each of the following situations :

(i)  Declare a function that accepts an argument which is an array of pointers to integer quantity and returns a character.

(ii) Declare a pointer to a function that accepts an argument which is a pointer to integer . array and returns a pointer to character.

(iii) Declare a function that accepts two arguments an array and pointer to integer, and returns float.

(c). A C program contains following declaration:

Static rat x – {10, 20, 30, 40, 50, 60, 70, 80};

i)    What is meaning of x?

ii)   What is meaning of (x + 2)?

iii)  What is meaning of *x ?

iv) What is meaning of (*x + 2)?

v)  What is value of *(x + 2)?

d.  Write a C program that will encode or decode multiple line of text. Store the encoded text within a data file. The program should include following features:

i)    Enter the text from keyboard, encode the text and store it in a data file

ii)   Retrieve the encoded text and display it in its encoded form

iii)  Display the size of file.

Encoding format is:

Original character ABC — Z a b — z

Encoded character D E F — C d e — c

2 a. What are bit fields? To what type do bit fields belong? How individual bits are are accessed? Explain with an example.

b.  Define a structure student consisting of name, age and marks as its members. Allocate memory dynamically for N students. Read the information about the students from keyboard. Write a function that displays the student information having highest marks among  students.

c.   What is union data type? How is a union member accessed? How a member of a union variable is assigned an initial value? How it differs from that of structure variable ?

d.  Write a C function min (array) that accepts the array of type integer and returns the address of minimum element of the array.

3 a. Write an algorithm for converting a fully parenthesized infix expression to suffix expression. Use the algorithm to convert following expression to suffix expression:

A + (((B-C)*(D-E)+F)/G)*(H-J)

b.  Write a C program to check whether a given string is palindrome or not using stack operation.        (

c.   Write a C program using function PEEP() that checks whether given element is present in the stack or not. Display the result of the search in the main program.

4 a. What is recursive function? Explain with an example what are its

b.  Write a recursive algorithm to search an element using binary search. Use this algorithm to find the element 3 in the array 1, 3, 7, 15, 21, 22, 36, 78, 95, 106. Show the tracing of the algorithm.

c.   Write a C function to implement Ackerman’s function defined as below: a(m, n) = n+1 if m = = 0 a(m, n) – a(m-l, 1) if m:^ 0, n = = 0 a(m, n) = a(m-l, a(m, n-1)) if m: – 0, n: = 0 Calculate result for a(2, 2).

5 (a). What is priority queue? Write an algorithm to insert an element into a

priority queue implemented using array.

b.  Write a C program to reverse the given single linked list. First pointer points to starting node of the list, and NULL value in the address of part of the node indicates end of list.

c.   Write an algorithm to insert a node into a circular queue implemented as a single linked list.

 6 a. Explain how a list can be implemented using array. What are its limitations? b. Write a C function to insert a node at a given position in a doubly linked list. c. Discuss the different ways of implementing binary tree structure. 7 a. Write a C function of traverse a binary tree in preorder and post order. b. Discuss with respect to tree data structure i) Threaded binary tree ii) Expression. c. Explain with example the method of interpolation search. 8 a. Write an algorithm to insert an element into binary search tree. b. Write an algorithm to sort a set of elements using address calculation sort. c. What is hashing? How hash clashes are resolved? Explain with an example.