Punjab Technical University 2010-2nd Sem B.Sc Information Technology A0306 Data Strycture Through C - Question Paper

Roll No...........................

Total No. of Questions : 13]

Paper ID [A0306]

[Total No. of Pages : 03

(Please fill this Paper ID in OMR Sheet)

B.Sc. IT/DCA (202/204) (S05) (N) (Sem. - 2^nd) DATA STRUCTURES THROUGH C

Time : 03 Hours Instruction to Candidates:

1)    Section - A is Compulsory.

2)    Attempt any Nine questions from Section - B.

Section - A

(15 x 2 = 30)

a)    Define abstract data type?

b)    What is LIFO?

c)    Evaluate the following prefix expressions ++26 + - 1324 (similar types can be asked.)

d)    Compare features of queues and stacks.

e)    What are the characteristics of a graphs?

f)    How is it possible to insert different type of element in stack?

g)    What data structure would you mostly like see in a non recursive implementation of a recursive algorithm?

h)    When will you sort an array of pointers to list elements, rather than sorting the elements themselves?

i)    Parenthesis are never needed in prefix or postfix expression. Why? j) List out the areas in which data structures are applied extensively. k) How many null branches are there in a binary tree with 20 nodes?

l) List out few of the applications of tree data - structures? m) In an AVL tree, at what condition the balancing is to be done?

n) Write about heap sort.

o) Classify the Hashing functions based on the various methods by which the key value is found?

Section - B

(9 x 5 = 45)

Q2) Write a binary search algorithm. And use binary search to find the element 40, 11, 22, 30, 33, 40, 44, 55, 60, 66, 77, 80, 88, 99

Q3) Define the following terms:

(a)    Strictly a binary tree.

(b)    Complete binary tree.

(c)    Depth of a tree.

(d)    Binary search tree.

(e)    Almost complete binary tree.

Q4) What is the advantage of queue representing as list? For such representation write the insertion and deletion procedure.

Q5) What are the advantages of a doubly linked list over a singly linked list? Write a program that inserts a given value in to an ordered doubly linked list in to its proper positions.

Q6) Let A be an n x n matrix array. Write a module which

a)    Find the no of non zero elements in A.

b)    Find the sum of elements above diagonal.

c)    Find the product of PROD of the diagonal elements.

Q7) What is the data structures used to perform recursion?

Q8) What are application of Binary Search Trees?

Q9) What graph traversal algorithm uses a queue to keep track of vertices which need to be processed?

Q10) Write an algorithm to delete element in a heap?

Q11) Here is an array of ten integers:

5 3 8 9 1 7 0 2 6 4

Draw this array after the FIRST iteration of the large loop in a selection sort (sorting from smallest to largest)

Q12) Draw the directed graph that corresponds to this adjacency matrix:

Q13) Consider the quicksort algorithm. Can the arrays LOWER and UPPER be implemented as queues rather than stacks? Why?

A-281    3

Attachment: punjab-technical-university-2010-b-sc-information-technology-23605-1.pdf

Earning:   Approval pending.